Immediately we’re saying probably the most vital cryptographic safety improve in iMessage historical past with the introduction of PQ3, a groundbreaking post-quantum cryptographic protocol that advances the state-of-the-art of end-to-end safe messaging. With compromise-resilient encryption and in depth defenses in opposition to even extremely refined quantum assaults, PQ3 is the primary messaging protocol to achieve what we name Stage 3 safety — offering protocol protections that surpass these in all different extensively deployed messaging apps. To our data, PQ3 has the strongest safety properties of any at-scale messaging protocol on the planet.
When iMessage launched in 2011, it was the primary extensively accessible messaging app to offer end-to-end encryption by default, and now we have considerably upgraded its cryptography over time. We most lately strengthened the iMessage cryptographic protocol in 2019 by switching from RSA to Elliptic Curve cryptography (ECC), and by defending encryption keys on system with the Safe Enclave, making them considerably tougher to extract from a tool even for probably the most refined adversaries. That protocol replace went even additional with an extra layer of protection: a periodic rekey mechanism to offer cryptographic self-healing even within the extraordinarily unlikely case {that a} key ever grew to become compromised. Every of those advances have been formally verified by symbolic analysis, a finest observe that gives robust assurances of the safety of cryptographic protocols.
Traditionally, messaging platforms have used classical public key cryptography, corresponding to RSA, Elliptic Curve signatures, and Diffie-Hellman key trade, to ascertain safe end-to-end encrypted connections between gadgets. All these algorithms are based mostly on troublesome mathematical issues which have lengthy been thought of too computationally intensive for computer systems to unravel, even when accounting for Moore’s legislation. Nonetheless, the rise of quantum computing threatens to vary the equation. A sufficiently highly effective quantum laptop might clear up these classical mathematical issues in basically other ways, and due to this fact — in idea — accomplish that quick sufficient to threaten the safety of end-to-end encrypted communications.
Though quantum computer systems with this functionality don’t exist but, extraordinarily well-resourced attackers can already put together for his or her potential arrival by profiting from the steep lower in fashionable knowledge storage prices. The premise is easy: such attackers can accumulate massive quantities of right now’s encrypted knowledge and file all of it away for future reference. Regardless that they will’t decrypt any of this knowledge right now, they will retain it till they purchase a quantum laptop that may decrypt it sooner or later, an assault state of affairs often known as Harvest Now, Decrypt Later.
To mitigate dangers from future quantum computer systems, the cryptographic neighborhood has been engaged on post-quantum cryptography (PQC): new public key algorithms that present the constructing blocks for quantum-secure protocols however don’t require a quantum laptop to run — that’s, protocols that may run on the classical, non-quantum computer systems we’re all utilizing right now, however that may stay safe from recognized threats posed by future quantum computer systems.
To motive by way of how numerous messaging purposes mitigate assaults, it’s useful to put them alongside a spectrum of safety properties. There’s no commonplace comparability to make use of for this function, so we lay out our personal easy, coarse-grained development of messaging safety ranges within the picture on the prime of this submit: we begin on the left with classical cryptography and progress in direction of quantum safety, which addresses present and future threats from quantum computer systems. Most current messaging apps fall both into Stage 0 — no end-to-end encryption by default and no quantum safety — or Stage 1 — with end-to-end encryption by default, however with no quantum safety. A couple of months in the past, Sign added help for the PQXDH protocol, changing into the first large-scale messaging app to introduce post-quantum security within the preliminary key institution. This can be a welcome and important step that, by our scale, elevated Sign from Stage 1 to Stage 2 safety.
At Stage 2, the appliance of post-quantum cryptography is restricted to the preliminary key institution, offering quantum safety provided that the dialog key materials isn’t compromised. However right now’s refined adversaries have already got incentives to compromise encryption keys, as a result of doing so offers them the flexibility to decrypt messages protected by these keys for so long as the keys don’t change. To finest defend end-to-end encrypted messaging, the post-quantum keys want to vary on an ongoing foundation to put an higher certain on how a lot of a dialog might be uncovered by any single, point-in-time key compromise — each now and with future quantum computer systems. Due to this fact, we imagine messaging protocols ought to go even additional and attain Stage 3 safety, the place post-quantum cryptography is used to safe each the preliminary key institution and the continued message trade, with the flexibility to quickly and robotically restore the cryptographic safety of a dialog even when a given key turns into compromised.
iMessage now meets this aim with a brand new cryptographic protocol that we name PQ3, providing the strongest safety in opposition to quantum assaults and changing into the one extensively accessible messaging service to achieve Stage 3 safety. Help for PQ3 will begin to roll out with the general public releases of iOS 17.4, iPadOS 17.4, macOS 14.4, and watchOS 10.4, and is already within the corresponding developer preview and beta releases. iMessage conversations between gadgets that help PQ3 are robotically ramping as much as the post-quantum encryption protocol. As we acquire operational expertise with PQ3 on the large world scale of iMessage, it should totally substitute the present protocol inside all supported conversations this 12 months.
Designing PQ3
Greater than merely changing an current algorithm with a brand new one, we rebuilt the iMessage cryptographic protocol from the bottom as much as advance the state-of-the-art in end-to-end encryption, and to ship on the next necessities:
- Introduce post-quantum cryptography from the beginning of a dialog, so that each one communication is protected against present and future adversaries.
- Mitigate the impression of key compromises by limiting what number of previous and future messages might be decrypted with a single compromised key.
- Use a hybrid design to mix new post-quantum algorithms with present Elliptic Curve algorithms, making certain that PQ3 can can by no means be much less secure than the present classical protocol.
- Amortize message measurement to keep away from extreme extra overhead from the added safety.
- Use formal verification strategies to offer robust safety assurances for the brand new protocol.
PQ3 introduces a brand new post-quantum encryption key within the set of public keys every system generates regionally and transmits to Apple servers as a part of iMessage registration. For this software, we selected to make use of Kyber post-quantum public keys, an algorithm that acquired shut scrutiny from the worldwide cryptography neighborhood, and was chosen by NIST because the Module Lattice-based Key Encapsulation Mechanism commonplace, or ML-KEM. This allows sender gadgets to acquire a receiver’s public keys and generate post-quantum encryption keys for the very first message, even when the receiver is offline. We discuss with this as preliminary key institution.
We then embody — inside conversations — a periodic post-quantum rekeying mechanism that has the flexibility to self-heal from key compromise and defend future messages. In PQ3, the brand new keys despatched together with the dialog are used to create recent message encryption keys that may’t be computed from previous ones, thereby bringing the dialog again to a safe state even when earlier keys have been extracted or compromised by an adversary. PQ3 is the primary massive scale cryptographic messaging protocol to introduce this novel post-quantum rekeying property.
PQ3 employs a hybrid design that mixes Elliptic Curve cryptography with post-quantum encryption each throughout the preliminary key institution and through rekeying. Thus, the brand new cryptography is only additive, and defeating PQ3 safety requires defeating each the present, classical ECC cryptography and the brand new post-quantum primitives. It additionally means the protocol advantages from all of the expertise we amassed from deploying the ECC protocol and its implementations.
Rekeying in PQ3 includes transmitting recent public key materials in-band with the encrypted messages that gadgets are exchanging. A brand new public key based mostly on Elliptic Curve Diffie-Hellman (ECDH) is transmitted inline with each response. The post-quantum key utilized by PQ3 has a considerably bigger wire measurement than the present protocol, so to satisfy our message measurement requirement we designed the quantum-secure rekeying to occur periodically slightly than with each message. To find out whether or not a brand new post-quantum key’s transmitted, PQ3 makes use of a rekeying situation that goals to steadiness the common measurement of messages on the wire, protect the person expertise in restricted connectivity situations, and maintain the worldwide quantity of messages throughout the capability of our server infrastructure. Ought to the necessity come up, future software program updates can improve the rekeying frequency in a manner that’s backward-compatible with all gadgets that help PQ3.
With PQ3, iMessage continues to depend on classical cryptographic algorithms to authenticate the sender and confirm the Contact Key Verification account key, as a result of these mechanisms can’t be attacked retroactively with future quantum computer systems. To try to insert themselves in the course of an iMessage dialog, an adversary would require a quantum laptop able to breaking one of many authentication keys earlier than or on the time the communication takes place. In different phrases, these assaults can’t be carried out in a Harvest Now, Decrypt Later state of affairs — they require the existence of a quantum laptop able to performing the assaults contemporaneously with the communication being attacked. We imagine any such functionality remains to be a few years away, however as the specter of quantum computer systems evolves, we’ll proceed to evaluate the necessity for post-quantum authentication to thwart such assaults.
A formally confirmed protocol
Our closing requirement for iMessage PQ3 is formal verification — a mathematical proof of the meant safety properties of the protocol. PQ3 acquired in depth evaluate from Apple’s personal multi-disciplinary groups in Safety Engineering and Structure (SEAR) in addition to from a number of the world’s foremost consultants in cryptography. This features a group led by Professor David Basin, head of the Information Security Group at ETH Zürich and one of many inventors of Tamarin — a number one safety protocol verification device that was additionally used to judge PQ3 — in addition to Professor Douglas Stebila from the College of Waterloo, who has carried out in depth analysis on post-quantum safety for web protocols. Every took a unique however complementary strategy, utilizing completely different mathematical fashions to show that so long as the underlying cryptographic algorithms stay safe, so does PQ3. Lastly, a number one third-party safety consultancy supplemented our inner implementation evaluate with an impartial evaluation of the PQ3 supply code, which discovered no safety points.
Within the first mathematical evaluation, Security analysis of the iMessage PQ3 protocol, Professor Douglas Stebila centered on so-called game-based proofs. This system, also referred to as discount, defines a collection of “video games“ or logical statements to point out that the protocol is at the very least as robust because the algorithms that underpin it. Stebila’s evaluation reveals that PQ3 supplies confidentiality even within the presence of some key compromises in opposition to each classical and quantum adversaries, in each the preliminary key institution and the continued rekeying section of the protocol. The evaluation decomposes the numerous layers of key derivations all the way down to the message keys and proves that, for an attacker, they’re indistinguishable from random noise. Via an in depth demonstration that considers completely different assault paths for classical and quantum attackers within the proofs, Stebila reveals that the keys used for PQ3 are safe so long as both the Elliptic Curve Diffie-Hellman drawback stays exhausting or the Kyber post-quantum KEM stays safe.
The iMessage PQ3 protocol is a well-designed cryptographic protocol for safe messaging that makes use of state-of-the-art methods for end-to-end encrypted communication. In my evaluation utilizing the reductionist safety methodology, I confirmed that the PQ3 protocol supplies post-quantum confidentiality, which may give customers confidence within the privateness of their communication even within the face of potential enhancements in quantum computing know-how. —Professor Douglas Stebila
Within the second analysis, A Formal Analysis of the iMessage PQ3 Messaging Protocol, Prof. David Basin, Felix Linker, and Dr. Ralf Sasse at ETH Zürich use a technique referred to as symbolic analysis. As highlighted within the paper’s summary, this evaluation features a detailed formal mannequin of the iMessage PQ3 protocol, a exact specification of its fine-grained safety properties, and machine-checked proofs utilizing the state-of-the-art symbolic Tamarin prover. The analysis yielded a fine-grained evaluation of the secrecy properties of PQ3, proving that “within the absence of the sender or recipient being compromised, all keys and messages transmitted are secret” and that “compromises might be tolerated in a well-defined sense the place the impact of the compromise on the secrecy of knowledge is restricted in time and impact,” which confirms that PQ3 meets our targets.
We offer a mathematical mannequin of PQ3 in addition to show its secrecy and authenticity properties utilizing a verification device for machine-checked safety proofs. We show the properties even when the protocol operates within the presence of very robust adversaries who can corrupt events or possess quantum computer systems and due to this fact defeat classical cryptography. PQ3 goes past Sign almost about post-quantum defenses. In PQ3, a post-quantum safe algorithm is a part of the ratcheting and used repeatedly, slightly than solely as soon as within the initialization as in Sign. Our verification supplies a really excessive diploma of assurance that the protocol as designed features securely, even within the post-quantum world. —Professor David Basin
Diving into the small print
As a result of we all know PQ3 will probably be of intense curiosity to safety researchers and engineers in addition to the cryptographic neighborhood, this weblog submit is absolutely two posts in a single. So far, we laid out our design targets, outlined how PQ3 meets them, and defined how we verified our confidence within the protocol with impartial assessments. For those who’d like to grasp extra element concerning the cryptographic underpinnings, the rest of the submit is a deeper dive into how we constructed the PQ3 protocol.
Publish-quantum key institution
iMessage permits a person to register a number of gadgets on the identical account. Every system generates its personal set of encryption keys, and the personal keys are by no means exported to any exterior system. The related public keys are registered with Apple’s Id Listing Service (IDS) to allow customers to message one another utilizing a easy identifier: electronic mail handle or telephone quantity. When a person sends a message from one among their gadgets, all of their different gadgets and the entire recipient’s gadgets obtain the message. The messages are exchanged by way of pair-wise periods established between the sending system and every receiving system. The identical message is encrypted successively to every receiving system, with keys uniquely derived for every session. For the remainder of this description, we’ll give attention to a single device-to-device session.
As a result of the receiving system won’t be on-line when the dialog is established, the primary message in a session is encrypted utilizing the general public encryption keys registered with the IDS server.
Every system with PQ3 registers two public encryption keys and replaces them repeatedly with recent ones:
- A post-quantum Kyber-1024 key encapsulation public key
- A classical P-256 Elliptic Curve key settlement public key
These encryption keys are signed with ECDSA utilizing a P-256 authentication key generated by the system’s Safe Enclave, together with a timestamp used to restrict their validity. The system authentication public key’s itself signed by the Contact Key Verification account key, together with some attributes such because the supported cryptographic protocol model. This course of permits the sender to confirm that the recipient system’s public encryption keys have been uploaded by the meant recipient, and it guards in opposition to downgrade assaults.
When Alice’s system instantiates a brand new session with Bob’s system, her system queries the IDS server for the important thing bundle related to Bob’s system. The subset of the important thing bundle that incorporates the system’s authentication key and versioning data is validated utilizing Contact Key Verification. The system then validates the signature protecting the encryption keys and timestamps, which attests that the keys are legitimate and haven’t expired.
Alice’s system can then use the 2 public encryption keys to share two symmetric keys with Bob. The primary symmetric key’s computed by way of an ECDH key trade that mixes an ephemeral encryption key from Alice with Bob’s registered P-256 public key. The second symmetric key’s obtained from a Kyber key encapsulation with Bob’s post-quantum public key.
To mix these two symmetric keys, we first extract their entropy by invoking HKDF-SHA384-Extract twice — as soon as for every of the keys. The ensuing 48-byte secret is additional mixed with a site separation string and session data — which incorporates the person’s identifiers, the general public keys utilized in the important thing trade, and the encapsulated secret — by invoking HKDF-SHA384-Extract once more to derive the session’s preliminary keying state. This mixture ensures that the preliminary session state can’t be derived with out figuring out each of the shared secrets and techniques, that means an attacker would want to interrupt each algorithms to recuperate the ensuing secret, thus satisfying our hybrid safety requirement.
Publish-quantum rekeying
Ongoing rekeying of the cryptographic session is designed such that keys used to encrypt previous and future messages can’t be recomputed even by a strong hypothetical attacker who is ready to extract the cryptographic state of the system at a given time limit. The protocol generates a brand new distinctive key for every message, which periodically contains new entropy that isn’t deterministically derived from the present state of the dialog, successfully offering self-healing properties to the protocol. Our rekeying strategy is modeled after ratcheting, a method that consists of deriving a brand new session key from different keys and making certain the cryptographic state at all times strikes ahead in a single course. PQ3 combines three ratchets to realize post-quantum encryption.
The primary ratchet, referred to as the symmetric ratchet, protects older messages in a dialog to realize ahead secrecy. For each message, we derive a per-message encryption key from the present session key. The present session key itself is then additional derived into a brand new session key, ratcheting the state ahead. Every message key’s deleted as quickly as a corresponding message is decrypted, which prevents older harvested ciphertexts from being decrypted by an adversary who is ready to compromise the system at a later time, and supplies safety in opposition to replayed messages. This course of makes use of 256-bit keys and intermediate values, and HKDF-SHA384 as a derivation perform, which supplies safety in opposition to each classical and quantum computer systems.
The second ratchet, referred to as the ECDH ratchet, protects future messages by updating the session with recent entropy from an Elliptic Curve key settlement, making certain that an adversary loses the flexibility to decrypt new messages even when that they had compromised previous session keys — a property referred to as post-compromise safety. The ECDH-based ratchet has a symmetrical move: the personal key of the outgoing ratchet public key from the sender is used with the final public key acquired from the recipient to ascertain a brand new shared secret between sender and receiver, which is then blended into the session’s key materials. The brand new PQ3 protocol for iMessage makes use of NIST P-256 Elliptic Curve keys to carry out this ratchet, which imposes solely a small 32-byte overhead on every message.
As a result of the second ratchet makes use of classical cryptography, PQ3 additionally provides a conditionally executed Kyber KEM-based ratchet. This third ratchet enhances the ECDH-based ratchet to offer post-compromise safety in opposition to Harvest Now, Decrypt Later quantum assaults as effectively.
The usage of a post-quantum ratchet could cause vital community overhead in comparison with an ECDH-based ratchet on the identical safety stage. The post-quantum KEM requires sending each a public key and an encapsulated secret as a substitute of a single outgoing public key. As well as, the underlying mathematical construction for quantum safety requires considerably bigger parameter sizes for public keys and encapsulated keys in comparison with Elliptic Curves.
To restrict the dimensions overhead incurred by frequent rekeying whereas preserving a excessive stage of safety, the post-quantum KEM is instantiated with Kyber-768. In contrast to the IDS-registered public keys used for the preliminary key institution, ratcheting public keys are used solely as soon as to encapsulate a shared secret to the receiver, considerably limiting the impression of the compromise of a single key. Nonetheless, whereas a 32-byte ECDH-based ratchet overhead is appropriate on each message, the post-quantum KEM ratchet will increase the message measurement by greater than 2 kilobytes. To keep away from seen delays in message supply when system connectivity is restricted, this ratchet must be amortized over a number of messages.
We due to this fact carried out an adaptive post-quantum rekeying criterion that takes into consideration the variety of outgoing messages, the time elapsed since final rekeying, and present connectivity situations. At launch, this implies the post-quantum ratchet is carried out roughly each 50 messages, however the criterion is bounded such that rekeying is at all times assured to happen at the very least as soon as each 7 days. And as we talked about earlier, as the specter of quantum computer systems and infrastructure capability evolves over time, future software program updates can improve the rekeying frequency whereas preserving full backward compatibility.
Finishing the general public key ratchets, whether or not based mostly on ECDH or Kyber, requires sending and receiving a message. Though customers might not instantly reply to a message, iMessage contains encrypted supply receipts that enable gadgets to quickly full the ratchet even and not using a reply from the recipient, so long as the system is on-line. This system avoids delays within the rekeying course of and helps help robust post-compromise restoration.
Just like the preliminary session key institution, the secrets and techniques established by way of the three ratchets are all mixed with an evolving session key utilizing HKDF-SHA384 by way of sequential calls to the Extract perform. On the finish of this course of, we receive a closing message key, which might now be used to encrypt the payload.
Padding and encryption
To keep away from leaking details about the message measurement, PQ3 provides padding to the message earlier than encryption. This padding is carried out with the Padmé heuristic, which particularly limits the knowledge leakage of ciphertexts with most size M to a sensible optimum of O(log log M) bits. That is similar to padding to an influence of two however ends in a decrease overhead of at most 12 % and even decrease for bigger payloads. This strategy strikes a wonderful steadiness between privateness and effectivity, and preserves the person expertise in restricted system connectivity situations.
The padded payload is encrypted with AES-CTR utilizing a 256-bit encryption key and initialization vector, each derived from the message key. Whereas public key algorithms require basic modifications to realize quantum safety, symmetric cryptography algorithms just like the AES block cipher solely require doubling the important thing measurement to keep up their stage of safety in opposition to quantum computer systems.
Authentication
Every message is individually signed with ECDSA utilizing the elliptic curve P-256 system authentication key protected by the Safe Enclave. The receiving system verifies the mapping between the sender’s identifier (electronic mail handle or telephone quantity) and the general public key used for signature verification. If each customers have enabled Contact Key Verification and verified one another’s account key, the system verifies that the system authentication keys are current within the Key Transparency log and that the corresponding account key matches the account key saved within the person’s iCloud Keychain.
The system’s authentication key’s generated by the Safe Enclave and by no means uncovered to the remainder of the system, which helps stop extraction of the personal key even when the Software Processor is totally compromised. If an attacker have been to compromise the Software Processor, they could be capable to use the Safe Enclave to signal arbitrary messages. However after the system recovers from the compromise by way of a reboot or a software program replace, they might not be capable to impersonate the person. This strategy presents stronger ensures than different messaging protocols the place the authentication key’s generally shared between gadgets or the place the authentication takes place solely at the start of the session.
The message signature covers a variety of fields, together with the distinctive identifiers of the customers and their push notification tokens, the encrypted payload, authenticated knowledge, a ratchet-derived message key indicator that binds the signature to a singular location within the ratchet, and any public key data used within the protocol. The inclusion of those fields within the signature ensures that the message can solely be used within the context meant by the sender, and all of the fields are exhaustively documented within the analysis papers from Stebila, Basin, and collaborators.
Conclusion
Finish-to-end encrypted messaging has seen an incredible quantity of innovation lately, together with vital advances in post-quantum cryptography from Sign’s PQXDH protocol and in key transparency from WhatsApp’s Auditable Key Listing. Constructing on its pioneering legacy as the primary extensively accessible messaging app to offer end-to-end encryption by default, iMessage has continued to ship superior protections that surpass current techniques. iMessage Contact Key Verification is probably the most refined key transparency system for messaging deployed at scale, and is the present world state-of-the-art for automated key verification. And the brand new PQ3 cryptographic protocol for iMessage combines post-quantum preliminary key institution with three ongoing ratchets for self-healing in opposition to key compromise, defining the worldwide state-of-the-art for safeguarding messages in opposition to Harvest Now, Decrypt Later assaults and future quantum computer systems.