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.

The Ideal Cipher Model (wonky)

A friend who’s learning cryptography writes with a few questions about block ciphers:

(1) Let’s say we’re using AES-128 — 128 bit keys, 128 bit blocks.

  • For a given 128 bit block of plaintext “P” – if I was to iterate through all 2**128 key permutations and encrypt the same plaintext P with each key, would the outputs all be unique, or would there be collisions?
  • For a given 128 bit key “K”, if I was to use K to encrypt every possible (2**128) plaintext, would the outputs all be unique, or would there be collisions?
These are all reasonable questions with simple answers. But I’m not going to give them. Why bother with two simple answers when we can give one really complicated intuition?

What’s Claude Shannon got to do with it?

Back in the late 1940s when people were still thinking on this whole information theory business, a gentleman named Claude Shannon came up with a model for what a block cipher should do. His idea was — and yes, I’m embellishing a lot here — that an ‘ideal’ block cipher would work kind of like a magical elf.*

You could ask the elf to encipher and decipher things for you. But instead of using a mathematical algorithm, it would just keep a blackboard with a big table. The table would have three columns (Key, Plaintext, Ciphertext), and it would start off empty.

When you asked the elf to encipher a plaintext P under a key K, it would do the following:
  1. Check to see if (K, P) were already recorded in some row of the table. If they were, it would read off the corresponding ciphertext value C from the same row, and return C.
  2. If no matching row was found, it would generate a perfectly random ciphertext C.
  3. It would then check for an existing table entry containing the same key and ciphertext (K, C). If this entry was found in the table, it would throw C away and repeat step (2).
  4. Otherwise it would add (K, P, C) to the table and return C to the caller.

Now I realize this looks complicated, but if you think about this for a little while you’ll realize that this little thought experiment does ‘work’ a lot like a real block cipher.

Just like a block cipher, it will always give the same output when you pass it a given key and plaintext. Furthermore — for a given key K, no two plaintexts will ever encipher to the same ciphertext. This models the fact that a block cipher is a permutation.

Lastly, the output of the encipherment is very ‘random’ — in the sense that it’s intuitively not linked to the input. Calling the cipher on different inputs should produce values that are very much unrelated.

Of course, you also need the elf to decipher stuff as well. Decipherment works mostly like the process above. When you ask to decipher (K, C), it checks to see whether the given key and ciphertext are already in the table (i.e., they were previously enciphered). If so it looks up and returns the corresponding plaintext. Otherwise it generates a new random plaintext, makes sure it hasn’t previously appeared in the table with that key, and returns the result.

Under the assumption that AES works like our elf, we can now answer my friend’s questions. Clearly if I encrypt the same plaintext with many different keys, I will get many different ciphertexts. They’ll each be random and 128 bits long, which means the probability of any two ciphertexts being the same (colliding) is quite small. But there’s no rule preventing it, and over a large enough set it’s actually quite likely.

Similarly, the second question is answered by the fact that the cipher is a permutation, something that’s captured in our elf’s rule (3).

This is an awful lot of work to answer a few simple questions…

Yes, it certainly is. But the ‘Elf’ model is useful for answering much more interesting questions — like: is a given encryption scheme secure?

For example, take the CBC mode of operation, which is a way to turn a block cipher into an encryption scheme:

CBC encryption takes in a random key (K) and a random ‘Initialization Vector’ (IV), both of which are chosen by the encryptor. Now let’s see what happens if we CBC-encrypt an N-block message using our elf.

  1. The encryptor XORs the first plaintext block with the (random) Initialization Vector (IV), which should give a randomly-distributed value. We’ll call this P’.
  2. He then sends (K, P’) to be enciphered by the elf. Since the elf has never seen (K, P’) — meaning it’s not in the table — it will generate a random value (C1), which will become the first ciphertext block.
  3. The encryptor now XORs the next plaintext block with C1, which again should yield a randomly-distributed value which we’ll call P”.
  4. He sends (K, P”) to be enciphered by the elf. Since P” is also random (and, say, 128 bits long), the probability that it’s already in the table is astronomically low. Thus with high probability the elf will again generate a random value (C2), which becomes the second ciphertext block.
  5. He then repeats steps (3) and (4) for all the remaining blocks.
Note that with overwhelming probability — and unless you encrypt really long ciphertexts** — the elf will generate a random value for each ciphertext block. Hence the entire ciphertext will consist of a random string, which means it really shouldn’t leak anything about the message (except for the length).

Of course, an attacker might also talk to the elf to try to learn something about the message. But note that even this attack isn’t useful unless he can guess the (random) key K, since the elf will give him random results unless he asks for a value that includes K. Since K is a randomly-chosen secret key, the attacker should not be able to guess it.

Do ideal ciphers exist?

Now all of this is well and good, but it leaves us with an important question: is AES actually as good as an ideal cipher? Unfortunately, the resounding answer to this question is no.

The problem here is that ideal ciphers are totally unworkable. Obviously we can’t have an actual elf randomly filling in a bulletin board as we encrypt things. I want to carry a copy of the block cipher around with me (in software or hardware). I also want my copy of the cipher to be consistent with your copy, so that I can send you messages and you can decrypt them.

To make the elf idea work, we would each need to carry around a copy of the elf’s table that’s completely filled in from the start — meaning it would already contain entries for every possible plaintext (resp. ciphertext) and key I might ever need to encipher/decipher. When you consider that there would be 2^128 rows just for a single key, you realize that, no, this is not a question of running out to Best Buy and picking up some more SD cards. It’s fundamentally hard.

So carrying ideal ciphers around is not possible. The question then is: is there something that’s as good as an ideal cipher, without requiring us to carry around an exponentially-sized table.

The answer to that question is a mixed bag. The bad news is that nothing really works as well as an ideal cipher. Worse yet, there exists schemes that would be provably secure with an ideal cipher, but would fail catastrophically if you implemented them with any real block cipher. So that sucks.

On the other hand, those are theoretical results. Unless you’re doing some very specific things, the ideal cipher model is a moderately helpful tool for understanding what block ciphers are capable of. It’s also a good jumping off point for understanding the real proofs we actually use for modes like CBC. These proofs use more ‘realistic’ assumptions, e.g., that the block cipher is a pseudorandom permutation.

But those proofs will have to wait for another time. I’ve reached my wonkery limit for today.

Notes:

* For the record, at no point did Claude Shannon ever refer to an ‘elf’. At least not in writing.

** The probability of a ‘collision’ (i.e., asking the elf to encipher a value that’s already been enciphered) goes up as you put encipher more blocks. At a certain point (for AES, close to 2^64 blocks) it becomes quite high. Not coincidentally, this roughly coincides with the number of blocks NIST says you should encrypt with CBC mode.

Attack of the week: RC4 is kind of broken in TLS

Update: I’ve added a link to a page at Royal Holloway describing the new attack. 

Listen, if you’re using RC4 as your primary ciphersuite in SSL/TLS, now would be a great time to stop. Ok, thanks, are we all on the same page?

No?

I guess we need to talk about this a bit more. You see, these slides have been making the rounds since this morning. Unfortunately, they contain a long presentation aimed at cryptographers, and nobody much seems to understand the real result that’s buried around slide 306 (!). I’d like to help.

Here’s the short summary:

According to AlFardan, Bernstein, Paterson, Poettering and Schuldt (a team from Royal Holloway, Eindhoven and UIC) the RC4 ciphersuite used in SSL/TLS is broken. If you choose to use it — as do a ridiculous number of major sites, including Google — then it may be possible for a dedicated attacker to recover your authentication cookies. The current attack is just on the edge of feasibility, and could probably be improved for specific applications.

This is bad and needs to change soon.

In the rest of this post I’ll cover the details in the usual ‘fun’ question-and-answer format I save for these kinds of attacks.

What is RC4 and why should I care?

RC4 is a fast stream cipher invented in 1987 by Ron Rivest. If you like details, you can see this old post of mine for a longwinded discussion of RC4’s history and flaws. Or you can take my word: RC4 is old and crummy.

Despite its age and crumminess, RC4 has become an extremely popular ciphersuite for SSL/TLS connections — to the point where it accounts for something absurd like half of all TLS traffic. There are essentially two reasons for this:

  1. RC4 does not require padding or IVs, which means it’s immune to recent TLS attacks like BEAST and Lucky13. Many admins have recommended it as the solution to these threats.
  2. RC4 is pretty fast. Faster encryption means less computation and therefore lower hardware requirements for big service providers like Google.

So what’s wrong with RC4?

Like all stream ciphers, RC4 takes a short (e.g., 128-bit) key and stretches it into a long string of pseudo-random bytes. These bytes are XORed with the message you want to encrypt, resulting in what should be a pretty opaque (and random-looking) ciphertext.

The problem with RC4 is that the above statement is not quite true. The bytes come out of the RC4 aren’t quite random looking — they have small biases. A few of these biases have been known for years, but weren’t considered useful. However, recent academic work has uncovered many small but significant additional biases running throughout the first 256 bytes of RC4 output. This new work has systematically identified many more.

At first blush this doesn’t seem like a big deal. Cryptographically, however, it’s a disaster. If I encrypt the same message (plaintext) with many different RC4 keys, then I should get a bunch of totally random looking ciphertexts. But these tiny biases mean that they won’t be random — a statistical analysis of different positions of the ciphertext will show that some values occur more often.

By getting many different encryptions of the same message — under different keys — I can tally up these small deviations from random and thus figure out what was encrypted.

If you like analogies, think of it like peeking at a picture with your hands over your eyes. By peeking through your fingers you might only see a tiny sliver of the scene you’re looking at. But by repeating the observation many times, you may be able to combining those slivers and figure out what you’re looking at.

Why would someone encrypt the same message many times?

The problem here (as usual) is your browser.

You see, there are certain common elements that your browser tends to send at the beginning of every HTTP(S) connection. One of these values is a cookie — typically a fixed string that identifies you to a website. These cookies are what let you log into Gmail without typing your password every time.

If you use HTTPS (which is enforced in many sites by default), then your cookies should be safe. After all, they’ll always be sent over an encrypted connection to the website.Unfortunately, if your connection is encrypted using RC4 (as is the case with Gmail), then each time you make a fresh connection to the Gmail site, you’re sending a new encrypted copy of the same cookie. If the session is renegotiated (i.e., uses a different key) between those connections, then the attacker can build up the list of ciphertexts he needs.

To make this happen quickly, an attacker can send you a piece of Javascript that your browser will run — possibly on a non-HTTPS tab. This Javascript can then send many HTTPS requests to Google, ensuring that an eavesdropper will quickly build up thousands (or millions) of requests to analyze.

Probability of recovering a plaintext byte (y axis) at a particular byte position in the RC4-encrypted stream (x axis), assuming 2^24 ciphertexts. Increasing the number of ciphertexts to 2^32 gives almost guaranteed plaintext recovery at all positions. (source)

Millions of ciphertexts? Pah. This is just crypto-wankery.

It’s true that the current attack requires an enormous number of TLS connections — in the tens to hundreds of millions — which means that it’s not likely to bother you. Today. On the other hand, this is the naive version of the attack, without any special optimizations.

For example, the results given by Bernstein assume no prior plaintext knowledge. But in practice we often know a lot about the structure of an interesting plaintext like a session cookie. For one thing, they’re typically Base64 encoded — reducing the number of possibilities for each byte — and they may have some recognizable structure which can be teased out using advanced techniques.

It’s not clear what impact these specific optimizations will have, but it tends to reinforce the old maxim: attacks only get better, they never get worse. And they can get a lot better while you’re arguing about them.

So what do we do about it?

Treat this as a wakeup call. Sites (like Google) need to stop using RC4 — before these attacks become practical. History tells us that nation-state attackers are already motivated to penetrate Gmail connections. The longer we stick with RC4, the more chances we’re giving them.

In the short term we have an ugly choice: stick with RC4 and hope for the best, or move back to CBC mode ciphersuites — which many sites have avoided due to the BEAST and Lucky13 attacks.

We could probably cover ourselves a bit by changing the operation of browsers, so as to detect and block Javascript that seems clearly designed to exercise these attacks. We could also put tighter limits on the duration and lifespan of session cookies. In theory we could also drop the first few hundred bytes of each RC4 connection — something that’s a bit of a hack, and difficult to do without breaking the TLS spec.

In the longer term, we need to move towards authenticated encryption modes like the new AEAD TLS ciphersuites, which should put an end to most of these problems. The problem is that we’ll need browsers to support these modes too, and that could take ages.

In summary

I once made fun of Threatpost for sounding alarmist about SSL/TLS. After all, it’s not like we really have an alternative. But the truth is that TLS (in its design, deployment and implementation) needs some active help. We’re seeing too many attacks, and they’re far too close to practical. Something needs to give.

We live in a world where NIST is happy to give us a new hash function every few years. Maybe it’s time we put this level of effort and funding into the protocols that use these primitives? They certainly seem to need it.

Here come the encryption apps!

It seems like these days I can’t eat breakfast without reading about some new encryption app that will (supposedly) revolutionize our communications — while making tyrannical regimes fall like cheap confetti.

This is exciting stuff, and I want to believe. After all, I’ve spent a lot of my professional life working on crypto, and it’s nice to imagine that people are actually going to start using it. At the same time, I worry that too much hype can be a bad thing — and could even get people killed.

Given what’s at stake, it seems worthwhile to sit down and look carefully at some of these new tools. How solid are they? What makes them different/better than what came before? And most importantly: should you trust them with your life?

To take a crack at answering these questions, I’m going to look at four apps that seem to be getting a lot of press in this area. In no particular order, these are Cryptocat, Silent Circle, RedPhone and Wickr.

A couple of notes…

Before we get to the details, a few stipulations. First, the apps we’ll talk about here are hardly the only apps that use encryption. In fact, these days almost everyone advertises some form of ‘end-to-end encryption‘ for your data. This has even gotten Skype and Blackberry into a bit of hot water with foreign governments.

However — and this is a critical point — ‘end-to-end encryption’ is rapidly becoming the most useless term in the security lexicon. That’s because actually encrypting stuff is not the interesting part. The real challenge turns out to be distributing users’ encryption keys securely, i.e., without relying on a trusted, central service.

The problem here is simple: if I can compromise such a service, then I can convince you to use my encryption key instead of your intended recipient’s. In this scenario — known as a Man in the Middle (MITM) attack — all the encryption in the world won’t help you.

Man in the Middle attack (image credit: Privacy Canada via Wikipedia). Mallory convinces Alice and Bob to use her key, then transparently passes messages between the two.

And this is where most ‘end-to-end’ commercial services (like Skype and iMessage) seem to fall down. Clients depend fundamentally on a central directly server to obtain their encryption keys. This works fine if the server really is trustworthy, but it’s huge problem if the server is ever compromised — or forced to engage in MITM attacks by a nosy government.

(An even worse variant of this attack comes from services that actually store your secret keys for you. In this case you’re truly dependent on their good behavior.*)

One important feature of the ‘new’ encryption apps is that they recognize this concern. That is, they don’t require you to trust the service. A few even point this out in their marketing material, and have included their own dishonesty into the threat model.

Cryptocat

Cryptocat is an IM application developed by Nadim Kobeissi, who — when he’s not busy being harassed by government officials — manages to put out out a very useable app. What truly distinguishes Cryptocat is its platform: it’s designed to run as a plugin inside of a web browser (Safari, Chrome and Firefox).

Living in a browser is Cryptocat’s greatest strength and greatest weakness. It’s a strength because (1) just about everyone has a browser, (2) the user interface is pretty and intuitive, and (3) the installation process is trivial. Cryptocat’s impressive user base testifies to the demand for such an application.

The weakness is that it runs in a frigging web browser.

To put a finer point on it: web browsers are some of the most complex software packages you can run on a consumer device. They do eight million things, most of which require them to process arbitrary and untrusted data. Running security-critical code in a browser is like having surgery in a hospital that doubles as a sardine cannery and sewage-treatment plant — maybe it’s fine, but you should be aware of the risk you’re taking.

If that’s not good enough for you: go check out this year’s pwn2own results.

For non-group messaging, Cryptocat uses a protocol known as off-the-record (OTR) and ships the encrypted data over Jabber/XMPP — using either Cryptocat’s own server, or the XMPP server of your choice. OTR is a well-studied protocol that does a form of dynamic key agreement, which means that two parties who have never previously spoken can quickly agree on a cryptographic key. To ensure that your key is valid (i.e., you’re not being tricked by a MITM attacker), Cryptocat presents users with a key fingerprint they can manually verify through a separate (voice) connection.

So how does Cryptocat stack up?

Code quality: Nadim has taken an enormous amount of crap from people over the past year or two, and the result has been a consistent and notable improvement in Cryptocat’s code quality. While Cryptocat is written in Javascript (aaggh!), the application is distributed as a plugin and not dumped out to you like typical script. This negates some of the most serious complaints people level at Javascript crypto, but not all of them! Cryptocat has also been subject to a couple of commercial code audits.

Crypto: All of the protocols are well-studied and designed by experts. Update: Jake Appelbaum reminds me that while this is true for one-on-one communications, it’s not true for the multi-party (group chat) OTR protocol — which is basically hand-rolled. Don’t use that.

Ease of use: My five year old can use Cryptocat.

Other notes: If the silent auto-update functionality is activated (in Chrome) it is technically possible for someone to compromise Cryptocat’s update keys and quietly push out a malicious version of the app. This concern probably applies to most applications, but it is something you should be aware of.

Should I use it to fight an oppressive regime? Oh god no.

Silent Circle

Silent Circle is the brainchild of PGP inventor Phil Zimmerman and a cadre of smart/paranoid folks. It actually consists of multiple apps, supporting VoIP/IM/PGP-based Email and videoconferencing — with an optional Snapchat-like self-destructing messages feature. The apps can essentially replace the standard Phone and Messages apps in your iPhone or Android device.

Silent Circle is a paid subscription service, which means it’s marketed to folks who (in theory, anyway) really care about their security, but also don’t want to scrounge around with messy open-source software — for example, journalists working in dangerous locations or business executives running overseas operations. In exchange for $240/year you get the ability to securely call other SilentCircle subscribers and to dial ordinary telephone (POTS) numbers.

The termination to POTS is SilentCircle’s best feature, and also its biggest concern. When you directly call another SilentCircle user, your connection is encrypted from your phone to theirs. When you dial a normal phone line, your connection will only be encrypted until it reaches SilentCircle’s servers. From there it will travel on normal, tappable phone lines.

Now most users will probably understand this, and SilentCircle certainly does its best to make sure people do. Still, most users aren’t experts, and it’s easy to imagine a typical user getting confused — and possibly assuming they’re safer than they actually are.

SilentCircle uses ZRTP (and a variant called SCIMP) to generate the keys used in communications. It doesn’t require you to trust a central directory server, or to send your keys outside of the device. Your protection against MITM comes from two features: (1) the app presents a ‘short authentication string’ that users can verbally compare before they communicate, and (2) after you’ve successfully communicated the first time, it caches a ‘secret’ that can be used to protect future sessions.

Overall code quality: It took a while for SilentCircle to publish their code, but they’ve finally put most of it online. It’s much less fun to look at SilentCircle than it is to poke at Cryptocat — mostly because Nadim’s reactions are more entertaining — but the code for SilentCircle looks ok. (I’ve seen a couple of minor comments, but nobody’s found any security issues.) Moreover, the app has been independently audited and given a clean bill of health.

Crypto: SilentCircle uses ZRTP, which I dislike because it’s so complex — it’s like a choose-your-own-adventure by sadists. But ZRTP is old and well-studied so it’s unlikely that there are any serious issues lurking in it. The messaging app uses a simplified variant called SCIMP (Silent Circle Instant Messaging Protocol) which seems much better, since it ditches most of the crazy options I dislike about ZRTP. I’m pretty confident that both of these protocols work just fine.

Ease of use: To quote SilentCircle’s PR: so simple even an MBA can use it. (No, I’m kidding, they don’t say that. They just think it.)

Other thoughts: Rumor has it that the market price for an iOS vulnerability is currently near $500,000. That doesn’t mean iOS (or Silent Circle’s app) is bulletproof. But it should give you a little bit of confidence. If you’re being targeted with an iOS software vulnerability, then someone really wants you.

Should I use this to fight my oppressive regime? SilentCircle’s founders have made it clear that they’ll chew off their own legs before they allow themselves to be a party to eavesdropping on their clients. But even so — I would still have to think on this for a while.

RedPhone/TextSecure

RedPhone and TextSecure are developed by Moxie Marlinspike’s Open Whisper Systems. Note that OWS is actually Moxie’s second company — the original Whisper Systems was purchased by Twitter a couple of years back — not for the software, mind you; just to get hold of Moxie for a while.

RedPhone does a much of what SilentCircle does, though without the paid subscription and termination to POTS. In fact, I’m not quite sure if you can terminate it to POTS (I’ll update if I find out.)

Like Silent Circle, RedPhone uses ZRTP to establish keys, then encrypts voice data using AES. Consequently, most of what I said for SilentCircle also applies here, including the use of a short authentication string to prevent MITM attacks.

Overall code quality: After reading Moxie’s RedPhone code the first time, I literally discovered a line of drool running down my face. It’s really nice.

In fact, it was so nice that I decided to rough it up a little. I assigned it to the grad students in my Practical Crypto course — assuming that they’d find something, anything to take the shine off of it. Unfortunately they basically failed on this score (though see ‘Other thoughts’ below). In short: it’s very well written.

Crypto: Most of what I said about Silent Circle applies here, except that RedPhone uses only ZRTP, not SCIMP. However, RedPhone’s implementation of ZRTP is somewhat simplified and avoids most of the options that make ZRTP a pain to deal with.

Other thoughts: In fairness to my students, they did point out that Redphone does not retain a cache of secrets from connection to connection. Technically this is an optional feature of ZRTP, so it’s not wrong to omit it. However, it means that you have to verify the authentication string on every single call. Moxie is working on this, so it may change in the future.

Should I use this to fight my oppressive regime? Oh look, a pony!

Wickr

Wickr is an encrypted Snapchat-like app for the iPhone. Like the above applications it provides for instant messaging, but it also focuses heavily on the message destruction feature. Chats/messages can be set to self-destruct after a pre-specified period of time.

I’ve included Wickr on this list because I’ve seen it mentioned in a handful of respectable media outlets over the past few months. This means that people are either using Wickr, or that Wickr has very good PR folks. I also included it because it was at least partially designed by Dan Kaminsky, who generally knows his stuff.

Unfortunately I can’t say too much about Wickr because — to date — there’s virtually no technical information available on it. (Not even a white paper!) However, based on Tweets with Dan and this short post on the LiberationTech mailing list, I believe that Wickr uses a centralized directory server to share keys. In theory this could be ok if it provided a mechanism to compare key fingerprints between users, and/or detect invalid keys. But currently this does not seem to be the case.

As for the destruction of secrets, well, this does seem like a nice idea, particularly if the destruction is enforced cryptographically. Unfortunately this is a fundamentally hard problem to solve correctly: if I can get a copy of your phone’s memory while the message is there, I can keep the message forever.

Overall code quality: Who knows.

Crypto: Current versions use some kind of RSA-based key agreement. According to Dan, the next generation will use elliptic curve crypto with perfect forward secrecy. But the real horses head is the (apparent) reliance on a central directory server, which makes the service much more vulnerable to MITM.

Ease of use: Very easy. Just set your message expiration date, key in the destruct time, and send away.

Should I use this to fight my oppressive regime? Yes, as long your fight consists of sending naughty self-portraits to your comrades-at-arms. Otherwise, probably not.

In summary

If you’ve made it this far, I’m guessing you still have one burning question. Namely: What app should I use if I’m trying to overthrow my government?

The simple answer is that I just don’t know. It’s not an easy question.

Each of the above apps seem quite good, cryptographically speaking. But that’s not the problem. The real issue is that they each run on a vulnerable, networked platform. If I really had to trust my life to a piece of software, I would probably use something much less flashy — GnuPG, maybe, running on an isolated computer locked in a basement.

Then I would probably stay locked in the basement with it.

But not everyone is a coward like me. The widespread availability of smartphones has already changed the way people interact with their government. These encryption apps could well be the first wave in an entirely new revolution — one that makes truly private communication a reality.

Notes:

* Some services actually know and store your private keys, while others operate as a Certificate Authority, allowing you to ‘certify’ new public keys under your name. Either of these models makes eavesdropping relatively easy for someone with access to the server.

Why I hate CBC-MAC

If you’re like most people, you don’t have a strong opinion about CBC-MAC. In fact, if you’re like most people, you don’t have a strong opinion about any crypto primitive.

This is healthy. Keep up the good work.

I’m not most people. I’ve spent the last week thinking about and dealing with CBC-MAC — or more specifically, code that uses it in various contexts — and I need to share with you how much I despise this little algorithm. And beg you never to use it.

Oh yes, I know the temptation. You have this nice block cipher just sitting around — maybe you’re encrypting something — and you’ve heard how serious this whole message authentication thing is. Maybe you’ve even thought about using one of those fancy authenticated encryption modes, but found them to be too exotic and complicated.

Then it comes to you that all your problems would be solved if you just used CBC-MAC. This is too bad, because now your troubles are just beginning.

Now a quick note: there’s nothing really wrong with CBC-MAC, when implemented correctly. And it’s not even that hard to implement properly. The problem is that many people who use CBC-MAC (rather than HMAC or a proper AEAD mode) seem incapable of actually doing this. They get it wrong in hilariously, embarassingly, stupid, complicated ways.

But of course you wanted examples. Ok, let’s give some.

1. Your implementation doesn’t handle variable-length messages.

A quick reminder. CBC-MAC is very similar to the classic CBC mode for encryption, with a few major differences. First, the Initialization Vector (IV) is a fixed value, usually zero. Second, CBC-MAC only outputs the last block of the ciphertext — this single value forms the MAC.

Many dumb implementations stop here. And that leads to big problems.

Most notably, if your system allows for variable-length messages — as it should — there is a simple attack that allows you to forge new messages. First, get a MAC T on a message M1. Now XOR the tag T into the first block of some arbitrary second message M2, and get a MAC on the modified version of M2.

The resulting tag T’ turns out to be a valid MAC for the combined message (M1 || M2). This is a valid forgery, and in some cases can actually be useful.

The standard fix to prepend the message length to the first block of the message before MACing it. But a surprisingly large number of (dumb) implementations skip this extra step. And many CBC-MAC implementations are dumb implementations.

2. Your implementation uses a random Initialization Vector.

If CBC-MAC with a fixed IV is great, surely CBC-MAC with a random IV must be super-great. But no, it isn’t.

Using a random (or variable IV) is bad for the simple reason that verifying a CBC-MAC requires you to know the IV, and to know the IV you probably need to read it from somewhere. Typically this means the same untrusted place where you were storing your message.

If the attacker can change the CBC-MAC IV, they can also change the first block of the MACed message in an equivalent manner. This works because the first step of CBC-MAC is to XOR the IV with the message. There are all kinds of silly variants of this problem, and all of them hurt.

3. You’ve used the same key for MAC and encryption.

A general rule in cryptography is that you shouldn’t use the same key for two different cryptographic primitives — encryption and signature, for example. Or encryption and MAC.

Some people figure that rules were made to be broken.

Note that shared keys can actually be ok, in some cases. Combined modes like CCM (short for CTR + CBC-MAC) actually do use the same key for both operations. However, these modes do it in a very careful, thoughtful manner. Your garden-variety implementation doesn’t.

One particularly ugly pattern I’ve seen is to use (dumb) CBC-MAC on a plaintext, then to encrypt said plaintext in CTR mode using some initial counter (C). This is insecure for a bunch of reasons, but specifically because I might be able to completely decrypt your ciphertext.

To do this, I simply ask you to encrypt a series of small files corresponding to the counter values C, C+1, etc. of the ciphertext I want to attack. The CBC-MAC of each of these files lets me recreate the CTR-mode keystream I need to decrypt the original ciphertext. Now I have your message.

4. You’ve used CBC-MAC as a hash function.

This one isn’t really a problem with CBC-MAC, but it does crop up. In fact, it happened recently to the file sharing site Mega.

To make a long story short: cryptographic hash functions are public functions (i.e., no secret key) that have the property of collision-resistance (it’s hard to find two messages with the same hash). MACs are keyed functions that (typically) provide message unforgeability — a very different property. Moreover, they guarantee this only when the key is secret.

If you attempt to use CBC-MAC with a non-secret key, it becomes a very bad candidate for anything. In fact, you can trivially find useful collisions in the output, something that’s very bad if you’re using it to authenticate code. Which is what Mega was doing with it.

This isn’t true of all MACs — HMAC, for example, should retain the collision resistance of the underlying hash function even if the MAC key is compromised. This is yet another reason to prefer it for cases where cryptographic expertise is not a sure bet.

In summary

I’ll repeat that none of these are really problems with CBC-MAC, which is a perfectly lovely algorithm if implemented and used correctly. The problems above only crop up when people try to whip it up themselves, without using a standard construction.

If you must write your own code, my recommendation is to use HMAC — which is extremely hard to screw up. If you’re doing combined encryption/MAC and you only have a block cipher, then look into the CCM spec, which is a patent free AEAD mode. This should address all of these problems and give you some nice test vectors too.

What you shouldn’t do is code up some half-assed CBC-MAC thing and expect you’ll be ok. The fact is, you probably won’t.

Attack of the week: TLS timing oracles

Ever since I started writing this blog (and specifically, the posts on SSL/TLS) I’ve had a new experience: people come up to me and share clever attacks that they haven’t made public yet.

This is pretty neat — like being invited to join an exclusive club. Unfortunately, being in this club mostly sucks. That’s because the first rule of ‘TLS vulnerability club’ is: You don’t talk about TLS vulnerability club. Which takes all the fun out of it.

(Note that this is all for boring reasons — stuff like responsible disclosure, publication and fact checking. Nobody is planning a revolution.)

Anyway, it’s a huge relief that I’m finally free to tell you about a neat new TLS attack I learned about recently. The new result comes from Nadhem AlFardan and Kenny Paterson of Royal Holloway. Dubbed ‘Lucky 13’, it takes advantage of a very subtle bug in the way records are encrypted in the TLS protocol.

If you aren’t into long crypto posts, here’s the TL;DR:

There is a subtle timing bug in the way that TLS data decryption works when using the (standard) CBC mode ciphersuite. Given the right set of circumstances, an attacker can use this to completely decrypt sensitive information, such as passwords and cookies. 

The attack is borderline practical if you’re using the Datagram version of TLS (DTLS). It’s more on the theoretical side if you’re using standard TLS. However, with some clever engineering, that could change in the future. You should probably patch!

For the details, read on. As always, we’ll do this in the ‘fun’ question/answer format I save for these kinds of posts.

What is TLS, what is CBC mode, and why should I care if it’s broken?

Some background: Transport Layer Security (née SSL) is the most important security protocol on the Internet. If you find yourself making a secure connection to another computer, there’s a very good chance you’ll be doing it with TLS. (Unless you’re using UDP-based protocol, in which case you might use TLS’s younger cousin Datagram TLS [DTLS]).

The problem with TLS is that it kind of stinks. Mostly this is due to bad decisions made back in the the mid-1990s when SSL was first designed. Have you seen the way people dressed back then? Protocol design was worse.

While TLS has gotten better since then, it still retains many of the worst ideas from the era. One example is the CBC-mode ciphersuite, which I’ve written about several times before on this blog. CBC-mode uses a block cipher (typically AES) to encrypt data. It’s the most common ciphersuite in use today, probably because it’s the only mandatory ciphersuite given in the spec.

What’s wrong with CBC mode?

The real problem with TLS is not the encryption itself, but rather the Message Authentication Code (MAC) that’s used to protect the integrity (authenticity) of each data record.

Our modern understanding is that you should always encrypt a message first, then apply the MAC to the resulting ciphertext. But TLS gets this backwards. Upon encrypting a record, the sender first applies a MAC to the plaintext, then adds up to 255 bytes of padding to get the message up to a multiple of the cipher (e.g., AES’s) block size. Only then does it CBC-encrypt the record.

Structure of a TLS record. The whole thing is encrypted with CBC mode.

The critical point is that the padding is not protected by the MAC. This means an attacker can tamper with it (by flipping specific bits in the ciphertext), leading to a very nasty kind of problem known as a padding oracle attack.

In these attacks (example here), an attacker first captures an encrypted record sent by an honest party, modifies it, then re-transmits it to the server for decryption. If the attacker can learn whether her changes affected the padding — e.g., by receiving a padding error as opposed to a bad MAC error — she can use this information to adaptively decrypt the whole record. The structure of TLS’s encryption padding makes it friendly to these attacks.

Closeup of a padded TLS record. Each byte contains the padding length, followed by another (pointless, redundant) length byte.

But padding oracle attacks are well known, and (D)TLS has countermeasures!

The TLS designers learned about padding oracles way back in 2002, and immediately took steps to rectify them. Unfortunately, instead of fixing the problem, they decided to apply band-aids. This is a time-honored tradition in TLS design.

The first band-aid was simple: eliminate any error messages that could indicate to the attacker whether the padding check (vs. the MAC check) is what caused a decryption failure.

This seemed to fix things for a while, until some researchers figured out that you could simply time the server to see how long decryption takes, and thereby learn if the padding check failed. This is because implementations of the time would first check the padding, then return immediately (without checking the MAC) if the padding was bad. That resulted in a noticeable timing differential the attacker could detect.

Thus a second band-aid was needed. The TLS designers decreed that decryption should always take the same amount of time, regardless of how the padding check comes out. Let’s roll the TLS 1.2 spec:

[T]he 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.

Yuck. Does this even work?

Unfortunately, not quite. When the padding check fails, the decryptor doesn’t know how much padding to strip off. That means they don’t know how long the actual message is, and therefore how much data to MAC. The recommended countermeasure (above) is to assume no padding, then MAC the whole blob. As a result, the MAC computation can take a tiny bit longer when the padding is damaged.

The TLS designers realized this, but by this point they were exhausted and wanted to go think about something else. So they left us with the following note:

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.

And for the last several years — at least, as far as we know — they were basically correct.

How does this new paper change things?

The new AlFardan and Paterson result shows that it is indeed possible to distinguish the tiny timing differential caused by invalid padding, at least from a relatively close distance — e.g., over a LAN. This is partly due to advances in computing hardware: most new computers now ship with an easily accessible CPU cycle counter. But it’s also thanks to some clever statistical techniques that use many samples to smooth out and overcome the jitter and noise of a network connection.

The upshot is that new technique can measure timing differentials of less than 1 microsecond over a LAN connection — for example, if the attacker is in the same data center as your servers. It does this by making several thousand decryption queries and processing the results. Under the right circumstances, this turns out to be enough to bring (D)TLS padding oracle attacks back to life.

How does the attack work?

For the details, you should obviously read the full paper or at least the nice FAQ that Royal Holloway has put out. Here I’ll try to give some intuition.

Before I can explain the attack, you need to know a little bit about how hash-based MACs work. TLS typically uses HMAC with either MD5, SHA1 or SHA256 as the hash function. While these are very different hash functions, the critical point is that each one processes messages in 64-byte blocks.

Consequently, hashing time is a function of the number of blocks in the message, not the number of bytes. Going from a 64-byte input to a 65-byte input means an entire extra block, and hence a (relatively) large jump in the amount of computation time (an extra iteration of the hash function’s compression function).

There are a few subtleties in here. The hash functions incorporate an 8-byte length field plus some special hash function padding, which actually means a one-block message can only contain about 55 bytes of real data (which also includes the 13-byte record header). The HMAC construction adds a (constant) amount of additional work, but we don’t need to think about that here.

So in summary: you can get 55 bytes of data into one block of the hash. Go a single byte beyond that, and the hash function will have to run a whole extra round, causing a tiny (500-1000 hardware cycle) delay.

The attack here is to take a message that — including the TLS padding — would fall above that 55 byte boundary. However, the same message with padding properly removed would fall below it. When an attacker tampers with the message (damaging the padding), the decryption process will MAC the longer version of the message — resulting in a measurably higher computation time than when the padding checks out.

By repeating this process many, many thousand (or millions!) of times to eliminate noise and network jitter, it’s possible to get a clear measurement of whether the decryption succeeded or not. Once you get that, it’s just a matter of executing a standard padding oracle attack.

But there’s no way this will work on TLS! It’ll kill the session!

Please recall that I described this as a practical attack on Datagram TLS (DTLS) — and as a more theoretical one on TLS itself.* There’s a reason for this.

The reason is that TLS (and not DTLS) includes one more countermeasure I haven’t mentioned yet: anytime a record fails to decrypt (due to a bad MAC or padding error), the TLS server kills the session. DTLS does not do this, which makes this attack borderline practical. (Though it still takes millions of packet queries to execute.)

The standard TLS ‘session kill’ feature would appear to stop padding oracle attacks, since they require the attacker to make many, many decryption attempts. Killing the session limits the attacker to one decryption — and intuitively that would seem to be the end of it.

But actually, this turns out not to be true.

You see, one of the neat things about padding oracle attacks is that they can work across different sessions (keys), provided that that (a) your victim is willing to re-initiate the session after it drops, and (b) the secret plaintext appears in the same position in each stream. Fortunately the design of browsers and HTTPS lets us satisfy both of these requirements.

  1. To make a target browser initiate many connections, you can feed it some custom Javascript that causes it to repeatedly connect to an SSL server (as in the CRIME attack). Note that the Javascript doesn’t need to come from the target webserver — it can even served on an unrelated non-HTTPS page, possibly running in a different tab. So in short: this is pretty feasible.
  2. Morover, thanks to the design of the HTTP(S) protocol, each of these connections will include cookies at a known location in HTTP stream. While you may not be able to decrypt the rest of the stream, these cookie values are generally all you need to break into somebody’s account.

Thus the only practical limitation on such a cookie attack is the time it takes for the server to re-initiate all of these connections. TLS handshakes aren’t fast, and this attack can take tens of thousands (or millions!) of connections per byte. So in practice the TLS attack would probably take days. In other words: don’t panic.

On the other hand, don’t get complacent either. The authors propose some clever optimizations that could take the TLS attack into the realm of the feasible (for TLS) in the near future.

How is it being fixed?

With more band-aids of course!

But at least this time, they’re excellent band-aids. Adam Langley has written a 500-line OpenSSL patch (!) that modifies the CBC-mode decryption procedure to wipe out the timing differentials used by this attack. I would recommend that you think about updating at least your servers in the future (though we all know you won’t). Microsoft products should also see updates soon are allegedly not vulnerable to this attack, so won’t need updates.**

Still, this is sort of like fixing your fruitfly problem by spraying your kitchen with DDT. Why not just throw away the rotted fruit? In practice, that means moving towards modern AEAD ciphersuites like AES-GCM, which should generally end this madness. We hope.

Why not switch to RC4?

RC4 is not an option in DTLS. However, it will mitigate this issue for TLS, since the RC4 ciphersuite doesn’t use padding at all. In fact, this ancient ciphersuite has been (hilariously) enjoying a resurgence in recent years as the ‘solution’ to TLS attacks like BEAST. Some will see this attack as further justification for the move.

But please don’t do this. RC4 is old and creaky, and we really should be moving away from it too.

So what’s next for TLS?

I’d love to say more, but you see, the first rule of TLS vulnerability club is…

Notes:

* The attack on Datagram TLS is more subtle, and a lot more interesting. I haven’t covered it much in this post because TLS is much more widely used than DTLS. But briefly, it’s an extension of some previous techniques — by the same authors — that I covered in this blog last year. The gist is that an attacker can amplify the impact of the timing differential by ‘clogging’ the server with lots of unrelated traffic. That makes these tiny differentials much easier to detect.

** And if you believe that, I have a lovely old house in Baltimore to sell you…

In defense of Provable Security

It’s been a long time with no blogging, mostly thanks to travel and deadlines. In fact I’m just coming back from a workshop in Tenerife, where I learned a lot. Some of which I can’t write about yet, but am really looking forward to sharing with you soon.

During the workshop I had some time to talk to Dan Bernstein (djb), and to hear his views on the relevance of provable security. This is a nice coincidence, since I notice that Dan’s slides have been making the rounds on Twitter — to the general approval of some who, I suspect, agree with Dan because they think that security proofs are hard.

The problem here is that this isn’t what Dan’s saying. Part of the issue is that his presentation is short, so it’s easy to misinterpret his position as a call to just start designing cryptosystems the way we design software. That’s not right, or if it is: get ready for a lot of broken crypto.

This post is my attempt to explain what Dan’s saying, and then (hopefully) convince you he’s not recommending the crazy things above.

There’s no such thing as a “security proof”

Dan’s first point is that we’re using the wrong nomenclature. The term ‘security proof’ is misleading in that it gives you the impression that a scheme is, well… provably secure. There aren’t many schemes that can make this claim (aside from the One-Time Pad). Most security proofs don’t say this, and that can lead to misunderstandings.

The proofs that we see in day-to-day life are more accurately referred to as security reductions. These take something (like a cryptographic scheme) and reduce its security to the hardness of some other problem — typically a mathematical problem, but sometimes even another cryptosystem.

A classic example of this is something like the RSA-PSS signature, which is unforgeable if the RSA problem is hard, or Chaum-van Heijst-Pfitzmann hashing, which reduce to the hardness of the Discrete Logarithm problem. But there are more complex examples like block cipher modes of operation, which can often be reduced to the (PRP) security of a block cipher.

So the point here is that these proofs don’t actually prove security — since the RSA problem or Discrete Log or block cipher could still be broken. What they do is allow us to generalize: instead of analyzing many different schemes, we can focus our attention one or a small number of hard problems. In other words, it’s a different — and probably much better — way to allocate our (limited) cryptanalytic effort.

But we don’t study those problems well, and when we do, we break them

Dan argues that this approach is superficially appealing, but concretely it can be harmful. Take the Chaum et al. hash function listed above. Nobody should ever use this thing: it’s disastrously slow and there’s no solid evidence that it’s truly more secure than something like SHA-3 or even SHA-3’s lamest competitors.

And here (unfortunately) he’s got some evidence on his side: we’ve been amazingly unsuccessful at cryptanalyzing complex new cipher/hash primitives like AES, BLAKE and Keccak, despite the fact that these functions don’t have [real] security proofs. Where we make cryptanalytic progress, it’s almost always on first-round competition proposals, or on truly ancient functions like MD5. Moreover, if you take a look at ‘provably-secure’ number theoretic systems from the same era, you’ll find that they’re equally broken — thanks to bad assumptions about key and parameter sizes.

We’ve also gotten pretty good at chipping away at classic problems like the Discrete Logarithm. The charitable interpretation is that this is a feature, not a bug — we’re focusing cryptanalytic effort on those problems, and we’re making progress, whereas nobody’s giving enough attention to all these new ciphers. The less charitable interpretation is that the Discrete Logarithm problem is a bad problem to begin with. Maybe we’re safer with unprovable schemes that we can’t break, then provable schemes that seem to be slowly failing.

You need a cryptanalyst…

This is by far the fuzziest part (for me) of what Dan’s saying. Dan argues that security proofs are a useful tool, but they’re no substitute for human cryptanalysis. None of which I would argue with at all. But the question is: cryptanalysis of what?

The whole point of a security reduction is to reduce the amount of cryptanalysis we have to do. Instead of a separate signature and encryption scheme to analyze, we can design two schemes that both reduce to the RSA problem, then we can cryptanalyze that. Instead of analyzing a hundred different authenticated cipher modes, we can simply analyze one AES — and know that OCB and GCM and CBC and CTR will all be secure (for appropriate definitions of ‘secure’).

This is good, and it’s why we should be using security proofs. Not to mislead people, but to help us better allocate our very scarce resources — of smart people who can do this work (and haven’t sold out to the NSA).

…because people make mistakes

One last point: errors in security proofs are pretty common, but this isn’t quite what Dan is getting at. We both agree that this problem can be fixed, hopefully with the help of computer-aided proof techniques. Rather, he’s concerned that security proofs only prove that something is secure within a given model. There are  many examples of provably-secure schemes that admit attacks because those attacks were completely outside of that threat model.

As an example, Dan points to some older EC key agreement protocols that did not explicitly include group membership tests in their description. Briefly, these schemes are secure if the attacker submits valid elements of an elliptic curve group. But of course, a real life attacker might not. The result can be disastrously insecure.

So where’s the problem here? Technically the proof is correct — as long as the attacker submits group elements, everything’s fine. What the protocol doesn’t model is the fact that an attacker can cheat — it just assumes honesty. Or as Dan puts it: ‘the attack can’t even be modeled in the language of the proof’.

What Dan’s not saying

The one thing you should not take away from this discussion is the idea that security proofs have no value. What Dan is saying is that security proofs are one element of the design process, but not 100% of it. And I can live with that.

The risk is that some will see Dan’s talk as a justification for using goofy, unprovable protocols like PKCS#1v1.5 signature or the SRP password protocol. It’s not. We have better protocols that are just as well analyzed, but actually have a justification behind them.

Put it this way: if you have a choice between driving on a suspension bridge that was designed using scientific engineering techniques, and one that simply hasn’t fallen down yet, which one are you going to take? Me, I’ll take the scientific techniques. But I admit that scientifically-designed bridges sometimes do fall down.

In conclusion

While I’ve done my best to sum up Dan’s position, what I’ve written above is probably still a bit inaccurate. In fact, it’s entirely possible that I’ve just constructed a ‘strawman djb’ to argue with here. If so, please don’t blame me — it’s a whole lot easier to argue with a straw djb than the real thing.

Surveillance works! Let’s have more of it.

If you care about these things, you might have heard that Google recently detected and revoked a bogus Google certificate. Good work, and huge kudos to the folks at Google who lost their holidays to this nonsense.

From what I’ve read, this particular incident got started in late 2011 when Turkish Certificate Authority TURKTRUST accidentally handed out intermediate CA certificates to two of their customers. Intermediate CA certs are like normal SSL certs, with one tiny difference: they can be used to generate other SSL certificates. Oops.

One of the recipients noticed the error and reported it to the CA. The other customer took a different approach and installed it into an intercepting Checkpoint firewall to sniff SSL-secured connections. Because, you know, why not.

So this is bad but not exactly surprising — in fact, it’s all stuff we’ve seen before. Our CA system has far too many trust points, and it requires too many people to act collectively when someone proves untrustworthy. Unless we do something, we’re going to see lots more of this.

What’s interesting about this case — and what leads to the title above — is not so much what went wrong, but rather, what went right. You see, this bogus certificate was detected, and likely not because some good samaritan reported the violation. Rather, it was (probably) detected by Google’s unwavering surveillance.

The surveillance in question is conducted by the Chrome brower, which actively looks out for attacks and reports them. Here’s the money quote from their privacy policy:

“If you attempt to connect to a Google website using a secure
connection, and the browser blocks the connection due to information
that indicates you are being actively attacked by someone on the
network (a “man in the middle attack”), Chrome may send information
about that connection to Google for the purpose of helping to
determine the extent of the attack and how the attack functions.”

The specific technical mechanism in Chrome simple: Chrome ships with a series of ‘pins’ in its source code (thanks Moxie, thanks Tom). These tell Chrome what valid Google certificates should look like, and help it detect an obviously bogus certificate. When Chrome sees a bogus cert attached to a purported Google site, it doesn’t just stop the connection, it rings an alarm at Google HQ.

And that alarm is a fantastic thing, because in this case it may have led to discovery and revocation before this certificate could be stolen and used for something worse.

Now imagine the same thing happening in many other browsers, and not just for Google sites. Well, you don’t have to imagine. This is exactly the approach taken by plugins like Perspectives and Convergence, which monitor users’ SSL connections in a distributed fashion to detect bogus certificates. These plugins are great, but they’re not deployed widely enough. The technique should be standard in all browsers, perhaps with some kind of opt in. (I certainly would opt.)

The simple fact is that our CA system is broken and this is what we’ve got. Congratulations to Google for taking a major first step in protecting its users. Now let’s take some more.

The anatomy of a bad idea

I’ve been running a fever all day and am only coming back to my senses now, thanks to a huge (and possibly toxic) dose of Motrin. Sometimes when you’re under the weather, things kind of blur together. This is probably why I can only recall two things I read this afternoon.

The first was a news story concerning a series of tests in which the US government dropped nuclear bombs on a variety of canned beverages, apparently to see how well they held up (but possibly just because they had some nukes). The second was the W3C Web Cryptography API, a draft Javascript crypto API that will ultimately power a lot of the crypto we use on the web.

Even in my addled state, I can tell that only one of these things is a good idea.

(In case you’re still guessing, here’s a hint: we’ll still need beer after the bombs fall.)

Before I go further, let me be clear: I think the web absolutely should have a secure browser-based crypto API! My problem is that I can’t bear to watch the W3C screw it up. Because screw it up they absolutely will. The W3C, bless their sweet little hearts, has left a trail of wreckage behind every crypto project they’ve ever taken on. And these were small projects!

The Web Crypto API is far more ambitious, which means it will blow up that much more spectacularly when it goes. And unfortunately, the W3C contributors seem immune to all attempts to disuade them from this course.

So what is it?

The Web Cryptography API (henceforth WC-API) is a perfectly lovely idea: to build a standard Javascript API for doing crypto on the web. In theory it’ll be supported by lots of browsers and will include all the logic you need to manage keys securely and perform common cryptographic operations. Things like encryption, signing, etc.

This can’t be deployed soon enough — if it’s done right. The problem with current Javascript implementations is that they’re really bad at managing keys securely, and the crypto implementations are frequently ad-hoc, slow, and vulnerable to side-channel attacks. A common API should allow us to do much, much better.

But at the same time we need to recognize that cryptography is hard (seriously: this should be the name of my blog.) Moreover, Javascript development is — no offense — the last place we want people making hard cryptographic decisions. Decisions like, for example, ‘should I use the obsolete and very broken PKCS#1v1.5 encryption padding scheme in my protocol?’ These are things that very few people need to think about, and most people who are thinking about them are going to make the wrong choice.

Two visions

This is not a new argument. For two competing visions of how a cryptography library should work, consider two existing libraries: OpenSSL and NaCl. OpenSSL is the grand old lady of cryptography, ‘beloved’ by millions. Actually OpenSSL isn’t a crypto library except by accident — it’s an SSL library that happens to expose a bunch of underlying crypto routines. NaCl is much newer and basically tries to repair the damage wrought by OpenSSL.

If we must resort to analogies, let’s try these: OpenSSL is the space shuttle of crypto libraries. It will get you to space, provided you have a team of people to push the ten thousand buttons required to do so. NaCl is more like an elevator — you just press a button and it takes you there. No frills or options.

I like elevators.

Now obviously there are different reasons to take the space shuttle. Sometimes you need to go to places that aren’t supported by the buttons on an elevator. But you’d better know exactly what you’re doing, because making a mistake on the space shuttle is not something you get to do twice.

More concretely, NaCl takes the position that most users don’t need their crypto to be backwards compatible with other systems, and instead provides a simplified abstraction in the form of the ‘crypto_box‘ operation. This abstracts all the messy details of public and secret key cryptography into a single secure function call. This approach may seem a bit extreme, but it’s also sufficient for a huge amount of what most people need to get done when they’re encrypting things.

WC-API does not adhere to the NaCl vision. Instead, it follows in the OpenSSL tradition. Here the basic unit is the crypto primitive, which can be selected from a menu provided by the designers. This menu includes some pretty solid primitives like RSA-OAEP, ECDH and AES-GCM, but it also includes ridiculous stuff that should be banned from the universe — things like the aforementioned RSA-PKCS#1v1.5 (signature and encryption) padding as well as several unauthenticated symmetric modes of operation. Worse, some of the bad primitives are also the recommended ones.

The user has to pick the right ones, generate the right keys, and hopefully (god bless) tie them all together without running afoul of the various practical attacks that they’ll be victim to when they make the wrong choice.

Some will do this. Some will not.

But maybe you’re just being too sensitive…?

This is possible, but gosh, don’t take my word for it. If you think I’m just blowing smoke, please at least listen to IETF Crypto Forum Research Group representatives Kenny Paterson, Tibor Jager and Juraj Somorovsky when they say exactly the same things as me but in scarier language:

We noted that the standard contains some legacy crypto algorithms,
which have well-known serious weaknesses but are (unfortunately) still
widely used. These weaknesses frequently lead to attacks on systems
that naively use these algorithms.

For instance, several works [Ble98,BFKST12,JSS12, …] demonstrate the
vulnerability of RSA PKCS#1 v1.5 to variants of Bleichenbacher’s
attack in various (practical and widely-used) applications. Using
PKCS#1 v1.5 in a secure way is highly non-trivial and often
impossible, in particular in Web-based applications. Moreover, it is
known that the pure availability of PKCS#1 v1.5 encryption may also
spoil the security of other algorithms, like RSA-OAEP or
RSASSA-PKCS1-v1_5 signatures.

Similarly, unauthenticated block-cipher modes of operation, like CTR
and CBC, have in the past been shown to enable “padding-oracle”-like
attacks, for instance in [Vau02,DR’10,DR’11,JS’11,AP’12, …]. These
modes of operation should not be used without additional security
measures. An appropiate measure is a message authentication code,
which should be computed over the ciphertext and must be verified by
the receiver.

Actually we would like to recommend that these legacy ciphers are
removed from the standard. While in some special cases countermeasures
against the known attacks are possible, implementing these is highly
non-trivial and error-prone, thus much harder than implementing new
libraries supporting secure algorithms. Even worse, in many examples
there exists no countermeasure.

What about backwards compatibility?

Yes, I concede that there may occasionally be times when your Javascript needs to decrypt a message that was encrypted by some other, archaic piece of crypto software. And for those times there really is a need to support some of the obsolete crypto schemes provided in the current W3C specification. But “support” is not the same as “provide in your mainline API”.

Unfortunately, several proposals to separate the older algorithms into a different namespace have been shot down, as have proposals to strongly warn users against the bad algorithms. I can’t see any justification for these decisions, except that possibly there is a God and he wants cryptographers/pentesters to stay busy for the next few years.

So what does it all mean?

A while ago on Twitter somebody asked why I spend so much time criticizing things that are old and broken, rather than making things new and shiny. When I finished sputtering, I realized that the answer is simple: I’m lazy.

But that’s ok, because the truth is, most software developers are too. Not in a bad way, but simply in the sense that we want to get from point A to point B without being distracted by a lot of useless garbage. Give us a way to get between those two points and we’ll do it with alacrity. Make us understand that PKCS#1v1.5 is universally insecure unless you use it in a very particular way (that’s documented almost nowhere), and that even this relies on some pretty unusual assumptions — and you’ll tend to find a lot of people just making mistakes.

And in case this is all too doom-and-gloom for you, here’s a parting thought to cheer you up. No matter how bad this API turns out to be, at least we don’t have to drink it.

—

Update (12/30): A few people have criticized this post on the grounds that I should join the WebCrypto WG rather than complaining about it. Usually the implication is that I’m after blog hits.

The short answer is: if I really wanted blog hits, I wouldn’t be bitching about an obscure web standard! I’d be complaining about Apple. I speak from experience here.

The longer response is that many bright folks in and outside of the WG have made these points (see the CFRG note above). Their input has been respectfully considered and rejected. My impression is that we’re not dealing with a lack of knowledge here, but rather a more fundamental difference in approach. The WG has made an institutional decision to emphasize backwards compatibility over security. This works if you’re designing a standard and hoping to get it adopted quickly. It just doesn’t lead to a good standard.

I think there’s a certain kind of person who has the time and political skills to fix this kind of organizational problem, and I sincerely hope that person gets involved. But sadly, that person is not me.

Let’s talk about ZRTP

I just checked the date on my last post and it seems that I haven’t blogged in nearly a month. Believe me, this isn’t for lack of trying. The world has just been a very, very busy place.

But this is the Thanksgiving holiday and every (US) American knows the best part of Thanksgiving is sitting around for hours waiting for a huge bird to cook thoroughly enough that it won’t kill your family. And that means I finally have time to write about my favorite wonky topic: cryptographic protocols. And how utterly confusing they can be.

ZRTP

The subject of today’s post is the ZRTP key agreement protocol. ZRTP has recently gotten some press for being the primary key agreement used by Silent Circle, a new encrypted voice/video/text service launched by PGP inventor Phil Zimmermann and some other bright folks. But it’s also used in other secure VoIP solutions, like Zfone and Moxie’s RedPhone.

Silent Circle’s an interesting case, since it’s gotten some gentle criticism lately from a variety of folks — well, mostly Nadim Kobeissi — for being partially closed-source and for having received no real security audits. Nadim’s typical, understated critique goes like this:

And is usually followed by the whole world telling Nadim he’s being a jerk. Eventually a tech reporter notices the fracas and chimes in to tell us the whole Infosec community is a bunch of jerks:

And the cycle repeats, without anyone having actually learned much at all. (Really, it’s enough to make you think Twitter isn’t the right place to get your Infosec news.)

Now, as unhelpful as all this is, maybe we can make lemonade and let all of this serve as a teaching moment. For one thing, it gives us a (wonky) chance to learn a little bit about this ZRTP protocol that so many people seem to be using.

Overview of ZRTP

The ZRTP protocol is fully laid out in RFC 6189. This is one of the more confusing specs I’ve read — partly because the critical information is spread out across so many different sections, and partly because ZRTP seems determined to address every possible attack simultaneously.

Fortunately the Intro does a good job of telling us what the protocol’s up to:

ZRTP is a key agreement protocol that performs a Diffie-Hellman key exchange during call setup in the media path and is transported over the same port as the Real-time Transport Protocol (RTP) media stream which has been established using a signaling protocol such as Session Initiation Protocol (SIP). This generates a shared secret, which is then used to generate keys and salt for a Secure RTP (SRTP) session.

So: simple enough. ZRTP lets us establish keys over an insecure channel using Diffie-Hellman.

However we all know that Diffie-Hellman isn’t secure against active (Man-in-the-Middle) attacks. Normally we prevent these by signing Diffie-Hellman messages using keys distributed via a PKI. ZRTP is having none of it:

Although it uses a public key algorithm, [ZRTP] does not rely on a public key infrastructure (PKI) … [ZRTP] allows the detection of man-in-the-middle (MiTM) attacks by displaying a short authentication string (SAS) for the users to read and verbally compare over the phone. … But even if the users are too lazy to bother with short authentication strings, we still get reasonable authentication against a MiTM attack, based on a form of key continuity. It does this by caching some key material to use in the next call, to be mixed in with the next call’s DH shared secret, giving it key continuity properties analogous to Secure SHell (SSH).

So our protection is twofold: (1) every time we establish a connection with some remote party, we can verbally compare a “short authentication string” (SAS) to ensure that we’ve both agreed on the same key. Assuming that our attacker isn’t a voice actor, this should let us easily detect a typical MiTM. And just in case we’re too lazy to bother with this, even completing one ‘un-attacked’ connection leaves us with (2) a long-term shared secret that we can use to validate future connection attempts.

So is this a reasonable model? Well, you can draw your own conclusions — but it works fine for me. Moreover, I’m willing to accept just about any assumption that allows us to not think about the ‘Bill Clinton’ or ‘Rich Little attacks‘. So let’s just assume that this voice thing works… and move on to the interesting bits.

The Guts of the Protocol

ZRTP is an interaction between two parties, defined as an Initiator and a Responder. This figure from the spec illustrates the flow of a typical transaction:

Note that the identity of the party acting as the Initiator is determined during the protocol run — it’s the one that sends the Commit message (F5). The protocol breaks down into roughly four phases:

  1. Discovery and protocol negotiation (F1-F4), in which the parties start up a protocol transaction and agree on a supported ZRTP version and ciphersuites.
  2. Diffie-Hellman key establishment (F5-F7). This is almost ‘missionary position’ Diffie-Hellman, with one exception (the F5 message), which we’ll talk more about in a second.
  3. Key confirmation (F8-F10), in which the parties verify that they’ve agreed on the same key.
  4. Secure communication. That’s the last section, labeled “SRTP begins”.

Discovery and Protocol Negotiation

Messages F1-F4 are responsible for setting up a ZRTP connection. This stuff is (almost) entirely non-cryptographic, which means this is the part of the protocol where stuff is most likely to go wrong.

Let me explain: prior to completing the Diffie-Hellman key exchange in messages F5-F7, we can’t assume that Alice or Bob share a cryptographic key yet. Without a key, they can’t authenticate their messages — at least not until after the Diffie-Hellman transaction is complete. That means an attacker can potentially re-write any portion of those messages and get away with it. At least for a while.
So what’s in those messages? Well, just a couple of small things:
  1. A 4-character string containing the version of the ZRTP protocol.
  2. A Client Identifier string (cid), which is 4 words long and identifies the vendor and release of the ZRTP software.
  3. The 96-bit-long unique identifier for the ZRTP endpoint (ZID).
  4. A Signature-capable flag (S) indicates this Hello message is sent from a ZRTP endpoint which is able to parse and verify digital signatures.
  5. The MiTM flag (M), which has something to do with PBXes.
  6. The Passive flag (P), which is set to true if and only if this Hello message is sent from a device that is configured to always act as a Responder (not Initiator).
  7. The supported Hash algorithms, Cipher algorithms (including Diffie-Hellman handshake type), SRTP Auth Tag Types, Key Agreement Types, and SAS Types.
Which is to say: quite a lot! And some of these values are pretty critical. Changing the version number might allow an attacker to roll us back to an earlier (potentially insecure) version of the protocol. Changing the ciphers might (theoretically) allow us to switch to a weaker set of Diffie-Hellman parameters, hash function or Short Authentication String algorithm.
At this point a careful protocol reviewer will be asking ‘what does ZRTP does to prevent this?’ ZRTP gives us several answers, both good and not-so-good:
  • On the bad side, ZRTP allows us to send a hash of the Initiator’s Hello message through a separate integrity-protected channel, e.g.,secure SIP. (This protection gets folded on into later messages using a crazy hash-chain and MAC construction.) In general I’m not a fan of this protection — it’s like saying a life-preserver will keep you alive… as long as you have a separate lifeboat to wear it in. If you have a secure channel in the first place, why are you using ZRTP? (Even the ZRTP authors seem a little sheepish about this one.)
  • On the confusing side, Hello messages are MACed using a MAC key that isn’t revealed until the subsequent message (e.g., Commit). In theory this means you can’t forge a MAC until the Commit message has been delivered. In practice, an MiTM attacker can just capture both the Initiator Hello (F3) and the Commit message (F5), learn the MAC key, and then forge the Hello message to its heart’s content… before sending both messages on to the recipient. This entire mechanism baffles me. The less said about it the better.
  • A more reasonable protection comes from the key derivation process. In a later phase of the protocol, both ZRTP parties compute a hash over the handshake messages. This value is folded into the Key Derivation Function (KDF) that’s ultimately to compute session keys. The hashing process looks like:  total_hash = hash(Hello of responder || Commit ||                  DHPart1 || DHPart2)

But… zounds! One important message is missing: the Initiator’s Hello (F3). I can’t for the life of me figure out why this message would be left out. And unless there’s something really clever that I’m missing, this means an attacker can tamper with the Initiator’s Hello message without affecting the key at all.*So is this a problem? Well, in theory it means you could roll back any field in the Initiator Hello message without detection. It’s not exactly clear what practical benefit this would have. You could certainly modify the Diffie-Hellman parameters or ciphers to turn off advanced options like ECDH or 256-bit AES. Fortunately ZRTP does not support ‘export weakened‘ ciphers, so even the ‘weak’ options are pretty strong. Still: this seems like a pretty big oversight, and possibly an unforced error.

For the moment, let’s file it under ‘this protocol is really complicated‘ or ‘don’t analyze protocols at Thanksgiving‘. At very least I think this could use a good explanation.

(Update 11/25: After some back and forth, Moxie points out that the Hash, SAS and Cipher information is repeated in the Commit message [F5], so that should provide an extra layer of protection against rollback on those fields — but not the other fields like version or signature capability. And of course, an implementation might have the Responder prune its list of supported algorithms by basing it off the Initiator’s list, which would be a big problem.)
Diffie-Hellman Key EstablishmentAssuming that the two parties have successfully completed the negotiation, the next phase of the protocol requires the two parties to establish a shared key. This is done using (nearly) straight-up Diffie-Hellman. The parameters are negotiated in the previous phase, and are drawn from a list defined by RFC3526 and a NIST publication.
Normally a Diffie-Hellman agreement would work something like this (all exponentiation is in a group, i.e., mod p):

  1. Alice picks a, sends g^a (message F6).
  2. Bob picks b, sends g^b (message F7).
  3. Both parties compute g^ab and HMAC this value together with lots of other things to derive a session key s0.
  4. The parties further compute a 32-bit Short Authentication value as a function of s0, convert this into a human-readable Short Authentication String (SAS), and compare notes verbally.

The problem with the traditional Diffie-Hellman protocol is that it doesn’t play nice with the Short Authentication String mechanism. Say an MiTM attacker Eve has established a connection with Bob, during which they agreed on SAS value X. Eve now tries to run the Diffie-Hellman protocol with Alice. Once Alice sends her choice of g^a, Eve can now run an offline attack, trying millions of candidate b values until she gets one such that the derived SAS between her and Alice is also X.This is a problem, since Alice and Bob will now see the same SAS, even though Eve is duping them.ZRTP deals with this by forcing one party (Bob) to commit to g^b before the protocol even begins. Thus, in ZRTP Bob picks b and sends H(g^b) before Alice sends her first message. This ‘commitment’ is transmitted in the “Commit” message (F5).

This prevents Bob from ‘changing his mind’ after seeing Alice’s input, and thus the remote party has at most one chance to get a colliding SAS per protocol run. Which means Eve is (probably) out of luck.**

Key Confirmation & Secure Communication

The rest of the protocol does all of the stuff you expect from a key agreement protocol: the two parties, having successfully completed a Diffie-Hellman exchange, now derive a session key by HMACing together the value g^ab with total_hash and any pre-shared secrets they hold from older sessions. If all goes well, the result should be a strong secret that only the two parties know — or an SAS mismatch that reveals Eve’s tampering.

From this point it’s all downhill, or it should be at least. Both parties now have a shared secret that they can use to derive secure encryption and MAC keys. They now construct “Confirm” messages (F8, F9), which they encrypt and (partially) MAC. In principle this exchange gives both parties a chance to detect a mismatch in keys and call the whole thing off.There’s not a ton to say about this section except for one detail: the MAC on these messages is computed only over the encrypted portion (between the == signs below), and leaves out critical details like the Initialization Vector that’s used to encrypt them: ***

Structure of a ZRTP “Confirm” message (source).

Once again it’s not clear if there’s any practical impact here, but at least technically speaking, someone could tamper with this IV and thus change the decryption of the message (specifically, the first 64 bits of H0). I have no idea if this matters — or even if it’s a real attack — but in general it seems like the kind of thing you want to avoid. It’s another example of a place where I just plain don’t understand ZRTP.

Conclusion

I think it should be obvious at this point that I have no real point with this post — I just love protocols. If you’re still reading at this point, you must also love protocols… or else you did something really wrong, and reading this post is your punishment.

ZRTP is a fun protocol to analyze, since it’s a particularly complicated spec that deals with many use-cases at once. Plus it’s an old protocol and it’s been subjected to lots of analysis (including analysis by robots). That’s why I’m so surprised to see loose ends at this date, even if they’re not particularly useful loose ends.

Regardless of the results, anyone who’s interested in cryptography should try their hands at this from time to time. There are so many protocols that we rely on in our day-to-day existence, and far too few of these have really been poked at.

Notes:

* An older paper by Gupta and Shmatikov also notes the lack of authentication for ZID messages, and describes a clever attack that causes the peers to not detect mutually shared secrets. This seems to be fixed in later versions of the protocol, since the ZID values are now included in the Key Derivation Function. But not the rest of the fields in the Initiator Hello.

*** This is another place where the specification is a bit vague. It says that the MAC is computed over the “encrypted part of the message”, but isn’t entirely clear if the MAC is computed pre- or post- encryption. If it’s pre- encryption this is a bit non-standard, but not a major concern.