5 ms·

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

by kang 10y ago

benkuykendall 10y 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 10y ago
[deleted]
jcranmer 10y 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 10y ago
The same way as any other cryptographic algorithm does that, e.g. RSA.
- wolf550e 10y 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 10y 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 10y ago
  "unthinkable" is not really the right word. "impracticable", perhaps.
oconnor663 10y 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 10y 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.

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

by kang 10y 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 10y 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 10y ago

[deleted]

jcranmer 10y 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 10y ago

The same way as any other cryptographic algorithm does that, e.g. RSA.

wolf550e 10y 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 10y 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 10y ago
"unthinkable" is not really the right word. "impracticable", perhaps.

oconnor663 10y 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 10y 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.