2
$\begingroup$

After reading through the specification of the FIPS CTR_DRBG in SP 800-90A (see Section 10.2.1), I got the impression that the output of the DRBG coincides with its internal state as long as no additional input is given.

Let $(K, V)$ denote some previously initialized internal state. Let $E: K \times V \rightarrow V$ denote what ever block encryption algorithm is used.

When the CTR_DRBG_GENERATE function is called with no additional input, the output is calculated as described in 10.2.1.5.1, more specifically in the loop in step 4, which amounts to

$E(K,V+1) || E(K,V+2) || ... || E(K,V+n)$,

provided enough bits are requested.

Then the internal state is updated by calling the CTR_DRBG_UPDATE function with $\operatorname{provided\_data}= 0$ as specified in 10.2.1.2. Here in step 2 apparently the exact same loop happens, as above in step 4, except that it only generates a string of length of the internal state. Still, the new internal state starts with

$E(K,V+1) || E(K,V+2) || ... $.

There is still a final XORing with $\operatorname{provided\_data}$, but since that consists of all zeroes, it does not change anything.

Am I missing something here? Outputting the internal state like this seems unnecessary, because it allows anyone observing the output to predict all future output. At least before non-zero additional input is provided to the generate function or a reseed happens. This makes this CTR_DRBG specification completely incompatible with the AIS 20 requirement for forward secrecy, see 4.6.1 (DRG.1.2).

It is also completely avoidable, by simply adding different constants before encrypting, e.g. n+1, n+2, ... . Interestingly enough this seems to happen for the HASH_DRBG (10.1.1.4), although the situation is a little different there.

I am at a huge loss of why this could be the case. Is there a different threat modeling than what I have in mind? Is this forward prediction resistance simply not considered important enough?

$\endgroup$
2
$\begingroup$

Still, the new internal state starts with

$E(K,V+1) || E(K,V+2) || ... $.

There is where you are incorrect; the CTR_DRBG_GENERATE function updates $V$ while it runs, and hence the new internal state is actually>

$E(K,V+n+1) || E(K,V+n+2) || ... $

(where the $V$ value is initial value of $V$ when generate is called, not when the update is called).

Because these are encryptions of blocks that are distinct from the blocks used to generate the random output, there is minimal leakage of the new state (well, someone looking at the random output could deduce what the new state is not; however that's not of much help to an attacker)

$\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.