Sam Trenholme's webpage

Radio Gatun

Radio Gatun (RG) is the direct predecessor of SHA-3 (Keccak) that the same team of world-renowned cryptographers developed. It is a secure pseudo-random number generator and probably a secure hash function for generating 512-bit hashes [1]. There are two principal variants of RadioGatun: A 32-bit version (512-bit hashes) and a 64-bit version (may be able to make 1024-bit hashes). All implementations here are of the 32-bit version of RG, which is herein called RG32 (its official name is RadioGatun[32]).

I took an interest in this algorithm when originally designing Deadwood back in 2007. It served my purposes: It is a tiny secure random number generator which effectively compresses the entropy from a variety of sources with different levels of entropy.

When I say tiny, I mean it: The stripped -Os library used in Deadwood is under 1.5k in size. Indeed, the overhead of a 32-bit Linux ELF binary is larger than the compiled RG32 code. Here are the files; a description of these files is below:


librgolf.3 Public domain
librgolf.c public domain
nano-rg32.c public domain
README
ref-unix.tar.bz2
rg32-1.html
rg32-bin.c public domain
rg32.cpp
rg32-dom.html
rg32-dom.html.txt
rg32hash.exe
rg32hash-linux-bin
rg32hash.tar.gz public domain
rg32.html
rg32.py
RG32-testvectors
small_du_for_windows.7z
python-cryptoplus-20131019.tar.xz (third party Python lib; includes RG32)
rg32-benchmark.tar.bz2
rg-benchmark.tar.bz2

These files are mainly various implementations of RadioGatun[32], including a couple of C-language implementations, two Javascript implementations (one that uses Document.write, the other that uses DOM to output the test vectors), as well as a C++ implementation.

These programs are all open-source; some are released to the public domain and others have a liberal 2-clause BSD license.

One program is called "rg32hash" and is used like the md5sum program. Unlike the md5sum program, this program automatically recursively enters directories. Give it the file name or directory name you wish to hash, and it will output on the standard output the 256-bit Radio Gatun 32-bit hash of all of the files you list. If you want to perform a recursive hash from the current working directory, simply type in something like rg32hash . > RG32SUMS

I have both a Windows 32-bit binary and *nix source code of this program available.

librgolf.c is a public domain tiny (obfuscated, "golf code") API for including a good PRNG in a C program and adding only 12 lines to the code:

#include <stdint.h> // Public domain crypto-strong random number gen
#define rgp uint32_t // NO WARRANTY
#define rgf(a) for(c=0;c<a;c++){
#define rgn w[c*13]^=s;u[16+c]^=s;
void rgk(rgp*a,rgp*b){rgp m=19,A[m],x,o=13,c,y,r,q[3];rgf(3)y=c*o;q[c
]=b[y+12];for(r=o;--r;)b[y+r]=b[y+r-1];b[y]=q[c];}rgf(12)b[c+1+c%3*o]
^=a[c+1];}rgf(m)r+=c;y=c*7%m;r&=31;x=a[y]^(a[(y+1)%m]|~a[(y+2)%m]);A[
c]=x>>r|x<<(32-r);}rgf(m)a[c]=A[c]^A[(c+1)%m]^A[(c+4)%m];}rgf(3)a[c+o
]^=q[c];}*a^=1;}void rgl(rgp*u,rgp*w,char*v){rgp s,q,c,x;rgf(39)w[c]=
u[c%19]=0;}for(;;rgk(u,w)){rgf(3)for(s=q=0;q<4;){x=*v++;s|=(x?x:1)<<8
*q++;if(!x){rgn;rgf(17)rgk(u,w);}return;}}rgn;}}}rgp rgi(rgp*m,rgp*b)
{static int a=2;a&2?rgk(m,b):0;return m[a^=3];}
While this library is quite compact, it compiles with no warnings (even when -Wall is enabled) in GCC 4.4.6. The librgolf.c program includes an example using this API, which is non-Golfed (standard indentation, variable names, etc.) and public domain. There is also a public domain *NIX man page for the API.

ref-unix.tar.bz2 is a *NIX version of the Radio Gatun reference code and test vectors.

nano-rg32.c is a tiny (784-byte) C implementation of RG32, compatible on both 32-bit an 64-bit architectures. To use, have the input to hash be the first argument to the program, like this example:

$ gcc -Os -o nano-rg32 nano-rg32.c
$ ./nano-rg32 'Hello, world!'
1fe7b9fe37c3e771fdf88711c159741cd05fbece8be598c33f5028e362d96ab1

rg32.cpp is a small C++ class that implements RadioGatun32

rg32-bin.c is a small C program that outputs a RadioGatun32 binary stream on standard output.

small_du_for_windows is a Windows program that, in addition to having a (large file size compatible) version of "du" (called "sd"), has a similar program that provides both the RG32 hash and the size of files and folders; I made this program to compensate for MSYS' lack of the "du" command.

rg32-benchmark and rg-benchmark are tools I made in November of 2013 to time how fast it is to calculate 20,000,000 16-bit numbers using both RadioGatún[32] and RadioGatún[64].

On 64-bit systems, not surprisingly, the 64-bit version of RadioGatún is about 45% faster. What did surprise me is that, on 32-bit systems, the 64-bit version is about 5% faster than the 32-bit version. While the 64-bit version needs more operations on a 32-bit CPU, these operations are done only half the time; one gets an overall performance boost.

One advantage the 32-bit version does have is that its code is about 33% smaller (600-700 bytes smaller) than the 64-bit code on 32-bit systems.

RadioGatún, unlike ARX (add-rotate-exclusive or) ciphers, only performs bitwise rotations, exclusive or, and bitwise or operations, so it does not have the performance penalty running the 64-bit version on a 32-bit system that ARX ciphers have.


[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 RadioGatun[32] (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, I also understand that its low algebraic degree puts "hairline cracks" in its design; its direct successor SHA-3 is 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.