Signal is a public-key communications protocol used by billions of people in the form of the Signal app, WhatsApp, and Facebook Messenger. As such, its security is a matter of importance, and it has previously been analyzed by various authors.

The chief security requirements of Signal include:

• Forward security – compromise of the secret state of a user does not compromise past messages
• A randomness requirement – use of bad randomness does not compromise security in the absence of other failures
• Post-compromise security – a user can recover from compromise of her secret state if the attacker takes no further action

The first requirement entails deleting old keys, and the third entails refreshing keys with new randomness. All of this must be achieved in a real-time, asynchronous messaging environment, where delayed and lost messages are possible and an attacker may even inject messages into the stream. And decryption must not depend on the decryption of previous messages. This long list of requirements makes analysis particularly difficult.

At Upgrade 2021 Dr. Sanjam Garg, Senior Scientist with NTT Research, presented joint work on Signal with his collaborators A. Bienstock (NYU), J. Fairoze (UC Berkeley), P. Mukherjee and S. Raghuraman (both Visa Research). They both built on and criticized the 2019 paper, “The double ratchet: Security notions, proofs, and modularization for the Signal protocol,” which Garg refers to as the ACD work, for the paper’s authors, J. Alwen, S. Coretti and Y. Dodis.

In their paper, Garg et al. give a new definition of the security of the Signal protocol that captures finer-grained detail than previous work. Their analysis showed that in five particular ways ACD was too permissive of behaviors that should properly be characterized as security lapses, and for four of these cases Garg sketched how attacks might take advantage of these behaviors. ACD proved that their definition of Signal’s security holds under the decisional Diffie-Hellman assumption, but Garg said stronger assumptions are needed to prove the security requirements called for by the Signal protocol.

The Signal protocol itself has previously unsuspected security weaknesses, however. Garg described an attack in which two breaches of secrecy several messages apart could reveal all of the intervening messages, thus breaking the Signal security requirements. He was able to provide a fix for this involving earlier re-randomization, resulting in no extra communication cost and a small extra computational cost.

In his concluding remarks, Dr. Garg discussed the value of working on real-world protocols and the usefulness of his group’s work for future developments based on Signal.