SipHash is a cryptographic primitive that solves the following problem:
- One needs to make a small random-looking number from a longer string.
- The random number needs to be generated very quickly
- The random number has to be difficult to guess unless you know the secret key
It is the first cryptographic primitive I know of fast enough to be used as a hashing compression function.
Without something like SipHash, the following attack is possible:
- An attacker comes up with a large number of different strings which make the same random number (“hash value”).
- The underlying data structures which allow one to quickly look up a piece of data assume that there will not be a lot of different strings with the same hash value.
- If that assumption is broken by an attacker, the code will run more slowly and use more resources.
- This is a type of denial of service attack.
==Protecting against this attack==
I was not aware of this attack when I wrote MaraDNS in 2001; I finally patched against this attack in late 2011 and early 2012 (resulting in three CVE reports: 2011-5055, 2011-5056, and 2012-0024).
When I started Deadwood in 2007, however, I was aware of the attack, so I always made Deadwood use a randomized hash compression function. In 2007, the hash used a secret number which only changed whenever Deadwood was compiled. This was an issue with precompiled binaries (such as the Windows binary); in 2010 I revised it to use a second secret number that changes every time Deadwood is started.
The algorithm is quick and simple, and assumes that, not only does the attacker not know one or both of the secret numbers Deadwood uses for its hash compression function, but also that the attacker does not know the compressed hash values.
SipHash takes it to the next level. Not only is SipHash secure against hash collision attacks when the attacker doesn’t know the compressed hash, SipHash is also secure against attacks where an attacker would know the compressed hash output. With SipHash, the only thing that should be kept secret is its 128-bit key.
SipHash has a 128-bit key and performs add, rotate, and exclusive or (XOR) operations on 64-bit words. Its output is a 64-bit number. It would be possible to come up with a 32-bit SipHash variant with a 64-bit key; only the rotation constants have to be changed. This would run more quickly on 32-bit computers but its security margin would be a little low.
While it would be best to use rotation constants carefully tuned to maximize diffusion, a 32-bit version of SipHash where the rotation constants are divided by two (rounded up) should be pretty good.
It might be possible to have v0, v1, v2, and v3 have separate values in SipHash; this would result in the 64-bit word size version of this SipHash variant having a 256-bit key; a 32-bit word size variant would have a 128-bit key. The security impact of using a larger key is unknown; provided the key is well-chosen, such as one randomly generated or generated by another secure pseudo random number generator (PRNG), I can not see how a larger key would worsen security.
Another way to add some more entropy to SipHash is to change the XOR constant added to v2 after the message to have a value besides 0xff. This would, coupled with the v2/v3 change in the previous paragraph, give 64-bit SipHash a 320 bit key and a 32-bit SipHash variant a 160 bit key. Again, this works best if all subkeys are generated by a good PRNG.
While SipHash would increase MaraDNS’ security from an academic standpoint, as a practical matter the hash compression used by MaraDNS and Deadwood should be secure since the attacker can not readily determine what compression values are generated.
If SipHash had existed when I was fully developing MaraDNS or Deadwood, I would have used it. Even though the project is finished, I may update Deadwood (and maybe even MaraDNS’ authoritative server) to optionally use SipHash (or a 32-bit variant as described above) instead of its own home-grown hash compression function.
To post a comment about this blog entry, go to the forum (self-signed https). New accounts may post once I approve the account.