Serious vulnerability found in elliptic curve PRNG - cryptographers freak out.

Nov 16, 2007

A major component of cryptographic systems are pseudorandom number generators used to pull values out of thin air for the purposes of generating session keys and the bignum components of crypto keys, among other things. This is done so that an eavesdropping attacker can't predict ahead of time what a particular key is going to be and decrypt traffic as it's transmitted. Another reason is that it's easier to generate a pseudorandom number and check it for certain properties all at once than it is to work up such a number by hand and check it against those properties every step of the way. For example, generating really big prime numbers is hard to do for a person, but easy if you start pulling 128 digit numbers out of your ear and testing them to see if they're really prime using various and sundry techniques that I won't bore you with here.

Incidentally, I say pseudorandom because, by the strictest technical sense, the numbers thus generated aren't actually truly random because they are determined to a large degree by carefully engineered algorithms that are fed values from different parts of the computer they're running on. It is common for such a PRNG to be fed the current system clock time, number of packets received on all of the network interfaces, the number of interrupts logged by the OS' kernel, the number of processes running at that particular moment (down to the millisecond), and other stuff like that. The seed values would be damnably difficult to predict because they change faster than people can think. Still, they are close enough to being truly random that they are considered useful for cryptographic use.

Anyway, to keep up with the times, NIST (National Institute of Standards and Technology) is working up a new standard designated 800-90, which describes four methods of generating pseudorandom numbers, which the document refers to as DRBG's, or deterministic random bit generators, each using a different method. One of those generators, called Dual_EC_DRBG (dual elliptic curve deterministic random bit generator.. who came up with that?!) uses a method of generating random values using elliptic curves, a particularly arcane mathematical sub-field that involves points on a curve, a set of coordinates on a two-dimensional grid, and the equation defining the shape of the curve.

The problem is this: Two cryptographers named Dan Shumow and Niels Ferguson figured out that the equation and set of points NIST was thinking of ratifying as a standard (it's in the linked .pdf document at the top of page 58) is not just slightly biased toward one group of output numbers or another (this has been known since 2006), but that the constant values Q on the elliptic curve defined in the spec (Appendix, page 74) are actually based upon a common secret number.

"But Doc," you're probably saying to yourselves. "What in the hell does it mean?"

Just this: Each constant Q of the curve has a component that isn't immediately apparent, e, so each Q is actually some other number.... let's call it charlie raised to the power of e. This means that if you know value e, you then have insight into the state of the algorithm at any particular step of the process (read the other linked .pdf file, Shumow and Ferguson's presentation - it's short), and thus can figure out what the input of the algorithm was by performing some computational magick on just 32 bytes of encrypted traffic (or about four typed characters, assuming 8-bit bytes) and determine the rest of the plaintext, or data before encryption. Decrypt-a-mundo.

Who knows what that magick value e is? Nobody knows. Probably whoever came up with the constants Q in the first place, because the name of the person or organization isn't anywhere in the document.