Subject: Bike shed warning: integrity check for unprotected packets

From: Martin Thomson <[email-masked]>
Date: Wed, 1 Mar 2017 13:29:50 +1100

I would like to close https://github.com/quicwg/base-drafts/issues/167

However, I'd like to only close it once.  So I'd like to have a small
amount of discussion about the hash function we use.  Hopefully we
only have that discussion once also.

These are the choices I think are reasonable (drawing on the reams of
literature out there):

FNV-1a @128 bits [https://tools.ietf.org/html/draft-eastlake-fnv-03]
CRC32 [ITU-T Recommendation V.42]
Murmur3 [https://github.com/aappleby/smhasher/wiki/MurmurHash3]
GHASH [RFC 5116] or Poly1305 [RFC 7539] with a fixed key
AES-GCM or ChaCha20-Poly1305 with a fixed key

GQUIC currently uses a 128-bit variant of FNV-1a.  I'm guessing that
this was simply the best available at the time.

In all cases, the cost of these is essentially zero (it's possible
that a 128-bit version is slower, but I couldn't find any benchmarks
and it's probably still close to zero).  In my view, we should not
making this decision on performance grounds.

I have a preference for CRC32.  It's what SCTP uses (see RFC 3309).
It's smaller.  It's well documented and very widely implemented.  It's
got hardware support in both Intel and ARM chips, if you care about
saving cycles (pro tip: you should not).  It's not perfect for picking
a bucket in a hash table, though it's not bad for that purpose.
Rather, it is designed specifically for detecting errors in
transmission, i.e., exactly what we need.

In terms of size, I think that 32-bits is plenty.  We can't defend
against active modification, so this only exists to winnow out
Internet noise.  The combination of this AND the UDP checksum should
be plenty, even if the UDP checksum is basically ineffectual.

If speed is a determining factor, then Murmur is much faster.  Though
FNV-1a is *slightly* faster on some benchmarks I've seen (not all -
the one I ran was 15% slower than CRC), most of those concentrate on
the 32-bit variants so that they can do like-for-like comparisons.
The 128-bit variant probably requires uint128_t support for
performance and that's not widespread.

If we wanted to reuse code, we could use GHASH (which is part of
AES-GCM) or Poly1305 (part of ChaCha20-Poly1305).  Or we could encrypt
with a fixed key.  But I don't see the point in either of these which
are considerably more complicated.

Final question for those who made it this far: should we bind the hash
to the version?  We can claim that the hash is always the same for any
QUIC version, which would allow a receiver to validate the hash even
if it didn't support the selected version.  Or we could say that
version determines which hash is in use.

---

From: Jana Iyengar <[email-masked]>
Date: Tue, 28 Feb 2017 18:59:35 -0800

I do not have a strong opinion on this issue, but I'll note that there's
running code doing FNV-1a: it is what's used by Google QUIC and QuicGo
implementations. It was supposed to be in the original input spec to the
wg, but we forgot to mention it. This hash is only computed on cleartext
packets (handshake packets), so I don't think the compute difference
between the algorithms or hardware support matters. One correction and one
comment below:

> I have a preference for CRC32.  It's what SCTP uses (see RFC 3309).

Not that it matters, but SCTP uses CRC-32c. It's only slightly different
from CRC-32, but different enough that there's lesser hardware support for
CRC-32c.

> version determines which hash is in use.

It seems reasonable to make the hash version-dependent. If the version was
corrupted, a receiver might end up using the wrong hash algorithm, but the
chances of a collision there seem quite low.

My 2c: document FNV-1a, since that adds no work for existing QUIC
implementations, and make it version-dependent so the bikeshed is around
later.
- jana

---

From: Martin Thomson <[email-masked]>
Date: Wed, 1 Mar 2017 14:16:08 +1100

> implementations, and make it version-dependent so the bikeshed is around

The reason I opened this thread is to avoid a bikeshed buildup.  If
you want to argue for FNV-1a-128, then let's hear the argument.

(I agree with you about binding hash to version.  The faintest hint of
any dispute about suitability argues for that.)

---

From: "Lubashev, Igor" <[email-masked]>
Date: Wed, 1 Mar 2017 03:21:28 +0000

No strong options here, especially on the choice of the function. I have some preference for standardizing it across versions, so a server that got a packet with an unknown version can figure out whether it got a corrupt packet (that it should drop) or just an unsupported version (so it should continue with version negotiation).

- Igor

-----Original Message-----
From: Jana Iyengar [[email-masked]]
Received: Tuesday, 28 Feb 2017, 9:59PM
To: Martin Thomson [[email-masked]]
CC: IETF QUIC WG [[email-masked]]
Subject: Re: Bike shed warning: integrity check for unprotected packets

I do not have a strong opinion on this issue, but I'll note that there's running code doing FNV-1a: it is what's used by Google QUIC and QuicGo implementations. It was supposed to be in the original input spec to the wg, but we forgot to mention it. This hash is only computed on cleartext packets (handshake packets), so I don't think the compute difference between the algorithms or hardware support matters. One correction and one comment below:

On Tue, Feb 28, 2017 at 6:29 PM, Martin Thomson <[email-masked]<mailto:[email-masked]>> wrote:
I would like to close https://github.com/quicwg/base-drafts/issues/167<https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_quicwg_base-2Ddrafts_issues_167&d=DwMFaQ&c=96ZbZZcaMF4w0F4jpN6LZg&r=Djn3bQ5uNJDPM_2skfL3rW1tzcIxyjUZdn_m55KPmlo&m=Tvx2miJXvrX6fGLx1dhn_8d23j9Fm3DWgLwZHYoG-o8&s=PCodPZ_Bsu1BR51x1OfERiZwyqsdyR_c6bPlEisKNr8&e=>

FNV-1a @128 bits [https://tools.ietf.org/html/draft-eastlake-fnv-03<https://urldefense.proofpoint.com/v2/url?u=https-3A__tools.ietf.org_html_draft-2Deastlake-2Dfnv-2D03&d=DwMFaQ&c=96ZbZZcaMF4w0F4jpN6LZg&r=Djn3bQ5uNJDPM_2skfL3rW1tzcIxyjUZdn_m55KPmlo&m=Tvx2miJXvrX6fGLx1dhn_8d23j9Fm3DWgLwZHYoG-o8&s=2qBHNbPgVWhcdL5m3eqhXdq68ntYIwsfuc-Yy_Oz1sQ&e=>]
CRC32 [ITU-T Recommendation V.42]
Murmur3 [https://github.com/aappleby/smhasher/wiki/MurmurHash3<https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_aappleby_smhasher_wiki_MurmurHash3&d=DwMFaQ&c=96ZbZZcaMF4w0F4jpN6LZg&r=Djn3bQ5uNJDPM_2skfL3rW1tzcIxyjUZdn_m55KPmlo&m=Tvx2miJXvrX6fGLx1dhn_8d23j9Fm3DWgLwZHYoG-o8&s=JE2jHELKUS17jyFcsSudw0xgrRPSJZTxFg5yjI3bAcw&e=>]
GHASH [RFC 5116] or Poly1305 [RFC 7539] with a fixed key
AES-GCM or ChaCha20-Poly1305 with a fixed key

Not that it matters, but SCTP uses CRC-32c. It's only slightly different from CRC-32, but different enough that there's lesser hardware support for CRC-32c.

It seems reasonable to make the hash version-dependent. If the version was corrupted, a receiver might end up using the wrong hash algorithm, but the chances of a collision there seem quite low.

My 2c: document FNV-1a, since that adds no work for existing QUIC implementations, and make it version-dependent so the bikeshed is around later.
- jana

---

From: Victor Vasiliev <[email-masked]>
Date: Tue, 28 Feb 2017 23:55:16 -0500

I am not entirely clear -- are you suggesting to use CRC-32 (as defined in
V.42), or CRC-32Cc (as used in SCTP)?

My personal preference here lies with the algorithms which can be
implemented on a typical CPU without a lookup table -- that is to say, not
CRC or GHASH.  GHASH might be fine since it's MTI for TLS anyways.

---

From: Jana Iyengar <[email-masked]>
Date: Tue, 28 Feb 2017 21:26:37 -0800

> you want to argue for FNV-1a-128, then let's hear the argument.

Current QUIC implementations do FNV-1a-128. Admittedly not the strongest
argument, but I don't think I've heard a strong argument to change the
status quo either.

---

From: Jana Iyengar <[email-masked]>
Date: Tue, 28 Feb 2017 21:28:42 -0800

On Tue, Feb 28, 2017 at 7:21 PM, Lubashev, Igor <[email-masked]> wrote:

> No strong options here, especially on the choice of the function. I have
> some preference for standardizing it across versions, so a server that got
> a packet with an unknown version can figure out whether it got a corrupt
> packet (that it should drop) or just an unsupported version (so it should
> continue with version negotiation).
>

That's a good point... I hadn't thought about the responses being different
(drop vs. send version negotiation.) Perhaps that's a good reason to keep
this fixed across versions.

> *From:* Jana Iyengar [[email-masked]]
> *Received:* Tuesday, 28 Feb 2017, 9:59PM
> *To:* Martin Thomson [[email-masked]]
> *CC:* IETF QUIC WG [[email-masked]]
> *Subject:* Re: Bike shed warning: integrity check for unprotected packets
>
>> <https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_quicwg_base-2Ddrafts_issues_167&d=DwMFaQ&c=96ZbZZcaMF4w0F4jpN6LZg&r=Djn3bQ5uNJDPM_2skfL3rW1tzcIxyjUZdn_m55KPmlo&m=Tvx2miJXvrX6fGLx1dhn_8d23j9Fm3DWgLwZHYoG-o8&s=PCodPZ_Bsu1BR51x1OfERiZwyqsdyR_c6bPlEisKNr8&e=>
>>
>> FNV-1a @128 bits [https://tools.ietf.org/html/draft-eastlake-fnv-03
>> <https://urldefense.proofpoint.com/v2/url?u=https-3A__tools.ietf.org_html_draft-2Deastlake-2Dfnv-2D03&d=DwMFaQ&c=96ZbZZcaMF4w0F4jpN6LZg&r=Djn3bQ5uNJDPM_2skfL3rW1tzcIxyjUZdn_m55KPmlo&m=Tvx2miJXvrX6fGLx1dhn_8d23j9Fm3DWgLwZHYoG-o8&s=2qBHNbPgVWhcdL5m3eqhXdq68ntYIwsfuc-Yy_Oz1sQ&e=>
>> ]
>> Murmur3 [https://github.com/aappleby/smhasher/wiki/MurmurHash3
>> <https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_aappleby_smhasher_wiki_MurmurHash3&d=DwMFaQ&c=96ZbZZcaMF4w0F4jpN6LZg&r=Djn3bQ5uNJDPM_2skfL3rW1tzcIxyjUZdn_m55KPmlo&m=Tvx2miJXvrX6fGLx1dhn_8d23j9Fm3DWgLwZHYoG-o8&s=JE2jHELKUS17jyFcsSudw0xgrRPSJZTxFg5yjI3bAcw&e=>
>> ]

---

From: Martin J. Dürst <[email-masked]>
Date: Wed, 1 Mar 2017 14:44:52 +0900

> this fixed across versions.

Or, to be more precise, at least across the range of versions that we 
want version negotiation to happen. But that may be more precise than we 
need to care about now.

Regards,   Martin.

---

From: Martin Thomson <[email-masked]>
Date: Wed, 1 Mar 2017 16:57:53 +1100

> V.42), or CRC-32Cc (as used in SCTP)?

My mistake, I intended to state CRC32, the SCTP thing was in error
(it's a different polynomial and I failed to recognize that).

> CRC or GHASH.  GHASH might be fine since it's MTI for TLS anyways.

You don't think that support in recent processors for CRC32
instructions is enough to meet your requirement?