RadioGatún
Encyclopedia
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
.
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.
RadioGatún is actually a family of 64 different hash functions, distinguished by a single parameter, the word width in bit
s (w), adjustable between 1 and 64. The algorithm uses 58 words, each of size w, to store its internal state. Thus, for example, the 32-bit version of needs 232 bytes to store its state and the 64-bit version 464 bytes.
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
.
The same team that developed RadioGatún went on to make considerable revisions to this cryptographic primitive
, leading to the Keccak
SHA3 submission.
In light of the birthday attack
, this means that for a given word width w, RadioGatún is designed to have no attack with complexity greater than 29.5w. This corresponds to 2304 for the 32-bit version and 2608 for the 64-bit version.
present two attacks that do not break the designers' security claims, one with a complexity of 218w and another with a complexity of 223.1w. Khovratovich also authored a paper, entitled "Cryptanalysis of hash functions with structures", which describes an attack with a complexity of 218w.
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. 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. While more effective than the other attacks, this attack still does not break the security claim.
These test vectors only show the first 256 bits of the output of RadioGatún'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
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
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
created by Guido Bertoni, Joan Daemen
Joan Daemen
Joan Daemen |Limburg]], Belgium) is a Belgian cryptographer and one of the designers of Rijndael, the Advanced Encryption Standard , together with Vincent Rijmen. He has also designed or co-designed the MMB, Square, SHARK, NOEKEON, 3-Way, and BaseKing block ciphers...
, Michaël Peeters, and Gilles Van Assche. It was first publicly presented at the NIST Second Cryptographic Hash Workshop, held in Santa Barbara, California
Santa Barbara, California
Santa Barbara is the county seat of Santa Barbara County, California, United States. Situated on an east-west trending section of coastline, the longest such section on the West Coast of the United States, the city lies between the steeply-rising Santa Ynez Mountains and the Pacific Ocean...
, on August 24–25, 2006, as part of the NIST hash function competition
NIST hash function competition
The NIST hash function competition is an open competition held by the US National Institute of Standards and Technology for a new SHA-3 function to replace the older SHA-1 and SHA-2, which was formally announced in the Federal Register on November 2, 2007...
.
Although RadioGatún is a derivative of Panama, a stream cipher
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
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.
RadioGatún is actually a family of 64 different hash functions, distinguished by a single parameter, the word width in bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s (w), adjustable between 1 and 64. The algorithm uses 58 words, each of size w, to store its internal state. Thus, for example, the 32-bit version of needs 232 bytes to store its state and the 64-bit version 464 bytes.
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
Pseudorandomness
A pseudorandom process is a process that appears to be random but is not. Pseudorandom sequences typically exhibit statistical randomness while being generated by an entirely deterministic causal process...
.
The same team that developed RadioGatún went on to make considerable revisions to this cryptographic primitive
Cryptographic primitive
Cryptographic primitives are well-established, low-level cryptographic algorithms that are frequently used to build computer security systems. These routines include, but are not limited to, one-way hash functions and encryption functions.- Rationale :...
, leading to the Keccak
Keccak
Keccak is a cryptographic hash function designed by Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. Keccak is one of five finalists in the NIST hash function competition to select a SHA-3 algorithm. The authors claim 12.5 cycles per byte on an Intel Core 2 CPU...
SHA3 submission.
Claimed strength
The algorithm's designers claim that the first 19 × w bits (where w is the word width used) of RadioGatún's output is a cryptographically secure hash function. In other words, the first 608 bits of the 32-bit version and 1216 bits of the 64-bit version of RadioGatún can be used as a cryptographic hash value.In light of the birthday attack
Birthday attack
A birthday attack is a type of cryptographic attack that exploits the mathematics behind the birthday problem in probability theory. This attack can be used to abuse communication between two or more parties...
, this means that for a given word width w, RadioGatún is designed to have no attack with complexity greater than 29.5w. This corresponds to 2304 for the 32-bit version and 2608 for the 64-bit version.
Cryptanalysis
In the paper "Two attacks on RadioGatún", Dmitry Khovratovich and Alex BiryukovAlex Biryukov
Alex Biryukov is a cryptographer, currently an assistant professor at the University of Luxembourg. His notable work includes the design of the stream cipher LEX, as well as the cryptanalysis of numerous cryptographic primitives. In 1998, he developed impossible differential cryptanalysis together...
present two attacks that do not break the designers' security claims, one with a complexity of 218w and another with a complexity of 223.1w. Khovratovich also authored a paper, entitled "Cryptanalysis of hash functions with structures", which describes an attack with a complexity of 218w.
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. 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. While more effective than the other attacks, this attack still does not break the security claim.
Test vectors
The only RadioGatún variants with test vectors (published hash values for sample inputs so programmers can verify they are correctly implementing the algorithm) are the 32-bit and 64-bit versions.These test vectors only show the first 256 bits of the output of RadioGatún'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
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
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