Support this website or
listen to my music
Deadwood and SHA-3
November 2 2012
In today's blog, I discuss the possibility of updating Deadwood's underlying
cryptographic primitive, as well as post an updated election prediction.
What I chose
Back in 2007, when I began working on Deadwood, the only real
interesting algorithm for me was an oddball cryptographic primitive
called "Radio Gatun" (RadioGatun, which I also call RG32, to be exact).
This primitive not only generates a secure stream
of pseudo-random numbers, but also "compresses" entropy from a variety
of sources. All in under two kilobytes of code.
In 2007, RG32 was the best cryptographic primitive to use
for Deadwood's random number generator. But things started changing
My favorite SHA-3 candidate has always been Radio Gatun's direct
successor, Keccak. Back in 2008, I wrote that "Keccak looks promising":
By 2010, as I pointed out yesterday
, my praise for
Keccak became less guarded:
If I were to use one of the SHA-3 submissions for Deadwood’s
PRNG, I would use Keccak. Like Skein, it can output a stream of
infinite length from any input of any length. Unlike Skein, it
is more 32-bit compatible; not only is there a 32-bit “reduced
word length” variant officially blessed by the algorithm’s
creators, but also 64-bit Keccak more easily scales down to
32-bits than Skein, since the only operations done are permutes,
rotates, and exclusive ORs.
Now that Keccak has won and is now SHA-3, it's time to seriously consider
upgrading. The main advantage of Keccak over RG32 is that, now that
it is the new hashing standard, cryptographic researchers will concentrate
on finding weaknesses in it. In addition, it is more flexible in a lot of
ways than RG32--it is possible, for example, to simply increase
the rounds (or, likewise, increase its "capacity") should any weakness be
found in it.
Making the transition
Since I only actively develop MaraDNS and/or Deadwood one day each month,
it is going to take me a while to get around to updating Deadwood's
cryptographic primitive. Since RG32 is
ancestor to SHA-3, it should be a secure stream cipher (and probably a
secure hash [1
]) for the foreseeable future.
In addition to the time needed to implement SHA-3 as Deadwood's random
number generator, another factor is an ascetic one: Right now, Deadwood's
Windows binary is 65,024 bytes in size. I want to keep it under 65,536
bytes in size for as long as I can. Since Keccak is somewhat more
complicated than RG32, changing the cryptographic primitive will
probably finally make Deadwood over 65,536 bytes in size once and for
Like making sure Deadwood works in IPv6, this is a low-priority "wish list"
feature, but one I hope to have time to eventually implement.
Updated election prediction
With only four days to go until my birthday and the presidental election,
here is my updated prediction, again based on Nate Silver's model:
Obama gets OH
Romney gets OH
Obama gets FL
Romney gets FL
Obama gets VA
Romney gets VA
Romney gets FL and VA
Obama gets FL and/or VA
 RadioGatun's predecessor, Panama, has been around for over a decade
and, while broken as a hash function, is still a secure stream cipher.
While there have been some cryptographic analysis of RadioGatun, and
while one of RadioGatun's designer admits that "experiments did not
inspire confidence in RadioGatun", resulting in fairly significant tweaks
between RG32 and SHA-3, there is no attack, theoretical or
otherwise, against unmodified RG32 better than 2 ^ 352.
It is my personal opinion that RG32 will probably always be secure enough
to make a 512-bit hash (2 ^ 256 collision, 2 ^ 512 preimage), and will
almost certainly always be secure enough for a 256-bit hash (2 ^ 128
collision, 2 ^ 256 preimage). I also
understand that its low algebraic degree puts "hairline cracks" in its
design; its direct successor SHA-3 is probably better for new
deployments of a secure cryptographic hash and/or stream cipher.
If anyone knows of an attack against RG32 better than 2 ^ 352, please email me.
In order to reduce spam, comments for this entry are now closed
Previous entry -
Next entry -