Thursday, March 19, 2009

Radio Gatun cryptanalysis (NOT broken) ; Deadwood minor update

Over two years have passed since RadioGatún was published; there finally has been some cryptanalysis of RadioGatún. In the first attack (PDF file), Dmitry Khovratovich and Alex Biryukov were able to attack RadioGatún with a complexity of 2^576 for the 32-bit version of RadioGatún. This attack is clearly not practical, and is only slightly less complex than the claimed security for RadioGatún32, 2^608.

Thomas Fuhr and Thomas Peyrin have a more successful attack; they claim to be able to break RG32 with a complexity of 2^352 (and actually break the 2-bit version of Radio Gatún in their paper). Again, the attack is not practical, but is significantly less complex that RG32's security claim of 2^608. Even if this attack can be extended to the 32-bit version of RadioGatún, RG32 can still be used to make secure 512-bit hashes (a birthday attack on a 512-bit hash has a complexity of 2^256). I personally use it for 256-bit hashes and feel that there will not be any cryptanalysis that makes a collision attack for RG32 easier than 2^128 (and probably no attack easier than 2^256).

There has been no cryptanalysis against using RG32 as a stream cipher (like I do in Deadwood), and RadioGatún's close relative, Panama, has been around since the late 1990s and never has been broken when used as a stream cipher.
I am working on making Deadwood a bona fide Windows service. The first step of this work, porting MicroDNS to Windows (so I have a very simple server to make a service out of), has been done and can be downloaded as microdns-simple.c. Compile this program as gcc -DMINGW -o microdns-simple microdns-simple.c -lwsock32 on a Windows system with MinGW.