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.
“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.”
- acudoradavid posted this