3 ms·

Dumb question: why would a RNG need a crypto hash function? I get why it would be useful for a PRNG, but isn’t a true RNG simply supposed to gather entropy from

by Ecco 5y ago

Dumb question: why would a RNG need a crypto hash function? I get why it would be useful for a PRNG, but isn’t a true RNG simply supposed to gather entropy from the real world and just spit it back?

Kubuxu 5y ago
It uses it to expose part of the randomness without exposing internal state and mixing in new random events into the randomness pool. In essence hash functions are frequently used as Pseudo Random Functions as hash functions are PRFs with input compression.
edflsafoiewq 5y ago
The universe does not provide bits of pure, sublimated entropy. There's a little entropy in the low bits of the interrupt timings, but you don't know exactly where it is. You need to "stir" it to get the entropy to affect the whole pool.
tptacek 5y ago
No. The high-level design of most CSPRNGs is roughly that of a stream cipher. With an ordinary stream cipher like AES-CTR, we need a 128 bit key; if we had a password or a DH shared secret, we'd get the 128 bit key from a KDF, whose core would be a hash function. With a CSPRNG, in lieu of a key we have an (often indeterminate) stream of unpredictable events --- but we still have the equivalent of a KDF, a "mixing function", whose core is typically a hash function. Adding new "entropy" means feeding it through the mixing function. Getting random bytes means running the stream cipher and spitting out the keystream directly, instead of XORing it against a plaintext. Cryptographically speaking, the problem of taking a small secret and extracting a very large number of cryptographically unpredictable bytes is pretty fundamental to the whole project --- you know, of, like, cryptography. But for the fact that you'd like to be able to theoretically recover from a bug that discloses your random state (your "key"), you wouldn't really need more than a "seed"'s worth of entropy to run the CSPRNG indefinitely.
- _vvhw 5y ago
  By the way, thanks Thomas... I've always enjoyed and benefitted from your "CSPRNGs are essentially a stream cipher, and now you finally also understand what a stream cipher really is" explanations on HN over the years. I remember the first time I grokked it from one of your comments, and it was much clearer than anything I could find on Cryptography Stack Exchange (yes, I know!). Since then, I've used the AES-CTR trick for non-critical random generators for many user space fuzz test harnesses, and it's helped speed them up while also being stronger than a PRNG, without a repeating period.
  - tptacek 5y ago
    I just shoplifted it from Bernstein.
oconnor663 5y ago
/dev/random hasn't been a "true" RNG in the sense you're describing (an "entropy estimating" RNG I think) since Linux 5.6. However, even an entropy estimating RNG doesn't want to give raw bytes from entropy sources straight to callers, for a few reasons: 1. There might be more than one source. In that case, it's natural to want the output to be secure as long as any of the inputs are secure. For that, you need some way to securely mix two sources of randomness together, and hash functions are good at that. 2. Truly random numbers coming from lava lamps or thermometers or whatever aren't necessarily uniformly random. They might be, say, 1/3 zeros and 2/3 ones. Who knows. That's still useful randomness, but callers want uniformly random bytes, so again we reach for some sort of pseudorandom mixer like a hash function. In this case I think this step is called "whitening".
- akerl_ 5y ago
  Even back when /dev/random estimated entropy, it was still a CSPRNG. At that time, /dev/random and /dev/urandom used the same cryptographic function to generate pseudo-random bits, random just added some additional fluff based on the claim that it was “estimating” randomness.

by Ecco 5y ago

Kubuxu 5y ago

It uses it to expose part of the randomness without exposing internal state and mixing in new random events into the randomness pool. In essence hash functions are frequently used as Pseudo Random Functions as hash functions are PRFs with input compression.

edflsafoiewq 5y ago

The universe does not provide bits of pure, sublimated entropy. There's a little entropy in the low bits of the interrupt timings, but you don't know exactly where it is. You need to "stir" it to get the entropy to affect the whole pool.

tptacek 5y ago

No. The high-level design of most CSPRNGs is roughly that of a stream cipher. With an ordinary stream cipher like AES-CTR, we need a 128 bit key; if we had a password or a DH shared secret, we'd get the 128 bit key from a KDF, whose core would be a hash function. With a CSPRNG, in lieu of a key we have an (often indeterminate) stream of unpredictable events --- but we still have the equivalent of a KDF, a "mixing function", whose core is typically a hash function. Adding new "entropy" means feeding it through the mixing function. Getting random bytes means running the stream cipher and spitting out the keystream directly, instead of XORing it against a plaintext. Cryptographically speaking, the problem of taking a small secret and extracting a very large number of cryptographically unpredictable bytes is pretty fundamental to the whole project --- you know, of, like, cryptography. But for the fact that you'd like to be able to theoretically recover from a bug that discloses your random state (your "key"), you wouldn't really need more than a "seed"'s worth of entropy to run the CSPRNG indefinitely.

_vvhw 5y ago
By the way, thanks Thomas... I've always enjoyed and benefitted from your "CSPRNGs are essentially a stream cipher, and now you finally also understand what a stream cipher really is" explanations on HN over the years. I remember the first time I grokked it from one of your comments, and it was much clearer than anything I could find on Cryptography Stack Exchange (yes, I know!). Since then, I've used the AES-CTR trick for non-critical random generators for many user space fuzz test harnesses, and it's helped speed them up while also being stronger than a PRNG, without a repeating period.
- tptacek 5y ago
  I just shoplifted it from Bernstein.

oconnor663 5y ago

/dev/random hasn't been a "true" RNG in the sense you're describing (an "entropy estimating" RNG I think) since Linux 5.6. However, even an entropy estimating RNG doesn't want to give raw bytes from entropy sources straight to callers, for a few reasons: 1. There might be more than one source. In that case, it's natural to want the output to be secure as long as any of the inputs are secure. For that, you need some way to securely mix two sources of randomness together, and hash functions are good at that. 2. Truly random numbers coming from lava lamps or thermometers or whatever aren't necessarily uniformly random. They might be, say, 1/3 zeros and 2/3 ones. Who knows. That's still useful randomness, but callers want uniformly random bytes, so again we reach for some sort of pseudorandom mixer like a hash function. In this case I think this step is called "whitening".

akerl_ 5y ago
Even back when /dev/random estimated entropy, it was still a CSPRNG. At that time, /dev/random and /dev/urandom used the same cryptographic function to generate pseudo-random bits, random just added some additional fluff based on the claim that it was “estimating” randomness.