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

From: Martin Thomson <[email-masked]>
Date: Sun, 01 Dec 2019 14:05:51 -0800

>From @huitema:

> I went on to compare the time to encrypt 64 bytes versus the time to just authenticate 64 bytes. Results are below for two implementations of AES128 GCM, one from OpenSSL crypto library and another from Windows Bcrypt library -- both measured using 64 bit code on my Windows laptop:

   | encrypt | decrypt | authenticate | verify
--  | -- | -- | -- | --
bcrypt  | 0.35751 | 0.22602 | 0.24687 | 0.20189
openssl 1.1.1c | 0.30211 | 0.23956 | 0.24296 | 0.23926

> The times are measured here in microseconds -- these are the average on 100,000 operations. We see that the times are fractions of microseconds in both cases. The encryption operation is more expensive than a simple authentication, 45% more with brcrypt, 24% more with openssl. The decrypt operation is 12% more expensive than the simple authenticate with brcypt, almost the same with openssl.

-- 
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-560165426

---

From: David Schinazi <[email-masked]>
Date: Mon, 02 Dec 2019 09:31:42 -0800

These results are making me lean towards encrypting the token using the original connection ID as a nonce, but I don't feel overly strongly. I'll let folks share their thoughts here and if I don't hear back I'll add encryption to #3120.

-- 
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-560497423

---

From: Martin Thomson <[email-masked]>
Date: Mon, 02 Dec 2019 19:57:45 -0800

It's possible that the values @huitema produced for just authentication are high.  Most GCM implementations will still run the AES operation necessary to calculate the mask for GHASH.  With a fixed key and nonce, that operation can be replaced with a simple XOR.  Doing that additional optimization is not obvious, and it requires breaking the AEAD box open, but I expect that this will happen if implementations REALLY care about every cycle.

That would increase the difference a little, maybe as much as my 1.7x (or 1.5x on the newer CPU).

-- 
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-560987614

---

From: ekr <[email-masked]>
Date: Mon, 02 Dec 2019 21:51:32 -0800

I think at this point we need to see some data that supports the argument that encrypting the token is too slow. @nibanks, i think this was your view?

-- 
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-561010456

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 03 Dec 2019 07:50:46 -0800

What about the cost to the recipient of the Retry packet?  Currently, it is as simple as [looking up the token in a hash](https://github.com/litespeedtech/lsquic/blob/7ee4152504cba5b0a4b79ed9eab2cf8134128975/src/liblsquic/lsquic_engine.c#L1211).  IIUC, encrypting the token would replace the hash lookup with a decryption operation?

-- 
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-561229121

---

From: ekr <[email-masked]>
Date: Tue, 03 Dec 2019 08:03:35 -0800

This seems like an insignificant cost, given that any successful QUIC
connection will involve quite a lot more cryptography.

On Tue, Dec 3, 2019 at 7:50 AM Dmitri Tikhonov <[email-masked]>
wrote:

> What about the cost to the recipient of the Retry packet? Currently, it is
> as simple as looking up the token in a hash
> <https://github.com/litespeedtech/lsquic/blob/7ee4152504cba5b0a4b79ed9eab2cf8134128975/src/liblsquic/lsquic_engine.c#L1211>.
> IIUC, encrypting the token would replace the hash lookup with a decryption
> operation?
>
> —
> You are receiving this because you commented.
> Reply to this email directly, view it on GitHub
> <https://github.com/quicwg/base-drafts/issues/3274?email_source=notifications&email_token=AAIPLIKFWTSULAWAXEY4GCDQWZ543A5CNFSM4JSCYGX2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEFZ22QI#issuecomment-561229121>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/AAIPLIPPIIJY5J5XDTAZ32DQWZ543ANCNFSM4JSCYGXQ>
> .
>

-- 
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-561235085

---

From: Nick Banks <[email-masked]>
Date: Tue, 03 Dec 2019 08:04:56 -0800

I'm working with our hardware vendor that does DoS mitigation for Azure. Give me a little time and I'll try to get back to you with data.

Also, as far as the cost to the client for Retry, IMO, the higher the better. The goal in this scenario is to make it more expensive for attackers who are spamming initial packets. For a normal client creating a single connection, the cost is insignificant as ekr points out.

-- 
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-561235673

---

From: Nick Banks <[email-masked]>
Date: Fri, 06 Dec 2019 17:07:34 +0000 (UTC)

Here's a quote from our hardware partner:

> Here's some preliminary numbers. Due to code and library complexities, my team could not do the AES testing, but we could generate some results with the ghash.
> 
> The main thing is, encryption vs no encryption.
> Using no encryption as base (1x),  with ghash calculated, the CPU usage is roughly ~2.5x higher.
> 
> And if we expect AES to be 1.7x to 2.8x slower than ghash, we're looking at 4.25x to 7x slower for no encryption vs AES encryption.

And a bit more details in follow up:

> Again, these are preliminary numbers, and since we use ghash as benchmark base, the factor with different cpu generation & AES support is a little bit reduced here...
> 
> And, of course, the code is not tuned to the optimal, as we just took from the libraries mentioned by the link. (And I don't know how much of room left to tune the ghash & aes)
> 
> Attached is a little bit more details:
```
No ghash
------------------------------------------------------------
CPU Usage
Data1   14%   12%   11%   14%   12%

Port   InPPS   InBPS   OutPPS   OutBPS   
--------------------------------------------------------------------------
1   21738.64   22651666.98   0.00   0.00  
2   0.40   23.98   21738.64   22651666.98  

Ghash
------------------------------------------------------------
Data1   21%   29%   26%   27%   30%

Port   InPPS   InBPS   OutPPS   OutBPS  
--------------------------------------------------------------------------
1   20850.42   21725742.72   0.40   23.98   
2   0.40   23.98   20850.02   21725718.74  
```

I'm still of the opinion that, since the Retry packet is almost purely a DoS mitigation mechanism, our view should be what's the absolute simplest design we can take and still get what's absolutely necessary, not nice to have; instead of what else can we squeeze into this feature and hopefully not make it "too expensive".

-- 
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-562656995

---

From: Jana Iyengar <[email-masked]>
Date: Fri, 06 Dec 2019 12:08:14 -0800

I'm in agreement with @nibanks. My interest here is to detect corruption of Retry packets, and a ghash (equivalent) is adequate. Everything else is a nice to have... and I don't care much for these.

-- 
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-562719784

---

From: Christian Huitema <[email-masked]>
Date: Fri, 06 Dec 2019 12:43:51 -0800

I think I agree with Nick's reasoning. We started this issue by looking only at corruption during transmission. If we focus on that, a simple checksum would be sufficient. We can now start spin-bitting the checksum: crc64, fnv1a, 0-keyed aesgcm, md5... In fact, for curiosity, what is the spec of ghash?

-- 
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-562730566

---

From: David Schinazi <[email-masked]>
Date: Fri, 06 Dec 2019 13:08:32 -0800

@huitema I don't think we need to bikeshed the checksum. We already agreed in Cupertino that we'd use GMAC (which some people seem to call GHASH apparently?) which is equal to AES-128-GCM with an empty plaintext.

-- 
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-562737639

---

From: Praveen Balasubramanian <[email-masked]>
Date: Sat, 07 Dec 2019 05:31:42 -0800

I too think anything more than a checksum is unnecessary here. For a corner case scenario where there is NATting, we should not make the common case expensive. Given this is a DoS protection scenario when the system is deemed to be under attack, the mechanism we pick must be the least CPU intensive. My vote is to just keep simple checksum. Anything more is unnecessary because no need has been demonstrated for it. 

-- 
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-562851528

---

From: ianswett <[email-masked]>
Date: Mon, 09 Dec 2019 10:28:04 -0800

Agreed, let's stick with a checksum(GMAC/GHASH) as agreed in Cupertino

-- 
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-563368715

---

From: MikkelFJ <[email-masked]>
Date: Mon, 09 Dec 2019 12:06:33 -0800

If it's not clear, GHASH is the underlying hash algorithm for GCM and addition to the AES encryption track, but it somehow needs a key and a way to specify content and somewhere to place the result. GCM provides the framework for that hence GMAC is additional authenticated data without encrypted plaintext. Since there is no encryption in GMAC, GMAC is essentially GHASH, but with a clear way to specify the input/output parameters. There is probably an extra AES block encryption in GMAC to derive the GHASH key, and possibly an extra AES block encryption on the output, compared to raw GHASH, but I do not remember exactly.

-- 
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-563412734

---

From: MikkelFJ <[email-masked]>
Date: Mon, 09 Dec 2019 12:30:21 -0800

Using raw GHASH over GMAC would avoid the need for an AES module in hardware and only require carryless multiplication (CLMUL) for efficient operation, but I can't imagine where that case would be very relevant. Even on low-end microcontrollers it is more likely you have SHA-256 and AES hardware than CLMUL, at least for now. From that perspective Poly1305 would be more efficient, but given the nature of Retry and the dependence on AES-GCM elsewhere in the protocol, GMAC or GHASH makes more sense. GMAC is much simpler than GHASH because it can use existing libraries. If GHASH were to be used directly one would have to ensure that it is safe in the applied context and with the supplied key whereas GCM is well understood even if it costs a few block encryptions extra.

-- 
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-563423756

---

From: Martin Thomson <[email-masked]>
Date: Mon, 09 Dec 2019 13:37:26 -0800

As the PR proposes, GMAC is what we are using. A simple implementation can then just use GCM. Someone looking to save one AES operation can run GHASH with an XOR.

This saves on the number of primitives, and for someone willing to build silicon, it can be implemented fairly efficiently.

There is some odd middle space with software implementations on low end hardware that might be a little worse off, but they win because they need fewer primitives. A low end device probably needs external help with DoS, so maybe we can say that this is a net win.

To be clear,  Nick's situation isn't ideal either. Implementing GMAC in hardware is certainly not free, falling back to software is not fast, and this style of standalone DoS protection is otherwise relatively simple. But there are a number of competing concerns that need to be balanced.

-- 
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-563451278

---

From: MikkelFJ <[email-masked]>
Date: Mon, 09 Dec 2019 13:52:20 -0800

I don't think you can avoid the AES for GMAC, at least not if both endpoints are to verify the MAC. This is because GCM first receives a "master" key which it then splits into two keys, one for encryption and one for GHASH. This key split is done with an AES operation. So unless both endpoints agree on the GHASH key directly, you need to use AES to derive the GHASH key.

-- 
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-563456791

---

From: MikkelFJ <[email-masked]>
Date: Mon, 09 Dec 2019 14:04:52 -0800

I'm not sure if it is safe to use a fixed key for GMAC because the collision restance of GCM is the same as for GHASH, which limits traffic to roughly 2^32 bytes and places requirements on non-reuse.

-- 
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-563461576

---

From: Martin Thomson <[email-masked]>
Date: Mon, 09 Dec 2019 15:57:16 -0800

Yes, this is not "secure" in the sense that it would meet IND-CCA.  After all, we are publishing the key in an RFC.  The point is to reduce this to a checksum.

The arguments about "encryption" all amount to a desire to make accessing the Retry more difficult for a casual observer.  Someone with a copy of the RFC will obviously have no trouble.

-- 
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-563495059

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 09 Dec 2019 16:31:58 -0800

My +1 goes to just doing GMAC, due to the reasons others have laid out.

I'd also note that it is unlikely that middleboxes will ossify on the fact that the values of the token fields in Retry and Initial packets are equivalent, based on the behavior those developers see on the wire. This is because Retry is expected to be used *only* when there is an attack. Or, if those developers read the spec, the token will get ossified regardless of if it's encrypted in the Retry packet.

-- 
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-563504054

---

From: martinduke <[email-masked]>
Date: Wed, 18 Dec 2019 13:38:22 -0800

+1 to GMAC, though I care much more about resolving this (as one of the few remaining wire image issues) prior to draft-25 than what the actual outcome is.

I think it's important that draft-25 be the last wire image change for a while.

-- 
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-567224382

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 18 Dec 2019 20:52:10 -0800

This thread got poorly forked from #3014. We've already marked #3014 as proposal-ready, and I'm marking this proposal-ready as well.

-- 
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-567331873