David McClain

Dual EC-DRBG Flaw

I discovered a major flaw in a newly recommended (by NIST, NSA) cryptographic random number generator. 

The algorithm is known as the Dual Elliptic Curve Deterministic Random Bit Generator, or Dual EC-DRBG for short. There have been many criticisms of this algorithm since it was first recommended by NIST. 

Some people are suspicious that numbers in the algorithm were carefully selected by the government to allow them a backdoor into security systems; a backdoor that nobody knows about. I don’t take that as a serious possibility because it is very easy to develop your own numbers that NSA could never have known about in advance.
But the flaw I did find was posted to Bruce Schniers’s Security Blog site this morning:

“With all of the criticisms of the Dual EC DRBG algorithm, one I have not seen, but which stands as a possible risk factor for differentiating the output from a random source, is the development of limit cycles in the use of the first EC.

In the Dual EC DRBG, the X coordinate of a seed-multiplied point on the first curve is used as the seed for that same curve in the next cycle. This is similar to the use of iterated Hash functions.

It is possible that a limit cycle will develop with considerably shorter period than that of the the point group on the curve. This will then produce long duplicate bit streams at rates much more frequently than would be expected from a random source.

Concrete example: Take a humanly tolerable situation based on GF(2^7). With curve parameters A = 1, B = 26, P = (9,3), this group has a period of 73.

So starting with a seed of 10, a very much shorter limit cycle is developed with period 12.

I’m not stating that existing implementations do show such behavior, only that it cannot be ruled out. I don’t know how to predict when it will happen, and so I don’t know what good curves and keys should be used, nor if careful choices can even prevent the formation of limit cycle behavior.”

  1. acudoradavid posted this