Month: December 2011

2011 Redux

I started this blog just a few months ago and it’s been something of a learning experience. Someday maybe I’ll talk about that, but not in this post. What I’m here to talk about is regret — regret that there are so many things I missed the opportunity to blog about in 2011.

Since I’m finally done traveling and the alternative is to actually be productive, I thought this might be a good opportunity to make up for some of that lost blogging ground. Hence this post: my attempt to sum up what’s happened in practical cryptography in 2011.

Before anyone objects, I’m going to clarify the ground rules. This list is naturally incomplete, and moreover, I’m going to take ‘practical‘ seriously. That rules out reduced-round attacks (on anything); improvements in Fully-Homomorphic Encryption (getting faster!); and any paper with ‘composable’ in the title. I will cover implementation and usability issues. But I don’t really plan to take any of my own rules that seriously. If you think I missed something important, please feel free to follow up in comments.

Phishers don’t mess with the
imaginary SecurID key storage facility.
  1. SecurID not so secure after all. RSA’s SecurID has become practically synonymous with two-factor authentication. And it’s not a bad system. Back in 2010 if you’d asked me about the most likely avenue for a compromise, I would have guessed (a) theft of secrets from a local SecurID server, or (b) some kind of bug in the authentication software.What I wouldn’t have guessed was (c) compromise of RSA’s master seed data. Obviously that wasn’t going to happen — given the sensitivity of this information, RSA naturally took good care of it. Remember the underground research facility in Resident Evil? My vision of the RSA master seed storage facility was kind of like that, only without the friendly computer or Milla Jovovich.

    In retrospect this seems a bit naive, but really: SecurID was everywhere. Even military contractors used it. If local banks had learned to store their secrets in hardware security modules, then certainly RSA would take modest precautions with something as important as their master seed database.

    What 2011 taught us is that just because you think something will be done a certain way, it won’t necessarily be so. Perhaps 2012 will be different.

  2. Still more attacks on AES. I promised to keep this to the practical, and the latest attacks against AES certainly aren’t. The best of them still only shave a couple of bits off of the security of an AES key (although the new attacks don’t depend on related keys).Still, AES is such an important cipher that any reduction in its security margin is going to have some kind of practical impact. The question now is what lies down the road: (a) an improved AES beefed up with additional rounds, (b) a new standards competition, (c) apathy, or (d) something even weirder. Maybe 2012 will put us on a path to finding that answer.
  3. D-Wave actually builds a quantum computer. With two caveats: it’s not really a computer, and it may or may not be quantum.In case you’ve never heard of D-Wave, they’re a private company that purports to sell the first working adiabatic quantum computer, complete with “128 pair-wise coupled superconducting flux qubits”. If you’re not sure what to make of this, you’re not the only one. Thanks to D-Wave’s NDA-heavy business model, there’s been some doubt in learned quarters as to whether the D-Wave device actually performs useful quantum computation at all.

    But D-Wave has an active and respectable research department. Just this past May they published an article in Nature demonstrating apparent quantum tunneling amongst eight qubits. This is a far cry from the 128 qubits claimed in their commercial products, it doesn’t demonstrate entanglement, and of course, it doesn’t result in computation. Still it’s not nothing. So does this mean practical implementations of Shor’s algorithm are just around corner? Probably not.
     

  4. TLS falls to the BEAST. This fall Thai Duong and Juliano Rizzo raised the pulse of the security industry by demonstrating the most exciting practical attack against SSL/TLS in years. This attack is dear to my heart because it’s one of the first attacks I wrote about on this blog.BEAST is based on a five year-old academic attack on a twelve year old standard. Now there’s a bit more to the attack that Rizzo/Duong implemented, but still — how in the world does such a thing stay in the wild so long? A colleague describes Rizzo/Duong’s research strategy as ‘working their way through the Eurocrypt archives, actually exploiting the theoretical vulnerabilities that academics couldn’t be bothered to follow through on’. If this sounds dismissive, it wasn’t — he only wished that he’d done it first.

    Lesson: there’s a hell of a gap between academic crypto and ‘the real world’. We’re only safe as long as you believe in attackers who are sophisticated enough to spear-phish SecurID, but not bright enough to read a crypto paper. Time will tell if that belief is a good one.

  5. Nothing much happens with hash functions. Well, that’s a bit unfair. Things did happen, and there are some papers to show for it. The SHA3 finalists, announced late last year, continued to percolate through the system. (Go BLAKE!) Still, 2011 was a huge disappointment for those of us you who thought that it would be the year of SHA1 collisions. I guess there’s always 2012.
  6. Unsigned code running on iOS. Many cryptographers would exclude this from a list of ‘crypto’ happenings. Still, a theme of this blog is that your crypto doesn’t matter if your implementation undermines it.This is exactly what Charlie Miller demonstrated when he showed how to execute malicious application code on an iPhone. Even though iOS devices are only supposed to run signed code, it turns out that a few bad checks created a tiny section of memory in which these requirements were irrelevant. To thank him, Apple created a tiny section of their developer program in which Charlie Miller is irrelevant.
  7. Certificate Authorities still a giant mess. Some will say I’m exaggerating — there were only a few major hacks this year, notably Dutch CA DigiNotar, and a smaller CA called Gemnet. But don’t forget, Microsoft also revoked Digicert Malaysia — not because they were hacked, but for using 512-bit RSA keys to sign certificates (!!) And this is only a partial list of the problems we know about. All in all, it was not a good year to be a CA.
  8. Secure police radios not all that secure. APCO Project 25 is a digital radio standard used by law enforcement. Naturally it supports encryption — a valuable tool when you’re discussing a confidential source or razzing those Occupy protestors. And the P25 encryption itself isn’t half bad (it’s unauthenticated AES). Rather, the problem with P25 is that simply getting encryption turned on is a daunting prospect — to the point where it often doesn’t happen.
     
    To illustrate the problem, a team from UPenn spent two years snarfing up confidential traffic. The agents generating most of this traffic either thought it was encrypted, or would have encrypted it if only they could’ve figured out how to set the keys. Still more evidence that usability is every bit as important as crypto, implementation, or any other issue that we come across in our field.
  9. XML Encryption nearly as awful as XML itself. This fall brought news of a clever attack on the unauthenticated W3C XML Encryption standard. The attack, by researchers Tibor Jager and Juraj Somorovsky, used various features of XML encoding to implement what I would call a ‘padding oracle attack-plus-plus’ — which completely decrypts protected XML on Axis2 and JBoss systems.The W3C response: “We are so sorry for promulgating this terrible standard and recommend that you never, ever listen to anything we say regarding security every again.” No, of course I’m just kidding. Actually, they’re adding AES-GCM as an option. Should take care of everything.
  10. Quantum key distribution still a work in progress. Quantum Key Distribution (QKD), sometimes known as ‘quantum crypto’ is a promising technique for distributing keys over geographic distances without the need to rely on complicated stuff like hard mathematical problems. Instead, you just need to run direct fiber-optic cables to the person you want to communicate with (much easier). On the bright side, the security of QKD is supposedly based on fundamental quantum-physical properties.In general, the caveat in any QKD design is that security only holds if the physical device works as expected. This year researchers from Singapore and Norway showed that this is a big assumption: by exploiting certain limitations of existing detector equipment, they were able to extract an entire secret key without anyone being the wiser. None of these attacks are fundamental ‘breaks’ of QKD, and indeed they’ve already been mitigated. But it goes to show how you should never trust a system just because someone tells you it’s ‘theoretically unbreakable’.
And that’s 2011. I’m sure I’m missing tons of important stuff — and that’s what comments are for. Please enjoy the rest of your holidays and be safe in the new year.

What’s TLS Snap Start?

Google is promoting a new TLS extension which is designed to speedsugar-snap-peas up the negotiation of TLS handshakes. The extension is called called Snap Start, and it’s already been deployed in Chrome (and presumably throughout Google’s back end.)

So what is Snap Start, why is it different/better than simply resuming a TLS session, and most importantly: how snappy is it?

Background: The TLS Handshake

To understand Snap Start we need to quickly review the TLS handshake. Snap Start only supports the classic (non-ephemeral) handshake protocol, so that’s what we’ll be talking about here. Leaving out a lot of detail, that handshake can be reduced to the following four messages:

  1. C -> S: Client sends a random nonce CR.
  2. C <- S: Server responds with its public key (certificate) and another nonce SR.
  3. C -> S: Client generates a pre-master secret PMS, encrypts it with the server’s public key and sends the ciphertext to the server.
  4. C <- S: The client and server both derive a ‘master secret’ by hashing* together (CR, SR, PMS). The server and client also MAC all previous handshake messages to make sure nothing’s been tampered with. Finally the server notifies the client that it’s ready to communicate.

I’m ignoring many, many important details here. These include ciphersuite negotiation, parameter data, and — most importantly — client authentication, which we’ll come back to later. But these four messages are what we need to think about right now.

So why Snap Start?

It only takes a glance at the above protocol to identify the problem with the classic handshake: it’s frickin’ slow. Every new TLS connection requires two latency-inducing round-trips. This can be a drag when you’re trying to deploy TLS everywhere.

Now technically you don’t need to run the whole handshake each time you connect. Once you’ve established a TLS session you can resume it anytime you want — provided that both client and server retain the master secret.** Session resumption reduces communication overhead, but it isn’t the answer to everything. Most people will balk at the idea of hanging onto secret keys across machine reboots, or even browser restarts. Moreover, it’s not clear that a busy server can afford to securely cache the millions of keys it establishes every day.

What’s needed is a speedy handshake protocol that doesn’t rely on caching secret information. And that’s where Snap Start comes in.

The intuition behind Snap Start is simple: if TLS requires too many communication rounds, then why not ditch some. In this case, the target for ditching is the server’s message in step (2). Of course, once you’ve done that you may as well roll steps (1) and (3) into one mutant mega-step. This cuts the number of handshake messages in half.

There are two wrinkles with this approach — one obvious and one subtle. The obvious one is that step (2) delivers the server’s certificate. Without this certificate, the client can’t complete the rest of the protocol. Fortunately server certificates don’t change that often, so the client can simply cache one after the first time it completes the full handshake.***

Replays

The subtle issue has to do with the reason those nonces are there in the first place. From a security perspective, they’re designed to prevent replay attacks. Basically, this is a situation where an attacker retransmits captured data from one TLS session back to a server in the hopes that the server will accept it as fresh. Even if the data is stale, there are various scenarios in which replaying it could be useful.

Normally replays are prevented because the server picks a distinct (random) nonce SR in step (2), which has implications throughout the rest of the handshake. But since we no longer have a step (2), a different approach is required. Snap Start’s solution is simple: let the client propose the nonce SR, and just have the server make sure that value hasn’t been used before.

Obviously this requires the server to keep a list of previously-used SR values (called a ‘strike list’), which — assuming a busy server — could get out of control pretty fast.

The final Snap Start optimization is to tie proposed SR values with time periods. If the client suggests an SR that’s too old, reject it. This means that the server only has to keep a relatively short strike list relating to the last few minutes or hours. There are other optimizations to deal with cases where multiple servers share the same certificate, but it’s not all that interesting.

So here’s the final protocol:

  1. The client generates a random nonce CR and a proposed nonce SR. It also generates a pre-master secret PMS, encrypts it with the server’s public key and sends the ciphertext and nonces to the server.
  2. The server checks that SR hasn’t been used before/recently. Both the client and server both derive a ‘master secret’ by hashing* together (CR, SR, PMS). The server notifies the client that it’s ready to communicate.

The best part is that if anything goes wrong, the server can always force the client to engage in a normal TLS handshake.

Now for the terrible flaw in Snap Start 

No, I’m just kidding. There doesn’t seem to be anything wrong with Snap Start. With caveats. It requires some vaguely synchronized clocks. Moreover, it’s quite possible that a strike list could get wiped out in a server crash, which would open the server up to limited replays (a careful implementation could probably avoid this). Also, servers that share a single certificate could wind up vulnerable to cross-replays if their administrator forgets to configure them correctly.

One last thing I didn’t mention is that Snap Start tries to use as much of the existing TLS machinery as possible. So even though the original step (2) (‘Server Hello’ message) no longer exists, it’s ‘virtually’ recreated for the purposes of computing the TLS Finished hash check, which hashes over all preceding handshake messages. Ditto for client authentication signatures. Some new Snap-specific fields are also left out of these hashes.

As a consequence, I suppose there’s a hypothetical worry that an attack on Snap Start (due to a bad server implementation, for example) could be leveraged into an attack that works even when the client requests a normal TLS handshake. The basic idea would be to set up a man-in-the-middle that converts the client’s standard TLS handshake request into a Snap Start request, and feeds convincing lies back to the client. I’m fairly certain that the hash checks and extra Snap Start messages will prevent this attack, but I’m not 100% sure from reading the spec.

Beyond that, all of this extra logic opens the door for implementation errors and added complexity. I haven’t looked at any server-side implementations, but I would definitely like to. Nonetheless, for the moment Snap Start seems like a darned good idea. I hope it means a lot more TLS in 2012.

Notes:

* Technically this is a denoted as a PRF, but it’s typically implemented using hash functions.

** At session resumption the master secret is ‘updated’ by combining it with new client and server randomness.

*** Certificate revocation is still an issue, so Snap Start also requires caching of ‘stapled’ OCSP messages. These are valid for a week.

A brief note on end-of-year giving

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.

A question for you

This post is addressed to you, my patient and wonderful audience.

I realize that my interests may not be entirely representative of yours. So what would you like to read about? I don’t guarantee that I’ll write on any of your suggestions, but I do promise to at least think about the topics you propose.

Feel free to make your suggestions in comments or Twitter. If you don’t, be warned: you’ll be as much to blame for that future post on Leakage Resilient Cryptography as I will.

What’s the deal with RC4?

Jacob Appelbaum tweets:RC4

Does anyone have a good reading list on practically attacking RC4?

I don’t intend to give an exact answer to Jacob’s question here, but his tweet caught my eye for a reason. You see, just the other week I advised implementers to avoid RC4 — both because it’s easy to misuse, and because it’s has some real and theoretical flaws. But that doesn’t mean any particular RC4 implementation is broken.

Instead, you should take my advice as the crypto equivalent of “don’t run with scissors”, “don’t run near the pool”, or “don’t run near the pool while carrying scissors”. I don’t know anyone who’s actually lost an eye because they ignored these warnings, but I still yell this stuff at my kids. It’s common sense.

Still, this leaves us with a question: how bad is RC4, really?

RC4, the stream cipher for the rest of us

First, the basics. RC4 was invented in 1987 by Ron Rivest. It spent its first seven years as an RSA trade secret before it was eventually leaked to a public mailing list in 1994. The rest, as they say, is history.

You could argue that RC4’s rise was inevitable. By the time of its leak, it was already in widespread commercial use. Unlike DES it was fast in software.* More importantly, the scheme itself is dirt simple. You can fit the code for RC4 onto a cocktail napkin, with plenty of room left over for the cocktail. And of course, having become public, the ‘alleged’ RC4 was free.

One phase of the RC4 PRG. K is the
output byte. Image: Wikipedia.

The scheme consists of two parts: a key scheduling algorithm (KSA), and a pseudo-random generator (PRG). To encrypt a message, you run the key through the key scheduler, which produces a scrambled array called the state vector. You then feed the state vector into the PRG, which continuously permutes it while outputting a series of bytes. You then XOR those ‘keystream’ bytes with your plaintext.

RC4 is probably most famous for its (mis)use in 802.11 WEP. It’s still used in WPA-TKIP (unsurprising, since TKIP is just a bandaid patch for WEP). But its use goes way beyond that. For one thing, it’s a common ciphersuite for TLS, and as of a year or two ago it was even preferred by browsers like Chrome. Up until recently, Microsoft used it everywhere. Skype uses it to obfuscate (though not to encrypt) its communication protocol. It shows up in malware and a zillion crappy DRM packages.

To make a long story short, you’ll usually find RC4 anywhere the hardware was too weak, or the developers too lazy to use a better cipher.

The plain stupid

There are a few basic things you need to avoid when using any PRG-based cipher. These aren’t specific to RC4, but for some reason they seem to crop up at a higher rate in RC4 implementations than with other ciphers.

The big honking obvious one is that you can’t re-use the same RC4 keystream to encrypt two different messages. I hope I don’t need to go into the consequences, but they’re bad. Don’t do it.

You’d think this is so obvious that nobody could get it wrong, but that’s exactly what Microsoft famously did back in 2005, encrypting different versions of a Word document with the same key. If you must use the same key for different messages, the solution is to combine the key with an Initialization Vector or ‘nonce’. Unfortunately this can be problematic as well.

Another big issue is ciphertext malleability. If you flip a bit in an RC4 ciphertext, you’ll see the same bit flipped in the decrypted plaintext. This is awesome at parties. More to the point, it can lead to practical padding-oracle type attacks that totally compromise the security of your encryption.**

The solution to the latter problem is simply to MAC your ciphertexts. Unfortunately, people don’t use RC4 because they know what a MAC is — they use RC4 because you can download the code from Wikipedia. So, again, while this can happen with many ciphers, it tends to happen with RC4 a lot more than it should.

Key Scheduling

Leaving aside the stupid, the real problem with RC4 is the Key Scheduling Algorithm (KSA), which kind of sucks.

Picture a brand new box of playing cards. Starting with the unshuffled deck, work systematically from top to bottom, swapping each card’s position with another card in the deck. The position you’re swapping to is determined by a few simple computations involving the original card’s face value and the cryptographic key. Now do this with a stack of about five ordered decks and you’ve got the RC4 KSA.

While this shuffle seems thorough, the devil is in those simple computations. Ultimately their simplicity means the shuffle isn’t unpredictable enough. This leads to predictable patterns that show up in the first PRG output bytes. For example, Mantin and Shamir noted that the second output byte takes on the value ‘0’ with about twice the probability it should. By itself that may not seem terribly useful, but for one thing: it’s enough to practically determine whether an unknown algorithm is RC4, given about 128 keystreams on different (random) keys.

From what I can tell, the first person to notice problems with KSA was Andrew Roos, who posted a paper to sci.crypt about a year after the leak. Aside from the fact that it was published on Usenet, Roos’s result is notable for two reasons. First, he correctly identified use of concatenated IVs as a likely source of weakness in WEP implementations — years before anyone else did. Second, Roos gave recommendations that — had they been followed — could have prevented a lot of subsequent heartache. (Lesson: don’t publish scientific results in newsgroups.)

FMS

Roos’s paper set the table for the most famous attack on RC4, and the one that people still associate with RC4, even though it’s rarely used in its original form. This is, of course, the Fluhrer, Mantin and Shamir, or ‘FMS’ attack, which appeared in 2001.

Just like Roos, FMS looked at the KSA and found it wanting — specifically, they discovered that for certain weak keys, the first byte output by the PRG tends to be correlated to bytes of the key. These weak keys can be obtained by prepending a few chosen bytes (say, 3 of them) to an unknown, fixed, secret key. Given keystreams resulting from 60 such chosen keys, you can derive one byte of the secret portion of the key. A 16-byte key can therefore be computed from about 960 such keystreams.

On the face of it this sounds pretty unlikely — after all, how are you going to get an encryptor to prepend chosen bytes to their secret key. Fortunately the attack works fine even if the adversary just knows that the appropriate bytes were used. This works perfectly for implementations that prepend (or append) a known Initialization Vector to the WEP key. Simply by observing a few million IVs, an attacker can eventually collect enough keystreams to meet the FMS requirements.

All of this would have be a historical footnote if it hadn’t been for protocols like WEP, which (among its many problems) used a three-byte prepended IV. FMS was quickly demonstrated to work on WEP, then packaged into a neat tool and distributed.

Klein, Dropping and Hashing

There are two common approaches to dealing with the FMS attack:

  1. Drop the first N bytes of the RC4 keystream, for values of N ranging from 256 to 3,072.
  2. Don’t concatenate the IV to the key, hash the two together instead.

The first option is sometimes referred to as RC4-drop[N], and the actual value of N has been subject to some debate. In 2006, Klein presented a super-charged variant of the FMS attack that reduced the necessary number of IVs from millions down to about 25,000. More importantly, he showed that FMS-type attacks are still (borderline) viable even if you drop the first 256 bytes of the keystream. So 768 seems like a bare minimum to me, and some people will argue for much larger values.

The second approach was adopted for WPA-TKIP, which was proposed as a band-aid replacement for WEP. TKIP was designed to support legacy WEP-capable devices that had internal RC4 hardware, but weren’t powerful enough to handle AES. It made a bunch of positive changes to WEP (including adding a larger IV to prevent keystream reuse), but the most notable change was a new custom hash function that creates a per-packet key from an IV and secret key.

As a hash function, the TKIP hash kind of stinks. For one thing, it can be inverted given only about 10 per-packet keys and about 2^32 computation (these days, a few minutes on a TI calculator). However, this isn’t as big of a deal as it sounds: pre-image resistance isn’t precisely a goal of the TKIP hash, since those per-packet keys themselves should themselves be hard to obtain. Nonetheless, I wouldn’t recommend that you mess around with it. If you must use RC4, try a proper hash function. Or better yet, don’t use RC4 at all.

Distinguishers

 Last but not least: RC4 is just a PRG, and a PRG is secure if its output is indistinguishable from a stream of truly random bits — to a ‘reasonable’ adversary who doesn’t know the key.*** Hence a great deal of RC4 research focuses on the quality of the cipher’s PRG.

So is RC4 a good pseudo-random generator? Meh. Given a mere 1.5GB of keystream data, Fluhrer and McGrew presented an algorithm that distinguishes RC4 from random. I already mentioned Mantin and Shamir who cranked this down to about 256 bytes (over various unknown, unrelated keys) by looking at the second output byte. Finally, Mantin noticed the presence of repeating patterns in RC4, which aren’t simply dependent on the first few bytes of output, and can be used to distinguish RC4 given about 64MB of keystream.

There are, of course, other distinguishing attacks. But does it matter?

Well, sort of. Indistinguishability is a critical characteristic of an XOR-based stream cipher. If we have it, then the security argument for RC4 encryption is very simple: to an adversary who can’t distinguish the PRG, RC4 encryption is indistinguishable from using a one-time pad.

Unfortunately the converse isn’t true. Just because RC4 output is distinguishable from random doesn’t mean that there’s a practical attack on the cipher. These results are important mostly because they illustrate the fundamental wonkiness of RC4, wonkiness that doesn’t go away just because you drop the first 3,072 bytes. But they don’t exactly give us a practical opening into the cipher itself. Yet.

Ok, none of this was very helpful. I just want to know: can I use RC4?

Great question.

The upshot is that RC4, if used as recommended (with hashed IVs and/or dropped output and MACs), is perfectly sufficient for securely encrypting messages. Today. The problem is, we never know what the future will bring.

My advice? Don’t run with scissors. You can lose an eye that way.

Notes:

* My totally unscientific results, from running ‘openssl speed’ on a lightly loaded Macbook Pro: 3DES-EDE: 21 bytes/μsec. DES: 54 bytes/μsec. AES-128: 118 bytes/μsec. RC4: 248 bytes/μsec.

** You might argue that RC4 implementations shouldn’t use padding in the first place, since (unlike CBC mode encryption with a block cipher) messages don’t need to be padded to a multiple of a block size. This is true — however, I would note that ‘padding oracle’-style attacks needn’t rely specifically on padding. Padding is just one type of encoding that can leak useful information if used incorrectly. For a great example, see Jager and Somorovsky’s recent result that uses UTF8 coding checks to defeat XML encryption.

*** By reasonable, of course, we mean ‘computationally limited’. This rules out attacks that require an unrealistically long time, quantum computing, or ESP.

Programming note

I realize that posts have been a bit light on this blog over the past couple of weeks. I’ve been a bit preoccupied recently, but this will soon change. I’m also aware that I have a few outstanding unfinished threads, and I certainly haven’t forgotten them. If you have no idea what I’m talking about, that’s great! See:

Stay tuned. There will be content.

Liveblogging WWII: December 12, 1941

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

Is there an Enigma bubble?

First it was .com stocks, then it was housing. Now it’s WWII-era German Enigma machines. From a recent CNN story:

An Enigma machine which featured in a Hollywood movie about the codebreakers of World War II has smashed auction estimates and sold for a world record price. 

The encoding device sparked a three-way bidding war when it went under the hammer at Christie’s in London Thursday, selling for £133,250 ($208,137) — more than double the upper estimate of £50,000. 

Christie’s said the previous record for an Enigma machine was £67,250, at the same auction house, in November 2010.

I for one would love to own an Enigma. But unless it’ll lead me to a cache of buried Nazi gold I have to draw the line at $100,000. It’s not like the Enigma algorithm is getting better.

But lack of funding doesn’t mean you shouldn’t be creative.

When I worked at AT&T I was told an (apocryphal?) story about a noted cryptographer who couldn’t afford to purchase an Enigma for himself, so he set out instead to blackmail one out of the NSA. Allegedly it took him only four conference submissions before they gave in. The last paper described how to attack a significant cryptosystem with paper and pencil.

This sounds so improbable that I can’t believe it really happened — which means that it probably did. If anyone knows the story and has a source for it, please drop me a line.

Matt Green smackdown watch (Are AEAD modes more vulnerable to side-channel attacks?)

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:

  • GCM mode: at very minimum, the decryptor will encipher the supplied IV. Technically, this is the only encipherment that needs to happen in order to check that the authentication tag is valid.**** If it’s not valid, GCM decryption can reject the ciphertext before going further.

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.