Sunday, January 15, 2012

EAX', Knight Rider, and an admission of defeat

A few weeks back I found myself on the wrong side of Daniel Bernstein over something I'd tweeted the week before. This was pretty surprising, since my original tweet hadn't seemed all that controversial.

What I'd said was that cryptographic standards aren't always perfect, but non-standard crypto is almost always worse. Daniel politely pointed out that I was nuts -- plenty of bad stuff appears in standards, and conversely, plenty of good stuff isn't standardized. (As you can see, the conversation got a little weirder after that.)

Today I'm here to say that I've found religion. Not only do I see where Daniel's coming from, I'm here to surrender, throw down my hat and concede defeat. Daniel: you win. I still think standards are preferable in theory, but only if they're promulgated by reasonable standards bodies. And we seem to have a shortage of those.

My new convictions are apropos of an innocuous-looking ePrint just posted by Kazuhiko Minematsu, Hiraku Morita and Tetsu Iwata. These researchers have found serious flaws in an authenticated block cipher mode of operation called EAX' (henceforth: EAXprime). EAXprime was recently adopted as the encryption mode for ANSI's Smart Grid standard, and (until today) was practically a shoo-in to become a standalone NIST-certified mode of operation.

Ok, so standards get broken. Why I am I making such a big deal about this one? The simple reason is that EAXprime isn't just another standard. It's a slightly-modified version of EAX mode, which was proposed by Bellare, Rogaway and Wagner. And the important thing to know about EAX (non-prime) is that it comes with a formal proof of security.

It's hard to explain how wonderful this is. The existence of such a proof means that (within limits) a vulnerability in EAX mode would indicate a problem with the underlying cipher (e.g., AES) itself. Since we're pretty confident in the security of our standard block ciphers, we can extend that confidence to EAX. And the best part: this wonderful guarantee costs us almost nothing -- EAX is a very efficient mode of operation.

But not efficient enough for ANSI, which decided to standardize on a variant called EAXprime. EAXprime is faster: it uses 3-5 fewer block cipher calls to encrypt each message, and (in the case of AES) about 40 bytes less RAM to store scheduled keys. (This is presumably important when your target is a tiny little embedded chip in a smart meter.)

Unfortunately, there's a cost to that extra speed: EAXprime is no longer covered by the original EAX security proof. Which brings us towards the moral of the story, and to the Minematsu, Morita and Iwata paper.

Did you ever see that old episode of Knight Rider where the bad guys figure out how to neutralize KITT's bulletproof coating? Reading this paper is kind of like watching the middle part of that episode. Everything pretty much looks the same but holy crap WTF the bullets aren't bouncing off anymore.

The MMI attacks allow an adversary to create ciphertexts (aka forgeries) that seem valid even though they weren't created by the actual encryptor. They're very powerful in that sense, but they're limited in others (they only work against very short messages). Still, at the end of the day, they're attacks. Attacks that couldn't possibly exist if the standards designers had placed a high value on EAX's security proof, and had tried to maintain that security in their optimized standard.

And this is why I'm admitting defeat on this whole standards thing. How can I advocate for crypto standards when standards bodies will casually throw away something as wonderful as a security proof? At least when KITT lost his bulletproof coating it was because of something the bad guys did to him. Can you imagine the good guys doing that to him on purpose?

1 comment: