0
$\begingroup$

Based on the BSI evaluation criteria for quality of deterministic random number generators:

K4 – It should be impossible, for all practical purposes, for an attacker to calculate, or guess from an inner state of the generator, any previous numbers in the sequence or any previous inner generator states.

What is exactly the inner state in simple words? Is it the the very first seed? Also I would appreciate if you explain what is meant by the above rule?

Many Thanks.

$\endgroup$
0
$\begingroup$

I'll use ChaCha20 as an example. It's a stream cipher, but is used as the core of the system random number generator on Linux.

I'll also refer you to this excellent article about how ChaCha20 works as a stream cipher.

ChaCha20 can be used as a fast key erasure CSPRNG. When a caller requests $N$ bits of random data (a single number in the sequence), it's used to generate $N+256$ bits, and the last 256 bits are used as a new key for future requests. (Some systems like Linux additionally XOR in some bits from various system noise sources when they make this new key.)

ChaCha20 works by scrambling a 512-bit block repeatedly, using 20 rounds (broken into 80 quarter rounds) for each $N-256$ bits of output.

The inner state is the 512-bit block that gets scrambled. It consists of a constant value, a counter, a nonce (a second counter in this case), and a key (which is where the initial seed goes).

ChaCha20 is a strong cipher. It's computationally infeasible (read: effectively impossible) to discover anything about the key given only the output.

So if an attacker gets a copy of the inner state used in the generation of a requested number, they know the key used for that particular request, which is the last 256 bits of the previous request's output. But it's impossible to generate the key used for the previous request from any amount of its output, let alone the last 256 bits only, so they can't discover the number returned by the previous request from this alone. Therefore, they can't discover the previous number returned, and from there can't determine any other previous numbers in the sequence.

CSPRNGs other than ChaCha20 may have different sized inner states, but there's generally some fixed-size block that gets scrambled repeatedly in some manner. Part of it will be the seed, part will be other data needed in the computation of the output.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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