MARSHAL: Messaging with Asynchronous Ratchets and Signatures for faster HeALing

Secure messaging applications are deployed on devices that can be compromised, lost, stolen, or corrupted in many ways. Thus, recovering from attacks to get back to a clean state is essential and known as healing. Signal is a widely-known, privacy-friendly messaging application, that uses key-ratcheting mechanism updates keys at each stage to provide end-to-end channel security, forward secrecy, and post-compromise security. We strengthen this last property, by providing a faster healing. Signal needs up to two full chains of messages before recovering, our protocol enables recovery after the equivalent of a chain of only one message. We also provide an extra protection against session-hijacking attacks. We do so, while building on the pre-existing Signal backbone, without weakening its other security assumptions, and still being compatible with Signal's out-of-order message handling feature. Our implementation results show that, while slower than Signal (as expected), MARSHAL's spectacular gain in healing speed comes at a surprisingly low cost, with individual stages (including key-derivation, encryption, and decryption) taking less than 6 ms.