# RadioGatún

__: Cryptographic hash primitive__

**Short description**Template:Infobox hash function

**RadioGatún** is a cryptographic hash primitive created by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. It was first publicly presented at the NIST Second Cryptographic Hash Workshop, held in Santa Barbara, California, on August 24–25, 2006, as part of the NIST hash function competition. The same team that developed RadioGatún went on to make considerable revisions to this cryptographic primitive, leading to the Keccak SHA-3 algorithm.^{[1]}

RadioGatún is a family of 64 different hash functions, distinguished by a single parameter, the word width in bits (*w*), adjustable between 1 and 64. The only word sizes with official test vectors are the 32-bit and 64-bit variants of RadioGatún. The algorithm uses 58 words, each using *w* bits, to store its internal state, so the 32-bit version needs 232 bytes to store its state (since each word needs 32 bits or four bytes, and 58 multiplied by four is 232) and the 64-bit version 464 bytes (each word using eight bytes).

Although RadioGatún is a derivative of Panama, a stream cipher and hash construction from the late 1990s whose hash construction has been broken, RadioGatún does not have Panama's weaknesses when used as a hash function. As of 2019, RadioGatún is still a secure hash function;^{[2]}^{[3]}^{[4]} the largest version of RadioGatún that is broken is the one with a word size of two bits. RadioGatún has a claimed security strength of 304 bits for the 32-bit version and 608 bits for the 64-bit version. The best known cryptanalysis has not broken this claim: It needs 352 bits of work for the 32-bit version and 704 bits of work for the 64-bit version.

RadioGatún can be used either as a hash function or a stream cipher; it can output an arbitrarily long stream of pseudo-random numbers; this kind of hash construction is now known as an "Extendable-Output Function" (XOF).^{[5]}

## Claimed strength

The algorithm's designers, in the original RadioGatún paper, claimed that the first 19 × *w* bits (where *w* is the word width used) of RadioGatún's output is a cryptographically secure hash function.^{[6]}

Since publishing the paper, the designers revised their security claim, and now claim that RadioGatún has the security of a cryptographic sponge function with a capacity of 19*w*.^{[7]} This means that the 32-bit version of RadioGatún can be used to make a hash with 304 bits of security (both from collision attacks and from Preimage attacks), and the 64-bit version offers 608 bits of security.

## Implementation details

The designers call RadioGatún an "ideal mangling function". RadioGatún uses a "belt" and "mill" to cryptographically process binary data, with the majority of mangling operations performed on the "mill" part of RadioGatún.^{[8]}

Keccak removed the belt, increased the size of the mill from 19 words to 25 words, and made the mill function somewhat more complicated.^{[9]}

The core belt function looks like this:

(A,B) = R(a,b) for row = 0 to 2 do for all i do B[i, row] = b[i + 1 mod 13, row] end for end for {Belt function: simple rotation} for i = 0 to 11 do B[i + 1, i mod 3] = B[i + 1, i mod 3] ⊕ a[i + 1] end for {Mill to belt feedforward} A = Mill(a) {Mill function} b = B for i = 0 to 2 do A[i + 13] = A[i + 13] ⊕ b[12, i] end for {Belt to mill feedforward}

And the mill function Mill(A) looks like this:

{all indices should be taken modulo 19, x ≫ y denotes bitwise rotation (rotate x right y bits) x ⊕ y denotes exclusive or x |~ y denotes performing a bitwise or between x and the bitwise negation of y} for all i do A[i] = a[i] ⊕ (a[i + 1]|~a[i + 2]) end for {γ: non-linearity} for all i do a[i] = A[7i] ≫ i(i + 1)/2 end for {π: intra-word and inter-word dispersion} for all i do A[i] = a[i] ⊕ a[i + 1] ⊕ a[i + 4] end for {θ: diffusion} A[0] = A[0] ⊕ 1 {ι: asymmetry}

The Wikibooks page on RadioGatún provides full implementation details.

## Cryptanalysis

In the paper "Two attacks on RadioGatún", Dmitry Khovratovich presents two attacks that do not break the designers' security claims, one with a complexity of 2^{18w} and another with a complexity of 2^{23.1w}.^{[10]} Khovratovich also authored a paper, entitled "Cryptanalysis of hash functions with structures", which describes an attack with a complexity of 2^{18w}.^{[11]}

In the paper "Analysis of the Collision Resistance of RadioGatún using Algebraic Techniques", Charles Bouillaguet and Pierre-Alain Fouque present a way of generating collisions with the 1-bit version of the algorithm using an attack that needs 2^{24.5} operations.^{[12]} The attack can not be extended to larger versions since "all the possible trails we knew for the 1-bit version turned out to be impossible to extend to n-bit versions." This attack is less effective than the other attacks and also does not break RadioGatún's security claim.

The most effective attack against the algorithm, one with a complexity of 2^{11w}, is given in the paper "Cryptanalysis of RadioGatun" by Thomas Fuhr and Thomas Peyrin. In the paper, they break the 2-bit (word size of two) version of RadioGatún.^{[13]} While more effective than the other attacks, this attack still does not break the security claim.

The developers of RadioGatún have stated that their "own experiments did not inspire confidence in RadioGatún".^{[14]}

## Test vectors

The only RadioGatún variants that the designers supplied test vectors (published hash values for sample inputs so programmers can verify they are correctly implementing the algorithm) for are the 32-bit and 64-bit versions.

### RadioGatún[32]

These test vectors, generated using the 32-bit version of RadioGatún, only show the first 256 bits of RadioGatún[32]'s arbitrarily long output stream:

RadioGatun[32]("") = F30028B54AFAB6B3E55355D277711109A19BEDA7091067E9A492FB5ED9F20117

```
RadioGatun[32]("The quick brown fox jumps over the lazy dog") =
191589005FEC1F2A248F96A16E9553BF38D0AEE1648FFA036655CE29C2E229AE
```

```
RadioGatun[32]("The quick brown fox jumps over the lazy cog") =
EBDC1C8DCD54DEB47EEEFC33CA0809AD23CD9FFC0B5254BE0FDABB713477F2BD
```

### RadioGatún[64]

Here are hashes for the 64-bit version:

RadioGatun[64]("") = 64A9A7FA139905B57BDAB35D33AA216370D5EAE13E77BFCDD85513408311A584

```
RadioGatun[64]("The quick brown fox jumps over the lazy dog") =
6219FB8DAD92EBE5B2F7D18318F8DA13CECBF13289D79F5ABF4D253C6904C807
```

```
RadioGatun[64]("The quick brown fox jumps over the lazy cog") =
C06265CAC961EA74912695EBF20F1C256A338BC0E980853A3EEF188D4B06FCE5
```

## References

- ↑ "The Road from Panama to Keccak via RadioGatún". http://drops.dagstuhl.de/opus/volltexte/2009/1958/.
- ↑ Kishore, Neha; Raina, Priya (2019). "Parallel cryptographic hashing: Developments in the last 25 years".
*Cryptologia***43**(6): 504–535. doi:10.1080/01611194.2019.1609130. "RadioGatún (Bertoni et al.2006) is still secure". - ↑ Thomas Pornin (2011-04-03). "Need suggestion for faster Linux fingerprint/hash comparison". https://stackoverflow.com/questions/5522135/need-suggestion-for-faster-linux-fingerprint-hash-comparison. "Among those I cite, the Radiogatun and Shabal functions are currently unbroken."
- ↑ Zooko Wilcox (2017-02-24). "Lessons From The History Of Attacks On Secure Hash Functions". https://z.cash/technology/history-of-hash-function-attacks.html. "no new secure hash functions (designed after approximately the year 2000) have so far succumbed to collision attacks, either."
- ↑ "Archived copy". http://csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/documents/perlner_XOFs.pdf.
- ↑ Page 9 (Section 6) of "RadioGatún, a belt-and-mill hash function" states that "RadioGatún
[l
*w*] offers a security level indicated by a capacity*c*= 19 * w. For the 64-bit version RadioGatún this is a capacity of 1216 bits, for the 32-bit version and 16-bit version this gives 608 and 304 bits respectively." - ↑ http://radiogatun.noekeon.org/ "We now prefer to express the security claim for RadioGatún as a flat sponge claim with capacity 19
*w*" - ↑ "RadioGatún, a belt-and-mill hash function". 2006-07-20. http://radiogatun.noekeon.org/RadioGatun.pdf.
- ↑ "The road from Panama to Keccak via RadioGatún". https://pdfs.semanticscholar.org/558b/881dc0b72a97346c265f6c28a5159994f9ce.pdf. "For Keccak, we have therefore decided to remove the belt and instead increase the number of words in the mill"
- ↑ Khovratovich, Dmitry. "Two attacks on RadioGatún". https://pdfs.semanticscholar.org/ab3c/47316b50b87c280da744a28ca15a6156ac0f.pdf.
- ↑ https://www.cryptolux.org/images/7/79/Struct.pdf Template:Bare URL PDF
- ↑ Bouillaguet, Charles; Fouque, Pierre-Alain. "Analysis of the Collision Resistance of RadioGatun using Algebraic Techniques". http://hal.archives-ouvertes.fr/inria-00417797/en/.
- ↑ Fuhr, Thomas; Peyrin, Thomas. "Cryptanalysis of RadioGatun". http://eprint.iacr.org/2008/515.
- ↑ "Keccak and the SHA-3 Standardization". http://csrc.nist.gov/groups/ST/hash/sha-3/documents/Keccak-slides-at-NIST.pdf.

## External links

- The RadioGatún Hash Function Family, RadioGatún's official web page, with the hash's official description, public domain reference code, and test vectors
- rg32hash, an independent public-domain implementation of the 32-bit version of RadioGatún

Original source: https://en.wikipedia.org/wiki/RadioGatún.
Read more |