Monday, March 21, 2016

Attack of the Week: Apple iMessage

Today's Washington Post has a story entitled "Johns Hopkins researchers poke a hole in Apple’s encryption", which describes the results of some research my students and I have been working on over the past few months.

As you might have guessed from the headline, the work concerns Apple, and specifically Apple's iMessage text messaging protocol. Over the past months my students Christina Garman, Ian Miers, Gabe Kaptchuk and Mike Rushanan and I have been looking closely at the encryption used by iMessage, in order to determine how the system fares against sophisticated attackers. The results of this analysis include some very neat new attacks that allow us to -- under very specific circumstances -- decrypt the contents of iMessage attachments, such as photos and videos.

The research team. From left:
Gabe Kaptchuk, Mike Rushanan, Ian Miers, Christina Garman
Now before I go further, it's worth noting that the security of a text messaging protocol may not seem like the most important problem in computer security. And under normal circumstances I might agree with you. But today the circumstances are anything but normal: encryption systems like iMessage are at the center of a critical national debate over the role of technology companies in assisting law enforcement.

A particularly unfortunate aspect of this controversy has been the repeated call for U.S. technology companies to add "backdoors" to end-to-end encryption systems such as iMessage. I've always felt that one of the most compelling arguments against this approach -- an argument I've made along with other colleagues -- is that we just don't know how to construct such backdoors securely. But lately I've come to believe that this position doesn't go far enough -- in the sense that it is woefully optimistic. The fact of the matter is that forget backdoors: we barely know how to make encryption work at all. If anything, this work makes me much gloomier about the subject.

But enough with the generalities. The TL;DR of our work is this:
Apple iMessage, as implemented in versions of iOS prior to 9.3 and Mac OS X prior to 10.11.4, contains serious flaws in the encryption mechanism that could allow an attacker -- who obtains iMessage ciphertexts -- to decrypt the payload of certain attachment messages via a slow but remote and silent attack, provided that one sender or recipient device is online. While capturing encrypted messages is difficult in practice on recent iOS devices, thanks to certificate pinning, it could still be conducted by a nation state attacker or a hacker with access to Apple's servers. You should probably patch now.
For those who want the gory details, I'll proceed with the rest of this post using the "fun" question and answer format I save for this sort of post.
What is Apple iMessage and why should I care?
Those of you who read this blog will know that I have a particular obsession with Apple iMessage. This isn’t because I’m weirdly obsessed with Apple — although it is a little bit because of that. Mostly it's because I think iMessage is an important protocol. The text messaging service, which was introduced in 2011, has the distinction of being the first widely-used end-to-end encrypted text messaging system in the world. 

To understand the significance of this, it's worth giving some background. Before iMessage, the vast majority of text messages were sent via SMS or MMS, meaning that they were handled by your cellular provider. Although these messages are technically encrypted, this encryption exists only on the link between your phone and the nearest cellular tower. Once an SMS reaches the tower, it’s decrypted, then stored and delivered without further protection. This means that your most personal messages are vulnerable to theft by telecom employees or sophisticated hackers. Worse, many U.S. carriers still use laughably weak encryption and protocols that are vulnerable to active interception.

So from a security point of view, iMessage was a pretty big deal. In a single stroke, Apple deployed encrypted messaging to millions of users, ensuring (in principle) that even Apple itself couldn't decrypt their communications. The even greater accomplishment was that most people didn’t even notice this happened — the encryption was handled so transparently that few users are aware of it. And Apple did this at very large scale: today, iMessage handles peak throughput of more than 200,000 encrypted messages per second, with a supported base of nearly one billion devices. 
So iMessage is important. But is it any good?
Answering this question has been kind of a hobby of mine for the past couple of years. In the past I've written about Apple's failure to publish the iMessage protocol, and on iMessage's dependence on a vulnerable centralized key server. Indeed, the use of a centralized key server is still one of iMessage's biggest weaknesses, since an attacker who controls the keyserver can use it to inject keys and conduct man in the middle attacks on iMessage users.

But while key servers are a risk, attacks on a key server seem fundamentally challenging to implement -- since they require the ability to actively manipulate Apple infrastructure without getting caught. Moreover, such attacks are only useful for prospective surveillance. If you fail to substitute a user's key before they have an interesting conversation, you can't recover their communications after the fact.

A more interesting question is whether iMessage's encryption is secure enough to stand up against retrospective decryption attacks -- that is, attempts to decrypt messages after they have been sent. Conducting such attacks is much more interesting than the naive attacks on iMessage's key server, since any such attack would require the existence of a fundamental vulnerability in iMessage's encryption itself. And in 2016 encryption seems like one of those things that we've basically figured out how to get right.

Which means, of course, that we probably haven't.
How does iMessage encryption work?
What we know about the iMessage encryption protocol comes from a previous reverse-engineering effort by a group from Quarkslab, as well as from Apple's iOS Security Guide. Based on these sources, we arrive at the following (simplified) picture of the basic iMessage encryption scheme:


To encrypt an iMessage, your phone first obtains the RSA public key of the person you're sending to. It then generates a random AES key k and encrypts the message with that key using CTR mode. Then it encrypts k using the recipient's RSA key. Finally, it signs the whole mess using the sender's ECDSA signing key. This prevents tampering along the way.

So what's missing here?

Well, the most obviously missing element is that iMessage does not use a Message Authentication Code (MAC) or authenticated encryption scheme to prevent tampering with the message. To simulate this functionality, iMessage simply uses an ECDSA signature formulated by the sender. Naively, this would appear to be good enough. Critically, it's not.

The attack works as follows. Imagine that a clever attacker intercepts the message above and is able to register her own iMessage account. First, the attacker strips off the original ECDSA signature made by the legitimate sender, and replaces it with a signature of her own. Next, she sends the newly signed message to the original recipient using her own account:


The outcome is that the user receives and decrypts a copy of the message, which has now apparently originated from the attacker rather than from the original sender. Ordinarily this would be a pretty mild attack -- but there's a useful wrinkle. In replacing the sender's signature with one of her own, the attacker has gained a powerful capability. Now she can tamper with the AES ciphertext (red) at will.

Specifically, since in iMessage the AES ciphertext is not protected by a MAC, it is therefore malleable. As long as the attacker signs the resulting message with her key, she can flip any bits in the AES ciphertext she wants -- and this will produce a corresponding set of changes when the recipient ultimately decrypts the message. This means that, for example, if the attacker guesses that the message contains the word "cat" at some position, she can flip bits in the ciphertext to change that part of the message to read "dog" -- and she can make this change even though she can't actually read the encrypted message.

Only one more big step to go.

Now further imagine that the recipient's phone will decrypt the message correctly provided that the underlying plaintext that appears following decryption is correctly formatted. If the plaintext is improperly formatted -- for a silly example, our tampering made it say "*7!" instead of "pig" -- then on receiving the message, the recipient's phone might return an error that the attacker can see.

It's well known that such a configuration capability allows our attacker the ability to learn information about the original message, provided that she can send many "mauled" variants to be decrypted. By mauling the underlying message in specific ways -- e.g., attempting to turn "dog" into "pig" and observing whether decryption succeeds -- the attacker can gradually learn the contents of the original message. The technique is known as a format oracle, and it's similar to the padding oracle attack discovered by Vaudenay.
So how exactly does this format oracle work?
The format oracle in iMessage is not a padding oracle. Instead it has to do with the compression that iMessage uses on every message it sends.

You see, prior to encrypting each message payload, iMessage applies a complex formatting that happens to conclude with gzip compression. Gzip is a modestly complex compression scheme that internally identifies repeated strings, applies Huffman coding, then tacks a CRC checksum computed over the original data at the end of the compressed message. It's this gzip-compressed payload that's encrypted within the AES portion of an iMessage ciphertext.

It turns out that given the ability to maul a gzip-compressed, encrypted ciphertext, there exists a fairly complicated attack that allows us to gradually recover the contents of the message by mauling the original message thousands of times and sending the modified versions to be decrypted by the target device. The attack turns on our ability to maul the compressed data by flipping bits, then "fix up" the CRC checksum correspondingly so that it reflects the change we hope to see in the uncompressed data. Depending on whether that test succeeds, we can gradually recover the contents of a message -- one byte at a time.

While I'm making this sound sort of simple, the truth is it's not. The message is encoded using Huffman coding, with a dynamic Huffman table we can't see -- since it's encrypted. This means we need to make laser-specific changes to the ciphertext such that we can predict the effect of those changes on the decrypted message, and we need to do this blind. Worse, iMessage has various countermeasures that make the attack more complex.

The complete details of the attack appear in the paper, and they're pretty eye-glazing, so I won't repeat them here. In a nutshell, we are able to decrypt a message under the following conditions:
  1. We can obtain a copy of the encrypted message
  2. We can send approximately 2^18 (invisible) encrypted messages to the target device
  3. We can determine whether or not those messages decrypted successfully or not
The first condition can be satisfied by obtaining ciphertexts from a compromise of Apple's Push Notification Service servers (which are responsible for routing encrypted iMessages) or by intercepting TLS connections using a stolen certificate -- something made more difficult due to the addition of certificate pinning in iOS 9. The third element is the one that initially seems the most challenging. After all, when I send an iMessage to your device, there's no particular reason that your device should send me any sort of response when the message decrypts. And yet this information is fundamental to conducting the attack!

It turns out that there's a big exception to this rule: attachment messages.
How do attachment messages differ from normal iMessages?
When I include a photo in an iMessage, I don't actually send you the photograph through the normal iMessage channel. Instead, I first encrypt that photo using a random 256-bit AES key, then I compute a SHA1 hash and upload the encrypted photo to iCloud. What I send you via iMessage is actually just an iCloud.com URL to the encrypted photo, the SHA1 hash, and the decryption key.

Contents of an "attachment" message.
When you successfully receive and decrypt an iMessage from some recipient, your Messages client will automatically reach out and attempt to download that photo. It's this download attempt, which happens only when the phone successfully decrypts an attachment message, that makes it possible for an attacker to know whether or not the decryption has succeeded.

One approach for the attacker to detect this download attempt is to gain access to and control your local network connections. But this seems impractical. A more sophisticated approach is to actually maul the URL within the ciphertext so that rather than pointing to iCloud.com, it points to a related URL such as i8loud.com. Then the attacker can simply register that domain, place a server there and allow the client to reach out to it. This requires no access to the victim's local network.

By capturing an attachment message, repeatedly mauling it, and monitoring the download attempts made by the victim device, we can gradually recover all of the digits of the encryption key stored within the attachment. Then we simply reach out to iCloud and download the attachment ourselves. And that's game over. The attack is currently quite slow -- it takes more than 70 hours to run -- but mostly because our code is slow and not optimized. We believe with more engineering it could be made to run in a fraction of a day.

Result of decrypting the AES key for an attachment. Note that the ? represents digits we could not recover for various reasons, typically due to string repetitions. We can brute-force the remaining digits.
The need for an online response is why our attack currently works against attachment messages only: those are simply the messages that make the phone do visible things. However, this does not mean the flaw in iMessage encryption is somehow limited to attachments -- it could very likely be used against other iMessages, given an appropriate side-channel.
How is Apple fixing this?
Apple's fixes are twofold. First, starting in iOS 9.0 (and before our work), Apple began deploying aggressive certificate pinning across iOS applications. This doesn't fix the attack on iMessage crypto, but it does make it much harder for attackers to recover iMessage ciphertexts to decrypt in the first place.

Unfortunately even if this works perfectly, Apple still has access to iMessage ciphertexts. Worse, Apple's servers will retain these messages for up to 30 days if they are not delivered to one of your devices. A vulnerability in Apple Push Network authentication, or a compromise of these servers could read them all out. This means that pinning is only a mitigation, not a true fix.

As of iOS 9.3, Apple has implemented a short-term mitigation that my student Ian Miers proposed. This relies on the fact that while the AES ciphertext is malleable, the RSA-OAEP portion of the ciphertext is not. The fix maintains a "cache" of recently received RSA ciphertexts and rejects any repeated ciphertexts. In practice, this shuts down our attack -- provided the cache is large enough. We believe it probably is.

In the long term, Apple should drop iMessage like a hot rock and move to Signal/Axolotl.
So what does it all mean?
As much as I wish I had more to say, fundamentally, security is just plain hard. Over time we get better at this, but for the foreseeable future we'll never be ahead. The only outcome I can hope for is that people realize how hard this process is -- and stop asking technologists to add unacceptable complexity to systems that already have too much of it.

14 comments:

  1. Excellent reading, very nice paper. I was wondering if including an HMAC of the message using k as the key (or another key encrypted in the RSA ciphertext) would negate the attack.

    ReplyDelete
  2. Cool! Could Manger's attack on RSA OAEP be applicable here by any chance?

    ReplyDelete
  3. > In the long term, Apple should drop iMessage like a hot rock and move to Signal/Axolotl.
    Do you mean this seriously? What would the cost be for Apple to migrate?

    ReplyDelete
    Replies
    1. Will never happen. iMessage is one of the platform's top features, and not necessarily for its security/privacy.

      Delete
    2. Axolotl is an open protocol: https://whispersystems.org/blog/advanced-ratcheting/
      So Matthew didn't suggest Apple should switch to Signal application, but changes the underlying iMessage protocol.

      Delete
  4. This was a great read, thanks! Any comments on weak bit strenth of RSA keys? 1280 is way below the security margin (according to Lenstra's equations, the optimistic assumption is 1280-bit RSA fails by 2017). This could enable retrospective decryption of all ciphertexts of specific targets. Moore's law would state the amount of targets will double every 18 months

    ReplyDelete
  5. Would it not be sufficient to use authenticated encryption for the symmetric (DEM) part of the encrypted message? In other words, just use a CCA-secure signcryption scheme? CCA-insecurity when using a malleable DEM is a basic exercise in e.g., Katz-Lindell's textbook.

    ReplyDelete
  6. I might not understood it right on first read, but if you can change just one bit in the url to poit to i8loud.com, then you should be able to figure out the original url just by looking at the server logs. What am I missing?

    ReplyDelete
    Replies
    1. The point is not to figure out the original url. You repeatedly maul the attachment message to figure out the encryption key. This is what is needed to download the attachment. The url is not enough

      Delete
  7. This was a great read, thanks!

    ReplyDelete
  8. Is it obviously detectable by the owner of the phone? It appears that the phone would receive very many garbled messages/attachments/pictures from an unknown sender. Using the phone itself as a validity oracle to decrypt messages seems to leave substantial evidence of the adversary's actions.

    ReplyDelete
  9. Great research. Can you do it for the RCS system that Google and the carriers plan to adopt soon? I'd rather a similar paper came out before they got a chance to promote that service as amazing and even got people to switch away from iMessage or Whatsapp. Its insecurity needs to be exposed now.

    ReplyDelete
  10. I'm also curious about Nikos Fotiou's question. This article seems to suggest that a signature is not as good as a HMAC. However, it seems to me that the critical missing step in this protocol is that they don't check that the key that produced the signature is "connected" to the key that encrypted the message. If you just attached a random MAC, using a different key, I think you could have the same problem (that is, an attacker could replace your MAC with their own). Am I misunderstanding something?

    In this case of iMessage, the fact that they use three different encryption technologies (RSA to encrypt the AES key, AES to encrypt the message, ECDSA to sign the message) means this is not trivial to fix, and its simpler with an HMAC where the encryption key and the signature key are the same. However, if they had signed the message with the original RSA key instead of using ECDSA, I think they could have avoided this weakness!

    I'm always impressed: cryptographic protocols are so easy to screw up.

    ReplyDelete