Hacker News Reader

Comment by JoachimS | Hacker News Reader

Good article that really shows why design decisions can have impact 20, 30 years or more.

This is why I get fairly upset when people design something new I n 2014 that uses md5. Yes even if your application does not use md5 for anything security related, the mere fact that you use a bad, slow algorithm should be considered wrong. And adding new dependencies will make it harder for us to migrate away and extend that tail even further.

If you need a good hash function that is fast, use SipHas. If you need a really secure one, use SHA-512, SHA-3, BLAKE or just SHA-256.

View on HN

Do NOT use SipHash as a cryptographic hash function. It is designed to be a PRF, and its output length is way too small to make it collision-resistant when used as a hash. SHA-3, SHA-512/256 or BLAKE(2) (in increasing order of performance) are suitable cryptographic hash functions.

I think you meant: it [SipHash] is NOT designed to be a PRF.

No, I meant what I wrote. SipHash is fine as a keyed primitive -- 128-bit security against key recovery, (64 - t)-bit security against 2^t forgery attempts.

However, as a hash function (e.g., with a fixed key), it is entirely too weak: 2^32 work for a collision, and 2^64 work for arbitrary (second-)preimages.

OK... so if it's suitable as a PRF, then you should be able to widen the output by using two different keys and concatenating the results, no?

Unfortunately not: it's only 64 times slower to generate 2^64 collisions for hash function by generic attacks than just one, and those 2^64 messages will contain a collision for another hash function of length 128. The total time is only the sum of the times for each one.

Ah, that makes sense. Thanks!

The attack you describe---Joux's multicollisions, as far as I can tell---applies to Merkle-Damgard functions. SipHash is a spongy, wide-pipe, design where that sort of thing doesn't work. The generic bound is (k!)^(1/k) ⋅ 2^(n(k-1)/k)) work to find a k-collision, or approximately k ⋅ 2^n for large k.

I believe the spirit of the original poster's message was that SipHash is not strong enough to be used for cryptographic purposes.

No, SipHash is acceptable cryptographic PRF; it's just not acceptable as a standalone general-purpose cryptographic hash.

A PRF is secure as long as attackers don't get to know exactly how it works, which, with SipHash, they don't if they don't know the key used for it.

A cryptographic hash function is secure --- it's Hard to find two inputs that produce the same output, it's (even) Hard(er) to find a specific input that generates a given output --- even when it's not keyed.

SipHash is a cryptographic building block that is performant in part because it takes advantage of relaxing the constraint of being a good cryptographic hash function, and only tries to be a good cryptographic PRF.

Makes sense, thanks for the clarification.

Slow? I thought md5 was faster than the SHA-* family

Yes, way faster. It would be great if it weren't for those pesky collisions.

Collisions aren't a concern unless you're hashing trillions of records. It's not really a concern for the vast majority of software projects.

Collisions are a concern if an attacker has any input into what you're hashing, and can therefore induce collisions. MD5 is broken in that there are real-world attacks by which an attacker can do so.

Reply on news.ycombinator.com