Radio Gatún

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 some 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 Gatún 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 11 lines to the code:

#include <stdint.h> // Public domain random numbers
#define rg uint32_t // NO WARRANTY
#define rgp(a) for(c=0;c<a;c++)
#define rgn w[c*13]^=s;u[16+c]^=s;
void rgf(rg*a,rg*b){rg m=19,A[19],x,o=13,c,y,r=0;rgp(12)b[c+c%3*o]^=a
[c+1];rgp(m){r=(c+r)&31;y=c*7;x=a[y++%m];x^=a[y%m]|~a[(y+1)%m];A[c]=x
>>r|x<<(32-r);}for(y=39;y--;b[y+1]=b[y])a[y%m]=A[y%m]^A[(y+1)%m]^A[(y
+4)%m];*a^=1;rgp(3)a[c+o]^=b[c*o]=b[c*o+o];}void rgl(rg*u,rg*w,char*v
){rg s,q,c,x;rgp(40)w[c]=u[c%19]=0;for(;;rgf(u,w)){rgp(3){for(s=q=0;q
<4;){x=*v++;s|=(x?255&x:1)<<8*q++;if(!x){rgn;rgp(17)rgf(u,w);return;}
}rgn;}}}rg rgi(rg*m,rg*b,rg*a){if(*a&2)rgf(m,b);return m[*a^=3];}

Here is a version which I put on a coffee mug: tinyrg32.c.

# RadioGatun[32]("¡Es una niña!") = 89C92F4D5C20AF24F02EC270F8BECD06​5024ABBA1DFEF6C7F0B621D24D79D559

Note that the string “¡Es una niña!” is UTF-8 encoded Unicode. If the string were encoded in ISO 8859-1 format, its RG32 sum would be E6DE0CDA7B9AD7BBEC79533B82D221D2​BC48C4557B491E58DB2E9D388F9279FE

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

nanorg32.c is a tiny (607-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 nanorg32 nanorg32.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.

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