A Few Thoughts on Cryptographic Engineering

On cellular encryption

2013-05-13T21:19:00.004-07:00

If you're interested in technology/privacy issues then you probably heard last week's big news out of the Boston Marathon case. It comes by way of former FBI agent Tim Clemente, who insists that our government routinely records all domestic phone calls.

Clemente's claim generated lots of healthy skepticism. This isn't because the project is technically infeasible (the numbers mostly add up), or because there's no precedent for warrantless wiretapping. To me the most convincing objection was simple: it'd be hard to keep secret.* Mostly for boring phone company reasons.

But this led to another interesting discussion. What if we forget local phone eavesdropping and focus on an 'easier' problem: tapping only cellular phone calls.

Cellular eavesdropping seems a lot more tractable, if only because mobile calls are conducted on a broadcast channel. That means you can wiretap with almost no carrier involvement. In fact there's circumstancial evidence that this already happening -- just by different parties than you'd think. According to a new book by reporters Marc Ambinder and Dave Brown:

The FBI has quietly removed from several Washington, D.C.–area cell phone towers, transmitters that fed all data to wire rooms at foreign embassies.

This raises a few questions: once you've tapped someone's cellular signals, what do you do with the data? Isn't it all encrypted? And how easy would it be for the US or some foreign government to lay their hands on the plaintext?

All of this which serves as a wonderful excuse to noodle about the state of modern cellular encryption. Be warned that this is not going to be a short post! For those who don't like long articles, here's the TL;DR: cellular encryption is a whole lot worse than you think.

GSM

GSM is the granddaddy of all digital cellular protocols, and it remains of the most popular protocols in the world. One thing that makes GSM special is its call encryption capability: the protocol is designed to encrypt all calls in between the handset and the local tower.

Call encryption is facilitated by a long-term secret key (call it K) that's stored within the tamper-resistant SIM card in your GSM phone. Your carrier also has a copy of this key. When your GSM phone connects to a tower, the parties execute the following authentication and key agreement protocol:

GSM authentication and key agreement protocol (source). MS represents the 'mobile station' (phone) and
HLR is the 'home location register', a central database. The MS and HLR combine a long-term secret Ki
with a random nonce RAND to create the shared communication key Kc. A3 and A8 are
typically implemented using the COMP128 function.

The interaction above serves two purposes: first, both the phone and carrier (HLR) derive a pair of values that will be used for authentication and key agreement. This includes a session key Kc as well as a short authentication token SRES that the phone will use to authenticate itself to the tower. Derivation is performed using two functions (A3 and A8) that accept the long-term secret K and with a random nonce RAND.

There are a handful of well-known problems with the GSM security protocols. In no particular order, they are:

Lack of tower authentication. GSM phones authenticate to the tower, but the tower doesn't authenticate back. This means that anyone can create a 'fake' tower that your phone will connect to. The major problem here is that in GSM, the tower gets to pick the encryption algorithm! That means your attacker can simply turn encryption off (by setting encryption 'algorithm' A5/0) and simply route the cleartext data itself.

In theory your phone is supposed to alert you to this kind of attack, but the SIM chip contains a bit that can de-active the warning. And (as researcher Chris Paget discovered) carriers often set this bit.
Bad key derivation algorithms. The GSM ciphers were developed using the 'make stuff up and pray nobody sees it' school of cryptographic algorithm design. This is a bad approach, since it's incredibly hard to keep algorithms secret -- and when they do leak, they tend to break badly. This was the case for the original A3/A8 algorithms, which are both implemented using single function called COMP128-1. Unfortunately COMP128 turns out to be seriously broken -- to the point where you can clone a user's SIM key in as few as 8 queries.
Bad encryption algorithms. Fortunately it's easy to replace COMP128-1 by swapping out your SIM card. Unfortunately the situation is much worse for GSM's A5/1 call encryption cipher, which is embedded in the hardware of most handsets and tower equipment. A5/1 was leaked around the same time as COMP128 and rapidly succumbed to a series of increasingly powerful attacks. Today it's possible to conduct an efficient known-plaintext attack on A5/1 using a series of rainbow tables you can obtain from BitTorrent. The upshot is that most A5/1 calls can now be decrypted on a high-end PC.
Terrible encryption algorithms. But it's actually worse than that. GSM phones support an 'export weakened' variant called A5/2, which is so weak you can break it in real time. The worst part is that A5/2 uses the same key as A5/1 -- which means an active attacker (see #1 above) can briefly activate the A5/2 mode, crack to recover the encryption key, then switch back to A5/1 with a known key. This is much faster than attacking A5/1 directly, and allows eavesdroppers to intercept incoming phone calls from a legitimate (A5/1 supporting) tower.

Alleged 'Stingray' tracking device
mounted on an SUV (source).

Another unfortunate aspect of the GSM protocol is that you don't need to attack the crypto to do useful things. For example, if all you want to do is determine which devices area in an area, you simply present yourself as a valid tower -- and see which phones connect to you (by sending their IMSI values). This is the approach taken by IMSI-catchers like Stingray.

Now the 'good news' here is that attacks (1), (2) and (4) require active involvement by the attacker. This means they have to be after you specifically and -- at least in principal -- they're detectable if you know what to look for. (You don't.) However, the weaknesses in A5/1 are a whole different kettle of fish. They permit decryption of even passively recorded A5/1 GSM calls (in real time, or after the fact) even to an attacker with modest resources.

3G/4G/LTE

A valid response to the points above is to note that GSM is nearly 30 years old. You probably wouldn't blame today's Ford execs for the crash performance of a 1982 Ford Escort, and similarly you shouldn't hold the GSM designers responsible for a 1980s protocol -- even if billions of people still rely on it.

Overview of the 3G AKA protocol. Look familiar?

The great news is that modern phones often support the improved '3G' (e.g., UMTS) or LTE standards. These offer a bundle of improvements that substantially improve security over the original GSM. These can be summed up as follows:

Mutual authentication. The 3G protocols use a new 'Authentication and Key Agreement' (AKA) protocol, which adds mutual authentication to the tower connection. To validate that the phone is speaking to a legitimate tower, the carrier now computes a MAC that the phone can verify before initiating a connection. This prevents many of the uglier protocol attacks that plagued GSM.
Better authentication algorithms. The session keys and authentication tags are still computed using proprietary algorithms -- now called f1-f5, f5* -- but the algorithms are purportedly much stronger. Since their design is carrier-specific it's not easy to say exactly how they work. However this 3GPP recommendation indicates that they might be based on a block cipher like AES.
Better encryption. Call encryption in 3G uses a proprietary block cipher called KASUMI. KASUMI is based off of a Mitsubishi proposal called MISTY1, which was heavy customized to make it faster in cellular hardware.

The biggest source of concern for 3G/LTE is that you may not be using it. Most phones are programmed to gracefully 'fail over' to GSM when a 3G/4G connection seems unavailable. Active attackers exploit this feature to implement a rollback attack -- jamming 3G/4G connections, and thus re-activating all of the GSM attacks described above.

A more subtle concern is the weakness of the KASUMI cipher. Unfortunately KASUMI seems much weaker than the original MISTY1 algorithm -- so much weaker that in 2010 Dunkelman, Keller and Shamir were able to implement a related-key attack that recovered a full 128 bit call key in just under two hours!

Now before you panic, you should know that executing this attack requires a substantial amount of data, all of which must all be encrypted under highly unrealistic attack conditions. Still, it's interesting to note that the same attack fails completely when applied to the original MISTY1 design.

Top: generation of keys (CK, IK) and authentication tags AUTN, XRES using the functions f1-f5. Bottom: one proposed implementation of those functions using a 128-bit block cipher Ek. This could be AES (source).
And yes, it looks complicated to me, too.

What if you have already the keys?

The encryption flaws above seem pretty significant, and they really are -- if you're a private eavesdropper or a foreign government. For US national security organizations they're probably beside the point. It seems unlikely that the NSA would have to 'break' any crypto at all.

This is because both the GSM and AKA protocols lack an important property known as forward secrecy. What this means is that if I can record an encrypted call, and later obtain the long-term key K for that phone, then I can still reliably decrypt the whole communication -- even months or years later. (Protocols such as Diffie-Hellman or ECMQV prevent this.) Worse, for cellular conversations I can do it even if I only have one half (the tower side) of the communication channel.

Unfortunately I don't think you have to be a conspiracy theorist to suppose that the carriers' key databases are probably stored somewhere in Ft. Meade. Thus to the truly paranoid: stop talking on cellphones.

In conclusion

Sometimes conspiracy theories can be fun. Sometimes they're downright creepy.

For me this discussion veers towards the 'creepy'. Not so much because I think the NSA really is tapping all our cellphones (I suspect they just read our Facebook). Rather, the creepiness is in seeing just how vulnerable our privacy infrastructure is, even to people who are far less capable than the NSA.

As a result, your data isn't just available to nation states: it's also potentially available to that goofball neighbor who bought an IMSI-catcher off the Internet. Or to your business competitor. Or even to that one girl who finally got GnuRadio to compile.

We're rapidly approaching a technological crossroads, one where we need to decide if we're going to keep trusting others to protect our data -- or if we're going to take charge of it and treat carriers as the dumb and insecure pipes that they are. I suspect that we're well on our way towards this world -- and sadly, so does the FBI. It'll be interesting to see how things play out.

Notes:

* The argument is that recording all local calls in real time is a bigger job than just splitting major trunks or re-routing a few specific targets. It would seem to require significant changes to the US phone infrastructure. This is particularly true at the local office, where you'd need to upgrade and provision thousands of devices to record all calls passing through them. Building this capability is possible, but would require a lot of effort -- not to mention the complicity of hundreds (or thousands) of collaborators at the local telcos. And that means a whole lot of people keeping a very big secret. People aren't so good at that.

We're still alive

2013-05-07T06:44:00.000-07:00

It's been a busy couple of weeks chock full of deadlines, all of which have had a direct and negative impact on blogging productivity.

Still: things are happening in the world! In the next few weeks I hope to have posts up on exciting topics like convergent encryption, IBM's exciting open source Fully Homomorphic Encryption library (AES in less than 30 hours!), password hashing, cellular wiretapping... and plenty more on the hot mess that is the field of practice-oriented provable security.

Please hang in there. Normal service will resume shortly.

Zerocoin: making Bitcoin anonymous

2013-04-11T13:55:00.000-07:00

This is what it's like to die of stupid.

Wow, what the heck is going on with Bitcoin?

When I started this post, the value of a single bitcoin had surged upwards of $250. It's corrected a bit since then (down $100 or so), but it's pretty clear that we live in a very different world than we did two weeks ago.

And I'm not sure I really like this world. It's a world where I have to listen to CNBC reporters try to understand Bitcoin. Ouch. I think we can all agree that we were better off before this happened.

The explosion of interest in Bitcoin is both wonderful and terrible. It's wonderful because Bitcoin is an amazing technical innovation -- the first decentralized electronic currency to actually make something of itself. It's terrible because Bitcoin has some technical rough edges that really need to be filed off before we start using it for anything.

The rough edge that particularly interests me is user privacy. Or rather, Bitcoin's troubling lack of it.

In this post I'm going to describe a new piece of research out of my lab at Johns Hopkins that provides one potential solution to this problem. This is joint work led by my hardworking students Ian Miers and Christina Garman, along with my colleague Avi Rubin. Our proposal is called Zerocoin, and we'll be presenting it at this year's IEEE S&P.

For those who just want the TL;DR, here it is:

Zerocoin is a new cryptographic extension to Bitcoin that (if adopted) would bring true cryptographic anonymity to Bitcoin. It works at the protocol level and doesn't require new trusted parties or services. With some engineering, it might (someday) turn Bitcoin into a completely untraceable, anonymous electronic currency.

In the rest of the post I'm going to explain Zerocoin, what it can do for Bitcoin, and how far away that 'someday' might be. This is going to be a long, wonky post, so I won't be offended if you stop here and take my word that it's all true.

For everyone else, strap in. I need to start with some background.

Bitcoin in 300 words

Before I get to Zerocoin I need to give the world's shortest explanation of how Bitcoin works. (See here for a slightly less terrible explanation.)

At its heart, Bitcoin is a transaction network with a distributed public ledger. Transactions are files that contains messages like "User X transfers 3 bitcoins to user Y" and "User Y transfers 2.5 of those bitcoins to user Z". Users aren't identified by name. Instead, their identities are public keys for a digital signature scheme.* This allows users to sign their transactions, and makes it very difficult to forge them.

Now none of this stuff is really new. What makes Bitcoin special is the way it maintains the transaction ledger. Rather than storing the whole thing on a single computer, the ledger -- called a block chain -- is massively replicated and updated by a swarm of mutually distrustful parties running in a peer-to-peer network.

To make this work, nodes pull transactions off of a peer-to-peer broadcast network, then compete for the opportunity to tack them on the end of the chain. To keep one party from dominating this process (and posting bad transations), competition is enforced by making the parties solve hard mathematical problems called 'proofs of work'. The integrity of the block chain is enforced using hash chaining, which makes it very difficult to change history.

Now the block chain is fascinating, and if you're interested in the gory details you should by all means see here. This post mostly isn't going to get into it. For now all you need to know is that the block chain works like a global ledger. It's easy to add (valid) transactions at the end, but it's astonishingly difficult to tamper with the transactions that are already there.

So what's the problem?

The block chain is Bitcoin's greatest strength. Unfortunately from a privacy perspective, it's also the currency's greatest weakness.

This is because the block chain contains a record of every single Bitcoin transaction that's ever been conducted. Due to the way Bitcoin works, this information can't be limited to just a few trustworthy parties, since there are no trusted parties. This means all of your transactions are conducted in public.

Illustration of a Bitcoin block chain. Each transaction is tied to the one that precedes it.
The transaction at far left is almost certainly a drug deal.

In a sense this makes Bitcoin less private than cash, and even worse than credit cards. If you choose to engage in sensitive transactions on Bitcoin, you should be aware that a record will be preserved for all eternity. Spend with care.

Now some will say this is unfair, since Bitcoin users are not identified by name -- the only identifier associated with your transactions is your public key. Moreover, you can make as many public keys as you'd like. In other words, Bitcoin offers privacy through pseudonymity, which some argue is almost as good as the real thing.

But don't get too comfortable. Already several academic works have succeeded in de-anonymizing Bitcoin transactions. And this work is just getting started. You see, there's an entire subfield of computer science that can roughly be described as 'pulling information out of things that look exactly like the Bitcoin transaction graph', and while these researchers haven't done much to Bitcoin yet -- that's only because they're still fighting over the grant money. We will see more.

If you're a Bitcoin user who values your privacy, this should worry you. The worst part is that right now your options are somewhat limited. Roughly speaking, they are:

Just be careful. Generate lots of public keys and make sure your client software is extremely careful not to use them in ways that could tie one to another (e.g., getting 'change' from one key sent to another). This seems to be the major privacy thrust of the current Bitcoin development effort, and we're all waiting to see how it pans out.

Use a laundry. For the more paranoid, there are services called 'laundries' that take in bitcoins from a whole bunch of users, mix them up and shuffle them back out. In theory this makes it hard to track your money. Unfortunately, laundries suffer from a few problems. First, they only work well if lots of people are using them, and today's laundries have relatively low volume. More importantly, you're entirely dependent on the honesty and goodwill of the laundry itself. A dishonest (or hacked) laundry can steal your coins, or even trace its inputs and outputs -- which could completely undermine your privacy.

Use a Chaumian e-cash system. On the wonkier side, there have been attempts to implement real anonymous cryptographic e-Cash for Bitcoin. I've written about these systems before and while I think they're neat, the existing schemes (from Chaum on forward) have one critical flaw: they all rely on a central 'bank' to issue and redeem e-Cash tokens. The need for this bank has been a major stumbling block in getting these systems up and running, and it's almost unworkable for Bitcoin -- since trusted parties are antithetical to Bitcoin's decentralized nature.

In short, the current solutions aren't perfect. It would be awfully nice if we had something better. Something with the power of cryptographic e-Cash, but without the need to change Bitcoin's network model. And this is where Zerocoin comes in.

Zerocoin

Zerocoin is not intended as a replacement for Bitcoin. It's actually a separate anonymous currency that's designed to live side-by-side with Bitcoin on the same block chain. Zerocoins are fully exchangeable on a one-to-one basis with bitcoins, which means (in principle) you can use them with existing merchants.

Zerocoins themselves can be thought of literally as coins. They're issued in a fixed denomination (for example, 1 BTC), and any user can purchase a zerocoin in exchange for the correct quantity of bitcoin. This purchase is done by placing a special new 'Zerocoin Mint' transaction onto the block chain.

Once a Mint transaction has been accepted by the Bitcoin peers, the same user can later redeem her zerocoin back into bitcoins. She simply embeds a (preferably new) destination Bitcoin address into a 'Zerocoin Spend' transaction, then sends it into the network. If the transaction checks out, the Bitcoin peers will treat it just like a normal Bitcoin transfer -- meaning that she'll receive the full bitcoin value of the coin (minus transaction fees) at the destination address.

Now you're probably wondering what any of this has to do with privacy. To explain that, I need to give you one more piece of information:

Aside from educated guesswork, there's no way to link a Zerocoin Mint transaction to the Zerocoin Spend transaction that redeems it.

Redeeming a zerocoin gives you a completely different set of bitcoins than the ones you used to purchase it. In fact, you can think of Zerocoin like the world's biggest laundry -- one that can handle millions of users, has no trusted party, and can't be compromised. Once as user converts her bitcoins into zerocoins, it's very hard to determine where she took them back out. Their funds are mixed up with all of the other users who also created zerocoins. And that's a pretty powerful guarantee.

Illustration of a Bitcoin/Zerocoin block chain. A user transforms bitcoins into a zerocoin,
then (at some unspecified later point) 'Spends' it to redeem the bitcoins. The linkage between Mint
and Spend (dotted line) cannot be determined from the block chain data.

The key to the whole process is to make it all work at the protocol level -- meaning, without adding new trusted parties. And doing that is the goal of Zerocoin.

How does it work?

Zerocoin uses a combination of digital commitments, one-way accumulators and zero-knowledge proofs, and some extensions to the existing Bitcoin protocol. It also shares some similarities to a previous work by Sander and Ta-Shma. For the details, you can see our paper. Here I'm going to try to give a very high-level intuition that avoids the muck.

The key idea in Zerocoin is that each coin commits to (read: encrypts) a random serial number. These coins are easy to create -- all you need to do is pick the serial number and run a fast commitment algorithm to wrap this up in a coin. The commitment works like encryption, in that the resulting coin completely hides the serial number . At the same time this coin 'binds' you to the number you've chosen. The serial number is secret, and it stays with you.

To 'Mint' the new coin you post it to the network along with a standard Bitcoin transaction containing enough (normal) bitcoins to 'pay for' it. The Mint transaction adds some new messages to the Bitcoin protocol, but fundamentally there's no magic here. The Bitcoin network will accept the transaction into the block chain as long as the input bitcoins check out.**

The Zerocoin 'Spend' transaction is a little bit more complicated. To redeem your zerocoin, you first create a new transaction that contains the coin's serial number (remember that you kept it secret after you made the coin). You also attach a zero-knowledge proof of the following two statements:

You previously posted a valid zerocoin on the block chain.
This particular zerocoin contained the serial number you put in your transaction.

The key to making this all work is that zero-knowledge proof. What you need to know about these is that anyone can verify such a proof, and she'll be absolutely convinced that you're telling the truth about these statements. At the same time, the proof reveals absolutely no other information (hence the 'zero' knowledge).

This means anyone who sees your Spend transaction will be convinced that you really did previously Mint a zerocoin, and that it contained the serial number you just revealed. They can then check the block chain to make sure that particular serial number has never been Spent before. At the same time, the zero knowledge property ensures that they they have absolutely no idea which zerocoin you're actually spending. The number of such coins could easily run into the millions.

All of this leads us to one final question: where do your bitcoins go after you Mint a zerocoin, and how do you get them back when you Spend?

The simple answer is that they don't go anywhere at all. The bitcoins used in a 'Mint' transaction just sit there on the block chain. The Zerocoin protocol semantics require that nobody can access those coins again except by publishing a valid Zerocoin 'Spend'. When you publish a Spend, the protocol allows you to 'claim' any of the previously-committed bitcoins -- regardless of who posted them. In other words, you Mint with one set of bitcoins, and you leave with someone else's.

When will Zerocoin be available?

For those looking to use Zerocoin tomorrow, I would advise patience. We've written a proof-of-concept implementation that extends the C++ bitcoind client to support Zerocoin, and we'll be releasing a cleaned up version of our code when we present the paper in May.

But before you get excited, I need to point out some pretty serious caveats.

First of all, Zerocoin is not cheap. Our current zero-knowledge proof averages around 40KB, and take nearly two seconds to verify. By the standards of advanced crypto primitives this is fantastic. At the same time, it poses some pretty serious engineering challenges -- not least of which is: where do you store all these proofs?

This probably isn't the end of the world. For one thing, it seems likely that we'll be able to reduce the size and cost of verifying the proof, and we think that even the current proof could be made to work with some careful engineering. Still, Zerocoin as currently construed is probably not going to go online anytime soon. But some version of Zerocoin might be ready in the near future.

Another problem with Zerocoin is the difficulty of incrementally deploying it. Supporting the new Mint and Spend functionality requires changes to every Bitcoin client. That's a big deal, and it's unlikely that the Bitcoin folks are going to accept a unilateral protocol change without some serious pushback. But even this isn't a dealbreaker: it should be possible to start Zerocoin off using some training wheels -- using a trusted central party to assist with the process, until enough Bitcoin clients trust it and are willing to support it natively.

In fact, one of the biggest barriers to adoption is human beings themselves. As complicated as Bitcoin is, you can explain the crypto even to non-experts. This makes people happy. Unfortunately Zerocoin is a different animal. It will take time to convince people that these new techniques are safe. We hope to be there when it happens.

In conclusion

I realize that this blog post has run slightly longer than usual. Thanks for sticking with me!

As regular readers of this blog know, I have a passion for anything that gets interesting crypto out into the world. Bitcoin is a great example of this. It would be wonderful if this gave us an opportunity to do even more interesting things. Perfectly untraceable e-Cash would definitely fit that bill.

But even if we don't get there, the fact that reputable computer science conferences are accepting papers about 'that crazy Bitcoin thing' tells you a lot about how much it's grown up. In the long run, this is good news for everyone.

Notes:

* There are a lot of simplifications in here. Identities are the hash of your public key. The block chain is really computed using a Merkle tree for efficiency reasons. The peer-to-peer network isn't quite a broadcast network. Did I mention you should read the paper?

** Note that for those who 'know' their Bitcoin, you can think of the Zerocoin as a piece of extra data that gets added to a Bitcoin transaction. The inputs are still standard bitcoins. There's just no output. Instead, the transaction contains the coin data.

The Ideal Cipher Model (wonky)

2013-04-10T21:09:00.000-07:00

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:

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.
If no matching row was found, it would generate a perfectly random ciphertext C.
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).
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.

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'.
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.
The encryptor now XORs the next plaintext block with C1, which again should yield a randomly-distributed value which we'll call P''.
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.
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

2013-03-12T13:44:00.000-07:00

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:

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.
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 techiques.

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!

2013-03-09T10:50:00.000-08:00

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: 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

Using SilentCircle on a
Huawei complete negates
the point of using SilentCircle.

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.

The SilentCircle short authentication string.

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 current 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.

Cryptography is a systems problem (video)

2013-02-21T18:46:00.003-08:00

Tonight's the Usenix Security deadline. Who has time to blog...?

But in case you're dying for a dose of crypto wonkery (and have an hour with nothing better to do) feel free to check out this talk on SSL/TLS I just gave at Dartmouth. Slides here.

Thanks to Sergey Bratus for the invitation and to everyone who filled out the excellent audience.

Why I hate CBC-MAC

2013-02-14T21:38:00.001-08:00

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

2013-02-04T04:00:00.000-08:00

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.

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.
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

2013-01-25T02:31:00.003-08:00

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.

2013-01-04T13:19:00.005-08:00

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 doing 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

2012-12-28T14:52:00.004-08:00

(source/cc)

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

2012-11-24T06:51:00.004-08:00

Source: Zooko.

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:

Silent Circle is morally bankrupt for promoting its unreviewed, closed-source, centralized crypto software and marketing it as “secure.”
— Nadim Kobeissi (@kaepora) November 6, 2012

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:

This twitter.com/marshray/statu… is exactly the kind of thing that makes a community look juvenile, petty and not ready for primetime.
— Quinn Norton (@quinnnorton) November 7, 2012

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.

The SilentCircle authentication string prevents MiTM. But is it trying to tell you something? (source)

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:

Discovery and protocol negotiation (F1-F4), in which the parties start up a protocol transaction and agree on a supported ZRTP version and ciphersuites.
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.
Key confirmation (F8-F10), in which the parties verify that they've agreed on the same key.
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:

A 4-character string containing the version of the ZRTP protocol.
A Client Identifier string (cid), which is 4 words long and identifies the vendor and release of the ZRTP software.
The 96-bit-long unique identifier for the ZRTP endpoint (ZID).
A Signature-capable flag (S) indicates this Hello message is sent from a ZRTP endpoint which is able to parse and verify digital signatures.
The MiTM flag (M), which has something to do with PBXes.
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).
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 Establishment

Assuming 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):

Alice picks a, sends g^a (message F6).
Bob picks b, sends g^b (message F7).
Both parties compute g^ab and HMAC this value together with lots of other things to derive a session key s0.
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.

Attack of the week: Cross-VM side-channel attacks

2012-10-26T19:21:00.000-07:00

It's been a busy week for crypto flaws. So busy in fact, that I'm totally overwhelmed and paralyzed trying to write about them. It's made blogging almost impossible.

So let's just blast through it, then we can get to the subject I actually want to talk about.

First, at the start of the week we received news that many Android applications and a few (critical!) Java libraries simply don't validate certificates on TLS/SSL connections. This is disastrous, embarrassing and stupid, since lack of certificate verification makes TLS trivially vulnerable to man-in-the-middle attacks. I was going to say something shrill and over-the-top about all of this, but turns out that Threatpost has already totally beaten me there with this synopsis:

The death knell for SSL is getting louder.

Yes indeed, Threatpost. Thank you for making me feel better.

In other news, we learned that major email providers -- who should remain nameless, but are actually Microsoft, Google, Apple, Yahoo and everyone else -- have been competing to see who can deploy the shortest RSA key for DomainKeys Identified Mail (DKIM). I'm told that Yahoo was ahead with 384 bits, but Microsoft had a research team working on a 22-bit key and Apple had abandoned keys altogether, opting for a simple note from Tim Cook asserting that any invalid email messages were probably the recipient's fault. (Ba-dum-tschch.)

So that's the headline news, and I don't want to write about any of it.

What I do want to write about is a result that's gotten a lot less attention -- mostly because it's subtle, falls into the category of 'things we thought of knew about, but didn't explore' and because it involves Hidden Markov models -- which are to tech reporters as raw garlic and silver are to vampires.

This new result is by Zhang, Juels, Reiter and Ristenpart, and it appeared in the ACM CCS conference just a few weeks ago, and it deals with something very relevant to the way we build modern systems. Specifically, if we're going to go and stick all of cryptographic services in cloud-based VMs, how secure can we possibly expect them to be?

The answer is: unfortunately, not very. To get into the details I'm going to use the standard 'fun' question/answer format I usually save for these kinds of attacks.

Why would I put my cryptography in a VM anyway?

In case you missed it, the cloud is our future. The days of running our own cranky hardware and dealing with problems like power-supply faults are long gone. If you're deploying a new service, there's a good chance it'll be at least partly cloud-based. There's a decent chance it will be entirely cloud-based.

Take Instagram, for instance. Their entire $1bn service runs on a few hundred cleverly-managed EC2 instances. While Instagram itself isn't exactly a security product, they do use TLS and SSH (presumably on the instances themselves), and this implies public key crypto and the use of secret keys.

Now this shouldn't be a problem, but VM instances often share physical hardware with other instances, and since EC2 is a public service, those co-resident VMs may not be entirely friendly. The major threat here is, of course, software vulnerabilities -- things that can let an attacker break out of one VM and into another. But even if you perfect the software, there's another more insidious threat: namely, that the attacker VM instance could be able to run a side-channel attack on the co-resident VM.

This threat has long been discussed, and security people generally agree that it's a concern. But actually implementing such an attack has proven surprisingly difficult. This is because real hypervisors put a lot of fluff between the attacking process and the bare metal of the server. Different VMs often run on different cores. Moreover, since each VM has an entire OS running inside of it, there's tons of noise.

In fact, there's been plenty of reason to wonder if these attacks are simply the product of security researchers' fevered imaginations, or if something we need to worry about. What Zhang, Juels, Reiter and Ristenpart tell us is: yes, we should worry. And oh boy, do they do it in a nifty way.

So what is it and how does it work?

The new result focuses specifically on the Xen Hypervisor, which is the one actually used by services like Amazon EC2. Although the attack was not implemented in EC2 itself, it focuses on similar hardware: multi-core servers with SMT turned off. The threat model assumes that the attacker and victim VM are co-resident on the machine, and that the victim is decrypting an Elgamal ciphertext using libgcrypt v.1.5.0.

Now, Elgamal encryption is a great example for side-channel attacks, since it's implemented by taking a portion of the ciphertext, which we'll call x, and computing x^e mod N, where e is the secret key and N is (typically) a prime number. This exponentiation is implemented via the 'square and multiply' algorithm, shown in the figure below:

Square and multiply algorithm (source: Zhang et al.)

The first thing you notice about square-and-multiply is that its operation depends fundamentally on the bits of the secret key. If the ith bit of e is 1, the steps labeled (M) and (R) are conducted. If that bit is 0, they aren't. The bits of the key results in a distinctive set of computations that can be detected if the attacking VM is able to precisely monitor the hardware state.

Now, side-channel attacks on square-and-multiply are not new. They date back at least to Paul Kocher's observations in the mid-to-late 90s using power and operating time as a channel, and they've been repeatedly optimized as technology advances. More recent attacks have exploited cache misses in a shared processor cache (typical in hyper-threading environments) as a means by which a single process can monitor the execution of another one.

However, while these attacks have worked from one process to another, they've never been applied to the full Xen VM setting. This is a pretty challenging problem for a variety of reasons, including::

The difficulty of getting the attacking process to run frequently enough to take precise measurements.
The problem that VCPUs can be assigned to different cores, or irrelevant VCPUs can be assigned to the same core.
Noisy measurements that give only probabilistic answers about which operations occurred on the target process.

And so on and so forth. The challenge in this paper is to overcome all that nonsense and still recover useful information from the attacked VM.

So what's the basic idea?

At a fundamental level, the attack in this paper is quite similar to previous attacks that worked only across processes. The attacking VM first 'primes' the L1 instruction cache by allocating continuous memory pages, then executing a series of instructions designed to load the cache with cache-line-sized blocks it controls.

The attacker then gives up execution and hopes that the target VM will run next on the same core -- and moreover, that the target is in the process of running the square-and-multiply operation. If it is, the target will cause a few cache-line-sized blocks of the attacker's instructions to be evicted from the cache. Which blocks are evicted is highly dependent on the operations that the attacker conducts.

To see what happened, the attacking VM must recover control as quickly as possible. It then 'probes' to see which blocks have been evicted from the cache set. (This is done by executing the same instructions and timing the results. If a given block has been evicted from the cache, execution will result in a cache miss and a measurable delay.) By compiling a list of which blocks were missing, the attacker gains insight into which instructions may have been executed while the target VM was running.

A big challenge for the attacker is the need to regain control quickly. Wait too long and all kinds of things will happen -- the state of the cache won't give any useful information.

Normally Xen doesn't allow VCPUs to rapidly regain control, but there are a few exceptions: Xen gives high priority to Virtual CPUs (VCPUs) that receive an interrupt. The authors were able to exploit this by running a 2-VCPU VM, where the second VCPU's only job is to issue Inter-Processor Interrupts (IPIs) in an effort to get the first VCPU back in control as quickly as possible. Using this approach they were able to get back in the saddle within about 16 microseconds -- an eternity in processing time, but enough to give useful information.

But isn't that data noisy as hell? And fragmented?

Yes. The challenge here is that the attacking VM has no control over where in the computation it will jump in. It could get just a small fragment of the square-and-multiply operation (which is hundreds or thousands operations long), it could jump into the OS kernel, it could even get the wrong VM, thanks to the fact that they can run on any core. Plus the data could be pretty noisy.

The solution to these problems is what's so nifty about this paper. First, they don't just monitor one execution -- they assume that the device is constantly decrypting different ciphertexts, all with the same key. This is a pretty reasonable assumption for something like an SSL web server.

Next, they use machine learning techniques to identify which of the many possible instruction sequences are associated with particular cache measurements. This requires the researchers to train the algorithm beforehand on the target hardware, having the target VCPU conduct of square, multiply and modular reduce calls in order build a training model. During the attack, the data was further processed using a Hidden Markov Model to eliminate errors and bogus measurements from non-cryptographic processes.

Even after all this work, the attacker winds up with thousands of fragments, some of which contain errors or low-confidence results. These can be compared against each other to reduce errors, then stitched together to recover the key itself. Fortunately this is a problem that's been solved in many other domains (most famously: DNA sequencing), and the techniques used here are quite similar.

A good way to illustrate the process is to present a totally made-up example, in which six fragments are reconstructed to form a single spanning sequence:

S1: SRSRMRSRMRSRSRSMR
S2: MRSRSRSRMR**SRMRSR
S3: SRMRSRSR
S4: MRSRSRSR**SRMRSR
S5: MR*RSRMRSRMRSR
S6: MRSRSRMRSRSRSRMR
------------------------------------------------
SRSRMRSRMRSRSRSMRSRSRMRSRSRSRMRSRMRSRSRMRSRMRSR

This is obviously a huge simplification of a very neat (and complex) process that's very well described in the paper. And if all this technical stuff is too much for you: it's basically like the scene in Argo where the little kids reconstructed the shredded photos of the embassy workers. Just without the kids. Or the photos.

So does it actually work?

It would be a hell of a bad paper if it didn't.

With everything in place, the researchers applied their attack against a 4096-bit Elgamal public key, which (due to an optimization in libgcrypt) actually has a 457-bit private key e. After several hours of data collection, they were able to obtain about 1000 key-related fragments, of which 330 turned out to be long enough to be useful for key reconstruction. These allowed the attackers to reconstruct the full key with only a few missing bits, and those they were able to guess using brute force.

And that, as they say, is the ballgame.

Left: Fragment size vs. number of fragments recovered, Right: sequence accuracy as a function of fragments in a batch. (source: Zhang et al.)

Oh my god, we're all going to die.

I would note that this isn't actually a question. But before you start freaking out and pulling down your cloud VMs, a few points of order.

First: there's a reason these researchers did this with libgcrypt and Elgamal, and not, say OpenSSL and RSA (which would be a whole lot more useful). That's because libgcrypt's Elgamal implementation is the cryptographic equivalent of a 1984 Stanley lawnmower engine -- it uses textbook square-and-multiply with no ugly optimizations to get in the way. OpenSSL RSA decryption, on the other hand, is more like a 2012 Audi turbo-diesel: it uses windowing and CRT and blinding and two different types of multiplication, all of which make it a real pain in the butt to deal with.

Secondly, this attack requires a perfect set of conditions. As proposed it works only works with two VMs, and requires specific training on the target hardware. This doesn't mean that the attack isn't viable (especially since cloud services probably do use lots of identical hardware), but it does mean that messiness -- the kind you get in real cloud deployments -- is going to be more of an obstacle than it seems.

One last thing worth mentioning is that before you can attack a VM, you have to get your attack VM onto the same physical hardware with your target. This seems like a pretty big challenge. Unfortunately, some slightly older research indicates that this is actually very feasible in existing cloud deployments. In fact, for only a few dollars, researchers were able to co-locate themselves with a given target VM with about 40% probability.

In the short term, you certainly shouldn't panic about this, especially given how elaborate the attack is. But it does indicate that we should be thinking very hard about side-channel attacks, and considering how we can harden our systems and VMMs to be sure they aren't going to happen to us.

The crypto dream

2012-10-16T11:15:00.004-07:00

(Credit: Matt Blaze/cc)

Arvind Narayanan just gave a fascinating talk at Princeton's Center for Information Technology Policy entitled 'What Happened to the Crypto Dream?'. That link is to the video, which unfortunately you'll actually have to watch -- I have yet to find a transcript.

From the moment I heard the title of Arvind's talk I was interested, since it asks an important question that I wanted a chance to answer. Specifically: what happened to the golden future of crypto? You know, the future that folks like Phil Zimmermann offered us -- the one that would have powered the utopias of Neal Stephenson and the dystopias of William Gibson (or do I have that backwards?) This was the future where cryptography fundamentally altered the nature of society and communications and set us free in new and exciting ways.

That future never quite arrived. Oh, mind you, the technology did -- right on schedule. We're living in a world where it's possible to visit Tokyo without ever leaving your bed, and where governments go to war with software rather than tanks. Yet in some ways the real future is more Stephen King than William Gibson. The plane landed; nobody was on board.

So what did happen to the crypto dream?

Arvind gives us a bunch of great answers, and for the most part I agree with him. But we differ in a few places too. Most importantly, Arvind is a Princeton scholar who has been known to toss out terms like 'technological determinism'. Me, I'm just an engineer. What I want to know is: where did we screw it all up? And how do we make it right?

The premise, explained

Once upon a time most important human transactions were done face-to-face, and in those transactions we enjoyed at least the promise that our communications would be private. Then everything changed. First came the telephones and telegraphs, and then computer networks. As our friends and colleagues spread farther apart geographically, we eagerly moved our personal communications to these new electronic networks. Networks that, for all their many blessings, are anything but private.

People affected by telephonic surveillance (1998-2011). Source: ACLU

Some people didn't like this. They pointed out that our new electronic communications were a double-edge sword, and were costing us protections that our ancestors had fought for. And a very few decided to do something about it. If technological advances could damage our privacy, they reasoned, then perhaps the same advances could help us gain it back.

Technically, the dream was born from the confluence of three separate technologies. The first was the PC, which brought computing into our living room. The second was the sudden and widespread availability of computer networking: first BBSes, then WANs like GTE Telenet, and then the Internet. Most critically, the dream was fueled by the coincidental rise of scientific, industrial cryptography, starting with the publication of the Data Encryption Standard and continuing through the development of technologies like public-key cryptography.

By 1990s, the conditions were in place for a privacy renaissance. For the first time in history, the average person had access to encryption technology that was light years beyond what most governments had known before. The flagbearer of this revolution was Philip Zimmermann and his Pretty Good Privacy (PGP), which brought strong encryption to millions. Sure, by modern standards PGP 1.0 was a terrible flaming piece of crap. But it was a miraculous piece of crap. And it quickly got better. If we just hung in there, the dream told us, the future would bring us further miracles, things like perfect cryptographic anonymity and untraceable electronic cash.

It's worth pointing out that the 'dream' owes a lot of its power to government itself. Congress and the NSA boosted it by doing what they do best -- freaking out. This was the era of export regulations and 40-bit keys and Clipper chips and proposals for mandatory backdoors in all crypto software. Nothing says 'clueless old dinosaurs' like the image of Phil Zimmermann being searched at the border -- for copies of a program you could download off the Internet!

And so we all held a million key signing parties and overlooked a few glaring problems with the software we were using. After all, these would be resolved. Once we convinced the masses to come along with us, the future would be encrypted and paid for with e-Cash spent via untraceable electronic networks on software that would encrypt itself when you were done using it. The world would never be the same.

Obviously none of this actually happened.

If you sent an email today -- or texted, or made a phone call -- chances are that your communication was just as insecure as it would have been in 1990. Maybe less so. It probably went through a large service provider who snarfed up the cleartext, stuffed it into an advertising algorithm, then dropped it into a long term data store where it will reside for the next three years. It's hard to be private under these circumstances.

Cryptography is still everywhere, but ufortunately it's grown up and lost its ideals. I don't remember the last time I bothered to send someone a GPG email -- and do people actually have key signing parties anymore?

There are a few amazingly bright spots in this dull landscape -- I'll get to them in due course -- but for the most part crypto just hasn't lived up to its privacy billing. The question is why? What went so terribly wrong? In the rest of this post I'll try to give a few of my answers to this question.

Problem #1: Crypto software is too damned hard to use.

Cryptographers are good at cryptography. Software developers are good at writing code. Very few of etiher camp are good at making things easy to use. In fact, usability is a surprisingly hard nut to crack across all areas of software design, since it's one of a few places where 99% is just not good enough. This is why Apple and Samsung sell a zillion phones every year, and it's why the 'year of Linux on the Desktop' always seems to be a few years away.

Security products are without a doubt the worst products for usability, mostly because your user is also the enemy. If your user can't work a smartphone, she might not be able to make calls. But if she screws up with a security product, she could get pwned.

Back in 1999 -- in one of the few usability studies we have in this area -- Alma Whitten and J.D. Tygar sat down and tried to get non-experts to use PGP, a program that experts generally thought of as being highly user friendly. Needless to say the results were not impressive. And as fun as it is to chuckle at the people involved (like the guy who revoked his key and left the revocation message on his hard drive) the participants weren't idiots. They were making the same sort of mistakes everyone makes with software, just with potentially more serious consequences.

And no, this isn't just a software design problem. Even if you're a wizard with interfaces, key management turns out to be just plain hard. And worse, your brililant idea for making it easier will probably also make you more vulnerable. Where products have 'succeeded' in marketing end-to-end encryption, they've usually done so by making radical compromises that undermine the purpose of the entire exercise.

Think Hushmail, where the crypto client was delivered from a (potentially) untrustworthy server. Or S/MIME email certificates which are typically generated in a way that could expose private key to the CA. And of course, there's Skype, which operates their own user-friendly CAs, a CA that can potentially pwn you in a heartbeat.

Problem #2: Snake-oil cryptography has cluttered the space.

As Arvind points out, most people don't really understand the limitations of cryptography. This goes for people who rely on it for their business (can't tell you how many times I've explained this stuff to DRM vendors.) It goes double for the average user.

The problem is that when cryptography does get used, it's often applied in dangerous, stupid and pointless ways. And yet people don't know this. So bad products get equal (or greater) billing than good ones, and the market lacks the necessary information to provide a sorting function. This is a mess, since cryptography -- when treated as a cure-all with magical properties -- can actually make us less secure than we might otherwise be.

Take VPN services, for example. These propose to secure you from all kinds of threats, up to and including totalitarian governments. But the vast majority of commercial VPN providers do terribly insecure things, like use a fixed shared-secret across all users. Data encryption systems are another big offender. These are largely purchased to satisfy regulatory requirements, and buying one can get you off the hook for all kinds of bad behavior: regulations often excuse breaches as long as you encrypt your data -- in some way -- before you leave it in a taxi. The details are often overlooked.

With so much weak cryptography out there, it's awfully hard to distinguish a good system. Moreover, the good system will probably be harder to use. How do you convince people that there's a difference?

Problem #3: You can't make money selling privacy.

As I'll explain in a minute this one isn't entirely true. Yet of all the answers in this post I tend to believe that it's also the one with the most explanitory power.

Here's the thing: developing cryptographic technology isn't cheap, and it isn't fast. It takes time, love, and a community of dedicated developers. But more importantly, it requires subject matter experts. These people often have families and kids, and kids can't eat dreams. This means you need a way to pay them. (The parents, that is. You can usually exploit the kids as free labor and call it an 'internship'.)

Across the board, commercialization of privacy technologies has been something of a bust. David Chaum gave it a shot with his anonymous electronic cash company. Didn't work. Hushmail had a good run. These guys are giving it a shot right now -- and I wish them enormous luck. But I'm not sure how they're going to make people pay for it.

In fact, when you look at the most successful privacy technologies -- things like PGP or Tor or Bitcoin -- you notice that these are the exceptions that prove the rule. Tor was developed with US military funding and continues to exist thanks to generous NGO and government donations. PGP was a labor of love. Bitcoin is... well, I mean, nobody really understands what Bitcoin is. But it's unique and not likely to be repeated.

I could think of at least two privacy technologies that would be wonderful to have right now, and yet implementing them would be impossible without millions in seed funding. And where would you recover that money? I can't quite figure it out. Maybe Kickstarter is the answer to this sort of thing, but I'll have to let someone else prove it to me.

Problem #4: It doesn't matter anyway. You're using software, and you're screwed.

Some of the best days of the crypto dream were spent fighting government agencies that legitimately believed that crypto software would render them powerless. We generally pat ourselves on the back for 'winning' this fight (although in point of fact, export regulations still exist). But it's more accurate to say that governments decided to walk away.

With hindsight it's pretty obvious that they got the better end of the deal. It's now legal to obtain strong crypto software, but the proportion of (non-criminal) people who actually do this is quite small. Worse, governments have a trump card that can circumvent the best cryptographic algorithm. No, it's not a giant machine that can crack AES. It's the fact that you're implementing the damned thing in software. And software vulnerabilities will overcome all but the most paranoid users, provided that the number of people worth tracking is small enough.

Arvind points this out in his talk, and refers to a wonderful talk by Jonathan Zittrain called 'The End of Crypto' -- in which Jonathan points out how serious the problem is. Moreover, he notes that we're increasingly losing control of our devices (thanks to the walled garden model), and argues that such control is a pre-condition for secure communications This may be true, but let me play devil's advocate: the following chart shows a price list for 0days in commercial software. You tell me which ones the government has the hardest time breaking into.

Estimated price list for 0-days in various software products. (Source: Forbes)

Whatever the details, it seems increasingly unlikely that we're going to live the dream while using the software we use today. And sadly nobody seems to have much of an answer for that.

Problem #5: The whole premise of this post is wrong -- the dream is alive!

Of course, another possibility is that the whole concept is just mistaken. Maybe the dream did arrive and we were all just looking the other way.

Sure, GPG adoption may be negligible, and yes, most crypto products are a disaster. Yet with a few clicks I can get on a user-friendly (and secure!) anonymous communications network, where my web connections will be routed via an onion of encrypted tunnels to a machine on the other side of the planet. Once there I can pay for things using a pseudonymous electronic cash service that bases its currency on nothing more than the price of a GPU.

If secure communications is what I'm after, I can communicate through OTR or RedPhone or one of a dozen encrypted chat programs that've recently arrived on the scene. And as long as I'm not stupid, there's surprisingly little that anyone can do about any of it.

In conclusion

This has been a very non-technical post, and that's ok -- you don't have to get deeply technical in order to answer this particular question. (In fact, this one place I slightly disagree with Arvind, who also brings up the efficiency of certain advanced technologies like Secure Multiparty Computation. I truly don't think this is a story about efficiency, because we have lots of efficient privacy protocols, and people still don't use them.)

What I do know is that there's so much we can do now, and there are so many promising technologies that have now reached maturity and are begging to be deployed. These include better techniques for anonymizing networks, adding real privacy to currencies like Bitcoin, and providing user authentication that actually works. The crypto dream can still live. Maybe all we need is a new generation of people to dream it.

So you want to use an alternative cipher...

2012-10-09T09:09:00.002-07:00

Not this cipher.

Once in a while I run into discussions that hinge on the following dubious proposition: that AES is bad and we need to replace it. These discussions always make me leery, since they begin with facts not in evidence, and rarely inspire any confidence that the solution is going to be any better than the 'problem'.

In fact, this whole point of view is so rarified that I've debated whether to even write this post, since my opinion is that AES is the last place your system is going to break down -- and you should be focusing your attention on fixing all the other broken things first.

Moreover, the simple advice on AES mirrors the ancient wisdom about IBM: nobody ever got fired for choosing it. Not only is AES is the NIST standard (certified in FIPS 140 and NSA's Suite B), but there are hundreds of solid implementations to choose from. If that's not enough for you, many processors now support AES operations natively, meaning that your application can now offload most of the work to hardware without the help of an expensive co-processor.

So why not just stick with AES? People who have these discussions generally give a variety of reasons, some of which are more valid than others. First, there's what I call the 'slight paranoia' viewpoint, which holds that AES has been around for a long time and could (soon/someday) fail. In just the last few years we've seen a few impractical attacks on the construction, which could be beginning of a trend. Or maybe not.

The second (less paranoid) objection is that AES is somewhat troublesome to implement in software. To make it run fast you have to expand the key and pre-compute a series of tables -- all of which increases key setup time and potentially makes you vulnerable to cache timing attacks. Good implementations take this into account, but even the best ones aren't perfect. And in a few cases your performance constraints are so tight that AES just isn't fast enough.

Now I'm not saying that any of these (except possibly for the last reason) are good reasons to ditch AES. In fact, ditching AES would be the opposite of my recommendation. But let's say that you've already made the decision to explore more recent, modern alternatives. What are they? Should you trust them? And most importantly: what will they buy you?

Salsa20

Based on an informal (and totally unscientific poll), the consensus among advanced AES-switchers is that Salsa20 has a lot going for it. This is mostly due to Salsa20's performance characteristics, but also because people are growing increasingly confident in its security.

Now, just for the record, Salsa20 is a stream cipher, while AES is a block cipher. This distinction is important: stream ciphers produce a string of pseudo-random output bits which are XORed with the message to be encrypted. Block ciphers can be configured to do the same thing (e.g., by running them in CTR or OFB mode), but they can also process plaintext blocks in other ways.

One important difference -- and a reason implementers have historically preferred block ciphers -- is that many block cipher modes allow you to randomly access just a portion of an encrypted message, without wasting time decrypting the whole thing. A second advantage is that block ciphers can be used to construct both encryption and message authentication (MACs), which makes them a wonderful building block for constructing authenticated encryption modes.

Salsa20 takes care of the first issue by providing a means to randomly access any block of the generated keystream. Each invocation of the Salsa20 keystream generator takes a key, a nonce (serving as an IV), and a block position in the stream. It then outputs the 512-bit block corresponding to that position. This makes it easy to, for example, seek to the last block of a multi-gigabyte file.

It's also possible to use Salsa20 in an authenticated encryption mode -- but it's not trivial. And to do this the cipher must be composed with a polynomial-based MAC like Dan Bernstein's poly1305. I won't lie and say that this usage is standardized and well-defined -- certainly not in the way that, say, EAX or GCM modes are with AES.

On the positive side, Salsa20 is fast in software. The key setup time is negligible and it has one of the lowest cycles-per-byte counts of any reputable ciphers. Current figures show Salsa20/12 to be 2-3x as fast as a heavily optimized AES-CTR, and maybe even faster for the implementation that you would actually use (of course, hardware implementations of AES could make up for a lot of this advantage).

The basic limitation a cipher like Salsa20 is the same as with any non-standard cipher -- no matter how good the design, you're using an alternative. Alternatives don't get the same attention that standards do. To its credit, Salsa20 has received a decent amount of academic cryptanalysis, most of it positive, but still nothing compared to AES.

Threefish

Threefish is another recent contribution to the 'alternative ciphers' canon, and hails from Schneier, Ferguson, Lucks, Whiting, Bellare, Kohno, Callas, and Walker. (With a list of authors this long, how could it not be excellent?)

Threefish's distinction is that it's one of a relatively small number of ciphers that recently passed through (most of) a NIST competition. The dubious aspect is that the competition wasn't a competition for designing a cipher. Rather, Threefish was submitted as a building block for the SHA3 candidate Skein, which made it to the final round of the competition but was ultimately passed over in favor of Keccak.

Threefish is a wide-block cipher that can be configured to operate on 256, 512 or 1024-bit blocks. Right off the bat this seems useful for applications like disk encryption, where ciphers are typically used to encrypt large blocks of material (sometimes in 'wide block cipher modes' like CMC or EME). But it seems like a nice choice for security and performance reasons.

While Threefish has seen some cryptanalysis, this is still relatively limited (a few major results). None of these results are 'successful', which is noteworthy and confidence-inspiring. But even with this work, it's hard to say where the cipher stands in relation to AES.

The AES could-have-beens: Twofish, Serpent, etc.

AES seems like it's always been AES, so it's easy to forget that just a few years ago it was called Rijndael and there were four other finalists that could just as easily have taken the title. Those finalists all received a lot of cryptanalytic attention, and none of them went away when AES was selected.

The two ciphers I occasionally run into are Bruce Schneier's Twofish and Anderson/Biham/Knudsen's Serpent. Both have decent performance in software, and both have stood up relatively well to cryptanalysis. On the flipside, neither of the two ciphers has received very much in the way of analysis since the AES competition ended (Twofish's most recent significant result was in 2000).

Any of these ciphers could be a worthy alternative to AES if you were desperate, but I wouldn't go out of my way to use one.

In conclusion

I realize none of the above actually tells you which AES alternative to use, and that's mostly because I don't want to legitimize the question. Unless your adversary is the NSA or you have some serious performance constraints that AES can't satisfy, my recommendation is to stick with AES -- it's the one standard cipher that nobody gets fired for using.

But if you are in the latter category (meaning, you have performance constraints) I'm pretty impressed by Salsa20/12's performance in software, provided you have a good strategy for providing authentication. Even better, while Salsa20 is not standardized by NIST, standardization efforts are ongoing in the eCRYPT eStream project. The result could be increasing adoption of this cipher.

If your concern is with the security of AES, I have less advice to give you. The beautiful thing about AES is that it's so widely studied and used that we'll almost certainly have plenty of notice should the cipher really start to fail. That is, provided the people attacking it are doing so in the public, academic literature. (If your enemy is the NSA I'm just not sure what to tell you. Just run.)

That still leaves a class of folks who worry about encrypting things for the long-haul. For these folks the best I can propose is to securely combine AES with another well-studied cipher like Salsa20, Threefish or one of the AES finalists. This will cost you -- and there's no guarantee that both ciphers will stand over the long term. But the probability of two significant breaks seems lower than the probability of one.

SHA3 is over. Long live SHA3!

2012-10-03T07:28:00.002-07:00

The Keccak 'sponge'
(Wikipedia/CC)

The news today is all about hash functions, and specifically, the new hash function we're all going to be calling SHA3. After six long years NIST has finally announced the winner of the SHA3 competition: it's Keccak.

This isn't a total shock: the scuttlebut is that Keccak got most of the 'hums' in NIST's informal 'hum if you like this hash function' poll at the SHA3 conference this year, followed closely by BLAKE. (Yes, seriously, this is how we do things.) Obviously hums aren't the only criteria NIST uses to pick a standard, but they do us an idea where the community stands on things. Moreover, Keccak sports a radically different design than SHA2 and its competitors -- something that appears to have given it a strong competitive advantage.

Now please let me stipulate (again!) that I'm no expert in hash function design. And sadly, many of the leading hash function experts had 'losing' submissions of their own, which means they're still in the first stages of the grieving process -- the one where they say nice things about the winner while secretly plotting its demise. (I'm only kidding. Sort of.)

So while I'm no expert in the deep internals of the design, I can sum up a few things that others -- both expert and non-expert -- are saying about the process and the decision.

To begin with, nobody really thinks that NIST blew it here. All of the finalists were strong designs, and each provides a substantial security margin over the previous state of the art. Each was evaluated under a base standard of 'indifferentiability from a random oracle', and each possesses a security proof to that effect (for more on what this means, see this post.) This is a great turn for NIST, which has been been iffy on provable security in the past. Concretely, this means no more length-extension attacks as in SHA1/2, though admittedly some SHA2 variants already satisfy this requirement.

Moreover, I hear nobody complaining about the security of Keccak. The major gripes appear to be centered around its performance in software, a concern that really does have some grounding. But more on that in a second.

So what do we know about Keccak/SHA3? This list is by no means comprehensive (nor does it represent my own thoughts alone), but it will hopefully provide a few insights:

The name 'Keccak' comes from 'Kecak', a Balinese dance. (h/t JP Aumasson)
Keccak differs from the other SHA3 finalists in that it uses a 'sponge' construction. Where other designs rely on a 'compression function' which is extended to larger domains, Keccak uses a non-compressing function to absorb and then 'squeeze out' a short digest. It's unclear whether this design is radically better or worse than the existing approaches. But it is different. NIST clearly felt that in this case, different is better.
Keccak doesn't blaze in software. In fact, Keccak/512 is estimated to be as much as half as fast in software as SHA-512. This fantastic table of tables sums up the results across all of the finalists. Needless to say they are highly processor dependent. I'm already seeing the first signs of pushback from security developers on mailing lists.
Keccak is quite speedy on hardware, something NIST cited in its decision. It also looks like it will be very GPU-friendly.
'Attacks' on Keccak include a full distinguisher that applies to all 24 rounds of the hash function. But don't worry, the numbers in this attack are completely ridiculous, and this is in no way an actual attack.
Keccak includes relatively few non-linear bit operations per CPU instruction. The round function has algebraic degree 2, which facilitates some of the theoretical 'zero-sum' attacks on reduced-round Keccak (due to Aumasson and Meier).
No, it is not pronounced 'Ketchup', despite my best attempts to convince people of this. (Though there actually is a reduced-round variant called Keccup.)

My contribution to the SHA3 competition.

The full Keccak specification (including pseudocode and 'readable' C code) can be found here. A series of implementations exist for the SUPERCOP project. Unfortunately I know of no public or commercial implementations, at least not on major cryptographic libraries. I expect that to change quickly, and I also expect a whole bunch of further optimizations -- particularly on the GPU side.

It's not clear how the adoption of SHA3 will proceed. Right now there are no significant clouds on the horizon for the SHA2 series, and for the moment it seems like many people will continue to use those -- at least, those who aren't still using SHA1 or (god help us) MD5. I'm not sure what my recommendation is on switching, except that nobody's in a rush. If you absolutely must worry about long-term security, my recommendation is to consider using SHA2 and SHA3 in a secure composition. But I doubt anyone reading this blog needs to be that paranoid.

Even if you were rooting for another function, there is one major bright side to the selection of Keccak. Now that the SHA3 competition is behind us, cryptographers will have time to get back to the real task: putting holes in SHA1 and SHA2. I very much look forward to the results.

On the (provable) security of TLS: Part 2

2012-09-28T01:05:00.003-07:00

This is the second post in a series on the provable security of TLS. If you haven't read the first part, you really should!

The goal of this series is to try to answer an age-old question that is often asked and rarely answered. Namely: is the TLS protocol provably secure?

While I find the question interesting in its own right, I hope to convince you that it's of more than academic interest. TLS is one of the fundamental security protocols on the Internet, and if it breaks lots of other things will too. Worse, it has broken -- repeatedly. Rather than simply patch and hope for the best, it would be fantastic if we could actually prove that the current specification is the right one.

Unfortunately this is easier said than done. In the first part of this series I gave an overview of the issues that crop up when you try to prove TLS secure. They come at you from all different directions, but most stem from TLS's use of ancient, archaic cryptography; gems like, for example, the ongoing use of RSA-PKCS#1v1.5 encryption fourteen years after it was shown to be insecure.

Despite these challenges, cryptographers have managed to come up with a handful of nice security results on portions of the protocol. In the previous post I discussed Jonnson and Kaliski's proof of security for the RSA-based TLS handshake. This is an important and confidence-inspiring result, given that the RSA handshake is used in almost all TLS connections.

In this post we're going to focus on a similarly reassuring finding related to the the TLS record encryption protocol -- and the 'mandatory' ciphersuites used by the record protocol in TLS 1.1 and 1.2 (nb: TLS 1.0 is broken beyond redemption). What this proof tells us is that TLS's CBC mode ciphersuites are secure, assuming... well, a whole bunch of things, really.

The bad news is that the result is extremely fragile, and owes its existence more to a series of happy accidents than from any careful security design. In other words, it's just like TLS itself.

Records and handshakes

Let's warm up with a quick refresher.

TLS is a layered protocol, with different components that each do a different job. In the previous post I mostly focused on the handshake, which is a beefed-up authenticated key agreement protocol. Although the handshake does several things, its main purpose is to negotiate a shared encryption key between a client and a server -- parties who up until this point may be complete strangers.

The handshake gets lots of attention from cryptographers because it's exciting. Public key crypto! Certificates! But really, this portion of the protocol only lasts for a moment. Once it's done, control heads over to the unglamorous record encryption layer which handles the real business of the protocol: securing application data.

Most kids don't grow up dreaming about a chance to work on the TLS record encryption layer, and that's fine -- they shouldn't have to. All the record encryption layer does is, well, encrypt stuff. In 2012 that should be about as exciting as mailing a package.

And yet TLS record encryption still manages to be a source of endless excitement! In the past year alone we've seen three critical (and exploitable!) vulnerabilities in this part of TLS. Clearly, before we can even talk about the security of record encryption, we have to figure out what's wrong with it.

Welcome to 1995

Development of the SSLv1
record encryption layer

The problem (again) is TLS's penchant for using prehistoric cryptography, usually justified on some pretty shaky 'backwards compatibility' grounds. This excuse is somewhat bogus, since the designers have actually changed the algorithms in ways that break compatibility with previous versions -- and yet retained many of the worst features of the originals.

The most widely-used ciphersuites employ a block cipher configured in CBC mode, along with a MAC to ensure record authenticity. This mode can be used with various ciphers/MAC algorithms, but encryption always involves the following steps:

If both sides support TLS compression, first compress the plaintext.
Next compute a MAC over the plaintext, record type, sequence number and record length. Tack the MAC onto the end of the plaintext.
Pad the result with up to 256 bytes of padding, such that the padded length is a multiple of the cipher's block size. The last byte of the padding should contain the padding length (excluding this byte), and all padding bytes must also contain the same value. A padded example (with AES) might look like:

0x MM MM MM MM MM MM MM MM MM 06 06 06 06 06 06 06
Encrypt the padded message using CBC mode. In TLS 1.0 the last block of the previous ciphertext (called the 'residue') is used as the Initialization Vector. Both TLS 1.1 and 1.2 generate a fresh random IV for each record.

Upon decryption the attacker verifies that the padding is correctly structured, checks the MAC, and outputs an error if either condition fails.

To get an idea of what's wrong with the CBC ciphersuite, you can start by looking at the appropriate section of the TLS 1.2 spec -- which reads more like the warning label on a bottle of nitroglycerin than a cryptographic spec. Allow me sum up the problems.

First, there's the compression. It's long been known that compression can leak information about the contents of a plaintext, simply by allowing the adversary to see how well it compresses. The CRIME attack recently showed how nasty this can get, but the problem is not really news. Any analysis of TLS encryption begins with the assumption that compression is turned off.

Next there's the issue of the Initialization Vectors. TLS 1.0 uses the last block of the previous ciphertext, which is absurd, insecure and -- worse -- actively exploitable by the BEAST attack. Once again, the issue has been known for years yet was mostly ignored until it was exploited.

So ok: no TLS 1.0, no compression. Is that all?

Well, we still haven't discussed the TLS MAC, which turns out to be in the wrong place -- it's applied before the message is padded and encrypted. This placement can make the protocol vulnerable to padding oracle attacks, which (amazingly) will even work across handshakes. This last fact is significant, since TLS will abort the connection (and initiate a new handshake) whenever a decryption error occurs in the record layer. It turns out that this countermeasure is not sufficient.

To deal with this, recent versions of TLS have added the following patch: they require implementers to hide the cause of each decryption failure -- i.e., make MAC errors indistinguishable from padding failures. And this isn't just a question of changing your error codes, since clever attackers can learn this information by measuring the time it takes to receive an error. From the TLS 1.2 spec:

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.

To sum up: TLS is insecure if your implementation leaks the cause of a decryption error, but careful implementations can avoid leaking much, although admittedly they probably will leak some -- but hopefully not enough to be exploited. Gagh!

At this point, just take a deep breath and say 'all horses are spherical' three times fast, cause that's the only way we're going to get through this.

Accentuating the positive

Having been through the negatives, we're almost ready to say nice things about TLS. Before we do, let's just take a second to catch our breath and restate some of our basic assumptions:

We're not using TLS 1.0 because it's broken.
We're not using compression because it's broken.
Our TLS implementation is perfect -- i.e., doesn't leak any information about why a decryption failed. This is probably bogus, yet we've decided to look the other way.
Oh yeah: we're using a secure block cipher and MAC (in the PRP and UF-CMA sense).

And now we can say nice things. In fact, thanks to a recent paper by Kenny Paterson, Thomas Ristenpart and Thomas Shrimpton, we can say a few surprisingly positive things about TLS record encryption.

What Paterson/Ristenpart/Shrimpton show is that TLS record encryption satisfies a notion they call 'length-hiding authenticated encryption', or LHAE. This new (and admittedly made up) notion not only guarantees the confidentiality and authenticity of records, but ensures that the attacker can't tell how long they are. The last point seems a bit extraneous, but it's important in the case of certain TLS libraries like GnuTLS, which actually add random amounts of padding to messages in order to disguise their length.

There's one caveat to this proof: it only works in cases where the MAC has an output size that's greater or equal to the cipher's block size. This is, needless to say, a totally bizarre and fragile condition for the security of a major protocol to hang on. And while the condition does hold for all of the real TLS ciphersuites we use -- yay! -- this is more a happy accident than the result of careful design on anyone's part. It could easily have gone the other way.

So how does the proof work?

Good question. Obviously the best way to understand the proof is to read the paper itself. But I'd like to try to give an intuition.

First of all, we can save a lot of time by starting with the fact that CBC-mode encryption is already known to be IND-CPA secure if implemented with a secure block cipher (PRP). This result tells us only that CBC is secure against passive attackers who can request the encryption of chosen messages. (In fact, a properly-formed CBC mode ciphertext should be indistinguishable from a string of random bits.)

The problem with plain CBC-mode is that these security results don't hold in cases where the attacker can ask for the decryption of chosen ciphertexts.

This limitation is due to CBC's malleability -- specifically, the fact that an attacker can tamper with a ciphertext, then gain useful information by sending the result to be decrypted. To show that TLS record encryption is secure, what we really want to prove is that tampering gives no useful results. More concretely, we want to show that asking for the decryption of a tampered ciphertext will always produce an error.

We have a few things working in our favor. First, remember that the underlying TLS record has a MAC on it. If the MAC is (UF-CMA) secure, then any ciphertext tampering that results in a change to this record data or its MAC will be immediately detected (and rejected) by the decryptor. This is good.

Unfortunately the TLS MAC doesn't cover the padding. To continue our argument, we need to show that no attacker can produce a legitimate ciphertext, and that includes tampering that messes with the padding section of the message. Here again things look intuitively good for TLS. During decryption, the decryptor checks the last byte of the padded message to see how much padding there is, then verifies that all padding bytes contain the same numeric value. Any tampering that affects this section of the plaintext should either:

Produce inconsistencies in some padding bytes, resulting in a padding error, or
Cause the wrong amount of padding to be stripped off, resulting in a MAC error.

Both of these error conditions will appear the same to the attacker, thanks to the requirement that TLS implementations hide the reason for a decryption failure. Once again, the attacker should learn nothing useful.

This all seems perfectly intuitive, and you can imagine the TLS developers making exactly this argument as they wrote up the spec. However there's one small exception to the rule above, which can turn TLS implementations that add an unnecessarily large amount of padding to the plaintext. (For example, GnuTLS.)

To give an example, let's say the unpadded record + MAC is 15 bytes. If we're using AES, then this plaintext can be padded with a single byte. Of course, if we're inclined to add extra padding, it could also be padded with seventeen bytes -- both are valid padding strings. The two possible paddings are presented below:

If the extra-long padding is used, the attacker could maul the longer ciphertext by truncating it -- throwing away the last 16-byte ciphertext block. Truncation is a viable way to maul CBC ciphertexts, since it has the same effect on the underlying plaintext. The CBC decryption of the truncated ciphertext would yield:

Which not very useful, since the invalid padding would lead to a decryption error. However, the attacker could fix this -- this time, using the fact that TLS can be mauled by flipping bits in the last byte of the Initialization Vector. Such an attack would allow the attacker to convert that trailing 0x10 into an 0x00. This result is now valid ciphertext that will not produce an error on decryption.

So what has the attacker learned by this attack? In practice, not very much. Mostly what they know is the length of the original ciphertext -- so much for GnuTLS's attempt to disguise the length. But more fundamentally: this attacker of 'mauling' the ciphertext totally screws up the nice idea we were going for in our proof.

So the question is: can this attack be used against real TLS? And this is where the funny restriction about MAC size comes into play.

You see, if TLS MACs are always bigger than a ciphertext block, then all messages will obey a strict rule: no padding will ever appear in the first block of the CBC ciphertext.

Since the padding is now guaranteed to start in the second (or later) block of the CBC ciphertext, the attacker cannot 'tweak' it by modifying the IV (this attack only works against the first block of the plaintext). Instead, they would have to tamper with a ciphertext block. And in CBC mode, tampering with ciphertext blocks has consequences! Such a tweak will allow the attacker to change padding bytes, but as a side effect it will cause one entire block of the record or MAC to be randomized when decrypted. And what Paterson/Ristenpart/Shrimpton prove is that this 'damage' will inevitably lead to a MAC error.

This 'lucky break' means that an attacker can't successfully tamper with a CBC-mode TLS ciphertext. And that allows us to push our way to a true proof of the CBC-mode TLS ciphersuites. By contrast, if the MAC was only 80 bits (as it is in some IPSEC configurations), the proof would not be possible. So it goes.

Now I realize this has all been pretty wonky, and that's kind of the point! The moral to the story is that we shouldn't need this proof in the first place! What it illustrates is how fragile and messy the TLS design really is, and how (once again) it achieves security by luck and the skin of its teeth, rather than secure design.

What about stream ciphers?

The good news -- to some extent -- is that none of the above problems apply to stream ciphers, which don't attempt to hide the record length, and don't use padding in the first place. So the security of these modes is much 'easier' to argue.

Of course, this is only 'good news' if you believe that the stream ciphers included with TLS are good in the first place. The problem, of course, is that the major supported stream cipher is RC4. I will leave it to the reader to decide if that's a worthwhile tradeoff.

In conclusion

There's probably a lot more that can be said about TLS record encryption, but really... I think this post is probably more than anyone (outside of the academic community and a few TLS obsessives) has ever wanted to read on the subject.

In the next posts I'm going to come back to the much more exciting Diffie-Hellman handshake and then try to address the $1 million and $10 million questions respectively. First: does anyone really implement TLS securely? And second: when can we replace this thing?

Notes:

* One thing I don't mention in this post is the TLS 1.0 'empty fragment' defense, which actually works against BEAST and has been deployed in OpenSSL for several years. The basic idea is to encrypt an empty record of length 0 before each record goes over the wire. In practice, this results in a full record structure with a MAC, and prevents attackers from exploiting the residue bug. Although nobody I know of has ever proven it secure, the proof is relatively simple and can be arrived at using standard techniques.

On the (provable) security of TLS: Part 1

2012-09-06T15:40:00.000-07:00

If you sit a group of cryptographers down and ask them whether TLS is provably secure, you're liable to get a whole variety of answers. Some will just giggle. Others will give a long explanation that hinges on the definitions of 'prove' and 'secure'. What you will probably not get is a clear, straight answer.

In fairness, this is because there is no clear, straight answer. Unfortunately, like all the things you really need to know in life, it's complicated.

Still, just because something's complicated doesn't mean that we get to ignore it. And the security of TLS is something we really shouldn't ignore -- because TLS has quietly become the most important and trusted security protocol on the Internet. While plenty of security experts will point out the danger of improperly configured TLS setups, most tend to see (properly configured) TLS as a kind of gold standard -- and it's now used in all kinds of applications that its designers would probably never have envisioned.

And this is a problem, because (as Marsh points out) TLS (or rather, SSL) was originally designed to secure $50 credit card transactions, something it didn't always do very well. Yes, it's improved over the years. On the other hand, gradual improvement is no substitute for correct and provable security design.

All of which brings us to the subject of this -- and subsequent -- posts: even though TLS wasn't designed to be a provably-secure protocol, what can we say about it today? More specifically, can we prove that the current version of TLS is cryptographically secure? Or is there something fundamental that's holding it back?

The world's briefest overview of TLS

If you're brand new to TLS, this may not be the right post for you. Still, if you're looking for a brief refresher, here it is:

TLS is a protocol for establishing secure (Transport layer) communications between two parties, usually denoted as a Client and a Server.

The protocol consists of several phases. The first is a negotiation, in which the two peers agree on which cryptographic capabilities they mutually support -- and try to decide whether a connection is even possible. Next, the parties engage in a Key Establishment protocol that (if successful) authenticates one or both of the parties, typically using certificates, and allows the pair to establish a shared Master Secret. This is done using a handful of key agreement protocols, including various flavors of Diffie-Hellman key agreement and an RSA-based protocol.

Finally, the parties use this secret to derive encryption and/or authentication keys for secure communication. The rest of the protocol is very boring -- all data gets encrypted and sent over the wire in a (preferably) secure and authenticated form. This image briefly sums it up:

Overview of TLS (source)

So why can't we prove it secure?

TLS sounds very simple. However, it turns out that you run into a few serious problems when you try to assemble a security proof for the protocol. Probably the most serious holdup stems from the age of the cryptography used in TLS. To borrow a term from Eric Rescorla: TLS's crypto is downright prehistoric.

This can mostly be blamed on TLS's predecessor SSL, which was designed in the mid-90s -- a period better known as 'the dark ages of industrial crypto'. All sorts of bad stuff went down during this time, much of which we've (thankfully) forgotten about. But TLS is the exception! Thanks to years of backwards compatibility requirements, it's become a sort of time capsule for all sorts of embarrassing practices that should have died a long slow death in a moonlit graveyard.

For example:

The vast majority of TLS handshakes use an RSA padding scheme known as PKCS#1v1.5. PKCS#1v1.5 is awesome -- if you're teaching a class on how to attack cryptographic protocols. In all other circumstances it sucks. The scheme was first broken all the way back in 1998. The attacks have gotten better since.
The (AES)-CBC encryption used by SSL and TLS 1.0 is just plain broken, a fact that was recently exploited by the BEAST attack. TLS 1.1 and 1.2 fix the glaring bugs, but still use non-standard message authentication techniques, that have themselves been attacked.
Today -- in the year 2012 -- the 'recommended' patch for the above issue is to switch to RC4. Really, the less said about this the better.

Although each of these issues have all been exploited in the past, I should be clear that current implementations do address them. Not by fixing the bugs, mind you -- but rather, by applying band-aid patches to thwart the known attacks. This mostly works in practice, but it makes security proofs an exercise in frustration.

The second obstacle to proving things about TLS is the sheer complexity of the protocol. In fact, TLS is less a 'protocol' than it is a Frankenstein monster of of options and sub-protocols, all of which provide a breeding ground for bugs and attacks. Unfortunately, the vast majority of academic security analyses just ignore all of the 'extra junk' in favor of addressing the core crypto. Which is good! But also too bad -- since these options where practically every real attack on TLS has taken place.

Lastly, it's not clear quite which definition of security we should even use in our analysis. In part this is because the TLS specification doesn't exactly scream 'I want to be analyzed'. In part it's because definitions have been evolving over the years.

So you're saying TLS is unprovable?

No. I'm just lowering expectations.

The truth is there's a lot we do know about the security of TLS, some of it surprisingly positive. Several academic works have even given us formal 'proofs' of certain aspects of the protocol. The devil here lies mainly in the definitions of 'proof' and -- worryingly -- 'TLS'.

For those who don't live for the details, I'm going to start off by listing a few of the major known results here. In no particular order, these are:

If properly implemented with a secure block cipher, the TLS 1.1/1.2 record encryption protocol meets a strong definition of (chosen ciphertext attack) security. Incidentally, the mechanism is also capable of hiding the length of the encrypted records. (Nobody even bothers to claim this for TLS 1.0 -- which everybody agrees is busted.)
A shiny new result from CRYPTO 2012 tells us that (a stripped-down version of) the Diffie-Hellman handshake (DHE) is provably secure in the 'standard model' of computation. Moreover, combined with result (1), the authors prove that TLS provides a secure channel for exchanging messages. Yay!

This result is important -- or would be, if more people actually used DHE. Unfortunately, at this point more people bike to work with their cat than use TLS-DHE.
At least two excellent works have tackled the RSA-based handshake, which is the one most people actually use. Both works succeed in proving it secure, under one condition: you don't actually use it! To be more explicit: both proofs quietly replace the PKCS#v1.5 padding (in actual use) with something better. If only the real world worked this way.
All is not lost, however: back in 2003 Jonnson and Kaliski were able to prove security for the real RSA handshake without changing the protocol. Their proof is in the random oracle model (no biggie), but unfortunately it requires a new number-theoretic hardness assumption that nobody has talked about or revisited since. In practice this may be fine! Or it may not be. Nobody's been able to investigate it further, since every researcher who tried to look into it... wound up dead. (No, I'm just kidding. Although that would be cool.)
A handful of works have attempted to analyze the entirety of SSL or TLS using machine-assisted proof techniques. This is incredibly ambitious, and moreover it's probably the only real way to tackle the problem. Unfortunately, the proofs hugely simplify the underlying cryptography, and thus don't cover the full range of attacks. Moreover, only computers can read them.

While I'm sure there are some important results I'm missing here, this is probably enough to take us 95% of the way to the 'provable' results on TLS. What remains is the details.

And oh boy, are there details. More than I can fit in one post. So I'm going to take this one chunk at a time, and see how many it takes.

An aside: what are we trying to prove, anyway?

One thing I've been a bit fast-and-loose on is: what are we actually proving about these protocols in the first place, anyway? The question deserves at least a few words -- since it's received thousands in the academic literature.

One obvious definition of security can be summed up as 'an attacker on the wire can't intercept modify data', or otherwise learn the key being established. But simply keeping the data secret isn't enough; there's also a matter of freshness. Consider the following attack:

I record communications between a legitimate client and his bank's server, in which the client requests $5,000 to be transferred from her account to mine.
Having done this, I replay the client's messages to the server a hundred times. If all goes well, I'm a whole lot richer.

Now this is just one example, but it shows that the protocol does require a bit of thinking. Taking this a step farther, we might also want to ensure that the master secret is random, meaning even if (one of) the Client or Server are dishonest, they can't force the key to a chosen value. And beyond that, what we really care about is that the protocol data exchange is secure.

Various works take different approaches to defining security for TLS. This is not surprising, given the 'security analysis' provided in the TLS spec itself is so incomplete that we don't quite know what the protocol was intended to do in the first place. We'll come back to these definitional issues in a bit.

The RSA handshake

TLS supports a number of different ciphersuites and handshake protocols. As I said above, the RSA-based handshake is the most popular one -- almost an absurd margin. Sure, a few sites (notably Google) have recently begun supporting DHE and ECDH across the board. For everyone else there's RSA.

So RSA seems as good a place as any to start. Even better, if you ignore client authentication and strip the handshake down to its core, it's a pretty simple protocol:

Clearly the 'engine' of this protocol is the third step, where the Client picks a random 48-byte pre-master secret (PMS) and encrypts it under the server's key. Since the Master Secret is derived from this (plus the Client and Server Randoms), an attacker who can't 'break' this encryption shouldn't be able to derive the Master Key and thus produce the correct check messages at the bottom.

So now for the $10,000,000 question: can we prove that the RSA encryption secure? And the simple answer is no, we can't. This is because the encryption scheme used by TLS is RSA-PKCS#1v1.5, which is not -- by itself -- provably secure.

Indeed, it's worse than that. Not only is PKCS#1v1.5 not provably secure, but it's actually provably insecure. All the way back in 1998 Daniel Bleichenbacher demonstrated that PKCS#1v1.5 ciphertexts can be gradually decrypted, by repeatedly modifying them and sending the modified versions to be decrypted. If the decryptor (the server in this case) reveals whether the ciphertext is correctly formatted, the attacker can actually recover the encrypted PMS.

0x 00 02 { at least 8 non-zero random bytes } 00 { two-byte length } { 48-byte PMS }

RSA-PKCS #1v1.5 encryption padding for TLS

Modern SSL/TLS servers are wise to this attack, and they deal with it in a simple way. Following decryption of the RSA ciphertext they check the padding. If it does not have the form above, they select a random PMS and go forward with the calculation of the Master Secret using this bogus replacement value. In principle, this means that the server calculates a basically random key -- and the protocol doesn't fail until the very end.

In practice this seems to work, but proving it is tricky! For one thing, it's not enough to treat the RSA encryption as a black box -- all of these extra steps and the subsequent calculation of the Master Secret are now intimately bound up with the security of the protocol, in a not-necessarily-straightforward way.

There are basically two ways to deal with this. Approach #1, taken by Morrisey, Smart and Warinschi and Gajek et al., follows what I call the 'wishful thinking' paradigm. Both show that if you modify the encryption scheme used in TLS -- for example, by eliminating the 'random' encryption padding, or swapping in a CCA-secure scheme like RSA-OAEP -- the handshake is secure under a reasonable definition. This is very interesting from an academic point of view; it just doesn't tell us much about TLS.

Fortunately there's also the 'realist' approach. This is embodied by an older CRYPTO paper by Jonnson and Kaliski. These authors considered the entirety of the TLS handshake, and showed that (1) if you model the PRF (or part of it) as a random oracle, and (2) assume some very non-standard number-theoretic assumptions, and (more importantly) (3) the TLS implementation is perfect, then you can actually prove that the RSA handshake is secure.

This is a big deal!

Unfortunately it has a few problems. First, it's highly inelegant, and basically depends on all the parts working in tandem. If any part fails to work properly -- if for example, the server leaks any information that could indicate whether the encryption padding is valid or not -- then the entire thing crashes down. That the combined protocol works is in fact, more an accident of fate than the result of any real security engineering.

Secondly, the reduction extremely 'loose'. This means that a literal interpretation would imply that we should be using ginormous RSA keys, much bigger than we do today. We obviously don't pay attention to this result, and we're probably right not to. Finally, it requires that we adopt odd number-theoretic assumption involving a 'partial-RSA decision oracle', something that quite frankly, feels kind of funny. While we're all guilty of making up an assumption from time to time, I've never seen this assumption either before or since, and it's significant that the scheme has no straightforward reduction the RSA problem (even in the random oracle model), something we would get if we used RSA-OAEP.

If your response is: who cares -- well, you may be right. But this is where we stand.

So where are we?

Good question. We've learned quite a lot actually. When I started this post my assumption was that TLS was going to be a giant unprovable mess. Now that I'm halfway through this summary, my conclusion is that TLS is, well, still mostly a giant mess -- but one that smacks of potential.

Of course so far I've only covered a small amount of ground. We still have yet to cover the big results, which deal with the Diffie-Hellman protocol, the actual encryption of data (yes, important!) and all the other crud that's in the real protocol.

But those results will have to wait until the next post: I've hit my limit for today.

Click here for Part 2.

Hey Amazon: Banning Security Researchers Isn't Making Us Safer

2012-09-02T21:56:00.001-07:00

Readers of this blog may recall that I'm a big fan of the RSA-key 'cracking' research of Nadia Heninger, Zakir Durumeric, Eric Wustrow and Alex Halderman. To briefly sum it up: these researchers scanned the entire Internet, discovering nearly 30,000 weak RSA keys installed on real devices. Which they then factored.

In the fast-paced world of security, this is already yesterday's news. The problems have been responsibly disclosed and repaired, and the manufacturers have promised not to make, well, this particular set of mistakes again. The research even received the Best Paper award at Usenix Security.** So you might ask why I'm writing about it now. And the answer is: I'm not.

What I'm writing about today is not the research itself, but rather: the blowback from the research. You see, Heninger et al. were able to conduct their work mostly thanks resources rented from Amazon's Elastic Compute Cloud (EC2). And in response, Amazon has booted them off the service.

This is a real drag, and not just for the researchers in question.

Cloud services like EC2 are a huge resource for ethical security researchers. They help us to learn things about the Internet on a scale that we could never accomplish with the limited resources in most university labs. Cloud services also give us access to software and hardware that would be nigh on impossible to justify to a grant committee, stuff like GPU cluster instances which are invaluable to cryptographers who want to run specialized cracking tasks.

But more importantly: the rise of cloud computing has given rise to a whole new class of security threat: things we never had to worry about before, like side-channel and covert channel attacks between co-located VMs. Securing the cloud itself requires real-world analysis, and this means that researchers have to be trusted to do some careful, non-malicious work on actual platforms like EC2. Unfortunately this is just kind of research that the Heninger et al. ban could serve to discourage.

Now, I don't pretend that I know all the details of this particular case. I haven't spoken to the researchers about it, and although the paper makes their scan seem pretty benign, it's always possible that it was more aggressive than it should have been.*

Moreover, I can't challenge Amazon's right to execute this ban. In fact their Acceptable Use Policy explicitly prescribes security scans under a section titled 'No Security Violations':

Unauthorized Access. Accessing or using any System without permission, including attempting to probe, scan, or test the vulnerability of a System or to breach any security or authentication measures used by a System.

The question here is not whether Amazon can do this. It's whether their -- or anyone else's -- interests are being served by actually going through with such a ban. The tangible result of this one particular research effort is that thousands of vulnerable systems became secure. The potential result of Amazon's ban is that millions of systems may remain insecure.

Am I saying that Amazon should let researchers run amok on their network? Absolutely not. But there has to be a balance between unfettered access and an outright ban. I think we'll all be better off if Amazon can clearly articulate where that balance is, and provide us with a way to find it.

Update (9/3): Kenn White points me to this nice analysis of the public EC2 image-set. The authors mention that they worked closely with Amazon Security. So maybe this is a starting point.

Notes:

* Admittedly, this part is a little bit ambiguous in their paper. NMAP host discovery can be somewhere between gentle poke and 'active scrub' depending on the options you've set.

** In case you haven't seen it, you may also want to check out Nadia's (NSFW?) Usenix/CRYPTO rump session talk.

Reposted: A cryptanalysis of HDCP v2.1

2012-08-27T10:05:00.000-07:00

Update 8/27: This post was originally published three weeks ago under a different title. I subsequently took it down to give affected vendors time to patch the bugs. As a result of the notification, Digital Content Protection LLC (DCP) has updated the spec to v2.2.

Contrary to my understanding when I wrote the original post, HDCP v2 actually is used by a number of devices. I would like to give credit to Alon Ziv at Discretix, who had previously discovered the Locality Check issue, and to Martin Kaiser who experimentally verified the master secret issue on a European Samsung TV and a Galaxy S II.

Finally, I would like to thank Hanni Fakhoury and Marcia Hofmann at the Electronic Frontier Foundation for all of their helpful advice. The EFF is one of the only organizations that represents security researchers. Please consider donating so they can keep doing it!

Over the past couple of weeks I've mostly been blogging about inconsequential things. Blame summer for this -- it's hard to be serious when it's 104 degrees out. But also, the world just hasn't been supplying much in the way of interesting stuff to write about.

Don't get me wrong, this is a good thing! But in a (very limited) way it's also too bad. One of the best ways to learn about security systems is to take them apart and see how they fail. While individual systems can be patched, the knowledge we collect from the process is invaluable.

Fortunately for us, we're not completely helpless. If we want to learn something about system analysis, there are plenty of opportunities right out there in the wild. The best place to start is by finding a public protocol that's been published, but not implemented yet. Download the spec and start poking!

This will be our task today. The system we'll be looking at is completely public, and (to the best of my knowledge) has not yet been deployed anywhere (Update: see note above). It's good practice for protocol cryptanalysis because it includes all kinds of complicated crypto that hasn't been seriously reviewed by anyone yet.

(Or at least, my Google searches aren't turning anything up. I'm very willing to be corrected.)

Best of all, I've never looked at this system before. So whatever we find (or don't find), we'll be doing it together.

A note: this obviously isn't going to be a short post. And the TL;DR is that there is no TL;DR. This post isn't about finding bugs (although we certainly will), it's about learning how the process works. And that's something you do for its own sake.

HDCPv2

The protocol we'll be looking at today is the High Bandwidth Digital Content Protection (HDCP) protocol version 2. Before you get excited, let me sort out a bit of confusion. We are not going to talk about HDCP version 1, which is the famous protocol you probably have running in your TV right now.

HDCPv1 was analyzed way back in 2001 and found to be wanting. Things got much worse in 2010 when someone leaked the HDCPv1 master key -- effectively killing the whole system.

What we'll be looking at today is the replacement: HDCP v2. This protocol is everything that its predecessor was not. For one thing, it uses standard encryption: RSA, AES and HMAC-SHA256. It employs a certificate model with a revocation list. It also adds exciting features like 'localization', which allows an HDCP transmitter to determine how far away a receiver is, and stop people from piping HDCP content over the Internet. (In case they actually wanted to do that.)

HDCPv2 has barely hit shelves yet (Update: though it was recently selected as the transport security for MiraCast). The Digital Content Protection licensing authority has been keeping a pretty up-to-date set of draft protocol specifications on their site. The latest version at the time of this writing is 2.1, and it gives us a nice opportunity to see how industry 'does' protocols.

An overview of the protocol

As cryptographic protocols go, HDCPv2 has a pretty simple set of requirements. It's designed to protect high-value content running over a wire (or wireless channel) between a transmitter (e.g., a DVD player) and a receiver (a TV). The protocol accomplishes the following operations:

Exchanging and verifying public key certificates.
Establishing shared symmetric keys between the transmitter and receiver.
Caching shared keys for use in later sessions.
Verifying that a receiver is local, i.e., you're not trying to proxy the data to some remote party via the Internet.

These functions are accomplished via three (mostly) separate protocols: a public-key Authenticated Key Agreement (AKE) protocol, a pairing protocol, where the derived key is cached for later use, and a locality check protocol to ensure that the devices are physically close.

I'm going to take these protocols one at a time, since each one involves its own messages and assumptions.

Phase (1): Authenticated Key Agreement (AKE)

The core of HDCPv2 is a custom key exchange protocol, which looks quite a bit like TLS. (In fact, the resemblance is so strong that you wonder why the designers didn't just use TLS and save a lot of effort.) It looks like this:

HDCPv2 key agreement protocol (source). Click the image to enlarge.

Now, there's lots going on here. But if we only look at the crypto, the summary is this:

The transmitter starts by sending 'AKE_Init' along with a random 64-bit nonce R_tx. In response, the receiver sends back its certificate, which contains its RSA public key and device serial number, all signed by the HDCP licensing authority.

If the certificate checks out (and is not revoked), the transmitter generates a random 128-bit 'master secret' K_m and encrypts it under the receiver's public key. The result goes back to the receiver, which decrypts it. Now both sides share K_m and R_tx, and can combine them using a wacky custom key derivation function. The result is a shared a session key K_d.

The last step is to verify that both sides got the same K_d. The receiver computes a value H', using HMAC-SHA256 on inputs K_d, R_tx and some other stuff. If the receiver's H' matches a similar value computed at the transmitter, the protocol succeeds.

Simple, right?

Note that I've ignored one last message in the protocol, which turns out to be very important. Before we go there, let's pause and take stock.

If you're paying close attention, you've noticed a couple of worrying things:

The transmitter doesn't authenticate itself at all. This means anyone can pretend to be a transmitter.
None of the handshake messages (e.g., AKE_Transmitter_Info) appear to be authenticated. An attacker can modify them as they transit the wire.
The session key K_d is based solely on the inputs supplied by the transmitter. The receiver does generate a nonce R_rx, but it isn't used in the above protocol.

None of these things by themselves are a problem, but they make me suspicious.

Phase (2): Pairing

Public-key operations are expensive. And you only really need to do them once. The designers recognized this, and added a feature called 'pairing' to cache the derived K_m for use in later sessions. This is quite a bit like what TLS does for session resumption.

However, there's one catch, and it's where things get complicated: some receivers don't have a secure non-volatile storage area for caching keys. This didn't phase the designers, who came up with a 'clever' workaround for the problem: the receiver can simply ask the transmitter to store K_m for it.

To do this, the receiver encrypts K_m under a fixed internal AES key K_h (which is derived by hashing the receiver's RSA private key). In the last message of the AKE protocol the receiver now sends this ciphertext back to the transmitter for storage. This appears in the protocol diagram as the ciphertext E(K_h, K_m).

The obvious intuition here is that K_m is securely encrypted. What could possibly go wrong? The answer is to ask how K_m is encrypted. And that's where things get worrying.

According to the spec, K_m is encrypted using AES in what amounts to CTR mode, where the 'counter' value is defined as some value m. On closer inspection, m turns out to be just the transmitter nonce R_tx padded with 0 bits. So that's simple. Here's what it looks like:

Encryption of the master key K_m with the receiver key K_h. The value m is equal to (R_tx || 0x000000000000000).

Now, CTR is a perfectly lovely encryption mode provided that you obey one unbreakable rule: the counter value must never be re-used. Is that satisfied here? Recall that the counter m is actually chosen by another party -- the transmitter. This is worrying. If the transmitter wants, it could certainly ask the receiver to encrypt anything it wants under the same counter.

Of course, an honest transmitter won't do this. But what about a dishonest transmitter? Remember that the transmitter is not authenticated by HDCP. The upshot is that an attacker can pretend to be a transmitter, and submit her own K_m values to be encrypted under K_h and m.

Even this might be survivable, if it weren't for one last fact: in CTR mode, encryption and decryption are the same operation.

All of this leads to the following attack:

Observe a legitimate communication between a transmitter and receiver. Capture the values R_tx and E(K_h, K_m) as they go over the wire.
Now: pretend to be a transmitter and initiate your own session with the receiver.
Replay the captured R_tx as your initial transmitter nonce. When you reach the point where you pick the master secret, don't use a random value for K_m. Instead, set K_m equal to the ciphertext E(K_h, K_m) that you captured earlier. Recall that this ciphertext has the form:

AES(K_h, R_Tx || 000...) ⊕ K_m

Now encrypt this value under the receiver's public key and send it along.
Sooner or later the receiver will encrypt the 'master secret' you chose above under its internal key K_h. The resulting ciphertext can be expanded to:
AES(K_h, R_Tx || 000...) ⊕ AES(K_h, R_Tx || 000...) ⊕ K_m

Thanks to the beauty of XOR, the first two terms of this ciphertext simply cancel out. The result is the original K_m from the first session! Yikes!

This is a huge problem for two reasons. First, K_m is used to derive the session keys used to encrypt HDCP content, which means that you may now be able to decrypt any past HDCP content traces. And even worse, thanks to the 'pairing' process, you may be able to use this captured K_m to initiate or respond to further sessions involving this transmitter.

Did I mention that protocols are hard?

Phase (3): The Locality Check

For all practical purposes, the attack above should be our stopping point. Once you have the stored K_m you can derive the session keys and basically do whatever you want. But just for fun, let's go on and see what else we can find.

At its heart, the locality check is a pretty simple thing. Let's assume the transmitter and receiver are both trusted, and have successfully established a session key K_d by running the AKE protocol above. The locality check is designed to ensure that the receiver is nearby -- specifically, that it can provide a cryptographic response to a challenge, and can do it in < 7 milliseconds. This is a short enough time that it should prevent people from piping HDCP over a WAN connection.

(Why anyone would want to do this is a mystery to me.)

In principle the locality check should be simple. In practice, it turns out to be pretty complicated. Here's the 'standard' protocol:

Simple version of the locality check. K_d is a shared key and R_rx is a receiver nonce.

Now this isn't too bad: in fact, it's about the simplest challenge-response protocol you can imagine. The transmitter generates a random nonce R_n and sends it to the receiver. The receiver has 7 milliseconds to kick back a response L', which is computed as HMAC-SHA256 of {the session key K_d, challenge nonce R_n, and a 'receiver nonce' R_rx}. You may recall that the receiver nonce was chosen during the AKE.

So far this looks pretty hard to beat.

But here's a wrinkle: some devices are slow. Consider that the 7 milliseconds must the round-trip communication time, as well as the time required to compute the HMAC. There is a very real possibility that some slower, embedded devices might be not be able to respond in time.

Will HDCP provide a second, optional protocol to deal with those devices? You bet it will.

The second protocol allows the receiver to pre-compute the HMAC response before the timer starts ticking. Here's what it looks like:

'Precomputed' version of the protocol.

This is nearly the same protocol, with a few small differences. Notably, the transmitter gives the receiver all the time it wants to compute the HMAC. The timer doesn't start until the receiver says it's ready.

Of course, there has to be something keeping the RTT under 7ms. In this case the idea is to keep the receiver from speaking until it's received some authenticator from the transmitter. This consists of the least significant 128-bits of the expected HMAC result (L'), which is computed in the same way as above. The receiver won't speak until it sees those bits. Then it'll it kick back its own response, which consists of the most-significant 128 bits of the same value.

Ok, so here we have a protocol that's much more complicated. But considered its own, this one looks pretty ok by me.

But here's a funny question: what if we try running both protocols at once?

No, I'm not being ridiculous. You see, it turns out that the receiver and transmitter get to negotiate which protocol they support. By default they run the 'simple' protocol above. If both support the pre-computed version, they must indicate this in the AKE_Transmitter_Info and AKE_Receiver_Info messages sent during the handshake.

This leads to the following conjecture: what if, as a man-in-the-middle attacker, we can convince the transmitter to run the 'pre-computed' protocol. And at the same time, convince the receiver to run the 'simple' one? Recall that none of the protocol flags (transmitted during the AKE) are authenticated. We might be able to trick both sides into seeing a different view of the other's capabilities.

Here's the setup: we have a receiver running in China, and a transmitter located in New York. We're a man-in-the-middle sitting next to the transmitter. We want to convince the transmitter that the receiver is close -- close enough to be on a LAN, for example. Consider the following attack:

Modify the message flags so that the transmitter thinks we're running the pre-computed protocol. Since it thinks we're running the pre-computed protocol, it will hand us R_n and then give us all the time in the world to do our pre-computation.
Now convince the receiver to run the 'simple' protocol. Send R_n to it, and wait for the receiver to send back the HMAC result (L').
Take a long bath, mow the lawn. Watch Season 1 of Game of Thrones.
At your leisure, send the RTT_READY message to the transmitter, which has been politely waiting for the receiver to finish the pre-computation
The transmitter will now send us some bits. Immediately send it back the most significant bits of the value L', which we got in step (2).
Send video to China.

Now this attack may not always work -- it hinges on whether we can convince the two parties to run different protocols. Still, this is a great teaching example in that it illustrates a key problem in cryptographic protocol design: parties may not share the same view of what's going on.

A protocol designer's most important job is to ensure that such disagreements can never happen. The best way to do this is to ensure that there's only one view to be had -- in other words, dispense with all the options and write a single clear protocol. But if you must have options, make sure that the protocol only succeeds if both sides agree on what those options are. This is usually accomplished by authenticating the negotiation messages, but even this can be a hard, hard problem.

Compared to the importance of learning those lessons, actually breaking localization is pretty trivial. It's a stupid feature anyway.

In Conclusion

This has been a long post. To the readers I have left at this point: thanks for sticking it out.

The only remaining thing I'd like to say is that this post is not intended to judge HDCPv2, or to make it look bad. It may or it may not be a good protocol, depending on whether I've understood the specification properly and depending on whether the above flaws make it into real devices. Which, hopefully they won't now.

What I've been trying to do is teach a basic lesson: protocols are hard. They can fail in ruinous, subtle, unexpected, exciting ways. The best cryptographers -- working with BAN logic analyzers and security proofs -- still make mistakes. If you don't have those tools, steer clear.

The best 'fix' for the problem is to recognize how dangerous protocols can be,and to avoid designing your own. If you absolutely must do so, please try to make yours as simple as possible. Too many people fail to grok this lesson, and the result is, well, HDCPv2.

===

Update 8/27: As I mentioned above, DCP has released a new version of the specification. Version 2.2 includes several updates: it changes the encryption of Km to incorporate both the Transmitter and Receiver nonces. It also modifies the locality check to patch the bug described above. Both of these changes appear to mitigate the bugs above, at least in new devices.

Dear Apple: Please set iMessage free

2012-08-18T23:29:00.003-07:00

Normally I avoid complaining about Apple because (a) there are plenty of other people carrying that flag, and (b) I honestly like Apple and own numerous lovely iProducts. I'm even using one to write this post.

Moroever, from a security point of view, there isn't that much to complain about. Sure, Apple has a few irritating habits -- shipping old, broken versions of libraries in its software, for example. But on the continuum of security crimes this stuff is at best a misdemeanor, maybe a half-step above 'improper baby naming'. Everyone's software sucks, news at 11.

There is, however, one thing that drives me absolutely nuts about Apple's security posture. You see, starting about a year ago Apple began operating one of the most widely deployed encrypted text message services in the history of mankind. So far so good. The problem is that they still won't properly explain how it works.

And nobody seems to care.

I am, of course, referring to iMessage, which was deployed last year in iOS Version 5. It allows -- nay, encourages -- users to avoid normal carrier SMS text messages and to route their texts through Apple instead.

Now, this is not a particularly new idea. But iMessage is special for two reasons. First it's built into the normal iPhone texting application and turned on by default. When my Mom texts another Apple user, iMessage will automatically route her message over the Internet. She doesn't have to approve this, and honestly, probably won't even know the difference.

Secondly, iMessage claims to bring 'secure end-to-end encryption' (and authentication) to text messaging. In principle this is huge! True end-to-end encryption should protect you from eavesdropping even by Apple, who carries your message. Authentication should protect you from spoofing attacks. This stands in contrast to normal SMS which is often not encrypted at all.

So why am I looking a gift horse in the mouth? iMessage will clearly save you a ton in texting charges and it will secure your messages for free. Some encryption is better than none, right?

Well maybe.

To me, the disconcerting thing about iMessage is how rapidly it's gone from no deployment to securing billions of text messages for millions of users. And this despite the fact that the full protocol has never been published by Apple or (to my knowledge) vetted by security experts. (Note: if I'm wrong about this, let me know and I'll eat my words.)

What's worse is that Apple has been hyping iMessage as a secure protocol; they even propose it as a solution to some serious SMS spoofing bugs. For example:

Apple takes security very seriously. When using iMessage instead of SMS, addresses are verified which protects against these kinds of spoofing attacks. One of the limitations of SMS is that it allows messages to be sent with spoofed addresses to any phone, so we urge customers to be extremely careful if they're directed to an unknown website or address over SMS.

And this makes me nervous. While iMessage may very well be as secure as Apple makes it out to be, there are plenty of reasons to give the protocol a second look.

For one thing, it's surprisingly complicated.

iMessage is not just two phones talking to each other with TLS. If this partial reverse-engineering of the protocol (based on the MacOS Mountain Lion Messages client) is for real, then there are lots of moving parts. TLS. Client certificates. Certificate signing requests. New certificates delivered via XML. Oh my.

As a general rule, lots of moving parts means lots of places for things to go wrong. Things that could seriously reduce the security of the protocol. And as far as I know, nobody's given this much of a look. It's surprising.

Moreover, there are some very real questions about what powers Apple has when it comes to iMessage. In principle 'end-to-end' encryption should mean that only the end devices can read the connection. In practice this is almost certainly not the case with iMessage. A quick glance at the protocol linked above is enough to tell me that Apple operates as a Certificate Authority for iMessage devices. And as a Certificate Authority, it may be able to substantially undercut the security of the protocol. When would Apple do this? How would it do this? Are we allowed to know?

Finally, there have been several reports of iMessages going astray and even being delivered to the wrong (or stolen) devices. This stuff may all have a reasonable explanation, but it's yet another set of reasons why we it would be nice to understand iMessage better than we do now if we're going to go around relying on it.

So what's my point with all of this?

This is obviously not a technical post. I'm not here to present answers, which is disappointing. If I knew the protocol maybe I'd have some. Maybe I'd even be saying good things about it.

Rather, consider this post as a plea for help. iMessage is important. People use it. We ought to know how secure it is and what risks those people are taking by using it. The best solution would be for Apple to simply release a detailed specification for the protocol -- even if they need to hold back a few key details. But if that's not possible, maybe we in the community should be doing more to find out.

Remember, it's not just our security at stake. People we know are using these products. It would be awfully nice to know what that means.

On Gauss

2012-08-15T09:07:00.004-07:00

If you pay attention to this sort of thing, you've probably heard about the new state-sponsored malware that's making the rounds in the Middle East. It's called 'Gauss', and like its big brother Flame, it was discovered by Kaspersky Labs (analysis at the link).

I don't have much to say about Gauss that hasn't been covered elsewhere. Still, for those who don't follow this stuff routinely, I thought I might describe a couple of the neat things we've learned about it.

Here's the nutshell summary: Gauss is your basic run-of-the-mill government-issued malware, highly modularized and linked to the same C&C infrastructure that Flame used. It seems mainly focused on capturing banking data, but (as I'll mention in a second) it may do other things. Unlike Flame, there's no evidence that Gauss uses colliding MD5 certificates to get itself onto a host system. Though, in fairness, we may not yet have the complete picture at this point.

So if there are no colliding certificates, what's interesting about Gauss? So far as I can tell, only two things. First, it installs a mystery font. Second -- and far more interesting -- it contains an encrypted payload.

Palida Narrow. Every Gauss-infected system gets set up with a new font called Palida Narrow, which appears to be a custom-generated variant of Lucida Bright with some unusual glyphs in it. From Kaspersky's report:

[Gauss] creates a new TrueType font file “%SystemRoot%\fonts\pldnrfn.ttf” (62 668 bytes long) from a template and using randomized data from the ShutdownInterval key.

Now this looks exciting! Unfortunately Kaspersky has not explained how the randomization works, or indeed if the data is truly random. This leaves us with nothing to do but speculate.

And plenty of folks have. Theories range from the practical (remote host detection) to the slightly wild (on-site vulnerability fuzzing). My favorite is the speculation that Palida is used to steganographically fingerprint the author of certain printed materials. While this theory is almost certainly wrong, it's not completely nuts, and even has some precedent in the research literature.

The 'Godel' payload. For all the excitement about fonts, the big news of Gauss is the presence of an encrypted module called 'Godel'.

Godel should be setting your hair on fire, if only because it attempts to replicate itself via a vulnerability in the code that Windows uses to handle USB sticks. This the very same vector that Stuxnet used to infect the air-gapped centrifuge controllers at Natanz. It's a good indicator that Godel is targeted at a similarly air-gapped system.

Of course the question is: which system? Godel goes to great lengths to ensure that we don't know.

Presumably the designers made this decision based on some bitter experience with Stuxnet, which didn't protect its code at all. The result in Stuxnet's case was that researchers quickly decompiled the payload and identified the parameters that it looked for in a target systems. Somebody -- presumably Stuxnet's handlers -- were unhappy about this: on July 15, 2010 a distributed denial of service attack crippled the industrial control mailing listservs where this was being discussed.

To avoid a repeat of this episode, Gauss's designers chose to encrypt the Godel payload under a key derived from a specific configuration on the targeted computer.

The details can be found in this Kaspersky post. To make a long story short, Godel derives an encryption key by repeatedly MD5 hashing a series of (salted) executable filenames and paths located on the target system. Only a valid entry will unlock the program sections, allowing Godel to do its job.

Example of the salted file path/executable name pair. From Kaspersky.

The key derivation process is performed using ~~1000~~ 10,000 iterations of MD5. The resulting key is fed to RC4. While the use of RC4 and MD5 may seem a little bit archaic (c'mon guys, get with the 21st century!), it likely reflects a decision to use the Microsoft CryptoAPI across a broad range of Windows versions rather than some sort cryptographic retro-fetish.

The real question is: how well does it work?

Probably very well, with caveats. Kaspersky says they're looking for a world-class cryptographer to help them crack the code. What they should really be looking for is someone with a world-class GPU.

As best I can see, the only limitation of Gauss's approach is that the designers should have used a more time-intensive function to derive their keys. ~~1000~~ 10,000 iterations of MD5 sounds like a lot, but really it isn't; not in a world with efficient GPUs that you can rent. This code won't be broken based on weaknesses in RC4 or MD5. It will be broken by exhaustively searching the file path/name space using a GPU (or even FPGA)-based system, or possibly just getting lucky.

No doubt Kaspersky is working on such a project right now. If we learn anything more about the mystery of Godel, it will almost certainly come from that work.

A missing post (updated)

2012-08-07T19:00:00.003-07:00

Update (8/27): I've put the original post back up.

Update (8/9): I've re-written this post to include a vague, non-specific explanation of the bug. I've now confirmed the problem with one vendor, who has asked for a week to issue a patch. So far I haven't had a response from the DCP's technical people. And yes, I do realize someone PasteBinned the original post while it was up.

A few people have asked what happened to the post that was in this space just a few hours ago. No, you're not going crazy. It was here.

The post contained a long, detailed evaluation of the HDCP v2 protocol. My idea was to do real-time evaluation of an industry protocol that hasn't been deployed yet -- a kind of 'liveblogging' cryptanalysis. What I expected to find was some bad practices, which I would gently poke fun at. I didn't expect to find anything serious.

I was wrong in that initial judgement, with some caveats. I'm going to give a vague and non-specific summary here, and I hope to re-post the detailed technical post in a few days when I've heard (something, anything!) from DCP, the organization that maintains HDCP.

In case you've never heard of it, HDCP is a security protocol used to 'protect' video traveling over wired and wireless networks. There are two versions. Version 1 is in your TV today, and was seriously compromised in 2010. Version 2 is much better, but has only been deployed in a few products -- including those that implement MiraCast (formerly Wi-Fi Display).

Version 2 contains a key agreement protocol that's designed to establish a session encryption key between a transmitter (your phone, for example) and a receiver (a TV). Once this key is established, the transmitter can encrypt all video data going over the wire.

What I discovered in my brief analysis is a flaw in the key agreement protocol that may allow a man-in-the-middle to recover the session key (actually the 'master secret' used to derive the session key). This could potentially allow them to decrypt content. More on that in a minute, though.

I also discovered some slightly less serious flaws elsewhere in the protocol. It turns out that the DCP already knows about those, thanks to some enterprising work by a smart guy at an unnamed vendor (who deserves credit, and will get it once I put the original post back up).

Now for a few big caveats about the session key bug.

The bug I found does not get you all the way to decrypting HDCPv2 streams in practice, thanks to a tiny additional protection I missed while writing the original post. I don't think much of this protection, since it involves a secret that's stored in every single HDCPv2-compliant device. That's a pretty lousy way to keep a secret.

And of course I haven't personally verified this in any real HDCP devices, since I don't own any. Although if I did, I could use this nifty HDCP plugin for WireShark to do some of the work.

The issue has been confirmed by one vendor, who is working on a patch for their product. Their products are used in real things that you've heard of, so I'm trusting that they'd know.

The last thing I want to address is why I published this, and why I subsequently pulled it.

When I wrote the original post I thought HDCP v2 was just a 'paper spec' -- that there were no devices actually using it. Shortly after posting, I came across one commercial product that does claim to support HDCPv2. Later I discovered a few others. To be on the safe side, I decided to pull the post until I could notify the vendors. Then through sheer ineptitude I briefly re-posted it. Now I'm doing my best to put the toothpaste back in the tube.

As soon as I get some feedback I intend to put the post back up. A post which, incidentally, was not intended to break anything, but rather to serve as a lesson in just how complicated it is to design your own protocol. I suppose it's achieved that goal.

Anyway, I'm putting this up as a placeholder in case you're curious about what happened or why the heck I'm not blogging. Writing a long technical post and then having to can it is a drag. But hopefully we'll be back to our regularly-scheduled programming in no time at all.

Four theories on the cryptography of Star Trek

2012-07-24T08:23:00.001-07:00

"I'm sorry Captain. They rotated by fourteen."

Over on ZDNet they're asking why cybersecurity is like Star Trek. I think this is the wrong question. A better one is: why is the cybersecurity so bad on Star Trek?

Please don't take this the wrong way. I'm a huge Trek fan. I've watched every episode ever made, and I'd do it again if I had time. Even the Holodeck ones.

But I also teach computer security, and specifically, cryptography. Which is ruining the show for me! How can I buy into a universe where the protagonists have starships, transporters and dorky positronic robots, but still can't encrypt an email to save their lives? The Trek crew has never encountered an encryption scheme that didn't crack like an egg when faced with an 'adaptive algorithm' (whatever that is), or -- worse -- just a dude doing math in his head.

But there's no reason to take my word for this. Thanks to the miracle of searchable Star Trek, you can see for yourself.

Cryptographers deserve better. Viewers deserve better. And while I can't fix bad screenwriting, I can try to retcon us an explanation. And that will be the subject of this post: four scientifically credible explanations why 24th century crypto could legitimately be so awful.

Theory #1: A quantum leap

One answer to the mystery of Trek's bad crypto is so obvious it's mundane. It's the 24th century, and of course all the computers are quantum. Everyone knows that quantum computers are super-duper-powerful, and would blow through traditional encryption like a knife through butter.

But not so fast! As I've written before on this blog, quantum computers are actually quite limited in what (we think) they can do. This even goes for quantum computers enhanced with bio-neural gel packs, whatever the hell those are.

Specifically: while QCs are very good at solving certain number-theoretic problems -- including the ones that power RSA and most public-key encryption schemes -- theorists don't believe that they can efficiently solve NP-complete problems, which should still leave an opening for complexity-theoretic crypto to thrive in the 24th century. And yet we never hear about this in Trek.

Of course it's always possible that the theorists are wrong. But quantum computers still don't explain why Spock can apparently crack encryption codes in his head. (And no, 'Vulcans are really good at math' is not a theory.)

Theory #2: It's the warp drive, stupid

If there's a single technology that makes the Star Trek universe different from ours, it's the Warp drive. And this tees up our next theory:

Could it be that there's a conflict between faster-than-light travel and secure cryptography? Could Zephram Cochrane have done in crypto?

Shockingly, there might actually be something to this. Exhibit A is this paper by Scott Aaronson and John Watrous -- two honest-to-god complexity theorists -- on the implications of a physical structure called a 'closed timelike curve' (CTC) and what would happen if you used one to go back in time and kill your grandfather.

Aaronson and Watrous aren't really interested in killing anyone. What they're interested in is paradoxes, and particularly, what it means if the Universe resolves paradoxes. It turns out that this resolution power has huge implications for computing.

It seems that computers with access to paradox-resolving time travel would be dramatically more powerful than any of the computers we can envision today, regardless of whether they're quantum or classical. In fact, CTC-enhanced computers would be powerful enough to efficiently solve problems in the complexity class PSPACE. This would utterly doom the type of complexity-theoretic crypto we rely on today.

But this still leaves a question: does the Warp drive necessarily imply the existence of CTCs?

One clue comes from Einstein's special theory of relativity, which implies that faster-than-light travel would imply violation of causality. For those without the physics background: Star Trek IV.

Theory #3: Complexity theory is dead

Do you remember the episode in Deep Space Nine where O'Brien and Bashir discussed the latest developments in Ferengi computer science? How about the episode that took place at a Vulcan complexity theory conference? No, I don't either. These things never happened.

This all by itself is suspicious. Trek characters could waste hours blabbering about subspace fields or trying to convince Data he's a real boy. But something as central as the computers that run their ship and keep them alive? Not a peep, not even in a "TECH" scene.

It's almost as though by the end of the 24th century, complexity theory has fallen off of the list of things people care about. Which brings me to my next theory:

In the Star Trek Universe, P = NP.

In one sense this would be huge and mostly great news for computer scientists. But it would be a disaster for the efficient (complexity-theoretic) encryption we use on a daily basis. For things like RSA and AES to be truly secure, we require the existence of 'one-way functions'. And those can only exist if P does not equal NP (P != NP).

Fortunately for cryptography, most computer scientists are convinced that P != NP. They just haven't been able to to prove it. The most recent attempt was made by Vinay Deolalikar of HP Labs, and his proof foundered on subtleties just like every one before it. This means the problem is still open, and technically could go either way.

If P did turn out to be equal to NP, it's conceivable that result would look exactly like Star Trek! A few algorithms could still be quite difficult to break (i.e., the attacks would have huge polynomial runtimes). But maybe not. People might instead fall back on obscurity to overcome the mathematical impossibility of building strong complexity-theoretic encryption. One-time pads would still work, of course, and quantum key distribution might allow for point-to-point transmission. Everything else would become a massive joke.

Now, this theory still doesn't explain the 'breaking crypto in your head' thing, or why it takes like six hours to change the Enterprise's command codes. But it would go a long way to repairing the damage wrought by years of bad scriptwriting.

Theory #4: The Stallman effect

Live long and publish your source.

This last theory is the most mindbending. It's also not mine (I ripped it off from Chris Long).

To get a fix on it, you first have to think about this Federation we hold so dear. Here we have a society where the cost of making something is simply the marginal cost of replicating a copy. Money isn't necessary, and people are free to devote themselves to activities that are fun, after spending the necessary ten hours a week on required tasks such as legislation, family counseling, robot repair and asteroid prospecting.

Does any of this sound familiar to you? Yes. The Federation was founded on the teachings of Richard M. Stallman.

A society based on the teachings of RMS can't possibly get security right. To such a society, security is simply a tool that prevents you you from accessing the full capabilities of your ~~computer~~ replicator. How could we expect serious crypto in a society that worships the legacy of RMS?

A minor problem with this theory is that it doesn't explain why bad cryptography crosses species lines: even the Romulans have terrible encryption. Of course, the Romulans have frigging cloaking devices and still haven't managed to wipe us out. So maybe we can just chalk that one up to incompetence.

In conclusion

I admit that there's only so far you can go with all of this. At a certain point you have to give in and admit that the Trek screenwriters don't know encryption from a Chronoton field. And honestly, what they've done with cryptography is nothing compared to what they've done to physics, electronics, and historical drama.

And please don't get me started on the Holodeck. Can't they just fit that thing with an OFF switch?

Still, if nothing else, this post has given me another forum to bitch about my favorite grievance: bad cryptography in movies and TV. And a chance to remind Hollywood (should any representatives be reading) that I am ready and willing to help you with your cryptographic script writing problems for a very reasonable fee. Just don't expect anyone to do crypto in their head.