Last week the students and I went looking for our long-lost GnuRadio USRP in a dusty hardware security lab down the hall. This particular USRP hasn’t been seen in about five years (I suspect it may have been deported with the lab’s previous occupant) so the whole thing was kind of a long shot.

Sometimes best part of a treasure hunt is what you find along the way. The students didn’t find the USRP, but they did uncover a fog machine and laser that someone had tucked under a workbench. This kept them happy ’til we got a whiff of the “fog” it was making. I scored something even better: a mint copy of Tim Hartnell‘s 1985 masterpiece, the Giant Book of Computer Games.

If you’re just a few years younger than me, you might think Games is a book about games. But of course, it literally is games: dozens of all-caps BASIC listings, printed in a font that was probably old when Wargames was new. Each game sits there on the page, pregnant with potential, waiting for a bored 9-year old to tap it into his C64 or Apple ][ and hit “RUN”. (Sadly, this could be a long wait.)

Flipping through Games brings back memories. The Chess AI was a bastard, routinely cheating even if you implemented it properly. And you never implemented anything properly, at least not on the first pass. This was part of the fun. Between typos and the fact that Hartnell apparently coded to his own BASIC standard, the first play usually went like this:

WELCOME TO SNARK HUNT
ENTER 1 FOR SNARK, 2 FOR HUNTER
> 2
YOU CHOSE SNARK
?SYNTAX ERROR AT LINE 3980
READY

You learned debugging fast. When that didn’t work, your last, desperate move was simply to delete the offending lines — ’til the program either (a) worked, or (b) got so crazy that you deleted it and loaded Bruce Lee off a cassette. Sometimes you hit the sweet spot between the two: my “Chess” AI would grab control of my pieces Agent Smith-style and send them hurtling towards my undefended King. I never saw this as a bug, though; I just thought it had style.

When I started writing this post I intended to make a broader point about how my experience with Games mirrors the way that modern implementers feel when faced with a mysterious, unjustified cryptographic standard. I think there is a point to be made here, and I’ll make it. Another day.

But when I googled to see what Hartnell is up to, I was saddened to learn that he died all the way back in 1991, only a few years after Games was published. He was only a few years older than I am today. So on reflection, I think I’ll just let this post stand as it is, and I’ll go spend some time with my kid.

Tim, wherever you are, please accept this belated tribute. Your book meant a lot to me.

I wanted to take a quick break from the technical to bug you about something important.

The end of the year is coming up and no doubt there are some folks thinking about last minute charitable donations. There are many, many worthy causes you can support. All things being equal, I’d give to my local food bank first, given how much need there is, and how far these institutions can stretch a charitable dollar ($1 at a food bank buys the equivalent of $20 at a retail supermarket).

But if you have something left over I’d strongly recommend that you give to the Electronic Frontier Foundation. In case you haven’t noticed, there’s a lot of crazy stuff going on with technology and the law these days. I recently poked fun at how small the EFF’s budget is, but I meant it with love (and with reason!). They’re fighting a tough uphill battle with minimal resources.

I have a personal reason for supporting the EFF. Back when I was a grad student, some colleagues and I reverse-engineered a commercial device as part of a research project. This is something that security researchers do from time to time, and it’s something we should be able to do. Our goal was expose flaws in industrial security systems, and hopefully to spur the adoption of better technology. (Note: better technology is now out there, and no, I’m not taking credit. But scrutiny is generally a good thing.)

Anyway, we knew that there were legal obstacles related to this work, we just didn’t realize how significant they’d be. When we first disclosed our findings, there were some… unpleasant phone calls at high levels. The University’s legal counsel politely informed us that in the event of a lawsuit — even a frivolous one — we’d be bearing the expense on our own. This is not a pleasant prospect for a newly-married grad student who’s just signed mortgage papers.

It’s possible that without the EFF we’d have called the whole thing off right then. But the EFF did support us. They took our case (for free!), and worked miracles.

While our story has a happy ending, white hat security research in the US is still a minefield. Sadly this state of affairs doesn’t seem to be improving. The EFF is just about the only group I know of that stands up for security researchers. Even if you’re not a researcher, you probably benefit indirectly from their work.

So please take a minute to donate. It’s tax deductible and some employers will match. If you donate at least $65 and become a member, they’ll even send you an awesome T-shirt (I have one from 1999 that’s still going strong — it’s ugly as sin but damn, the build quality is high.) Again, I’m not saying this should be the only donation you make this year, but it certainly would be a good one.

On the other hand, writing:
/* Paul Kocher thinks this is ok */ 
does not necessarily make it ok.

Just sayin’.

In mid-December 1941, Driscoll finally sent the British some information on her special method, with only cursory answers to the few questions Denniston had posed four months before. Driscoll again declared her faith in her approach, but GCCS concluded that it “apparently failed.” For one thing, it could not, as she had claimed, overcome the problem of turnover — that is, the tumbling of the Enigma’s wheels before enough letters had been enciphered to identify the wheel being used. And as Turing pointed out to her in a letter in October 1941, her method would take seventy-two thousand hours — more than eight years — to find a solution. Given Driscoll’s obstinacy, Bletchley park began to have second thoughts about providing more technical information.

As luck would have it, an apparent mix-up in the mail delivery between OP20G and Bletchley Park soon brought the simmering distrust and jealousies between the two agencies flaring the the surface. Dennison’s early October dispatch — a bag of materials containing detailed answers to all but one of Driscoll’s questions — never reached OP20G, the Navy claimed. It didn’t take long for Safford, who feared the British were breaking their promises, to push Leigh Noyes into firing off a series of complaints to the British. Through November and December 1941, angry memos and accusations flew across the Atlantic. Noyes didn’t mince his words: Britain had broken its promise to OP20G; American had no use for the Bombe; and if GCCS cooperated, Driscoll could have her method working on real problems. …

Noyes, who was unaware of the complexities of the mail mix-up, continued to fire off angry memos to the British, some of them clearly threatening. The U.S. Navy, he said, had never agreed to confine itself to Enigma research. It had always intended to be “operational” — that is, intercepting and decoding messages on its own. He told Hastings that all the Navy wanted from the British was the information on the Enigma and the codebooks and Enigma machine that Safford and Driscoll had requested.

Then, belying later histories of GCCS and OP20G relations, Noyes apologized to the British, twice. On December 10 and again on the twelfth, he declared that British explanations and actions since his outbursts had satisfied him and “everyone” at OP20G. The missing package, of course, was found. On December 13, Bletchley received a cryptic yet pointed message from someone in the U.S. Navy Department: “Luke Chapter 15, v 9: And she found it. She calleth together her friends and neighbors saying: Rejoice with me for I have found the piece which we lost”.

— Jim DeBrosse, Colin Burke: The secret in Building 26

Apropos of my last post, Colin Percival tweets:

I still think encrypt+MAC trumps AEAD because of side channel attacks on block ciphers.

AEAD stands for Authenticated Encryption with Associated Data, and it describes several new modes of operation that perform encryption and authentication all in one go, using a block cipher and a single key, rather than a separate MAC.* In my last post I recommended using one of these things, mostly because it’s simpler.

Colin thinks you’re better off using traditional encryption plus a separate hash-based MAC, e.g., HMAC (using a separate key), rather than one of these fancy new modes. This is because, at least in theory, using a block cipher for authentication could make you more vulnerable to side channel attacks on the block cipher.**

This tweet is followed by some back and forth, which becomes amusing when I fail to read a simple diagram and make a fool of myself. Also, I step on a rake.

My foolishness aside, this point deserves some unpacking. Let’s grant — without comment — the proposition that block-ciphers are vulnerable to side-channel analysis and HMAC-SHAx isn’t. Or at very least, if it is vulnerable, we’re only going to expose the MAC key, and we don’t care about that.***

Let’s also grant that our implementation is free of better vulnerabilities, and that side-channel attacks on block ciphers are actually where our attacker’s going to hit us.

So now we’re talking about three separate questions:

1. Will using Encrypt + MAC (vs an AEAD) protect you from side-channel attacks on encryption? Trivial answer: no. You’re using the block cipher to encrypt, so who cares what authentication you perform afterwards.

But ok, maybe your side-channel attack requires the device to encrypt known, or chosen plaintexts, and it won’t do that for you. So you need something stronger.

• Will using Encrypt + Mac (vs an AEAD) save you from side-channel attacks that work against the decryption of arbitrary ciphertexts? Answer: again, probably not. If you can get your hands on some legit ciphertexts (replays, for example), you can probably exercise the block cipher. At least in theory, this should be enough to implement your attack.
• Will using Encrypt + Mac (vs an AEAD) save you from side-channel attacks that require decryption of known, or chosen ciphertexts? Answer: this may be the case where the means of authentication really matters.

So let’s drill into case (3) a bit. If you’re using Encrypt + MAC with a hash-based MAC (and a separate key), then the block cipher only comes into play for legitimate messages. Your decryption process simply terminates when it encounters an invalid MAC. This should prevent you from submitting chosen or mauled ciphertexts — you’re limited to whatever legit ciphertexts you can get your hands on.

On the other hand, if you’re using an AEAD mode of operation — which typically uses a single key for both authentication and encryption — then technically your block cipher (and key) come into play for every ciphertext received, even the invalid ones.

Alright, let’s dig into the modes a bit to see what kinds of encipherment/decipherment actually happens when you submit a ciphertext (and its IV, associated data) to be decrypted:

Since the IV is typically adversarially-selected (in part), this gives the adversary a chance to exercise the encipherment mode of the cipher on a single partially-chosen block. One block doesn’t sound bad — however, he may be able to submit many such chosen ciphertexts.

• CCM mode: CCM is a combination of CTR-mode encryption with CBC-MAC. Since the MAC is computed over the plaintext, the CCM decryptor can’t verify (and hence reject a bad ciphertext) until after he’s completely decrypted it. Decryption is actually encipherment of a set of known counter values, the first of which is (partly) chosen by the adversary.
• OCB mode: Difficult to say. It’s the same as CCM, as far as decryption before MAC testing. However, this complicated by the fact that the cipher is ‘tweaked’ in a DES-X-type construction. And honestly, nobody uses it anyway.
• EAX mode: the good news is that the MAC is computed on the ciphertext, so the decryptor shouldn’t decrypt the ciphertext unless the MAC is valid. The bad news is that the MAC is a CBC-style MAC (OMAC), using the same key as for decryption, so authentication will encipher at least some chosen values.

So where are we? Pretty far down the rabbit hole.

I’m going to go with the following: if you’re deeply afraid of side-channel attacks on your block cipher, you might feel marginally better about with Encrypt + MAC if your application is definitely not vulnerable to cases (1) and (2) above and you’re positive that HMAC-SHAx isn’t vulnerable to side-channel attacks. Otherwise I’d use an AEAD just to make my life simpler.

But I’m not passing judgement on this. It’s a new perspective to me, and I’m genuinely curious to see what others have to say. Can people recommend any practical attacks, papers, opinions on this subject?

Notes:

* Includes GCM, CWC, OCB, EAX and CCM modes.

** Attacks like the recent attack on the Mifare DESFire, or timing/cache timing attacks on AES.

*** Of course, if you do expose the MAC key through one side-channel attack, then you might be able to do something more sophisticated against the encryption algorithm. But my head is already hurting too much.

**** Technically, checking GHASH also requires you to encipher the 0 message under the cipher key, but that can be done beforehand. It doesn’t need to happen each time you decrypt.

Luther Martin has a post on the difference between academic andcommercial cryptographers. You should read the whole thing, but I wanted to add my $.02 on this part:

I don’t have any firsthand experience with this, but I’ve heard stories of how people in the academic world who try to approach cryptography from the point of view of commercial cryptographers also encounter problems. The places where they work typically put more value on inventing new things, so practical implementations are often considered not as good as less practical, yet new, inventions.

I do have some firsthand experience with this. And Luther’s basically right.

I’m fortunate to have a foot in both the commercial and academic worlds. On the one hand, this means that I get to spend my days working with real products, which is fascinating because, well, it’s fascinating. And it’s relevant.

Unfortunately, from a technological point of view, commercial crypto doesn’t exactly set the world on fire. Once in a while you get to work with a company which is doing something interesting, like Voltage or PGP. But for the most part you’re playing with the same basic set of tools.

Therefore, when I have a chance to do research, I tend to gravitate to the purely academic. This includes protocols that enhance user privacy — stuff like this.

I will cheerfully admit that there’s about a 1% chance that any of my academic work will be deployed in this decade. And I’m ok with that! I enjoy solving problems, and I like that in crypto research, at least, we’re not slaves to the immediate practical.

But maybe as academics, we take this too far.

I advise some grad students, and one of my sad duties is to inculcate them with this understanding: you can do whatever you want in your career, but if you want to get published, the absolute worst thing is be too practical. Don’t kill yourself implementing some cryptosystem that’s practical and deployable, unless there’s something extremely sexy and new in it. And if that’s the case, try not to waste all that time implementing it in the first place! The reviewers (mostly) don’t care.

This is problematic, since in my opinion there’s a huge gap between commercial work and academic crypto. This includes a big category of technologies that we need in order to make (secure) crypto easier to deploy. But none of the incentives are there to support this kind of research.

Despite this, I’m trying to shift some of my work in that direction. This means a whole lot of time-consuming work writing tools like this one. Building this kind of tool is a pre-requisite to doing real research. Unfortunately it requires a lot of scut work, and that’s not going to get anyone a ton of sexy research publications. Still someone needs to do it.

I’m not really sure what to do about this, and I sure hope it changes at some point.

Random thought of the day, apropos of this comment by Jon Callas:

We know that the attack against EMC/RSA and SecureID was done with a vuln in a Flash attachment embedded in an Excel spreadsheet. According to the best news I have heard, the Patient Zero of that attack had had the infected file identified as bad! They pulled it out of the spam folder and opened it anyway. That attack happened because of a security failure on the device that sits between the keyboard and chair, not for any technology of any sort.