RadioGatún

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.Page 9 (Section 6) of "RadioGatún, a belt-and-mill hash function" states that "RadioGatún [lw] 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."

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 19w. 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.

Keccak removed the belt, increased the size of the mill from 19 words to 25 words, and made the mill function somewhat more complicated.

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, and Module:RadioGatun32 is an implementation of the 32-bit version of RadioGatún.

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 218w and another with a complexity of 223.1w.{{cite book |chapter-url = https://pdfs.semanticscholar.org/ab3c/47316b50b87c280da744a28ca15a6156ac0f.pdf |archive-url = https://web.archive.org/web/20180807185914/https://pdfs.semanticscholar.org/ab3c/47316b50b87c280da744a28ca15a6156ac0f.pdf |url-status = dead |archive-date = 2018-08-07

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 224.5 operations.{{cite book | chapter-url=http://hal.archives-ouvertes.fr/inria-00417797/en/

The most effective attack against the algorithm, one with a complexity of 211w, 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.{{cite journal

The developers of RadioGatún have stated that their "own experiments did not inspire confidence in RadioGatún".{{cite web

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:

RadioGatún[64]

Here are hashes for the 64-bit version:

RadioGatun64 = 64A9A7FA139905B57BDAB35D33AA216370D5EAE13E77BFCDD85513408311A584

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

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

References

References

1. (2022). "A comprehensive review of the security flaws of hashing algorithms". Journal of Computer Virology and Hacking Techniques.
2. (2019). "Parallel cryptographic hashing: Developments in the last 25 years". Cryptologia.
3. Thomas Pornin. (2011-04-03). "Need suggestion for faster Linux fingerprint/hash comparison".
4. Zooko Wilcox. (2017-02-24). "Lessons From The History Of Attacks On Secure Hash Functions".
5. "Archived copy".
6. http://radiogatun.noekeon.org/ "We now prefer to express the security claim for RadioGatún as a flat sponge claim with capacity 19''w''"
7. (2006-07-20). "RadioGatún, a belt-and-mill hash function".
8. "The road from Panama to Keccak via RadioGatún".
9. https://www.cryptolux.org/images/7/79/Struct.pdf Cryptanalysis of hash functions with structures - University of Luxembourg