Subject: Re: [quicwg/base-drafts] Why does stateless reset have to be checked after MAC failure (#2152)

From: Martin Thomson <[email-masked]>
Date: Mon, 26 Aug 2019 04:02:34 -0700

@ekr, I know that this is now old, but I think that there's something here.  Not in the ordering, which I think is not important, but in the constant time piece.

I think that this implies that constant-time comparison with every viable stateless reset is something we should do on every packet.

There's been an assumption throughout that packet processing time for dropped packets isn't observable.  I think that's a bad assumption, frankly.  It's not like you can't put a packet with a known processing time after each probe.  

So I think that we've got to at least say that this is what happens.  But we've just raised the packet processing load considerably, so I doubt that this will be well received.

-- 
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/2152#issuecomment-524817436

---

From: MikkelFJ <[email-masked]>
Date: Mon, 26 Aug 2019 04:17:27 -0700

Depending on implementation it can be very hard to do constant time.

Even if you compare keys in constant time, the cache latency can be much higher. For stateless resets I'd assume a lookup only happens once and then it is removed from, say, a hash table. That is, there is no cache latency difference between a valid and an invalid lookup. Compare this to connectionsID's that are looked up frequently. Here it is possible to guess to valid CID's based on lookup times.

But even if you do not have cache latency issues, you have hash collision issues. This makes a hash table unsuitable. The alternernative is binary tree, or a trie. The binary tree will be have to modified to do log N comparisons for all lookups even if the key is found higher up. And regardless a binary tree is much much slower than a hash table. Tries are very complex to implement correctly and must still be implemented for maximum search path comparison.

Another approach is to timestamp the lookup and busyloop until you reach, say, 100ns of cpu cycles after performaning the lookup in a hash table. This is still faster than a binary tree, but slower than the trie.

I seriously doubt most implementations would go out of their way to make resets effectively constants time.

So the question is - does that make most implementations trivial targets for DoS resets?
And what about guessing CID's?

How can practically protect against this, because trusting the implementation to be constant time is not realistic.

-- 
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/2152#issuecomment-524821286

---

From: MikkelFJ <[email-masked]>
Date: Mon, 26 Aug 2019 04:21:31 -0700

A related problem is the use of API access tokens. Many people argue against JWT token validation because you cannot retire a JWT token. But a JWT token is easy to verify in constant time. An opaque access token must be looked up, and this is very hard to do constant time. This could be major security concern on the internet at large.

-- 
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/2152#issuecomment-524822313

---

From: MikkelFJ <[email-masked]>
Date: Mon, 26 Aug 2019 04:23:54 -0700

Thus, a solution to the reset problem could be to define an algorithm and share keys with the client. The problem is that the clients key must be session specific while that server cannot share its server keys, so something creative must be invented. If this is done, another latency will be added to the per packet overhead, which is also not desirable, similar to header protection.

-- 
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/2152#issuecomment-524822878

---

From: Martin Thomson <[email-masked]>
Date: Mon, 26 Aug 2019 04:30:42 -0700

I imagine this to be much simpler than you suggest.  An endpoint that sends packets using a given set of connection IDs puts all the associated stateless reset tokens into a structure.  Then along with decrypting packets, it iterates through that structure and performs a constant time comparison with each.  That's something that won't have weird cache usage patterns, other than the usual cost of getting these values into the cache if they fall out.  The number of active values shouldn't be a secret, which is most of what that tells you.

The result of this will be two Boolean values: whether the AEAD was OK and whether the stateless reset was triggered.  An authentic packet will be the logical OR of those two values.  Anything else is dropped.  After that point, you have crossed into packets being "good", so the time you take to process the packet is less of a concern.

-- 
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/2152#issuecomment-524824568

---

From: MikkelFJ <[email-masked]>
Date: Mon, 26 Aug 2019 04:48:39 -0700

If you can guarantee that there are only a short list to search, then yes. But it is only per connection ID that list is short, so you need to make the connection ID lookup constant time. You can potentially have much more than 100K connection ids to map. For normal operation you first validate the packet, so here the CID lookup is less critical, but for reset that is not the case. Clearly performing a linear search over all CID's is not viable.

-- 
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/2152#issuecomment-524829243

---

From: Martin Thomson <[email-masked]>
Date: Mon, 26 Aug 2019 05:03:11 -0700

I think that the list could be narrowed by path.  If you have tons of connections on the same path, yeah, that's not great.

-- 
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/2152#issuecomment-524833309

---

From: MikkelFJ <[email-masked]>
Date: Mon, 26 Aug 2019 09:05:58 -0700

You don't need constant time because you are not replying to the reset. Worst case is that you ignore / reject the reset and continue sending observable packets. The timing of those packets is largely (but not entirely) independent of the reset lookup timing. Further, if a reset is successfully guessed, you are dead, so the only thing to protect is how you test for and react to unmatched resets. If packets are paced you should be good.

-- 
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/2152#issuecomment-524920971

---

From: Martin Thomson <[email-masked]>
Date: Mon, 26 Aug 2019 16:40:12 -0700

> You don't need constant time because you are not replying to the reset. 

That assumes that you don't have observable behaviour that follows the processing of that packet.  What I'm concerned about is being able to measure the time to compare, which gives an attacker a read on the value of the stateless reset token.

I think that it is sufficient for the comparison of each stateless reset token to be constant time, but the process might be cut short if a match is found.  And it might be OK to not check stateless reset tokens if the packet decrypts successfully.  That would all be on the basis that we're protecting multiple discrete items and not a single secret.

-- 
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/2152#issuecomment-525074690

---

From: MikkelFJ <[email-masked]>
Date: Tue, 27 Aug 2019 00:14:20 -0700

A practical solution to the problem is to sample dropped packets and process these during idle time and eventually tear down a connection if necessary, rather than immediately. It can also be done in a separate thread although that on its own will not fully hide timing.

-- 
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/2152#issuecomment-525172262

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 27 Aug 2019 00:52:47 -0700

While I agree that endpoints should not leak information that let's the attacker guess a valid token value, I am not sure if we need to require constant time comparison, as suggested by #2993.

I think that the practical defense would be mix a secret seed securely into the hash key (e.g., by using HMAC), much like we do for hash tables to prevent DoS collision attacks. Assuming that we mix a secure seed, the attacker would not be possible to deduce information from the response time of the hash table.

-- 
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/2152#issuecomment-525184801

---

From: Martin Thomson <[email-masked]>
Date: Tue, 27 Aug 2019 06:44:48 -0700

Assume that you do have a way of measuring how long it takes to process a garbage packet.  Also assume that there is just one token.  If you don't compare in constant time, the attacker can measure how long it takes to compare the possible token with the real token.  For every byte that matches, you take a tiny bit longer.  A complete search takes just 2^12 guesses, multiplied by any oversampling factor you might need to extract the side channel information.  That makes it not very hard.

-- 
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/2152#issuecomment-525308095

---

From: MikkelFJ <[email-masked]>
Date: Tue, 27 Aug 2019 07:00:42 -0700

But if you need that many guesses to kill a connection, it is not viable. If it is to guess a master secret, the solution is to use a one way hash. Guessing a specific token will not reveal anything of importance beyond being able to kill the connection.

-- 
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/2152#issuecomment-525314829

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 27 Aug 2019 10:13:12 -0700

@martinthomson That's a fair point.

Let me adjust my approach: use `PRP(stateless_reset_token)` internally comparing the stateless reset tokens. For example, we could use `AES(master_secret, stateless_reset_token)`. Then, we would not leak anything even if both the hash lookup or the comparison of the token values (now done by comparing the values permuted by AES) are not constant-time.

-- 
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/2152#issuecomment-525397064

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 27 Aug 2019 10:29:11 -0700

OK for comparing each reset token, I think using PRP can be considered as a way of implementing constant-time comparison.

Then, the discussion would be if we should state something like: "lookup of stateless reset tokens MUST NOT leak timing information. Such lookup table can for example be implemented by using PRP(stateless_reset_token) instead of the stateless reset token itself, for lookup and comparing the values."

-- 
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/2152#issuecomment-525403268

---

From: Martin Thomson <[email-masked]>
Date: Tue, 27 Aug 2019 15:37:51 -0700

Using a PRP like that requires touching all the values in constant time anyway, so that's just a more expensive method of doing a constant-time comparison.

-- 
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/2152#issuecomment-525510181

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 27 Aug 2019 16:03:56 -0700

I do not think that it would be expensive. Rather, I think using PRP might be the simplest and cheapest way.

The hash table needs to use be resistant to hash collision DoS attacks, because the stateless reset tokens are supplied by the peers. Therefore, to calculate the hash key, I'd assume that endpoints would be using some function that takes a master secret and a stateless reset token. That function can be a PRP.

-- 
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/2152#issuecomment-525516439

---

From: Martin Thomson <[email-masked]>
Date: Tue, 27 Aug 2019 17:21:40 -0700

If you are using a hash table, sure.  But if you can narrow the values down to those tokens that were associated with packets sent on that path, a list would be a better storage method and then a straight constant-time comparison is much simpler.

-- 
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/2152#issuecomment-525532718

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 27 Aug 2019 18:57:05 -0700

Yeah I am not sure if you would want to maintain a hash table using paths as keys just for that purpose. IIUC, at the moment, there is no need for such a hash table on the server side.

-- 
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/2152#issuecomment-525551331