Sam Trenholme's webpage
Support this website

Radio Gatún

Radio Gatún (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 256-bit hashes [1]. There are two principal variants of RadioGatun: A 32-bit version (256-bit hashes) and a 64-bit version (may be able to make 512-bit hashes). Most 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 some of these files is below:


librgolf.3
librgolf.c
librgolf.txt
linebreak.c
linebreak-wedge.c
nanorg32-2009.c
nanorg32.c
nanorg32-vertical.c
old-tiny
python-cryptoplus-20131019.tar.xz
ref-unix.tar.bz2
rg32
rg32-1.html
rg32-benchmark.tar.bz2
rg32-bin.c
rg32.class.php.txt
rg32.cpp
rg32.cs
rg32-dom.html
rg32-dom.html.txt
rg32hash-2017-06-11
rg32hash-2017-06-11.tar.xz
rg32hash.c
rg32hash.exe
rg32hash-linux-bin
rg32hash.tar.gz
rg32.html
rg32.py
RG32-testvectors
rg-benchmark.tar.bz2
rg.class.php.txt
rg_test_vector_maker.tar.xz
rotate.amount.sh
show.mill.c
small_du_for_windows.7z
sphlib-3.0.zip
tiny32api.c
tinyrg32.c
variants

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

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.


[1] RadioGatún'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 RadioGatún, 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 256-bit hash (2 ^ 256 collision, 2 ^ 304 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.