Archive for the ‘Cryptography’ Category

“Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.”

Thursday, September 19th, 2013

There’s an interesting post over at the Cryptographic Engineering blog about Duel-EC.

For those not following the story, Dual-EC is a pseudorandom number generator proposed by NIST for international use back in 2006. Just a few months later, Shumow and Ferguson made cryptographic history by pointing out that there might be an NSA backdoor in the algorithm. This possibility — fairly remarkable for an algorithm of this type — looked bad and smelled worse. If true, it spelled almost certain doom for anyone relying on Dual-EC to keep their system safe from spying eyes.

The post itself is pretty wonky, but a couple of scattershot points:

Flaw #1: Dual-EC has no security proof.
Let me spell this out as clearly as I can. In the course of proposing this complex and slow new PRG where the only damn reason you’d ever use the thing is for its security reduction, NIST forgot to provide one. This is like selling someone a Mercedes and forgetting to attach the hood ornament.

Flaw #3: You can guess the original EC point from looking at the output bits.

Flaw #4: If you know a certain property about the Dual_EC parameters, and can recover an output point, you can predict all subsequent outputs of the generator.

This is a huge deal in the case of SSL/TLS, for example. If I use the Dual-EC PRG to generate the “Client Random” nonce transmitted in the beginning of an SSL connection, then the NSA will be able to predict the “Pre-Master” secret that I’m going to generate during the RSA handshake. Given this information the connection is now a cleartext read. This is not good.

Flaw #5: Nobody knows where the recommended parameters came from.

So does all of this amount to a backdoor? Quoth Matthew Green,

including some kind of hypothetical backdoor would be a horrible, horrific idea — one that would almost certainly blow back at us.
You’d think people with common sense would realize this. Unfortunately we can’t count on that anymore.

(Subject line hattip.)

(You know, I’m halfway tempted to start a Kickstarter for a truly random random number generator. Something based off atomic decay, perhaps. What’s stopping me is:

  1. I have no electronics design skills or ability. Of course, I could hire someone, but…
  2. I’d be surprised if someone hasn’t already done this.)

(Edited to add: You could just get your random numbers from here, of course, while you’re waiting for the revolution. Nothing wrong with that plan, is there?)

(Speaking of Big John von Neumann, I just finished Turing’s Cathedral: The Origins of the Digital Universe, about the early history of computing, with a strong concentration on the Princeton Institute for Advanced Study and von Neumann’s work. It’s an interesting book – I think it serves as a good introductory biography of von Neumann. Dyson wanders a bit into the mystic towards the end, a little bit more than I would have liked, which prevents me from fully endorsing it. But if you liked Project Orion: The True Story of the Atomic Spaceship, you should enjoy this book as well.)