International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Algorithm Substitution Attacks: State Reset Detection and Asymmetric Modifications

Authors:
Philip Hodges , University of Waterloo, Waterloo, Canada
Douglas Stebila , University of Waterloo, Waterloo, Canada
Download:
DOI: 10.46586/tosc.v2021.i2.389-422
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8915
Search ePrint
Search Google
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.
BibTeX
@article{tosc-2021-31090,
  title={Algorithm Substitution Attacks: State Reset Detection and Asymmetric Modifications},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universit├Ąt Bochum},
  volume={2021, Issue 2},
  pages={389-422},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8915},
  doi={10.46586/tosc.v2021.i2.389-422},
  author={Philip Hodges and Douglas Stebila},
  year=2021
}