Subject: [TLS] FNV versus SHA-1 in cached info

From: Stefan Santesson <[email-masked]>
Date: Fri, 07 May 2010 13:14:04 +0200

At the recent IETF meeting in Anaheim, Eric announced that he was not all
that happy with the choice of FNV in the Cached info draft.

I have recently had an e-mail exchange with Eric on this matter where he
told med that he do not want to see FNV used over SHA-1 in a TLS protocol
and that he plans on sending a message on the subject to this list.

I would therefore like to kick off the discussion as I want us to conclude
this issue and publish the draft. There is no reason to drag this on
forever.

The reason I personally agreed to use FNV for this draft is not because it
is better than SHA-1, nor that it is easier to implement (provided you have
a crypto library with SHA-1 functionality). The rationales for me was to
avoid a politically charged situation where many automatically think you
need 1) a high level of security 2) algorithm agility and 3) negotiations to
ensure interoperability, as soon as a hash algorithm is used for anything.

It was evident from earlier discussions on the list that we could not get
out of this discussion and the unnecessary extra protocol complexity unless
we picked a non-cryptographic hash.

Eric told me that he do not like the uncertainly introduced by a new
algorithm.

I don¹t understand this argument in this case, when the selected algorithm
isn¹t required to provide security.
The only issues of relevance (that I can se) is:

1) Does FNV do the job to create reasonably unique identifiers of cached
objects?
2) Can FNV be implemented with reasonable expectation of interoperability?

The answer to both questions is YES.

The draft contains code samples and test vectors. We already have three test
implementations that has demonstrated interoperability by matching the test
vectors. Its fast and its extremely easy to implement.

I would not have any problem with using SHA-1 if it could be used with no
agility what so ever. But I seriously doubt that this will be accepted and
for that reason I would like to keep FNV.

Please provide your thoughts and comments so we can close this issue and
move on.

/Stefan

---

From: Stefan Santesson <[email-masked]>
Date: Fri, 07 May 2010 13:23:21 +0200

Sorry, just want to complement the list of important criteria I can see:

1) Does FNV do the job to create reasonably unique identifiers of cached
objects?
2) Can FNV be implemented with reasonable expectation of interoperability?
3) Is the algorithm free of any IPR and license requirements.

The answer to all three is YES.

/Stefan

On 10-05-07 1:14 PM, "Stefan Santesson" <[email-masked]> wrote:

> At the recent IETF meeting in Anaheim, Eric announced that he was not all that
> happy with the choice of FNV in the Cached info draft.
> 
> I have recently had an e-mail exchange with Eric on this matter where he told
> med that he do not want to see FNV used over SHA-1 in a TLS protocol and that
> he plans on sending a message on the subject to this list.
> 
> this issue and publish the draft. There is no reason to drag this on forever.
> 
> The reason I personally agreed to use FNV for this draft is not because it is
> better than SHA-1, nor that it is easier to implement (provided you have a
> crypto library with SHA-1 functionality). The rationales for me was to avoid a
> politically charged situation where many automatically think you need 1) a
> high level of security 2) algorithm agility and 3) negotiations to ensure
> interoperability, as soon as a hash algorithm is used for anything.
> 
> It was evident from earlier discussions on the list that we could not get out
> of this discussion and the unnecessary extra protocol complexity unless we
> picked a non-cryptographic hash.
> 
> agility what so ever. But I seriously doubt that this will be accepted and for
> that reason I would like to keep FNV.
> 
> Please provide your thoughts and comments so we can close this issue and move
> on.
> 
> /Stefan
> 
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 07 May 2010 13:24:18 +0200

> for that reason I would like to keep FNV.

I also prefer to use FNV here.

Organizations are performing review of how MD5 and eventually SHA-1 are
used in their code bases, and this is costly.  If we know when designing
a protocol that the normal cryptographic properties are not essential,
and that an algorithm like FNV will suffice, it saves everyone the costs
associated with that review.  This is only one argument for FNV, there
are others.

I wish we used something like FNV instead of SHA-1 in SASL GS2, the use
there also do not require cryptographic properties.

/Simon

---

From: "Kemp, David P." <[email-masked]>
Date: Fri, 7 May 2010 09:21:29 -0400

> Please provide your thoughts and comments so we can close this issue
and move on.
> Stefan

My thoughts exactly.  I originally believed that non-negotiable SHA-1
would be free of controversy, but since that has turned out not to be
the case, I favor keeping FNV. 

If Eric can get Russ to mandate that the TLS WG SHALL accept the use of
SHA-1 for a non-cryptographic purpose (truncated to 64 bits for emphasis
as well as for bandwidth, and not subject to agility requirements), that
would be a reasonable outcome.  But that's not the IETF way.

Using SHA-256 for this purpose is unreasonable, and I would not be in
favor of any outcome that would cause that to happen.

Dave

---

From: Adam Langley <[email-masked]>
Date: Fri, 7 May 2010 10:35:13 -0400

> The answer to all three is YES.

Given that FNV has already been written up in the draft, I support its
continued inclusion. Although I viewed the initial reason behind the
switch somewhat critically, on reflection I think its use makes clear
what properties we require of the hash.

AGL

---

From: Nicolas Williams <[email-masked]>
Date: Fri, 7 May 2010 11:26:21 -0500

> > for that reason I would like to keep FNV.

It's been accepted elsewhere.  If cryptographic properties are not
required then algorithm agility is also not required.

> I also prefer to use FNV here.

I am of two minds about this issue.

> used in their code bases, and this is costly.

This is true, however, you'd think that we should all also audit our
code bases and protocols (proprietary and otherwise) to ensure that we
do use strong cryptographic algorithms where we _need_ them, that we
have migration plans, and that we execute them.  Just removing uses of
MD5 and SHA-1 will not do.

I'm concerned that a blanket "must not use MD5 nor SHA-1" rule will be
counter-productive for _proprietary_ protocols: developers might resort
to home-grown non-cryptographic hashes where they need cryptographic
ones, just to avoid unwelcome auditor attention.  Clearly that won't
happen for Internet protocols -not much- but there's a bigger world out
there, and training management to just ban weak algorithms might well
have unintended and very negative consequences.

Thus I'm not too sympathetic to arguments that we should refrain from
using MD5/SHA-1 where cryptographic properties are not needed.  I'd
rather train auditors to analyze protocols correctly than to apply
reflexive dicta.

But I've also seen the pressure to avoid using MD5/SHA-1 altogether, and
understand that often it's just easier to give.

>                                                If we know when designing
> associated with that review.  [...]

Does it?  We still have to review whether cryptographic properties were
or were not necessary.

> there also do not require cryptographic properties.

Quick, we're still in AUTH48!  (Just kidding.)

Nico
--

---

From: "Blumenthal, Uri - 0668 - MITLL" <[email-masked]>
Date: Fri, 7 May 2010 13:10:40 -0400

For cryptographic purposes agility is critical, and it's obvious.

For non-cryptographic purposes - who cares. Let the implementers figure what
works best and "codify" it. If it's SHA - fine. If it's FNV - fine. If it's
MD4 - fine. No sense avoiding cryptographically broken algorithms for
non-cryptographic use.

-- 
Regards,
Uri         [email-masked]
<Disclaimer>

---

From: Nicolas Williams <[email-masked]>
Date: Fri, 7 May 2010 12:28:52 -0500

> MD4 - fine. No sense avoiding cryptographically broken algorithms for

I agree, but it's important to have a rationale for this position.  I
stated one.  Simon and others have stated rationales for the opposite
position (that we should not use MD5 nor SHA-1 even when cryptographic
properties are not required).

It'd be nice if we didn't have to revisit this every time someone needs
a non-cryptographic hash function in an Internet protocol.

Nico
--

---

From: "Blumenthal, Uri - 0668 - MITLL" <[email-masked]>
Date: Fri, 7 May 2010 14:50:37 -0400

Well, I have not seen a *convincing* rationale why cryptographically
unsuitable algorithms must not be used in non-cryptographic applications,
and I see no reason why formerly-cryptographic algorithms should be an
exception from the above.

-- 
Regards,
Uri

---

From: Stefan Santesson <[email-masked]>
Date: Fri, 07 May 2010 21:58:24 +0200

Let me remind that we started off with SHA-1 with no agility.

That kicked off a lot of debate whether agility was required and the general
opinion was that we needed agility, so agility was added.

That kicked off a long debate on what hash algorithm that should be
mandatory and what measures that should be in place to advertise supported
hash algorithms.

And this when discussion is held by prime experts.

I believe that we in this case have demonstrated our inability to agree on a
single cryptographic hash algorithm without agility, when no cryptographic
properties are required.

Except for that I think you are right. SHA-1 would work fine.

Is there anyone who has a compelling argument why FNV would be bad?

/Stefan

---

From: Nicolas Williams <[email-masked]>
Date: Fri, 7 May 2010 15:20:55 -0500

> opinion was that we needed agility, so agility was added.

Your use is not for cryptographic purposes, therefore you don't need
hash agility.

In GS2, for example, we use a hash function to derive SASL mechanism
names from GSS-API mechanism OIDs.  We don't care about collisions, and
there are no attacks on hash functions that result in attacks on GS2
from this use of hashing.  Hash agility in the GS2 case would be worse
than stupid: changing hash functions would break applications.

The answer to "where's the hash agility?" is "we don't need it because
we're not using SHA-1 for its cryptographic properties".

By accepting that "hash agility" goes with "cryptographic hash function"
even when you don't ndeed nor depend on its cryptographic properties
you've simply caused yourself to do a sizeable amount of pointless work
(FNV).  And not just you, but also implementors (yeah, if they use one
of the languages for which you include implementations then they can
cut-n-paste from your document, after getting approval from their
lawyers).  Why do this to yourself and to the rest of us when there's a
much better answer?

Nico
--

---

From: Michael D'Errico <[email-masked]>
Date: Fri, 07 May 2010 13:47:01 -0700

> Is there anyone who has a compelling argument why FNV would be bad?

I've been using the 32-bit version of FNV for hash tables for many
years, and it has served me well.  There are always collisions among
the keys, but overall the spread among buckets is decent.  I just ran
a quick test to see how often collisions happen and found that with
2^20 buckets, inserting 2^10 strings of length 128 bytes, randomly
generated (um, I mean pseudo-randomly generated :-), there was a
single collision in about 1/3 of the trials.

So, while I think FNV-64 is probably fine for this draft, perhaps
a study should be done to hash a bunch of server certificates
currently in use on major sites and check for collisions.  The same
could be done with a 64-bit truncated SHA-1.

If there are any collisions when using FNV-64, but not SHA-1/64, then
we might want to avoid FNV.

Mike

---

From: "Kemp, David P." <[email-masked]>
Date: Fri, 7 May 2010 16:51:02 -0400

> [Nico] By accepting that "hash agility" goes with
> "cryptographic hash function" even when you don't need
> nor depend on its cryptographic properties you've simply
> caused yourself to do a sizeable amount of pointless work (FNV).

What work is involved in bringing a 5 LOC algorithm like FNV into
greater visibility and use?  Hardly any -- certainly not a sizeable
amount, and certainly not pointless.  Having identified an optimal
solution (small, fast, sufficient), it would now be a step
backwards to switch to a sub-optimal solution (larger, slower,
more-than-sufficient).

> [Simon] If we know when designing a protocol that the normal
> cryptographic properties are not essential, and that an algorithm
> like FNV will suffice, it saves everyone the costs associated with
> that review.  This is only one argument for FNV, there are others.

Yes.

Dave

---

From: Nicolas Williams <[email-masked]>
Date: Fri, 7 May 2010 16:06:00 -0500

> backwards to switch to a sub-optimal solution (larger, slower,

Oh, I had no idea what FNV's origin was.  Now that I've read

    http://isthe.com/chongo/tech/comp/fnv/

I think the extra work argument is lame :)

It'd have been nice if the I-D had had an informative reference...

Nico
--

---

From: "Kemp, David P." <[email-masked]>
Date: Fri, 7 May 2010 17:17:55 -0400

Hmm, maybe my math is rusty, but with a 20 bit hash, wouldn't you expect
a birthday collision in about 1/2 of the trials of 2^10 inputs?  Does
FNV have some magical collision-aversion property :-) ?

-----Original Message-----
From: Michael D'Errico

Mike

---

From: Stefan Santesson <[email-masked]>
Date: Sat, 08 May 2010 00:07:11 +0200

Yes, that seems about correct.

You need to generate 1,1774 * 2^10  values to have 0.5 probability to find a
collision (in a 2^20 bucket).

/Stefan

---

From: Stefan Santesson <[email-masked]>
Date: Mon, 10 May 2010 14:27:32 +0200

Unfortunately even informational references need to be stable documents
(AFAIK).

/Stefan

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 10 May 2010 10:02:36 -0500

> Unfortunately even informational references need to be stable documents

Not true.

---

From: Paul Hoffman <[email-masked]>
Date: Mon, 10 May 2010 08:16:46 -0700

>> Unfortunately even informational references need to be stable documents

+1 to Nico. There are plenty (too many, IMO) informational references in RFCs that are to web sites that have already been 404'd.

--Paul Hoffman, Director
--VPN Consortium