Support this website
In today's blog, I discuss the possibility of updating Deadwood's underlying
cryptographic primitive, as well as post an updated election prediction.
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[32], 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.
My favorite SHA-3 candidate has always been Radio Gatun's direct successor, Keccak. Back in 2008, I wrote that "Keccak looks promising":
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 the direct ancestor to SHA-3, it should be a secure stream cipher (and probably a secure hash [1]) for the foreseeable future.
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:
[1] 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.
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[32], 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 in 2008.
SHA-3
My favorite SHA-3 candidate has always been Radio Gatun's direct successor, Keccak. Back in 2008, I wrote that "Keccak looks promising":
http://samiam.org/blog/old-20081217-rg32.htmlBy 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 the direct 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 all.
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:
Overall Romney 3.72% Tie 0.27% Obama 96.01% Obama gets OH Romney 1.11% Tie 0.13% Obama 98.76% Romney gets OH Romney 14.28% Tie 0.86% Obama 84.86% Obama gets FL Romney 0.05% Tie 0.00% Obama 99.94% Romney gets FL Romney 6.67% Tie 0.49% Obama 92.84% Obama gets VA Romney 1.42% Tie 0.24% Obama 98.35% Romney gets VA Romney 8.21% Tie 0.34% Obama 91.45% Romney gets FL and VA Romney 14.75% Tie 0.62% Obama 84.63% Obama gets FL and/or VA Romney 1.18% Tie 0.19% Obama 98.63% Obama EVs 240-249 0.2% 250-259 0.9% 260-269 2.9% 270-279 7.6% 280-289 13.6% 290-299 19.8% 300-309 16.9% 310-319 15.8% 320-329 11.0% 330-339 8.4% 340-349 2.7% 350-359 0.1%
Footnote
[1] 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