Paper 2012/038

Cryptanalysis of the CHES 2009/2010 Random Delay Countermeasure

François Durvaux, Mathieu Renauld, François-Xavier Standaert, Loic van Oldeneel tot Oldenzeel, and Nicolas Veyrat-Charvillon

Abstract

Inserting random delays in cryptographic implementations is often used as a countermeasure against side-channel attacks. Most previous works on the topic focus on improving the statistical distribution of these delays. For example, efficient random delay generation algorithms have been proposed at CHES 2009/2010. These solutions increase security against attacks that solve the lack of synchronization between different leakage traces by integrating them. In this paper, we demonstrate that integration may not be the best tool to evaluate random delay insertions. For this purpose, we first describe different attacks exploiting pattern recognition techniques and Hidden Markov Models. Using these tools, we succeed in cryptanalyzing a (straightforward) implementation of the CHES 2009/2010 proposal in an Atmel microcontroller, with the same data complexity as an unprotected implementation of the AES Rijndael. In other words, we completely cancel the countermeasure in this case. Next, we show that our cryptanalysis tools are remarkably robust to attack improved variants of the countermeasure, e.g. with additional noise or irregular dummy operations. We also exhibit that the attacks remain applicable in a non-profiled adversarial scenario. Overall, these results suggest that the use of random delays may not be effective for protecting small embedded devices against side-channel leakage. They also confirm the need of worst-case analysis in physical security evaluations.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
side-channel analysis
Contact author(s)
fstandae @ uclouvain be
History
2012-01-29: received
Short URL
https://ia.cr/2012/038
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/038,
      author = {François Durvaux and Mathieu Renauld and François-Xavier Standaert and Loic van Oldeneel tot Oldenzeel and Nicolas Veyrat-Charvillon},
      title = {Cryptanalysis of the CHES 2009/2010 Random Delay Countermeasure},
      howpublished = {Cryptology ePrint Archive, Paper 2012/038},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/038}},
      url = {https://eprint.iacr.org/2012/038}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.