4 ms·
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 2
by JoachimS 12y ago
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.
- pbsd 12y agoDo 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.
- lisper 12y agoI think you meant: it [SipHash] is NOT designed to be a PRF.
- pbsd 12y agoNo, 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.
- lisper 12y agoOK... 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?
- wbl 12y agoUnfortunately 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.
- lisper 12y agoAh, that makes sense. Thanks!
- pbsd 12y agoThe 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.
- v64 12y agoI believe the spirit of the original poster's message was that SipHash is not strong enough to be used for cryptographic purposes.
- tptacek 12y agoNo, 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.
- v64 12y agoMakes sense, thanks for the clarification.
- Andys 12y agoSlow? I thought md5 was faster than the SHA-* family
- WhitneyLand 12y agoYes, way faster. It would be great if it weren't for those pesky collisions.
- MagicWishMonkey 12y agoCollisions aren't a concern unless you're hashing trillions of records. It's not really a concern for the vast majority of software projects.
- vertex-four 12y agoCollisions 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.