Tuesday, September 10, 2013

Is OpenSSL's Cryptography Broken?

by Dietrich Schmitz

Last month, in early August, a colleague Friend of mine, +Scott Doty contacted me.  He expressed his concern regarding Red Hat's implementation of OpenSSL.

The issue brought to my attention by Scott concerns a specific bugzilla ticket which was opened in 2007 and has never been addressed.

I offered Scott to reach out to Red Hat's public relations the same day he contacted me.  The answer returned the following day was essentially a 'no comment' and that I should refer to the comments section on the ticket -- deemed to be 'self-explanatory'.  If you take the time to review the ticket, you'll see where Scott appended his own comments in the August time frame toward the bottom.  It's fairly long.

Red Hat had absolutely no intention of fixing the bug, specifically, regarding the treatment of the Elliptic Curve Cryptography implementation in OpenSSL, and according to the comments on the ticket they felt ECC was patent encumbered.

Yet, in other sources on the Internet, one can find reference to a 'work-around' which would avoid any IP infringement issues.  Quoting from Wikipedia.org's ECC page:

"...However, according to RSA Laboratories, "in all of these cases, it is the implementation technique that is patented, not the prime or representation, and there are alternative, compatible implementation techniques that are not covered by the patents."[3] Additionally,Daniel J. Bernstein has stated that he is "not aware of" patents that cover the Curve25519 elliptic curve Diffie–Hellman algorithm or its implementation.[4] RFC 6090, published in February 2011, documents ECC techniques, some of which were published so long ago that even if they were patented any such patents for these previously published techniques would now be expired...."

Alright, so it struck Scott as being odd that such a bug was laying around collecting dust, and I agreed.

In the meantime, we have seen a series of news releases with Snowden giving out new information.  One of the claims has been that the capability of NSA to penetrate presumed to be secure cryptography standards has become much improved to such an extent that they are now collecting information flowing over SSL with impunity and have broken a few other cryptographic standards, purportedly.  I say this only because it's Snowden's word vs. the NSA and the NSA is completely 'mum' on the topic.

The sensational news story "Report: NSA Can Break Internet Encryption"arrived last week and created quite a stir.  The title is a carefully crafted wording.  Naturally, it is quite an unsettling thought to have all presumed Internet security breached, but the story's author hedged a bit at the end of his story saying:
"...Despite the NSA's ability to crack web encryption with these means, Wired's Kim Zetter notes that "these methods don’t involve cracking the algorithms and the math underlying the encryption, but rather rely upon circumventing and otherwise undermining encryption." 
And Snowden himself said during a Q&A with The Guardian in June that cryptography works. 
"Properly implemented strong crypto systems are one of the few things that you can rely on," he said...."
Now, the distinction to be made ties into the title of the story -- namely that, provided that an 'implementation' of strong cryptography coded 'properly' with no side-effect bugs cannot be hacked.

Put another way, bug-laden cryptography can result in weakening of the underlying cipher's strength and so can potentially be cracked.

This would seem to suggest that the NSA have found defects in various cryptographic standards, or, by whatever means, have introduced themselves intentionally crafted bugs in such a way to induce such weakening, thereby achieving their end-goal to crack encryption methodologies.

This led me to think more about OpenSSL and that languishing buzilla ticket.  Just yesterday, I had an exchange with +Jan Wildeboer to whom I regularly communicate, usually on Google Plus.  I broached the matter of the Red Hat OpenSSL bugzilla ECC ticket with him and curiously enough, today, he cc'd me with this Google Plus post (thank you Jan):

Mike Hearn

Shared publicly  -  10:29 AM
A few days ago Bruce Schneier, who has reviewed the leaked Snowden documents, warned against the use of elliptic curve cryptography on the grounds that it requires users to agree on curve parameters and he no longer trusts the parameters to not have back doors. Specifically he's talking about the NIST curves. NIST is a US organisation that was previously widely respected and considered trustworthy.

However, his warning seemed to be based more on general conservatism than any specific intelligence cleaned from the leaked documents. We know the NSA has tried to subvert the standards setting process and we know they may have advanced mathematical attacks that the public doesn't know about. ECC requires various constants to be agreed on globally for an instantiation to be used. Hence, the concern.

But that isn't specific evidence. Unfortunately, today I  learned (via Gregory Maxwell) that the process for selecting the "random" curve parameters appears on the surface to be completely implausible. The parameters are the output of SHA1, which should be good if the seed was selected in a reproducible manner. But they were not. The seeds are extremely large constants with no explanations of where they came from. That smells very strongly of something that might be hacked.

It gets better. It turns out that these constants are not only unexplainable but were actually generated by an employee of the NSA. And it turns out that the IEEE working group that worked on standards for ECC was actually holding its meetings on the NSA campus and its membership therefore had to be approved by the NSA as well.

At this point it is fair to assume that the NIST SECG curves should be abandoned for all uses. Bitcoin uses secp256k1 which was not selected in the same way and is more likely to be OK, and besides the NSA is unlikely to care about stealing peoples wallets (we don't use ECC for secrecy, just authenticity). And luckily academics like djb and Tanja Lange have created new variants of ECC independently of the NSA which are technically better anyway. But the upgrade process away from the SEC curves is going to be a pain.

So, that's quite interesting.  It would now appear that ECC is borked and quite possibly has been so for quite some time, thanks to the handy-work of the NSA.

The cat is now out of the bag.  I am now wondering how many other cryptographic standards need a thorough audit and scrubbing of any questionable code and fixing of languishing bugs?

-- Dietrich
Enhanced by Zemanta


Post a Comment