Algorithm Substitution Attacks: State Reset Detection and Asymmetric Modifications

  • Philip Hodges University of Waterloo, Waterloo, Canada
  • Douglas Stebila University of Waterloo, Waterloo, Canada
Keywords: Algorithm Substitution Attack, Symmetric Encryption, State Reset, Kleptography

Abstract

In this paper, we study algorithm substitution attacks (ASAs), where an algorithm in a cryptographic scheme is substituted for a subverted version. First, we formalize and study the use of state resets to detect ASAs, and show that many published stateful ASAs are detectable with simple practical methods relying on state resets. Second, we introduce two asymmetric ASAs on symmetric encryption, which are undetectable or unexploitable even by an adversary who knows the embedded subversion key. We also generalize this result, allowing for any symmetric ASA (on any cryptographic scheme) satisfying certain properties to be transformed into an asymmetric ASA. Our work demonstrates the broad application of the techniques first introduced by Bellare, Paterson, and Rogaway (Crypto 2014) and Bellare, Jaeger, and Kane (CCS 2015) and reinforces the need for precise definitions surrounding detectability of stateful ASAs.

Published
2021-06-11
How to Cite
Hodges, P., & Stebila, D. (2021). Algorithm Substitution Attacks: State Reset Detection and Asymmetric Modifications. IACR Transactions on Symmetric Cryptology, 2021(2), 389-422. https://doi.org/10.46586/tosc.v2021.i2.389-422
Section
Articles