Subject: [quicwg/base-drafts] Encrypting Retry token (#3274)

From: Martin Thomson <[email-masked]>
Date: Tue, 26 Nov 2019 23:45:31 -0800

In Singapore, we reached an impasse regarding the use of encryption on Retry.

>From that discussion, there were two outcomes considered:

* "encrypt" using a fixed key and nonce and don't encrypt the token; put the original destination connection ID in the AAD along with the entire packet

* encrypt the token using the fixed key and a nonce that takes the first 8 bytes of the original destination connection ID; the AAD only includes the connection IDs and version

The first can be reduced to running GHASH with a fixed XOR on the final tag if you really want to save effort.  I've implemented and measured that.

The second can be implemented naively, just by building a new AES key for every record.  That's not terribly slow at 2.8x slower.  With some nasty tricks, I was able to get the AES version under 1.7x slower.  Given the relative cost of these functions, I think that this is an acceptable cost.

There's no guarantee that this is correct - I haven't even checked that these programs produce the right output, but the count of operations is approximately right, so I'm posting this issue.  My code can be found at [martinthomson/quic-retry-tag](https://github.com/martinthomson/quic-retry-tag/blob/master/bench.c) in case reproduction or validation thrills you.

Here's the output of a sample run on my old machine with about 1Mb of Retry packets fed through the different implementations, which takes about 32 seconds to complete:

```
Measuring best of 1000 iterations
ghash:          22450242
aes_gcm_slow:   60070152
aes_gcm_fast:   35240211
```

Now, obviously this is a microbenchmark.  The rest of the cost will be elsewhere, but I tried to isolate the variable.  Hopefully this helps the decision-making process.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3274

---

From: Martin Thomson <[email-masked]>
Date: Wed, 27 Nov 2019 15:26:13 -0800

Since I did this, I've realized that even this was an overly pessimistic outcome.  By precomputing the XOR stream for CTR protection, it should be possible to make an even faster version of the protected form here.

The result should be to narrow the gap between the GHASH-only and encrypted variant further.  The difference should be limited to performing an XOR with a fixed value and a single AES operation (which in my experience is marginally cheaper than an extra GHASH operation, though the addition of ODCID to the AAD is rarely a full block, so it's hard to predict the exact outcome).

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3274#issuecomment-559284228

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 27 Nov 2019 19:28:28 -0800

@martinthomson 
> Since I did this, I've realized that even this was an overly pessimistic outcome. By precomputing the XOR stream for CTR protection, it should be possible to make an even faster version of the prot…

I might be missing something, but I wonder if you can precompute the XOR streams for all the nonces (2<sup>64</sup> bits).

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3274#issuecomment-559327038

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 27 Nov 2019 19:34:12 -0800

Regarding the numbers, Martin, thank you for collecting them.

I think that the benchmark confirms our expectation that the cost of running AES (based on fixed key, with different nonce) does not matter when a conventional CPU with AES offloading is used.

Though I think the other question might be if we can require all the DDoS mitigation boxes to be capable of running AES fast.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3274#issuecomment-559328131

---

From: Martin Thomson <[email-masked]>
Date: Wed, 27 Nov 2019 19:37:18 -0800

> I might be missing something, but I wonder if you can precompute the XOR streams for all the nonces (2<sup>64</sup> possibilities).

Oh, and I realized again why I didn't do that yesterday: 2<sup>64</sup> lots of precomputation is a little too much :)  Forget that bit.  The numbers are basically correct.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3274#issuecomment-559328712

---

From: Martin Thomson <[email-masked]>
Date: Wed, 27 Nov 2019 21:52:37 -0800

Here are the results from a different system (ignore absolute values and concentrate on relative values):

```
ghash:           5825976
aes_gcm_slow:   18750874
aes_gcm_fast:    8619132
```

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3274#issuecomment-559352347