In August 2007, a young programmer in Microsoft’s Windows security group stood up to give a five-minute turbo talk at the annual Crypto conference in Santa Barbara.

It was a Tuesday evening, part of the conference’s traditional rump session, when a hodge-podge of short talks are presented outside of the conference’s main lineup. To draw attendees away from the wine and beer that competed for their attention at that hour, presenters sometimes tried to sex up their talks with provocative titles like “Does Bob Go to Prison?” or “How to Steal Cars – A Practical Attack on KeeLoq” or “The Only Rump Session Talk With Pamela Anderson.”

Dan Shumow and his Microsoft colleague Niels Ferguson titled theirs, provocatively, “On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng.” It was a title only a crypto geek would love or get.

The talk was only nine slides long (.pdf). But those nine slides were potentially dynamite. They laid out a case showing that a new encryption standard, given a stamp of approval by the U.S. government, possessed a glaring weakness that made an algorithm in it susceptible to cracking. But the weakness they described wasn’t just an average vulnerability, it had the kind of properties one would want if one were intentionally inserting a backdoor to make the algorithm susceptible to cracking by design.

For such a dramatic presentation — by mathematicians’ standards — the reaction to it was surprisingly muted. “I think folks thought, ‘Well that’s interesting,’ and, ‘Wow, it looks like maybe there was a flaw in the design,’” says a senior Microsoft manager who was at the talk. “But there wasn’t a huge reaction.”

Six years later, that’s all changed.

Early this month the New York Times drew a connection between their talk and memos leaked by Edward Snowden, classified Top Secret, that apparently confirms that the weakness in the standard and so-called Dual_EC_DRBG algorithm was indeed a backdoor. The Times story implies that the backdoor was intentionally put there by the NSA as part of a $250-million, decade-long covert operation by the agency to weaken and undermine the integrity of a number of encryption systems used by millions of people around the world.

The Times story has kindled a firestorm over the integrity of the byzantine process that produces security standards. The National Institute of Standards and Technology, which approved Dual_EC_DRBG and the standard, is now facing a crisis of confidence, having been forced to re-open the standard for public discussion, while security and crypto firms scramble to unravel how deeply the suspect algorithm infiltrated their code, if at all. On Thursday, corporate giant RSA Security publicly renounced Dual_EC_DRBG, while also conceding that its commercial suite of cryptographic libraries had been using the bad algorithm as its default algorithm for years.

But beneath the flames, a surprising uncertainty is still smoldering over whether Dual_EC_DRBG really is backdoored. The Times, crypto experts note, hasn’t released the memos that purport to prove the existence of a backdoor, and the paper’s direct quotes from the classified documents don’t mention any backdoor in the algorithm or efforts by the NSA to weaken it or the standard. They only discuss efforts to push the standard through committees for approval.

Jon Callas, the CTO of Silent Circle, whose company offers encrypted phone communication, delivered a different rump session talk at the Crypto conference in 2007 and saw the presentation by Shumow. He says he wasn’t alarmed by it at the time and still has doubts that what was exposed was actually a backdoor, in part because the algorithm is so badly done.

“If [NSA] spent $250 million weakening the standard and this is the best that they could do, then we have nothing to fear from them,” he says. “Because this was really ham-fisted. When you put on your conspiratorial hat about what the NSA would be doing, you would expect something more devious, Machiavellian … and this thing is just laughably bad. This is Boris and Natasha sort of stuff.”

Indeed, the Microsoft presenters themselves — who declined to comment for this article — didn’t press the backdoor theory in their talk. They didn’t mention NSA at all, and went out of their way to avoid accusing NIST of anything. “WE ARE NOT SAYING: NIST intentionally put a back door in this PRNG,” read the last slide of their deck.

The Microsoft manager who spoke with WIRED on condition of anonymity thinks the provocative title of the 2007 presentation overstates the issue with the algorithm and is being misinterpreted — that perhaps reporters at the Times read something in a classified document showing that the NSA worked on the algorithm and pushed it through the standards process, and quickly took it as proof that the title of the 2007 talk had been right to call the weakness in the standard and algorithm a backdoor.

But Paul Kocher, president and chief scientist of Cryptography Research, says that regardless of the lack of evidence in the Times story, he discounts the “bad cryptography” explanation for the weakness, in favor of the backdoor one.

“Bad cryptography happens through laziness and ignorance,” he says. “But in this case, a great deal of effort went into creating this and choosing a structure that happens to be amenable to attack.

“What’s mathematically creative [with this algorithm] is that when you look at it, you can’t even prove whether there is a backdoor or not, which is very bizarre in cryptography,” he says. “Usually the presence of a backdoor is something you can prove is there, because you can see it and exploit it…. In my entire career in cryptography, I’ve never seen a vulnerability like this.”

Read more: How a Crypto ‘Backdoor’ Pitted the Tech World Against the NSA

Print Friendly

Related posts: