Paper 2020/1452

ASAP: Algorithm Substitution Attacks on Cryptographic Protocols

Sebastian Berndt, Jan Wichelmann, Claudius Pott, Tim-Henrik Traving, and Thomas Eisenbarth


The security of digital communication relies on few cryptographic protocols that are used to protect internet traffic, from web sessions to instant messaging. These protocols and the cryptographic primitives they rely on have been extensively studied and are considered secure. Yet, sophisticated attackers are often able to bypass rather than break security mechanisms. Kleptography or algorithm substitution attacks (ASA) describe techniques to place backdoors right into cryptographic primitives. While highly relevant as a building block, we show that the real danger of ASAs is their use in cryptographic protocols. In fact, we show that highly desirable security properties of these protocols - forward secrecy and post-compromise security - imply the applicability of ASAs. We then analyze the application of ASAs in three widely used protocols: TLS, WireGuard, and Signal. We show that these protocols can be easily subverted by carefully placing ASAs. Our analysis shows that careful design of ASAs makes detection unlikely while leaking long-term secrets within a few messages in the case of TLS and WireGuard, allowing impersonation attacks. In contrast,Signal's double-ratchet protocol shows higher immunity to ASAs, as the leakage requires much more messages.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ASIACCS 2022
algorithm substitution attackskleptographysubverted algorithmbackdoorsforward security
Contact author(s)
sebastian berndt @ gmail com
2022-02-15: last of 2 revisions
2020-11-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sebastian Berndt and Jan Wichelmann and Claudius Pott and Tim-Henrik Traving and Thomas Eisenbarth},
      title = {{ASAP}: Algorithm Substitution Attacks on Cryptographic Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1452},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.