Cryptanalysis of the iMessage Protocol

Introductory Material

It was brought to my attention recently that the Apple publishes the details of their security protocols online (which is pretty cool of them), so I took the opportunity to do a somewhat rudimentary review of the iMessage protocol as it’s described in this document.  As that document appears to have been published in January 2018, I would say that it’s safe to assume that the iMessage protocol outlined in that document is the current protocol in use on modern iOS devices like the iPhone X and my iPhone 8.

Although I would not consider myself to be a cryptographic expert by any means, I will say that there are quite a few concerning things that I noted in my analysis.  Let me start off by just describing the protocol itself based on my understanding.

There are two parties trying to communicate – Bob and Alice.  Upon enabling iMessage on their phone for the first time, the device generates two key pairs – a 1280-bit RSA key pair and an ECDSA key pair on curve P-256.  In total, there will be four key pairs between Bob and Alice.  Here’s a little ‘demo’ to demonstrate how a message exchange might go based on my understanding from reading the linked document:

[Bob sending to Alice]

  • [1] Alice’s generated long-term key pairs: (RSA_A_priv, RSA_A_pub) & (ECDSA_A_priv, ECDSA_A_pub)
  • [2] Bob’s generated long-term key pairs: (RSA_B_priv, RSA_B_pub) & (ECDSA_B_priv, ECDSA_B_pub)
  • [3] Bob wants to send a message “Mn” to Alice
  • [4] Bob generates a random 88-bit HMAC key unique the message, lets call this HMACKey_B_A_Mn
  • [5] Bob calculates a 40-bit integrity value by making the calculation HMAC-SHA256(HMACKey_B_A_Mn, RSA_B_pub || RSA_A_pub || Mn), lets call this MAC_B_A_Mn
  • [6] Bob derives a 128-bit AES key unique to the message, derived as HMACKey_B_A_Mn || MAC_B_A_Mn, lets call this AESKey_B_A_Mn
  • [7] Bob produces the encrypted message “Mn_ENC” by performing AES-CTR-ENC(AESKey_B_A_Mn, Mn)
  • [8] Bob encrypts the AES Key itself using by performing RSA-OAEP(RSA_A_pub, AESKey_B_A_Mn), lets call this AESKey_B_A_Mn_ENC
  • [9] Bob produces a digital signature (w/ SHA-1) by making the calculation ECDSA-Sign(ECDSA_B_priv, Mn_ENC || AESKey_B_A_Mn_ENC), lets call this Sig_SHA1_Mn.
  • [10] Bob sends Mn_ENC || AES_Key_B_A_Mn_ENC || Sig_SHA1_Mn to Alice.

The Bad

From this alone it was clear to me that there are quite a few flaws with this scheme.  In order to discuss the flaws, however, I think it’s important to make this point.  Right now, entities like NIST have security targets based on bits of “security strength”:

  • The minimum strength being enforced right now is 112 bits of security strength.
  • To accomplish 112 bits of security strength, one might use algorithm primitives like: RSA 2048, ECDSA w/ P-224, Three-Key Triple-DES, SHA-224
  • Another target would be 128 bits of security strength, which is what they’d use to encrypt “Secret” data.
  • To accomplish this, one might use algorithm primitives like: RSA 3072, ECDSA w/ P-256, AES-128, SHA-256
  • Another higher target would be 192 bits of security strength, which is what they’d use to encrypt “Top Secret” data.
  • To accomplish this, one might use algorithm primitives like: RSA 7680, ECDSA w/ P-384, AES-192, SHA-384
  • And finally, in order to accomplish 256 bits of security strength: RSA 15360, ECDSA w/ P-521, AES-256, SHA-512

This brings us to flaw #1, which you’ll note affecting steps [1][2] and [8].  They use 1280-bit RSA keys, which doesn’t even meet the bare minimum requirements that are enforced by standardization bodies.  Using the General Number Field Sieve (GNFS), a 1280-bit RSA key is estimated to have a security strength equivalent to 89.46 bits.  This is clearly well below the 112 bit minimum – and a note here is that that this is exponentially weaker.  If something provides 111 bits of security strength, it it twice as easy to brute force when compared to something with 112 bits of security strength.  So the difference between 89.46 and 112 bits of security strength is a factor of 2^(112-89.46) = 6,098,402 (although I admit that saying something is 6 million times weaker in the world of cryptography isn’t truly as awful as it sounds…)

There’s also an important flaw #1.1 here that comes from the fact that they’re using RSA to transport the AES Keys at all – the iMessage protocol very clearly lacks forward secrecy.  What this means is that if an attacker is able to retrieve the encrypted contents of incoming iMessage messages and then at a later date compromises Alice’s RSA key pair, then the attacker can go back and decrypt all of the previously encrypted messages.  This is a bad property that could be easily mitigated by incorporating an algorithm like ephemeral ECDH.

If that wasn’t scary enough for you, lets move on to flaw #2 – the potential weakening of their AES Key.  The strength of a symmetric key (assuming that the underlying algorithm is secure) is largely based on the length of the key and the amount of entropy (randomness) used to produce the key.  With AES-128 (which is used by Apple here), an ideal scenario would have 128 bits of guaranteed randomness being used to establish the key.

Lets look at their key derivation combining steps [4][5] and [6]:

AESKey_B_A_Mn = HMACKey_B_A_Mn || HMAC-SHA256(HMACKey_B_A_Mn, RSA_B_pub || RSA_A_pub || Mn)

For each individual item:

  • HMACKey_B_A_Mn: Assuming good random number generation, contains 88 bits of entropy.  Note that this is not additive – while this value appears twice in their key derivation function, but does not equate to 176 bits of entropy due to it appearing twice.  Repeating the same value twice does not add any additional “randomness” when it’s known that every time the value will repeated in such a fashion.
  • RSA_B_pub: This value is known to the public as it is a public key, so it does not provide any entropy.  0 bits of entropy.
  • RSA_A_pub: This value is known to the public as it is a public key, so it does not provide any entropy.  0 bits of entropy.
  • Mn: The message itself will likely contain some randomness as people are somewhat random.  I am not privy to Apple’s message format either, so I’m not sure what all it contains that could add additional entropy (i.e.: timestamps).  Without further information, I would say you’d generally want to assume the worst case here since it’s a variable input and just assume you’re working with an empty message with 0 bits of entropy.

So in totality in the worst case there may only be 88 bits of entropy being used here to produce a 128-bit key.  This would (in effect) weaken the AES encryption being used to protect the message to an equivalent of 88 bits of security strength, which once again does not meet the lower bar of 112 bits established previously.  This is about on par with the amount of security strength that their RSA encryption is providing, however, and I’m curious if that was an intentional (and bad) design decision…

Now lets look at how the message’s integrity is verified.  There are basically two components providing integrity – the 40-bit HMACKey_B_A_Mn value and the 160-bit SHA1 digest included as part of the ECDSA signature (Sig_SHA1_Mn).  I’ll focus on just the latter portion as it’s safe to assume that the SHA1 digest is going to be providing more value.  The next flaw, flaw #3, is somewhat obvious based on a previous post that I made.  In short, collisions for SHA-1 can be found (and have provably been found) with complexity that would fall at about 61 of 63 bits of security strength.  This, once again (surprise surprise), does not meet the lower bar of 112 bits I established previously.  I’ll give them credit that they used P-256 which is designed to fall into that 128-bits of security strength group of algorithms – but the fact that they used SHA-1 as the digest (and not like SHA-256) ruined that…

I guess this also brings up a good point, which I’ll call flaw #3.1, which is just that they didn’t bother to just use a standardized authentication encryption scheme here like AES-GCM or AES-CCM, but instead decided to roll their own sort of authenticated encryption scheme using AES-CTR with a combination of a 40-bit MAC.  While this 40-bit MAC may somewhat mitigate the attack that Matt Green discussed here that resulted from the lack of a MAC in the message – a 40-bit MAC is not providing any meaningful level of security in my opinion.  I assume that the reason that it was done this way was to make it backwards compatible with the original iMessage protocol formats.

The Not-So-Bad

According to Apple’s document, there’s actually a somewhat layered approach to their encryption.  While the iMessage protocol I described above is full of holes, it looks like the encrypted message that I described above is actually communicated over a “forward-secret TLS channel” using Apple’s “Apple Push Notification” (APN) servers as a middle man.  Basically what this does (assuming the TLS is implemented correctly / securely) is that it limits the scope of the flaws I discussed above pretty significantly.  Without this TLS tunneling, the flaws I explained above would be exploitable by basically anyone that’s able to perform a network capture of the traffic coming out of an iOS device – so like people on the same WiFi network as you, ISPs, VPN providers, etc.  With the TLS tunneling, the flaws I explained above would only be exploitable to a smaller subset of attackers, such as:

  • Insider threats at Apple (or in Apple’s supply chain for producing APNs) that are able to capture traffic going through APNs
  • Attackers who are able to remotely compromise APNs and capture traffic going through them
  • Partners of Apple (say the US Government perhaps) that could compel or convince Apple to provide a “tap” into the APNs, allowing for them to exfiltrate the encrypted iMessage messages (i.e.: without the outer layer of TLS)
  • Attackers who are able to compromise the iOS devices themselves (at that point though, you’d already have access to the messages anyways)

Realistically, I guess you’d say that the flaws discussed above are basically only something that you’d worry about being exploited by someone like a nation-state level actor who has significant time and resources to spend on things like supply chain interception or server exploitation as well as brute forcing encryption with ~89 bits of security strength.

That all being said, I still definitely think that Apple needs to fix the iMessage protocol.  There are well-vetted protocols out there like the Signal Protocol that can provide higher levels of security and significantly more desirable properties that iMessage doesn’t currently offer.  To me it looks like the iMessage encryption scheme itself may have been designed a while back when 80 bits of security strength was still the “lower bar” and “forward secrecy” wasn’t really a property that was frequently talked about.  It also appears that Apple somewhat “rolled their own” cryptography scheme (possible due to lack of standardized primitives at the time or due to patch-work bug fixes along the way that molded their protocol), using a custom key derivation protocol and a custom authenticated encryption scheme.  To me, it seems like the TLS tunneling is more of a patchwork “risk mitigation” as well to mask the inherent flaws in the underlying protocol – but that’s purely speculation.

For a company with hundreds of billions of dollars in reserves, it seems like fixing up a broken protocol like iMessage would be a “no-brainer” type of undertaking – especially with them marketing themselves as such a security-minded and privacy-focused company.  Heck, for the right price maybe I’d even move out to Silicon Valley and help!

Leave a Reply

Your email address will not be published. Required fields are marked *