iMessage is getting a major makeover that makes it among the two messaging apps most prepared to withstand the coming advent of quantum computing, largely at parity with Signal or arguably incrementally more hardened.
On Wednesday, Apple said messages sent through iMessage will now be protected by two forms of end-to-end encryption (E2EE), whereas before, it had only one. The encryption being added, known as PQ3, is an implementation of a new algorithm called Kyber that, unlike the algorithms iMessage has used until now, can’t be broken with quantum computing. Apple isn’t replacing the older quantum-vulnerable algorithm with PQ3—it’s augmenting it. That means, for the encryption to be broken, an attacker will have to crack both.
Making E2EE future safe
The iMessage changes come five months after the Signal Foundation, maker of the Signal Protocol that encrypts messages sent by more than a billion people, updated the open standard so that it, too, is ready for post-quantum computing (PQC). Just like Apple, Signal added Kyber to X3DH, the algorithm it was using previously. Together, they’re known as PQXDH.
iMessage and Signal provide end-to-end encryption, a protection that makes it impossible for anyone other than the sender and recipient of a message to read it in decrypted form. iMessage began offering E2EE with its rollout in 2011. Signal became available in 2014.
One of the biggest looming threats to many forms of encryption is quantum computing. The strength of the algorithms used in virtually all messaging apps relies on mathematical problems that are easy to solve in one direction and extremely hard to solve in the other. Unlike a traditional computer, a quantum computer with sufficient resources can solve these problems in considerably less time.
No one knows how soon that day will come. One common estimate is that a quantum computer with 20 million qubits (a basic unit of measurement) will be able to crack a single 2,048-bit RSA key in about eight hours. The biggest known quantum computer to date has 433 qubits.
Whenever that future arrives, cryptography engineers know it’s inevitable. They also know that it’s likely some adversaries will collect and stockpile as much encrypted data now and decrypt it once quantum advances allow for it. The moves by both Apple and Signal aim to defend against that eventuality using Kyber, one of several PQC algorithms currently endorsed by the National Institute of Standards and Technology. Since Kyber is still relatively new, both iMessage and Signal will continue using the more tested algorithms for the time being.
Ratcheting up resiliency
Another important part of the iMessage upgrade is automatic key refreshing that happens behind the scenes. By changing the key regularly as messages pass back and forth, messengers become more resilient in the event of a compromise. When an adversary obtains a static key, all messages sent with it are subject to immediate decryption. Key refreshing in the same scenario limits what can be decrypted to only a single message or a small subset of messages.
Signal has always provided key refreshing through a signature innovation in the protocol known as ratcheting. Apple says its key refresh mechanism is modeled on ratcheting. To do this, Apple is replacing the elliptic-curve cryptography used since 2019 with Elliptic-curve Diffie-Hellman.
The changes Apple is announcing put iMessage at parity with Signal, both in terms of PQC hardening and the key refresh through ratcheting. Apple, however, is taking things one step further by applying ratcheting not only to the quantum-vulnerable Elliptic-curve Diffie-Hellman algorithm but also to the PQ3 being added now. This improvement comes with some limitations, though. Because of the significant overhead in refreshing keys for PQC algorithms, the key updates can’t be made with the exchange of each message as they are with the Elliptic-curve Diffie-Hellman.
As University of Waterloo professor David Jao explained in an email:
The X3DH ratchet used in Signal depends heavily on ECDH and elliptic curve arithmetic. You need to be able to add public keys together, and add private keys together, in meaningful ways. Most post-quantum replacements for ECDH do not support the same arithmetic. This makes constructing post-quantum ratchets difficult and is part of the reason why no one has implemented it before. You can do it, but as mentioned in the Apple post, the overhead goes up from 32 bytes per ratchet to 2kB per ratchet. In the messaging context, the latter overhead is quite significant, being many times larger than the messages themselves. Apple mitigates this overhead by stepping up the ratchet every ~50 messages instead of every message. Of course, this design means that the security guarantees provided by the post-quantum ratchet are lessened: an adversary that compromises keys and transmissions could potentially gain access to up to your 50 most recent messages.
Since Apple is doing BOTH the normal X3DH/ECDH ratchet and the post-quantum PQ3 ratchet, the 50-message look back only applies to the PQ part. Each individual message is still protected by the ECDH ratchet with the 32-byte overhead. So you still have to break ECDH. Assuming quantum computers eventually get built, breaking ECDH will be easy, but that is not the case presently.
For now, ratcheting in Signal will be limited only to the X3DH part of the messaging app. In a statement, Signal President Meredith Whittaker wrote:
Before we deployed PQXDH in May, 2023, we carefully considered implementing a periodic amortized quantum rekeying process, similar to the one that Apple decided on for their PQ3 specification. We decided against it, not because it isn’t a good first step, but because we wanted to find an approach that would enable quantum rekeying to occur as frequently as non-quantum re-keying does—instead of relegating it to ratcheting less often, as is the case with Apple’s PQ3 approach. Such an approach is currently the realm of novel research, and something that will require solving extant problems in order to implement at Signal’s scale. We are currently working with the cryptographic research community to explore methods that could allow us to implement more frequent quantum rekeying.
Another difference between the two apps that privacy-minded people should remember is that, by default, iMessage backs up messages within iCloud with no E2EE. Advanced encryption will do nothing to protect users in this scenario. People should either turn off iCloud backups or turn on E2EE in iCloud. (Signal doesn’t back up messages at all.)
Apple said it turned to two outside cryptography teams to verify that PQ3 is secure. Both supplied mathematical proofs, one titled Security analysis of the iMessage PQ3 protocol and the other A Formal Analysis of the iMessage PQ3 Messaging Protocol.
The iMessages changes are already available in developer preview and beta releases. They generally go into effect with the public releases of iOS 17.4, iPadOS 17.4, macOS 14.4, and watchOS 10.4.