Apple implementing Quantum Protocol for iMessage

Apple’s Security Research team has published an article about how they are upgrading iMessage with improved security, specifically, with a new protocol called Post-Quantum 3, or PQ3. PQ3 should be resistant to its encryption being broken, even with a Quantum Computer. Before diving into the features of PQ3, a brief history, and comparison, of current encryption, starting with a brief history.

Brief History of Encryption

Encryption, at its most basic and fundamental level, is any method, or means, of taking readable text and making it unintelligible. This could be something as simple as a substitution cipher, like ROT13. ROT13 replaces each letter with one that is 13 characters ahead of it. For instance, the letter "A" would be replaced with "N", "B" would be replace with "O", and "C" would be replaced with "P". Given that there are 26 standard letters in the English alphabet, the letters end up being swapped. To illustrate what I mean, let us take the word "Apple". If you use ROT13 it would become "NCCYR". This is a very basic example of an encryption algorithm, and should not be used for anything sensitive, but it does provide a basic understanding.

Early computers did not take encryption into account, primarily because the computing power was not available. The first modern encryption protocols were developed by Netscape in 1995 and was called Secure Socket Layer, or SSL. SSL was eventually adopted by most browsers, and subsequently went through a number of revisions. Ultimately, to appease everyone involved, SSL was superseded by Transport Layer Security, or TLS, in 1999, and became an industry standard. TLS is currently at version 1.3.

Encryption is comprised of keys, and can be any length. The length of the key ends up indicating its security. The strength of a key is measured in bits, specifically the length of the key. The longer the key, the more difficult it is to break.. The first SSL algorithms could be up to 40 bits long. This was due to an export restriction by the United States government. However, that limitation has been lifted. The most common key lengths are 1024, 2048, and 4096. The longer the key length, the more difficult it would be to guess. The difficulty is not linear, instead it is logarithmic in terms of difficulty. The actual given length of time does depend on many factors, including the key length, but also the computers being used. You can easily calculate the possible number of keys, by taking 2 and raising it to the length of the key, minus 1. Therefore, for a 1024-bit key it would be 2 ^ 1023, or

possible keys. This would take an extremely long time to attempt to get the base keys used.

Another example, for a 4096 bit key, the number of combinations would be 522194440706576253345876355358312191289982124523691890192116741641976953985778728424413405967498779170445053357219631418993786719092896803631618043925682638972978488271854999170180795067191859157214035005927973113188159419698856372836167342172293308748403954352901852035642024370059304557233988891799014503343469488440893892973452815095130470299789726716411734651513348221529512507986199933857107770846917779942645743159118957217248367043905936319748237550094520674504208530837546834166925275516486044134775384991808184705966507606898412918594045916828375610659246423184062775112999150206172392431297837246097308511903252956622805412865917690043804311051417135098849101156584508839003337597742539960818209685142687562392007453579567729991395256699805775897135553415567045292136442139895777424891477161767258532611634530697452993846501061481697843891439474220308003706472837459911525285821188577408160690315522951458068463354171428220365223949985950890732881736611925133626529949897998045399734600887312408859224933727829625089164535236559716582775403784110923285873186648442456409760158728501220463308455437074192539205964902261490928669488824051563042951500651206733594863336608245755565801460390869016718045121902354170201577095168 possible combinations.

As you can see, it’s not just that it gets longer, but significantly longer.

There are a number of different means of generating the keys. These means are what is called a cipher suite, or set of algorithms. There are a number of different cipher suites, including Rivest–Shamir–Adleman (RSA), Data Encryption Standard (DES), or Advanced Encryption Standard (AES). The suite used depends on the intended usage.

There are two different types of encryption, symmetrical and asymmetrical encryption. Symmetrical encryption is where you use the same key to encrypt as well as decrypt the data.

Asymmetric encryption uses two keys, a private and public key, for encryption and decryption. Asymmetrical encryption is the basis for TLS. These two keys work in conjunction to be able to encrypt and decrypt. Only these two keys will work together. Another public key cannot function with the private key.

DES and AES are used for symmetric key cryptography, while RSA is used for public key cryptography.

How Keys Are Exchanged

One of the more common tasks for any type of encryption is the exchanging of keys. The way that this works is as follows:

1. The client sends a synchronization packet to the server.
2. The server sends a synchronization acknowledgment packet back to the client.
3. The client sends an acknowledgment back to the server, along with a Client Hello packet.
4. The server sends back a Server Hello, certificate, and Server Hello Done packet back to the client.
5. The client sends Client Key exchange, Change Cipher Specification, and Finished packet to the server.
6. The server sends a Change Cipher Specification and Finished packet to the client.

At this point, the ciphers to be used, and the public keys are established. There is a lot more information that is contained within these six steps. I will not go into detail for all of them. You can learn more about that by reading an article from CloudFlare titled What happens in a TLS handshake?, but this is a brief overview.

There are a few things that need to be pointed out. First, during the initial exchange the client sends which TLS protocols that it can understand. This is needed because the server or client may not be able to handle a particular protocol. The client and server should agree upon the highest level protocol that both can support.

The second thing to mention is that it may seem like this interaction would take a long time, but as you can probably guess, today’s devices are fast enough to support this and have this interaction take, at most, a few seconds, but in most situations this is much faster.

Now that we have a basic understanding of how key exchanges occur, let us look at how encryption works with iMessage.

How iMessage Encryption works

According to Apple’s "iMessage security overview" support article, quote:

When a user turns on iMessage on a device, the device generates encryption and signing pairs of keys for use with the service. For encryption, there is an encryption RSA 1280-bit key as well as an encryption EC 256-bit key on the NIST P-256 curve. For signatures, Elliptic Curve Digital Signature Algorithm (ECDSA) 256-bit signing keys are used. The private keys are saved in the device’s keychain and only available after first unlock. The public keys are sent to Apple Identity Service (IDS), where they are associated with the user’s phone number or email address, along with the device’s APNs address.

For iMessage keys, there would be 2^1279 possible combinations, so it is not likely that anybody could guess your private key. There is no way to derived from your private key from your public key.

Using today’s hardware, it will take an extremely long time to decrypt the data. While it may take a significantly long time on today’s hardware, that will not always be the case. This is where being proactive with post-quantum

Post Quantum Cryptography with iMessage

In Apple’s security article, Apple has outlined how it is incorporating this new PQ3 protocol into iMessage, starting with iOS 17.4.

There are actually currently four levels of cryptography, Level 0 to Level 3, with future levels possible. Level 0 and 1 are part of the "Classical Cryptography", while Level 2 and 3 are "Post-Quantium Cryptography".

Level 0

Level 0 is no-end-to-end encryption, or what is commonly called "clear-text" communications. This includes apps like Telegram, WeChat, SMS, and Skype.

Level 1

Level 1 is services that have encryption enabled by default. This includes the previous version of iMessage, as well as other apps like WhatsApp, Line, and previous versions of Signal.

Level 2

Level 2 contains services who have Post-Quantum Cryptography for key establishment only. This means that the methods used to generate the encryption keys are resistant to being broken by current day computers, as well as quantum computers. The only app that has this is Signal.

Level 3

Level 3 is similar to Level 2, except it also includes ongoing Post Quantum Cryptography rekeying . The only service that will support this, for now, is iMessage starting in iOS 17.4. Let us look at this re-keying a bit in depth.

Protecting Data

One of the possible issues with any encryption is that computers will get better and may be able to easily break previous encryption schemes. With most encryption, if a key is compromised then all of the previous messages, as well as any future messages using the same key, would be easily decrypted.

In order to protect against a key being compromised, Apple’s PQ3 takes this into account by adding the level 3 feature of ongoing rekeying. The way that this works is by changing the keys on a regular basis. Per Apple’s security article:

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.

This re-keying should go a long way to being able to protect conversations should a key get compromised. And even if a flaw s found in a cipher,

Closing Thoughts

Quantum computers being capable of breaking encryption is not anything that one needs to worry about right now. Even though there is no current worry, it is best to be proactive and Apple is doing just that. With iOS 17.4 they are updating the encryption of iMessage to include cryptography that is not only resistant to being broken by today’s computers, but also resistant to quantum computers.

Apple could match Signal and just have post-quantum keys, but instead they are going beyond that to re-keying on a regular basis and minimizing the ability to access data even if a key is compromised at some point. Even if a post-quantum cipher is broken, the current level of cryptography will still protect

This post is just an overview, and Apple’s security article has a lot more in-depth information about the ciphers used, the encryption algorithms, and additional details, should you be interested.