A system call for random numbers: getrandom()

Posted Jul 27, 2014 4:02 UTC (Sun) by dlang (guest, #313)
In reply to: A system call for random numbers: getrandom() by nybble41
Parent article: A system call for random numbers: getrandom()

I think your assumptions are incorrect

As I understand it (vastly simplified and numbers small for examples sake)

you take 32 bits of random data, it gets mixed and seeds the PRNG, but the PRNG has it's state pool.

This state pool starts off with the 32 bits of random data, but is much larger (say 256 bits)

each time data is read from the PRNG, it calculates some random data. Some of this random data is fed to the user, the rest of the random data replaces the existing pool.

for 32 bits of random data, you can generate many TiB of output, and that output cannot be identified as not being random by any anlysis, yes, at some point it could repeat, but nobody can predict when that is, even if they have the contents of the pool

so the offset into the stream can be much larger than the randomness used to initialize the pool in the first place

If you are the only user of the PRNG, the offset into the stream is a known value to you and adds no randomness.

But if there are other users of the PRNG output, then that adds to the randomness of the bits you read from the PRNG

to post comments

A system call for random numbers: getrandom()

Posted Jul 27, 2014 23:12 UTC (Sun) by nybble41 (subscriber, #55106) [Link] (3 responses)

I don't think you're actually disagreeing with me.

If you don't control the offset, then yes, that contributes somewhat to the amount of entropy introduced into the PRNG. For example, if there could have been up to 1 MiB read from the PRNG in one-byte increments after it was seeded with 32 random bits but before you read your data, then that introduces at most 20 additional bits of entropy. You would have to search though a 52-bit space--32 bits of seed plus 20 bits of offset--to find a match for your data and determine the PRNG's internal state with a high degree of probability.

I say "at most 20 bits" because it would be unreasonable to assume that the possible offsets are uniformly distributed from zero to 1 MiB; some sizes will be more likely than others, reducing the search space.

On the other hand, if you fully randomized the PRNG's internal state, then any additional offset past that would contribute no additional entropy. Instead of searching the larger seed + offset space, you'd just search the PRNG's state space directly. If, that is, it were at all practical to brute-force search a 256-bit space.

A system call for random numbers: getrandom()

Posted Jul 28, 2014 0:13 UTC (Mon) by raven667 (subscriber, #5198) [Link] (2 responses)

I'm a bit of a layman, I didn't know that the PRNG was considered successfully seeded with only 32 bits, that seems awfully low, 256 bits sounds like a more reasonable number. It seems to be that it would be doable for a well financed organization to run the PRNG algorithm through every possible 32 bit seed value for a couple of megabytes of output at least. System startup isn't exposed to that many random variables, so it wouldn't surprise me if randomness taken from IRQ/IO timings and whatnot were clustered and not white noise there is enough different hardware/software combinations out there that this might not matter in a practical sense but your 32 bits of entropy is really something slightly smaller.

Over time as new randomness was folded in and the offset gets larger then I would have confidence that the state would be too random to predict but anything that uses the PRNG output shortly after it is initially set up seems that it could be using predictable values. This would seem to be of concern to users of randomness early in the boot process, ssh key generation being the most obvious, but there are other things which use randomness.

I would presume that the people who actually fully understand this stuff have thought about all of these things and are way ahead of a layman such as myself in mitigating these issues.

A system call for random numbers: getrandom()

Posted Jul 28, 2014 15:36 UTC (Mon) by apoelstra (subscriber, #75205) [Link] (1 responses)

>I didn't know that the PRNG was considered successfully seeded with only 32 bits

It's not :) unless the parent post was just giving example numbers, he meant to say "32 bytes" or 256 bits.

A system call for random numbers: getrandom()

Posted Jul 28, 2014 22:20 UTC (Mon) by nybble41 (subscriber, #55106) [Link]

The parent post was just giving example numbers. Those 32 bits would indeed be a fairly small seed for something like /dev/urandom, though it was the standard size for the C library's PRNG seed on 32-bit systems. (Hopefully no one was relying on rand() for anything security-related.)

On the other hand, if you seed /dev/urandom with 256 bits, but all but 32 of those bits are predictable to an attacker, you might as well be using a mere 32-bit seed... some entropy-starved embedded systems may be in this situation shortly after startup.