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

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

On 10-05-07 11:17 PM, "Kemp, David P." <DPKemp@missi.ncsc.mil> wrote:

> 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
> 
>> 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
> 
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls