[Cryptography] Dual_EC_DRBG backdoor: a proof of concept

[Theodore Ts'o]

On Fri, Jan 03, 2014 at 06:02:04PM +0100, Krisztián Pintér wrote:
> 
> i think you put too much burden on a prng. all prngs need a secret
> seed.

Sure, but a prng is not the only tool in the toolbox.  You can also
try to grab entropy from hardware, and from OS-level events.  Whether
you use Fortuna or Linux's /dev/random, or some other system which
tries to distill entropy from hardware level events, these are all
things which you can do instead of, or better yet, in addition to,
relying on some initial stored secret.

So for example, it's a really good idea to seed Linux's /dev/random
with some unpredictable randomness.  We save some before system
shutdown, and we reinitialize it with it on system startup.  But if
you are starting up a VM from scratch, initializing the seed file with
a secret is a useful thing to do.

> that said, as i heard, dual-ec does not have a security proof. correct
> me if i'm wrong.

It has a security proof *if* the primes chosen in an honest fashion.
What's not proven is whether the prims were chosen in an honest
fashion.

There are ways you can do that; for example, it used to be the case
that the IETF Nomcom chair would select the people on the committee by
publically announcing the list of volunteers, and a list of ten stock
symbols in advance, and then use an PRNG based on the stock volumes
and/or stock prices on a pre-announced date in advance.  The
presumption was that IETF members didn't have the ability to
manipulate the stock market to a fine enough degree to force a
particular outcome, and since it was public, it meant that the Nomcom
chair could demonstrate to the world that he or she didn't pack the
committee with people of his choosing.

If the adversary can control the US stock market, or there is the
belief that there that the adversary could control the US stock
market, maybe you would need to use multiple markets.  Of course, this
would still be subject to manipulation by world-wide secret society of
the Illmuinati....

       	 	  	     	 	- Ted