PQ News

On Wednesday February 21, Apple announced a major update to iMessage, their secure messaging service. iMessage forms part of the ‘Messages’ app that is only available on Apple’s iOS, iPadOS and macOS platforms, and is used for sending messages between Apple users.

This update will achieve post-quantum secure messaging for hundreds of millions of users, including the US where iMessage is currently used more frequently than WhatsApp. There’s little doubt that it’s a significant moment in the transition to PQC, and we think it’s an exciting announcement. 2024 is certainly the year in which post-quantum cryptography becomes ready for full-scale, mature product deployment!

At PQShield, we have experience with secure messaging. Our research team have published extensively on post-quantum Signal, as well as on how to protect the new MLS messaging standard against attacks from quantum computers. Last year, Signal released its own update, making it the first time a post-quantum secret messaging service has been deployed on a large scale.

Anatomy of a secure messaging protocol

There are three important components to a secure messaging protocol:

1. Establish a connection between two users who want to chat (we call this a cryptographic handshake). 
2. Secure exchange of messages between the two parties.
3. Rekeying: the continuous update of the keys used for the message exchange. 

This final component is an important part of state-of-the-art end-to-end messaging systems. For example, if Alice and Bob have been talking for a while, but Bob leaves his phone behind in a bar after a night out on the town, it could be possible to extract Bob’s secret keys from his phone (assuming any sensitive messages were previously deleted and can’t simply be retrieved directly) and then use them to decrypt all traffic between Alice and Bob going back to the beginning of their conversation, as well as all messages sent in the future. Continuously updating the messaging secrets and throwing away old keys ensures that those messages sent and deleted in the past will remain there, even in this powerful attack scenario.

The major innovation of Apple’s new protocol lies in this last component. By contrast, Signal with PQXDH (a post-quantum key agreement protocol) does not implement post-quantum rekeying. In their marketing announcement, Apple calls this a “Level 3” secure protocol, as shown in Figure 1.

Note that Signal with PQXDH remains at “Level 2”, although breaking the post-quantum security of Signal does require a powerful attack scenario. More on this later…

Figure 1: Apple describes their new PQ3 protocol as a “Level 3” secure protocol. Post-quantum Signal is designated as “Level 2”. (Image source: Apple security blog)

Post-quantum secret handshakes

Before we explore PQC rekeying in depth, let’s first discuss how messaging sessions are configured.

There are similarities between Apple’s iMessage PQ3 protocol and other protocols. For example, both Signal and PQ3 ensure Alice generates a number of one-time-use public key bundles and register them with a central facilitating server. Then, when Bob wants to initiate a chat with Alice, Bob fetches one of those bundles from the server and uses it to generate an encryption key and a ciphertext. This ciphertext is a special message that contains the key Bob generated that only Alice can open. This encryption key is also used to encrypt the first message that Bob wants to send to Alice.

The key difference between Signal’s protocol (for example X3DH/PQXDH) and Apple’s new PQ3 key exchange protocol, is that PQ3 does not provide a property referred to as deniability. Protocols with  deniability make it possible (in theory) for Bob to deny having initiated any chat messages with Alice. The protocol is set up in such a way that the handshake messages could have been generated by Alice on her own. However, because Apple uses digital (pre-quantum) digital signatures on every sent message, in PQ3, there is cryptographic proof that Bob generated each message and therefore there is no deniability.

This design decision makes the handshake protocol design easier; the change from Signal protocol’s X3DH handshake to the post-quantum secure PQXDH handshake wasn’t entirely trivial, and, as we explore later, further changes will be necessary to provide post-quantum authentication. Meanwhile Apple could simply replace the pre-quantum signatures with post-quantum signatures in their current design of PQ3, and they would be done. 

Continuous rekeying

During the exchange of messages, we need to ensure we create new keys for every new message, and discard the prior ones. Signal’s most significant contribution to secure messaging is arguably the Double Ratchet algorithm, which showed how this can be done in a very robust way. Apple’s PQ3 rekeying also builds on Double Ratchet.

The principle of Double Ratchet is that for each message that Alice sends to Bob, Alice “ratchets” her key forward using a one-way transformation (for example, a cryptographic hash function). In this way, Alice can discard old keys and use a new key for each message, while Bob does not have to be online. Ratcheting the key forward gives us forward secrecy. However, to offer post-compromise security, it’s also a requirement to do full key exchanges as often as possible.

Post-compromise security is important, as it enables Alice and Bob to recover from a secret key being leaked. For example, on Monday, Alice leaves her phone momentarily unattended and the shared secret key is extracted. Alice continues using her phone, and on Tuesday she exchanges a few more messages with Bob. The attacker can still read the first few messages; ratcheting the key forward by hashing it is not an operation that involves new secrets and thus anyone can do it. However, as soon as this exchange of messages also involves the exchange of freshly-generated public keys and ciphertexts, the attacker is no longer able to read the encrypted messages. 

Figure 2: Forward Secrecy and Post-Compromise Security together limit the impact of attacks.

This rekeying is implemented by making Alice generate a fresh public key when sending messages to Bob. She sends the key along with her messages. When Bob replies to Alice, Bob uses this public key to derive a new shared secret key and a new ciphertext, and uses this to update the key ratchet, sending the ciphertext along with his reply to Alice.

An important technical detail to reiterate is that PQ3 signs every message sent using non-deniable digital signatures, while Signal’s implementation of Double Ratchet uses deniable Message Authentication Codes (MACs). Using digital signatures is strictly less efficient than using MACs and it makes no practical difference for security. It seems then that Apple has made an explicit choice to be non-deniable.

Post-quantum rekeying

In principle, updating the Double Ratchet algorithm to use post-quantum key exchange is not very difficult. However, using ML-KEM has a significant impact on the size of the messages. The current implementation of Double Ratchet by Signal (and WhatsApp, Facebook Messenger, etc.) relies on elliptic-curve Diffie–Hellman (ECDH). An ECDH public key or ciphertext is only 64 bytes. Comparing that to the Kyber-768 algorithm used by PQ3’s ratchet, we are looking at (on average) roughly 1100 bytes, a 20x increase.

This increase in bandwidth requirements is likely the main reason for Signal’s delay in rolling out a post-quantum Double Ratchet. The bandwidth increase would affect both the users of the messaging app (who usually pay per gigabyte, after all), but also increase the cost of operating the Signal backend servers. The release of PQXDH gives Signal users post-quantum security, and only in the (fairly advanced) attack scenario of post-compromise security does it make a big difference that they do not yet have post-quantum rekeying: an attacker would need to both compromise a key on the device and record all traffic to break later.

Apple gets around the bandwidth problem by not using post-quantum rekeying for every message exchange. Most exchanges will actually still only use pre-quantum ECDH, in order to save on bandwidth. It’s only when a long time has elapsed and the circumstances are good, that iMessage performs a full post-quantum key exchange. While this only achieves an “intermediate” form of post-compromise security, it is still a step forward.  Apple describes that this is achieved by a custom tuneable heuristic that takes into account information such as the number of messages sent, as well as the network environment. It’s probable that Apple has been able to use its deep integration with the operating system as well as its deep knowledge of where and how its devices are used, to configure this heuristic.

Towards level 4: post-quantum authentication

Currently, neither Apple’s PQ3 nor the already-deployed Signal PQXDH protocol can solve the problem of post-quantum authentication (Apple’s “Level 4” in Figure 1).

We can certainly determine reasons why this is the case in Signal, and for PQ3 we can speculate. Before we discuss this, it is worth noting that achieving post-quantum confidentiality is a major step forwards as it prevents ‘harvest now, decrypt later’ attacks. In these attacks, an entity records traffic today and stores it until quantum-computing technology is sophisticated enough to decrypt it, some time in the future. It is true that to attack authentication, an attacker would need a cryptographically relevant quantum computer today. However, the problem of authentication might be more difficult to solve, and it should be investigated sooner rather than later.

For authentication, Signal’s X3DH/PQXDH protocols rely on a special property of Diffie–Hellman key exchange called “non-interactive key exchange”. Unfortunately, post-quantum key exchange mechanisms do not provide this property. This research paper, co-authored by PQShield’s Shuichi Katsumata, Thomas Prest, and Kris Kwiatkowski, in collaboration with AIST’s Keitaro Hashimoto, already shows that one solution is to use digital signatures (as PQ3 is doing). However, PQXDH would lose its deniability properties. Therefore, we need a more advanced redesign of the Signal handshake protocol to retain these properties and offer post-quantum authentication. The paper also describes how this can be done, but this relies on more advanced cryptography, namely ring signature schemes. 

As we hinted earlier, PQ3 could simply use post-quantum digital signatures, such as ML-DSA, to provide post-quantum authentication. However, Apple points out that the signing keys are stored in the secure key storage hardware of the devices on which iMessage runs. The likely problem here is that this secure hardware does not yet support post-quantum algorithms.

It’s worth pointing out that our team here at PQShield is happy to look into this, whether for Apple or for anyone encountering similar difficulties.

Celebrating formal methods

Apple has collaborated with academics from University of Waterloo and ETH Zürich to check the security of their new proposal. Douglas Stebila from UWaterloo developed a pen-and-paper proof of the security properties; David Basin, Felix Linker, and Ralf Sasse used protocol analysis tool Tamarin to model and computer-verify security properties of the PQ3 protocol. Note that Signal’s PQXDH protocol has also received formal analysis. At PQShield, we share the belief that new developments and deployments should use these techniques as much as possible – hopefully, we can share some of our own research and work with computer-aided security in the future.

Conclusions

Apple’s new PQ3 deployment is a remarkable milestone in the development and deployment of quantum-secure systems. It will impact a large number of users, and is a key turning point in the world’s transition to quantum-resistance. The real-world deployment of post-quantum rekeying is a significant step towards full post-quantum secure messaging.

At PQShield, our determination is to investigate how to reach Level 4 and beyond for quantum-secure messaging.

If you would like to find out more about our ground-breaking work on secure messaging, you can either read more in our whitepaper or watch a presentation in this on-demand webinar.