Subject: [hybi] Limitations of the XOR-based masking

From: Willy Tarreau <[email-masked]>
Date: Sun, 9 Jan 2011 18:51:18 +0100

Hi,

I found that it was possible to sensibly reduce the difficulty in making
an intermediary forward a valid HTTP request despite masking. My feeling
is that the risk remains extremely low as it still requires a substantial
amount of garbage to be skipped to find a request, and that we have not
detected any such vulnerable intermediaries. Still I wanted to share my
experiments.

Abstract:

  The attack described here does not exploit any weakness in the mask
  generation algorithm, it only exploits the way the mask is applied.
  This means that the strongest algorithm such as HMAC will not provide
  any advantage over the simpler ones such as a simple 32-bit random
  number obtained from a valid source. The residual risk is still almost
  zero, so if the HMAC method is acceptable, then any cheaper method
  providing at least a 32-bit key is also acceptable.

The goal of the initially proposed XOR masking is to prevent an attacker who
controls a server from forcing a client to send known text to it via a caching
intermediary which could see an HTTP request there and unduly cache the
attacker server's response.

It has been proven that some intermediaries will consider the 101+Upgrade
response as a final response and expect a new request from the client. It has
also been speculated that some lazy intermediaries might even scan the request
stream to seek a request after some garbage, hence the need to mask all the
stream.

It is a fact that some intermediaries exist who accept HTTP/0.9 requests after
an HTTP/1.1 request. Apache is one of them. And it even accepts requests
composed only from a GET method followed by a line feed, without resource name.
That might come from back in the old days where it was suggested that by default
the resource was "/".

What this means is that it's enough to send the 4 bytes "G", "E", "T", LF to
Apache for it to see a request. Even better, Apache rewrites the request as
a perfectly valid HTTP/1.1 request when forwarding it, which means that those
4 bytes are completely enough to fool a less lazy downstream cache :

  GET / HTTP/1.1
  Host: 10.8.3.1:8080
  X-Forwarded-For: 127.0.0.1
  X-Forwarded-Server: dummy-host.example.com
  Connection: Keep-Alive

This has several impacts :

1) A lazy intermediary which accepts the same requests as Apache, but which
   would search them anywhere in the stream could reformulate it as a plain
   valid request to next hop.

2) Even if the intermediary does not scan for the request anywhere in the
   stream, if we put the random key at the beginning of the stream, 1 time
   on 4 billion a random key will match "GET\n".

Note1: Apache does not expect a second request after a 101 and is not fooled
       by this issue.

Note2: It could probably be accepted that 4 billion connections to make a
       client emit such a request is high enough not to care more about the
       issue.

Hence it was interesting to see how the XOR-based masking could be abused to
make a client emit "GET\n" in less than 4 billion connections, regardless of
the algorithm used to build the masking key.

The principle is to make the client emit many incremental 32-bit values, hoping
that "GET\n" will appear soon enough. In theory, such a pattern should happen
every 2^32 patterns, which is every 16 gigabytes. This is far too much to
expect from a client to pass through a server to hope it will spot anything
useful. However, we have a way to reduce the analysis to two consecutive
phases each of the complexity of the square root of the pattern space (65536).

Since the currently discussed masking method involves a fixed mask which is
repeated over the stream, it is possible since the beginning of the stream
to determine how long it will take so a "GET\n" appear.

The fact that we're using a 160-bit mask means we can pack 5 of such 32-bit
patterns in a mask, then multiply by 5 the chances to see a "GET\n" from a
single pattern.

The client will then build a single frame composed of 5 times the same pattern,
then incremented 65536 times.

The server will check the input stream, looking for the bytes "G" and "E".
If those bytes do not appear, it will terminate the connection because it
means this connection will require too many blocks to get the correct values.

The 160-bit mask offers us the ability to find the required pattern a lot
faster, because in each connections, this fixed mask can in fact be seen as 5
indepedant 32-bit masks. The net effect it that it divides by 5 the number of
required connections to get the expected bytes (in practice, it is possible to
achieve the same optimization with a smaller mask, it just requires the client
to send multiple different patterns). On average, 65536/5 = 13107 connections
are required to get a candidate connection.

If the server finds that the XOR mask will make "G" and "E" appear, then it
reads the stream so that the client emits all possible combinations of 3rd
and 4th chars, which means that at most 20*65536 = 1.3 Megabytes are required
once a candidate connection is found.

The ws-attack program contains both the client and the server code. For the
sake of simplicity, it does not do any networking, but it is designed with
clearly distinct parts which communicate via a sequentially accessed buffer,
so that the roles are more easily identifiable and both could be split if
required.

Results :

   The program can be downloaded at http://1wt.eu/websocket/ws-attack.c

willy@pcw:~/c$ time ./ws-attack 
Found pattern 'GET\n' at block 172226 after 6615 connections and 1469504 bytes sent

real    0m0.030s
user    0m0.032s
sys     0m0.000s
willy@pcw:~/c$ time ./ws-attack 
Found pattern 'GET\n' at block 207343 after 16071 connections and 1696448 bytes sent

real    0m0.069s
user    0m0.068s
sys     0m0.000s
willy@pcw:~/c$ time ./ws-attack 
Found pattern 'GET\n' at block 150470 after 95 connections and 1313024 bytes sent

real    0m0.003s
user    0m0.000s
sys     0m0.004s
willy@pcw:~/c$ time ./ws-attack 
Found pattern 'GET\n' at block 139582 after 28577 connections and 1996592 bytes sent

real    0m0.119s
user    0m0.116s
sys     0m0.008s

Conclusion :

Between 1.3 and 1.9 MB of framing data were required to get the expected
request the masking method was supposed to prevent from appearing.

A sliding self-regenerating mask would only make it slightly harder for the
server to decide upon accepting or rejecting the connection, because once it
gets the seed, it can locally simulate the emitted stream to find whether the
pattern will appear or not, but the improvement is not significant.

All in all, we see that we still need the client to send megabytes of data
to make a short request pop up. It is extremely unlikely that any caching
intermediary would skip over that amount of data to spot a valid request, and
it is contrary to the principle of lazyness because implementing such one is
a lot harder than making it do the right thing. BTW, no such intermediary has
yet been detected nor identified.

All the issues always converge to the same point : avoiding the LF character
(and possibly the CR) in the WS stream. But that's not easy or it requires
more expensive escaping or encoding (eg: base64).

Proposals :

 1) keep the XOR-based masking with a simpler key generation algorithm to
    keep the per-frame masking cost low. An improvement might also consist
    in avoiding the LF character in the key.

 2) use a more expensive LF-less masking such as base64, but this one must be
    optional.

 3) escape the LF character and define an escape character which must also be
    escaped itself. It is cheaper network-wise, but more expensive on the
    client side where the stream must be read once to count the LFs before
    being encoded and emitted.

 4) use Dave Cridland's idea of inserting an invalid HTTP request before the
    beginning of the stream. The request should remain simple and short with
    the goal to quickly fail.

My personal suggestion would be stay in line with the progress that was done
and to go for #1.

Regards,
Willy

---

From: Andy Green <[email-masked]>
Date: Sun, 09 Jan 2011 18:41:46 +0000

> My personal suggestion would be stay in line with the progress that was done

Congratulations dude for doing that work, making it repeatable by 
providing code and identifying the tools used.

Although there's still no broken intermediary identified as you pointed 
out twice, otherwise this poured out a lot more facts and logic than 
heretofore.

Options 1 - 3 kill or reduce the chance of zerocopy, 4 leaves that open. 
  For that reason 4 sounds like the best guy to me.

Is the attack that it defeats is enough for the browser guys?

Is there anything otherwise wrong with Dave's idea, it's really simple 
and lightweight and leaves the rest of the current draft intact.

-Andy

---

From: Salvatore Loreto <[email-masked]>
Date: Sun, 9 Jan 2011 20:32:01 +0100

> and lightweight and leaves the rest of the current draft intact.
Hi Andy,

as officially announced yesterday 
(http://www.ietf.org/mail-archive/web/hybi/current/msg05677.html)
the consensus expressed (a strong consensus I would say) by the 
strawpoll was for adopt an handshake based on GET+Upgrade+masking.

so please,
just accept the fact the consensus is to go for masking!

/Sal

---
Salvatore Loreto
www.sloreto.com

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 10 Jan 2011 07:52:50 -0800

> means this connection will require too many blocks to get the correct values.

Nice observation.

I haven't gotten too much sleep but...

As I understand your attack, the way this works is that you're
exploiting the fact that
the server gets information about the repeating mask to shut down unproductive
byte sequences before they have been transmitted over the wire. This makes sense
if you think that the network transmission is the rate limiting step.

The obvious countermeasure to this is to ensure that the server
doesn't learn anything
useful prior to receiving the whole packet. This can't be done with a
fixed mask for the
reasons you indicate but can be done with a generated mask, I believe.
Consider the
packet structure (omitting most framing bits)

AES-CTR(K_msg, Payload) || K_msg

In this case, no matter how much information the attacker has about
payload byte i,
he doesn't learn anything useful about expected ciphertext
(transmitted) byte i+1
until the key is received (this is by definitional properties of
AES-CTR). So, the bytestream
on the wire is indistinguishable from random, precluding the attack
you describe.

The major cost is that an ordinary server cannot start processing the
message until the per-msg
key is received at the end, but since we've already disclaimed most
streaming modes
of operation (and the client can't stream anyway because of the need
to commit to the
packet contents), this seems like a relatively minor cost.

This attack seems to me like it makes full-length masking more attractive.

Best,
-Ekr

> _______________________________________________
> hybi mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/hybi
>

---

From: Bjoern Hoehrmann <[email-masked]>
Date: Mon, 10 Jan 2011 18:12:27 +0100

>detected any such vulnerable intermediaries. Still I wanted to share my

I think there are a couple of problems with your attack, but while Adam
Barth is evaluating whether we can make progress by sending many mails
without contributing any new information, it seems better to be brief.

As I understand it, you are saying by using many connections you can
reduce the amount of data that needs to be sent to make a pattern appear
on the wire. You can't make as many connections as you seem to need to
make much of a difference, because clients that can be controlled by
untrusted parties will have measures against that to prevent probing
and denial of service attacks.
-- 
Björn Höhrmann · mailto:[email-masked] · http://bjoern.hoehrmann.de
Am Badedeich 7 · Telefon: +49(0)160/4415681 · http://www.bjoernsworld.de
25899 Dagebüll · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 10 Jan 2011 19:25:09 +0100

Eric,

I'm not opposed to sending the key after the masked data, but I don't
see how that can be done with masked frames.
The receiver will need to see the frame, so they can see the length,
so they can find the key.  If the frame is masked, the you wont be
able to find the key.

But, (pushing my normal barrow), I see no reason why we could not
switch the extension data to be after the payload data in a frame.
With fragmentation, we should always be able to process complete
frames.

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 10 Jan 2011 18:59:52 +0000

I'm not sure precisely what you mean by "masked frames". If I were king, things
would look like this:

- length
- masked portion
- key

With everything else being packed into the masked portion.

I agree that length should not be masked.

-Ekr

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 10 Jan 2011 20:19:53 +0100

> With everything else being packed into the masked portion.

Well we are not that far apart, as was proposing

 - flags/opcode
 - length
 - masked portion
 - key (in extension data)

although as pointed out in a separate thread, that ordering makes our
63 bit length a bit of overkill.

As I was an advocate for smaller frames and fragmentation, I'd have no
issue with reducing the max frame size so that the key could be sent
afterwards.   But I see no will to revisit framing, so that leaves us
with:

 - flags/opcode
 - key (in extension data)
 - length
 - masked portion

is that really that far from what you have proposed?

Plus if the masking is an extension then objections to cryptographic
masking are less.

---

From: John Tamplin <[email-masked]>
Date: Mon, 10 Jan 2011 14:31:14 -0500

>> means this connection will require too many blocks to get the correct values.

This issue was raised some weeks ago -- the answer is simply to not
allow the client to alter the message after it has been handed off to
the network layer.  Even if some streaming API were exposed to JS, you
would send a message fragment in its own frame when the buffer filled
up -- the key from that frame would be useless for the attacker for
the next frame.  If one day JS adds the ability to send large byte
buffers, the browser will just have to enforce copy-on-write or some
similar mechanism to avoid letting the JS code change the buffer after
the server might have received some portion of the message.

> packet contents), this seems like a relatively minor cost.

I think this is an unacceptable cost, as the server now must buffer
every frame completely before handing bytes off to the next higher
layer.  Currently, the JS client has no way to modify the message
being sent while the key for that frame is useful.  If it ever does
get that capability, it seems easier to address it there than to
cripple every server implementation.

-- 
John A. Tamplin
Software Engineer (GWT), Google

---

From: John Tamplin <[email-masked]>
Date: Mon, 10 Jan 2011 14:36:32 -0500

> 63 bit length a bit of overkill.

Why does moving the key after the payload alter the utility of long lengths?

However, this also means that extension data cannot affect
interpretation of the payload data -- personally I am ok with that
because I think the interpretation of the payload data should be
controlled by the opcode, but during our earlier framing discussions
there were several who felt otherwise.  My main objection to putting
the key after the payload is that it requires buffering of every frame
from the client.  Aside from latency issues from the buffering, this
imposes a significant cost on servers handling many connections
simultaneously.

>  - key (in extension data)

The current framing has the length before the extension data.

> Plus if the masking is an extension then objections to cryptographic

If browsers are going to require it and Dave's statement about UK
crypto restrictions is correct, it would still limit the ability to
deploy infrastructure and server that are compatible with
browser-based clients (which initially will be the 99% case).

---

From: "Pat McManus @Mozilla" <[email-masked]>
Date: Mon, 10 Jan 2011 14:48:29 -0500

Breaking streaming by placing the key after the message is a cost out of
proportion to the benefit I see.

Heretofore masking has been a marginal cpu tax in exchange for a small
reduction in risk, but placing the key at the end of the message
sacrifices an important property of websockets. We should work to keep
that in place.

-- 
http://www.getfirefox.com/

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 10 Jan 2011 20:52:45 +0100

> Why does moving the key after the payload alter the utility of long lengths?

because you have to hold 2^63 bytes of data before you get the key
which you need to decode the data.
So you can't process the data as you go.

> The current framing has the length before the extension data.

oops yes.. but it's essentially the same.

---

From: Willy Tarreau <[email-masked]>
Date: Tue, 11 Jan 2011 00:09:55 +0100

Hi Eric,

> if you think that the network transmission is the rate limiting step.

Yes that was the asumption.

> on the wire is indistinguishable from random, precluding the attack

I also thought about that possibility, but it's clearly unusable on
large frames due to the need to buffer everything before taking the
simplest decision. Also, many intermediaries will have to receive a
whole frame before forwarding it, adding up the serialization delays
for each hop. And the emitter would receive no indication of any
possible start of receipt which can be particularly annoying when
sending large frames (eg: user uploading a photo in a rich application).
Or we would have to define a new frame-based masking on top of current
framing which would not permit large frames at all and which would
always indicate all the information needed to parse and take decision.

This becomes quite complex and counter-efficient for what it tries to
solve :-/

Willy

---

From: "Joonas Lehtolahti" <[email-masked]>
Date: Mon, 10 Jan 2011 21:12:01 +0200

> I agree that length should not be masked.

How would the length be represented in the message? As a hypothetical  
example if the length is agreed to be big-endian 32-bit integer, then  
message length 1195725834 would be 'GET\n' if interpreted as series of  
ASCII characters.

Just as a little snack for thought.

- Joonas