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).