Wednesday, December 17, 2008

Why Deadwood will still use RadioGatun

I have spent the last day or so looking at all of the SHA-3 hash function candidates; my first step was to look at all of them and see which ones can also be used as stream functions. As I pointed out yesterday (go there for links to the hash primitives I will talk about), only four of the SHA-3 submissions can be used both as a hash and as a stream cipher.

One thing that is important for Deadwood is to use a cryptographic primitive that works well with 32-bit words. Deadwood's target is a 32-bit embedded platform, such as a router. Radio Gatun works nicely here because it has both a 32-bit and a 64-bit variant; Deadwood uses the 32-bit variant.

Of the four submissions I listed yesterday, the only one whose SHA-3 submission uses 32-bit words is LUX (for the 224-bit and 256-bit long hashes). The other three use 64-bit words in their SHA-3 submissions.

It would appear that there is already cryptanalysis of LUX when it uses 32-bit words that concludes that LUX does not work well as a stream cipher or as a PRNG. This, in spite of the fact LUX only came out two months ago.

While Skein has incredible 64-bit performance and respectable 32-bit performance, it uses 64-bit words and there isn't a variant that uses 32-bit words.

MeshHash is designed to use 64-bit words from start to finish. In addition, there is already some cryptanalysis which doesn't look good.

Keccak, developed by the same group who created Radio Gatun, can work with 32-bit words, and indeed, while not part of the SHA-3 submission, the authors specify two forms of Keccak that can be used on 32-bit systems, one optimized for speed and another optimized for security. The "fast" version appears to have a good deal less security than Radio Gatun appears to have.

While Keccak looks promising and perhaps Skein can work well on 32-bit systems, Radio Gatun has been out in the wild for two years with no cryptographic attacks against it yet. Radio Gatun is closely related to Panama, which has been around for over 10 years without any weaknesses found in its stream cipher operation (which is how I use Radio Gatun in Deadwood).

So, in conclusion, while Keccak and possibly Skein deserve further investigation at a later date, neither is as freely adaptable to 32-bit systems as Radio Gatun is. While both have not been attacked yet, they are very new primitives that I want to give more time to be analyzed before I feel comfortable using them in Deadwood.

The other two primitives have already been attacked. Consequently, I don't feel entirely comfortable using them in Deadwood.

So, in conclusion, Deadwood will continue to use Radio Gatun as the engine for generating secure pseudo-random numbers for the foreseeable future.