1
$\begingroup$

Since Linux 5.18, the internal state of the ChaCha-based CSPRNG is a 256 bits (32 bytes) BLAKE2s hash. There is also a fast key erasure mechanism which reseeds the CSPRNG every minute (source).

I know we can read as much random data from /dev/urandom but I didn't understand how "conceptually" we can get, for example, a 512 bits secret (so 512 bits of entropy) from this output if the seed of the CSPRNG is only 256 bits.

Finally, the “crng” is our ChaCha-based pseudorandom number generator, which takes a 32-byte “seed” as a ChaCha key, and then expands this indefinitely, so that users of the RNG can have an unlimited stream of random numbers. The seed comes from the various entropy sources that pass through BLAKE2s.
https://www.zx2c4.com/projects/linux-rng-5.17-5.18/

I stumbled upon this question/answer which make me reconsider my thought process. I think I have found the answer but I'd like a confirmation. Here is my understanding :

A CSPRNG is intended to be indistinguishable from a true random source. There is no point of comparing the entropy of the seed and the entropy of the CSPRNG output. The output entropy is maximal. Specifically the entropy of a sequence of numbers generated by a CSPRNG is precisely its length in bits.

Basically, the output of a CSPRNG is not limited by the entropy of the data that was used to seed it.

However, this answer does not support my explanation...

There is no relationship between source entropy and the output entropy from a TRNG other than you can't output more entropy than you put in
Relationship between source and output entropy

$\endgroup$
2
  • 1
    $\begingroup$ I'm pretty sure the answer is: you're right, you cannot get 512 bits of entropy if you don't reseed in the middle with some new randomness. But I suspect the rest of the answer is: there is no reasonable context in which you require more than 256 bits of entropy. We have no known processes which could distinguish (before our sun explodes) between XChaCha20(s) and s' where s is 256 bits and s' is 512 bits. $\endgroup$
    – rozbb
    Jan 19 at 19:48
  • 1
    $\begingroup$ If you want more than 256 bits of entropy then you need to instantiate your own CSPRNG which has more than 256 bits of internal state (ex. keccak sponge) and then sample linux random multiple times (with some delay between samples) and absorb the samples. You will get getting fresh entropy linux is producing. This assumes linux reseeds its own internal CSPRNG state in between the times you sample it. $\endgroup$ Jan 20 at 23:48

2 Answers 2

2
$\begingroup$

You can, of course, extract 512 bits of data out of a CSPRNG and get a 512-bit secret. However, the rule with entropy is that you can't get more out than you put in. Thus, assuming that the amount of entropy in the CSPRNG in question is 256 bits, then the secret contains no more than 256 bits of entropy, no matter how large it is. (It could be smaller, say, if you generated a 128-bit output.)

It can in fact be very useful to generate larger outputs because we need a larger output without needing more security. For example, we might need to generate two separate 256-bit encryption keys, one for each direction, two separate 128-bit IVs (which might need to be unpredictable, but not secret), and two separate 256-bit MAC keys. However, ultimately, the security of our scheme is no more than 256 bits, and if an attacker could harness that level of brute force power (which physics tells us is not possible on this planet), they could break the entire scheme.

As a practical matter, we believe that 256 bits of security is beyond adequate for the indefinite future, so it doesn't matter that the CSPRNG might output lots of keystream based on it. On an active system, we'll reseed frequently anyway due to various network and timer interrupts, and that alone will offer plenty of security by limiting the amount of data we generate from a single CSPRNG seed (not to mention the TRNG included in many modern systems). We believe that even seeding the system with 256 bits of entropy once at boot and running it for an extended period of time should be fine.

It is true that a CSPRNG is intended to be indistinguishable from a random source up to a security bound. If I could harness enough power to try all $ 2^{256} $ possible keys, then of course I could make ChaCha fail the next bit test, since I could predict future output with certainty. However, when we say that a CSPRNG is intended to be indistinguishable from a random source, the security bound related to brute force is typically implied. As mentioned above, this is not a feasible task.

$\endgroup$
1
$\begingroup$

A simple way to look at it is if you collected all possible different versions of the 512 bit output.

Because $H_{out} \not > H_{in} $, you'd only find $ <2^{256}$ versions, not $2^{512}$ as you'd expect. The less than sign is there as BLAKE2 is a hash function and thus susceptible to collisions in its output. Thus "Specifically the entropy of a sequence of numbers generated by a CSPRNG is precisely its length in bits" is false.

$\endgroup$
1
  • $\begingroup$ Ok. That's makes sense. So the Linux CSPRNG cannot give out more than 256bits of entropy and we can't really implement an encryption algorithm on Linux using getrandom exclusively and requiring a key of more than 256 bits (of entropy). But that's okay because 256 bits is already extremely secure. $\endgroup$
    – Rand0mMan
    Jan 21 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.