Algorithm Substitution Attacks: State Reset Detection and Asymmetric Modifications

Authors

  • Philip Hodges University of Waterloo, Waterloo, Canada
  • Douglas Stebila University of Waterloo, Waterloo, Canada

DOI:

https://doi.org/10.46586/tosc.v2021.i2.389-422

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.

Downloads

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

Issue

Section

Articles