A diversion: BEAST Attack on TLS/SSL Encryption

Update 9/22/11: It appears that OpenSSL may have actually written a patch for the problem I describe below, all the way back in 0.9.6d (2002), so this attack may not be relevant to OpenSSL systems.  But I haven’t reviewed the OpenSSL code to verify this.  More on the patch at the bottom of this post.

Update 10/2/11: Yes, the attack works pretty much as described below (and see comments).  To advise future standards committees considering non-standard crypto, I have also prepared this helpful flowchart.

There’s some news going around about a successful attack on web browsers (and servers) that support TLS version 1.0.  Since this is ostensibly a blog, I figured this subject might be good for a little bit of real-world speculation.

My first thought is that “attacks” on TLS and SSL need to be taken with a grain of salt.  The protocol has been around for a long time, and new attacks typically fall into one of two categories: either they work around SSL altogether (e.g., tricking someone into not using SSL, or going to an untrusted site), or they operate on some obscure, little-used feature of SSL.

(Please don’t take this as criticism of the attacks I link to above.  At this point, any attack against TLS/SSL is a big deal, and those are legitimate vulnerabilities.  I’m trying to make a point about the strength of the protocol.)

This attack is by researchers Juliano Rizzo and Thai Duong, and if we’re to believe the press, it’s a bit more serious than usual.  Ostensibly it allows a man-in-the-middle to decrypt HTTPS-protected session cookies, simply by injecting a little bit of Javascript into the user’s web browser.  Since we’re constantly running third-party Javascript due to web advertising, this might not be a totally unrealistic scenario.

The attack is claimed to make use of a theoretical vulnerability present in all versions of SSL and TLS 1.0 (but not later versions of TLS).  Unfortunately there are few details in the news reports, so until the researchers present their findings on Friday, we have to rely on some educated guesses.  And thus, here’s a big caveat:

Every single thing I write below may be wrong!

What the heck is a Blockwise-Adaptive Chosen Plaintext Attack?

Based on a quick Google search, the attack may be based a paper written by Gregory Bard at the University of Maryland.  The basic idea of this attack is that it exploits the particular way that TLS encrypts long messages using block ciphers.  To do this, Bard proposes using Javascript.

Besides being incredibly annoying, Javascript is a huge potential security hole for most web browsers.  This is mostly mitigated in browsers, which place tight restrictions on the sorts of things that a Javascript program can do.  In terms of network communication, Javascript programs can barely do anything.  About the only exception to this rule is that they can communicate back to the server from which they were served.  If the page is HTTPS-protected, then communication gets bundled under the same TLS communication session used to secure the rest of the web page.

In practice, this means that any data sent by the Javascript program gets encrypted under the same key that is also used to ship sensitive data (e.g., cookies) up from the web browser to the server.  Thus, the adversary now has a way to encrypt any message she wants, under a key that matters.  All she has to do is sneak a Javascript program onto the user’s web page, then somehow intercept the encrypted data sent to the server by the browser.  This type of thing is known as a chosen plaintext attack.

Normally chosen plaintext attacks are not a big deal.  In fact, most encryption schemes are explicitly designed to deal with them.  But here is where things get interesting.

TLS 1.0 uses a block cipher to encrypt data, and arranges its use of the cipher using a variant of the Cipher Block Chaining mode of operation.  CBC mode is essentially a means of encrypting long messages using a cipher that only encrypts short, fixed-size blocks.

CBC mode encryption (diagram: Wikipedia).  The circular cross denotes the XOR operation.  The message is first divided into even-sized blocks.  A random Initialization Vector (IV) is used for the first block.  Each subsequent block is “chained” to the message by XORing the next block of plaintext with the previous block of ciphertext.

CBC mode encryption is illustrated above.  Note that it uses a block cipher as an ingredient.  It also depends on a random per-message nonce called an Initialization Vector, or IV for short.

If you asked me to describe the security properties of CBC, I would recite the following mantra: as long as you use a secure block cipher, and as long as you generate a new, random IV for each message, this mode is very secure against eavesdroppers — even when the adversary can obtain the encryption of chosen plaintexts.  If you doubted me, I would point you here for a formal proof.

You may have noticed that I emphasized the phrase “as long as”.  This caveat turns out to be important.

In the implementation of CBC mode, the TLS designers made one, tiny optimization.  Rather than generating a fresh IV for each message, the protocol re-uses the last block of the previous ciphertext message that was sent.  This value becomes the IV for the new message.

In practice, this tiny modification has huge implications.  If we assume that the adversary — let’s call her Sue — is sniffing the encrypted data sent by the browser, then she can obtain the IV that will be used for the next message.  Now let’s say she has also identified a different block of ciphertext C that she wants to decrypt, maybe because it contains the session cookie.  While she’s at it, she can easily obtain the block of ciphertext C’ that immediately precedes C.

None of this requires more than simple eavesdropping.  Sue doesn’t know what message C encrypts — that value, which we’ll call M, is what she wants to learn — but she does know that C can be expressed using the CBC encryption formula as:

      C = AES-ENC(key, M ⊕ C’)

Sue also knows that she can get her Javascript program to transmit any chosen block of data M* that she wants.  If she does that, it will produce a ciphertext C* that she can sniff.

Now let’s make one more huge assumption.  Imagine that Sue has a few guesses for what that unknown value of M might be.  It’s 16 bytes long, but maybe it only contains a couple of bytes worth of unknown data, such as a short PIN number.  If Sue generates her value M* based on one of those guesses, she can confirm whether C actually encrypts that value.

To cut through a lot of nonsense, let’s say that she guesses M correctly.  Then she’ll generate M* as:

M* = IV ⊕ M ⊕ C’

When her Javascript program sends out M* to be encrypted, the TLS layer will encrypt it as:

C* = AES-ENC(key, IV ⊕ M*) =                       (which we can re-write as…)
AES-ENC(key, IV ⊕ IV ⊕ M ⊕ C’ ) =      (and XORing cancels…)
AES-ENC(key, M ⊕ C’)

All I’ve done above is write out the components of M* in long form, and simplify the equation based on the fact that the IV ⊕ IV term cancels out (a nice property of XOR).  The important thing to notice is that if Sue guessed correctly, the ciphertext C* that comes out of the browser will be identical to the captured ciphertext C she wants to decrypt!  If she guessed wrong, it won’t.

So assuming that Sue has time on her hands, and that there are only a few guesses, she can repeat this technique over and over again until she figures out the actual value of M.

But this guessing stuff is crazy!

If you’re paying attention, you’ll already have twigged to the one huge problem with this attack.  Yes, it works.  But it only works if she has a small number of guesses for the value M.  But in practice, M is 16 bytes long.  If she somehow knows the value of all but two bytes of that value, she might be able to guess the remaining bytes in about 2^15 (32,768) attempts on average.  But in the more likely case that she doesn’t know any of the plaintext, she has to try on average about 2^127 possible values.

In other words, she’ll be guessing until the sun goes out.

Let’s get aligned

And this is where the cleverness comes in.  I don’t know exactly what Rizzo and Duong did, but the paper by Bard hints at the answer.  Recall that when the browser encrypts a CBC-mode message, the first step is to chop the message into equal-length blocks.  If it’s using AES, these will each be 16 bytes long.

If Sue needs to guess the full contents of a random 16-byte block, she’s hosed — there are too many possibilities.  The only way this technique works in general is if she knows most of a given block, but not all of it.

But what if Sue could convince the browser to align the TLS messages in a manner that’s useful to her?  For example, she could fix things so that when the browser sends the cookie to the server, the cookie would be pre-pended with something that she knows — say, a fixed 15-byte padding.  That would mean that the stuff she wants to learn — the start of the cookie — takes up only the last byte of the block.

If Sue knows the padding, all she has to guess is the last byte.  A mere 256 possible guesses!

Now what if she can repeat this trick, but this time using a 14-byte known padding. The block would now end with two bytes of the cookie, the first of which she already knows. So again, 256 more guesses and she now knows two bytes of the cookie!  Rinse, repeat.

This technique could be quite effective, but notice that it relies on some strong assumptions about the way Sue can get the browser to format the data it sends.  Does the Rizzo and Duong attack do this?  I have absolutely no idea.  But based on my understanding of the attack and the descriptions I’ve read, it represents my best speculation.

I guess pretty soon we’ll all know how good I am at guessing.

Update 9/22/11: This post by James Yonan offers the first piece of confirmation suggesting that BEAST is based on the Bard attack.  Yonan also points out that OpenSSL has included a “patch” to defend against this issue, all the way back to version 0.9.6d (2002).  In a nutshell, the OpenSSL fix encrypts random message fragments at the start of each new message sent to the server.  This additional message fragment works like an IV, ensuring that M* is no longer structured as I describe above.  Yonan also notes that NSS very recently added a similar patch, which indicates that NSS-based browsers were the problem (this includes Firefox, Chrome).

I’m usually critical of OpenSSL for being a code nightmare.  But (pending verification) I have to give those guys a lot of credit for this one.

Where Things Fall Apart: Primitives

This is the second installment in a series on cryptographic engineering.  See here for the Introduction.

In the previous post I argued that cryptographic systems often fail, at least in part because there are so many places for them to go wrong.  Over the next several of posts I’m going to give a few examples.  This section is intended as an overview rather than a deep examination of the issues.

Primitives: Making a call

The fundamental unit of any cryptographic system is the cryptographic primitive — codes, ciphers, digital signing algorithms. Traditionally, attacking a cryptographic system meant attacking the primitive itself. History is littered with broken primitives, including many that were believed to be “unbreakable” until, well, they weren’t.
 
This isn’t purely a history lesson. Many of these broken primitives are still with us today. To find one, all you need to do is take our your cellphone. The most common cellular technology in use today is GSM (Global System for Mobile), which was developed by a consortium of European telecoms, equipment manufacturers and national governments in the 1980s.
In a move that was very advanced for the time, the GSM designers included a built-in cipher called “A5”, which was designed to protect the confidentiality of calls transmitted between a phone and the cell tower. Call encryption represented a huge improvement over the prevailing analog cellphone technology of the day, which provided essentially no privacy for voice calls (with sometimes embarrassing results).
The A5/1 cipher (courtesy Wikipedia). 

Ross Anderson describes the selection process for A5/1 in his excellent book. By his account, European governments were divided into two factions: those that wanted to strongly protect call confidentiality (mostly those states bordering the Warsaw pact) and other states, such as France, who wanted to simplify government eavesdropping. The weak cipher faction won the day. Worse, they created an even weaker variant (A5/2) for export purposes.

One of the notable aspects of A5/1 is its simplicity. It was clearly designed with efficiency in mind, particularly efficiency in hardware. As with many hardware-optimized ciphers, it consists of several interlinked Linear Feedback Shift Registers (LFSRs). While it may be possible to build a secure cipher using this technique, LFSR-based ciphers seem to be overrepresented in the ranks of broken ciphers. Unfortunately A5/1 is no exception.

For a number of years there were no public attacks against A5/1, but that’s mostly because nobody knew how it worked. The cipher design was a well-guarded secret. This changed in the mid-1990s when the full cipher was published after having being reverse-engineered from a GSM phone.

By 1997 the first attacks had been published in the research literature, and over the next decade these attacks were gradually refined. By 2006 the weakened A5/2 cipher was essentially broken, and academic attacks on A5/1 had reached a level of practicality that put them within reach of even private groups. Finally, in 2009, security researchers published and began distributing via BitTorrent a series of pre-computed tables that allow for the complete decryption of a recorded, A5/1 encrypted phone call in just a few minutes.

To a motivated adversary, calls encrypted with A5/1 are essentially cleartext.

So why has A5/1 stuck with us? There are many answers to that question. Standards tend to be “sticky” once they achieve widespread adoption. Unless there’s a viable and cost-effective plan for incrementally renewing security, it can be almost impossible to convince to move the herd. Complicating matters, many GSM phones implement A5/1 in hardware. And while software can be updated, hardware is forever.

Thus, with an installed base of millions of GSM phones (and tower equipment) throughout the world, it’s unlikely that the primitive will be replaced anytime soon. Instead, we’ll gradually drift to to a newer technology, such as the UMTS “3G” standard which employs a new, proprietary block cipher called Kasumi, or A5/3. That is, assuming Kasumi makes it that long.

Misusing Primitives

Sometimes the problem isn’t with the primitive per se, but rather in the way it’s used. There are many, many examples of this. A classic example is the Wired Equivalent Privacy (WEP) protocol that used to be the standard for securing WiFi access points.

WEP was built around Ron Rivest’s RC4 stream cipher, developed in the late 1980s. These days security professionals are deeply suspicious of RC4, mostly because it’s non-standard and because there are some theoretical attacks against it. Still, as of today none of these attacks are quite practical… as long as RC4 is used correctly.

RC4 is a stream cipher, which means that, once you set it up with a key it deterministically spits out a stream of pseudo-random bits. To encrypt you use the exclusive-OR (XOR) function to merge those bits (called a “keystream”) with your message. For reasons that we’ll discuss later, it’s very important the encryptor should never use the same keystream to encrypt two different messages. To avoid this problem, WEP uses a slightly different RC4 key for each data packet it sends.  These keys are derived by simply concatenating a fixed 40-bit or 104-bit shared key with the packet’s sequence number, also known as an “Initialization Vector”. Using || to indicate concatenation, the keys look like this:

 Packet 1 RC4 encryption key = 00001 || {WEP secret key}
 Packet 2 RC4 encryption key = 00002 || {WEP secret key}

At the time WEP debuted nobody had seriously considered the implications of setting RC4 up this way. However, in the late 1990s a trio of researchers named Fluhrer, Mantin and Shamir took a closer look. Their result? It turns out RC4 is devastatingly insecure in this configuration. Essentially what they showed is that when RC4 is used to encrypt different messages with keys that are mostly the same (but only differ in, let’s say, the last few bytes), the resulting outputs are statistically correlated. Worse — much worse — given a large enough collection such ciphertexts it’s actually possible to recover the shared portion of the key. In the case of WEP that means recovering the shared WEP secret key used by all users, essentially breaking WEP altogether.

Many of the vulnerabilities in WEP have been addressed in the WPA2 spec, which replaces RC4 with the much more standard AES cipher, and adds some other important features such as message authentication. For those legacy devices whose hardware couldn’t support AES, the WPA designers also proposed a band-aid fix called TKIP. TKIP’s an interesting case study in design compromises — but that’s a story for another post.

The Great Hash Function Adventure

Sometimes you do everything right — and you still wind up in trouble. Consider the sad story of the MD5 hash function. Once upon a time MD5 was king of the world — it was the standard used for digital signatures, for hashing software packages, and anything else you can think of. Not only was it designed by professionals, it was rigorously tested and validated by no less than the National Institutes of Standards and Technology.

Today MD5 is like zucchini. If you have it, you really want to get rid of it.

If you’re not familiar with hash functions, you probably don’t realize how critical and pervasive they are in cryptographic systems. Briefly, a hash function takes a large file and reduces it to a small, fixed-size “digest” value. If you routinely download software from open source repositories you might be accustomed to checking a 20-byte SHA1 checksum to make sure you’re not getting the wrong file.

Hash functions are also used to make digital signatures more efficient — by hashing down large files so we can sign the resulting small digest, rather than the original file itself. This works because cryptographic hash functions are assumed to be “collision resistant”; namely, it’s hard to find two files A and B such that A and B both hash to the same digest. In principle if I give you a signature on the hash of A, it should be just as good as signature on A itself.

But consider what would happen if that guarantee broke down. Say Alice wants to obtain an SSL certificate on her domain name “www.alice.com”. A digital certificate is nothing more than a file containing Alice’s identity and key, all signed by some trusted authority like Verisign. Imagine now that Alice is evil: she’s come up with one file that says she owns “www.alice.com”, and a second file that says she owns “www.bankofamerica.com”.

Moreover, because Alice has found a collision in the hash function, both of these files hash to the same value.  And Verisign doesn’t sign the files directly, it signs the hashes.

Thus if Alice can get Verisign to sign the hash of that harmless “www.alice.com” file, then she’s got a signature that also works for her malicious file as well. This is very bad, at least if you’re a Bank of America customer.

Thus, when in 2004 a team of researchers announced that they’d discovered collisions in the MD5 hash function, security professionals took it very seriously. Fortunately, the attack described above requires Alice to come up with not just any collision (i.e., two arbitrary files that hash to the same thing), but what we call a “meaningful” collision — those two values must each contain valid certificate data. Surely it wouldn’t be so easy to find such meaningful collisions!

Unfortunately, it turns out that the construction of the MD5 hash function has a particular property that makes it easy to “extend” one collision into many different collisions, some of which can be meaningful. Within a year, researchers had shown how to construct colliding software files, colliding PDF files, and most importantly, colliding digital certificates. The latter attack was particularly significant, due to the attack described above.  A malicious individual could request a signed SSL certificate on “www.my-pony-blog.com” and instead come away with a valid certificate for “www.microsoft.com”.  Or worse, a certificate designating them as a Certificate Authority, with the right to create new certificates on any domain!

 

 The “supercomputer” used to find colliding digital certificates
(yes, it’s a bunch of Sony PS3s).  From the link above.

In the short term, the solution is to remove MD5 wherever it’s used. That would almost be enough, but it seems that the next candidate for collision finding is the widely-used SHA1 hash function. Fortunately NIST, the US organization responsible for certifying cryptography, is literally two steps ahead of this one. They’ve already begun a competition to choose a new hash function that will someday be designated SHA3.

So what if you’re using all the right primitives?  In the next sections we’ll discuss another way that security systems can go wrong: bad cryptographic protocols.

Introduction

If you used an electronic system today, you almost certainly depended on a cryptographic protocol to keep you out of harm’s way. Your access might have been a credit card transaction, a purchase at Amazon.com, or even just a mobile phone call. Or it could have been any one of a hundred other types of digital activity that depends in some way on cryptography.

Cryptography (literally, “hidden writing”) isn’t a new science. It dates back almost as far as the written word. Through most of that history it wasn’t exactly a science at all; the history of designing and breaking ciphers could be best described as a rare and underappreciated art form.

All of this changed somewhere between World War II and the disco era. With the advent of the digital computer and the communications network, cryptography was forced, awkwardly, into becoming a science.  But as we’ll see in these posts, successfully using cryptography is still very much an art.

Getting the message

Historically, if you wanted to send a confidential message — military orders during a war, let’s say — your best bet was to keep the message out of enemy hands. If you couldn’t do that, you only hope was that your enemy wouldn’t be able to make sense of what he had.

To make this work in practice, both you and your intended receipient needed to share some kind of understanding (or “key”) that would allow your recipient to decode the intended meaning. Furthermore, you needed to be reasonably sure that your enemy wouldn’t share that understanding. More has been written about this problem than is worth talking about here. Suffice it to say that it wasn’t the easiest problem, but it was a tractable one.

Fast forward to today. Instead of a soldier passing through enemy territory we have messages traveling over wired and wireless networks, in full view of eavesdroppers with sophisticated equipment. To make matters more complicated, we want to communicate with parties with whom we don’t share a prior relationship; for example, a website we’ve never visited before.  Even more interestingly, we may not fully trust the recipient of the message.

And as the icing on the cake, we’re doing this on the most insecure device ever invented: the modern general purpose computer. Even with the best modern cryptographic algorithms, building secure systems is a problem we’ve barely begun to solve. If you don’t believe this, all you need to do is take a glance through the list of successful breaks we’ve seen over the past few years!

So what’s this blog about?

This blog isn’t about the science of cryptography, or the strides that cryptographers have made over the past decades. We’ll mention those, since they’re important to the matter at hand.  But mostly we’re going to talk about failure. The kind of failures that occur on a routine basis when people actually try to implement modern cryptosystems.

Those failures are many and varied. To understand them, we’ll discuss some of the basic concepts of encryption and authentication. We’ll move on to discuss software vulnerabilities and physical security, including how side-channel attacks affect cryptographic implementations. In every case we’ll give real-world examples of systems that succeeded or failed because of a specific issue.

The content of this blog is an attempt to compress a semester-long course that I give from time to time, into something that stands on its own and doesn’t require textbook lengths. It isn’t intended to be a primary source on cryptographic algorithms — for that there are many other references, which I’ll provide as time goes by.  Instead, the purpose of this blog is to provide, via examples, an understanding of all the ways that cryptographic systems can fail.  At very least you’ll develop an appreciation of how hard it is to develop these systems yourself.

And with that brief introduction…  away we go!