Subject: [hybi] AES-128-CTR not much safer, but not fast either

From: Willy Tarreau <[email-masked]>
Date: Mon, 10 Jan 2011 01:09:08 +0100

I have reused Maciej's code for AES-128-CTR to make it emit a constant
stream and look there for a supposedly processable request (which is
valid since Apache processes it and transcodes it if it finds it at
the beginning of the stream).

willy@pcw:~/c$ time ./aes-128-ctr-get 
Found the 'GET\n' pattern on the wire after 1608425803 bytes

real    0m20.761s
user    0m20.761s
sys     0m0.000s

It requires the client to send more data, but here we're only
at 1.6 GB, roughly just 1000 times more than with the basic XOR
method.

However, it's limited to 640 Mbps only. It means that using this
as a mandatory masking method will not even allow me to use a
memcache at gigabit speeds on my local network :-(

Once again, I'm not saying that I'd believe that any intermediary
would seek a request that far. Neither do I believe it would seek
one after one megabyte nor after any non CRLF byte BTW.

But we're proposing this method because other ones are not deemed
sure enough. However, it does not either cover the issues which
caused the other methods to be proposed.

So now either we should conclude that using AES to prevent a request
from popping up is acceptable because the risks are low, so it must
be possible to disable it for some use cases, or we conclude that
it's not usable and the only masking solution consists in never
putting a CR/LF on the wire.

But we have to make choices. We can't disable the protocol that way
to fix a problem we finally don't fix.

Regards,
Willy

---

From: Adam Barth <[email-masked]>
Date: Sun, 9 Jan 2011 16:20:25 -0800

> memcache at gigabit speeds on my local network :-(

Then you shouldn't use WebSockets to talk to memcache on your local
network.  WebSockets is not the solution to every problem.  For the
important uses cases, 640 Mbps with today's CPUs is vastly more than
enough.

> putting a CR/LF on the wire.

The masking is not optional.  If your use case doesn't work with
masking, please a different protocol.

Kind regards,
Adam

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 10 Jan 2011 01:25:33 +0100

> important uses cases, 640 Mbps with today's CPUs is vastly more than

But a frontal switch which has to process the frames in an internet
infrastructure will require a crypto card to handle the non-secure
version of websocket. Clearly that does not make much sense !

The same machine has no problem handling 10 Gbps of HTTP traffic.
640 Mbps of WS traffic for multi-megabytes frames is a very low
performance in my opinion for a 3 GHz processor ! Any server is
able to cope with that bandwidth for large frames.

Regards,
Willy

---

From: Adam Barth <[email-masked]>
Date: Sun, 9 Jan 2011 16:31:33 -0800

> able to cope with that bandwidth for large frames.

Somehow, we will survive.

Kind regards,
Adam

---

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

> Somehow, we will survive.

Adam, it's not a matter of surviving or not, it's a matter of spending
*all* the CPU cycles of a machine for something which is proven inefficient
against the use case it was introduced for in the first place. The reason
it is inefficient is not because of they crypto part, but precisely because
the use case is wrong ("a caching intermediary might seek a request anywhere
in the stream and for as long as possible").

It is possible that you planned to cover other vulnerabilities with this,
but since you posted a complete paper without any argument for each new
point, it's very hard to spot the reasons. We can just discover something
is here, there is no *why* to that.

Under these conditions, you can certainly expect that some people will
bother why we'd suddenly decide that the protocol will work that way
despite the costs when there is no explanation at all.

Regards,
Willy

---

From: "Thomson, Martin" <[email-masked]>
Date: Mon, 10 Jan 2011 10:21:16 +0800

> Found the 'GET\n' pattern on the wire after 1608425803 bytes

You might also find the collected works of Shakespeare in the byte stream had you waited a little longer.  I'm not sure what you are hoping to prove by searching.

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 10 Jan 2011 07:36:46 +0100

On Mon, Jan 10, 2011 at 10:21:16AM +0800, Thomson, Martin wrote:
> You might also find the collected works of Shakespeare in the byte stream had you waited a little longer.

I know, that's just a matter of defining "a little longer", as none of us
will live long enough for that.

>  I'm not sure what you are hoping to prove by searching.

What I'm just showing is that we have the following points :
  1) it was reported by an experiment that some caching intermediaries
     were waiting for an HTTP request after the HTTP handshake was over

  2) it was speculated that some lazy intermediaries might possibly skip
     over whatever they did not understand to resync on an HTTP request
     they understand and execute it, hence the need for masking the
     stream or payload. Please note that no such intermediary has even
     been remotely detected, and that several people here who have
     already been involved with server code expressed that making them
     capable of doing so would be much more difficult than doing the
     right thing and would not even respect the principle of laziness.

  3) it has been suggested that a simple 32-bit XOR was not enough and
     that stronger cryptography was needed, because after a certain
     number of attempts, the server might get the client to send a
     request that such an intermediary can parse.

  4) it was reported that at least one intermediary (Apache) accepts
     an HTTP/0.9 request as simple as "GET\n".

  5) it was shown that whatever algorithm we used to address the third
     point was not enough to cover the second point for the supposedly
     lazy intermediaries from #2 acting like Apache.

So now, we have a choice :
  - either we agree that #2 above is not that much of a risk such that
    we don't need #3 to address it ;

  - or we agree that #2 is still much of a concern, but as #4 is real,
    then #3 is not a valid solution, as was proven with #5, and we
    must use another one.

But right now we're just complicating the protocol and removing some
possibilities of later extensions without addressing the reason why
we did that in the first place.

Thanks,
Willy

---

From: Adam Barth <[email-masked]>
Date: Sun, 9 Jan 2011 22:44:19 -0800

Or we could just use AES-128-CTR like everyone else in the known
universe and not worry about whether we've shaved exactly the right
number of hairs off our home-brew pseudo crypto.

Adam

On Sun, Jan 9, 2011 at 10:36 PM, Willy Tarreau <[email-masked]> wrote:
> _______________________________________________
> hybi mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/hybi
>

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 10 Jan 2011 07:58:22 +0100

> number of hairs off our home-brew pseudo crypto.

Adam, I just explained that AES-128-CTR as you proposed it does not
address the points that were raised which made it appear here.

In fact the real problem we really want to solve is make the CR/LF
bytes disappear from the stream. Those bytes are still present with
AES-128-CTR.

And if the risk suddenly becomes acceptable, then we can fallback
to much simpler masking algorithm which share the same risks for
that matter.

Willy

---

From: Adam Barth <[email-masked]>
Date: Sun, 9 Jan 2011 23:02:47 -0800

> bytes disappear from the stream. Those bytes are still present with

Fortunately, we don't need to make the CR/LF bytes disappear from the
stream.  What we need to do is prevent the attacker from choosing a
string that can be used to attack an intermediary.  Using AES-128-CTR
makes it so the attacker is forced to choose a pseudo-random sequence
of bytes.  I claim that it is infeasible to attack an intermediary in
this way using a pseudo-random sequence of bytes.

Kind regards,
Adam

---

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

> this way using a pseudo-random sequence of bytes.

For short a string lengths accepted by Apache (4 bytes), it *is* feasible
by making the client send an important amount of bytes as I have shown.
If we agree that we don't need to protect against that very unlikely issue,
then the simpler XOR masking is enough because the initial pseudo-random
makes it equally hard for the attacker to guess what the stream will look
like.

Regards,
Willy

---

From: Adam Barth <[email-masked]>
Date: Sun, 9 Jan 2011 23:16:01 -0800

> makes it equally hard for the attacker to guess what the stream will look

I stand by my claim that it is infeasible to attack an intermediary in
this way using a pseudo-random sequence of bytes.

Your "attack" of finding the string "GET\n" after 1608425803 bytes
(yes, that's 1.6 gigabytes) is meaningless.  How many bytes do you
think you'd have to examine before finding the string "Willy Tarreau"
?

Kind regards,
Adam

---

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

On Sun, Jan 09, 2011 at 11:16:01PM -0800, Adam Barth wrote:
> (yes, that's 1.6 gigabytes) is meaningless.

Precisely, and it is as much meaningless as finding it after the same
amount of bytes using a simple XOR method with a 32-bit key. That was
the point I wanted to make, because at one point it was speculated
in the 32-bit vs HMAC that it was a concern.

So now we can move on to simpler algorithms and stop cripling the
protocol.

Thanks,
Willy

---

From: Adam Barth <[email-masked]>
Date: Sun, 9 Jan 2011 23:55:50 -0800

Adam

---

From: Willy Tarreau <[email-masked]>
Date: Mon, 10 Jan 2011 11:50:44 +0100

> number of hairs off our home-brew pseudo crypto.

To the best of my knowledge, HTTP itself does not make use of AES-128-CTR
when posting data, nor when using PUT to send a file, despite some
implementations not being aware of this method.

Willy

---

From: Scott Ferguson <[email-masked]>
Date: Mon, 10 Jan 2011 10:07:19 -0800

Willy Tarreau wrote:
>      they understand and execute it....

Has anyone attempted to justify this claim?

It's implicit in the entire discussion about hash algorithms, but I 
haven't seen an argument that any intermediary, lazy or not, has or will 
ever implement any kind of HTTP resyncing.

-- Scott

---

From: Bruce Atherton <[email-masked]>
Date: Mon, 10 Jan 2011 11:25:35 -0800

> number of hairs off our home-brew pseudo crypto.

I've written applications that use simple XOR masking because 
AES-128-CTR is unnecessarily complex. Does that mean I'm now in an 
unknown universe?

Cool. Do I get to win the lottery in this one?

---

From: Yuta Kitamura <[email-masked]>
Date: Wed, 12 Jan 2011 17:56:28 +0900

Hi,

> Found the 'GET\n' pattern on the wire after 1608425803 bytes
The probability that you get some four-byte data from a random byte sequence
is 1/(256^4) = 1/4294967296 for each byte. Please note that the order of
256^4 is almost same as the above number. This means that, statistically,
it's quite possible to find a four-byte 'GET\n' sequence (and any other
four-byte sequence) in a few gigabytes of random bytes.

I think your experiment has just shown that the output of AES-128-CTR is
random enough.

I'm sorry if I'm missing your point.

Thanks,
Yuta

---

From: Willy Tarreau <[email-masked]>
Date: Wed, 12 Jan 2011 10:41:47 +0100

> four-byte sequence) in a few gigabytes of random bytes.

That's what I've been explaining from the beginning !

> I think your experiment has just shown that the output of AES-128-CTR is

I agree it's random enough, just as the simple 32-bit random XOR is ! And
that was my point : there is no vulnerability that would remain with the 
simple XOR that the AES would solve since in the end, we're down to just
a 32-bit randomness.

Willy

---

From: Cedric Vivier <[email-masked]>
Date: Wed, 12 Jan 2011 23:58:57 +0800

> simple XOR that the AES would solve since in the end, we're down to just

+1
If there really has to be masking (to protect against potential
intermediaries broken beyond reason), AES cannot protect those 4 bytes
any more than a simple XOR on a 32-bit key.

It is faster to process and simplifies development. Sure, you can link
to OpenSSL or your favorite crypto library from C/C++, it still adds
unnecessary bloat/complexity while also limiting possibility of using
other programming languages to write small/prototype/test WebSocket
servers without installing crypto bindings... (think Lua, Python [AES
not in standard library], ...).

Regards,