RadioGatún

Last updated • 4 min readFrom Wikipedia, The Free Encyclopedia
RadioGatún
The RadioGatun' round function and input mapping.png
General
DesignersGuido Bertoni
Joan Daemen
Michaël Peeters
Gilles Van Assche
First publishedAugust 2006
Derived from Panama
Successors Keccak (SHA-3)
Cipher detail
Block sizes 19 words in mill; 39 words in belt
Best public cryptanalysis
Fuhr/Peyrin 2008, 211w (352/704 bits) complexity

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]

Contents

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 2022, RadioGatún is still a secure hash function; [2] [3] [4] [5] 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). [6]

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. [7]

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. [8] 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. [9]

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

The core belt function looks like this:

(A,B)=R(a,b)forrow=0to2doforallidoB[i,row]=b[i+1mod13,row]endforendfor{Beltfunction:simplerotation}fori=0to11doB[i+1,imod3]=B[i+1,imod3]⊕a[i+1]endfor{Milltobeltfeedforward}A=Mill(a){Millfunction}b=Bfori=0to2doA[i+13]=A[i+13]⊕b[12,i]endfor{Belttomillfeedforward}

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

{allindicesshouldbetakenmodulo19,x≫ydenotesbitwiserotation(rotatexrightybits)x⊕ydenotesexclusiveorx|~ydenotesperformingabitwiseorbetweenxandthebitwisenegationofy}forallidoA[i]=a[i]⊕(a[i+1]|~a[i+2])endfor{γ:non-linearity}forallidoa[i]=A[7i]≫i(i+1)/2endfor{π:intra-wordandinter-worddispersion}forallidoA[i]=a[i]⊕a[i+1]⊕a[i+4]endfor{θ: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. [11] Khovratovich also authored a paper, entitled "Cryptanalysis of hash functions with structures", which describes an attack with a complexity of 218w. [12]

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. [13] 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 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. [14] 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". [15]

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

Related Research Articles

<span class="mw-page-title-main">Advanced Encryption Standard</span> Standard for the encryption of electronic data

The Advanced Encryption Standard (AES), also known by its original name Rijndael, is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.

<span class="mw-page-title-main">HMAC</span> Computer communications authentication algorithm

In cryptography, an HMAC is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and authenticity of a message. An HMAC is a type of keyed hash function that can also be used in a key derivation scheme or a key stretching scheme.

The MD5 message-digest algorithm is a widely used hash function producing a 128-bit hash value. MD5 was designed by Ronald Rivest in 1991 to replace an earlier hash function MD4, and was specified in 1992 as RFC 1321.

In cryptography, SHA-1 is a hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecimal digits. It was designed by the United States National Security Agency, and is a U.S. Federal Information Processing Standard. The algorithm has been cryptographically broken but is still widely used.

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

In computer science and cryptography, Whirlpool is a cryptographic hash function. It was designed by Vincent Rijmen and Paulo S. L. M. Barreto, who first described it in 2000.

<span class="mw-page-title-main">MD4</span> Cryptographic hash function

The MD4 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1990. The digest length is 128 bits. The algorithm has influenced later designs, such as the MD5, SHA-1 and RIPEMD algorithms. The initialism "MD" stands for "Message Digest".

The Secure Hash Algorithms are a family of cryptographic hash functions published by the National Institute of Standards and Technology (NIST) as a U.S. Federal Information Processing Standard (FIPS), including:

SHA-2 is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression function itself built using the Davies–Meyer structure from a specialized block cipher.

Panama is a cryptographic primitive which can be used both as a hash function and a stream cipher, but its hash function mode of operation has been broken and is not suitable for cryptographic use. Based on StepRightUp, it was designed by Joan Daemen and Craig Clapp and presented in the paper Fast Hashing and Stream Encryption with PANAMA on the Fast Software Encryption (FSE) conference 1998. The cipher has influenced several other designs, for example MUGI and SHA-3.

<span class="mw-page-title-main">Skein (hash function)</span> Cryptographic hash function

Skein is a cryptographic hash function and one of five finalists in the NIST hash function competition. Entered as a candidate to become the SHA-3 standard, the successor of SHA-1 and SHA-2, it ultimately lost to NIST hash candidate Keccak.

SHA-3 is the latest member of the Secure Hash Algorithm family of standards, released by NIST on August 5, 2015. Although part of the same series of standards, SHA-3 is internally different from the MD5-like structure of SHA-1 and SHA-2.

The following tables compare general and technical information for a number of cryptographic hash functions. See the individual functions' articles for further information. This article is not all-inclusive or necessarily up-to-date. An overview of hash function security/cryptanalysis can be found at hash function security summary.

The following outline is provided as an overview of and topical guide to cryptography:

MurmurHash is a non-cryptographic hash function suitable for general hash-based lookup. It was created by Austin Appleby in 2008 and is currently hosted on GitHub along with its test suite named 'SMHasher'. It also exists in a number of variants, all of which have been released into the public domain. The name comes from two basic operations, multiply (MU) and rotate (R), used in its inner loop.

In cryptography, rotational cryptanalysis is a generic cryptanalytic attack against algorithms that rely on three operations: modular addition, rotation and XOR — ARX for short. Algorithms relying on these operations are popular because they are relatively cheap in both hardware and software and run in constant time, making them safe from timing attacks in common implementations.

This article summarizes publicly known attacks against cryptographic hash functions. Note that not all entries may be up to date. For a summary of other hash function parameters, see comparison of cryptographic hash functions.

<span class="mw-page-title-main">Sponge function</span> Theory of cryptography

In cryptography, a sponge function or sponge construction is any of a class of algorithms with finite internal state that take an input bit stream of any length and produce an output bit stream of any desired length. Sponge functions have both theoretical and practical uses. They can be used to model or implement many cryptographic primitives, including cryptographic hashes, message authentication codes, mask generation functions, stream ciphers, pseudo-random number generators, and authenticated encryption.

<span class="mw-page-title-main">Speck (cipher)</span> Family of block ciphers

Speck is a family of lightweight block ciphers publicly released by the National Security Agency (NSA) in June 2013. Speck has been optimized for performance in software implementations, while its sister algorithm, Simon, has been optimized for hardware implementations. Speck is an add–rotate–xor (ARX) cipher.

Dmitry Khovratovich is a Russian cryptographer, currently a Lead Cryptographer for the Dusk Network, researcher for the Ethereum Foundation, and member of the International Association for Cryptologic Research.

References

  1. ↑ Bertoni, Guido; Daemen, Joan; Peeters, Michaël; Van Assche, Gilles (2009). "The Road from Panama to Keccak via RadioGatún". Drops-Idn/V2/Document/10.4230/Dagsemproc.09031.17. Dagstuhl Seminar Proceedings (DagSemProc). 9031: 1–9. doi: 10.4230/DagSemProc.09031.17 . Retrieved 2009-10-20.
  2. ↑ Sadeghi-Nasab, Alireza; Rafe, Vahid (2022). "A comprehensive review of the security flaws of hashing algorithms" (PDF). Journal of Computer Virology and Hacking Techniques. 19 (2): 287–302. doi:10.1007/s11416-022-00447-w. S2CID   253033894. RadioGatún continues to be a safe hash function
  3. ↑ 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. S2CID   201884222. RadioGatún (Bertoni et al.2006) is still secure
  4. ↑ Thomas Pornin (2011-04-03). "Need suggestion for faster Linux fingerprint/hash comparison". Among those I cite, the Radiogatun and Shabal functions are currently unbroken.
  5. ↑ Zooko Wilcox (2017-02-24). "Lessons From The History Of Attacks On Secure Hash Functions" . Retrieved 2018-06-28. no new secure hash functions (designed after approximately the year 2000) have so far succumbed to collision attacks, either.
  6. ↑ "Archived copy" (PDF). Archived from the original (PDF) on 2017-01-31. Retrieved 2017-07-17.{{cite web}}: CS1 maint: archived copy as title (link)
  7. ↑ 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."
  8. ↑ http://radiogatun.noekeon.org/ "We now prefer to express the security claim for RadioGatún as a flat sponge claim with capacity 19w"
  9. ↑ "RadioGatún, a belt-and-mill hash function" (PDF). 2006-07-20.
  10. ↑ "The road from Panama to Keccak via RadioGatún" (PDF). S2CID   2222603. Archived from the original (PDF) on 2018-08-05. For Keccak, we have therefore decided to remove the belt and instead increase the number of words in the mill
  11. ↑ Khovratovich, Dmitry (2008). "Two Attacks on RadioGatún" (PDF). Progress in Cryptology - INDOCRYPT 2008. Lecture Notes in Computer Science. Vol. 5365. pp. 53–66. doi:10.1007/978-3-540-89754-5_5. ISBN   978-3-540-89753-8. S2CID   6487398. Archived from the original (PDF) on 2018-08-07.
  12. ↑ https://www.cryptolux.org/images/7/79/Struct.pdf Cryptanalysis of hash functions with structures - University of Luxembourg
  13. ↑ Bouillaguet, Charles; Fouque, Pierre-Alain (2009). "Analysis of the Collision Resistance of Radio Gatún Using Algebraic Techniques". Selected Areas in Cryptography. Lecture Notes in Computer Science. Vol. 5381. pp. 245–261. doi:10.1007/978-3-642-04159-4_16. ISBN   978-3-642-04158-7.
  14. ↑ Fuhr, Thomas; Peyrin, Thomas (2008). "Cryptanalysis of RadioGatun". Cryptology ePrint Archive.
  15. ↑ "Keccak and the SHA-3 Standardization" (PDF).
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.