Subject: [quicwg/base-drafts] Add Security Considerations for SRT collision attack (#3005)

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

Addresses the concerns discussed in #2993, #2152.

**Warning: this PR builds on top of #2993.** Please let me know if you&#39;d want me to open an issue for this and handle the PR separately rather than piggybacking on #2993.
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/3005

-- Commit Summary --

  * describe collision attack on SRTs

-- File Changes --

    M draft-ietf-quic-transport.md (13)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/3005.patch
https://github.com/quicwg/base-drafts/pull/3005.diff

-- 
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/3005

---

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

@kazuho pushed 1 commit.

ef66d4679da7f5046b9343bd477a2011f182ecb6  _hash_ collision attack

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3005/files/942e430c55473a6ec2f261d0ec78835fe2895200..ef66d4679da7f5046b9343bd477a2011f182ecb6

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 03 Sep 2019 21:52:31 -0700

@kazuho pushed 1 commit.

c36c242c108a417f8190febc847c6e29531270a8  it's not constant time

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3005/files/ef66d4679da7f5046b9343bd477a2011f182ecb6..c36c242c108a417f8190febc847c6e29531270a8

---

From: ianswett <[email-masked]>
Date: Wed, 04 Sep 2019 04:54:28 -0700

ianswett approved this pull request.

Thanks for pointing this out.  A similar concern exists on the server side for connection ID lookup I believe?  Not as much the constant time aspect, but hash collisions.

-- 
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/3005#pullrequestreview-283560513

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 04 Sep 2019 07:41:37 -0700

janaiyengar commented on this pull request.

> @@ -5730,6 +5730,17 @@ decisions are made independently of client-selected values; a Source Connection
 ID can be selected to route later packets to the same server.

+## Hash Collision Attack on Stateless Reset Tokens
+
+As the stateless reset tokens are controlled by the peers, QUIC endpoints SHOULD

```suggestion
Since stateless reset tokens are generated by peers, endpoints SHOULD
```

> @@ -5730,6 +5730,17 @@ decisions are made independently of client-selected values; a Source Connection
 ID can be selected to route later packets to the same server.

+## Hash Collision Attack on Stateless Reset Tokens
+
+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

Is there an easy reference that can be cited for "hash flooding DoS attacks"?

> @@ -5730,6 +5730,17 @@ decisions are made independently of client-selected values; a Source Connection
 ID can be selected to route later packets to the same server.

+## Hash Collision Attack on Stateless Reset Tokens
+
+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

```suggestion
be resistant to hash flooding DoS attacks when using a hash map for storing and comparing
```

> @@ -5730,6 +5730,17 @@ decisions are made independently of client-selected values; a Source Connection
 ID can be selected to route later packets to the same server.

+## Hash Collision Attack on Stateless Reset Tokens
+
+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

```suggestion
those tokens. One way of achieving this property is to store and compare
```

> @@ -5730,6 +5730,17 @@ decisions are made independently of client-selected values; a Source Connection
 ID can be selected to route later packets to the same server.

+## Hash Collision Attack on Stateless Reset Tokens
+
+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 pseudo-random permutation (e.g., block cipher) or a keyed hash (e.g., HMAC
+{{?RFC2104}}) that is cryptographically secure, instead of using the raw token
+values as the hash keys.  This approach satisfies the secure comparison

Suggested rephrase: "... transformed values of the stateless tokens instead of the raw token values. A transformation such as a pseudo-random permutation (e.g. block cipher) or a cryptographically-secure keyed hash (e.g., HMAC {{?RFC2104}}) can be used to also ensure that comparing stateless tokens does not leak timing information, as specified in {{detect-stateless-reset}}."

-- 
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/3005#pullrequestreview-283653099

---

From: Martin Thomson <[email-masked]>
Date: Wed, 04 Sep 2019 07:41:59 -0700

martinthomson commented on this pull request.

I'm not entirely sure that this is something we need to highlight.  This is a well-known DoS risk with hash tables.  Documenting every way in which sub-optimal use of common data structures and algorithms might lead to exposure would be an endless task.

What we might want to emphasize is the how the requirement not to expose bits of the stateless reset token is difficult to achieve in certain contexts and how that limitation might be overcome.

As it is, this reads like general advice about hash table stuffing attacks.  But that masks the core issue about leakage.  The point to emphasize is that there is a transform in use that would cause leakage of the used value not to endanger the underlying value that is being tested.  That you need to use a PRF (note: PRP ⊆ PRF, so you don't need to mention that) is the key point.  And you only need that because you might use the value in a way that could leak.  If you don't (and there are designs that might allow that), then this complication isn't needed.

Of course, a nice consequence of keying off a PRF-scrubbed value is that you don't have to worry about hash stuffing.  But that's a secondary benefit.

-- 
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/3005#pullrequestreview-283668224

---

From: MikkelFJ <[email-masked]>
Date: Wed, 04 Sep 2019 07:50:35 -0700

I agree, it a hash table attack is a valid concern, but it also, to a lesser degree, applies to attacks in CIDs and so forth.

As far as I am aware, the Linux kernel chose RB-trees over hash tables in their network stack. But that is a slow solution.

-- 
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/3005#issuecomment-527936410

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 04 Sep 2019 17:37:55 -0700

@kazuho pushed 1 commit.

68c8254f3e58241d1b1511bdcb683663da7e97c8  Update draft-ietf-quic-transport.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3005/files/c36c242c108a417f8190febc847c6e29531270a8..68c8254f3e58241d1b1511bdcb683663da7e97c8

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 04 Sep 2019 17:38:29 -0700

@kazuho pushed 1 commit.

65963b0a62131a7b958382a508f2cfe50262f6cc  Update draft-ietf-quic-transport.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3005/files/68c8254f3e58241d1b1511bdcb683663da7e97c8..65963b0a62131a7b958382a508f2cfe50262f6cc

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 04 Sep 2019 17:38:43 -0700

@kazuho pushed 1 commit.

c97a0300480235812d88b6f95f62f4f2f6530223  Update draft-ietf-quic-transport.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3005/files/65963b0a62131a7b958382a508f2cfe50262f6cc..c97a0300480235812d88b6f95f62f4f2f6530223

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 04 Sep 2019 18:28:42 -0700

Closed #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/3005#event-2608979267

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 04 Sep 2019 18:28:45 -0700

ian

-- 
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/3005#issuecomment-528156559

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 04 Sep 2019 18:28:46 -0700

Reopened #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/3005#event-2608979363

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 04 Sep 2019 18:38:48 -0700

@ianswett 
> A similar concern exists on the server side for connection ID lookup I believe? Not as much the constant time aspect, but hash collisions.

That's a good point. For most CIDs no, but yes for the server CIDs that are initially chosen by the client. Though, for such CIDs, I think a hash map that uses `client-address-port || CID` as the key should be used for identifying connections, as the collision of CIDs (rather than the collision of hashed values) would be an issue.

We might want to expand on that.

OTOH, I think @martinthomson makes a good point in asking if collision of hashed values (or raw values) in general is something we need to talk. If we are to limit the discussion to how endpoints can fulfill the no-leak requirement regarding stored SRTs, maybe something like https://github.com/kazuho/base-drafts/commit/8908632504a0db7467ea73f05ceb99b0537ee72c would be sufficient.

FWIW, my intent behind creating this PR has been to give advice on how implementations can cope with the requirement, and nothing more.

-- 
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/3005#issuecomment-528158485

---

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

I think that kazuho@8908632 would be sufficient.  Let me see how I can cherry-pick that.

-- 
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/3005#issuecomment-528169505

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 04 Sep 2019 19:35:41 -0700

@martinthomson Thank you for cherry-picking the commit in #2993. Closing the PR.

-- 
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/3005#issuecomment-528170443

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 04 Sep 2019 19:35:43 -0700

Closed #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/3005#event-2609065464