It Has Taken Us Nearly Five Decades, But Finally, We Have Security/Trust-by-Design: Meet PQ3

Prof Bill Buchanan OBE
4 min readFeb 22, 2024

--

Since the creation of the Diffie-Hellman method in 1976, we have advanced our cybersecurity. So, after nearly five decades, it seems that we are finally getting to the point when we can properly say that we are building systems which are secure and trusted by design. We now see end-to-end encryption, digital signing, key exchange and secure enclaves coming to the fore.

Yesterday, Apple announced that they were upgrading iMessage with PQ3, and which is a quantum-robust method. Why? Shor showed that all our existing public key and key exchange methods can be cracked with the advent of quantum computers. This is supported as E2E (end-to-end) communications and replaces RSA and ECDSA for digital signing and ECDH for key exchange. Apple, too, has excellent security, and where secret symmetric and asymmetric keys are stored in a secure enclave on the device, and support rekeying at defined time intervals. While quantum computers at scale are a few years off, this protects against Harvest Now, and Decrypt Later.

In Figure 1, Apple outlines that applications such as Skype and WeChat have no E2E by default. At Level 2 we see E2E supported by default but use existing public key cryptography. At Level 3, we see the integration of the PQXDH (Post Quantum Key Exchange — Diffie Hellman) method supported by Signal. This uses the Kyber key exchange method but only occurs on the initial key establishment phase. The conversation key is then not protected by post-quantum methods. Apple has advanced this to Level 3 security, and where Kyber is used for both the initial key establishment and with all the subsequent keys used for conversations. This means that a compromise of any conversation key will not compromise other keys. This is known as Forward Secrecy (FS).

Figure 1: Leve 0, 1, 2 and 3 [ref]

The method was created within the Security Engineering and Architecture (SEAR) group, as well as from the Information Security Group at ETH Zurich.

At the current time, Kyber is the only NIST-approved standard for PQC key exchange. This is a lattice method and is used to negotiate the establishment and for rekeying. While we define that this is key exchange, it is actually a Key Encapsulation Method (KEM), and where Bob will generate a symmetric key for Alice to use, and where Bob encrypts the symmetric key with Alice’s long-term public key, and then she decrypts with her private key. At various times, Bob and Alice will rekey their long-term keys. The method used is a hybrid PQC method, and where X25519 is used to integrate with Kyber — this mixes elliptic curve methods with PQC methods:

To crack, an adversary (aka Eve) would need to crack both the elliptic curve method and the Kyber method. When rekeying, Bob and Alice will use ECDH (Elliptic Curve Diffie-Hellman) to generate new public keys. The security is thus as strong as the PQC method or the ECDH method — we then get double security proofs.

Overall, a user registers devices against a single account, and where each device generates its own key pair. The associated public key is then stored on Apple’s Identity Directory Service (IDS), and associated to an email address or phone number. When a message is sent from one device, there is then a key exchange between each of the associated devices for E2E session keys. As a device might not be online at the time the message is sent, the key is encrypted with the registered public key for the recipient. Overall, there are two public keys generated: A post-quantum Kyber-1024 key encapsulation public key; and a classical elliptic curve ECDH key. These are then signed with ECDSA from the P-256 private key stored in the secure enclave on the device. This is a Contact Key Verification key and identifies the device.

When Bob wishes to communicate with Alice, we will ask the IDS for the public keys associated with Alice’s device. This will include the authentication key and signed with the Contact Key. Bob then generates two symmetric keys, one is then encapsulated with Kyber, and the other using ECDH with the registered public key for Alice.

Conclusions

Welcome, to a new hybrid world of cybersecurity. Let’s dump the legacy, and properly design our systems with a focus on security, privacy and trust. Read more here:

--

--

Prof Bill Buchanan OBE

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. Based in Edinburgh. Old World Breaker. New World Creator. Building trust.