Douglas Stebila

Algorithm substitution attacks: state reset detection and asymmetric modifications

Comparison of properties of various ASA

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.

Keywords: algorithm substitution attack, symmetric encryption, state reset, kleptography

Reference

Philip Hodges, Douglas Stebila. Algorithm substitution attacks: state reset detection and asymmetric modifications. IACR Transactions on Symmetric Cryptography, 2021(2):389–422. June 2021. © The authors.

Download

BibTeX

@article{TOSC:HodSte21,
 	Author = {Philip Hodges and Douglas Stebila},
 	Doi = {10.46586/tosc.v2021.i2.389-422},
 	Journal = {IACR Transactions on Symmetric Cryptography},
 	Month = {June},
 	Number = {2},
 	Pages = {389--422},
 	Title = {Algorithm substitution attacks: state reset detection and asymmetric modifications},
 	Volume = {2021},
 	Year = {2021}
 }

Funding

• Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2016-05146
• NSERC Discovery Accelerator Supplement grant RGPIN-2016-05146