Although ping-pong keys are vulnerable to future quantum attacks, they are widely believed to be secure against current attacks on classical computers. The Signal Protocol developers didn’t want to remove them or the battle-tested code that produces them. That led them to the decision to add quantum resistance by adding a third ratchet. This uses a quantum-safe KEM to produce new secrets much like the Diffie-Hellman ratchet did before, ensuring post-commitment quantum safety.
The technical challenges were anything but easy. The elliptic curve keys generated in the X25519 implementation are approximately 32 bytes long, small enough to add to each message without creating a load on already restricted bandwidth or computing resources. An ML-KEM 768 key, on the other hand, is 1000 bytes. Additionally, Signal’s design requires sending an encryption key and ciphertext, making the total size 2272 bytes.
And then there were three
To handle the 71x increase, Signal developers considered a variety of options. One was to send the 2272-byte KEM key less frequently (say every 50 messages or once a week) rather than every message. That idea was rejected because it doesn’t work well in asynchronous or adversarial messaging environments. Signal Protocol developers Graeme Connell and Rolfe Schmidt explained:
Consider the case of “send a key if you haven’t sent one in a week”. If Bob has been offline for 2 weeks, what does Alice do when she wants to send a message? What if we can lose messages and we lose one in fifty that contains a new key? Or, what if there is an attacker in the middle who wants to prevent us from generating new secrets and can search for messages that are [many] bytes larger than the others and delete them, allowing only the passage of messages without a key?
Another option Signal engineers considered was to split the 2,272-byte key into smaller chunks, say 71 of them of 32 bytes each. Splitting the KEM key into smaller chunks and putting one in each message seems like a viable approach at first, but again, the asynchronous environment of messaging made it infeasible. What happens, for example, when data loss causes one of the fragments to be deleted? The protocol could address this scenario by simply repeating sending fragments after sending all 71 previously. But then an adversary monitoring the traffic could simply cause packet 3 to be discarded each time, preventing Alice and Bob from completing the key exchange.
#Signals #postquantum #makeover #surprising #engineering #achievement
