4 ms·

A kernel CSPRNG needs to: 1. Seed itself reliably. 2. Do nothing unless seeded. 3. Re-seed itself regularly, for forward secrecy. 4. Have good performance.

A kernel CSPRNG needs to: 1. Seed itself reliably. 2. Do nothing unless seeded. 3. Re-seed itself regularly, for forward secrecy. 4. Have good performance. How difficult is #1? It's as simple as gathering 128 bits of entropy. If you have 128 bits, you an expand them into an infinite sequence of random numbers, securely, forever. I think this is the essence of your comment. The topic is important, so it's worth being clear.

kang 11y ago
> If you have 128 bits, you an expand them into an infinite sequence of random numbers, securely, forever. How? And why 128 only?
- benkuykendall 11y ago
  A psuedorandom generator G(x) can expand n random bits to n+1 psuedorandom bits that still "look random" to any efficient program that sees them. The existence of such a G that is efficiently computable is hard to prove (at least as hard as P!=NP) but there are many reasonable functions we theorize to have this property. So with original entropy x, evaluate G(x) => x', c. Output the random bits c and repeat with x = x'. The sequence of c is psuedorandom. k=128 is the key length of the generator. We define an efficient program to be one that runs in some time polynomial in k. How big of a k you need is based on how powerful computers are at present.
- deleted 11y ago
  [deleted]
- jcranmer 11y ago
  Think of a CSPRNG as encrypting a simple incrementing counter with, say, AES using a random key (this is in fact one of the ways you can build a CSPRNG). A CSPRNG function that's not weak is basically equivalent in strength that has n bits of entropy is then basically equivalent to a cipher with that many bits of key. The acceptable safe maximum length isn't quite infinite, it's basically 2^64 rounds (not necessarily bits or bytes) for 128 bits of entropy. But that's basically arbitrarily long in practice as anyone cares.
- stingraycharles 11y ago
  The same way as any other cryptographic algorithm does that, e.g. RSA.
  - wolf550e 11y ago
    RSA is not used to encrypt large messages. Symmetric ciphers are used for this. With classic RSA, the secret key for the symmetric cipher is encrypted using RSA. Often (e.g. in the Signal protocol), a short secret key is extended using a HKDF (RFC 5869) to create enough bits for a symmetric key and an IV or a nonce (and a MAC key if needed). So for randomness, take 128 bits, use HKDF to extend to 192 bits, use 128 bits of output as AES-128 key, use next 64 bits of output as nonce, use 64 bits counter, produce AES-128(key, nonce||counter) for every value of counter until it overflows as randomness. 2^64 of 2^4 byte blocks is 2^68 bytes of randomness - enough for most purposes. An Intel chip will produce it at 1GB/sec per core.
- aortega 11y ago
  128 bits is widely considered a "big enough number" that a exhaustive search even on the fastest computers today will require an unthinkable amount of resources (time and power). It's the threshold for "secure" algorithms.
  - JdeBP 11y ago
    "unthinkable" is not really the right word. "impracticable", perhaps.
- oconnor663 11y ago
  One way to think about producing random bits is to just imagine encrypting a large file full of zeros. If you use a good cipher, the result should look totally random. (And if it's not totally random, you have a bad cipher.) So then the question becomes, what's the largest file you can encrypt with a single key? And the answer is any file you want. There's practically no size limit when you're encrypting files. 128 bits is usually the minimum recommended key size, not because of anything to do with the amount of randomness you can produce, but because you always have worry about an attacker guessing your key by brute force. Brute forcing a key is the same as just trying all possible keys to find one that works. (If there's another way to brute force the key, again you have a bad cipher.) We can estimate how big a key needs to be by looking at the fastest computers that exist: https://en.wikipedia.org/wiki/Supercomputer https://en.wikipedia.org/wiki/Supercomputer The fastest computer in the world does something like 2^55 operations per second. There are 2^25 seconds in a year, so if we generously assume that checking a key is just one operation, then a supercomputer like that could check about 2^80 keys per year. 128 is just the first nice power of 2 that's much larger than 80.
  - tptacek 11y ago
    There technically is a size limit --- and, for some constructions (like GCM), the size limit is potentially meaningful. But it's (a) enormous and (b) irrelevant, because the LRNG rekeys itself regularly. You can't extract random bytes from /dev/urandom fast enough to beat rekeying.
xorcist 11y ago
It used to be a real problem in virtual environments. That's why they all have special drivers for randomness now.
- Natanael_L 11y ago
  Yup, mass cloning a VM is really bad if you rely on stream ciphers for communication over the Internet and you do not instantly reseed. Suddenly you'll have tons of identical keystreams otherwise, making plaintext recovery trivial. Your VM host simply must instantly inject unique entropy into each VM guest instantly on creation, duplication and start. Otherwise you're breaking your own security.
  - xorcist 11y ago
    It also makes #2 above hard in practice. You simply don't know when to block. That's one of the reasons Linux developers are, shall we say, conservative with regards to the entropy pool. On a recent Linux environment those problems are solved however. Use proper random drivers for your virtualized environment and use getrandom() in your application.
  - infogulch 11y ago
    Could the host set a 'dirty entropy' flag whenever it creates/duplicates/starts a new VM? The VM could then watch for this flag and reseed when it notices.
    - Natanael_L 11y ago
      The solution in use now is that the guest OS asks the VM host for entropy using its VM guest specific kernel drivers, to seed the CSPRNG of the guest. If you have it do that on every guest RNG request you'll get the same desired effect without adding more communication. When you duplicate any VM guest, all sensitive key material should be replaced instantly (preferably never copied to begin with, the host should generate and inject fresh key material). Refilling the entropy pool alone isn't enough when reuse-insecure ciphers like stream ciphers are actively used, for the reasons stated above. Some ciphers are more tolerant of reuse (see AES-GCM vs AES-GCM-SIV).
merb 11y ago
The question is more how to make 'Have good performance' and 'good crypto'. It's mostly a tradeoff.
- Xylakant 11y ago
  "Good performance" needs to be on par or better with any userspace RNG. It's great if it's better but as long as there's an implementation that is on par with userspace there's no reason to write userspace RNGs at least from the performance perspective. Though there will still be people doing it for various reasons, one of them "because we can".

kang 11y ago

> If you have 128 bits, you an expand them into an infinite sequence of random numbers, securely, forever. How? And why 128 only?

benkuykendall 11y ago
A psuedorandom generator G(x) can expand n random bits to n+1 psuedorandom bits that still "look random" to any efficient program that sees them. The existence of such a G that is efficiently computable is hard to prove (at least as hard as P!=NP) but there are many reasonable functions we theorize to have this property. So with original entropy x, evaluate G(x) => x', c. Output the random bits c and repeat with x = x'. The sequence of c is psuedorandom. k=128 is the key length of the generator. We define an efficient program to be one that runs in some time polynomial in k. How big of a k you need is based on how powerful computers are at present.
deleted 11y ago
[deleted]
jcranmer 11y ago
Think of a CSPRNG as encrypting a simple incrementing counter with, say, AES using a random key (this is in fact one of the ways you can build a CSPRNG). A CSPRNG function that's not weak is basically equivalent in strength that has n bits of entropy is then basically equivalent to a cipher with that many bits of key. The acceptable safe maximum length isn't quite infinite, it's basically 2^64 rounds (not necessarily bits or bytes) for 128 bits of entropy. But that's basically arbitrarily long in practice as anyone cares.
stingraycharles 11y ago
The same way as any other cryptographic algorithm does that, e.g. RSA.
- wolf550e 11y ago
  RSA is not used to encrypt large messages. Symmetric ciphers are used for this. With classic RSA, the secret key for the symmetric cipher is encrypted using RSA. Often (e.g. in the Signal protocol), a short secret key is extended using a HKDF (RFC 5869) to create enough bits for a symmetric key and an IV or a nonce (and a MAC key if needed). So for randomness, take 128 bits, use HKDF to extend to 192 bits, use 128 bits of output as AES-128 key, use next 64 bits of output as nonce, use 64 bits counter, produce AES-128(key, nonce||counter) for every value of counter until it overflows as randomness. 2^64 of 2^4 byte blocks is 2^68 bytes of randomness - enough for most purposes. An Intel chip will produce it at 1GB/sec per core.
aortega 11y ago
128 bits is widely considered a "big enough number" that a exhaustive search even on the fastest computers today will require an unthinkable amount of resources (time and power). It's the threshold for "secure" algorithms.
- JdeBP 11y ago
  "unthinkable" is not really the right word. "impracticable", perhaps.
oconnor663 11y ago
One way to think about producing random bits is to just imagine encrypting a large file full of zeros. If you use a good cipher, the result should look totally random. (And if it's not totally random, you have a bad cipher.) So then the question becomes, what's the largest file you can encrypt with a single key? And the answer is any file you want. There's practically no size limit when you're encrypting files. 128 bits is usually the minimum recommended key size, not because of anything to do with the amount of randomness you can produce, but because you always have worry about an attacker guessing your key by brute force. Brute forcing a key is the same as just trying all possible keys to find one that works. (If there's another way to brute force the key, again you have a bad cipher.) We can estimate how big a key needs to be by looking at the fastest computers that exist: https://en.wikipedia.org/wiki/Supercomputer https://en.wikipedia.org/wiki/Supercomputer The fastest computer in the world does something like 2^55 operations per second. There are 2^25 seconds in a year, so if we generously assume that checking a key is just one operation, then a supercomputer like that could check about 2^80 keys per year. 128 is just the first nice power of 2 that's much larger than 80.
- tptacek 11y ago
  There technically is a size limit --- and, for some constructions (like GCM), the size limit is potentially meaningful. But it's (a) enormous and (b) irrelevant, because the LRNG rekeys itself regularly. You can't extract random bytes from /dev/urandom fast enough to beat rekeying.

xorcist 11y ago

It used to be a real problem in virtual environments. That's why they all have special drivers for randomness now.

Natanael_L 11y ago
Yup, mass cloning a VM is really bad if you rely on stream ciphers for communication over the Internet and you do not instantly reseed. Suddenly you'll have tons of identical keystreams otherwise, making plaintext recovery trivial. Your VM host simply must instantly inject unique entropy into each VM guest instantly on creation, duplication and start. Otherwise you're breaking your own security.
- xorcist 11y ago
  It also makes #2 above hard in practice. You simply don't know when to block. That's one of the reasons Linux developers are, shall we say, conservative with regards to the entropy pool. On a recent Linux environment those problems are solved however. Use proper random drivers for your virtualized environment and use getrandom() in your application.
- infogulch 11y ago
  Could the host set a 'dirty entropy' flag whenever it creates/duplicates/starts a new VM? The VM could then watch for this flag and reseed when it notices.
  - Natanael_L 11y ago
    The solution in use now is that the guest OS asks the VM host for entropy using its VM guest specific kernel drivers, to seed the CSPRNG of the guest. If you have it do that on every guest RNG request you'll get the same desired effect without adding more communication. When you duplicate any VM guest, all sensitive key material should be replaced instantly (preferably never copied to begin with, the host should generate and inject fresh key material). Refilling the entropy pool alone isn't enough when reuse-insecure ciphers like stream ciphers are actively used, for the reasons stated above. Some ciphers are more tolerant of reuse (see AES-GCM vs AES-GCM-SIV).

merb 11y ago

The question is more how to make 'Have good performance' and 'good crypto'. It's mostly a tradeoff.

Xylakant 11y ago
"Good performance" needs to be on par or better with any userspace RNG. It's great if it's better but as long as there's an implementation that is on par with userspace there's no reason to write userspace RNGs at least from the performance perspective. Though there will still be people doing it for various reasons, one of them "because we can".