After watching the resident Apple-hating trolls get their panties
twisted about iMessage security in a recent thread here, I just noticed
Apple's announcement that iMessage is now encrypted with post-quantum
cryptographic algorithms born from the NIST competition a while back:

iMessage with PQ3: The new state of the art in quantum-secure messaging
at scale

<https://security.apple.com/blog/imessage-pq3/>

---
Posted by Apple Security Engineering and Architecture (SEAR)

Today we are announcing the most significant cryptographic security
upgrade in iMessage history with the introduction of PQ3, a
groundbreaking post-quantum cryptographic protocol that advances the
state of the art of end-to-end secure messaging. With
compromise-resilient encryption and extensive defenses against even
highly sophisticated quantum attacks, PQ3 is the first messaging
protocol to reach what we call Level 3 security — providing protocol
protections that surpass those in all other widely deployed messaging
apps. To our knowledge, PQ3 has the strongest security properties of any
at-scale messaging protocol in the world.

Messaging apps are placed on a spectrum starting with classical
cryptography and progressing towards quantum security. Most apps fall
into Level 0, with no end-to-end encryption by default and no quantum
security, or Level 1, with end-to-end encryption by default, but with no
quantum security. Signal’s PQXDH protocol introduces post-quantum
security in the initial key establishment at Level 2 and iMessage with
PQ3 attains Level 3, where post-quantum cryptography is used to secure
both the initial key establishment and the ongoing message exchange.

<https://security.apple.com/assets/image/generated/xlarge_quantum_security_messaging_apps_DarkMode.png>

When iMessage launched in 2011, it was the first widely available
messaging app to provide end-to-end encryption by default, and we have
significantly upgraded its cryptography over the years. We most recently
strengthened the iMessage cryptographic protocol in 2019 by switching
from RSA to Elliptic Curve cryptography (ECC), and by protecting
encryption keys on device with the Secure Enclave, making them
significantly harder to extract from a device even for the most
sophisticated adversaries. That protocol update went even further with
an additional layer of defense: a periodic rekey mechanism to provide
cryptographic self-healing even in the extremely unlikely case that a
key ever became compromised. Each of these advances were formally
verified by symbolic evaluation, a best practice that provides strong
assurances of the security of cryptographic protocols.

Historically, messaging platforms have used classical public key
cryptography, such as RSA, Elliptic Curve signatures, and Diffie-Hellman
key exchange, to establish secure end-to-end encrypted connections
between devices. All these algorithms are based on difficult
mathematical problems that have long been considered too computationally
intensive for computers to solve, even when accounting for Moore’s law.
However, the rise of quantum computing threatens to change the equation.
A sufficiently powerful quantum computer could solve these classical
mathematical problems in fundamentally different ways, and therefore —
in theory — do so fast enough to threaten the security of end-to-end
encrypted communications.

Although quantum computers with this capability don’t exist yet,
extremely well-resourced attackers can already prepare for their
possible arrival by taking advantage of the steep decrease in modern
data storage costs. The premise is simple: such attackers can collect
large amounts of today’s encrypted data and file it all away for future
reference. Even though they can’t decrypt any of this data today, they
can retain it until they acquire a quantum computer that can decrypt it
in the future, an attack scenario known as Harvest Now, Decrypt Later.

To mitigate risks from future quantum computers, the cryptographic
community has been working on post-quantum cryptography (PQC): new
public key algorithms that provide the building blocks for
quantum-secure protocols but don’t require a quantum computer to run —
that is, protocols that can run on the classical, non-quantum computers
we’re all using today, but that will remain secure from known threats
posed by future quantum computers.

To reason through how various messaging applications mitigate attacks,
it’s helpful to place them along a spectrum of security properties.
There’s no standard comparison to employ for this purpose, so we lay out
our own simple, coarse-grained progression of messaging security levels
in the image at the top of this post: we start on the left with
classical cryptography and progress towards quantum security, which
addresses current and future threats from quantum computers. Most
existing messaging apps fall either into Level 0 — no end-to-end
encryption by default and no quantum security — or Level 1 — with
end-to-end encryption by default, but with no quantum security. A few
months ago, Signal added support for the PQXDH protocol, becoming the
first large-scale messaging app to introduce post-quantum security in
the initial key establishment. This is a welcome and critical step that,
by our scale, elevated Signal from Level 1 to Level 2 security.

At Level 2, the application of post-quantum cryptography is limited to
the initial key establishment, providing quantum security only if the
conversation key material is never compromised. But today’s
sophisticated adversaries already have incentives to compromise
encryption keys, because doing so gives them the ability to decrypt
messages protected by those keys for as long as the keys don’t change.
To best protect end-to-end encrypted messaging, the post-quantum keys
need to change on an ongoing basis to place an upper bound on how much
of a conversation can be exposed by any single, point-in-time key
compromise — both now and with future quantum computers. Therefore, we
believe messaging protocols should go even further and attain Level 3
security, where post-quantum cryptography is used to secure both the
initial key establishment and the ongoing message exchange, with the
ability to rapidly and automatically restore the cryptographic security
of a conversation even if a given key becomes compromised.

iMessage now meets this goal with a new cryptographic protocol that we
call PQ3, offering the strongest protection against quantum attacks and
becoming the only widely available messaging service to reach Level 3
security. Support for PQ3 will start to roll out with the public
releases of iOS 17.4, iPadOS 17.4, macOS 14.4, and watchOS 10.4, and is
already in the corresponding developer preview and beta releases.
iMessage conversations between devices that support PQ3 are
automatically ramping up to the post-quantum encryption protocol. As we
gain operational experience with PQ3 at the massive global scale of
iMessage, it will fully replace the existing protocol within all
supported conversations this year.

Designing PQ3

More than simply replacing an existing algorithm with a new one, we
rebuilt the iMessage cryptographic protocol from the ground up to
advance the state of the art in end-to-end encryption, and to deliver on
the following requirements:

- Introduce post-quantum cryptography from the start of a conversation, so
that all communication is protected from current and future adversaries.

- Mitigate the impact of key compromises by limiting how many past and
future messages can be decrypted with a single compromised key.

- Use a hybrid design to combine new post-quantum algorithms with current
Elliptic Curve algorithms, ensuring that PQ3 can can never be less safe
than the existing classical protocol.

- Amortize message size to avoid excessive additional overhead from the
added security.

- Use formal verification methods to provide strong security assurances
for the new protocol.

PQ3 introduces a new post-quantum encryption key in the set of public
keys each device generates locally and transmits to Apple servers as
part of iMessage registration. For this application, we chose to use
Kyber post-quantum public keys, an algorithm that received close
scrutiny from the global cryptography community, and was selected by
NIST as the Module Lattice-based Key Encapsulation Mechanism standard,
or ML-KEM. This enables sender devices to obtain a receiver’s public
keys and generate post-quantum encryption keys for the very first
message, even if the receiver is offline. We refer to this as initial
key establishment.

We then include — within conversations — a periodic post-quantum
rekeying mechanism that has the ability to self-heal from key compromise
and protect future messages. In PQ3, the new keys sent along with the
conversation are used to create fresh message encryption keys that can’t
be computed from past ones, thereby bringing the conversation back to a
secure state even if previous keys were extracted or compromised by an
adversary. PQ3 is the first large scale cryptographic messaging protocol
to introduce this novel post-quantum rekeying property.

PQ3 employs a hybrid design that combines Elliptic Curve cryptography
with post-quantum encryption both during the initial key establishment
and during rekeying. Thus, the new cryptography is purely additive, and
defeating PQ3 security requires defeating both the existing, classical
ECC cryptography and the new post-quantum primitives. It also means the
protocol benefits from all the experience we accumulated from deploying
the ECC protocol and its implementations.