Subject: [hybi] CRLF-less masking proposal

From: Willy Tarreau <[email-masked]>
Date: Sat, 15 Jan 2011 01:16:09 +0100

Hi all,

after some thoughts on the various proposals, I figured that increasing
the encoding slightly should not be a problem for small frames compared
to current proposals where they're inflated by at least 32-bit for the
key anyway, without offering total protection even at the beginning of
the stream. Thus it was worth giving a try to an encoding which totally
prevents an intermediary from finding an HTTP request *by design*.

Since the opinions on the current masking poll seem to be quite spread
apart, it looks like it's hard to satisfy everyone's concerns with the
proposed choices only, and maybe such a design would be less rejected
afterall, or maybe it can help someone find something better.

Regards,
Willy

----------

Here's a frame masking proposal which addresses various of the concerns that
were raised around masking and its justification :

  - ensure that no intermediary will find a request in the stream, at any
    position

  - maintain a cheap frame forwarding cost for intermediaries

  - maintain a cheap frame decoding cost for servers

The principle consists in preventing any CR/LF byte from appearing in the
stream. In order to achieve this, we'll use a 7 to 8 bit conversion and
all bytes on the wire will have the high bit set, thus preventing any of
the CR (13) or LF (10) or any other ASCII character from appearing in the
stream.

Since the framing itself may contain those bytes, the masking also applies to
the framing. At one point I thought we should keep the opcode unmasked, but I
figured that it could make the frame parsing more complex (eg: different code
for request and response, or for masked and unmasked frames).

It would still be nice to be able to disable the masking at some safe places,
and to support multiplexing at the same time. This proposal does not prevent
that since decoding the frame length is cheap. If we want to support both
masked and unmasked frames in the same stream later, we'll have to use one of
the reserved bits to indicate whether the frame is masked or not. The advantage
is that reserved bits always have a fixed position in the clear stream, as well
as they have one in the masked stream.

The masked stream format is rather simple. Each output byte is composed of its
lowest bits collected from one or two input bytes, and has the high bit set.
Bytes are read one at a time and sent one at a time. The lowest bits of input
byte B+1 are stored above the highest bit of input byte B :

    /* Encode 7 input bytes to 8, returns number of bytes read */
    int encode_stream(const unsigned char *src, unsigned char *dst)
    {
	unsigned int shift, rem;

	for (shift = rem = 0; shift < 7; shift++) {
	    rem += (*src++ << shift);
	    *dst++ = 0x80 | rem;
	    rem >>= 7;
	}
	*dst++ = 0x80 | rem;
	return shift;
    }

    /* Decode 8 input bytes to 7, returns the number of bytes written */
    int decode_stream(const unsigned char *src, unsigned char *dst)
    {
	unsigned int shift, rem;

	if (*src & 0x80 == 0)
	   return 0;
	rem = *src++ & 0x7F;

	for (shift = 0; shift < 7; shift++) {
	    if (*src & 0x80 == 0)
	        return shift;
	    rem += (*src++ & 0x7F) << (7 - shift);
	    *dst++ = rem;
	    rem >>= 8;
	}
	return shift;
    }

    uint64_t get_decoded_len(uint64_t encoded_len)
    {
	return encoded_len / 8 * 7;
    }

Note that we can even have direct-access functions to get some framing
information without decoding the whole stream :

    int get_opcode(const unsigned char *stream)
    {
	return stream[0] & 0x0F;
    }

    int get_length_8(const unsigned char *stream)
    {
	return ((stream[1] & 0x7F) >> 1) + ((stream[2] & 3) << 6);
    }

    int get_length_16(const unsigned char *stream)
    {
	int len;
	len = ((stream[2] & 0x7F) >> 2) + ((stream[3] & 7) << 5);
	len = (len << 8) + ((stream[3] & 0x7F) >> 3) + ((stream[4] & 15) << 4);
	return len;
    }

    uint64_t get_length63(const unsigned char *stream)
    {
	uint64_t len;

	len = ((stream[2] & 0x7F) >> 2) + ((stream[3] & 0x07) << 5);
	len = (len << 8) + ((stream[3] & 0x7F) >> 3) + ((stream[4] & 0x0F) << 4);
	len = (len << 8) + ((stream[4] & 0x7F) >> 4) + ((stream[5] & 0x1F) << 3);
	len = (len << 8) + ((stream[5] & 0x7F) >> 5) + ((stream[6] & 0x3F) << 2);

	len = (len << 8) + ((stream[6] & 0x7F) >> 6) + ((stream[7] & 0x7F) << 1);
	len = (len << 8) + ((stream[8] & 0x7F) >> 0) + ((stream[9] & 0x01) << 7);
	len = (len << 8) + ((stream[9] & 0x7F) >> 1) + ((stream[10] & 0x03) << 6);
	len = (len << 8) + ((stream[10] & 0x7F) >> 2) + ((stream[11] & 0x03) << 5);

	return len;
    }

    uint64_t get_length(const unsigned char *stream)
    {
	uint64_t len;

	len = get_length_8(stream);
	if (len == 126)
		return get_length_16(stream);
	else if (len == 127)
		return get_length_63(stream);
	else
		return len;
    }

These functions are just examples of what could be performed on the encoded
stream. They're quite not perfect and might even not compile at all due to
typos. If there is any interested in this proposal, I can work on them though.

The encoding has a cost, which is not much important for our main target which
are small frames. It is possible to encode short frames with a minimal amount
of bytes and make the stream end on the first byte without the high bit set.
It's possible though it would require a slightly smarter parser which must
always look at the last 8-byte chunk one byte at a time.

Below is a comparison between the following masking methods for various payload
sizes :
  - raw (unmasked)
  - XOR/AES/HMAC/any encoding with a 32-bit key prefixing the stream
  - this proposal padded to 8 bytes (% vs 32-bit)
  - this proposal in optimal format (% vs 32-bit)

Payload  Raw   32-bit key   7-to-8 padded  7-to-8 optimal
  0      2         6         8  (+ 33%)        3 (- 50%)
  1      3         7         8  (+ 14%)        4 (- 43%)
  2      4         8         8  (  =  )        5 (- 37%)
  3      5         9         8  (- 11%)        6 (- 33%)
  4      6        10         8  (- 20%)        7 (- 30%) 
  5      7        11         8  (- 28%)        8 (- 28%)
 	        
  6      8        12        16  (+ 33%)       10 (- 16%)
  7      9        13	    16  (+ 23%)       11 (- 15%)
  8     10        14	    16  (+  6%)       12 (- 14%)
  9     11        15	    16  (+ 11%)       13 (- 13%)
 10     12        16	    16  (  =  )       14 (- 12%)
 11     13        17	    16  (-  6%)       15 (- 12%)
 12     14        18	    16  (- 11%)       16 (- 11%)
 	        
 13     15        19        24  (+ 26%)       18 (-  6%)
 14     16        20	    24  (+ 20%)       19 (-  5%)
 15     17        21	    24  (+ 14%)       20 (-  5%)
 16     18        22	    24  (+  9%)       21 (-  5%)
 17     19        23	    24  (+  4%)       22 (-  5%)
 18     20        24	    24  (  =  )       23 (-  5%)
 19     21        25	    24  (-  9%)       24 (-  4%)
 	        
 20     22        26        32  (+ 23%)       26 (  =  )
 21     23        27	    32  (+ 18%)       27 (  =  )
 22     24        28	    32  (+ 14%)       28 (  =  )
 23     25        29	    32  (+ 10%)       29 (  =  )
 24     26        30	    32  (+  6%)       30 (  =  )
 25     27        31	    32  (+  3%)       31 (  =  )
 26     28        32	    32  (  =  )       32 (  =  )
 	        
 40     42        46        48  (+  4%)       48 (+  4%)
 50     52        56        64  (+ 14%)       60 (+  7%)
100    102       106       120  (+ 13%)      119 (+ 12%)
124    126       130       144  (+ 10%)      144 (+ 10%)
125    127       131       152  (+ 16%)      146 (+ 11%)

And so on... The suite converges towards +14.3% (8/7) compared to 32-bit keying
for large frames. Those comprised between 120 and 125 bytes are around +10-16%.

We can also note that for frames smaller than 20 bytes, the 7-to-8 encoding can
be smaller than 32-bit masking, and will always be smaller if the optimal format
is used.

All in all for the browser-to-server uses we're expecting, the network overhead
compared to other solutions remains quite low. For larger transfers in safe local
areas, we might want to disable the encoding to save network bandwidth. The CPU
usage will always remain low (and as recently discussed, network speeds increase
faster than CPU speeds so this tradeoff makes sense).

It is quite debuggable without any context as there is no per-session state to
maintain in order to decode the stream.

It is possible to quickly detect that raw HTTP is being fed into the framing
because there will be bytes without the highest bit set.

----------

---

From: Tomas Franzén <[email-masked]>
Date: Sun, 16 Jan 2011 15:32:51 +0100

This seems like a fantastic alternative to XOR and the encryption madness. Though I'd personally prefer Base64, I'm definitely willing to back this proposal if less overhead means more people accept it.

* Perfect masking - definite protection against CRLF
* Easy to understand and implement
* No concerns about randomness - it doesn't have to be random
* No concerns about export regulations

The only disadvantage I can think of is the very modest 14% overhead. Does anyone think this is a problem?

Tomas

On 15 jan 2011, at 01.16, Willy Tarreau wrote:

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

---

From: Adam Barth <[email-masked]>
Date: Sun, 16 Jan 2011 10:55:34 -0800

The main disadvantage of this approach only defends against the
attacks we know.  The reason we often use randomness in cryptography
is because it's much easier to reason about the properties of
uniformly random data.  Masking the attacker's data erases any control
the attacker has over the on-the-wire bytes.  With something like
base64, the attacker has a large degree of control even though the
attacker is restricted to a limited character set.

Adam

---

From: Willy Tarreau <[email-masked]>
Date: Sun, 16 Jan 2011 20:12:18 +0100

> attacker is restricted to a limited character set.

Agreed, but randomness is not the solution to everything. In the present
case, it would make some known dangerous patterns randomly appear from
time to time while a more controlled encoding will never make them happen.
So in fact, for *some* known issues randomness can be a worse solution
than something more controlled.

Regards,
Willy

---

From: Adam Barth <[email-masked]>
Date: Sun, 16 Jan 2011 11:53:55 -0800

> than something more controlled.

Honestly, that's a bunch of bunk.

Adam

---

From: Willy Tarreau <[email-masked]>
Date: Sun, 16 Jan 2011 21:05:00 +0100

> Honestly, that's a bunch of bunk.

Why ?

Simply send 4 billion different random patterns to Apache after the
handshake, and the one matching "GET\n" will be forwarded as a valid
HTTP request. And we're not talking about an attack, just random WS
connections to WS-unable intermediaries that will forward a request
instead of nicely failing.

In my opinion, there are uses for everything including crypto. And
there are cases where a perfectly controlled solution can sometimes
better fit the needs than just random mask-based crypto.

Regards,
Willy

---

From: Adam Barth <[email-masked]>
Date: Sun, 16 Jan 2011 15:34:10 -0800

> better fit the needs than just random mask-based crypto.

We've been over this Willy.  "GET\n" is not an attack.  The cost of
performing the attack doubles with each bit you add to the attack
string.  Anything even remotely interesting is wildly infeasible.
It's just simple math.

Adam

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 17 Jan 2011 06:45:41 +0100

On Sun, Jan 16, 2011 at 03:34:10PM -0800, Adam Barth wrote:
> We've been over this Willy.  "GET\n" is not an attack.

I simply disagree with you on this point. While it was speculated that
it was possible that an intermediary would try to skip garbage to find
a request, we still have not find such one and several of us have strong
reasons to believe they don't exist at all.

However I have given an example of intemediaries that accept "GET\n" as
a valid request and even turn it into a complete HTTP/1.1 request when
forwarding it. This one really exists, it's called Apache. And it's even
possible that other ones do exist.

Other participants will surely understand that I'm more concerned about
preventing an existing intermediary from finding a request where there
should not be one rather than trying to randomize a stream so that we're
sure an attacker cannot make a request appear where no known intermediary
looks for it.

Regards,
Willy

---

From: Maciej Stachowiak <[email-masked]>
Date: Sun, 16 Jan 2011 23:08:18 -0800

> sure an attacker cannot make a request appear where no known intermediary

To successfully pull off cache poisoning, you need to convince the intermediary that the request is being sent to the victim's host, not the attacker's host. This requires an attacker-controlled Host header. If the server thinks the request is being sent to the attacker's host, then no meaningful cache poisoning attack is possible.

Regards,
Maciej

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 17 Jan 2011 08:37:21 +0100

Hi Maciej,

On Sun, Jan 16, 2011 at 11:08:18PM -0800, Maciej Stachowiak wrote:
> To successfully pull off cache poisoning, you need to convince the
> intermediary that the request is being sent to the victim's host,
> not the attacker's host. This requires an attacker-controlled Host header.
> If the server thinks the request is being sent to the attacker's host,
> then no meaningful cache poisoning attack is possible.

No Adam proved the opposite in his paper, that was the real point of the
initial discussion BTW : there are intermediaries that only rely on the
destination IP address and which use the Host header as a cache index
key.

For instance, let's admit I'm the attacker, hosted at my-preferred-hsp.
This hosting provider has a front reverse proxy that acts like the ones
Adam has spotted in his study, which means that it does not route based
on the Host header. It supports HTTP/0.9 requests just like Apache, and
has a default host configured to match the provider's portal (which makes
sense in order to direct all unknown hosts to the point where he can
advertise his service).

Then by sending a "GET\n" after a successful 101 response over an already
established connection, the request would be turned into "GET / HTTP/1.1\r\n
Host: my-preferred-hsp\r\n\r\n" and my server behind it has control over
the response traffic.

I'm not making this up, this was precisely the point of Adam's paper.

Alternatively if we all agree that the risk of this appearing is quite low
and it's not our problem, then let's get away with this masking hassle. But
it looks like browser vendors will feel more comfortable with masking now
that we managed to scare them.

Regards,
Willy

---

From: Adam Barth <[email-masked]>
Date: Mon, 17 Jan 2011 00:44:00 -0800

> I'm not making this up, this was precisely the point of Adam's paper.

Please don't put words in my mouth.

Kind regards,
Adam

---

From: Takeshi Yoshino <[email-masked]>
Date: Mon, 17 Jan 2011 17:53:29 +0900

> sense in order to direct all unknown hosts to the point where he can
I couldn't understand this part well. What does "a default host" actually
means here? Could you please tell us the name of Apache directive/module for
better understanding?

Guessing from your explanation, maybe, a host header with it's value equals
to <default host> (e.g. welcome.my-preferred-hsp.com) will be added to a
request when the proxy receives a request toward unknown-IP (i.e. not in the
HSP's mapping), and the proxy forwards it to <default host> (e.g. the server
serving welcome.my-preferred-hsp.com). Right? Though it seems that you're
talking about intercepting proxy that routes only based on the destination
IP, without rewriting the destination IP we cannot guide the request to the
place where HSP can advertise the hosting service. Just adding host header
doesn't help.

> Host: my-preferred-hsp\r\n\r\n" and my server behind it has control over
Won't this request be forwarded to the server serving
welcome.my-preferred-hsp.com as I said above? Really Apache just extract
GET\n and keep receiving response from the attacker's host?

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 17 Jan 2011 10:17:55 +0100

> means here? Could you please tell us the name of Apache directive/module for

Just a ProxyPass directive out of a VirtualHost section.

> serving welcome.my-preferred-hsp.com). Right?

yes

> Though it seems that you're

That's not the point. The point is that we're adding masking because some
intermediaries have been detected whic only use the destination IP address
and don't forward based on the host header. However, they do cache based
on the host header. That means that the following handshake followed by a
data exchange over the same connection might help an attacker's server to
corrupt a cache :

   GET / HTTP/1.1
   Host: attacker.com
   Upgrade: WebSocket
   Connection: Upgrade

                            HTTP/1.1 101 Switching Protocols
                            Upgrade: WebSocket
   
   GET / HTTP/1.1
   Host: victim.com

                            HTTP/1.1 200 OK
                            <contents to inject into cache>
    
So we want to ensure that such intermediaries will not be abused by
such an HTTP-request looking stream after the handshake.

What we know till now :
  - some caches are vulnerable to the exchange above though we don't know
    which ones
  - some caches accept "GET\n" as a valid request even as the second one

So with that in mind we can't state for sure that a cache featuring both
combinations does not exist.

However we've not seen caches who happily skip garbage to find a request,
so I'm clearly not worried at all by anything looking like HTTP after
some HTTP-incompatible bytes or frames. The first bits of the initial
frames themselves might even be enough against this.

Regards,
Willy

---

From: Takeshi Yoshino <[email-masked]>
Date: Mon, 17 Jan 2011 19:24:11 +0900

> Just a ProxyPass directive out of a VirtualHost section.
Thanks, I checked that we can have Apache convert GET\n to e.g. GET /
HTTP/1.1\r\nHost: www.google.com\r\n\r\n with ProxyPass.

> data exchange over the same connection might help an attacker's server to

agreed

>  - some caches accept "GET\n" as a valid request even as the second one
What was not quite clear to me is that the proxy which converted "GET\n"
to "GET / HTTP/1.1\r\nHost: victim.com\r\n\r\n" is still asking some cache
behind it (or caching code inside itself) (which is targeted to be poisoned)
to keep talking with attacker.com. Your example above needs this assumption,
I think.
I cannot say that such software doesn't exist, but it doesn't sound
reasonable implementation.

Regards,
Takeshi

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 17 Jan 2011 11:47:18 +0100

> reasonable implementation.

In fact it's not *my* assumption, but such unreasonable implementations
were detected during Adam's experiment, which is what finaly drove us
to talk about masking. It is very reasonable to imagine that there could
be two successive layers, the first one just rewriting the request and
the second one doing cache.

To be honnest, I'm not much concerned by that because I consider that
having this issue happen once in 4 billion connections is not useful
enough to build a valuable attack. But what I'm stating is that if we
consider this to be a problem, then we must address it for real, not
just try to slightly reduce the probabilty of it appearing. Thus I'm
claiming that is we think that XOR on a 32-bit mask is not enough,
then we must use a mechanism that completely prevents any request from
ever appearing.

That's why I'm in favor of 1) simple XOR masking, 2) base64/128 as an
alternative.

Regards,
Willy

---

From: Dave Cridland <[email-masked]>
Date: Mon, 17 Jan 2011 11:24:06 +0000

> string.  Anything even remotely interesting is wildly infeasible.

Not the cost doubling. The probability halving. *That* is the simple  
maths involved. This would in turn double the cost of a dedicated  
attack, of course, but it merely halves the probablility of the same  
vulnerability being triggered accidentally.

Willy's argument is that one can reduce the probability to 0 for all  
the attacks described, and a zero probability must - by even simpler  
maths than your simple maths - be less likely to occur than a  
non-zero probability.

Now, if you extend your scope to suggesting that there are many  
"dangerous" bit-patterns possible and you don't want to risk the  
attacker being able to generate them, then the more bit patterns  
there are, the greater the probability of triggering them via random  
noise.

By describing the possible bit-patterns, we can construct a purely  
deterministic masking by which an attacker cannot produce that bit  
pattern on the wire, still reducing the probability of this occuring  
by chance to 0.

I doubt he'll make any headway on this argument, but it's entirely  
sound logic, and much simpler maths than yours.

However, he won't make any headway because you have the trump card of  
not actually explaining what these dangerous bit-patterns might be -  
we seem to have reached the point where Willy can propose a masking  
which entirely prevents any HTTP request appearing in the clear,  
which can be verified by a server, and which therefore not only  
prevents all described (and conjectured) attacks, but is also  
impossible to produce a weak implementation of, and it's still shot  
down because it "only defends against the attacks we know".

Arguing that your masking is somehow proof against something nobody's  
thought of yet is beyond the theoretical and well into the  
philosophical - I fail to see why things you haven't thought of are  
more likely to be real than things Willy hasn't thought of. Are you  
arguing that Willy's solution must be less good than yours because he  
might have more imagination?

Dave.
-- 
Dave Cridland - mailto:[email-masked] - xmpp:[email-masked]
  - acap://acap.dave.cridland.net/byowner/user/dwd/bookmarks/
  - http://dave.cridland.net/
Infotrope Polymer - ACAP, IMAP, ESMTP, and Lemonade

---

From: Yuta Kitamura <[email-masked]>
Date: Mon, 17 Jan 2011 22:11:53 +0900

1) I don't think you have successfully shown "GET\n" is an attack. I think
you need to demonstrate that you can do something meaningful by sending
random bytes (or, by sending "GET\n" after a few gigabytes of random bytes)
in the real world configuration and measure how many percentages of users
are affected by this problem. What you have been saying is just a theory and
does not sound realistic to me.

2) BASE64 is a step backward and I'm opposed to it. As Adam mentioned, we
should not let attackers control the bytes on wire. What we need to do is to
find a generic approach to address a class of problems (cross-protocol
attacks). Avoiding "\r\n" does not sound right because it just tries to
solve a problem specific to HTTP and does not address any other attacks to
non-HTTP protocols.

Regards,
Yuta

---

From: Dave Cridland <[email-masked]>
Date: Mon, 17 Jan 2011 13:56:21 +0000

> does not sound realistic to me.
It seems to me you've misunderstood Willy's argument. He's saying  
that an initial GET\n may be an attack, on the assumption that an  
initial full request is. He's argued against a '"GET\n" after a few  
gigabytes of random bytes' being a real issue for some time - indeed,  
he's argued that it'd be impractical to write any caching  
intermediary which would recognise a request after virtually any  
non-HTTP traffic.

Given that the only test "in the real world configuration" thus far  
performed has demonstrated there already exists a way to prevent all  
HTTP attacks across the sample without masking, using this argument  
to demonstrate that masking using random data is therefore required  
places you on extremely shaky ground.

> solve a problem specific to HTTP and does not address any other  

No, no, no.

The argument is:

a) Specific bit patterns on the wire can cause harm.

b) It seems probable that similar bit patterns may cause harm.

c) We should not allow attackers to produce the bit patterns in (a)  
or (b).

d) We should allow an attacker no influence on the output, and the  
output must be indistinguishable from random noise.

Now, (d) does not follow from (c), however much people repeat the  
fallacy. It is merely a way of making a deliberate attack very  
difficult.

Willy Tarreau's proposal implements (c), and in fact would protect  
against any other cross-protocol attacks where the target protocol  
relies on the presence of *any* 7-bit octets on the wire. I don't  
think any protocols remainins are vulnerable - but then, it's really  
not clear to me how one might mount a cross-protocol attack where the  
initial handling *has* to look like HTTP traffic, except for a  
cross-protocol attack on HTTP.

On the other hand, squirting purely random noise at a server will  
crash a large number of implementations, particularly of OSI based  
protocols. This in itself isn't an argument against the random  
masking, incidentally, because you'd need to find an X.400 server,  
say, which intially spoke HTTP, and moreover responded correctly to a  
WebSocket upgrade. But given that we're waaay into hypothetical  
territory, maybe I should insist that any design we do is validated  
not to be possible to use for cross-protocol attacks on X.400 MTAs.

Dave.

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 17 Jan 2011 14:59:12 +0100

On Mon, Jan 17, 2011 at 10:11:53PM +0900, Yuta Kitamura wrote:
> 1) I don't think you have successfully shown "GET\n" is an attack.

I don't say it's an attack, it's a request. Others have proven that a
request might become an attack with some intermediaries.

> I think

Oh I'm certain that this request (or any other one) after even 1 byte (eg:
\xFF) is not a valid request anymore. But it was decided differently here.
If you want my opinion, even the raw frames without any form of masking are
enough against faulty intermediaries.

> does not sound realistic to me.

No, it's not theory. If we put a random pattern at the begining of the
handshake, 1/2^32 times this random pattern will match "GET\n". By
sending that just after a first request, we'll get a second request
to be processed by some intermediaries. The raw framing does not cause
this to happen because simply having the high bit set in the first byte
is enough to prevent an HTTP parser from matching a valid HTTP method,
or "HTTP" in the response.

> should not let attackers control the bytes on wire.

The original design does not let them control *all* bits. The proposed
masking methods lets them have *any* pattern given a sufficient number
of attempts.

> What we need to do is to

The problem *is* specific to HTTP because the HTTP compliance of the whole
chain as well as the WebSocket compliance of the end point are verified by
the handshake. Just send a WS connection to an SMTP server, you won't get
any valid response because the maths involved in the response nonces can't
happen without a WS-specific computation.

The remaining part we're trying to solve is that some intermediaries might
be waiting for a second HTTP request after the WS handshake, so that clearly
is HTTP specific.

Regards,
Willy

---

From: Joe Mason <[email-masked]>
Date: Mon, 17 Jan 2011 11:32:16 -0500

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Adam Barth
>

It is, however, a random connection failure. We want to avoid those too.

The obvious solution that addresses all concerns and satisfies nobody is to use an XOR or AES mask, and then use Willy's algorithm to strip CRLF from the random data.  I'm sure everyone's thought of that and dismissed it as being overkill already, but I want to air the idea explicitly.

Joe

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: Maciej Stachowiak <[email-masked]>
Date: Mon, 17 Jan 2011 09:42:33 -0800

On Jan 17, 2011, at 3:24 AM, Dave Cridland wrote:

> Not the cost doubling. The probability halving. *That* is the simple maths involved. This would in turn double the cost of a dedicated attack, of course, but it merely halves the probablility of the same vulnerability being triggered accidentally.

It's not a security vulnerability if it's triggered accidentally, though it may be a bug.

Regards,
Maciej

---

From: Maciej Stachowiak <[email-masked]>
Date: Mon, 17 Jan 2011 09:45:06 -0800

> It is, however, a random connection failure. We want to avoid those too.

I doubt it. It's easy to set up an experiment to see if different masking variants have different success rates though.

Regards,
Maciej

---

From: Maciej Stachowiak <[email-masked]>
Date: Mon, 17 Jan 2011 09:55:32 -0800

> destination IP address and which use the Host header as a cache index

The paper did not prove the opposite. It showed that some proxies which route by IP but cache by Host are vulnerable to cache poisoning. You need an attacker-controlled Host header to poison the cache of your victim's choice.

> Host: my-preferred-hsp\r\n\r\n" and my server behind it has control over

Should this scenario occur, you can temporarily deface your hosting provider's homepage, but you can't mount cache poisoning on an arbitrary host of your choice. A more realistic attack scenario would be at minimum "GET / HTTP/1.1\nHost: a\n", which is 22 characters, or 176 bits. That's granting the generous assumption that you're attacking a single-character host. 

> I'm not making this up, this was precisely the point of Adam's paper.

I don't believe that was the point of Adam's paper at all.

> that we managed to scare them.

Being dismissive of security concerns doesn't help your case.

Regards,
Maciej

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 17 Jan 2011 19:53:18 +0100

On Mon, Jan 17, 2011 at 09:55:32AM -0800, Maciej Stachowiak wrote:
> Should this scenario occur, you can temporarily deface your hosting provider's homepage, but you can't mount cache poisoning on an arbitrary host of your choice.

I never said the opposite. But I find it surprizing that we should consider
that this is not a security issue to take into account while the ability
for someone to make a request appear after several gigabytes of garbage
when we're already sure that noone will look there is an issue...

> Being dismissive of security concerns doesn't help your case.

I'm not being dismissive, I'm trying to be pragmatic. We are focusing on
issues that nobody can seriously describe in details, but the ones that
are possibly smaller but more realistic because they involve existing
components are dismissed.

Sometimes I feel like we're thinking "well, let's have crypto there, what
issue could we solve with it, and under what condition might the issue
appear ?".

Crypto should not be a goal but a solution. Till now there is no much
problem.

Regards,
Willy

---

From: Jamie Lokier <[email-masked]>
Date: Mon, 17 Jan 2011 19:48:24 +0000

>From a user browser security POV, I would also worry about the
numerous script proxies and other 'personal protection' cheap
products, that presumably people install onto client machines and
client gateways (affecting other people) from time to time.  Most of
them seem to advertise themselves as ad-blockers and such.  From the
few HTTP parsers whose code I've read, I don't have a lot of
confidence in them not doing something overly-"helpful" like Apache.

There are a great many very permissive, sloppy HTTP parsers around,
many of them skipping whitespace anywhere, ignoring case, some even
ignore the method name (I've seen one that tests "is it POST?
otherwise assume GET"), and matching using regular expressions with no
error checking, or the most minimal C that works.

It would be nice if such things weren't client side proxies.  But a
quick Google just now revealed (a) it's really easy to write and
deploy quick'n'dirty proxies in Perl, Python etc.  I have no doubt
some of these are used on networks because the admin felt the need,
where the browser user can't be blamed.  (b) Google led me straight
away to a list of 37 proxies written in Python linked from one page,
most of them client-side.  Many of them billed as ad-blockers and
such, so possibly targetting users who don't write code themselves.

I have no idea how many are deployed, or how many are deployed on
gateways affecting users who didn't ask for it.

Where they are installed on the client or client's local network,
there's a fairly good chance they will be forwarding to one or even
two transparent caching proxies on the way to the origin server (ISP's
forward proxy and site's reverse proxy).

Regarding the Apache configuration as a client side transparent proxy:
I know this has existed; I've seen it used on a client network gateway.

It's easier to configure than Squid, quite versatile, and fits well if
you're using Apache already on the gateway machine (which seems to be
very common in small business environments).  Google reveals that
Apache does get used in that way; I don't know how much.

A 'default host' is explicitly configurable, so presumably some people
do use it.  From the online docs of Apache httpd 2.2:

   ProxyDomain Directive
   Description:	Default domain name for proxied requests
   Syntax:	ProxyDomain Domain
   Context:	server config, virtual host
   Status:	Extension
   Module:	mod_proxy

   This directive is only useful for Apache proxy servers within
   intranets. The ProxyDomain directive specifies the default domain
   which the apache proxy server will belong to. If a request to a host
   without a domain name is encountered, a redirection response to the
   same host with the configured Domain appended will be generated.
   Example

   ProxyRemote * http://firewall.example.com:81
   NoProxy .example.com 192.168.112.0/21
   ProxyDomain .example.com

I don't know if by "redirection" that means an internal redirect
(i.e. converting the request internally before forwarding) or a 3xx.

Anyway, Willy has shown that Apache does convert "GET\n" and forward
in some cases; maybe different from the above one.  If Apache uses the
system hostname for that, it's moderately likely to be the domain of
a web site, internet-facing or intranet.

-- Jamie

---

From: Jamie Lokier <[email-masked]>
Date: Mon, 17 Jan 2011 20:00:31 +0000

> or "HTTP" in the response.

Fwiw, there are proxies around whose HTTP parser will match the first
byte with the high bit set as part of the method name.  Hopefully it
doesn't matter.

I would really like to see a better effort to "fast fail reliably"
with bogus proxies so it's quicker to fallback to a different method
than WebSocket, and a CRC, MAC or something to protect against any
which mostly forward the data (so connection appears to work) but
randomly mangle it later.

> masking methods lets them have *any* pattern given a sufficient number

The solution to both concerns is to *combine* strong hashing (AES-CTR
etc.)  *and* escaping plausible HTTP request character sequences.

I don't like that because I think it's a strange thing to be
encrypting for some kind of half-security when you've selected *not*
to use a secure connection (i.e. not TLS).

But it's the technical solution to both concerns, and it has negligable
overhead (compared with AES or SHA in the first place.)

> be waiting for a second HTTP request after the WS handshake, so that clearly

I suppose you could make a WebSocket connection to the FTP command
port going through a NAT router that forwards all the bytes, so the WS
handshake succeeds, and then later mangles a few bytes because it's
substituting anything that looks like an text IP address in the stream.

Of course you wouldn't connect to the FTP port, but you might use some
other port than a NAT just happens to think is a good one to mangle
because it's also used by something else.

-- Jamie

---

From: Jamie Lokier <[email-masked]>
Date: Mon, 17 Jan 2011 20:20:42 +0000

> not to be possible to use for cross-protocol attacks on X.400 MTAs.

The main things seems to be HTTP proxies or pure data forwarding
proxies which look for something to mangle (i.e. NATs do this, as
would broken implementations of CONNECT in HTTP proxies, if there are any.)

If the server isn't forwarding what it receives to another server, and
doesn't do the handshake calculation, than it's unlikely to be
vulnerable - at least, no more than it is to regular HTTP requests
sent to that port.

The vector of attack which people are (rightly) concerned about is
only browsers running server-supplied scripts, as far as I can tell.
Right now all web infrastructure can largely count on browsers only
sending valid-looking HTTP requests, so they are safe from this sort
of attack as long as that can't be confused with what the server
really speaks.

I'm still not sure why sending a valid-looking "decoy" HTTP request
after CONNECT (such as OPTIONS * with Connection:close and
Content-Length:large) hasn't caught on as an idea, as I would expect
just about any non-HTTP server, or non-WebSocket HTTP server, to be
quite robust when receiving one of those (otherwise it would be
vulnerable to existing non-WebSocket attacks.)

ps. Thinking about that just made me realise the CONNECT-based WS
handshake we're planning doesn't work across two or more proxies,
which is very common (client gateway and server loadbalancer) :-( sigh.

-- Jamie

---

From: Jamie Lokier <[email-masked]>
Date: Mon, 17 Jan 2011 20:40:35 +0000

> It's not a security vulnerability if it's triggered accidentally, though it may be a bug.

If it can be triggered accidentally with more than 1/cryptosecure
probability, then it can be triggered by deliberately a well-placed
malicious script spawning WebSockets at the maximum rate in the
background (maybe WebWorkers, maybe not) on every client
(i.e. hundreds of thousands on some sites) that's visiting pages
containing the script, running for as long as the attacker has
patience (i.e. months.)

That's a *lot* of connections.

It doesn't even have to ammount to a DDOS on one site, as that kind of
attack could target a cross-section of servers, looking for any
opportunity to poison/misdirect a client while diffusing the load
across sites to hide its intensity.  A bit like the way port scanners
target random IPs; they don't care which one they get.

OF course there is some randomness level above which we can assume
it's so unlikely that it doesn't matter (like strong crypto).  On the
current internet, 2^32 is not enough against a concerted attack; 2^40
is a (just about) plausible attack figure if a script gets onto
popular sites, performs a smart diffused attack, and isn't noticed for
a month, say.  That's on today's internet.

-- Jamie

---

From: Dave Cridland <[email-masked]>
Date: Mon, 17 Jan 2011 20:54:02 +0000

> which is very common (client gateway and server loadbalancer) :-(  

Hence my argument to use a GET+Upgrade followed by a dummy CONNECT,  
which combines both valid HTTP to negotiate the WebSocket, plus a  
dummy CONNECT that's known to defend against further interpretation.

But, the argument goes, this isn't needed if you do masking, and  
masking is based on maths, rather than experimental testing.

Dave.

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 17 Jan 2011 23:21:06 +0100

Hi Jamie,

> byte with the high bit set as part of the method name.  Hopefully it

I agree there are and that does not matter because we're concerned about
the risk of caching, and a cache must consider the method.

> than WebSocket,

In fact it's not easy at all, considering the various behaviours that
can be encountered, in part because of those who consider 101 as a 1xx
and wait for a second response. However, I expect those ones to quickly
disappear once WS is standardized because they'll quickly get spotted
as the faulty part in many chains.

> and a CRC, MAC or something to protect against any

That's in fact where the Hello frames could sensibly help.

> etc.)  *and* escaping plausible HTTP request character sequences.

It might be one, but what are we making up for a clear text protocol ?

> to use a secure connection (i.e. not TLS).

exactly....

> overhead (compared with AES or SHA in the first place.)

Unfortunately, not so negligible either. My measurements have shown a
performance limit as low as slightly less than 1 Gbps on a Core2quad
3GHz. This machine is already able to forward 10 Gbps of HTTP traffic
without sweating. That means that it will make it quite hard or expensive
to support high data rates on frontend equipments (NAT router boxes, load
balancers, etc...).

> substituting anything that looks like an text IP address in the stream.

I see your point, but anyone using the FTP port as a transparent port is
looking for trouble. Other protocols such as HTTP, SMTP, and maybe a few
others are not doing checksums and would possibly experience issues as
well if run over port 21.

Regards,
Willy

---

From: Bjoern Hoehrmann <[email-masked]>
Date: Mon, 17 Jan 2011 23:33:11 +0100

>vulnerable to existing non-WebSocket attacks.)

Sending a valid-looking request may make an intermediary think that the
connection has not in fact been upgraded, so this may end up being less
secure than not sending a decoy.

>which is very common (client gateway and server loadbalancer) :-( sigh.

The methods the working group seems to be considering are WEBSOCKET,
GET, and OPTIONS, not CONNECT, as far as I am aware.
-- 
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: Joel Martin <[email-masked]>
Date: Mon, 17 Jan 2011 16:46:25 -0600

> to support high data rates on frontend equipments (NAT router boxes, load

Do you think you might have the opportunity to do the same perf tests on
base64 and 7-bit/8-bit in order to compare to the performance of the masking
options?

Thanks,

Joel Martin

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 17 Jan 2011 23:53:09 +0100

> base64 and 7-bit/8-bit in order to compare to the performance of the masking

Yes, it's easy to do, but it's possible that I won't have time to do that
before next week-end.

Regards,
Willy

---

From: Jamie Lokier <[email-masked]>
Date: Tue, 18 Jan 2011 01:06:13 +0000

> dummy CONNECT that's known to defend against further interpretation.

On the face of it, that sounds a reasonable plan.

Why I was only looking a few hours ago at a proxy toolkit (CPAN/Perl's
HTTP::Proxy) which ignores the Upgrade header.

What about sending repeated CONNECTs with WS negotiation headers,
until the reply says it's got through to a final WebSocket server
with a proper handshake?  I think that's fair game for pedantic HTTP
semanticists if we declare that the WS server _is_ logically a HTTP
proxy known as such to the client.  It's even got a standardised place
to authorise the connection, if that is relevant.

> masking is based on maths, rather than experimental testing.

Obviously masking doesn't help if the objective is to definitely work
or fail through whatever proxies live on the path.  It's good for
causing undefined behaviour, which we're assuming (unmathematically)
is not message corruption & frozen connections.

For the legitimate concern of browser script attacks, it's a good idea
(though expensive to implement compared with the alternative), and
randomness is not as strong for this type of security as
randomness+escaping.

-- Jamie

---

From: Bjoern Hoehrmann <[email-masked]>
Date: Tue, 18 Jan 2011 12:37:46 +0100

>randomly mangle it later.

Well obviously we'll require browser clients to check that the handshake
response does not include Content-Length, Transfer-Encoding and maybe a
couple of other headers, and we'll probably change the framing so that
if the first octet the server sends is white space or "H" the connection
is closed by the client, but if you need more integrity than that, you
can code your own. You'd likely do that anyway so you can recover from
it gracefully.

>etc.)  *and* escaping plausible HTTP request character sequences.

Masking does that already, pre-scan the masked frame for bad patterns
like "http" and "host" and pick a different key if you find it, and if
you cannot find a key within some resource limit, fragment the frame.
Not pretty, but then browser developers can figure out on their own how
they balance their performance requirements against their paranoia and
frustrating sloppy server developers who don't expect fragmentation.
-- 
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: Bjoern Hoehrmann <[email-masked]>
Date: Tue, 18 Jan 2011 12:45:35 +0100

>prevents an intermediary from finding an HTTP request *by design*.

If adding some overhead proportional to the message size is okay, we can
also add another byte of randomness every 8 byte block or so. That might
be preferable as it gives the attacker less control over the bits on the
wire and is easier to implement efficiently. Not that I've given it any
thought though.
-- 
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: Jamie Lokier <[email-masked]>
Date: Wed, 19 Jan 2011 01:23:03 +0000

> can code your own. You'd likely do that anyway so you can recover from

I've read that some proxies go into "tunnelling mode" when they see
data that doesn't look like proper HTTP they understand (such as very
broken HTTP headers sent by some Microsoft IIS servers a while ago).
In that mode, they just forward what they see without adding headers.
and I would worry a little about those mangling data later on due to
implementation bugs/quirks, hence the musing over a CRC or MAC.

Making sure the response doesn't contain headers that might be added
by a normal HTTP proxy seems reasonable, although I wouldn't expect
proxies to add any headers (except some of them add Via):

Absence of both Content-Length and Transfer-Encoding has a specific,
valid meaning in HTTP responses, so proxies shouldn't add them unless
they are changing to a different Transfer-Encoding.

> frustrating sloppy server developers who don't expect fragmentation.

That's an interesting idea, though escaping LF seems much easier.

-- Jamie

---

From: Bjoern Hoehrmann <[email-masked]>
Date: Wed, 19 Jan 2011 04:14:13 +0100

>implementation bugs/quirks, hence the musing over a CRC or MAC.

Well, the typical error people make when trying to write parsers by hand
is turning specifications formulated in the positive into code that is
formulated in the negative. HTTP method names cannot contain white space
so you skip white space preceding them and read them until you encounter
white space after them. If you follow that reasoning you can arrive at a
mostly blind forwarder. That is the underlying reasoning for masking and
if you consider that intermediaries sometimes modify things, like adding
a header, your concern is quite plausible even if very limited in scope.

However, support for this in the base protocol, or even in a standard
extension does not buy you much, if the data does get corrupted you'll
likely get some exception in your own client-side code or experience a
strange hang or an error event you didn't account for properly, whether
the browser detects the failure or not. If you make checksums part of
your own sub-protocol and have a way to, say, re-transmit broken stuff,
you would seem to be much better off, without having to persuade browser
vendors to adopt your integrity scheme and without making matters worse
for people who don't really need their "latest tweets" widget to work
perfectly all the time.

>they are changing to a different Transfer-Encoding.

The idea is to capture proxy-generated error messages (since the first
thing they see after the handshake is random junk, they may complain
about the request being malformed, exceeding buffer limits, lacking a
Host header, and so on) and deliberate attempts by a server to send
something that looks like a HTTP response and also a valid Websocket
frame, as they might need in a brute force attack against the masking
key to keep the connection alive. An intermediary might take a response
without "HTTP" at the beginning as HTTP/0.9 response and not read any
more requests until the server closes the connection, for instance.

>That's an interesting idea, though escaping LF seems much easier.

Well, port 80 is not a safe place, I would take it for granted that you
have components there with integer overflows if you'd allow large form
posts from browsers, buffer overflows if you allow long method names or
long paths or long header values, you might have components that attempt
to autodetect TLS or EBCDIC even, some might ignore the top bit of any
byte they see, it's easy to see how randomness helps you sleep at night,
even if there are any number of other vectors through which you can ex-
ploit such hypothetical and obviously silly setups.

Since the proponents of the more elaborate masking schemes didn't feel
like carefully explaining why the most basic masking scheme isn't good
enough when I suggested they do so back in december, I did experiment
http://lists.w3.org/Archives/Public/www-archive/2011Jan/0014.html with
this, and the numbers don't come out that badly. Certainly not something
you'd do permanently, but it gives people time to find and fix bugs and
then you can turn this off. Due diligence.

And in any case, masking LFs would increase the frame length, and as I 
mentioned earlier, if that is okay, you can also add randomness in pro-
portion to the message length. That may be the solution to make every-
one unhappy but too exhausted to object. What we should have done is
come up with a decent set of requirements and then have people skilled
in the arts of cryptography design us a solution along with an argument
why their solution makes good tradeoffs, or tell us to drop some of the
requirements.
-- 
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/