Post Reply 
 
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
My SipHash implementation
10-06-2013, 03:47 AM (This post was last modified: 10-06-2013 04:13 AM by samiam.)
Post: #1
My SipHash implementation

Original blog entry

In my last blog entry, I mentioned a fairly new cryptographic primitive called SipHash. Here, I will discuss my implementation of SipHash, and how SipHash fixes yet another security hole in unpatched DjbDNS 1.05.

My SipHash implementation

I now have a tarball with my implementation of SipHash. While there are many excellent public domain versions of SipHash already out there (including the reference code), this implementation uses the same data types Deadwood’s strings use (making it fairly easy to plug in to Deadwood), and is more extensible than other versions of SipHash. In particular, I have used the code to make a 32-bit SipHash variant (SipHash uses 64-bit words).

S32Hash

S32Hash is my own 32-bit variant of SipHash. It generates a 32-bit hash compression constant from a 64-bit key and a string of any length. While 64 bits is really not quite long enough to be secure — a 64-bit key was brute force solved in a little under five years using thousands of computers in 2002 — it should be secure in cases where an attacker does not have ready access to the compressed hash values (the normal case when using it to determine the hash buckets to use).

The initial XOR constants to apply to the key are the top 32 bits of the corresponding 64-bit constants:

Code:
32-bit   64-bit
736f6d65 736f6d6570736575
646f7261 646f72616e646f6d
6c796765 6c7967656e657261
74656462 7465646279746573

The rotation constants are simply the 64-bit rotation constants divided by two, and rounded up:

Code:
64-bit 32-bit
13     7
16     8
32     16
17     9
21     11
32     16

The first eight test vectors, where the key is 0x0001020304050607 and the text to hash is {0-length string, 0x00, 0x0001, 0x000102, 0x00010203, etc.}:

Code:
9dd5acc0
8e478ea4
dfc77dc1
a41e0118
918a67d2
f3ba2c74
2b1691d7
a7e80642

There is a tarball with reference code for this SipHash variant.

If I ever use this code in Deadwood, I will change the key setup to, instead of using a 64-bit key, initialize the four 32-bit values with random numbers generated by Deadwood’s cryptographic pseudo random number generator (PRNG). To minimize the chance of a weak key, I would make sure no single byte in the initial values has a value of 0.

The reason for this SipHash variant is because one of Deadwood’s design goals is to run best on a 32-bit system. For example, even though a 64-bit version of RadioGatún (Deadwood’s PRNG) exists, I use the 32-bit version.

Yet another DjbDNS security hole

Since DjbDNS was released before hash collision denial of service attacks were well known (I myself didn’t think of them until designing and implementing Deadwood in 2007), it has a hash collision security hole:

https://​00​f.​net/​2012/​06/​26/​dnscache-​poisoning-​and-​siphash/

There is a patch:

http://​download.​pureftpd.​org/​misc/​dnscache-​siphash.​patch

While DJB probably has too much pride to openly admit that he made a security mistake with his 1990s hash compression algorithm, he has made up for this security deficiency by kindly giving us SipHash.

I was aware that this part of djbdns’ code probably had a security issue back in August of 2010, but did not follow up on my investigation.

MaraDNS was secure first

Deadwood was secure against hash collision attacks back in 2007. This security was improved in 2010. Even then, MaraDNS 1 was legacy code, so I did not patch MaraDNS 1 until hash bucket collision attacks were more widely known in early 2012. All of this preceded the publication of SipHash in the summer of 2012, and the above djbdns security patch on July 27, 2012.

Adding SipHash to MaraDNS

As I mentioned before, while SipHash would improve Deadwood’s and MaraDNS’ authoritative security, since the hash compression values can not be readily seen by an attacker, the security improvement would be an academic one. I have to balance any security improvement against the potential for increased code size and slower code. And, more to the point, MaraDNS is finished. Since I never found a good revenue stream for MaraDNS (besides its value as “Resume-ware”), development is now firmly on the back burner.
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 


Forum Jump:


User(s) browsing this thread: 1 Guest(s)