Apple Announces 'Groundbreaking' New Security Protocol for iMessage

Can you explain the difference and what attacks PQ rekeying prevents that PQ key exchanging doesn't? When "the article" is a an apple fan boi site regurgitating apple press releases in breathless fashion, you might want to take their claims with a grain of salt.

Short answer: key exchanging is only important in a future where not only do nation states have quantum computers that can break classical algorithms, but can also break quantum proof encryption algorithms a few times with a lot of effort, but not many times over and over (if they could break them easily then they'll just break every key rotation). i.e. a speculative future that may never exist and quite frankly even if it did, won't for decades given the current state of quantum computers.

A more informative take from somewhere other than an Apple press release:

The changes Apple is announcing put iMessage at parity with Signal, both in terms of PQC hardening and the key refresh through ratcheting. Apple, however, is taking things one step further by applying ratcheting not only to the quantum-vulnerable Elliptic-curve Diffie-Hellman algorithm but also to the PQ3 being added now. This improvement comes with some limitations, though. Because of the significant overhead in refreshing keys for PQC algorithms, the key updates can’t be made with the exchange of each message as they are with the Elliptic-curve Diffie-Hellman.

As University of Waterloo professor David Jao explained in an email:

The X3DH ratchet used in Signal depends heavily on ECDH and elliptic curve arithmetic. You need to be able to add public keys together, and add private keys together, in meaningful ways. Most post-quantum replacements for ECDH do not support the same arithmetic. This makes constructing post-quantum ratchets difficult and is part of the reason why no one has implemented it before. You can do it, but as mentioned in the Apple post, the overhead goes up from 32 bytes per ratchet to 2kB per ratchet. In the messaging context, the latter overhead is quite significant, being many times larger than the messages themselves. Apple mitigates this overhead by stepping up the ratchet every ~50 messages instead of every message. Of course, this design means that the security guarantees provided by the post-quantum ratchet are lessened: an adversary that compromises keys and transmissions could potentially gain access to up to your 50 most recent messages.

Since Apple is doing BOTH the normal X3DH/ECDH ratchet and the post-quantum PQ3 ratchet, the 50-message look back only applies to the PQ part. Each individual message is still protected by the ECDH ratchet with the 32-byte overhead. So you still have to break ECDH. Assuming quantum computers eventually get built, breaking ECDH will be easy, but that is not the case presently.

For now, ratcheting in Signal will be limited only to the X3DH part of the messaging app. In a statement, Signal President Meredith Whittaker wrote:

Before we deployed PQXDH in May, 2023, we carefully considered implementing a periodic amortized quantum rekeying process, similar to the one that Apple decided on for their PQ3 specification. We decided against it, not because it isn't a good first step, but because we wanted to find an approach that would enable quantum rekeying to occur as frequently as non-quantum re-keying does—instead of relegating it to ratcheting less often, as is the case with Apple's PQ3 approach. Such an approach is currently the realm of novel research, and something that will require solving extant problems in order to implement at Signal’s scale. We are currently working with the cryptographic research community to explore methods that could allow us to implement more frequent quantum rekeying.

Another difference between the two apps that privacy-minded people should remember is that, by default, iMessage backs up messages within iCloud with no E2EE. Advanced encryption will do nothing to protect users in this scenario. People should either turn off iCloud backups or turn on E2EE in iCloud. (Signal doesn't back up messages at all.)