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.

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

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

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

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

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

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

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

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

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

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

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

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

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

Notes:

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

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

Reposted: A cryptanalysis of HDCP v2.1

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

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

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

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

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

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

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

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

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

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

HDCPv2

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

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

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

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

An overview of the protocol

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

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

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

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

Phase (1): Authenticated Key Agreement (AKE)

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

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

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

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

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

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

Simple, right?

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

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

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

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

Phase (2): Pairing

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

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

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

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

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

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

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

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

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

All of this leads to the following attack:

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

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

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

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

Did I mention that protocols are hard?

Phase (3): The Locality Check

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

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

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

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

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

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

So far this looks pretty hard to beat.

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

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

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

‘Precomputed’ version of the protocol.

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

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

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

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

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

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

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

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

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

A protocol designer’s most important job is to ensure that such disagreements can never happen. The best way to do this is to ensure that there’s only one view to be had — in other words, dispense with all the options and write a single clear protocol. But if you must have options, make sure that the protocol only succeeds if both sides agree on what those options are. This is usually accomplished by authenticating the negotiation messages, but even this can be a hard, hard problem.Compared to the importance of learning those lessons, actually breaking localization is pretty trivial. It’s a stupid feature anyway.

In Conclusion

This has been a long post. To the readers I have left at this point: thanks for sticking it out.The only remaining thing I’d like to say is that this post is not intended to judge HDCPv2, or to make it look bad. It may or it may not be a good protocol, depending on whether I’ve understood the specification properly and depending on whether the above flaws make it into real devices. Which, hopefully they won’t now.

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

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

===

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

Dear Apple: Please set iMessage free

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

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

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

And nobody seems to care.

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

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

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

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

Well maybe.

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

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

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

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

For one thing, it’s surprisingly complicated.

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

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

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

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

So what’s my point with all of this?

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

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

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

On Gauss

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The real question is: how well does it work?

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

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

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

A missing post (updated)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Four theories on the cryptography of Star Trek

“I’m sorry Captain. They rotated by fourteen.”

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

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

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

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

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

Theory #1: A quantum leap

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

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

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

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

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

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

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

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

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

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

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

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

Theory #3: Complexity theory is dead

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

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

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

In the Star Trek Universe, P = NP.

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

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

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

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

Theory #4: The Stallman effect

Live long and publish your source.

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

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

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

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

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

In conclusion

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

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

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

A Few Thoughts on Cryptographic Engineering

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

So you want to use an alternative cipher…

Salsa20

Threefish

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

In conclusion

SHA3 is over. Long live SHA3!

On the (provable) security of TLS: Part 2

Records and handshakes

Welcome to 1995

Accentuating the positive

So how does the proof work?

What about stream ciphers?

In conclusion

On the (provable) security of TLS: Part 1

So you’re saying TLS is unprovable?

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

The RSA handshake

So where are we?

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

Reposted: A cryptanalysis of HDCP v2.1

HDCPv2

An overview of the protocol

Phase (1): Authenticated Key Agreement (AKE)

Phase (2): Pairing

Phase (3): The Locality Check

In Conclusion

Dear Apple: Please set iMessage free

On Gauss

A missing post (updated)

Four theories on the cryptography of Star Trek

Theory #1: A quantum leap

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

Theory #3: Complexity theory is dead

Theory #4: The Stallman effect

In conclusion

Menu