Author: Matthew Green

I'm a cryptographer and professor at Johns Hopkins University. I've designed and analyzed cryptographic systems used in wireless networks, payment systems and digital content protection platforms. In my research I look at the various ways cryptography can be used to promote user privacy.

How (not) to use symmetric encryption

This is supposed to be a blog about cryptographic engineering. brass_key_corkscrew12That means crypto, but it also means software engineering, protocol design, HCI and hardware engineering (fair warning: my hardware experience mostly consists of solder burns).

And yet, in describing the attacks of the past few weeks, I’ve mostly been talking about basic symmetric encryption. This seems to be an area that people get wrong, no matter how straightforward it sounds.

So at the risk of boring my readership to tears — I’m going to spend the next two posts talking about the dos and don’ts of symmetric encryption, particularly symmetric encryption with block ciphers. I may also branch out a little into key derivation and management, but I know you’ll be understanding.

I realize that for some of you this may not make for scintillating reading, but here’s my thinking: we do it once now, we’ll never have to discuss it again. Right?

Excellent. In this first post I’m going to start with the don’ts.

Symmetric Encryption Don’t #1: Don’t encrypt with ECB mode

Block ciphers are designed to process discrete chunks of data. For example, AES works on 128-bit blocks. To encrypt longer messages with them, we use one of several “modes of operation“. These modes are not all created equal.

 Tux image: Larry Ewing. (I will not
thank the GIMP, no matter what
his license says.)

ECB (Electronic Codebook) mode is by far the stupidest. Essentially you’re just chopping the message up into blocks, then using the raw block cipher to encipher each block individually. There are two problems with ECB mode:

  1. It’s not randomized. This means that anytime you encrypt a given message under a key, you’ll get exactly the same ciphertext. This goes for substrings of the message as well.
  2. It treats each block of the message independently. As a result, some of the structure of the message can leak through. This includes things like padding, which will produce predictable patterns in the ciphertext.

The first point can be a problem in some circumstances. Imagine, for example, that you’re sending a relatively small number of messages (e.g., commands for a remote system). Every time you send a given command, you’re sending exactly the same ciphertext. This gets obvious pretty fast.

I would say that the second problem is the more serious one. Perhaps you’ve seen Wikipedia’s classic image of an ECB-mode encrypted TIFF file (right). But probably this seemed a little contrived to you — after all, who uses TIFF files anymore?

So allow me to give my favorite example of why ECB mode is problematic. This image comes from a software packaging system that used ECB mode to encrypt executable files. All I’ve done is open one of those encrypted files as a raw bitmap image. You’ll have to squint a little.

An executable file encrypted using ECB mode. Click to see a larger version.

This doesn’t give away the contents of the executable, but it gives a pretty good picture of where different segments are. Just look for the funny patterns and tire tracks. Just having this little bit of information might give you a nice head start on finding those segments when they’re in memory, which is potentially what you’re going to do next.

Symmetric Encryption Don’t #2: Don’t re-use your IVs

Every block cipher mode of operation except for ECB (which you shouldn’t use!) employs a special per-message nonce called an Initialization Vector, or IV. The basic purpose of an IV is to ensure that the encryption function works differently every time; it adds an element of randomness, or at least unpredictability to your ciphertexts.

Unfortunately, developers seem genuinely stumped by IVs. Maybe this isn’t their fault. Every mode of operation has slightly different rules about how to pick IVs, and a slightly different set of consequences for when you screw it up.

So let’s start with something simple. No matter what mode you use, this kind of thing is never ok:

This chunk of bad advice comes from an ancient (and hopefully obsolete) version of the AACS specification. But it’s hardly the exception. Grep for “IV” in the source repositories of just about any major software house, and I guarantee you’ll find plenty of stuff like this.

Why is this a problem? Let me count the ways:

  1. At a minimum, it eliminates any random behavior in the encryption scheme. With a fixed IV, a given message will always encrypt to the same ciphertext (if you’re using the same key). This goes for two messages that are the same up to a certain point. See my discussion of ECB mode above for why this can be a problem.
  2. If you’re using a stream cipher mode of operation like CTR or OFB, it’s a disaster. If you encrypt two different messages with the same key, and the IV is fixed, then an attacker can XOR two ciphertexts together. This will give them the XOR of the two underlying plaintexts. (Think this will be useless? I doubt it, especially if they’re clever.)

    By the way, this kind of thing also happens when people forget to change the IV when encrypting multiple versions of a file. Don’t do that either.

  3. If you’re using a chaining mode like CBC, use of a fixed IV can still lead to plaintext recovery. See, for example, this chosen plaintext attack on TLS, which only requires the adversary know which IV is being used. This type of attack is pretty tricky to implement, but it’s definitely possible.
  4. It will make you look stupid and embarrass you when a professional audits your code.

Clearly some of these issues are application-specific. Maybe you don’t think anyone will be able to leverage them. You might even be right — in this version of the application. But sooner or later, you or a future developer will bolt on new features, deploy it in the cloud, or make it into a browser applet. When they do, all of these issues will magically go from theoretically vulnerable to stupidly vulnerable.

And people will blame you.

So how do you use IVs correctly? I’ll talk about this more in my next post. But if you’re really chomping at the bit, my advice is to take a look at the FIPS specification for block cipher modes. (I must warn you, however: please don’t operate heavy machinery while reading these documents.)

Symmetric Encryption Don’t #3: Don’t encrypt your IVs

So you’ve generated your IV correctly, you’ve used it correctly, but now you’re hung up on a final question: what do I do with this darn thing?As I’ve said, IVs make people nervous. People know they’re not keys, but they’re not ciphertexts either. They wonder: is this an important value? Should I just send it over the wire as it is? Hmm, just to be safe, I’d better encrypt it. Even if I’m wrong, it can’t hurt.

As this Reddit commenter can attest, what you don’t know can hurt you.

Here’s a simple rule of thumb. IVs are not keys. They’re not secret. If you’ve chosen the IV correctly, you can send it along with your ciphertext in the clear. You should authenticate it (see below), but you should never encrypt it.

The worst thing you can do is encrypt your IVs using the same key that you’re using to encrypt messages. The absolute worst example is when you’re using CTR mode encryption, and you make the mistake of encrypting your IV using ECB mode. When you do this, anyone can XOR the first block of ciphertext with the encrypted IV, and obtain the plaintext of that block.

These problems aren’t limited to CTR. My advice: have faith in your IVs, and they’ll have faith in you.

Symmetric Encryption Don’t #4: Don’t forget to authenticate your ciphertexts

Once upon a time cryptographers looked at encryption and authentication as two unrelated operations. Encryption was for protecting the confidentiality of your data, and authentication was used to keep people from tampering with it.*

Nowadays we know that the two are much more tightly linked. You may not care about people tampering with your data, but your encryption scheme just well might. The problem is active attacks. See here and here for just a couple of examples.

To make a long story short, many of the clever attacks on symmetric encryption schemes these days require an attacker to tamper with ciphertexts, then submit them to be decrypted. Even if the decryptor leaks just a tiny bit of information (e.g., is the padding correctly formatted, is the message properly formatted), that can be enough to gradually peel away the encryption and recover the plaintext.

Obviously you don’t want this.

The very elegant solution is to authenticate your ciphertexts, and not just in any willy-nilly fashion. There are basically two approaches that won’t lead to heartburn down the road:

  1. Best: use an authenticated mode of operation, such as GCM, CCM, OCB or EAX. These modes handle encryption and authentication in one go (and they can even authenticate some optional unencrypted ‘associated’ data for you). Best yet, they use a single key.
  2. Almost as good: first encrypt your message using a secure mode of operation (say, CTR), then compute a Message Authentication Code (e.g., HMAC-SHA1) on the resulting ciphertext and its IV. Use two totally different keys to do this. And please, don’t forget to MAC the darn IV!

What you should not do is apply the MAC to the plaintext. First of all, this won’t necessarily prevent active attacks. Padding oracle attacks, for example, can still be leveraged against a scheme that authenticates the message (but not the padding). Furthermore, even if you MAC the padding, there’s still a slim possibility of timing attacks against your implementation.

Symmetric Encryption Don’t #5: Don’t CBC-encrypt in real time

Let me use this space to reiterate that there’s nothing wrong with CBC mode, provided that you use it correctly. The unfortunate thing about CBC mode is that there are many ways to use it incorrectly.

Knowing this, you shouldn’t be surprised to hear that CBC is the most popular mode of operation.

This ‘don’t’ is really a variant of point #2 above. CBC mode can be insecure when an attacker has the ability to submit chosen plaintexts to be encrypted, and if the encryption is on a live stream of data where the adversary can see the ciphertext blocks immediately after they come out (this is called ‘online’ encryption). This is because the adversary may learn the encryption of the previous plaintext block he submitted, which can allow him to craft the next plaintext block in a useful way.

If he can do this, he might be able to take some other ciphertext that he’s intercepted, maul it, and feed it through the encryptor. This kind of attack is challenging, but given the right circumstances it’s possible to decrypt the original message. This attack is called a blockwise chosen plaintext attack, and it’s essentially what the BEAST attack does.

Symmetric Encryption Don’t #6: Don’t share a single key across many devices

A wise man once said that a secret is something you tell one other person. I’m not sure he realized it, but what he was saying is this: don’t put the same symmetric key into a large number of devices (or software instances, etc.) if you want it to remain secret.

About the fastest way to lose security in a system is to spread a single key broadly and widely. It doesn’t matter if you’ve embedded that key inside of a tamper-resistant chip, buried in a block of solid concrete, and/or placed it in a locked file cabinet with a sign saying ‘beware of leopard‘.

The probability of your system being compromised goes up exponentially with each additional copy of that key. If you’re doing this in your current design, think hard about not doing it.

Symmetric Encryption Don’t #7: Don’t pluralize your keys using XOR

(credit)

This one is really a flavor of #5, but a more subtle and stupid one.

Key ‘pluralization’ refers to a process where you obtain multiple distinct keys from a single master key, or ‘seed’. Usually this is done using some strong cryptographic function, for example, a pseudo-random function.

This happens all over the place. For example: TLS does it to derive separate MAC and encryption keys from a master secret. But an extreme type of pluralization often occurs in large-scale systems that provide unique keys to a large number of users.

Think of a cellular provider distributing SIM cards, for example. A provider could generate millions of random authentication keys, distribute them to individual SIM cards, and then store the whole package in a back-end database. This works fine, but they’d have to store this database and do a lookup everytime someone contacts them to authorize a phone call.

Alternatively, they could start with one short master seed, then pluralize to derive each of the SIM keys on demand. This process would take as input the seed plus some auxiliary value (like the subscriber ID), and would output a key for that user. The advantage is that you no longer need to keep a huge database around — just the tiny initial seed.

This approach is so tempting that sometimes people forget about the ‘strong cryptographic function’ part, and they derive their keys using tools that aren’t so secure. For example, they might just XOR the master seed with the subscriber or device ID.

No, you say, nobody could be that dumb. And yet KeeLoq was. Millions of cars keys were provisioned with cryptographic keys that were generated this way. It turns out that if you can extract any one of those per-car keys, and if you know the device’s serial number, you can easily recover the master key — which means you can break into any other car.

Symmetric Encryption Don’t #8: Don’t use DES or RC4 or @#(*&@!

Ok, I said this was mostly going to be about block ciphers. DES fits that category, and I hope you know why not to use it. But RC4 also deserves a special mention just for being the world’s most popular dubious stream cipher.

RC4 shows up everywhere. It shows up in products. It shows up in malware. Basically, it shows up anywhere someone needed crypto, but was too lazy to download a copy of AES. Hell, I’ve used it myself — um, for personal reasons, not for work, mind you.

If you use RC4 correctly, it’s probably ok. For now. The problem is twofold. First of all, cryptanalysts are slowly chipping away at it — sooner or later they’re going to make some serious progress.

The second problem is that it’s not always used securely. Why not? You might as well ask why meth labs explode at a disproportionate rate. My guess is that the set of people who use caution when mixing volatile chemicals simply doesn’t overlap well with the set of people who cook methamphetamine. Ditto RC4 and proper usage.

I could waste a lot of time going on about all of this, but instead I’m just going to quote Thomas Ptacek:

if you see a bespoke crypto design, and it dates from after 2000, and it uses RC4, that’s an audit flag.

Now if Thomas says this about RC4, what do you think he’s going to say about your homebrew protocol based on the Russian GOST cipher? That’s right: nothing nice. Don’t let it happen to you.

In Summary

So this is where I leave you. I doubt this list is complete — I’ll try to update it if I think of anything else. At the very least, if we could fix these issues it would knock out a healthy chunk of the silly crypto issues I see on a day to day basis.

Oh, and a pony too.

Ok, so, I’m a little skeptical that all of these problems will go away that easily, but I’d be content with even just one or two of the points. So if you’re designing a new crypto product and could spare a minute just to glance at the above, you would certainly make my day.

Notes:

* Honestly, there was even a certain amount of confusion on this point. If you look at old protocols like  Needham-Schroeder, you’ll see that they basically treat encryption as authentication. Don’t do this. Most common modes of operation are malleable, meaning that you can mess with the ciphertext, cut and paste different ones, etc.

Academic vs. commercial cryptographers

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.

Human error is something to be engineered around, not lamented

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.

Quite frankly, if this is what qualifies as human error in a security system, then we’re all in deep trouble. We’re stuck with it. We’re born to it.

I’ll assume one of two things happened here:

  1. An AV scanning system identified a known signature inside of an attachment, recognized that this could be an exploit, and responded to this very serious issue by moving the file into the SPAM folder, where it joined many other legitimate messages that were improperly marked as spam.
  2. A Spam filter noticed something funny about a header, and moved the file into the SPAM folder, something it probably does eight times per week for no reason at all.

Unless your users are superhuman, the problem here is not the user. It’s the system. If the file legitimately contained a vulnerability, it shouldn’t have been moved into the SPAM filter where it could easily be mistaken for a random false positive.

If, on the other hand, the problem was just something to do with the headers, then maybe the user was just doing what was normal — pulling a probable false positive out of their spam folder, just like they did every day.

People are not superhuman. They react to the inputs you give them: GIGO applies. If security systems give people crap inputs, then they’ll make crap decisions. Fixing this problem is our job. We don’t get to complain every time a user does something perfectly understandable in response to bad data that we (security system designers) give them.

And of course, this leaves aside the basic fact that the master seed was available to this attack in the first place, something that boggles the mind… But I guess that’s all been said.

Non-governmental crypto attacks

Over on Web 1.0, Steve Bellovin is asking an interesting question:

Does anyone know of any (verifiable) examples of non-government enemies exploiting flaws in cryptography?  I’m looking for real-world attacks on short key lengths, bad ciphers, faulty protocols, etc., by parties other than governments and militaries.  I’m not interested in academic attacks — I want to be able to give real-world advice — nor am I looking for yet another long thread on the evils and frailties of PKI.

The responses vary from the useful to the not-so-useful, occasionally punctuated by an all-out flamewar — pretty much par for the course in these things.

Here are a few of the responses that sound pretty reasonable. They’re (mostly) not mine, and I’ve tried to give credit where it’s due:

  1. Cases of breached databases where the passwords were hashed and maybe salted, but with an insufficient work factor enabling dictionary attacks.*
  2. NTLMv1/MSCHAPv1 dictionary attacks.*
  3. NTLMv2/MSCHAPv2 credentials forwarding/reflection attacks.*
  4. The fail0verflow break of poorly-nonced ECDSA as used in the Sony PlayStation 3.*
  5. DeCSS.*
  6. Various AACS reverse-engineering efforts.
  7. The HDCP master key leak.*
  8. Various attacks on pay satellite TV services.****
  9. GSM decryption, which seems to have gone beyond the academic and into commercial products.
  10. Factoring of the Texas Instruments 512-bit firmware signing key for calculators, and Elcomsoft’s factoring of the Quicken backup key.**
  11. Key recovery in WEP.
  12. Exploits on game consoles: the original XBox,*** Wii software signing.

There’s also some debate about recent claims that 512-bit RSA certificate signing keys were factored and used to sign malware. As much as I’d like to believe this, the evidence isn’t too solid. Some posters claim that there were also 1024-bit keys used in these attacks. If that’s true, it points more to key theft (aka Steve’s ‘evils and frailties of PKI’).

You’ll also notice I’m leaving lots of stuff off of this list, only because I don’t know of any specific attacks based on it. That would include all the padding oracle attacks of late, the BEAST attack on TLS, bad Debian keys, and so on.

So what’s the takeway from all of this? Well, it’s complicated. A quick glance at the list is enough to tell us that there are plenty of ‘real people’ (aka non-professional cryptographers) out there with the skills to exploit subtle crypto flaws. That definitely supports my view that proper crypto implementation is important, and that your code will be exploited if you screw it up.

Some people may take comfort from the fact that there’s no crypto ‘pearl harbor’ on this list, i.e., the cryptographic equivalent of a Conficker or Stuxnet. I would say: don’t get too cocky. Sure, software security is a mess, and it’s a whole lot easier to set up a dumb fuzzer than to implement sophisticated crypto exploits. (No offense to dumb fuzzers — I’m friends with several.)

But on the other hand, maybe this is misleading. We mostly learn about software 0days from mass malware, which is relatively easy to catch. If sophisticated crypto exploits are being implemented, I would guess that they’re not going into retail worms and trojans — they’re being very quietly applied against high-value targets. Banking systems, for example.

But again, this is just speculation. What do you think?

Notes:

* Marsh Ray.

** Solar Designer.

*** Tom Ritter.

**** commenter “Swiss Made”, below.

Bram Cohen corrects me?

Bram Cohen has responded to my criticism of his comments on Practical Cryptography. For those who didn’t read my original post, here are my comments in a nutshell:

  1. No, you shouldn’t use RSA with public exponent 2 (i.e., Rabin-Williams). You’re way too likely to screw it up.
  2. No, you should not authenticate (MAC) before you encrypt. You should encrypt first, then you should add a MAC on the ciphertext. Or better yet, use a standard authenticated encryption scheme.
  3. You’re almost always better off using a standard encryption scheme that’s already been implemented and tested, no matter how much ‘better’ an alternative might sound.
You can see Bram’s response in the comments section, down at the bottom of the original post. I’ll try to hit the high points here without doing him an injustice:

Bram: Matthew, first of all, you’re being extremely dismissive of any practical concerns here. Practical crypto deployments bottleneck on the server doing modular exponentiations, and if you use the standard exponent over plain old 2, then you need *five times* as much computing power, which frequently translates into five times as many real machines consuming five times the power in five times as large of a colo space. 

My response? Fair enough. Rabin encryption is a little bit faster. If you’re writing towards an application that needs to perform enormous amounts of encryption, there’s a colorable argument that Rabin might be a good choice. But as Bram points out in his own response, if that’s the case, you’re probably better off using Elliptic Curve cryptography.

In general, I’m leery of efficiency arguments. Standard RSA encryption is extremely fast. The 0x10001 exponents was chosen to minimize the number of squarings required in the encryption process. According to this benchmark, taken on an Intel Core 2 1.83 GHz processor, 1024-bit encryption takes 0.08 milliseconds. That’s without hardware acceleration.

If you’re building a massive server farm and performance is an issue, perhaps there’s reason to worry about the encryption time. If you’re doing something with a very limited processor, and you really know what you’re doing, perhaps there’s some reason to be concerned about performance.

But as a general recommendation? No way. You’re just encouraging people to adopt schemes they don’t really understand, in order to realize a minor performance benefit they won’t notice.

Bram: Doing encrypt-then-authenticate looks a lot like authenticate-then-encrypt except that the authentication is plaintext, which obviously opens it to attacks which involve guessing the plaintext and verifying it because the authentication is right there, and you can extend those to modifying the ciphertext and replacing the authentication. I simply do not believe that making yourself susceptible to those problems is a win. 

Ok, I admit that I legitimately don’t understand Bram’s argument here. If anything, this sounds like the argument for encrypt-then-authenticate.

For the benefit of people who are just joining the discussion, there are basically two points of view. Bram says you should authenticate your plaintext (using a MAC) then you should encrypt it. I (and many other cryptographers) say you should encrypt first, then authenticate the ciphertext.

In a nutshell, the advantage of my approach is what happens at decryption time: when a ciphertext comes in, you first verify a MAC to ensure that the ciphertext is correct and hasn’t been tampered with. You do this with a key that’s not related to the encryption key. If the MAC verification fails, you stop. You simply don’t decrypt.

This ensures that no information about the plaintext ever leaks back to the attacker. If the attacker is tampering with ciphertexts (e.g., in an attempt to implement a padding oracle attack), he gets nothing. This approach has all kinds of nice advantages, one of which is its modularity.

You see, provided that you’re MACing the ciphertext, it doesn’t matter how the encryption scheme works. You don’t have to worry about using it a funny padding scheme. You don’t have to worry about any encoding or compression that might take place during the encryption process. If someone upgrades your encryption to a different mode of operation, you’re still fine — at least as far as active attacks are concerned.

Even better, the encrypt-then-authenticate approach can be proven IND-CCA secure (semantically secure against adaptive chosen ciphertext attacks). A proof can be found in this paper.

Bram: The other issue with encrypt-then-authenticate is that it makes the code more complicated and just plain uglier, which directly makes you more susceptible to the #1 cause of actual breaks, implementation error.

Ok, here again I disagree. Let’s take a look at the most common example of authenticate-then-encrypt that I can think of. It’s CBC-mode encryption as defined in the TLS specification. This has been standard going back to SSL 3.0, but it’s still used in current versions — due to backwards-compatibility issues.

So with that in mind, see this note included in the TLS 1.2 spec:

   Implementation note: Canvel et al. [CBCTIME] have demonstrated a
timing attack on CBC padding based on the time required to compute
the MAC.  In order to defend against this attack, implementations
MUST ensure that record processing time is essentially the same
whether or not the padding is correct.  In general, the best way to
do this is to compute the MAC even if the padding is incorrect, and
only then reject the packet.  For instance, if the pad appears to be
incorrect, the implementation might assume a zero-length pad and then
compute the MAC.  This leaves a small timing channel, since MAC
performance depends to some extent on the size of the data fragment,
but it is not believed to be large enough to be exploitable, due to
the large block size of existing MACs and the small size of the
timing signal.

Allow me to translate this to plain English: “because we chose to authenticate our plaintext, rather than our ciphertext, we had to (a) MAC both the message and the padding, and (b) even though we did that, it turned out that attackers could still hoover out a little bit of information based on the time that it takes to check the ciphertext (basically, implementations would immediately throw an error after seeing invalid padding, and this gave away the game). So implementers now have to do all this extra nonsense if they want their implementation to be secure.”

None of this is necessary in encrypt-then-authenticate. It’s simpler. Really!

I haven’t touched on every single point that Bram makes — you can see his argument in the original posts if you want.

The only final point I would like to make is that this stuff matters. If you get it wrong, you can attack an implementation. And too many people — professionals, even — get it wrong.

In conclusion: I certainly didn’t mean to bash Bram, but I’m happy to bash the advice itself. We can do better.

Digital Fortress: I read it so you don’t have to

Once in a while I run into a work of dramatic fiction that takes such a powerful, realistic look at modern cryptography — and its implications for our national security — that we should all be grateful to the author. They’ve made us all a little bit smarter.

Needless to say, Dan Brown’s Digital Fortress is not one of those books.

What is Digital Fortress? I’m not sure. It may be a practical joke. I’m hoping so, anyway, because the alternative — that Dan Brown spent time learning about cryptography and this is what came out — is too terrible to contemplate.

Miraculously, the end result is so ridiculous that it’s almost tolerable. Almost.

(Before I go further, I should warn you that there are huge spoilers below. But don’t worry about it because (a) you shouldn’t read this book, and (b) the plot is so predictable that I doubt it can really be spoiled.)

Where to begin? Let me just hit some of the high notes:

  • Matt Blaze gets whacked. Ok, Brown doesn’t call him Matt Blaze. The character in the book is named Greg Hale (single syllables, get it?) But we know he’s Matt Blaze because he single-handedly discovered a backdoor (“a few lines of cunning programming”) in the Skipjack cipher, one that would have let the NSA “read the world’s email”.For his efforts, Blaze/Hale is rewarded with a thankless job at the NSA which he hates. And not without reason! Everyone suspects him of being a turncoat (while simultaneously giving him access to their most important secrets, go figure.) Then to cap off the job experience, he’s horrifically murdered. I personally would have ended the book halfway through, and just made Hale the bad guy. Who could blame him
  • The EFF are the bad guys. Did you know that the National Security Agency (2011 ops budget: $9 bazillion) lives in constant terror of the “sharks” over at the Electronic Frontier Foundation (2011 ops budget: $67.34, mostly spent on construction paper)?I did not know this. I sure hope it’s true.Near the end of the book the NSA’s “firewall” goes down for a few minutes, and within seconds the EFF sharks are circling. This does not appear to be a metaphor — they’re actually swimming in literal circles around the NSA’s cyber-perimeter, trying to ferret out our nation’s secrets. Only our hero Susan Fletcher can stop them, thanks to her long, willowy legs staggering intellect.
  • The NSA has a secret supercomputer named TRANSLTR that can brute-force any cryptosystem. Hmm. Ok. This one is actually pretty accurate.
  • TRANSLTR is stumped by a new cipher that uses “rotating cleartext” to resist brute-force attacks. No, seriously. “Rotating cleartext”. Brilliant! This is such a good idea that I hereby offer to make this scheme a reality for only $800. My only condition is that you must never, ever try to decrypt anything with it.

I suppose I could also mention the NSA’s recruiting program for cryptographers, which would make a Big Ten football coach blush. Or the way that brilliant, righteous people always seem to be beautiful and athletic, while stupid evil people look like trolls (have you ever been to a crypto conference, Dan?)

These and other details are embedded in a stew of unintentional comic awfulness that really defies summarization. But it’s good. Not to read, mind you. Just to know about, so you have a reason to chuckle while you’re lamenting the damage that Brown’s writing has done to your temporal lobe.

I really could not recommend this book less, and am considering sending Dan Brown a bill for the time I spent reading it. But if you’re afflicted by a terrible case of Seasonal Affective Disorder and just need some levity in your life, it might keep you giggling through the long dark months ahead.

Happy Thanksgiving everyone!

Neat research ideas that went nowhere: Preventing offline dictionary attacks with CAPTCHAs

Once in a while I come across a research paper that’s so off the beaten path and so obviously applicable to a real problem, that I know it’s going to sink like a stone and never be heard from again.

Today I’d like to talk about an idea that was introduced back in CRYPTO 2006, but doesn’t seem to have gotten any real traction out in the real world since. (If I’m wrong and someone is using it, feel free to email me. I’d be happy to eat my words and hear more.)

This particular idea comes from a 2006 paper by Ran Canetti, Shai Halevi and Michael Steiner,* and it addresses a very real problem that we have with deployed encryption schemes: namely, they tend to rely on passwords. This means that even if you use strong cryptography, all of your data is vulnerable to someone with a password dictionary and a lot of computing power.

Password-Based Encryption (and why we hate it)

To explain how Canetti, Halevi and Steiner propose to deal with this, I need to give a little bit of background on password-based encryption.

First of all of all, no matter what Dan Brown says, we’ve gotten pretty good at building encryption schemes that stand up against very motivated adversaries. If you’re using a modern scheme and are properly generating/storing your secret keys, then it’s awfully unlikely that a third party is going to decrypt your data — even if that party is a government agency.** (I’m leaving aside the wrench factor).

Unfortunately, the previous paragraph embeds one major assumption that makes it inapplicable to the way that many people secure their data. You see, in a cryptographer’s imagination, everyone encrypts with a strong, random 128+ bit secret key, which they memorize and never write down.

But in real life, people mostly prefer to use their cat’s name.

The use of passwords to derive encryption keys is a lot more common than it should be. It’s depressingly common in many applications where people really need security. Passwords are the default authorization method for many fancy encrypting hard-drives and WDE packages. Windows just loves to encrypt things under your login credentials. (Many of these tools also support hardware tokens and TPM, but these are such a drag that most people don’t bother.)

To your attacker, this is a feature not a bug. If a key is derived from dictionary words, or some predictable mutation of dictionary words, then it can be guessed. All it takes is time and  computing power. Moreover, since password guessing is embarrassingly parallel, it’s just the kind of enterprise that you can throw a data center or five at. (Ever wondered why the state of Maryland uses so much electricity?)

So far I haven’t said anything you didn’t already know. But just for fun, let’s quickly talk about what we currently do to prevent dictionary attacks. There are basically three approaches:

  1. Use some trusted, on-line server (or tamper-resistant hardware) to assist with the key derivation process. If done correctly, the server/hardware can shut off an attacker after a few invalid guesses, assuming that it isn’t also compromised. Unfortunately, this solution assumes that the server or hardware will be available when you need your data. That isn’t always possible.
  2. Use key stretching, which increases the time required to convert a password into a cryptographic key. This can slow down a dictionary attack, but it just slows it down. Moreover, it’s pretty ineffective against an attacker with specialized hardware.
  3. Use salt, which is hardly worth mentioning since if you aren’t salting your passwords then you’re crazy. Unfortunately all this does is prevent pre-computation. It does nothing against normal dictionary attacks.

The human touch

In a perfect world, the online solution (1) above would probably be the best way to go. Unfortunately, we don’t live in a perfect world, and this may not be compatible with people’s requirements.

While it’s not possible to prevent dictionary attacks in an offline system, we may be able to slow them down. To do this, we have to make the decryption process much more resource-intensive. Unfortunately, it’s hard to win this game through computation alone, at least not in a world full of FPGAs and elastic compute clouds.

Not this sort of brains. (XKCD).

What Canetti, Halevi and Steiner realized is that there’s one resource that the adversary might not have in abundance: human brains.

What if we could mandate some sort of human interaction each time a user tries to decrypt a file? This shouldn’t be too burdensome for the legitimate decryptor, since presumably he’s human, and moreover he only needs to try once.

But a password cracker needs to try millions of passwords. Requiring a human interaction for each attempt should throw a serious wrench into the process.

Using Human Puzzles to stop dictionary attacks

Fortunately we already have a whole class of technologies that differentiate human beings from computers. Generally, these are known as Reverse Turing Tests (RTTs). Canetti, Halevi and Steiner propose to use RTTs to construct “human puzzles”. At a high level, the idea is pretty simple.

In every PBE scheme, a password must first be converted into a key. Normally you do this by hashing the password and some salt via a standard key derivation function (e.g., PBKDF2). Usually this is where you’d stop. The output of this function, which we’ll call K, would be the key used to encrypt and decrypt.

However, now we’re going to take things one step further. The first key will be further processed by converting it into a puzzle that only a human can solve. When a human solves this puzzle, they create a new key that, ideally, a computer all by itself should not be able to recover. The process should be reliable — it needs to produce the same result every time it’s run, possibly across many different users.

Once you get past the theoretical stuff, the concrete example that Canetti, Halevi and Steiner propose is to use CAPTCHAs to implement human puzzles.

CAPTCHAs: don’t you love them?

In their example, the process of deriving an encryption key from a password now looks like this:

  1. First hash the password with some random salt r to derive a first key K. Now break this into a bunch of small chunks, each (for example) about 20 bits long.
  2. Use each of these 20-bit chunks to index into a huge table containing 2^20 (about 1 million) distinct CAPTCHA images. Each CAPTCHA contains a hard-to-read string with at least 20 bits of entropy in it. This string could be a bunch of numbers, or some randomly-selected dictionary words.
  3. Give each CAPTCHA to the human user to solve. Collect the results.
  4. Hash all of the user’s responses together with another salt s to derive a final decryption key.

If we instantiate the hash function with, say, PBKDF2 and a 160-bit output, then this requires the legitimate user to solve 8 puzzles the first time they encrypt, and every subsequent time they decrypt.

The dictionary attacker, however, has to solve eight puzzles for every password they try. If we assume that they have to guess a large number of passwords, this means that over time they’ll have to solve a substantial fraction (if not all) of the 1 million CAPTCHAs. Even if they can outsource this work at a rate of 5 cents per CAPTCHA, solving the whole collection will still cost $50,000 and a whole lot of hassle.

(This is a hugely simplified analysis. Obviously the attacker doesn’t have to solve all of the CAPTCHAs. Rather, their probability of guessing the key is a function of the number of CAPTCHAs, the fraction of the CAPTCHAs that they’ve been able to solve, the complexity of the password, etc. See the full paper for a much better analysis.)

The sticky wicket

Now, this really might work, in the sense that it will slow down attacks. But if you’re a practical-minded sort, you probably have one small question about this proposal. Namely: where do the CAPTCHAs come from?

Well, a simple answer is that you generate them all randomly the first time you encrypt, and you ship them along with the encrypted file. If we assume that each CAPTCHA is a 4KB image file, then storing the entire collection will require about 4GB.

That’s seems like a lot of space, but really it isn’t. After all, it’s not like we’re working with floppy drives. We live in a world where a 16GB USB Flash Drive can be had for about $10. So it’s perfectly reasonable to assume that we’ll have lots storage for things we really care about.

In summary

Now maybe CAPTCHAs aren’t your thing. Maybe you don’t like the idea of storing 4GB worth of files just to ship someone an encrypted ZIP file. That’s fine. One of the neatest open problems in the paper is to find new sorts of human puzzles. In general, a human puzzle is any function that converts some input (say a 20-bit string) into an output, such that only a human being can do the transformation.

These don’t need to rely on bulky, stored CAPTCHAs. Hypothetically you could come up with a human puzzle that dynamically generates instances without a big stored database. For example, your puzzle might be based on recognizing human expressions, or inkblots. It just has to be reliable.

And that’s why I think this is such a neat paper. Whether or not this particular idea changes the world, it’s a new idea, it tries to solve a hard practical problem that most people have given up on, and it inspires some new ideas.

The crypto publishing game rarely produces papers with that particular combination. Just for that, I’d love to see it go somewhere.

Notes:

* Ran Canetti, Shai Halevi and Michael Steiner. 2006. Mitigating Dictionary Attacks on Password-Protected Local Storage. In CRYPTO ’06.

** Leaving aside what we all know the NSA’s got in its basement.

An update on our contest

Update 11/26/11: You can download all of these symbols in PDF and high-res PNG here.

A couple of weeks ago I sang the praises of the AIGA Symbol Signs package. I think it’s a great way to get nice looking presentations and diagrams, especially if you’re as graphically challenged as I am. (H/t goes to Thomas Ptacek for introducing me to it.)

The one thing Symbol Signs lacks is a good symbol for the Adversary. I’ve been using the diapered baby. Thomas likes the Martini glass. And yet both of these are really hacks. We can do better.

Thus I proposed a contest: $200 to the person who could come up with a new AIGA-consistent symbol to use for the adversary. Honestly, I kind of figured I’d never have to shell out. So it’s with pride and some financial trepidation that I today present not one, but two fantastic entries. The first, really a collection of adversaries, comes from my good friend Sam Small:

I particularly like that he provided me with the adversaries in both sexes. In my teaching I’ve been making a concerted effort to provide equal time to both female adversaries. I find that too many male (and even female!) cryptographers implicitly relate adversarial behavior to the male gender. (Apparently the whole Eve thing is just a figleaf.) But this isn’t fair. Women can be attackers too!

Also, I like the devil baby.

Our second entry comes straight from Thomas Ptacek himself. He only has one proposal, but what he lacks in quantity he makes up for in sinisterness:

And so here we are. I’m not quite sure who the winner is — it’ll take some thinking — but I can tell you that thanks to Sam and Thomas the security community is better off today than we were a few weeks ago.

As soon as I have time (this weekend) I’ll post both of these adversaries in downloadable PDF form. I urge you to use them frequently, and to use them wisely.

The first rule of vulnerability acknowledgement is: there is no vulnerability acknowledgement

Just for fun, today we’re going to look at two recent vulnerability acknowledgements. The first one’s pretty mild; on the Torino scale of vulnerability denial, it rates only about a three:

The research team notified Amazon about the issues last summer, and the company responded by posting a notice to its customers and partners about the problem. “We have received no reports that these vulnerabilities have been actively exploited,” the company wrote at the time. 

But this one from RSA, wow. The charts weren’t made for it. I suggest you read the entire interview, perhaps with a stiff drink to fortify you. I warn you, it only gets worse.

If our customers adopted our best practices, which included hardening their back-end servers, it would now become next to impossible to take advantage of any of the SecurID information that was stolen.

… We gave our customers best practices and remediation steps. We told our customers what to do. And we did it quickly and publicly. If the attackers had wanted to use SecurID, they would want to have done it quietly, effectively and under the covers. The fact that we announced the attack immediately, and the fact that we gave our customers these remediation steps, significantly disadvantaged the attackers from effectively using SecurID information.

… We think because we blew their cover we haven’t seen more evidence [of successful attacks].

I have a paper deadline midweek, so blogging will be light ’til then. Once that’s done, I’ll have something more substantial to say about all this.

Format Preserving Encryption, or, how to encrypt a credit card number with AES

People like to encrypt all kinds of things. This is really their own business. One of the lovely things about modern crypto is that for the most part, we don’t care.

You see, data is data. If you can encode it as a file then we can tell you how to encrypt it. There’s rarely any reason to develop special domain-specific encryption algorithms, like image encryptors. If you’re developing such an algorithm then chances are you’re doing it to implement some sort of goofy DRM scheme, rather than to provide serious cryptographic protection.

However, once in a blue moon, you do come across a case where you legitimately need an encryption algorithm that works with specific data types.

For example, let’s say I want to encrypt my credit card number. In principle this is no problem: card numbers are just numbers, after all.

Assuming that we want a general technique*, I could simply represent my 16-digit VISA card number as an integer between 0 and 9,999,999,999,999,999. In binary this value will require up to 54 bits to store (since lg 10,000,000,000,000,000 = 53.1508495).

In the absolute ‘best case’ — assuming that we don’t need to pad the message or add an IV (for example, if we’re using a stateful stream cipher, like AES-CTR), and we don’t care about authentication, we can encrypt this value without expansion. Thus, the ciphertext will be a randomish 54-bit string. Not bad at all.

But here’s a question: what if our software can’t handle a 54-bit string?

No, this isn’t crazy! For example, let’s say we need to store that encrypted card number in some legacy retail system that only accepts standard 16-digit decimal card numbers. Or alternatively, we want to transmit it through a normal payment processing network.** For both of these applications, we may need to first translate our ciphertext back into something that looks like a credit card number.

And this can be a problem. Certainly, the naive solution doesn’t work. If you’ve properly encrypted the card number, it should now be a uniformly distributed 54-bit string, which encodes to an integer between 0 and 18,014,398,509,481,983. Too many digits!

Moreover, there are applications where you might require additional properties from your encryption scheme. For example, it might be necessary to search a database for a particular card number. One way to do this is to use a deterministic encryption scheme, one that’s a permutation on the message space. This ensures that a given card number X will always encrypt to a unique number Y, which makes searching and comparison really easy.

If we didn’t care about the size of the ciphertext, we might be able to get away with encrypting the credit card number as a single block in ECB mode. Block ciphers are permutations, so this would satisfy the requirements just above.***

Unfortunately, this even further exacerbates our original problem. The block size for AES is 128 bits, even poor old DES is 64 bits. If we use ECB mode to encrypt, that’s how long the resulting ciphertext will be. We’ll never be able to encode something that long back to a 16-digit decimal number.

So what to do?

Format-Preserving Encryption

Fortunately there’s an answer to these problems, and it goes by the name of “Format-Preserving Encryption“, or FPE. As the name implies, the goal of a Format-Preserving Encryption scheme is to securely encrypt while preserving the original formatting of the plaintext data. That means, in a nutshell, that our 16-digit card number can encrypt to a 16-digit number, no problem at all.

The seminal work in this area was written by Black and Rogaway back in 2002. Right off the bat, these guys made three very important observations:

  1. There are all sorts of applications where you need to preserve the format of input data.
  2. You could design your own cipher to do it, but it would probably suck.****
  3. It would sure be nice if we could do it securely using standard ciphers, like AES.

And then, in one of those amazing coincidences that always seem to turn up in research papers, Black and Rogaway discovered that you can do it with standard ciphers. And better yet, you can do it fairly efficiently.

Two Problems

What Black and Rogaway noticed is that there are really two problems here. The first is to build a cipher that works on arbitrary bit lengths. The second problem is to use such a cipher to encrypt arbitrary sets, like the set of all people named “Gino” who live in Atlanta. Or, more usefully, the set of integers from 0 to 9,999,999,999,999,999.

Even better, they pointed out, the first problem has already been solved. Various people, starting with Luby and Rackoff, had shown how to use a pseudorandom function or permutation (e.g., AES) to build ciphers of arbitrary block size. This is usually accomplished with a Feistel network construction like the one used in the DES cipher.

The basic idea is illustrated in the diagram below. To build a cipher that operates on 54-bit blocks, for example, we would cut the input block input block into two 27-bit halves, L0 and R0, and push them through a Feistel network for several rounds. This is an amazingly simple construction; it requires only XOR and some non-linear function F(), which we’ll implement using an existing cipher like AES (with truncation of the output).

Note that each call to AES must use a different key, although we can derive these all from one single key using standard techniques. Since AES is much better than the DES S-boxes, we won’t need to run the network for 16 rounds. Three or four rounds is probably sufficient.*****

feistel
Diagram of a Feistel network. The input (left side) is split into two halves and passed
through a number of rounds. In the Luby-Rackoff variant, each function “F” is implemented via an independent, keyed pseudorandom function. Decryption is accomplished by reversing the process.

But like I said, this is only half the battle. Now we can construct a strong block cipher that operates on 54-bit inputs. I said above that this big enough to handle credit card, but I also pointed out that it’s too big.

If we encrypt a card number with such a cipher (in ECB mode), we’ll end up with a randomly-distributed 54-bit ciphertext that might not easily translate back into a 16-digit integer. We still need something more.

Cycling

Black and Rogaway had a few ideas on how to deal with this. One of their approaches is something called ‘cycling’, which is so astonishingly straightforward that you’d assume it doesn’t work. It does!

Here’s how it works. Let’s say I want to encrypt my Visa card number (“4532294977918448“). I’ll follow these steps:

  1. First, I’ll encode the number as 54-bit integer, then encrypt it using the fancy 54-bit block cipher I built above.
  2. At the end of this process I should have 54-bit ciphertext C. Now, there’s a very good chance that, represented as an integer, C will be ‘small’ enough to represent as a 16-digit integer. If so, then I’m done. That’s my output!
  3. But what if C is too large? No problem. If it first you don’t succeed, just try again. Take that first ciphertext C, and encrypt it again using the blockcipher to get a new C. Go back to step 2.

I’ll let you work out the decryption algorithm.

Now, the pedantic among you will observe that technically speaking, this encryption process could put you in an infinite a ridiculously long (but finite) loop.***** At very least, you can’t say in advance how long it will go on.

However, if we assume that the cipher behaves ‘randomly’, then we can easily get an idea of how likely we are to be satisfied at stage (2). Roughly speaking, there’s a 55% probability that we’ll get it right each time through the loop (10,000,000,000,000,000 / 2^54). This means that on average we shouldn’t require more than a couple of encryptions

If you’re not convinced, go grab a (slightly biased) coin and start flipping. You’re done when you get tails.

A note on security

Cycling is not the only technique that Black and Rogaway propose. They have a couple of others that may be better for your specific application. You can check out the paper if this kind of thing interests you.

Another neat thing about the cycling technique is that it actually doesn’t cost you anything. This is a very cryptographer kind of thing to say, since it actually does cost you quite a lot — in terms of time and extra computation. But what it doesn’t cost you much of is security. You might think that all this repetition might make the cipher somehow weaker. But Black and Rogaway show that it doesn’t, at least not in the ideal case.

In Summary: The real world 

So we know how to deterministically encipher arbitrary numbers. But a more important question is: is any of this a good idea?

Well, sometimes in security, application requirements trump perfection. Obviously it would be better to protect your data using standard, randomized encryption. This deterministic stuff only works well if there’s a certain amount of unpredictability in the underlying data, and that’s never guaranteed.

For example, your typical credit card number isn’t really 16 digits of random data at all. Typically it’s composed of a 4-6 digit Bank Identification Number (BIN), followed by a Personal Account Number (PAN), followed by a special checksum digit that’s computed deterministically based on the previous digits. The Personal Account number is the really unpredictable bit, and if you use an American Express card (15 digits total), it could be as short as 8 digits.

That means in an extreme case, there might be only about 100 million possible PAN numbers. Still a pretty large number, but if you knew the BIN and could gain access to an encryption oracle that lets you encrypt arbitrary card numbers at a rate of 1,000 per second, you could generate every possible ciphertext in a little over a day. This would let you decrypt any encrypted card number, simply by looking it up in a table.

Probably this scenario is unrealistic, but it’s something to keep in mind if you plan to deploy a system like this.

Notes:

* Credit card numbers do have some structure, so in practice you could take advantage of that. For the moment, let’s not.

** In practice, this application requires more thinking. CCNs contain routing information called the Bank Identification Number (the first few digits) as well as a meaningful checksum digit (the last one).

*** Though be careful with this: the permutation property only holds if you can encode your data into a single cipher block. If you have to break it up across multiple blocks, it doesn’t work anymore.

**** As I’ve explained elsewhere, I am not being rude. In cryptography ‘suck’ is a purely technical term meaning “slow, complex, and probably insecure”.

***** There are various specific attacks that dictate how many rounds you need to use. Don’t take my word here as gospel.

****** Updated per Terence’s comment below. However I’m not sure that this is comforting to anyone but a cryptographer 🙂 Also see JoachimV’s comment for some updates on the field.