### Correlated Extra-Reductions Defeat Blinded Regular Exponentiation - Extended Version

Margaux Dugardin, Sylvain Guilley, Jean-Luc Danger, Zakaria Najm, and Olivier Rioul

##### Abstract

Walter & Thomson (CT-RSA '01) and Schindler (PKC '02) have shown that extra-reductions allow to break RSA-CRT even with message blinding. Indeed, the extra-reduction probability depends on the type of operation: square, multiply, or multiply with a constant. Regular exponentiation schemes can be regarded as protections, as the operation sequence does not depend on the secret. In this article, we show that there exists a strong negative correlation between extra-reductions of two consecutive operations, provided that the first one feeds the second one. This allows to mount successful attacks even against blinded asymmetrical computations with a regular exponentiation algorithm (such as Square-and-Multiply Always or Montgomery Ladder). We put forward various attack strategies depending on the context (e.g., known modulus or not, known extra-reduction detection probability, etc.), and implement them on two devices (single core ARM Cortex-M4 and dual core ARM Cortex M0-M4)

Note: Some precisions, especially that the modulus need not be prime (as in RSA without CRT), and that a global timing attack would not be successful, as we should be able to attribute an extra-reduction to one targeted multiplication/square.

Available format(s)
Publication info
A minor revision of an IACR publication in CHES 2016
Keywords
side-channel analysisMontgomery modular multiplicationextra-reduction leakagemessage blindingregular exponentiation
Contact author(s)
margaux dugardin59 @ gmail com
History
2017-01-10: last of 2 revisions
See all versions
Short URL
https://ia.cr/2016/597

CC BY

BibTeX

@misc{cryptoeprint:2016/597,
author = {Margaux Dugardin and Sylvain Guilley and Jean-Luc Danger and Zakaria Najm and Olivier Rioul},
title = {Correlated Extra-Reductions Defeat Blinded Regular Exponentiation - Extended Version},
howpublished = {Cryptology ePrint Archive, Paper 2016/597},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/597}},
url = {https://eprint.iacr.org/2016/597}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.