Subject: [quicwg/base-drafts] Add a description of the FNV-1a algorithm (#480)

From: Martin Thomson <[email-masked]>
Date: Thu, 27 Apr 2017 21:46:03 -0700

I've added this in the TLS document, even though this would have been easier to
add to the transport document in some ways.  The current plan (if we ever clear
our backlog) is to move the details of the packet protection and key schedule
to the transport.  If that ever happens, it will be easy enough to move this
new text at the same time as the packet protection.

Two choices that I made here:

1. all packets are protected, including Public Reset - this means that the
packet construction code can have very simple logic for determining whether to
add an integrity check, namely is there an AEAD?; the cost being that public
reset is a little bigger

2. the integrity check mechanism can change in a new version - this avoids
expanding the list of things that we promise that won't change between
versions; the cost being one extra trivial check on receiving an unprotected
packet

Closes #167.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Add a description of the FNV-1a algorithm

-- File Changes --

    M draft-ietf-quic-tls.md (76)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/480.patch
https://github.com/quicwg/base-drafts/pull/480.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/480

---

From: janaiyengar <[email-masked]>
Date: Thu, 27 Apr 2017 22:17:57 -0700

janaiyengar commented on this pull request.

> +integrity check length needs to be subtracted from available space when padding
+the initial client packet.
+
+The sender then calculates the integrity check over the entire packet, starting
+from the type field.  The output of the hash is appended to the packet.
+
+A receiver that receives an unprotected packet first checks that the version is
+correct, then removes the trailing octets.  It calculates the integrity check
+over the remainder of the packet.  Unprotected packets that do not contain a
+valid integrity check MUST be discarded.
+
+An implementation could choose to treat the addition and removal of the
+integrity check as though it were an AEAD.
+
+
+## The 128-bit FNV-1a Algorithm {#fnv1a}

Remove this entirely, and leave a reference to the FNV IETF draft (https://datatracker.ietf.org/doc/html/draft-eastlake-fnv).

> +128-bit FNV-1a hash (see {{fnv1a}}).  The output of this hash is appended to the
+payload of the packet.
+
+The integrity check algorithm MAY change for other versions of the protocol.
+
+
+## Integrity Check Processing
+
+An endpoint sending a packet that has a long header and a type that does not
+indicate that the packet will be protected (that is, 0-RTT Encrypted (0x05),
+1-RTT Encrypted (key phase 0) (0x06), or 1-RTT Encrypted (key phase 1) (0x07))
+first constructs the packet that it sends without the integrity check.
+
+In constructing the packet, the endpoint has to consider the extra length that
+the integrity check will add relative to the path MTU.  In particular, the
+integrity check length needs to be subtracted from available space when padding

"when padding the initial client packet" --> "when generating unprotected client packets". 

> +
+In constructing the packet, the endpoint has to consider the extra length that
+the integrity check will add relative to the path MTU.  In particular, the
+integrity check length needs to be subtracted from available space when padding
+the initial client packet.
+
+The sender then calculates the integrity check over the entire packet, starting
+from the type field.  The output of the hash is appended to the packet.
+
+A receiver that receives an unprotected packet first checks that the version is
+correct, then removes the trailing octets.  It calculates the integrity check
+over the remainder of the packet.  Unprotected packets that do not contain a
+valid integrity check MUST be discarded.
+
+An implementation could choose to treat the addition and removal of the
+integrity check as though it were an AEAD.

Unnecessary -- remove this sentence

> +
+
+## Integrity Check Processing
+
+An endpoint sending a packet that has a long header and a type that does not
+indicate that the packet will be protected (that is, 0-RTT Encrypted (0x05),
+1-RTT Encrypted (key phase 0) (0x06), or 1-RTT Encrypted (key phase 1) (0x07))
+first constructs the packet that it sends without the integrity check.
+
+In constructing the packet, the endpoint has to consider the extra length that
+the integrity check will add relative to the path MTU.  In particular, the
+integrity check length needs to be subtracted from available space when padding
+the initial client packet.
+
+The sender then calculates the integrity check over the entire packet, starting
+from the type field.  The output of the hash is appended to the packet.

Google QUIC adds this hash right after the packet header. This is similar to how AEAD does it, where the hash appears just before the encrypted payload, and it is indeed how we generate these packets (null encrypter with an FNV hash.) Can you change this to have the hash after the packet header?

-- 
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/480#pullrequestreview-35276530

---

From: Martin Thomson <[email-masked]>
Date: Thu, 27 Apr 2017 22:19:55 -0700

martinthomson commented on this pull request.

+payload of the packet.
+

Nope, other client packets don't have strong requirements about length, but that one needs to be handled specially (the second flight of handshake packets doesn't have a size constraint).

-- 
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/480#discussion_r113853969

---

From: Martin Thomson <[email-masked]>
Date: Thu, 27 Apr 2017 22:20:35 -0700

+

I'd prefer to have it at the end.  Then it's not wedged in the middle so that you have to hash 17 octets, jump 16 and then hash the rest.

-- 
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/480#discussion_r113854013

---

From: Martin Thomson <[email-masked]>
Date: Thu, 27 Apr 2017 22:21:50 -0700

That draft has an uncertain future.  It's not even an IETF draft.  I don't want to hitch our wagon to something like that.

It's even more uncertain given that the market is now overwhelmingly using Murmur variants.

-- 
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/480#discussion_r113854084

---

From: Martin Thomson <[email-masked]>
Date: Thu, 27 Apr 2017 22:23:19 -0700

+

Note also that "AEAD" doesn't do it any particular way.  AES-GCM adds the authentication tag at the end.

-- 
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/480#discussion_r113854182

---

From: Martin Thomson <[email-masked]>
Date: Thu, 27 Apr 2017 23:43:47 -0700

@martinthomson pushed 1 commit.

b19829c  Remove advice

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/480/files/1e8d5dab076371e0e3672320f97494b824139b1a..b19829cff70c5ea38b9be97e9b2335a3676ca900

---

From: ekr <[email-masked]>
Date: Fri, 28 Apr 2017 00:40:11 -0700

ekr requested changes on this pull request.

+

I agree with MT here. While there's no rules about where authentication tags for AEAD, as a practical matte everyone thinks they go last for the reason MT indicates. Is there any technical reason it should go first?

trailing 16 octets.

+QUIC uses the 128-bit version of the alternative Fowler/Noll/Vo hash, or FNV-1a
+{{FNV}}.

(FNV-1a), not "or" because these are the same thing, not alternatives

> +for each input octet:
+    hash := hash XOR input octet
+    hash := hash * prime
+```
+
+That is, a 128-bit unsigned integer is initialized with an offset basis.  Then,
+for each octet of the input, the exclusive binary OR of the value is taken, then
+multiplied by a prime.  Any overflow from multiplication is discarded.
+
+The offset basis for the 128-bit FNV-1a is the decimal value
+144066263297769815596495629667062367629 (in hex,
+0x6c62272e07bb014262b821756295c58d).  The prime is 309485009821345068724781371
+(in hex, 0x1000000000000000000013b; or as an expression 2^88 + 2^8 + 0x3b).
+
+Once all octets have been processed in this fashion, the final integer value is
+encoded on 16 octets in network byte order.

encoded as.

-- 
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/480#pullrequestreview-35294312

---

From: ekr <[email-masked]>
Date: Fri, 28 Apr 2017 00:41:06 -0700

I agree we need to document this here. Having a core piece of QUIC farmed out to some individual draft is not good. If someone wants to resurrect draft-eastlake as a QUIC document, then that would be OK I guess.

-- 
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/480#issuecomment-297930656

---

From: janaiyengar <[email-masked]>
Date: Fri, 28 Apr 2017 12:26:48 -0700

+

My bad -- I had assumed that AEAD convention was to do it at the beginning, but I was wrong. Trailing hash SGTM.

-- 
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/480#discussion_r114003189

---

From: janaiyengar <[email-masked]>
Date: Fri, 28 Apr 2017 12:34:17 -0700

+payload of the packet.
+

I see what you were trying to describe. This process generally applies to *all* packets though, which an implementer needs to be careful about if the packet is to fit within the max packet size.

-- 
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/480#discussion_r114004426

---

From: janaiyengar <[email-masked]>
Date: Fri, 28 Apr 2017 12:35:52 -0700

Ok with documenting FNV here, but I'd prefer the draft as a reference instead of the website.

-- 
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/480#issuecomment-298087982

---

From: Martin Thomson <[email-masked]>
Date: Sun, 30 Apr 2017 19:02:06 -0700

+payload of the packet.
+

Good point.

-- 
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/480#discussion_r114091945

---

From: Martin Thomson <[email-masked]>
Date: Sun, 30 Apr 2017 19:22:51 -0700

d4622fd  Review comments

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

---

From: janaiyengar <[email-masked]>
Date: Sun, 30 Apr 2017 21:56:39 -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/480#pullrequestreview-35539551

---

From: janaiyengar <[email-masked]>
Date: Sun, 30 Apr 2017 22:00:33 -0700

Merged #480.

-- 
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/480#event-1063702438