As a teasing, Threefry is crush resistant, easy to implement, suitable for parallel applications and a working pure Python code is presented! I was motivated to understand this topic because the nano-dimer program by Peter Colberg uses it. Requirements for a Pseudorandom Number Generator (PRNG) include a good performance and a low memory usage (critical for GPUs). A good overview of these considerations is given in Salmon et al doi:10.1145/2063384.2063405.

Threefish¶

The Threefish block cipher is a part of the encryption candidate Skein. A block cipher is a reversible transformation of a sequence of bytes that depends on a user chosen key. Threefish (see the Wikipedia page and the official specification) is built of several simple components:

• a mix function that operates on words
• a permutation function $\pi$ that operates on several consecutive words
• a key schedule, that defines how the information in the key is applied within the algorithm

Here, a word is defined as a sequence of 64 bits. In practice, it is stored as an unsigned 64-bit integer. All sums are computed modulo $2^{64}-1$.

The full algorithm, going from a series of "plain text" words $p_i$ to the corresponding "cipher" $c_i$ consists in applying the following steps for $N_r$ rounds:

1. one round in four, add the key to the current value of the data
2. apply the mix function to two consecutive words at a time
3. permute the words according to $\pi$

After the last round, a final addition of the key is applied and the full data is XOR-ed with the initial value $p$. In Threefish, the key schedule is modified by a tweak, an extra set of two words. The specification provides:

• a set of rotation constants for the mix function
• the constant C240 that is part of the key schedule
• the permutation function $\pi$
• the number of rounds.

Threefish is specified for blocks of 256, 512 and 1024 bits. Below is a plain implementation of Threefish-256 that operates on 4 words blocks, in Python (the code is intended for Python 3). The test reproduces the content of the example found on the official NIST CD release of Skein. Intermediate steps are obtained by adding the argument "debug=True" and follow the step-by-step content of the file KAT_MCT/skein_golden_kat_internals.txt.

The code reproduces section 3.3 of the skein specification, with identical or close notation for all symbols, and is hopefully self-explaining.

Block ciphers, random numbers and Threefry¶

The motivation for this post (and the corresponding code) is to generate random numbers. The use of cryptographic protocols as keyed counter-based pseudorandom number generators is presented in Salmon et al "Parallel Random Numbers: As Easy as 1, 2, 3", doi:10.1145/2063384.2063405, Proceedings of SC'11. The use of the the Skein algorithm (based on Threefish) to generate random numbers is already mentioned in its specification, but the paper by Salmon et al goes further by specializing the algorithm (and others as well) for use in a PRNG context. I present here their specialization of Threefish: Threefry. Threefry is based on the Threefish block cipher, with three shortcuts. The number of rounds is reduced, the tweak that influence the key schedule is removed and the final XOR-ing of the output with the input data is removed. This latter shortcut is not explicit in the manuscript, as far as I understand. I concentrate here on Threefry-2x64, that is using two 64-bit words, with 20 rounds.

Whereas the prototypical PRNG steps from integer value to integer value using (more or less) complex iteration schemes, a counter based PRNG gives a random value directly for any point in the sequence at a fixed computational cost. The purpose of a cryptographic algorithm is to make it hard to guess the input from the output. Changing the input value from $i$ to $i+1$ will output an uncorrelated value.

The algorithm depends on a key of two words. One of them can be used as the seed and the other to identify one stream (i.e. a compute unit in a parallel computing environment). The position in the random stream is given as the "plain text" word.

Practically, it means that instead of keeping a state for the PRNG it is possible to request random_number(counter, key) where random_number is a pure function, counter is simply the iteration number that is requested and key is used to identify the stream (including a stream "id" and a seed).

The authors of the paper provide an implementation at http://www.thesalmons.org/john/random123/ or http://www.deshawresearch.com/resources_random123.html

As I wanted to understand the algorithm and have a working Threefish above, here is a Python version of Threefry-2x64.

Test output from the Random123 distribution, in the file Random123-1.08/examples/kat_vectors.

Using Threefry for random numbers¶

Below, illustrate the use of Threefry as one would use a typical PRNG. A seed is chosen, from which the key K is built. Then a loop uses the threefry function to generate two 64-bit words. The data is collected and show in a histogram and a next-point correlation plot. Also, the random numbers are used to estimate $\pi$ via the Monte Carlo method.

Final comments¶

By dissecting the algorithm and presenting a pure Python version, I hope I made it easier to understand Threefry for other who are not familiar with cryptography. The code presented here is purely illustrative in the sense that it presents no performance benefit and a C version will likely be added to my own random module. The stateless nature of Threefry makes it suited for OpenMP Shared-Memory Paralellism where one does not even need a thread-private state. Only the thread ID needs to be given to the PRNG. If a states ends up to be needed, only the sequence number needs to be tracked.