In defense of Provable Security

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

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

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

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

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

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

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

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

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

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

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

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

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

You need a cryptanalyst…

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

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

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

…because people make mistakes

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

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

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

What Dan’s not saying

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

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

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

In conclusion

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

Surveillance works! Let’s have more of it.

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

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

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

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

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

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

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

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

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

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

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

The anatomy of a bad idea

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

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

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

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

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

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

So what is it?

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

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

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

Two visions

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

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

I like elevators.

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

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

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

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

Some will do this. Some will not.

But maybe you’re just being too sensitive…?

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

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

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

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

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

What about backwards compatibility?

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

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

So what does it all mean?

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

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

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

—

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

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

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

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

Let’s talk about ZRTP

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

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

ZRTP

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

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

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.

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 EstablishmentAssuming that the two parties have successfully completed the negotiation, the next phase of the protocol requires the two parties to establish a shared key. This is done using (nearly) straight-up Diffie-Hellman. The parameters are negotiated in the previous phase, and are drawn from a list defined by RFC3526 and a NIST publication.
Normally a Diffie-Hellman agreement would work something like this (all exponentiation is in a group, i.e., mod p):

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

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

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 unfortunately 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 either 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…

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!

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

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 PRF sense respectively).**

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 (PRF) 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.

** The typical security definition for a MACs is SUF-CMA (strongly unforgeable under chosen message attack). This result uses the stronger — but also reasonable — assumption that the MAC is actually a PRF.

On the (provable) security of TLS: Part 1

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.

Some random thoughts about crypto. Notes from a course I teach. Pictures of my dachshunds.

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

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

You need a cryptanalyst…

…because people make mistakes

What Dan’s not saying

In conclusion

So what is it?

Two visions

What about backwards compatibility?

So what does it all mean?

ZRTP

Overview of ZRTP

The Guts of the Protocol

Conclusion

Why would I put my cryptography in a VM anyway?

So what is it and how does it work?

So what’s the basic idea?

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

So does it actually work?

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

The premise, explained

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

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

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

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

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

In conclusion

Salsa20

Threefish

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

In conclusion

Records and handshakes

Welcome to 1995

Accentuating the positive

So how does the proof work?

What about stream ciphers?

In conclusion

So you’re saying TLS is unprovable?

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

The RSA handshake

So where are we?

Menu