Subject: Re: [quicwg/base-drafts] Perform stateless reset token comparisons in constant time (#2993)

From: Jana Iyengar <[email-masked]>
Date: Tue, 03 Sep 2019 15:29:20 -0700

janaiyengar approved this pull request.

-- 
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/pull/2993#pullrequestreview-283294497

---

From: Jana Iyengar <[email-masked]>
Date: Tue, 03 Sep 2019 15:35:40 -0700

... modulo change to accommodate @kazuho 's comment.

-- 
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/pull/2993#pullrequestreview-283296425

---

From: ianswett <[email-masked]>
Date: Tue, 03 Sep 2019 15:35:46 -0700

ianswett approved this pull request.

Given how simple this is to do in practice, it seems worthwhile, even if the attack is not a very effective one.

-- 
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/pull/2993#pullrequestreview-283296452

---

From: Martin Thomson <[email-masked]>
Date: Tue, 03 Sep 2019 15:41:24 -0700

@martinthomson pushed 1 commit.

9e7142b9989bad34fdd86cc9c7dec57abfe514ea  Be a little clearer about what is being protected

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2993/files/e4123fc84870a688212a82b48fec71cc44d729ab..9e7142b9989bad34fdd86cc9c7dec57abfe514ea

---

From: Marten Seemann <[email-masked]>
Date: Tue, 03 Sep 2019 15:45:34 -0700

Maybe I'm missing something obvious here, but how is this easy to implement?

In my implementation, I have a map of reset tokens -> connections. Unless I switch to a constant time map implementation (the standard library doesn't provide one, you'd have to write that yourself), the comparisons are (probably?) not constant time. Given that this would cause some considerable complexity, I don't think it's worth defending against this rather uninteresting attack, and I'm not sure if a MUST is the right way to go here.

-- 
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/pull/2993#issuecomment-527669147

---

From: ianswett <[email-masked]>
Date: Tue, 03 Sep 2019 16:16:16 -0700

To support @marten-seemann point, a SHOULD and a comment about why you should do it and the impact of not doing so seems fine to me.

-- 
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/pull/2993#issuecomment-527676016

---

From: Martin Thomson <[email-masked]>
Date: Tue, 03 Sep 2019 17:50:22 -0700

One thing that I'm trying to protect is the integrity of the specification and the analysis that (I hope) will come.  If we allow weaseling out of this sort of requirement, then the analysis has to allow for that too.

If you are using a hash map, then you can do as @kazuho suggests: use a PRP (a PRF would also work) to produce an intermediate value from the incoming value and compare that in non-constant time.  As long as the operation cannot be reversed by an attacker and the secret input to the PRP (i.e., the token) are handled in constant time, the secret doesn't leak.

We can't assume that resetting a connection is without cost.  QUIC has the nice property that connections can survive network flutters, which means that a lot of investment could be made in a connection.  (That's probably still inadvisable.)  A well-positioned attacker doesn't have to perform a huge amount of work to recover a stateless reset token, relative to the value they might gain in disrupting a "high-value" connection of that sort.

If we use a "MUST", then we're not stopping someone from deciding that this requirement doesn't apply to them.  But they would take responsibility for that, hopefully with some awareness of what is being risked.  Yes, we could use "MUST avoid leaking through timing side channels unless <X>", but determining what X needs to be is tricky as it depends so much on application protocol and other contextual stuff.

-- 
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/pull/2993#issuecomment-527694231

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 03 Sep 2019 18:46:30 -0700

kazuho approved this pull request.

-- 
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/pull/2993#pullrequestreview-283340375

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 03 Sep 2019 19:10:10 -0700

@marten-seemann 
> In my implementation, I have a map of reset tokens -> connections. Unless I switch to a constant time map implementation (the standard library doesn't provide one, you'd have to write that yourself)

As I stated on the issue, using a "standard hash map implementation" for storing stateless reset tokens as-is is not a good approach, as it might be vulnerable to [hash flooding DoS attacks](https://131002.net/siphash/siphashdos_appsec12_slides.pdf). I think this is a unique property for a hash map containing stateless reset tokens; hash maps containing CIDs is not susceptible to the issue as CIDs are chosen by the endpoint (rather than the peer), nor are the hash maps containing streams, as stream IDs are generated in sequential order (assuming that an endpoint would not have a very high stream concurrency per each connection).

Considering that, we _might_ want to state something like the following in Security Considerations: _As the stateless reset tokens are controlled by the peers, QUIC endpoints SHOULD be resistant to hash flooding DoS attacks when using a hash map for retaining those tokens. One way of achieving such property is to retain and compare the transformed values of the stateless tokens where the transformation is defined as a cryptographically-secure pseudo-random permutation (e.g., block cipher) or a pseudo-random function (e.g., secure hash function), instead of using the raw token values as the hash keys. This approach also satisfies the constant time comparison requirements in section x.y._

-- 
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/pull/2993#issuecomment-527709362

---

From: Martin Thomson <[email-masked]>
Date: Tue, 03 Sep 2019 19:15:31 -0700

A PR that said that might be worth talking about.

Nit: You need the "secure hash function" to be keyed in some way.

-- 
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/pull/2993#issuecomment-527710413

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 03 Sep 2019 19:30:33 -0700

@martinthomson Fair enough. Created #3005.

-- 
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/pull/2993#issuecomment-527713303

---

From: Marten Seemann <[email-masked]>
Date: Tue, 03 Sep 2019 22:13:21 -0700

> One thing that I'm trying to protect is the integrity of the specification and the analysis that (I hope) will come. If we allow weaseling out of this sort of requirement, then the analysis has to…

@martinthomson I was wrong on this, and you're absolutely right. Implementation difficulties shouldn't make us lower our security guaranties, or the language we use to describe them.

@kazuho Thanks for the pointer to the hash flooding attack. By the way, here's the [video](https://media.ccc.de/v/29c3-5152-en-hashflooding_dos_reloaded_h264) corresponding to the slides you linked.

-- 
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/pull/2993#issuecomment-527742872

---

From: Martin Thomson <[email-masked]>
Date: Tue, 03 Sep 2019 23:05:27 -0700

Rust has inbuilt defenses against hash flooding, and some languages have that built in.  Note that this is something that doesn't guarantee constant time over inputs, as that is generally not a design goal, though many schemes have that naturally.  Even then, the functions used might be trivially reversible.

-- 
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/pull/2993#issuecomment-527755292

---

From: Martin Thomson <[email-masked]>
Date: Wed, 04 Sep 2019 19:32:48 -0700

8908632504a0db7467ea73f05ceb99b0537ee72c  add example that uses PRF

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2993/files/9e7142b9989bad34fdd86cc9c7dec57abfe514ea..8908632504a0db7467ea73f05ceb99b0537ee72c