When it comes to designing secure protocols, I have a principle that goes like this: if you have to perform any cryptographic operation before verifying the MAC on a message you've received, it will somehow inevitably lead to doom.

Let me give you two popular examples.

1. Vaudenay Attack

This is probably the best-known example of how performing a cryptographic operation before verifying the MAC on a message can go wrong.  In general, there are three different ways to combine a message authentication code with an encrypted message:

1. Authenticate And Encrypt : The sender computes a MAC of the plaintext, encrypts the plaintext, and then appends the MAC to the ciphertext. E_k1(P) || MAC_k2(P)
2. Authenticate Then Encrypt : The sender computes a MAC of the plaintext, then encrypts both the plaintext and the MAC. E_k1(P || MAC_k2(P))
3. Encrypt Then Authenticate : The sender encrypts the plaintext, then appends a MAC of the ciphertext. E_k1(P) || MAC_k2(E_k1(P))

The first often fails badly, the second mostly works, and the third is generally optimal.  The third way, "encrypt-then-authenticate," is optimal because it does not violate the doom principle.  When you receive a message, the very first thing you can do is verify the MAC.

By contrast, although "authenticate-then-encrypt" works at first glance, it does violate the doom principle.  In order to verify the MAC, the recipient first has to decrypt the message, since the MAC is part of the encrypted payload.  Many protocol designers (including the designers of SSL) did not see this as a problem, however, and so decided to test the inevitability of doom.

Vaudenay's well-known attack delivers. 

In order to decrypt ciphertext that was encrypted in CBC mode, as part of the decryption process one has to remove the padding that was originally appended to the plaintext (in order to make it a multiple of the underlying cipher's block size).  There are a number of different padding formats, but the most popular (as defined in PKCS#5) is to append the necessary N bytes of a value of N.  So if a block needs to be padded out by 5 bytes, for insance, one would append 5 bytes of the value 0x05.

When receiving a message, one would decrypt it, look at the value of the last byte (call it N), and then insure that the preceding N-1 bytes also had the value of N.  Should they have an incorrect value, one has encountered a padding error, and should abort.  Since the MAC is part of the encrypted payload, all of this needs to happen before the MAC can be verified.  And thus, inevitable doom.

If you'll recall, the CBC decryption process looks like this:

So if an attacker were to have a ciphertext message that they would like to decrypt, arbitrarily modifying the last byte of the second to last ciphertext block before sending it on to the recipient would have a deterministic effect on the last byte of the last ciphertext block. And that's the byte the receiver is going to look at in order to process the padding.

A receiver processing a message thus has two possible crypto-related error conditions: a padding error, and a MAC error.  Sometimes protocols will emit different error responses to the sender based on the condition, but even if they don't, a sender can often differentiate between the two conditions simply based on timing.

This means that if an attacker were to take a ciphertext message and arbitrarily modify the last byte of the second to last block (R, as mentioned above), it would most likely trigger a padding error.  This is because the attacker's modification tweaks the value of the last byte of the last block, which is what the receiver is looking to for padding information.  Instead of seeing 5 bytes of 0x05, for instance, the recipient will see 4 bytes of 0x05 and then a random byte of a different value.

If the attacker cycles through enough modifications of R, however, (and there are only 8bits worth) they will eventually trigger a MAC error rather than a padding error.  This is because the last byte of the last block will eventually get set to 0x01, which is valid padding.  At that point the attacker knows that the real value of the last byte of the last ciphertext block is R xor 1.  The attacker just decrypted a byte!  They can then deterministicly set the last byte value to 0x02, and do the same thing with the second to last byte of the second to last block.  And so on, until they've recovered the entire message.  Doom.

2. SSH Plaintext Recovery

The following plaintext recovery attack against SSH is another particularly clever exploitation of the doom principle.  The SSH packet format is as follows:

We see that SSH has the same problem as above: in order to verify the MAC, one first has to decrypt the message.  At first glance, however, SSH is safe, because the type of padding it uses does not make it vulnerable to Vaudenay. By specifying the padding length in a one byte field at a fixed location prior to the payload, it slips by.

SSH has another strange feature, however, which is that the length of the message itself is encrypted.  This means that before a recipient can verify the MAC, they first need to decrypt the first block of the message.  Not just so that they can calculate the MAC over the plaintext, but so that they even know how long the message is, and how much data to read off the network in order to decrypt it!

So before a recipient has verified the MAC on a message they receive, the very first thing they are going to do is decrypt the first block and interpret the first four bytes as the length of the message.  Glossing over a few details, this means that if an attacker is holding a ciphertext block they would like to decrypt (perhaps from the middle of a previously transmitted message), they can simply send it to the recipient, who will decrypt it and parse the first four bytes as a length.  The recipient will then proceed to read that many bytes off the network before verifiing the MAC.  An attacker can then send one byte at a time, until the recipient encounters a MAC error and closes the connection.  At this point the attacker will know what value the recipient interpreted that four byte length to be, thus revealing the first four bytes of plaintext in a ciphertext block. Doom again!

In Conclusion

These are two of my favorite examples, but there are actually a number of other ways in which this has manifested itself.  Watch out for it, because even if these particular cases don't apply, the general pattern will somehow inevitably cause trouble.  It always does.

From Swindle To Hazard

In recent months, Comodo has been hacked repeatedly, DigiNotar was compromised, and the security of CAs as a whole has been found to be not altogether inspiring.  The consensus finally seems to be shifting from the notion that CAs are merely a ripoff, to the notion that they are a ripoff, a security problem, and that we want them dead as immediately as possible.  The only question that remains is how to replace them.

The Trouble Comes With Generality

We need CA signatures (or an alternative authenticity infrastructure) for general purpose network communication tools: things like your web browser, command-line SSL clients, mail clients, and IM clients.  These are applications that can make arbitrary SSL connections to whatever destination you specify, and could not possibly have any advance knowledge of what SSL certificate they should expect to receive from those arbitrary locations.

Instead, these clients are given advance knowledge of a handful of CA certificates, which then sign the certificates for all of the arbitrary locations a general purpose network client would like to connect.  As they say, all problems in computer science can be solved by another layer of indirection. 

But of course, you really strike out when that abstraction layer fails.

Mobile Is An Escape

One of the interesting things about the mobile environment is that we actually have an opportunity to write client-side software again.  For better or worse, this means that mobile developers are no longer constrained by the generality of the web browser.  This has obviously been explosive in its opportunity for integration with hardware-backed services like location information, accelerometer data, camera support, and IPC with other client-side software. 

But it also creates a number of security-related opportunities, one of which is the way that mobile apps do secure communication.

If you have a mobile app that makes SSL connections to a service you control, there is really no reason to be validating your service's certificate using CA signatures.  Remember, CA signatures are for general purpose network communication, and that's not what is happening here.  We need an authenticity infrastructure when there is no way to have advance knowledge of what SSL certificate a client should expect to see, but your app knows where it will be connecting, and it knows exactly what it should expect.

Google is already doing this.  They have an "app" called Chrome, and when their app makes SSL connections to their own services, it checks to make sure that the certificates it sees are the ones it knows Google is using.  They call this "pinning," and you should do it for your mobile apps. 

There are two possible ways to do this on Android, here's how!

Option 1: Wipe The Page Clean

The first option is to leave CA certificates behind all together.  In addition to providing enhanced security, it feels refreshing.

On the server side, you'll want to create your own 4096bit signing certificate that you keep offline, and use it to sign certificates that you generate for your web services.  If you've got cash, you can do this with an HSM, otherwise you can just use OpenSSL and keep the signing certificate's key offline.

On the client side, you simply need to distribute the signing certificate with your app and validate against it.  On Android, to distribute it, first create a keystore using keytool:

Put yourapp.store in the "assets" directory of your Android app.  Now all you need to do is validate against it.  To make a standard HTTPS request:

Or in order to open a straight SSL socket, your code would be similar:

In both cases, you would obviously want to cache your SSLSocketFactory, and there's some exception handling to be done.  But by implementing something similar to the above, your App has securely opted out of the CA system entirely.

Option 2: Trust But Verify

If you need to stick with CA-signed certificates for some reason, you can limit the scope of your exposure.  By default, your App likely validates against all of the CA certificates that ship with Android, but that means any single compromised CA in the total set can potentially compromise your communication (even if it's not the CA you're using).  Your App knows what CA you're using, however, so it can limit trust to signatures from that CA only (or a small set of CAs as backup).

As explained in Adam Langley's nice Chrome writeup, you'll want to pin the SubjectPublicKeyInfo of the CA certificate you're using (and perhaps one or two others as a backup).  I've put together a small Python script for generating a pin for a certificate, available here (these are compatible with Chrome's pins — thanks are due to Adam Langley for providing his reference implementation in Go).

In order to generate your pin, you would do something similar to:  

On the Android side, I've put together a simple TrustManager implementation that is layered on top of the default system TrustManager, so that it continues validating against the system CA certificate store, but can additionally be made to enforce pins (as generated by you, above).

You can use this PinningTrustManager as follows:

...where you would, of course, substitute your own pins and destination URL.

By doing this, your App is still vulnerable to the security and whims of the CA certificates you pin, but at least you're no longer exposed to the security and whims of all 650 different CAs.

In Conclusion

Either by leaving CAs behind entirely (!), or by limiting exposure to them, anyone doing secure communication via mobile apps today has an opportunity to move beyond the constraints of the web browser and protect themselves.  Give it a shot.

In the future, hopefully we'll see solutions to the "general purpose" validation problem (such as Convergence) integrated into general purpose clients, along with "general purpose" certificate pinning solutions (such TACK).

BasicConstraints Back Then

In one week it will have been 9 years since I first published sslsniff — way back in 2002!  While sslsniff has evolved to be a general-purpose MITM tool for SSL connections, I originally published it as a proof of concept exploit for the BasicConstraints vulnerability that I released along with it.

The vulnerability was that, back then, nobody really validated certificate chains correctly.  Webkit browsers, as well as the Microsoft CryptoAPI (and by extension Internet Explorer, Outlook ,etc...), validated all the signatures in a certificate chain, but failed to check whether the intermediate certificates had a valid CA BasicConstraints extension set. This meant that you could take any old CA-signed certificate and use it to sign any other certificate.

In other words, if you bought a valid certificate for your website, what you got was the equivalent of a CA certificate. You could use it to create a valid signature for any other website, and (naturally) intercept SSL traffic.

Full Circle

Today, Gregor Kopf and Paul Kehrer released an advisory for iOS, announcing that it is also vulnerable to the BasicConstraints attack. Since this is the anniversary of the bug that prompted the release of sslsniff to begin with, I've updated it to add iOS fingerprinting support.  To intercept traffic from vulnerable iPhones, simply run:

sslsniff -a -c <path/to/your/certificate> -f ios -h <httpPort> -s <sslPort> -w iphone.log

Enjoy!

The Background

In the early 90's, at the dawn of the World Wide Web, some engineers at Netscape developed a protocol for making secure HTTP requests, and what they came up with was called SSL.  Given the relatively scarce body of knowledge concerning secure protocols at the time, as well the intense pressure everyone at Netscape was working under, their efforts can only be seen as incredibly heroic. It's amazing that SSL has endured for as long as it has, in contrast to a number of other protocols from the same vintage. We've definitely learned a lot since then, though, but the thing about protocols and APIs is that there's very little going back.

Generally speaking, all secure protocols need to provide three things: secrecy, integrity, and authenticity. If any of these break, the whole protocol breaks. SSL doesn't do any of the three very elegantly by today's standards (and in many cases just barely squeaks by), but most of the practical attacks we've seen over the past ten years have focused on the authenticity piece.  The designers of SSL chose to use Certification Authorities as a key component of the authenticity process, and we've been stuck with that decision even after having long since outgrown the circumstances in which it was originally imagined.

Lately, however, the general perception of Certification Authorities seems to be shifting from the old vibe of "total ripoff" to a new vibe of "total ripoff and also insecure." So there has been a growing amount of talk about changing the authenticity piece of SSL. I'd like to take a moment to discuss the problem, though, so that we don't accidentally make the same mistake twice.

Defining The Problem

At the moment, there seems to be a general consensus that the CA system is not long for this world, and that's a major step forward.  But while almost everyone seems to agree that we should develop something else, the exact problem with what we have is not entirely well defined.  Let's look at what people have suggested the problem might be.

1. There are too many CAs. This is perhaps the easiest conclusion to take away from the EFF's SSL observatory project. By scanning the internet, the project determined that there are approximately 650 different organizations who are currently capable of signing certificates. That seems like a lot of organizations.

   But remember when there was only one? That didn't feel any better to me. There was effectively a single vendor that could charge as much as they wanted and do whatever they wanted without any recourse. And at the time, everyone was criticizing the browsers for supporting this conspiracy by not allowing others in the club. Now that they have, they're being criticized all over again.

   So looking at this strictly in terms of quantity feels a little too simplistic for me. Much has been made about the fact that the DHS or the Chinese government have their own CA in that list, but certainly, if the DHS or the Chinese government were made to be the only valid CA, people might feel similarly annoyed, even though the quantity would be low.

2. There are a few bad apples. The subtle undertone in some of the discussions around CAs is that there are a handful of reputable CAs, and then a number of other sketchy ones. But as Chris Soghoian noted in his certified lies paper, even back when VeriSign was the only game in town, they ran a line of services that specialized in providing hosted "CALEA compliance." Basically, the very organization who had been entrusted to facilitate intercept-free communication had a division in their company that was selling intercept services.

   While some companies in this industry have been less intelligent about managing their image than others, my feeling is that there aren't really any existing players here who don't have dirt on their hands. And personally, I don't currently trust any of them.

3. There's a mixed scope. Some have suggested that the problem with all of this is the scoping. That the DHS shouldn't be able to sign certificates for Chinese sites or vice-versa. To me this seems like a low bar. There are plenty of people who don't trust the DHS to sign certificates for any sites, and restricting the Chinese government to Chinese sites doesn't feel like a particularly powerful win either. So I'm also skeptical that this is the essence of the problem. 

Trust Agility

I would like to suggest that the current problems with the CA system can be reduced to a single missing property. I call this property trust agility.

At the moment, if I decide that I don't trust VeriSign or Comodo or any other CA, what can I do? The very best I could do would be to remove the offending CA's certificate from my trusted CA database, but then some large percentage of secure sites I visit would break. I could take an ideological stand to never visit any of those sites again, but in reality, there isn't actually an appropriate response, and this is as true for browser vendors as it is for individuals like me.

Essentially, at some point a decision was made to anchor trust in an organization like Comodo, and now we're locked into trusting them — forever.

By contrast, there are two important elements to trust agility:

1. A trust decision can be easily revised at any time. It seems reasonable to think that we'll need to anchor our trust somewhere. That we'll pick some entity or group of entities to authenticate our communication. And right now, I could identify a set of organizations that I would trust to do this effectively. But what seems insane is to think that I could identify an organization who I would not only be willing to trust right now, but forever, without any future possibility of changing my mind based on that organization's performance.

   If we're locked into making a single decision now that will effect us forever, what incentive is there for the trust provider we select to act in a way that will continue to warrant our trust?

2. Individual users have the option of deciding where to anchor their trust. Some say that better scoping would fix the "bad CA problem." That if VeriSign did something particularly egregious and were somehow restricted to only authenticating certain sites, site owners would then be able to switch to a different CA in a separate scope (as opposed to now, where VeriSign can continue to sign certificates for your site even if you're not their customer). This, in a  way, would be a limited type of trust agility.

   I think it's worth recognizing, though, that if it's a struggle to convince sites to deploy SSL by default to begin with, it might be a stretch to think that site operators are going to be actively making these kinds of decisions in our best interest.  I also think it's important to recognize that different people might have different notions of what is trustworthy behavior and what isn't. A single site operator deciding who all their users are required to trust, particularly in this globalized world, doesn't feel quite right when it's the user's data — not the site operator's — that's at risk.

   By contrast, trust agility allows individual users, not site operators or anyone else, the option of deciding who they would like to trust to provide authenticity. And it allows individuals to revise those decisions at any time.

DANE, DNSSEC, and SSL Authenticity

There has been a growing flurry of activity around leveraging DNSSEC — if it ever comes to exist — as a replacement mechanism for SSL's authenticity piece. The basic idea is that instead of getting your site's certificate signed by a a Certification Authority, you just put it in your DNS record. Since DNSSEC is supposed to ensure that the DNS responses a client receives are authentic, it should prevent someone from performing a man-in-the-middle attack and substituting a forged certificate. It's essentially removing the authenticity element from SSL and using the one from DNSSEC instead.

There's an almost immediately visceral appeal to leveraging DNSSEC this way, because DNS tends to be mentally associated with the word distributed. And distributed sounds pretty good in this context.  One immediately imagines wiping Certification Authorities — who have overcharged and underprovided for so long — off the face of the internet, and replacing them with a distributed trust system instead.

But on second glance, the cold truth is that the distributed part of DNS is the information in the records, while the trust relationships are actually extremely hierarchical. This isn't any different from the current SSL situation. Already, SSL certificates themselves are distributed throughout the internet on an individual site's web server, with the trust relationships consolidated into the CA hierarchy.

So the "distributedness" of the two cases is exactly the same, the only difference being that adding DNSSEC to the mix would make things a little slower. But if the basic structure is the same, the next obvious question is whether there might be any improvement in how the DNSSEC trust relationships work compared to the current CA system.

It turns out that in the case of DNSSEC, there are three classes of people that we have to simultaneously trust:

1. The registrars. CAs are sketchy, but this is a whole new world of sketchiness. Think, sketchasaurus. Registrars were never built or selected with security in mind, and most of them don't have a very good track record in this area. Shouldn't it be laughable that the current first step in deploying DNSSEC is to create an account with GoDaddy? I mean really, do you trust this guy? Forever?

2. The TLDs. In the case of .com, that's VeriSign again. Same player, same game.

   Take a moment to look at the organizations responsible for the other generic TLDs, as well as the executives that compose those organizations. Are these the people that you would choose to trust? Forever?

   In the case of country-code TLDs, this requires trusting the governments of those TLDs. Does everyone visiting hip domains like .io, .cc, or .ly trust the corresponding government behind them? Do the citizens of localized domains like .cn or .ir want to trust their governments with all of their local secure traffic? Like it or not, governments tend to be more interested in intercepting rather than securing communication.

3. The root. This is ICANN. If the recent domain name seizures are any indication of the future, it seems like we might want to think carefully about forever making the decision to entrust all of our secure communication with this organization.

So unfortunately the DNSSEC trust relationships depend on sketchy organizations and governments, just like the current CA system.

Worse, far from providing increased trust agility, DNSSEC-based systems actually provide reduced trust agility. As unrealistic as it might be, I or a browser vendor do at least have the option of removing VeriSign from the trusted CA database, even if it would break authenticity with some large percentage of sites. With DNSSEC, there is no action that I or a browser vendor could take which would change the fact that VeriSign controls the .com TLD.

If we sign up to trust these people, we're expecting them to willfully behave forever, without any incentives at all to keep them from misbehaving. The closer you look at this process, the more reminiscent it becomes. Sites create certificates, those certificates are signed by some marginal third party, and then clients have to accept those signatures without ever having the option to choose or revise who we trust. Sound familiar?

No Trust Agility, No Future

So here we are on the cusp of something. At long last, we're finally approaching the critical mass necessary to replace the CA system that we've long since grown out of. But when evaluating replacement models for the CA system, the very first question we should ask is "who do I have to trust, and for how long?" If the answer is "a prescribed set of people, forever" we should probably proceed with extreme caution. I believe that if we don't develop a solution which offers trust agility, we will inevitably find ourselves back in the exact same place that we're currently trying to escape from.

The DNSSEC community has been struggling to get DNSSEC deployed for a long time, for the most part in the face of ambivalence. I suspect that they see the SSL authenticity piece as a potential sense of urgency which could finally make people care enough to push the DNSSEC cart over the hill, but I think we should be careful about getting on board.

I'll write more soon about alternative authenticity pieces for SSL, which do provide trust agility, that I am considerably more inspired by.

EDIT 11/27/11 :: There is a video followup to this post, where I introduce Convergence.