Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

runtime: switch to a fast, collision-resistant hash function #4604

Closed
patrickmn opened this issue Jan 1, 2013 · 14 comments
Closed

runtime: switch to a fast, collision-resistant hash function #4604

patrickmn opened this issue Jan 1, 2013 · 14 comments

Comments

@patrickmn
Copy link

SipHash is a very fast PRG for short inputs developed by J. P. Aumasson and D. J.
Bernstein, competitive in speed with MurmurHash, but with the security benefits of
cryptographically strong hash functions, i.e. finding collisions is a major undertaking
even if the IV can be guessed, or if computing digests for the set of all IVs. Thus, it
can be an ideal choice for a hash table hash function, and provides significantly better
protection against collision attacks than a non-collision resistant hash function using
a random IV. It is also extremely simple. The entire implementation:
https://131002.net/siphash/siphash24.c

Most notably, Perl, the first by far to adopt any kind of hash function randomization
(in the early 90s, when the attack was first described) have switched to SipHash in
their 64-bit implementation.

iant suggested I file this ticket as I was commenting on the now-closed
https://golang.org/issue/2630. I plan to make a sample
implementation and provide benchmarks to back this up. I don't think this is terribly
urgent, but that it would be a better long-term solution. It might even be faster than
FNV in some cases where collisions were common since Sip has better distribution.
@patrickmn
Copy link
Author

Comment 1:

Erh, make that early 00's!

@rsc
Copy link
Contributor

rsc commented Jan 2, 2013

Comment 2:

Happy to leave this open for now but I don't think this is terribly important. Not for
Go 1.1.

Labels changed: added priority-someday, removed priority-triage, go1.1.

Status changed to LongTerm.

@patrickmn
Copy link
Author

Comment 3:

Agree

@patrickmn
Copy link
Author

Comment 4:

WIP CL by mdempsky: https://golang.org/cl/7029053/

@remyoudompheng
Copy link
Contributor

Comment 5:

Is this updated by https://golang.org/cl/7543043 ?

@mdempsky
Copy link
Member

Comment 6:

Probably, but I didn't see in 7543043 a description of what "aeshash" is.  Is there a
high level description of the new hashing algorithm?

@rsc
Copy link
Contributor

rsc commented Mar 19, 2013

Comment 7:

The new hash function is AES on chips that support it. It was faster than
all the other things we tried.

@rsc
Copy link
Contributor

rsc commented Mar 19, 2013

Comment 8:

This is fixed on new enough x86. It might be nice to do something for ARM. Will leave
open as a someday.

@mdempsky
Copy link
Member

Comment 9:

Right, I see that it uses AES-NI, but it doesn't appear to actually be AES (both because
AES is a block cipher not a hash function, and that using AES-NI to implement AES
requires more than just the AESENC instruction).  That's why I was asking if there's a
high-level description of the actual hash algorithm.
If not, I'll try to piece one together from reading the assembly code.

@gopherbot
Copy link

Comment 10 by keknehv:

f is a SubBytes/ShiftRows/MixColumns step.
s0, s1 are supposed to be random data... as is seed? || is concatenation
aeshash32/64: hash = s0 ^ f(s1 ^ f(s0 ^ f(data || seed)))
aeshash: 
acc = seed
for quadword in data:
   acc = quadword ^ f(s1 ^ f(acc))
if partial: # len(data) % 8 != 0
   acc = partialdata ^ f(s2 ^ f(acc))
hash = s0 ^ f(s1 ^ f(s0 ^ (acc))) 
Basically 3~5 rounds of AES with reused round keys.
I like mdempsky's SipHash-2-4 CL.

@rmmh
Copy link
Contributor

rmmh commented Apr 20, 2013

Comment 11:

f is a SubBytes/ShiftRows/MixColumns step.
s0, s1 are supposed to be random data... as is seed? || is concatenation
aeshash32/64: hash = s0 ^ f(s1 ^ f(s0 ^ f(data || seed)))
aeshash: 
acc = seed
for quadword in data:
   acc = quadword ^ f(s1 ^ f(acc))
if partial: # len(data) % 8 != 0
   acc = partialdata ^ f(s2 ^ f(acc))
hash = s0 ^ f(s1 ^ f(s0 ^ (acc))) 
Basically 3~5 rounds of AES with reused round keys.
I like mdempsky's SipHash-2-4 CL.

@rsc
Copy link
Contributor

rsc commented Dec 4, 2013

Comment 12:

Labels changed: added repo-main.

@rsc
Copy link
Contributor

rsc commented Mar 3, 2014

Comment 13:

Adding Release=None to all Priority=Someday bugs.

Labels changed: added release-none.

@rsc rsc added this to the Unplanned milestone Apr 10, 2015
@bradfitz
Copy link
Contributor

bradfitz commented Feb 2, 2017

Fixed by @khr in https://codereview.appspot.com/7543043

@bradfitz bradfitz closed this as completed Feb 2, 2017
@golang golang locked and limited conversation to collaborators Feb 2, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

7 participants