Subject: [hybi] Masking overhead with measurements and code

From: Willy Tarreau <[email-masked]>
Date: Sat, 8 Jan 2011 12:16:32 +0100

Since I was not convinced at all by the supposedly very low
overhead of using HMAC to compute a masking key, I have written
a WebSocket framing parser which reads, parses and forwards frames.
It supports 7, 16 and 63-bit lengths, stops after forwarding the
last frame with opcode 0x01 and exits with an error if the input
is broken before reaching the end of the closing frame.

When called with any argument, it computes an hmac-sha1 key derived
from a simple 32-bit constant key (for simplicity) for each frame.

The payload is not even unmasked with the key, the purpose is just
to evaluate the cost for a front server/load balancer/switch supposed
to switch frames to a server farm.

I have ran it over a stream of messages whose payload was between 1
and 125 bytes, with an average of 29 bytes (rnd(1..5) ^ 3), so that
we're in line with many legitimate uses of the protocol such as online
chat, and it happens to always fit in one byte length, making the
stream generator even easier to write.

The results :

willy@pcw:~/c$ wc -c /dev/shm/ws-stream.bin
579976835 /dev/shm/ws-stream.bin

- without masking :
  willy@pcw:~/c$ time ./ws-parse < /dev/shm/ws-stream.bin >/dev/null 
  20000001 messages forwarded

  real    0m1.753s
  user    0m1.544s
  sys     0m0.208s

  => average bit rate : 4.1 Gbps

- with HMAC-based masking :
  willy@pcw:~/c$ time ./ws-parse 1 < /dev/shm/ws-stream.bin >/dev/null 
  20000001 messages forwarded

  real    0m42.098s
  user    0m41.759s
  sys     0m0.212s

  => average bit rate : 172 Mbps

Masking the stream with HMAC multiplies the parsing time by 24 on small
messages !!! We're not at all in the range of a few percent more. The
parser with HMAC is limited to only 172 Mbps on a 3 GHz system, which
is the speed at which the non-masking parser would run on a 125 MHz
system.

Considering those facts, I'm strongly opposed to using HMAC as well as
any algorithm which has a similar level of complexity, which is normally
required only for cryptographically strong usages.

We're not trying to encrypt the stream, we're just ensuring that no
broken intermediary will accidentally find a request that was put
there on purpose by an attacker. Such a complexity is not required
at all and is way overkill. The per-byte masking cost must remain
very low even for small frames.

I still think that a simple sliding XOR based on a cheap modification
of the seed is far more than enough against choosen text attacks for
this use case, such as the example code I provided yesterday, or any
other one with the same level of complexity.

The code to reproduce those tests can be freely downloaded there :

    http://1wt.eu/websocket/

It's clearly not a model of beauty as it's only a POC. So it's not needed
to comment on its ugliness or its possible improvements.

Regards,
Willy

---

From: Maciej Stachowiak <[email-masked]>
Date: Sat, 08 Jan 2011 14:26:50 -0800

Hi Willy,

Thanks for actually testing! One thing to note about your experiment - you're testing only a single part of a complete WebSocket service, omitting the I/O parts and whatever processing actually occurs in response to a message received. So I don't think it's correct to infer a percent overhead from this experiment. What we can do, though, is see whether this isolated component alone would be too slow to let us process some number of messages per second.

Looking at this another way, I'd like to see how this compares to the goal of 200k messages processed per second on a server handling 1 million concurrent connections. Your test runs everything serially and therefore makes use of only a single CPU core. A realistic scenario would involve processing many connections in parallel. On my system (apparently somewhat slower than yours), here's what I get running 4 tests in parallel:

$ time sh -c './ws-parse 1 < /tmp/stream.bin > /dev/null & ./ws-parse 1 < /tmp/stream.bin > /dev/null & ./ws-parse 1 < /tmp/stream.bin > /dev/null & ./ws-parse 1 < /tmp/stream.bin > /dev/null'
20000002 messages forwarded
20000002 messages forwarded
20000002 messages forwarded
20000002 messages forwarded

real	1m34.343s
user	4m37.364s
sys	0m1.459s

That's 94 seconds total to process 80 million messages. This would imply a rate of ~850k operations per second, well within the margins for 200k messages processed a second, with plenty of CPU to spare to do the actual processing. Note: I doubt my laptop could actually handle a million concurrent connections as in the example scenario. A dual 6-core 3 GHz Xeon, for example would probably be able to do this 10-20x as fast as my single dual-core 2.66Ghz Core i7.

My conclusion: HMAC to compute a per-frame mask would not be an obstacle to handling a million concurrent connections on a single server. It falls well within a reasonable performance target.

Regards,
Maciej

On Jan 8, 2011, at 3:16 AM, Willy Tarreau wrote:

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

---

From: Willy Tarreau <[email-masked]>
Date: Sun, 9 Jan 2011 00:36:58 +0100

Hi Maciej,

On Sat, Jan 08, 2011 at 02:26:50PM -0800, Maciej Stachowiak wrote:
> 
> Hi Willy,
> 
> Thanks for actually testing! One thing to note about your experiment - you're
> testing only a single part of a complete WebSocket service, omitting the I/O
> parts

I/O parts are intentionally not emphasized because depending on what the
intermediary does and how the lower levels work, it can represent a very
low overhead. For instance, the 10 Gbps Myricom NICs I'm working with are
very efficient at doing LRO (Large Receive Offload, which consists in
aggregating segments before passing through network layers). The application
layer receives TCP segments of about 20-50 kB, which precisely is in the
range of the read size I've used in the experiment (32 kB). Sending many
segments to a NIC already costs almost nothing with most NICs and drivers
today. So as long as the framing permits it, it is possible that a front
proxy splits aggregate streams to multiple server farms without too much
cost.

In fact, what I predict we'll see in the medium term is that we'll have
for WebSocket exactly what we already have with HTTP: dedicated boxes
which will do TCP packet splicing in ASICs and deliver it to the CPU to
perform content-based switching and policy enforcement. Thus the theorical
I/O operations cannot really be counted as I/O operations, but much more
as messages processed and/or bandwidth.

Also, please note that I/Os were not really omitted either, as currently
the fwrite() calls are of major concern, because they're responsible for
63% of the CPU usage. I could not count for the read(). I should have used
mmap() for that, it was way out of the scope.

> and whatever processing actually occurs in response to a message received.

Yes indeed.

> So I don't think it's correct to infer a percent overhead from this experiment.

It depends how you see it, it shows that on the amount of CPU spent in the WS
handling code, 96% was spent in HMAC, >2.5% in I/Os, <1.5% in frame parsing.

> What we can do, though, is see whether this isolated component alone would be
> too slow to let us process some number of messages per second.

Which finally is equivalent to see how to size the isolated component for a
given task.

> Looking at this another way, I'd like to see how this compares to the goal
> of 200k messages processed per second on a server handling 1 million concurrent
> connections. Your test runs everything serially and therefore makes use of only
> a single CPU core.

Yes, but that's common across stream processing devices to dedicate cores to
functions. That avoids the high cost of locking when there is a need for any
type of shared data.

> A realistic scenario would involve processing many connections in parallel.
> On my system (apparently somewhat slower than yours), here's what I get
> running 4 tests in parallel:
> 
> 

Once again, it depends if the workload can realistically be split on multiple
cores, but I'm following you on this.

> My conclusion: HMAC to compute a per-frame mask would not be an obstacle to handling a million concurrent connections on a single server. It falls well within a reasonable performance target.

In a single server the size of yours. Without the HMAC, a much lower-end
processor is able to do the task. That means that it can enable routers
to perform software-based framing analysis for NAT. It can enable firewalls
to perform content analysis at a small cost.

Now look at it the other side. Right now we're finding high-end HTTP load
balancers capable of handling one million HTTP requests per second, and
almost as many connections per second. Those devices sell well BTW, because
there is a demand at large ISPs or enterprises. At these rates, they do very
little thing. They connect, forward, splice connections together and that's
almost all they do. But that's huge because they're offloading a lot of the
I/O job for multiple other devices that will be able to individually process
their share of the job.

Such devices require extremely fast frame processing, that's the key point.
The more expensive the per-frame forwarding cost, the higher the number of
equipments will be required for the task.

Some large sites already struggle with limited infrastructure performance.
I recently read somewhere from a Facebook engineer that they were impatient
to get 100GB Ethernet, because all their servers are connected at 10GB and
that's not enough. Ah it was here :

   http://www.pcworld.com/businesscenter/article/188412/facebook_sees_need_for_terabit_ethernet.html

I don't know what's their bandwidth, but at 500 million users and 250
regular (at least once a month), they must have big fat pipes well
used in both directions, with I-don't-know-how-many parallel chat
sessions.

Also it's important to keep in mind that if WebSocket gets success, it
can be adopted in areas we've not thought about. For instance, HTTP is
currently used by some databases. It's never fast enough. The "nosql"
DBs as some like to call them are stressed to process hundreds of
thousands of requests/response a second at even moderately sized sites.
HTTP is overkill for the task since the job consists in returning a
variable from RAM or storing one, but it's handy.

WebSocket might be a very well suited alternative to HTTP for these
uses. Wasting a major part of the DB's CPU sycle and latency decoding
frames in an environment where it's irrelevant is simply a shame.

Other uses : mobile phone operators are progressively pushing IP
closer to the radio, even for voice. We could think that WebSocket
could be used as an underlying block at some point in those environments
for its ability to frame data, and mix various types of frames together
(eg: data+voice+signaling with different opcodes).

The endpoint which has to process the frames should avoid spending its
time doing HMACs that are irrelevant to its use.

So as you can see, I'm really concerned by the relative overhead because
we'll always find a usage for a given sizing, and that's always been the
case since the first network protocols were designed. If IP conceptors
30 years ago had imagined that their packets would be processed by switches
at rates over 100 million per second, they would probably have adapted it
a little bit to make a few things easier to process for the hardware. That's
my concern too : how to ensure it scales smoothly in case it works.

Regards,
Willy

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 8 Jan 2011 15:59:13 -0800

FWIW, I don't know how you're computing HMAC, but the naive
implementation is about
1/2 as fast as optimized implementations. The trick is to precompute
and cache the
hash state after you have incorporated the keys. This saves a bunch of
setup overhead.

Best,
-Ekr

---

From: Jack Moffitt <[email-masked]>
Date: Sat, 8 Jan 2011 17:01:29 -0700

> hash state after you have incorporated the keys. This saves a bunch of

He used openssl's HMAC implementation. I'm not familiar with it
particularly, but it seems a reasonable approximation of what most
people will do. It's good to know there may be a 2x speedup to be
gained.

jack.

---

From: "Pat McManus @Mozilla" <[email-masked]>
Date: Sat, 08 Jan 2011 19:05:27 -0500

Willy, this is great. Thanks.

On Sat, 2011-01-08 at 12:16 +0100, Willy Tarreau wrote:

>  I have written

[..]

> stream generator even easier to write.

[..]

> messages !!! 

Based on your experiment I was able to repeat it here on a single core
of a 2.7ghz i5. (I got a multiple of about 22x).

I thought a few other datapoints were in order. So I rearranged your
test to be more like a server doing dispatch. I measured just frame
parsing, frame parsing with a xor on the data, and frame parsing with a
xor and a 20 byte hmac for each frame for frame sizes ranging on average
from 27 bytes up to 32KB.

The xor just uses a constant even when we calculate the hmac. It
shouldn't matter for measurement. 

These are gigabits per second of payload data:

Msgs      parsed    plain-xor    xor-hmac
--------  ------    ---------    --------
27 byte    11.7          7.1       0.15
250 byte   40.4         20.6       1.3
1 KB       50.8         25.2       5.1
4 KB       57.1         26.7      12.3
8 KB       57.1         26.7      17.0
32 KB      58.32        26.7      23.6

These are K-messages per second:

Msgs      parsed       plain-xor    xor-hmac
--------  ------       ---------    --------
27 byte    54000       33000          692
250 byte   20000       10000          668
1 KB        6349        3000          597
4 KB        1785         833          394
8 KB         892         416          265
32 KB        222         102           90

Most of the tests moved about 4GB of data that was all in page cache. It
looks like plain xor is expensive, but that basically is just measuring
memory bandwidth of streaming all the data bytes through the processor
cache which you have to figure a server is going to need to do
eventually - you can see the limit on my desktop is reached around
26gbit/s. I replaced xor with an accumulator and and got the same
timings.

One of the things only marginally related to the question at hand that
this tells me is that even at its most pathological case of 27 byte
messages the xor and ws framing doesn't kill us if we can process
33million of them per second on a single core of a commodity desktop.

I also ran a test that just calculated hmacs across the same 20 bytes to
find the bottleneck. It was 694K on one core of this box. One way to
look at the 27 byte test is that the core was doing almost exclusively
HMAC instead of core WS, but the other way is to say even though hmac
dominated the core it still did 692K messages per second! We can do a
deep dive on the I/O and where it matters, but the hmac rate is probably
the interesting limit for this discussion. (ekr suggests perhaps this
could preform better - but I think it is sufficient to use this as a
conservative number for now).

I guess I am swayed by what Maciej has to say - even though the hmac is
imo grotesquely way too expensive compared to the amount of risk it is
avoiding, it really doesn't add up to anything all that important to
obsess over. Claims of "a few percent" are not true, but even at its
most pathological a server can process 694 thousand of them per second
with a single core of a commodity desktop. Anyone interested in those
kinds of volumes easily has a LOT more processor (heck I have 3 unused
cores - and this is not a server class machine), and probably
specialized security processors (e.g. cavium nitrox) in the case of
routing switches,  that can cope without breaking a sweat - and in turn
can accommodate easily millions of messages per second.

Even with hmac enabled, processing this purely in software on even old
systems is totally reasonable for significant data flows. Giant
multiplexing servers will require more oomph. I can live with that -
they'll almost certainly have a lot more trouble terminating the
commensurate TCP than parsing websockets.

To sum it up: This is a lot like masking in general. I'm not a proponent
of HMAC because I think it is an un-necessary cost. But if that's what
we need to get consensus and ship this thing that is a reasonable
compromise I can support because I don't think it materially damages the
utility of websockets. And that is the question I find myself asking all
the time lately.

-Pat

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

---

From: Willy Tarreau <[email-masked]>
Date: Sun, 9 Jan 2011 08:47:09 +0100

Hi Pat,

> of a 2.7ghz i5. (I got a multiple of about 22x).

Nice to see that results are easily reproduceable :-)

> from 27 bytes up to 32KB.

Cool. I started to do that and stopped at one point because it was taking
too much time to me for little added value. Do not hesitate to post your
updates, as apparently the prog can serve as a basis for experiments. Maybe
if we complete it we could even post the parser as an example implementation
in an annex of the spec (it needs some improvements though).

> shouldn't matter for measurement. 

That's not a problem for me either. As you've seen, I made similar choices
for the experiment.

> 26gbit/s. I replaced xor with an accumulator and and got the same

I'm not surprised you hit memory bandwidth limits. In find, I was
impressed to see how efficient the framing is for a parser, as it's
very easy to handle. I suspect we can optimize the xor if we want so
that it works on 32- or 64- bit quantities at a time on aligned
boundaries, but that's not the point for now.

> 33million of them per second on a single core of a commodity desktop.

Agreed. We must just keep in mind that we don't update the xor mask
right now, but if properly done it should not cause significantly more
memory accesses.

> conservative number for now).

I've seen his suggestion too, but I don't know how to do what he suggests.
It was already not easy to find some example code for using HMAC, as the
openssl man is not particularly helpful on the subject.

> obsess over.

That's the point where I disagree. Granted for a browser with one message
once in a while, nobody will even notice the difference. But on some
intermediaries, we'll have to oversize their CPUs just for being able
to process a given amount of messages.

> Claims of "a few percent" are not true, but even at its
> kinds of volumes easily has a LOT more processor

No, I disagree with this point too. It really depends on target usage.
Imagine that a product such as memcache is updated to support WebSocket
as an exchange protocol. There would be nothing wrong with that. The
message rate could be much higher on the centralized server. Also, more
and more services are migrating to virtualized environments. People do
pay for small systems, they order them in 500 MHz steps. Here we're
saying that someone who implements that in such an environment will
have to afford a bigger VM just to be able to process HMAC between
two VMs running on the same hypervisor !

> (heck I have 3 unused

Not necessarily. From my experience, security processors excel on streaming
but are not better than commodity processors running at amazing frequencies
when it comes to key setups or such things (and often their libraries still
make use of the main processor power for those complex tasks).

Also, keep in mind that contrary to a common belief, border infrastructure
equipments are generally equipped with smaller processors than what you can
find in your average server or desktop. They often have dedicted ASICs for
switching and/or packet forwarding, state matching, but the upper layers are
handled by much smaller processors running finely tuned software.

For instance, I remember that the Alteon web switches were using two ASICs
per port for wire-speed packet forwarding and session processing, but when
it came to content inspection or layer 7 processing, the management CPU was
involved (a 150 MHz PPC) for that task.

If you check what's inside a big F5 LB such as an 8800, you'll be surprized 
to discover a smaller CPU than in the servers it distributes traffic to.

> commensurate TCP than parsing websockets.

Precisely not. Efficient software and hardware already exists to process
TCP. HMAC processing can be improved but will always find a limit. Hashing
algorithms are designed to ensure that there is a non-null setup cost in
order to limit the ability to brute-force them. So even if we manage to
gain a nice 2x gain there, we'll still spend 90% of the CPU time in HMAC
computations.

> utility of websockets. And that is the question I find myself asking all

I think that it sensibly limits the use cases and that's what I don't agree
with. Considering what improvement it brings over simple XOR masking, and
the huge additional cost, I'd really vote for the simpler mask method.

Thanks,
Willy

---

From: Greg Wilkins <[email-masked]>
Date: Sun, 9 Jan 2011 10:43:18 +0100

On 9 January 2011 01:05, Pat McManus @Mozilla <[email-masked]> wrote:

> I guess I am swayed by what Maciej has to say - even though the hmac is imo
> grotesquely way too expensive compared to the amount of risk it is avoiding,
> it really doesn't add up to anything all that important to obsess over.
> Claims of "a few percent" are not true, but even at its most pathological a
> server can process 694 thousand of them per second with a single core of a
> commodity desktop. Anyone interested in those kinds of volumes easily has a
> LOT more processor (heck I have 3 unused cores - and this is not a server
> class machine), and probably specialized security processors (e.g. cavium
> nitrox) in the case of routing switches,  that can cope without breaking a
> sweat - and in turn can accommodate easily millions of messages per second.
>

The HMAC message rate may be sufficient for a intermediary that does nothing
but forward messages.

But the CPU cost is significant and on server boxes that will be running WS
and running the application, then message rate is not the only thing as
servers have other things they need to use the CPU's for.
So if WS with no masking at my required message rate takes 5% of my CPU, but
I can probably live with XOR masking taking 10%, but HMAC masking taking
25-50% of my CPU is going to be prohibitive!

Not all of the high volume servers I've worked with have been CPU bound, but
certainly some of them have been.

regards

---

From: Maciej Stachowiak <[email-masked]>
Date: Sun, 09 Jan 2011 06:13:03 -0800

Hi Pat, including XOR seems like a great idea. I coded up my own XORing version, and I decided to also test HMAC with cached state as suggested by Eric, and AES-CTR instead of XOR. 

Here is a summary of my results on two-way parallel runs:

Plain XOR: ~5.1 million msg/sec
HMAC+XOR: ~370 thousand msg/sec
cached state HMAC+XOR: 1.2 million msg/sec
AES-CTR: 2.6 million msg/sec

== Conclusions ==

- HMAC is much faster if you do the state caching thing.
- AES-CTR is even faster than that.
- We should use AES-CTR for masking.

Here is my code (based on Willy's version):

Here is the raw data:

== Plain XOR ==

time (./ws-parse < /tmp/stream.bin > /dev/null & ./ws-parse < /tmp/stream.bin > /dev/null)
Mode: 0
Mode: 0
20000002 messages forwarded
20000002 messages forwarded

real	0m3.922s
user	0m7.314s
sys	0m0.519s

== HMAC+XOR ==

$ time (./ws-parse 1 < /tmp/stream.bin > /dev/null & ./ws-parse 1 < /tmp/stream.bin > /dev/null)
Mode: 1
Mode: 1
20000002 messages forwarded
20000002 messages forwarded

real	0m53.586s
user	0m53.222s
sys	0m0.347s

== cached state HMAC+XOR ==

$ time (./ws-parse 2 < /tmp/stream.bin > /dev/null & ./ws-parse 2 < /tmp/stream.bin > /dev/null)
Mode: 2
Mode: 2
20000002 messages forwarded
20000002 messages forwarded

real	0m16.399s
user	0m32.098s
sys	0m0.631s

== AES-CTR ==

$ time (./ws-parse 3 < /tmp/stream.bin > /dev/null & ./ws-parse 3 < /tmp/stream.bin > /dev/null)
Mode: 3
Mode: 3
20000002 messages forwarded
20000002 messages forwarded

real	0m7.695s
user	0m7.396s
sys	0m0.290s

On Jan 8, 2011, at 4:05 PM, Pat McManus @Mozilla wrote:

> Based on your experiment I was able to repeat it here on a single core of a 2.7ghz i5. (I got a multiple of about 22x).
> 
> I thought a few other datapoints were in order. So I rearranged your test to be more like a server doing dispatch. I measured just frame parsing, frame parsing with a xor on the data, and frame parsing with a xor and a 20 byte hmac for each frame for frame sizes ranging on average from 27 bytes up to 32KB.
> 
> The xor just uses a constant even when we calculate the hmac. It shouldn't matter for measurement. 
> 
> Most of the tests moved about 4GB of data that was all in page cache. It looks like plain xor is expensive, but that basically is just measuring memory bandwidth of streaming all the data bytes through the processor cache which you have to figure a server is going to need to do eventually - you can see the limit on my desktop is reached around 26gbit/s. I replaced xor with an accumulator and and got the same timings.
> 
> One of the things only marginally related to the question at hand that  this tells me is that even at its most pathological case of 27 byte messages the xor and ws framing doesn't kill us if we can process 33million of them per second on a single core of a commodity desktop.
> 
> I also ran a test that just calculated hmacs across the same 20 bytes to find the bottleneck. It was 694K on one core of this box. One way to look at the 27 byte test is that the core was doing almost exclusively HMAC instead of core WS, but the other way is to say even though hmac dominated the core it still did 692K messages per second! We can do a deep dive on the I/O and where it matters, but the hmac rate is probably the interesting limit for this discussion. (ekr suggests perhaps this could preform better - but I think it is sufficient to use this as a conservative number for now).
> 
> I guess I am swayed by what Maciej has to say - even though the hmac is imo grotesquely way too expensive compared to the amount of risk it is avoiding, it really doesn't add up to anything all that important to obsess over. Claims of "a few percent" are not true, but even at its most pathological a server can process 694 thousand of them per second with a single core of a commodity desktop. Anyone interested in those kinds of volumes easily has a LOT more processor (heck I have 3 unused cores - and this is not a server class machine), and probably specialized security processors (e.g. cavium nitrox) in the case of routing switches,  that can cope without breaking a sweat - and in turn can accommodate easily millions of messages per second.
> 
> Even with hmac enabled, processing this purely in software on even old systems is totally reasonable for significant data flows. Giant multiplexing servers will require more oomph. I can live with that - they'll almost certainly have a lot more trouble terminating the commensurate TCP than parsing websockets.
> 
> To sum it up: This is a lot like masking in general. I'm not a proponent of HMAC because I think it is an un-necessary cost. But if that's what we need to get consensus and ship this thing that is a reasonable compromise I can support because I don't think it materially damages the utility of websockets. And that is the question I find myself asking all the time lately.
> 
> -Pat
> 
> --

---

From: Willy Tarreau <[email-masked]>
Date: Sun, 9 Jan 2011 15:34:23 +0100

Hi Maciej,

> AES-CTR: 2.6 million msg/sec

Those are indeed better results.

>From what was previously said, AES cannot be used due to export
regulations, so this can be quite a showstopper for broader adoption.

Regards,
Willy

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 9 Jan 2011 07:11:56 -0800

> openssl man is not particularly helpful on the subject.

I'm not an expert on the OpenSSL interface, but the general procedure in most
systems is to call HMAC_Init() or equivalent and then memcpy() the result
so that it incorporates the key.

> I
> order to limit the ability to brute-force them.

(1) As far as I know, this is not in fact a design criterion for hash
algorithms. Indeed,
how could it be since the "key schedule" for a hash is fixed and so
you can always
precompute. Perhaps you're thinking of encryption algorithms--though
even then this
is no longer really a design goal.

(2) The precomputation I described above is precisely the optimization
that removes any
setup cost.

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 9 Jan 2011 07:14:14 -0800

On Sun, Jan 9, 2011 at 1:43 AM, Greg Wilkins <[email-masked]> wrote:
>> avoiding, it really doesn't add up to anything all that important to obsess
>> over. Claims of "a few percent" are not true, but even at its most
>> pathological a server can process 694 thousand of them per second with a
>> single core of a commodity desktop. Anyone interested in those kinds of
>> volumes easily has a LOT more processor (heck I have 3 unused cores - and
>> this is not a server class machine), and probably specialized security
>> processors (e.g. cavium nitrox) in the case of routing switches,  that can
>> cope without breaking a sweat - and in turn can accommodate easily millions
>> of messages per second.
>

Wow, I think you have this completely backwards: it's in systems that
do almost nothing
that the cost of adding a new, expensive operation is large. In
systems that are already
doing a lot of other processing, the marginal cost is comparaitvely
low even though it may
occasionally push you over some threshold; Amdahl's law and all that.

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 9 Jan 2011 07:18:41 -0800

On Sun, Jan 9, 2011 at 6:13 AM, Maciej Stachowiak <[email-masked]> wrote:

>
> Hi Pat, including XOR seems like a great idea. I coded up my own XORing
> version, and I decided to also test HMAC with cached state as suggested by
> Eric, and AES-CTR instead of XOR.
>
You'll recall this was Adam's and my original suggestion. :)

We only started discussing hash-based systems when concerns about export
were raised. If those concerns are still operative, we can get another
factor of two by going from HMAC-SHA1 to SHA-1 alone. That doesn't thrill me
from a cryptographic perspective because merging the key is tricky,but I'm
sure we can figure something out that's sufficient unto the day.

Best,
-Ekr

> Based on your experiment I was able to repeat it here on a single core of a
> 2.7ghz i5. (I got a multiple of about 22x).
>
> I thought a few other datapoints were in order. So I rearranged your test
> to be more like a server doing dispatch. I measured just frame parsing,
> frame parsing with a xor on the data, and frame parsing with a xor and a 20
> byte hmac for each frame for frame sizes ranging on average from 27 bytes up
> to 32KB.
>
> memory bandwidth of streaming all the data bytes through the processor cache
> which you have to figure a server is going to need to do eventually - you
> can see the limit on my desktop is reached around 26gbit/s. I replaced xor
> with an accumulator and and got the same timings.
>
> this tells me is that even at its most pathological case of 27 byte messages
> the xor and ws framing doesn't kill us if we can process 33million of them
> per second on a single core of a commodity desktop.
>
> find the bottleneck. It was 694K on one core of this box. One way to look at
> the 27 byte test is that the core was doing almost exclusively HMAC instead
> of core WS, but the other way is to say even though hmac dominated the core
> it still did 692K messages per second! We can do a deep dive on the I/O and
> where it matters, but the hmac rate is probably the interesting limit for
> this discussion. (ekr suggests perhaps this could preform better - but I
> think it is sufficient to use this as a conservative number for now).
>
> systems is totally reasonable for significant data flows. Giant multiplexing
> servers will require more oomph. I can live with that - they'll almost
> certainly have a lot more trouble terminating the commensurate TCP than
> parsing websockets.
>
> To sum it up: This is a lot like masking in general. I'm not a proponent of
> HMAC because I think it is an un-necessary cost. But if that's what we need
> to get consensus and ship this thing that is a reasonable compromise I can
> support because I don't think it materially damages the utility of
> websockets. And that is the question I find myself asking all the time
> lately.
>
> -Pat
>
>   -- http://www.getfirefox.com/
>

---

From: Patrick McManus <[email-masked]>
Date: Sun, 09 Jan 2011 10:41:28 -0500

On Sun, 2011-01-09 at 07:14 -0800, Eric Rescorla wrote:
> ges.

+1 ,.. at these volumes the concerning case is the ws-router, not the
server doing useful things. It is of course a syllogism to conclude that
the more expensive hmac means less resources for "real work". 

I think the more useful conclusion here given the raw volumes is that
any reasonable volume of "real work" precludes reaching message rates
where the hmac adds up to very much. Of course I cannot know that for
certain before someone accuses me of presuming I know every use case for
the protocol - it is a judgment based on experience. ymmv.

That leaves us, imo:

 1 - hmac adds a significant but bearable cost in return for a very
minor reduction in risk
 2 - aes costs computationally less for the same return but has
potential hassles with legal vetting. aes is being deployed in new intel
commodity processors, likely driving the cost down even further.
  3 - xor with a sliding mask is probably the cheapest option given
consensus on masking and comes bundled with a non-specific risk.

My preference remains for #3 because I'm not paranoid about the specific
risk - but I don't see any reason to object to #1 if that is needed for
consensus. Websockets would still be a perfectly good protocol with #1
and the fact that it reflects input from wide points of view might only
makes it stronger. I would want to research #2 more before supporting
that as part of the standard.

---

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

> that as part of the standard.

I agree with your approach Pat. Also, I'm still doing some work but it
appears that for our precise concern, HMAC will finally not provide any
better protection over a simple XOR due to the ease of making the client
generate known small messages. Anyway, both do still offer quite a good
masking capability, which is what we're looking for in the first place.

More on that later.

Cheers,
Willy

---

From: Maciej Stachowiak <[email-masked]>
Date: Sun, 09 Jan 2011 11:44:45 -0800

> regulations, so this can be quite a showstopper for broader adoption.

I remember that being said, but I am skeptical. My understanding of US crypto export regulations is that merely using existing crypto facilities from the operating system or from separate components is not subject to export limitations. AES-CTR is in libcrypto which is widely available all over the world. I'm skeptical that there is any place in the world where you can easily use SHA1 HMAC but not AES-CTR. So if anyone wants to claim that use of AES-CTR would cause problems with export regulations, I would ask them to substantiate that claim.

Even if the export considerations do turn out to be real, AES-CTR has better security properties and considerably better performance than HMAC. I don't think we should let the legal regime around crypto limit the quality of the protocol.

Regards,
Maciej

---

From: Willy Tarreau <[email-masked]>
Date: Sun, 9 Jan 2011 21:03:46 +0100

> Even if the export considerations do turn out to be real, AES-CTR has better security properties and considerably better performance than HMAC. I don't think we should let the legal regime around c…

Well, I understand your point, but it could be seen from a different angle :
some will think that it's not worth risking to limit WS adoption just because
we're trying to cover an issue that has been speculated might exist. For
instance, most low-level network equipment would not require any form of
encryption at all. If a NAT router requires support for AES in order to
be able to NAT addresses presented in the stream, it's very well possible
that the firm will need a license to address some countries.

Also, you may be interested in the other experiment I have posted. In short,
we could make such a supposedly existing intermediary emit a request after
feeding it with several megs of data and a few tens of thousands of connection
attempts. In this context, AES-CTR will only require more bytes to be sent
(at most 16 GB). But there is no reason to think that an intermediary that is
broken enough to be able to spot a request after several megs of data is not
able anymore after several gigs.

So in the end, despite the better crypto properties for AES-CTR than HMAC,
whether they're basic XOR, HMAC or AES, they're addressing the same issues
and risks, at different costs to exploit the supposed issues and at different
implementation costs.

Regards,
Willy

---

From: Jack Moffitt <[email-masked]>
Date: Sun, 9 Jan 2011 13:05:50 -0700

> I remember that being said, but I am skeptical. My understanding of US crypto export regulations is that merely using existing crypto facilities from the operating system or from separate component…

This does not seem to be the case:

http://stackoverflow.com/questions/2135081/does-my-application-contain-encryption

It appears not to matter if you use something that is part of the
system, even for uses as benign as using a system library to access an
https URL.  Of course, it's possible Apple is overly conservative.

I don't think it's terribly difficult to get the required permission,
but I imagine that TLS adoption in iOS apps is quite low because of
this problem. Given that the App Store seems to enforce these
regulations, I think we can expect it to also apply to a WebSocket
with AES-CTR.

It appears that this may be improving:

http://www.federalregister.gov/articles/2011/01/07/2010-32803/publicly-available-mass-market-encryption-software-and-other-specified-publicly-available-encryption

jack.

---

From: Maciej Stachowiak <[email-masked]>
Date: Sun, 09 Jan 2011 12:16:31 -0800

> https URL.  Of course, it's possible Apple is overly conservative.

I work for Apple, and the answer there doesn't seem to match what I've heard about export compliance from our legal department. However, since it's a complicated issue, I won't claim there is a definitive answer to this question, and I am certainly not qualified to give legal advice on the matter. 

> http://www.federalregister.gov/articles/2011/01/07/2010-32803/publicly-available-mass-market-encryption-software-and-other-specified-publicly-available-encryption

If the legal regime is being liberalized, then we definitely shouldn't cripple the protocol.

Regards,
Maciej

---

From: Maciej Stachowiak <[email-masked]>
Date: Sun, 09 Jan 2011 12:22:22 -0800

> able anymore after several gigs.

I think your conclusion here is wrong. AES-CTR does not repeat the key schedule on any fixed cycle, as I understand it. It generates a psuedorandom non-repeating keystream. Your analysis was for a repeating 160-bit mask. I'm not sure I am convinced by the rest of your analysis, but it doesn't apply to AES-CTR.

> and risks, at different costs to exploit the supposed issues and at different

Keep in mind that we're trying to address multiple threat models, and also to be robust against attacks we haven't thought of yet. It's definitely not the case that these different approaches are equivalent in all ways, even if it were true that they are equivalent for the "send a giant blow" attack.

Regards,
Maciej

---

From: Jack Moffitt <[email-masked]>
Date: Sun, 9 Jan 2011 13:24:08 -0700

> If the legal regime is being liberalized, then we definitely shouldn't cripple the protocol.

I should have said before, but I agree with this point. The problem
already exists for TLS and other protocols that are pretty critical,
and I see no reason why WebSocket should make concessions for legal
reasons in that context.

jack.

---

From: Willy Tarreau <[email-masked]>
Date: Sun, 9 Jan 2011 21:28:27 +0100

On Sun, Jan 09, 2011 at 12:22:22PM -0800, Maciej Stachowiak wrote:
> I think your conclusion here is wrong. AES-CTR does not repeat the key
> schedule on any fixed cycle, as I understand it.

I've never said that. The fact that it *does not* repeat the key
precisely is what makes it harder to get the expected pattern.

> It generates a psuedorandom non-repeating keystream.

Exactly. And in a pseudorandom keystream, a given 32-bit pattern
will appear once in 16GB, and could appear once in a cleaverly
built 4GB stream too.

> Your analysis was for a repeating 160-bit mask. I'm not sure I
> am convinced by the rest of your analysis, but it doesn't apply
> to AES-CTR.

The program does not appear to AES-CTR, but the base of the analysis
definitely does : we can get a parsable HTTP request that at least
one known intermediary is able to process in 2^32 32-bit patterns.

Regards,
Willy

---

From: Maciej Stachowiak <[email-masked]>
Date: Sun, 09 Jan 2011 12:34:37 -0800

> will appear once in 16GB, and could appear once in a cleaverly

There's no way to guarantee that a chosen 32-bit pattern will appear anywhere in AES-CTR output for an attacker-controlled input. It could appear 0 times, no matter what the input is. So your claim is false.

Regards,
Maciej

---

From: Willy Tarreau <[email-masked]>
Date: Sun, 9 Jan 2011 21:52:02 +0100

> There's no way to guarantee that a chosen 32-bit pattern will appear anywhere in AES-CTR output for an attacker-controlled input. It could appear 0 times, no matter what the input is. So your claim…

That's the principle of randomness. A typical pseudo-random should make
any pattern appear. Of course it is possible that it does not appear, but
the probability to see the pattern at least once in a perfectly random
series of 2^32 patterns is of 1-(1-1/(2^32))^(2^32) = 1-1/e = 63%. It's
already 39% in half the patterns and becomes 86% in the double of the
patterns.

Regards,
Willy

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 10 Jan 2011 10:08:05 +0100

> occasionally push you over some threshold; Amdahl's law and all that.

Eric,

I did not say system that are "already doing a lot of other
processing", I said systems where parsing is around 5% of the CPU
load.   This may be for a high message rate on a large server or it
may be for a low message rate on a constrained device.   For such
systems, multiplying the CPU work needed to parse a message several
times will have significant impacts.

Besides, it is self evident that adding cryptographic processing to a
protocol puts additional loads on application servers - we need only
look at SSL and the existence of SSL offload devices.

regards

---

From: Dave Cridland <[email-masked]>
Date: Mon, 10 Jan 2011 12:50:32 +0000

On Sun Jan  9 19:44:45 2011, Maciej Stachowiak wrote:
> I remember that being said, but I am skeptical. My understanding of  
> US crypto export regulations is that merely using existing crypto  
> facilities from the operating system or from separate components is  
> not subject to export limitations. AES-CTR is in libcrypto which is  
> widely available all over the world. I'm skeptical that there is  
> any place in the world where you can easily use SHA1 HMAC but not  
> AES-CTR. So if anyone wants to claim that use of AES-CTR would  
> cause problems with export regulations, I would ask them to  
> substantiate that claim.
> 
> 
I can only repeat that in the UK, we must ship software such that  
high-grade encryption algorithm support can be disabled, by  
government regulations. Using AES-CTR as a masking algorithm would  
prevent us from shipping with WebSocket support.

> Even if the export considerations do turn out to be real, AES-CTR  
> has better security properties and considerably better performance  
> than HMAC. I don't think we should let the legal regime around  
> crypto limit the quality of the protocol.

Perhaps not, but it would affect the deployment.

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: Eric Rescorla <[email-masked]>
Date: Mon, 10 Jan 2011 07:40:31 -0800

> look at SSL and the existence of SSL offload devices.

Funny you should mention that: all measurements show that the dominant cost
of TLS is the RSA key exchange, which is why it's such a common strategy not
to accelerate the symmetric cryptography at all.

-Ekr

---

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

On Mon, Jan 10, 2011 at 4:50 AM, Dave Cridland <[email-masked]> wrote:
>> I remember that being said, but I am skeptical. My understanding of US
>> crypto export regulations is that merely using existing crypto facilities
>> from the operating system or from separate components is not subject to
>> export limitations. AES-CTR is in libcrypto which is widely available all
>> over the world. I'm skeptical that there is any place in the world where you
>> can easily use SHA1 HMAC but not AES-CTR. So if anyone wants to claim that
>> use of AES-CTR would cause problems with export regulations, I would ask
>> them to substantiate that claim.
>>
>>
> I can only repeat that in the UK, we must ship software such that high-grade
> encryption algorithm support can be disabled, by government regulations.

I don't mean to be flat-out contradictory, but I'd like to see a legal
opinion on this point,
because at least in the US, the use to which you are putting
encryption matters, and
this use would be fine.

-Ekr