Category: TLS/SSL

How do Interception Proxies fail?

I have some substantive posts in the works, but mostly this week hasn’t been good for blogging. In the meantime, I wanted to point readers to this fascinating talk by researcher Jeff Jarmoc, which I learned about through the Corelan team blog:

SSL/TLS Interception Proxies and Transitive Trust

SSL/TLS is entrusted with securing many of the communications services we take for granted in our connected world. Threat actors are also aware of the advantages offered by encrypted communication channels, and increasingly utilize encryption for exploit delivery, malware command-and-control and data exfiltration.

To counter these tactics, organizations are increasingly deploying security controls that intercept end-to-end SSL/TLS channels. Web proxies, DLP systems, specialized threat detection solutions, and network IPSs now offer functionality to intercept, inspect and filter encrypted traffic. Similar functionality is also present in lawful intercept systems and solutions enabling the broad surveillance of encrypted communications by governments. Broadly classified as “SSL/TLS Interception Proxies,” these solutions act as man-in-the-middle, violating the end-to-end security guarantees promised by SSL/TLS.

In this presentation we’ll explore a phenomenon known as “transitive trust,” and explain how deployment of SSL/TLS interception solutions can introduce new vulnerabilities. We detail a collection of new vulnerabilities in widely used interception proxies first discovered by the Dell SecureWorks CTU and responsibly disclosed to the impacted vendors. These vulnerabilities enable attackers to more easily intercept and modify secure communications. In addition, we will introduce a public web site that organizations can use to quickly and easily test for these flaws.

I can’t find Jeff’s slides or whitepaper at the moment (Update: The slides are now public. There’s a lot more to his talk than I cover in this post.) What I can tell from the summary is that Jeff is doing us all an invaluable favor — essentially, putting his hands deep in the scuzz to find out what’s down there.

To make a long story short, the answer is nothing good. The details are in the Corelan post (which, ironically, gives me a TLS error), but to sum it up: Jeff mostly focuses on what interception proxies do when the proxy receives an invalid certificate from a remote website — for example, one that is expired or revoked.

Normally your browser would be the one dealing with this, but in a MITM scenario you’re totally dependent on the proxy. Even if the proxy checks the certificate properly in the first place, they’re still in a tough place. They essentially have the following options:

  1. Reject the connection altogether (probably safest)
  2. Give users the option to proceed or abort (no worse than standard TLS)
  3. Ignore the errors and make the connection anyway (run for the hills!) 

Jeff correctly points out that option (3) is the most dangerous, since it opens users up to all kinds of bad TLS connections that would normally ring alarm bells in your browser. Worse, this seems to be the default policy of a number of commercial interception proxies, mostly for unintentional/stupid reasons.

Beyond these default settings, it seems to be that there’s another question here, namely: how are these devices being configured in the field? My guess is that this depends greatly on whether the “victims” of interception know that their TLS traffic is being monitored. If deployers choose to do interception quietly, it could make a big difference in how a proxy will handle cert issues.

I stress that we’re now speculating, but let’s pretend that ACME corporation wants to intercept its employees’ TLS connections, but doesn’t actively want to advertise this fact.* This may restrict their options. For one thing, option (2) is probably out, since this would produce obvious messages on the end-users’ web browser. Even option (1) might be iffy, since some sites will simply not work, without any decent explanation. Hence — in speculation land — one could imagine some organizations deliberately choosing option (3), on the theory that being quiet is better than being secure.**

This is different than the vulnerabilities that Jeff addresses (which mainly deal with devices’ default settings), but it’s something I’ve been wondering about since I first heard of the practice. After all, you’ve gone to all this trouble to get a publicly-rooted MITM CA, now you’re going to advertise that you’re using it? Maybe, maybe not.

The world of TLS MITM interception is a fascinating one, and I can’t possibly learn enough about it. Hopefully we’ll soon learn even more, at least about the nasty CA-facilitated variant of it, as CAs start to respond to Mozilla’s recent ultimatum.

Notes:

* They may notify their employees somehow, but that’s different from reminding them on a daily basis. This isn’t totally nuts: it’s one speculative reason for deploying CA-generated MITM certificates, rather than generating an org certificate and installing it throughout your enterprise.

** I suppose there are workarounds for this case, such as re-writing the MITM cert to include the same class of errors (expiration dates, name errors) but I’d be utterly shocked if anyone uses them.

Attack of the week: Datagram TLS

Nadhem Alfardan and Kenny Paterson have a paper set to appear in NDSS 2012 entitled ‘Plaintext-Recovery Attacks Against Datagram TLS‘.* This is obviously music to my ears. Plaintext recovery! Datagram TLS! Padding oracles. Oh my.

There’s just one problem: the paper doesn’t seem to be online yet (Update 1/10: It is now. See my update further below.) Infoworld has a few vague details, and it looks like the vulnerability fixes are coming fast and furious. So let’s put on our thinking caps and try to puzzle this one out.

What is Datagram TLS?

If you’re reading this blog, I assume you know TLS is the go-to protocol for encrypting data over the Internet. Most people associate TLS with reliable transport mechanisms such as TCP. But TCP isn’t the only game in town.

Audio/video streaming, gaming, and VoIP apps often use unreliable datagram transports like UDP. These applications don’t care if packets arrive out of order, or if they don’t arrive at all. The biggest priority is quickly handling the packets that do arrive.

Since these applications need security too, TLS tries to handle them via an extension called Datagram TLS (DTLS). DTLS addresses the two big limitations that make TLS hard to use on an unreliable datagram transport:

  1. TLS handshake messages need to arrive whole and in the right order. This is easy when you’re using TCP, but doesn’t work so well with unreliable datagram transport. Moreover, these messages are bigger than the typical 1500 byte Ethernet frame, which means fragmentation (at best), and packet loss (at worst).
  2. Ordinarily TLS decryption assumes that you’ve received all the previous data. But datagrams arrive when they want to — that means you need the ability to decrypt a packet even if you haven’t received its predecessor.

There are various ways to deal with these problems; DTLS mounts a frontal assault. The handshake is made reliable by implementing a custom ack/re-transmit framework. A protocol-level fragmentation mechanism is added to break large handshake messages up over multiple datagrams. And most importantly: the approach to encrypting records is slightly modified.

So what’s the problem?

To avoid radical changes, DTLS inherits most of the features of TLS. That includes its wonky (and obsolete) MAC-then-Encrypt approach to protecting data records. Encryption involves three steps:

  1. Append a MAC to the plaintext to prevent tampering.
  2. Pad the resulting message to a multiple of the cipher block size (16 bytes for AES). This is done by appending X bytes of padding, where each byte must contain the value X.
  3. Encrypt the whole mess using CBC mode.

Cryptographers have long known that this kind of encryption can admit padding oracle attacks. This happens when a decryptor does something obvious (throw an error, for example) when it encounters invalid padding, i.e., padding that doesn’t meet the specification above.

CBC Mode encryption, courtesy Wikipedia.

This wouldn’t matter very much, except that CBC mode is malleable. This means an attacker can flip bits in an intercepted ciphertext, which will cause the same bits to be flipped when the ciphertext is ultimately decrypted. Padding oracle attacks work by carefully tweaking a ciphertext in specific ways before sending it to an honest decryptor. If the the decryptor returns a padding error, then the adversary knows something about the underlying plaintext. Given enough time the attacker can use these errors to completely decrypt the message.

I could spend a lot of time describing padding oracle attacks, but it’s mostly beside the point.** Standard TLS implementations know about this attack and deal with it in a pretty effective way. Whenever the decryptor encounters bad padding, it just pretends that it hasn’t. Instead, it goes ahead with the rest of the decryption procedure (i.e., checking the MAC) even if it knows that the message is already borked.

This is extra work, but it’s extra work with a purpose. If a decryptor doesn’t perform the extra steps, then messages with bad padding will get rejected considerably faster than other messages. A clever attacker can detect this condition by carefully timing the responses. Performing the unnecessary steps (mostly) neutralizes that threat.

Ok, so you say these attacks are already mitigated. Why are we still talking about this?

Before I go on, I offer one caveat: what I know about this attack comes from speculation, code diffs and some funny shapes I saw in the clouds this afternoon. I think what I’m saying is legit, but I won’t swear to it until I read Alfardan and Paterson’s paper.

But taking my best guess, there are two problems here. One is related to the DTLS spec, and the second is just an implementation problem. Either one alone probably wouldn’t be an issue; the two together spell big trouble.

The first issue is in the way that the DTLS spec deals with invalid records. Since standard TLS works over a reliable connection, the application should never receive invalid or out-of-order data except when packets are being deliberately tampered with. So when standard TLS encounters a bad record MAC (or padding) it takes things very seriously — in fact, it’s required to drop the connection.

This necessitates a new handshake, a new key, and generally makes it hard for attackers to run an honest padding oracle attack, since these attacks typically require hundreds or thousands of decryption attempts on a single key.***

DTLS, on the other hand, runs over an unreliable datagram transport, which may not correct for accidental packet errors. Dropping the connection for every corrupted packet just isn’t an option. Thus, the standard is relaxed. An invalid MAC (or padding) will cause a single record to be thrown away, but the connection itself goes on.

This still wouldn’t matter much if it wasn’t for the second problem, which is specific to the implementation of DTLS in libraries like OpenSSL and GnuTLS.

You see, padding oracle vulnerabilities in standard TLS are understood and mitigated. In OpenSSL, for example, the main decryption code has been carefully vetted. It does not return specific padding errors, and to avoid timing attacks it performs the same (unnecessary) operations whether or not the padding checks out.

In a perfect world DTLS decryption would do all the same things. But DTLS encryption is subtly different from standard TLS encryption, which means it’s implemented in separate code. Code that isn’t used frequently, and doesn’t receive the same level of scrutiny as the main TLS code. Thus — two nearly identical implementations, subject to the same attacks, with one secure and one not. (Update 1/11: There’s a decent explanation for this, see my update below.)

And if you’re the kind of person who needs this all tied up with a bow, I would point you to this small chunk of the diff just released for the latest OpenSSL fix. It comes from the DTLS-specific file d1_pkt.c:

+ /* To minimize information leaked via timing, we will always

+        * perform all computations before discarding the message.

+        */
+ decryption_failed_or_bad_record_mac = 1;

I guess that confirms the OpenSSL vulnerability. Presumably with these fixes in place, the MAC-then-Encrypt usage in DTLS will now go back to being, well, just theoretically insecure. But not actively so.

Update 1/11/2012: Kenny Paterson has kindly sent me a link to the paper, which wasn’t available when I wrote the original post. And it turns out that while the vulnerability is along the lines above, the attack is much more interesting.

An important aspect that I’d missed is that DTLS does not return error messages when it encounters invalid padding — it just silently drops the packet. This helps to explain the lack of countermeasures in the DTLS code, since the lack of responses would seem to be a padding oracle attack killer.

Alfardan and Paterson show that this isn’t the case. They’re able to get the same information by timing the arrival of ‘heartbeat’ messages (or any predictable responses sent by an upper-level protocol). Since DTLS decryption gums up the works, it can slightly delay the arrival of these packets. By measuring this ‘gumming’ they can determine whether padding errors have ocurred. Even better, they can amplify this gumming by sending ‘trains’ of valid or invalid packets.

All in all, a very clever attack. So clever, in fact, that it makes me despair that we’ll ever have truly secure systems. I guess I’ll have to be satisfied with one less insecure one.

Notes:

* N.J.A. Alfardan and K.G. Paterson, Plaintext-Recovery Attacks Against Datagram TLS, To appear in NDSS 2012.

** See here for one explanation. See also a post from this blog describing a padding oracle attack on XML encryption.

*** There is one very challenging padding oracle attack on standard TLS (also mitigated by current implementations). This deals with the problem of session drops/renegotiation by attacking data that remains constant across sessions — things like passwords or cookies.

What’s TLS Snap Start?

Google is promoting a new TLS extension which is designed to speedsugar-snap-peas up the negotiation of TLS handshakes. The extension is called called Snap Start, and it’s already been deployed in Chrome (and presumably throughout Google’s back end.)

So what is Snap Start, why is it different/better than simply resuming a TLS session, and most importantly: how snappy is it?

Background: The TLS Handshake

To understand Snap Start we need to quickly review the TLS handshake. Snap Start only supports the classic (non-ephemeral) handshake protocol, so that’s what we’ll be talking about here. Leaving out a lot of detail, that handshake can be reduced to the following four messages:

  1. C -> S: Client sends a random nonce CR.
  2. C <- S: Server responds with its public key (certificate) and another nonce SR.
  3. C -> S: Client generates a pre-master secret PMS, encrypts it with the server’s public key and sends the ciphertext to the server.
  4. C <- S: The client and server both derive a ‘master secret’ by hashing* together (CR, SR, PMS). The server and client also MAC all previous handshake messages to make sure nothing’s been tampered with. Finally the server notifies the client that it’s ready to communicate.

I’m ignoring many, many important details here. These include ciphersuite negotiation, parameter data, and — most importantly — client authentication, which we’ll come back to later. But these four messages are what we need to think about right now.

So why Snap Start?

It only takes a glance at the above protocol to identify the problem with the classic handshake: it’s frickin’ slow. Every new TLS connection requires two latency-inducing round-trips. This can be a drag when you’re trying to deploy TLS everywhere.

Now technically you don’t need to run the whole handshake each time you connect. Once you’ve established a TLS session you can resume it anytime you want — provided that both client and server retain the master secret.** Session resumption reduces communication overhead, but it isn’t the answer to everything. Most people will balk at the idea of hanging onto secret keys across machine reboots, or even browser restarts. Moreover, it’s not clear that a busy server can afford to securely cache the millions of keys it establishes every day.

What’s needed is a speedy handshake protocol that doesn’t rely on caching secret information. And that’s where Snap Start comes in.

The intuition behind Snap Start is simple: if TLS requires too many communication rounds, then why not ditch some. In this case, the target for ditching is the server’s message in step (2). Of course, once you’ve done that you may as well roll steps (1) and (3) into one mutant mega-step. This cuts the number of handshake messages in half.

There are two wrinkles with this approach — one obvious and one subtle. The obvious one is that step (2) delivers the server’s certificate. Without this certificate, the client can’t complete the rest of the protocol. Fortunately server certificates don’t change that often, so the client can simply cache one after the first time it completes the full handshake.***

Replays

The subtle issue has to do with the reason those nonces are there in the first place. From a security perspective, they’re designed to prevent replay attacks. Basically, this is a situation where an attacker retransmits captured data from one TLS session back to a server in the hopes that the server will accept it as fresh. Even if the data is stale, there are various scenarios in which replaying it could be useful.

Normally replays are prevented because the server picks a distinct (random) nonce SR in step (2), which has implications throughout the rest of the handshake. But since we no longer have a step (2), a different approach is required. Snap Start’s solution is simple: let the client propose the nonce SR, and just have the server make sure that value hasn’t been used before.

Obviously this requires the server to keep a list of previously-used SR values (called a ‘strike list’), which — assuming a busy server — could get out of control pretty fast.

The final Snap Start optimization is to tie proposed SR values with time periods. If the client suggests an SR that’s too old, reject it. This means that the server only has to keep a relatively short strike list relating to the last few minutes or hours. There are other optimizations to deal with cases where multiple servers share the same certificate, but it’s not all that interesting.

So here’s the final protocol:

  1. The client generates a random nonce CR and a proposed nonce SR. It also generates a pre-master secret PMS, encrypts it with the server’s public key and sends the ciphertext and nonces to the server.
  2. The server checks that SR hasn’t been used before/recently. Both the client and server both derive a ‘master secret’ by hashing* together (CR, SR, PMS). The server notifies the client that it’s ready to communicate.

The best part is that if anything goes wrong, the server can always force the client to engage in a normal TLS handshake.

Now for the terrible flaw in Snap Start 

No, I’m just kidding. There doesn’t seem to be anything wrong with Snap Start. With caveats. It requires some vaguely synchronized clocks. Moreover, it’s quite possible that a strike list could get wiped out in a server crash, which would open the server up to limited replays (a careful implementation could probably avoid this). Also, servers that share a single certificate could wind up vulnerable to cross-replays if their administrator forgets to configure them correctly.

One last thing I didn’t mention is that Snap Start tries to use as much of the existing TLS machinery as possible. So even though the original step (2) (‘Server Hello’ message) no longer exists, it’s ‘virtually’ recreated for the purposes of computing the TLS Finished hash check, which hashes over all preceding handshake messages. Ditto for client authentication signatures. Some new Snap-specific fields are also left out of these hashes.

As a consequence, I suppose there’s a hypothetical worry that an attack on Snap Start (due to a bad server implementation, for example) could be leveraged into an attack that works even when the client requests a normal TLS handshake. The basic idea would be to set up a man-in-the-middle that converts the client’s standard TLS handshake request into a Snap Start request, and feeds convincing lies back to the client. I’m fairly certain that the hash checks and extra Snap Start messages will prevent this attack, but I’m not 100% sure from reading the spec.

Beyond that, all of this extra logic opens the door for implementation errors and added complexity. I haven’t looked at any server-side implementations, but I would definitely like to. Nonetheless, for the moment Snap Start seems like a darned good idea. I hope it means a lot more TLS in 2012.

Notes:

* Technically this is a denoted as a PRF, but it’s typically implemented using hash functions.

** At session resumption the master secret is ‘updated’ by combining it with new client and server randomness.

*** Certificate revocation is still an issue, so Snap Start also requires caching of ‘stapled’ OCSP messages. These are valid for a week.

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.