3
$\begingroup$

Recently, the DUHK attack on bad RNG implementations of hardware devices has been published.

The attack is based on a (known or reverse engineerable) hardcoded key, which is used for a ANSI X9.31 based PRNG to create key material.

According to the blog post by Matthew Green, the attack is explicitely based on the X.931 generator: "ANSI X9.31 (and its cousin X9.17) is over twenty years old. It’s (fortunately) been deprecated as of 2016, but a huge number of products still use it. This algorithm should have disappeared ten years earlier"

But I keep wondering, how this attack is specific to ANSX X9.31. As far as I understand it, the very same problems would arise, if a hardcoded key would be used with any of the other keyed PRNG standards (like HMAC_DRBG or CTR_DRBG). What am I missing?

$\endgroup$
  • 1
    $\begingroup$ Also see Wagner and Goldberg's Randomness and the Netscape Browser. It looks like the same class of attack, and it appears the Netscape's PRNG was a little stronger because Netscape used time+pid, and not just time. To add insult to injury, Netscape had 40-bit export restrictions to contend with on their cryptography back in 1996, and it still appears to be stronger than some of these appliances used today. $\endgroup$ – jww Oct 31 '17 at 22:42
3
$\begingroup$

As far as I understand it, the very same problems would arise, if a hardcoded key would be used with any of the other keyed PRNG standards (like HMAC_DRBG or CTR_DRBG). What am I missing?

The issue is that, for X9.31, the key really is a long term key; it is never updated as a part of the RNG process.

That is, the state of X9.31 consists of a 'current state' (64 or 128 bits), and a 'key'; when you generate the next batch of outputs, you update the 'current state', but not the 'key'. Hence, if you start with a fixed key, you'll end up using that for the life of the PRNG.

So, if we assume that the X9.31 has been used for a while (and so the attacker doesn't know the exact state; one of its input is the 'current time', that does act as a weak entropy source). However, if X9.31 starts with a fixed key, that key is still in effect; if the attacker sees one output and has a guess of the current time, he can then predict future outputs (and previous as well, the state update function is invertible if you know the key).

In contrast, for the HMAC_DRBG or the CTR_DRBG generates, when they generate a batch of output, they update the 'current state', but they also update the 'current key'. So, if the PRNG is used for a while (and so the attacker doesn't know the state of the PRNG), the attacker won't know anything about the HMAC_DRBG or CTR_DRBG key, hence the attacker has no advantage in predicting future (or previous) outputs.

Of course, if the PRNG starts off with no entropy (fixed key and state), and doesn't get enough entropy before the attacker observes the output, the attacker can easily recover the state (and predict outputs); this is true for any PRNG. What is special about X9.31 with a fixed key is that this also holds even if the state has been given enough entropy.

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