Radio Gatun

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:

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];}

Code Golfers who think they can make a smaller working implementations of RG32 as a library are welcome to submit their entries. Some rules:

• Your successful entry must be donated to the public domain and be made public.
• The first lines must have the "Public domain crypto-strong random number gen" and "NO WARRANTY" comments.
• It needs to be 700 bytes or shorter.
• All global defines, variables, and functions must start with "rg" and be three characters or longer.
• It must compile, run, and correctly generate all RG32 test vectors in an RHEL6 clone (gcc 4.4.6), both compiled as x86 and x86_64 code.
• Lines must be 72 columns or shorter
• The code must fit in 16 lines or fewer, including the comment.
• The library file must terminate with a newline
• It must compile with no warnings when compiled as gcc -Wall -Os -c -o librgolf.o librgolf.c
• The API must be compatible.
• The only prize is your entry posted here, with credit.

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.

If anyone knows of an attack against RG32 better than 2 ^ 352, please email me.