Thursday, April 24, 2014

Attack of the Week: Triple Handshakes (3Shake)

3Shake logo designed by @Raed667
The other day Apple released a major security update that fixes a number of terrifying things that can happen to your OS/X and iOS devices. You should install it. Not only does this fix a possible remote code execution vulnerability in the JPEG parser (!), it also patches a TLS/SSL protocol bug known as the "Triple Handshake" vulnerability. And this is great timing, since Triple Handshakes are something I've been meaning (and failing) to write about for over a month now.

But before we get there: a few points of order.

First, if Heartbleed taught us one thing, it's that when it comes to TLS vulnerabilities, branding is key. Henceforth, and with apologies to Bhargavan, Delignat-Lavaud, Pironti,  Fournet and Strub (who actually discovered the attack*), for the rest of this post I will be referring to the vulnerability simply as "3Shake". I've also taken the liberty of commissioning a logo. I hope you like it.

On a more serious note, 3Shake is not Heartbleed. That's both good and bad. It's good because Heartbleed was nasty and 3Shake really isn't anywhere near as dangerous. It's bad since, awful as it was, Heartbleed was only an implementation vulnerability -- and one in a single TLS library to boot. 3Shake represents a novel and fundamental bug in the TLS protocol.

The final thing you should know about 3Shake is that, according to the cryptographic literature, it shouldn't exist.

You see, in the last few years there have been at least three four major crypto papers purporting to prove the TLS protocol secure. The existence of 3Shake doesn't make those results wrong. It may, however, indicate that cryptographers need to think a bit more about what 'secure' and 'TLS' actually mean. For me, that's the most fascinating implication of this new attack.

I'll proceed with the usual 'fun' question-and-answer format I save for this sort of thing.

What is TLS and why should you care?

Since you're reading this blog, you probably already know something about TLS. You might even realize how much of our infrastructure is protected by this crazy protocol.

In case you don't: TLS is a secure transport protocol that's designed to establish communications between two parties, who we'll refer to as the Client and the Server. The protocol consists of two sub-protocols called the handshake protocol and the record protocol. The handshake is intended to authenticate the two communicating parties and establish shared encryption keys between them. The record protocol uses those keys to exchange data securely.

For the purposes of this blog post, we're going to focus primarily on the handshake protocol, which has (at least) two major variants: the RSA handshake and the Diffie-Hellman handshake (ECDHE/DHE). These are illustrated below.

Simplified description of the TLS handshakes. Top: RSA handshake. Bottom: Diffie-Hellman handshake.
As much as I love TLS, the protocol is a hot mess. For one thing, it inherits a lot of awful cryptography from its ancient predecessors (SSLv1-3). For another, it's only really beginning to be subjected to rigorous, formal analysis.

All this means we're just now starting to uncover some of the bugs that have been present in the protocol since it was first designed. And we're likely to discover more! That's partly because this analysis is at a very early stage. It's also partly because, from an analysts' point of view, we're still trying to figure out exactly what the TLS handshake is supposed to do.

Well, what is the TLS handshake supposed to do?

Up until this result, we thought we had a reasonable understanding of the purpose of the TLS handshake. It was intended to authenticate one or both sides of the connection, then establish a shared cryptographic secret (called the Master Secret) that could be used to derive cryptographic keys for encrypting application data.

The first problem with this understanding is that it's a bit too simple. There isn't just one TLS handshake, there are several variants of it. Worse, multiple different handshake types can be used within a single connection.

The standard handshake flow is illustrated -- without crypto -- in the diagram below. In virtually every TLS connection, the server authenticates to the client by sending a public key embedded in a certificate. The client, for its part, can optionally authenticate itself by sending a corresponding certificate and proving it has the signing key. However this client authentication is by no means common. Many TLS connections are authenticated only in one direction.

Common TLS handshakes. Left: only server authenticates.
Right: client and server both authenticate with certificates.
TLS also supports a "renegotiation" handshake that can switch an open connection from one mode to the other. This is typically used to change a connection that was authenticated only in one direction (Server->Client) into a connection that's authenticated in both directions. The server usually initiates renegotiation when the client has e.g., asked for a protected resource.

Renegotiating a session. A new handshake causes the existing connection to be mutually authenticated.
Renegotiation has had problems before. Back in 2009, Ray and Dispensa showed that a man-in-the-middle attacker could actually establish a (non-authenticated) connection with some server; inject some data; and when the server asks for authentication, the attacker could then "splice" on a real connection with an authorized client by simply forwarding the new handshake messages to the legitimate client. From the server's point of view, both communications would seem to be coming from the same (now authenticated) person:

Ray/Dispensa attack from 2009. The attacker first establishes an unauthenticated connection and injects some traffic ("drop table *"). When the server initiates a renegotiation for client authentication, the attacker forwards the new handshake messages to an honest client Alice who then sends real traffic. Since the handshakes are not bound together, Bob views this as a single connection to one party.
To fix this, a "secure renegotiation" band-aid to TLS was proposed. The rough idea of this extension was to 'bind' the renegotiation handshake to the previous handshake, by having the client present the "Finished" message of the previous handshake. Since the Finished value is (essentially) a hash of the Master Secret and the (hash of) the previous handshake messages, this allows the client to prove that it -- not an attacker -- truly negotiated the previous connection.

All of this brings us back to the question of what the TLS handshake is supposed to do.

You see, the renegotiation band-aid now adds some pretty interesting new requirements to the TLS handshake. For one thing, the security of this extension depends on the idea that (1) no two distinct handshakes will happen to use the same Master Secret, and (2) that no two handshakes will have the same handshake messages, ergo (3) no two handshakes will have the same Finished message.

Intuitively, this seemed like a pretty safe thing to assume -- and indeed, many other systems that do 'channel binding' on TLS connections also make this assumption. The 3Shake attack shows that this is not safe to assume at all.

So what's the problem here?

It turns out that TLS does a pretty good job of establishing keys with people you've authenticated. Unfortunately there's a caveat. It doesn't truly guarantee the established key will be unique to your connection. This is a pretty big violation of the assumptions that underlie the "secure renegotiation" fix described above.

For example: imagine that Alice is (knowingly) establishing a TLS connection to a server Mallory. It turns out that Mallory can simultaneously -- and unknown to Alice -- establish a different connection to a second server Bob. Moreover, if Mallory is clever, she can force both connections to use the same "Master Secret" (MS).

Mallory creates two connections that use the same Master Secret.
The first observation of the 3Shake attack is that this trick can be played if Alice supports either of the or RSA and DHE handshakes -- or both (it does not seem to work on ECDHE). Here's the RSA version:**

RSA protocol flow from the triple handshake attack (source). The attacker is in the middle, while the client and server are on the left/right respectively. MS is computed as a function of (pms, cr, sr) which are identical in both handshakes. 
So already we have a flaw in the logic undergirding secure renegotiation. The Master Secret (MS) values are not necessarily distinct between different handshakes.

Fortunately, the above attack does not let us resurrect the Ray/Dispensa injection attack. While the attacker has tricked the client into using a specific MS value, the handshake Finished messages -- which the client will attach to the renegotiation handshake -- will not be the same in both handshakes. That's because (among other things) the certificates sent on each connection were very different, hence the handshake hashes are not identical. In theory we're safe.

But here is where TLS gets awesome.

You see, there is yet another handshake I haven't told you about. It's called the "session resumption handshake", and it allows two parties who've previously established a master secret (and still remember it) to resume their session with new encryption keys. The advantage of resumption is that it uses no public-key cryptography or certificates at all, which is supposed to make it faster.



It turns out that if an attacker knows the previous MS and has caused it to be the same on both sides, it can now wait until the client initiates a session resumption. Then it can replay messages between the client and server in order to update both connections with new keys:

An attacker replays the session resumption handshake to ensure the same key on both sides. Note that the handshake messages are identical in both connections. (authors of source)
Which brings us to the neat thing about this handshake. Not only is the MS the same on both connections, but both connections now see exactly the same (resumption) handshake messages. Hence the hash of these handshakes will be identical, which means in turn that their "Finished" message will be identical.

By combining all of these tricks, a clever attacker can pull off the following -- and absolutely insane -- "triple handshake" injection attack:

Triple handshake attack. The attacker mediates two handshakes that give MS on both sides, but two different handshake hashes. The resumption handshake leaves the same MS and an identical handshake hash on both sides. This means that the Finished message from the resumption handshake will be the same for the connections on either side of the attacker. Now he can hook up the two without anyone noticing that he previously injected traffic.
In the above scenario, an attacker first runs a (standard) handshake to force both sides of the connection to use the same MS. It then causes both sides to perform session resumption, which results in both sides using the same MS and having the same handshake hash and Finished messages on both sides. When the server initiates renegotiation, the attacker can forward the third (renegotiation) handshake on to the legitimate client as in the Ray/Dispensa attack -- secure in the knowledge that both client and server will expect the same Finished token.

And that's the ballgame.

What's the fix?

There are several, and you can read about them here.

One proposed fix is to change the derivation of the Master Secret such that it includes the handshake hash. This should wipe out most of the attacks above. Another fix is to bind the "session resumption" handshake to the original handshake that led to it.

Wait, why should I care about injection attacks?

You probably don't, unless you happen to be one of the critical applications that relies on the client authentication and renegotiation features of TLS. In that case, like most applications, you probably assumed that a TLS connection opened with a remote user was actually from that user the whole time, and not from two different users.

If you -- like most applications -- made that assumption, you might also forget to treat the early part of the connection (prior to client authentication) as a completely untrusted bunch of crap. And then you'd be in a world of hurt.

But don't take my word for it. There's video! (See here for the source, background and details):

video


What does this have to do with the provable security of TLS?

Of all the questions 3Shake raises, this one is the most interesting. As I mentioned earlier, there have been several recent works that purport to prove things about the security of TLS. They're all quite good, so don't take any of this as criticism.

However, they (with one exception, the miTLS project) didn't find this attack. Why is that?

The first reason is simple: many of these works analyze only the basic TLS handshake, or they omit at least one of the possible handshakes (e.g., resumption). This means they don't catch the subtle interactions between the resumption handshake, the renegotiation handshake, and extensions -- all of which are the exact ingredients that make most TLS attacks possible.

The second problem is that we don't quite know what standard we're holding TLS to. For example, the common definition of security for TLS is called "Authenticated and Confidential Channel Establishment" (ACCE). Roughly speaking this ensures that two parties can establish a channel and that nobody will be able to determine what data is being sent over said channel.

The problem with ACCE is that it's a definition that was developed specifically so that TLS could satisfy it. As a result, it's necessarily weak. For example, ACCE does not actually require that each handshake produces a unique Master Secret -- one of the flaws that enables this attack -- because such a definition was not possible to achieve with the existing TLS protocol. In general this is what happens when you design a protocol first and prove things about it later.

What's the future for TLS? Can't we throw the whole thing out and start over again?

Sure, go ahead and make TLS Rev 2. It can strip out all of this nonsense and start fresh.

But before you get cocky, remember -- all these crazy features in TLS were put there for a reason. Someone wanted and demanded them. And sadly, this is the difference between a successful, widely-used protocol and your protocol.

Your new replacement for TLS might be simple and wonderful today, but that's only because nobody uses it. Get it out into the wild and before long it too will be every bit as crazy as TLS.

Notes:

* An earlier version of this post incorrectly identified the researchers who discovered the attack.

** The Diffie-Hellman (DHE) version is somewhat more clever. It relies on the attacker manipulating the D-H parameters such that they will force the client to use a particular key. Since DHE parameters sent down from the server are usually 'trusted' by TLS implementations, this trick is relatively easy to pull off.

14 comments:

  1. You're charging the news outlets for using that logo I hope ;)
    Thank you for the bit at the end about "successful, widely-used protocol and your protocol." People tend to forget that systems evolve, that features are added and deprecated over time (and that sometimes a fresh start is much more difficult than it looks).

    ReplyDelete
  2. Don't forget that as well as the session ids and /their/ resumption that's in the core protocol, there's also rfc 5077 for session tickets providing a whole new mechanism.

    ReplyDelete
  3. another 3Shake logo
    http://en.wikipedia.org/wiki/File:WC-2014-Brasil.svg

    ReplyDelete
  4. Excellent article, thanks! (didn't find the dachshunds though ;-)

    ReplyDelete
  5. Thank you for the work you put into this. Have you reported this to the TLS maintainers? Is there any discussion about this on the TLS IETF list?

    ReplyDelete
  6. Nice post! Thank you

    ReplyDelete
  7. Likewise, thanks for the overview.

    ReplyDelete
  8. The issue here is many, many people choosing to use TLS in contexts where it is the wrong tool. So they go and add features to make in work in the new context and they break the security of the protocol. It has happened many, many times.

    'My Protocol' might not be messy and necessarily won't serve all purposes. But that is the point. Thinking that one secure protocol for all purposes can exist is wrong. We need different protocols for each application, each simple, with proven properties and easily understood implementations.

    A protocol for credit card transactions. A protocol for securing a web pages/sessions (TLS doesn't do that, it secures a web-client/web-server session - different thing). A protocol for attesting to intent ("Sell 30 stocks"). A protocol for email transfer and a protocol for email content (different things again). A protocol for typed sessions (SSH does this, but it's complex too).

    Security protocols need to run between the entities that have something to protect. App - App, web-app to user, web-server to web client, MUA-MTA etc. etc. TLS is used for all these things and the result it the mess we have.

    Renegotiation is bad, resumption is bad. Start a session, do stuff, end the session. Never, ever try to modify the thing as you go along. The new exchanges only achieve to add to the attack surface.

    So the goal of those of us who are ambitious enough to think we can do better is not to replace TLS. It is to eliminate TLS and it usages and replace the usages with sensible usages that each have a security scheme well matched to the individual problem.

    ReplyDelete
  9. Matthew, since you're knowledgable on the subject, why don't you participate in the definition of TLS 1.3 that is currently happening on the TLS mailing list? It always puzzles me how experts who have a lot to say about TLS on their blogs don't participate in the TLS WG. (e. g. you, Ivan Ristic, Bruce Schneier...)

    ReplyDelete
  10. About that "My protocol", or "TLS rev2"...
    they are already working on TLS 1.3, it won't have compression and might only support AEAD chipers.

    But I still think it's a mess, is missing important authentication features and can't be used everywhere.
    ...So I've been working on a new encryption/authentication/authorization protocol for federated environments, I started a little more than half a year ago and I will probably finish the implementation by the end of this year.

    Session resumption is *NOT* bad, key renegotiation is absolutely necessary.
    Just because they failed to consider how it all worked together it doesn't mean you should throw away everything.

    I am throwing away TLS, kerberos, OAuth and everything else, and putting all the features together. Eliminating the features the we use today would be idiocy.

    @David: Single things for a single purpose like you propose can only make nightmares.
    But you obviously didn't think about the wonderful TCP+TLS+PHP session +OAuth session nightmare, where everything tries to do one thing, and you end up doing everything twice and trying to keep it together with bad duct tape.
    Or are you proposing to rewrite everything every time?

    ReplyDelete
  11. Several of the links to the images appear to be broken.

    ReplyDelete
  12. I think its worth noting that the researchers who discovered the attack are some of the same researchers attempting security proofs about TLS, so it is quite possible that the latter research agenda led to the discovery of this attack (I haven't examined the paper in detail to see if they note whether this is the case or not). If so, this is an ideal result: scratching at why a proof won't go through to see if there is a potential attack, before automatically weakening definitions.

    ReplyDelete
  13. This thing applies with client public-private key pairs brought to the server in the client certificate.

    If the server application does channel binding using the client public key found in the client certificate it receives from Mallory, the resumed session will have only the access rights of Mallory. If Mallory chooses to share its (server hosted) resources with the original client, it does not need this TLS vulnerability to do so.

    This is not a "fix," but a TLS use case with built-in protection against the original protocol weakness.

    Am I correct?

    - Thierry Moreau

    ReplyDelete
  14. "The elliptic curve version of DHE (ECDHE) allows servers
    to offer arbitrary curves, and so theoretically suffers from the
    same attack, but all the TLS implementations we tested only
    support well-known named curves standardized by NIST."

    Next day after 3Shake publication we putted ECDHE cipher suites with highest priorities in the SSL servers.. long before any "fixes" appeared on horizon...

    ReplyDelete