Paper 2023/880

On Active Attack Detection in Messaging with Immediate Decryption

Khashayar Barooti, École Polytechnique Fédérale de Lausanne
Daniel Collins, École Polytechnique Fédérale de Lausanne
Simone Colombo, École Polytechnique Fédérale de Lausanne
Loı̈s Huguenin-Dumittan, École Polytechnique Fédérale de Lausanne
Serge Vaudenay, École Polytechnique Fédérale de Lausanne

The widely used Signal protocol provides protection against state exposure attacks through forward security (protecting past messages) and post-compromise security (for restoring security). It supports immediate decryption, allowing messages to be re-ordered or dropped at the protocol level without affecting correctness. In this work, we consider strong active attack detection for secure messaging with immediate decryption, where parties are able to immediately detect active attacks under certain conditions. We first consider in-band active attack detection, where participants who have been actively compromised but are still able to send a single message to their partner can detect the compromise. We propose two complementary notions to capture security, and present a compiler that provides security with respect to both notions. Our notions generalise existing work (RECOVER security) which only supported in-order messaging. We also study the related out-of-band attack detection problem by considering communication over out-of-band, authenticated channels and propose analogous security notions. We prove that one of our two notions in each setting imposes a linear communication overhead in the number of sent messages and security parameter using an information-theoretic argument. This implies that each message must information-theoretically contain all previous messages and that our construction, that essentially attaches the entire message history to every new message, is asymptotically optimal. We then explore ways to bypass this lower bound and highlight the feasibility of practical active attack detection compatible with immediate decryption.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2023
active attack detectionRECOVER securityratchetingmessagingimmediate decryptionout-of-order
Contact author(s)
khashayar barooti @ epfl ch
daniel collins @ epfl ch
simone colombo @ epfl ch
lois huguenin-dumittan @ epfl ch
serge vaudenay @ epfl ch
2023-06-12: approved
2023-06-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Khashayar Barooti and Daniel Collins and Simone Colombo and Loı̈s Huguenin-Dumittan and Serge Vaudenay},
      title = {On Active Attack Detection in Messaging with Immediate Decryption},
      howpublished = {Cryptology ePrint Archive, Paper 2023/880},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.