# Cryptography/RadioGatún

This article describes a cryptographic algorithm named RadioGatún. To fully understand this article, the following concepts need to be understood by the reader:
* Binary numbers To maximize performance, RadioGatún works directly with binary numbers
* Hexadecimal numbers are used to illustrate some parts of the algorithm
* Bitwise logic operations RadioGatún uses bitwise negation, bitwise or, and bitwise exclusive or
* Bit rotation RadioGatún uses circular rotations
* Cryptographic hashes RadioGatún is a, as far as we know, secure cryptographic hash
* Pseudo-random number generator RadioGatún also functions as a secure random number generator
* The reader should be familiar with at least one programming language which can perform the bitwise operations RadioGatún performs.

## What is RadioGatún?

RadioGatún is the direct predecessor of Keccak, the SHA-3 hashing standard. It is one of the fastest hashes out there: The 64-bit version of RadioGatún is about as fast as Blake2b, and the 32-bit version is about as fast as Blake2s. While Blake2 was given variable-length output as an add-on, RadioGatún has intrinsic variable length support, acting both as a cryptographic hash and as a stream cipher.
RadioGatún is the oldest secure variable length hash out there; it has been around since 2006, and, as of 2020, there is no known attack which weakens its security claims. MD5 was broken within 12 years of its release; RadioGatún has been around longer and still appears secure.
The 32-bit version appears to offer 304 bits of security; the 64-bit version looks to have 608 bits of security. In other words, the 32-bit version is more than secure enough for 256 bit hashes, while the 64-bit version can make 512 bit hashes.

## Note on notation
### Arrays

The code below uses a number of arrays to alter the RadioGatún state. The arrays are zero-indexed; this means that the first element of an array has the index 0 instead of the index 1. Instead of representing an array of 3 words as i[1], i[2], and i[3] (one-indexed arrays), we represent them as i[0], i[1], and i[2].

### Hexadecimal numbers

Since RadioGatún directly manipulates binary numbers, we sometimes put numbers in Hexadecimal format. When this is done, we put an "0x" at the beginning of the number. Examples: 0x07 is 7; 0x10 is 16.

### Bytes and words

On this page, bytes are always eight bits in size. Words can be 32 bits or 64 bits, depending on the version of RadioGatún being used.

## Variable word length

RadioGatún is a cipher designed in the mid-first-2000s-decade, in an era when servers were running a mixture of 32-bit and 64-bit operating systems, most desktops were still running 32-bit systems, and well before any hand held phones were running 64-bit code. This in mind, the cipher has different modes to support both 32-bit and 64-bit operation. There are also tiny versions that make cryptoanalysis easier: People investigating RadioGatún's security can analyze the one-bit or two-bit versions (as of 2018, the largest RadioGatún variant that has been broken is the two-bit one).
While RadioGatún has 8-bit and 16-bit support, the eight-bit version is probably too small to be secure, and the 16-bit might be too small. That in mind, only the 32-bit and 64-bit variants of RadioGatún will be looked at.
RadioGatún uses 58 words (of either 32-bit or 64-bit length, depending on the RadioGatún variant we are looking at) to store its state. For the rest of this document, "word" is either a 32-bit or 64-bit number, depending on which RadioGatún variant is being used.

## State initialization

To initialize RadioGatún's state, all 58 words are reset to have the value 0.

## The belt and mill

RadioGatún stores its state in two pieces: 39 words are stored in the belt, which can be visualized as three rows of 13 words. The mill is 19 words wide. Some implementations of RadioGatún use an extra word to store the belt, which facilitates code size optimizations.

## The beltmill function

While the RadioGatún spec considers the "belt" and "mill" operations separate, they are both done at the same time, so, in this document, we will consider a combined beltmill operation. This is the core of the RadioGatún algorithm, and all parts of RadioGatún (the input map, the mixing of RadioGatún after the input ends, and the generation of pseudo-random output bits) use the same beltmill function.
The RadioGatún spec considers the mill three arrays of 13 elements each; we will, here, consider the mill a single 40-word array. In addition, the ordering of operations in this book are different than as described in the spec.
This operation acts like a blender, blending the bits of RadioGatún state in a manner which is both predictable and believed to be cryptographically secure.

### Belt to mill feedforward

In the belt to mill feedforward, we exclusive or 12 words in the mill with 12 words in to the belt, as follows:
* The first word (element 0 in programming languages with zero-indexed arrays) of the mill is exclusive ored with the second word (element 1) of the mill; the resulting word is stored as the element 0 in the belt
* Element 14 of the belt is exclusive ored with element 2 of the mill
* Element 28 of the belt is exclusive ored with element 3 of the mill
* Element 3 of the belt is exclusive ored with element 4 of the mill
* Element 17 of the belt is exclusive ored with element 5 of the mill
* Element 31 of the belt is exclusive ored with element 6 of the mill
* Element 6 of the belt is exclusive ored with element 7 of the mill
* Element 20 of the belt is exclusive ored with element 8 of the mill
* Element 34 of the belt is exclusive ored with element 9 of the mill
* Element 9 of the belt is exclusive ored with element 10 of the mill
* Element 23 of the belt is exclusive ored with element 11 of the mill
* Element 37 of the belt is exclusive ored with element 12 of the mill
This can be viewed as followed in pseudo-code:
Here, % is the modulo operation: The remainder after division (For example: 5 modulo 3 is 2; 11 modulo 4 is 3)
^ is the exclusive or operation
* is multiplication
+ is addition

### The main mill operation

In the main mill operation, we perform a number of operations on the words in the mill, putting the results in a temporary array "t" of 19 words.
We set the rotate constant, "r", to 0
We do the following 19 times, for values of "a" between 0 and 18 inclusive:
* We add "a" to "r"
* We modulo "r" by the word size for the RadioGatún variant in use (For RadioGatún[32], the 19 rotate values are [0, 1, 3, 6, 10, 15, 21, 28, 4, 13, 23, 2, 14, 27, 9, 24, 8, 25, 11]; for RadioGatún[64], [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 2, 14, 27, 41, 56, 8, 25, 43])
* We set an index, "i", to "a" multiplied by seven
* We module "i" by 19, the mill width (the 19 "i" values are [0, 7, 14, 2, 9, 16, 4, 11, 18, 6, 13, 1, 8, 15, 3, 10, 17, 5, 12])
* We set "k" to be the mill index "i"
* We set index "ia" to be one added to "i", modulo 19. "Modulo 19" here means that, if "i" has the value 18, instead of giving "ia" the value 19, we give it the value 0 instead.
* We set index "ib" to be two added to "i", modulo 19. "Modulo 19" here means that, if i + 2 is 19 or higher, we subtract 19 from "i": If "i" is 17, "ib" will be 0 (instead of 19); if "i" is 18, "ib" will be 1 (instead of 20).
* We copy the mill element "ib" in to "mb"
* We perform bitwise negation on "mb" (we make every 0 bit 1, and every 1 bit 0)
* We copy the mill element "ia" in to "ma"
* We perform a bitwise or on "ma" and "mb", putting the result in "mc"
* We exclusive or "mc" with the mill element "i", and put the result in the element of the temporary array "t" indexed by "a"
* We take the element in the temporary array "t" with index "a", and rotate it right by "r" bits
This might look like this is pseudo-code:
The operators are the same as above; in addition, ~ is bitwise negation
rotate_right is a circular rotate right. For example, for 32-bit RadioGatún, rotate_right might look like this is C:

### Updating the mill

Now that we have performed some operations on the elements in the mill and put them in a 19-word temporary array "t", we can now update the actual mill based on the values we have in "t".
For each value of "a" between 0 and 18 inclusive:
* "i1" will be "a" incremented by one (a + 1), modulo 19
* "i2" will be "a" incremented by four (a + 4), modulo 19
* Set the mill element "a" to the value of element "a" in the "t" array
* Exclusive or mill element "a" with the value of element "i1" in the "t" array
* Exclusive or mill element "a" with the value of element "i2" in the "t" array
In pseudo-code:

### Rotating the belt

We now rotate the belt. In the RadioGatún specification, this is described as taking each of the three rows of the belt, and moving the values one to the right. All of the words move right one, like a conveyor belt, except the word on the right is moved to the left. The belt has three rows of 13 elements each; we do this rotate separately on the three rows.
To make the code simpler and smaller, we can look at the belt as an array of 40 (not 39) elements, then move all of the elements over by one. After doing that, we then take three values and move then down the belt, to make the belt circular.
For "i" between 38 and 0 (inclusive; note that we're starting at 38 then going down to 0):
* Increment "i" by one and give it the value "i1" (so 38 becomes 39, 37 becomes 38, and so on)
* Assign the belt element with the index "i1" the value of the belt element with the index "i"
The reason why we go down from 38 to 0 instead of up from 0 to 39 is because, if we incremented instead of decremented "i", all of the elements in the mill would have the same value (mill element 0), destroying the mill.
Once we shift all of the elements in the mill up by one, we now move three of the elements down again.
For "i" between 0 and 2 (inclusive):
* "i0" is "i" multiplied by 13 (the belt width)
* "i1" is "i0" with 13 added to it
* Take the belt element "i0" and assign the value of the belt element "i1" to it
This second loop makes the belt three 13-element circular belts
The above two steps can be done with the following pseudo-code:
Note that speed optimized implementations of RadioGatún, such as the ones written by Thomas Pornin in sphlib, do not rotate the belt; instead they run 13 different versions of the beltmill function, changing which elements to interact with instead of moving 39 elements around.

### The iota step

The iota step simply takes the first word in the mill (element 0), and exclusive ors it by the number 1.
In pseudocode:
Note that, in Keccak, the iota step is significantly more complex.

### Belt to mill

To finish off the beltmill function, we exclusive or three words in the mill against three words in the belt, storing the result in the mill words:
* Mill element 13 (the 14th element in the mill) is exclusive ored against Belt element 0 (the first word in the lowest row of the mill), storing the result in mill element 13
* Mill element 14 (15th element in the mill) is exclusive ored against Belt element 13 (the first word in the middle row of the mill), storing the result in mill element 14
* Mill element 15 (16th element in the mill) is exclusive ored against Belt element 26 (the first word in the top row of the mill), storing the result in mill element 15
In pseudo-code:
Note that code sized optimized versions of RadioGatún will put this in a 3-step loop, since we can do both the second part of the belt rotation and the belt-to-mill operation in one small loop, but speed-optimized versions will unroll the loop (convert actions performed in a loop in to multiple actions performed outside of a loop, to save the CPU cycles needed to process the loop).

## Input mapping

The input mapping step is where we take a binary string of arbitrary octet length, and use it to establish RadioGatún's state.

### A simplified input map

We will first look at RadioGatún[32] (32-bit RadioGatún) in the case where the hash input is precisely 32 bits in length.
First we initialize RadioGatún: We set all words in the belt and mill to have a value of 0. After doing that, we do the following (all of these steps are actually exclusive ors, but since we are exclusive oring against the value 0, it is equivalent to setting them to the desired values):
* We set the first element of the belt (belt element 0) to have our 32-bit hash input.
* We set the 17th byte of the mill (mill element 16) to be the same 32-bit hash input.
* We have the 14th byte of the belt (belt element 13, or, if you will, the first word in the belt's second row) be a binary 1.
* We set the 18th byte of the mill (mill element 17) to also have the value 1.
Voila! We have now put a 32-bit hash input (or, if you will, "seed") in to RadioGatún.
Pseudocode:
Once we have put this 32-bit value in to the RadioGatún state (the belt and mill), we can now perform the "blank rounds" step.

### Blank rounds

After the input string is ended, RadioGatún runs 18 blank rounds: 18 iterations of the Beltmill function.
In pseudocode:
Once the blank rounds are performed, jump to the "Generating Output" section which follows.

### What about other hash sizes?

RadioGatún does not support only 32-bit inputs; it supports an input of any number of bytes, from 0 and up. We will now describe how to process inputs of other lengths.

### Little endian

RadioGatún assumes to run on a little-endian processor (or, should we say, the reference implementation used to generate the reference test vectors was run on a little-endian machine). This in mind, eight-bit bytes are converted in to 32-bit or 64-bit words (depending on whether we're using the 32-bit or 64-bit variant) with the first bytes made to be the least significant bits.
In other words, if RadioGatún is given the string '124', which consists of the bytes (in hexadecimal) 0x31, 0x32, and 0x34, this will be converted by RadioGatún[32] (the 32-bit version) in to 0x01343231, and in to 0x0000000001343231 with the 64-bit version of RadioGatún.
Here, the first byte given to RadioGatún is made in to the lowest (least significant) eight bytes of the word used by RadioGatún.
Speed optimized versions of RadioGatún which know they are being run on little endian machines can simply read the words from memory to prepare them to affect the state.

### Input padding

One may also observe that the byte 0x01 is placed after the end of the string above; this is a padding byte used to let RadioGatún know where the string has ended. This padding byte protects RadioGatún from some security attacks. So, if our string is the three byte string '124', or 0x31 0x32 0x34, this becomes 0x31 0x32 0x34 0x01, which is then converted in to a little endian number like 0x01343231. If a one-byte string with the value 0x01 is given to RadioGatún, this is converted in to 0x01 0x01 before the little endian conversion is done.
RadioGatún can read in any arbitrary binary string, including strings with 0x00 (NULL), 0x01, etc., as long as the string's length is a multiple of 8 (0 bits long, 8 bits long, 16 bits long, 24 bits long, etc.); the reason why RadioGatún does not support other input lengths is because its padding behavior is not fully defined, and there are no official test vectors which are not a multiple of eight bits long.

### Putting the input in to RadioGatún

Once the input string is converted in to little endian words, we take three words and exclusive or them against the RadioGatún state, as follows:
* We take these three words and give them the names "w1", "w2", and "w3". For example, if RadioGatún[32] was given the string '12345678901' as an input, "w1" will have the value 0x34333231, "w2" will be 0x38373635, and "w3" will be 0x01313039. Should the string be shorter, such as '1' (0x31), we will zero pad things: "w1" will be 0x00000131, and both "w2" and "w3" will simply be 0x00000000; if using RadioGatún[64] and just ASCII '1' as a string, "w1" will be 0x0000000000000131, and both "w2" and "w3" will be 0x0000000000000000.
* We exclusive or the first byte of the belt (belt element 0) against "w1", placing the result back in belt[0]
* We exclusive or the 17th byte of the mill (mill element 16) against "w1", placing the result back in mill[16]
* We exclusive or the 14th byte of the belt (belt element 13, or, if you will, the first byte in the belt's second row) against "w2", placing the result back in belt[13]
* We exclusive or the 18th byte of the mill (mill element 17) against "w2", placing the result back in mill[17]
* We exclusive or the 27th byte of the belt (belt element 26, or, if you will, the first byte in the belt's top row) against "w3", placing the result back in belt[26]
* We exclusive or the 19th byte of the mill (mill element 18) against "w3", placing the result back in mill[18]
* We now run the Beltmill function against RadioGatún's state
Should the string, including the final 0x01 padding byte, be used up, we move on to the next section. Otherwise, we move forward in the string either 12 or 24 bytes (depending on whether we are calculating RadioGatún[32] or RadioGatún[64]) and repeat the above steps.
In this pseudocode example, we read in the input byte-by-byte to make the code endian-neutral (it runs the same way on both big-endian and little-endian machines). RadioGatunWordSize indicates the word size for the variant of RadioGatún we are implementing, and can be 32 or 64; Beltmill is the beltmill function described previously:
getByteFromString is a function which gets a single octet (8-bit byte) from our input string. isEndOfString returns true if the last call to getByteFromString failed because we have reached the end of the input string.
Once this is done, perform the 18 blank rounds, as described above, then go to the "generating output" section which follows to generate RadioGatún's hash output.

### Security properties

Since RadioGatún was designed to be a secure hash function, it is not computationally feasible to find two different inputs that establish the same internal state. In addition, it should not be possible to distinguish RadioGatún's output from actual random bits—it will appear to be noise. It should also not be possible to predict what pseudo-random bits will come next when shown RadioGatún's output unless the input is known, even if the attacker knows they are looking at RadioGatún generated bits.

## Generating output

Once we have run the blank rounds, we can now outputs words in the mill of RadioGatun to generate as many cryptographically secure random numbers as desired.
The process is simple:
* We look at the second element in the mill (mill element number 1) to get the first 32 or 64 bits of random output, depending on whether we chose to implement RadioGatún[32] or RadioGatún[64]
* We look at the third element in the mill (mill element number 2) to get another 32/64 bits of output
* We run the Beltmill operation, as already described previously
* We repeat the above three steps to get as many output bits as desired
Here is some pseudocode showing this:
getWordFromRadioGatun gives us 32 bits if using the 32-bit version of RadioGatun, and 64 bits if using the 64-bit version.
Note that, for reference test vector compatibility, the numbers need to be endian swapped (or, equivalently, the mill needs to be seen as an array of bytes on a small-endian system).

## Example

In this example, we process the string '1234' with RadioGatún[32]. As per the reference specification:

### Initial belt and mill state after running input map

This in mind, after running and finishing the input map, the belt and mill is as follows:
In this chart, the left hand number is the array index for the element in question. Instead of treating the belt like a single array of 39 (or 40) words, we treat the belt like three rows of 13 words. If using code that treats the belt as a single array, belt row 1 consists of elements 0-12 in the belt, row 2 has elements 13-25, and row 3 has elements 26-38.

### First run of Beltmill

After we perform the belt rotation, the belt and mill look like this (observe how the elements moved from row 0 to row 1 in the belt):
The main mill operation sets the 19 elements in the temporary ("t") array as follows:
After we use those values to update the mill, the mill and belt will look like this:
The iota step only affects the first element of the mill (making it 0xfffffffe here):

### The second Beltmill call

And the above is how the state looks after running the Beltmill operation once. Here is how it looks after running Beltmill on it again:

### Beltmill after 18 calls

After running it 16 more times (for a total of 18 Beltmill calls), it looks like this:

### Generating output bits

At this point, we use mill index 1 (0x4fd2bd9e) to generate the first 32 bits of output:
Observe that there has been an endian swap: The first byte is now the fourth byte, the second byte is now the third byte, the third byte is now the second byte, and the last byte is now the first byte.
The next 32 bits of the hash come from mill index 2 (0x79939946):
Now that we have extracted the values of two elements on the mill to generate some random numbers, we run the Beltmill operation again. We will look at this in some more detail.

### Another detailed look at a Beltmill call

First, we run the belt-to-mill feed-forward, resulting in:
We next rotate the belt:
Here is how the temporary array "t" looks after we do the main mill operation:
Now we use those values to update the mill:
The iota step only affects word 0 of the mill:
The belt to mill operation affects elements 13 to 15 in the mill:
At this point, we take words 1 and 2 from the mill to generate 64 more bits of hash output:

### Running Beltmill again to generate more random bits

We then run Beltmill again, resulting in:
Giving us these 64 bits of hash output:
To generate the final 64 bits of the desired 256-bit hash, we run Beltmill one final time:
And finish off our hash as follows:
We can, if more pseudo-random numbers are desired, run Beltmill as many times as we want to generate more numbers.