iMessage on an iPhone
Apple is overhauling the cryptographic security of iMessage by introducing a new messaging protocol to thwart advanced computing that has yet to become a feasible threat, and probably won't for years.
Apple already includes end-to-end encryption in its secure iMessage platform. But while elements such as Contact Key Verification can help keep users secure from current-generation computing threats, it could have a hard time taking on quantum computing.
To thwart quantum computers when they eventually become more commonly used, Apple is not waiting until they arrive to bolster its security.
As described in an Apple Security Research Blog post on Wednesday, Apple wants to protect communications that are occurring now from the future threat by introducing a new cryptographic protocol to iMessage called PQ3.
Harvest Now, Decrypt Later
Encryption relies on mathematical problems and algorithms to maintain security, with more complex models offering more security simply by the nature of how encryption is broken. If a bad actor cannot get the key to break the encryption, they instead have to rely on brute-forcing every potential combination of keys to defeat the algorithm.
For current computers, it's a time and resource-intensive task to crunch through every single possibility until the right one is discovered. However, quantum computers have the potential to do the same calculations quickly, breaking encryption.
However, quantum computing is still not available since it is still being worked on, and isn't commercially viable to roll out to a wider audience For the moment, quantum computing isn't an issue, but at some point in the future, it could be.
Banking on the probability that quantum computing will become more widespread in the future, bad actors are still holding onto encrypted data they can't access now, in the belief they can decrypt the data down the road. It is an attack scenario referred to as Harvest Now, Decrypt Later, and one that relies more on cheap storage than the expense of trying to break security by brute force.
Harvest Now, Decrypt Later does theoretically mean that all currently encrypted communications is at risk from future exposure by someone wholesale collecting communications, on the expectation that it will be easier to do with quantum computing.
Post-quantum cryptography
To try and minimize the risks from the use of quantum computing, cryptographers have worked on post-quantum cryptography (PQC). This consists of new public key algorithms that are becoming the basis of quantum-secure protocols, namely protocols that can be used by current non-quantum computers, but that are still secure when put against quantum computers.
Apple describes the state of quantum cryptography in messaging applications in a tiered approach, increasing with the level number. Level 0 and Level 1 are deemed Classical Cryptography without quantum security, while Level 2 and later are categorized as using PQC.
Level 0 is for messaging systems without any use of quantum security, nor do they use end-to-end encryption by default. This includes Skype, QQ, Telegram, and WeChat.
Level 1 is still not classed as quantum-secure, but it does include end-to-end encryption by default. Services using this include Line, Viber, WhatsApp, and the previous version of iMessage.
Moving to PQC levels, Signal is the first and only large-scale messaging app to be classed as Level 2, with its support for the Post-Quantum Extended Diffie-Hellman (PQXDH) key agreement protocol. This basically uses public keys for two parties to mutually authenticate each other at the start of a conversation.
However, even Level 2 has its issues, according to Apple, since it only provides quantum security if the conversation key isn't compromised. An attacker can potentially have the means to compromise encryption keys, providing access to the encrypted conversations until the keys are changed.
By regularly changing the keys, this places a limit on how much of a conversation an attacker could see if a key is compromised. This is the case both for acquired key access and for quantum processing attempts.
With this line of thinking, Apple says that apps should try to achieve Level 3 security, when PQC is used in securing the initial establishment of keys for communications as well as the ongoing message exchange. Level 3 should also include the ability to automatically restore cryptographic security, even if a key is compromised.
iMessage and PQ3
Apple's announcement is that it has come up with a new cryptographic protocol it calls PQ3 that will be incorporated into iMessage. The change offers "the strongest protection against quantum attacks," with iMessage becoming the first and only to support Level 3 security.
The rollout of PQ3 to iMessage will start with the public releases of iOS 17.4, iPadOS 17.4, macOS 14.4, and watchOS 10.4, and has already been incorporated into developer previews and beta releases. Existing iMessage conversations between devices that can support PQ3 will be automatically changing over to the new protocol.
Apple adds that, as it "gains operational experience with PQ3 at the massive global scale of iMessage," PQ3 will replace existing cryptographic protocols within all supported conversations by the end of 2024.
There were a number of requirements needed by Apple for PQ3 to work properly. This included introducing post-quantum cryptography from the start of a conversation, as well as limiting how much of a conversation could be decrypted with a single compromised key.
It also had to use a hybrid design that combines post-quantum algorithms with current Elliptic Curve algorithms so that PQ3 cannot be less safe than current-gen protocols. There's also a need to amortize the message size, reducing the overhead of additional security.
Lastly, it needs to use formal verification methods that can "provide strong security assurances for the new protocol," Apple writes.
On this last point, Apple has already gone to great lengths to formally verify PQ3's effectiveness, including an extensive review from multi-disciplinary teams in Apple's Security Engineering and Architecture, as well as foremost experts in cryptography.
A team led by Professor David Basin, the head of the Information Security Group at ETH Zurich, as well as Professor Douglas Stebila of the University of Waterloo, have researched post-quantum security for internet protocols. Each used different mathematical approaches to demonstrate PQ3 will remain secure so long as the underlying cryptographic algorithms hold up.
Apple also brought in a leading third-party security consultancy to independently assess PQ3's source code, and found no security issues.
How PQ3 works
PQ3 uses a new post-quantum encryption key in the public keys the devices generate locally, which are sent to Apple's servers for iMessage registration. This process lets sender devices get the receiver's public keys and to generate post-quantum encryption keys from the very first message and initial key establishment, even if the recipient is offline.
A "periodic post-quantum rekeying mechanism" is also included within conversations, which can self-heal the security from key compromises. New keys sent with conversations are used to create fresh encryption keys, which cannot be computed by analysis of previous keys, further maintaining security.
Attackers would also have to beat the hybrid design that combines both the Elliptic Curve and post-quantum elements for initial key establishment and for rekeying.
The rekeying process involves the transmission of new public key material in-band with encrypted devices that devices are exchanging with each other. New public keys based on Elliptic Curve Diffie-Hellman (ECDH) are transmitted in line with responses.
Since the post-quantum key is much larger than current existing protocols, Apple minimizes the impact of the size by making the rekeying process happen periodically, instead of every message.
The condition of whether to rekey and transmit is one that tries to balance the size of messages in a conversation, the experience of users with limited connectivity, and the need to maintain infrastructure performance. Apple adds that, if it's needed in the future, software updates could increase the rekeying frequency, while keeping the system backward-compatible with all PQ3-supporting hardware.
After implementing PQ3, iMessage will continue to use classic cryptographic algorithms to authenticate senders and verify the Contact Key Verification account key, as it says the mechanisms are not able to be attacked retroactively by future quantum computers.
To insert itself into the middle of an iMessage conversation, an attacker would need a quantum computer that could break an authentication key before or at the time the communication takes place. Apple claims this thwarts Harvest Now, Decrypt Later scenarios since it requires a quantum computer capable of performing the attack at the time of the communication itself.
Apple believes the capability to attack the new protocol is "many years away," but its security team insists it will continue to assess the needs of post-quantum authentication to defeat future attacks.
