There’s a close correspondence between pseudorandom number generators and stream ciphers: a stream cipher is a PRNG that generates a keystream which is XORed with the plaintext/ciphertext to encrypt/decrypt it. A stream cipher is just a PRNG with hard mode turned up to 11.
A standard way to make a stream cipher is to encrypt a counter with a block cipher; this is called counter mode when it’s done with a general-purpose block cipher like AES, but it’s also how stream-specific ciphers like ChaCha20 work.
Cryptographically secure PRNGs emit the key stream from a stream cipher. (They also have machinery for secure rekeying.) For example arc4random was based on the RC4 stream cipher; the Linux kernel CSPRNG uses ChaCha20.
Philox is designed like a simplified stream cipher: its state is a counter which is passed through a few rounds of a keyed mixing function to produce its output.
PCG uses a linear congruential generator instead of a counter, ie, its state update is a multiply-add instead of an increment. PCG’s key is the LCG addend. PCG has much simpler output mixing functions, which use different bitfields from the state as the function’s input and key.
I think the variant of Philox that is closest to pcg32 is Philox4x32-7. If I understood the description correctly, the comparison is roughly,
pcg32 has a 2 word state and 2 word key
philox has a 4 word state and a 2 word key
pcg32 requires a 64 bit multiplication and a few shifts and xors
philox requires seven 64 bit multiplications and xors
pcg32 bandwidth was measured on a single core of a CPU that’s 12 years newer; compiled for AVX2 it was easily getting > 10 GB/s on a single core
philox bandwidth numbers are per-chip from a 4 core CPU, getting 5 GB/s total using all four cores
Thanks to the poster for making me aware of the paper, I was searching for some time for a good algorithm in this class.
The one aspect that I think is overlooked from the paper, is that it doesn’t just provide a good random number generator, but also a bijective random number generator even for small counters (i.e. 32 bits). Why does this matter? Because sometimes you want to “scramble” an input, but at the same time avoid collisions, i.e. sometimes one needs a permutation that also looks randomly (and you don’t want to generate one and cache it in memory).
As another poster said, it’s no secret that AES (the only widely accepted block cipher which isn’t yet broken) can act as a “permutation scrambler” (let’s call it like that) :), however it works only for 128 bit numbers. I only know of a single other alternative that provides a similar “permutation scrambler” for smaller numbers (say 32 bits), however it passes only the small test suite, and has a corner-case for the largest few inputs: https://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/ (and it’s implementation).
A PRNG with a 32 bit state can pass SmallCrush, but not Crush or BigCrush because its period is too small.
You can trade off the randomness of the generator against the randomness of the output permutation. At one extreme is the trivial generator, just a counter, and at the other extreme is the trivial output mixer, just the identity function.
A linear congruential generator can produce a permutation of 2^32 values, but the lower bits have small periods so it isn’t great by itself. You can add an output function that mixes the higher bits with the lower bits to improve the randomness, and so long as the function is invertible it will remain a permutation.
The difference from PCG is that PCG’s output permutations are non-invertible and halve the bit width from the state to the output. But they have some ideas worth reusing, for instance, shifting or rotating by amounts that vary depending on part of the state, so the small-period lower bits are mixed with varying selections of the upper bits.
I’m surprised this is a publishable result. Not only is counter mode well known to be a cryptographically secure prng itself, its parallelism has long been obvious. GCM mode is built on top of counter mode explicitly due to the parallelism. And several real systems divide up the counter-space per thread or per process.
I think this was the first work that tried applying counter-mode to non-cryptographic PRNGs and managed to get decent performance while passing the usual statistical tests. It was published in 2011 at a supercomputing conference which is a field that has longstanding difficulties getting enough random numbers fast enough – the paper’s introduction explains the unsatisfactory state of the art. Similarly, the seekability of LCGs was “just” an application of modexp repeated squaring, but it was publishable at a supercomputing conference in 1994 for roughly the same reasons (but was no longer relevant in 2011 because raw LCGs are crappy).
Counter mode is itself a cryptographic PRNG. If you’re talking about the security bounds when seeding without sufficient entropy, it is akin to talking about the bits of entropy in the key.
But it does make sense that most people in HPC wouldn’t have been deep in the crypto literature. At the time they would have been likely to know counter mode, but probably not as likely to know it was a cryptographic PRNG. So point taken.
Counter mode is a cryptographic PRNG if the mixing function is cryptographically strong. The point of this paper is to get good results fast by using a weak mixing function to make an insecure PRNG. (In supercomputing they use known seeds for reproducibility; I dunno how they choose seeds (I bet it’s just the time) but that’s not what the paper is about.)
Their starting point is a reduced-round version of AES (10 -> 5) with a simplified key schedule. AES-NI was new at the time so this was probably its first use in a fast insecure PRNG.
This was published in 2011, and the audience is the High-Performance Computing (HPC) community (not crypto people or PRNG experts). I don’t know what the PRNG field was like in 2011, and it might be that the paper mostly contains not-so-novel ideas but was accepted because those ideas were little-known in the HPC and benefited from more publicity.
GCM mode was 2005, and a NIST standard by 2007. The result about counter mode probably came in the paper that first formalized the notion of a pseudo-random-permutation, which I believe was Luby and Rackoff in ’88.
The drive for GCM was hardware manufacturers like Cisco and Intel that were concerned about supporting high performance computing.
But I get the point that the reviewers may not have had the background.
Interesting to compare to my recent work to parallelize pcg32
There’s a close correspondence between pseudorandom number generators and stream ciphers: a stream cipher is a PRNG that generates a keystream which is XORed with the plaintext/ciphertext to encrypt/decrypt it. A stream cipher is just a PRNG with hard mode turned up to 11.
A standard way to make a stream cipher is to encrypt a counter with a block cipher; this is called counter mode when it’s done with a general-purpose block cipher like AES, but it’s also how stream-specific ciphers like ChaCha20 work.
Cryptographically secure PRNGs emit the key stream from a stream cipher. (They also have machinery for secure rekeying.) For example arc4random was based on the RC4 stream cipher; the Linux kernel CSPRNG uses ChaCha20.
Philox is designed like a simplified stream cipher: its state is a counter which is passed through a few rounds of a keyed mixing function to produce its output.
PCG uses a linear congruential generator instead of a counter, ie, its state update is a multiply-add instead of an increment. PCG’s key is the LCG addend. PCG has much simpler output mixing functions, which use different bitfields from the state as the function’s input and key.
I think the variant of Philox that is closest to pcg32 is Philox4x32-7. If I understood the description correctly, the comparison is roughly,
pcg32 has a 2 word state and 2 word key
philox has a 4 word state and a 2 word key
pcg32 requires a 64 bit multiplication and a few shifts and xors
philox requires seven 64 bit multiplications and xors
pcg32 bandwidth was measured on a single core of a CPU that’s 12 years newer; compiled for AVX2 it was easily getting > 10 GB/s on a single core
philox bandwidth numbers are per-chip from a 4 core CPU, getting 5 GB/s total using all four cores
Thanks to the poster for making me aware of the paper, I was searching for some time for a good algorithm in this class.
The one aspect that I think is overlooked from the paper, is that it doesn’t just provide a good random number generator, but also a bijective random number generator even for small counters (i.e. 32 bits). Why does this matter? Because sometimes you want to “scramble” an input, but at the same time avoid collisions, i.e. sometimes one needs a permutation that also looks randomly (and you don’t want to generate one and cache it in memory).
As another poster said, it’s no secret that AES (the only widely accepted block cipher which isn’t yet broken) can act as a “permutation scrambler” (let’s call it like that) :), however it works only for 128 bit numbers. I only know of a single other alternative that provides a similar “permutation scrambler” for smaller numbers (say 32 bits), however it passes only the small test suite, and has a corner-case for the largest few inputs: https://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/ (and it’s implementation).
Does anyone know ofther good alternatives?
A PRNG with a 32 bit state can pass SmallCrush, but not Crush or BigCrush because its period is too small.
You can trade off the randomness of the generator against the randomness of the output permutation. At one extreme is the trivial generator, just a counter, and at the other extreme is the trivial output mixer, just the identity function.
A linear congruential generator can produce a permutation of 2^32 values, but the lower bits have small periods so it isn’t great by itself. You can add an output function that mixes the higher bits with the lower bits to improve the randomness, and so long as the function is invertible it will remain a permutation.
The difference from PCG is that PCG’s output permutations are non-invertible and halve the bit width from the state to the output. But they have some ideas worth reusing, for instance, shifting or rotating by amounts that vary depending on part of the state, so the small-period lower bits are mixed with varying selections of the upper bits.
I’m surprised this is a publishable result. Not only is counter mode well known to be a cryptographically secure prng itself, its parallelism has long been obvious. GCM mode is built on top of counter mode explicitly due to the parallelism. And several real systems divide up the counter-space per thread or per process.
I think this was the first work that tried applying counter-mode to non-cryptographic PRNGs and managed to get decent performance while passing the usual statistical tests. It was published in 2011 at a supercomputing conference which is a field that has longstanding difficulties getting enough random numbers fast enough – the paper’s introduction explains the unsatisfactory state of the art. Similarly, the seekability of LCGs was “just” an application of modexp repeated squaring, but it was publishable at a supercomputing conference in 1994 for roughly the same reasons (but was no longer relevant in 2011 because raw LCGs are crappy).
Counter mode is itself a cryptographic PRNG. If you’re talking about the security bounds when seeding without sufficient entropy, it is akin to talking about the bits of entropy in the key.
But it does make sense that most people in HPC wouldn’t have been deep in the crypto literature. At the time they would have been likely to know counter mode, but probably not as likely to know it was a cryptographic PRNG. So point taken.
Counter mode is a cryptographic PRNG if the mixing function is cryptographically strong. The point of this paper is to get good results fast by using a weak mixing function to make an insecure PRNG. (In supercomputing they use known seeds for reproducibility; I dunno how they choose seeds (I bet it’s just the time) but that’s not what the paper is about.)
Their starting point is a reduced-round version of AES (10 -> 5) with a simplified key schedule. AES-NI was new at the time so this was probably its first use in a fast insecure PRNG.
This was published in 2011, and the audience is the High-Performance Computing (HPC) community (not crypto people or PRNG experts). I don’t know what the PRNG field was like in 2011, and it might be that the paper mostly contains not-so-novel ideas but was accepted because those ideas were little-known in the HPC and benefited from more publicity.
GCM mode was 2005, and a NIST standard by 2007. The result about counter mode probably came in the paper that first formalized the notion of a pseudo-random-permutation, which I believe was Luby and Rackoff in ’88.
The drive for GCM was hardware manufacturers like Cisco and Intel that were concerned about supporting high performance computing.
But I get the point that the reviewers may not have had the background.