3 ms·

You can easily predict the output of a system from its input, if said input can only take a few possible values, by simply trying all possible inputs until you

by cesarb 11y ago

You can easily predict the output of a system from its input, if said input can only take a few possible values, by simply trying all possible inputs until you find one which matches the output. The extra step of hashing the pool into a key to a keystream generator does not prevent that. If the key has only a few possible values, and you can observe enough of its output, you can brute force it. If, for instance, the pool has only 256 possible values (8 bits of entropy), perhaps because the system just booted and almost nothing has been added yet to the pool, there will be only 256 possible keys, and only 256 possible output streams. If you have enough of the output (on average around one byte), you can try the 256 possible pool states, and see which one would give you the same output you have. And since now you know both the pool and generator state, the system's entropy is now zero: it's completely predictable. The only way to prevent that is to never output anything, until the number of possible states is large enough (like 2^128 or more) that brute forcing is not viable. Which AFAIK is what the new getrandom() syscall does.

Freaky 11y ago
The complaint isn't about blocking before you've been seeded, it's blocking afterwards because you've generated some random numbers and feel like you've somehow "used up" your entropy pool in doing so.
wtbob 11y ago
> The only way to prevent that is to never output anything, until the number of possible states is large enough (like 2^128 or more) that brute forcing is not viable. Fortunately, it's easy to store a value which can take one of 2^128 possible states: it's 16 bytes. That's all. That's all you need. That's all you'll ever need. Take that one value; use it to key a keyed hash or an HMAC or a stream cypher or a block cypher. Encrypt the 16-byte value for 0, then 1, then 2 &c. You will get an effectively infinite sequence of random numbers. 'But wait!' you say, 'maybe I'm worried that I might expose some of that state!' Then just periodically rekey that keyed hash or HMAC or stream cypher or block cypher. There are a number of ways to do that: one possibility would be to hash the current key and the new entropy, but there are other, smarter ways to do it as well. That's it. That's all you need.

by cesarb 11y ago

Freaky 11y ago

The complaint isn't about blocking before you've been seeded, it's blocking afterwards because you've generated some random numbers and feel like you've somehow "used up" your entropy pool in doing so.

wtbob 11y ago

> The only way to prevent that is to never output anything, until the number of possible states is large enough (like 2^128 or more) that brute forcing is not viable. Fortunately, it's easy to store a value which can take one of 2^128 possible states: it's 16 bytes. That's all. That's all you need. That's all you'll ever need. Take that one value; use it to key a keyed hash or an HMAC or a stream cypher or a block cypher. Encrypt the 16-byte value for 0, then 1, then 2 &c. You will get an effectively infinite sequence of random numbers. 'But wait!' you say, 'maybe I'm worried that I might expose some of that state!' Then just periodically rekey that keyed hash or HMAC or stream cypher or block cypher. There are a number of ways to do that: one possibility would be to hash the current key and the new entropy, but there are other, smarter ways to do it as well. That's it. That's all you need.