Correlated extra-reductions defeat blinded regular exponentiation

Margaux Dugardin; Sylvain Guilley; Jean Luc Danger; Zakaria Najm; Olivier Rioul

doi:10.1007/978-3-662-53140-2_1

Correlated extra-reductions defeat blinded regular exponentiation

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Walter and Thomson (CT-RSA ’01) and Schindler (PKC ’02)It should be emphasized that that have shown that extra-reductions allow to break RSA-CRT even with message blinding. Indeed, the extrareduction probability depends on the type of operation (square, multiply, or multiply with a constant). Regular exponentiation schemes can be regarded as protections since 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 feeds the second. 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 investigate various attack strategies depending on the context— known or unknown modulus, known or unknown extra-reduction detection probability, etc.—and implement them on two devices: a single core ARM Cortex-M4 and a dual core ARM Cortex M0-M 4.

Original language	English
Title of host publication	Cryptographic Hardware and Embedded Systems, CHES 2016 - 18th International Workshop, Proceedings
Editors	Benedikt Gierlichs, Axel Y. Poschmann
Publisher	Springer Verlag
Pages	3-22
Number of pages	20
ISBN (Print)	9783662531396
DOIs	https://doi.org/10.1007/978-3-662-53140-2_1
Publication status	Published - 1 Jan 2016
Externally published	Yes
Event	18th International Conference on Cryptographic Hardware and Embedded Systems, CHES 2016 - Santa Barbara, United States Duration: 17 Aug 2016 → 19 Aug 2016

Publication series

Name	Lecture Notes in Computer Science
Volume	9813 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Conference on Cryptographic Hardware and Embedded Systems, CHES 2016
Country/Territory	United States
City	Santa Barbara
Period	17/08/16 → 19/08/16

Keywords

Extra-reduction leakage
Message blinding
Montgomery modular multiplication
Regular exponentiation
Side-channel analysis

Access to Document

10.1007/978-3-662-53140-2_1

Cite this

Dugardin, M., Guilley, S., Danger, J. L., Najm, Z., & Rioul, O. (2016). Correlated extra-reductions defeat blinded regular exponentiation. In B. Gierlichs, & A. Y. Poschmann (Eds.), Cryptographic Hardware and Embedded Systems, CHES 2016 - 18th International Workshop, Proceedings (pp. 3-22). (Lecture Notes in Computer Science; Vol. 9813 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-662-53140-2_1

@inproceedings{d4c08e8d90384ec392a3b73415d2ee4f,

title = "Correlated extra-reductions defeat blinded regular exponentiation",

abstract = "Walter and Thomson (CT-RSA {\textquoteright}01) and Schindler (PKC {\textquoteright}02)It should be emphasized that that have shown that extra-reductions allow to break RSA-CRT even with message blinding. Indeed, the extrareduction probability depends on the type of operation (square, multiply, or multiply with a constant). Regular exponentiation schemes can be regarded as protections since 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 feeds the second. 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 investigate various attack strategies depending on the context— known or unknown modulus, known or unknown extra-reduction detection probability, etc.—and implement them on two devices: a single core ARM Cortex-M4 and a dual core ARM Cortex M0-M 4.",

keywords = "Extra-reduction leakage, Message blinding, Montgomery modular multiplication, Regular exponentiation, Side-channel analysis",

author = "Margaux Dugardin and Sylvain Guilley and Danger, \{Jean Luc\} and Zakaria Najm and Olivier Rioul",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2016.; 18th International Conference on Cryptographic Hardware and Embedded Systems, CHES 2016 ; Conference date: 17-08-2016 Through 19-08-2016",

year = "2016",

month = jan,

day = "1",

doi = "10.1007/978-3-662-53140-2\_1",

language = "English",

isbn = "9783662531396",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "3--22",

editor = "Benedikt Gierlichs and Poschmann, \{Axel Y.\}",

booktitle = "Cryptographic Hardware and Embedded Systems, CHES 2016 - 18th International Workshop, Proceedings",

}

Dugardin, M, Guilley, S, Danger, JL, Najm, Z & Rioul, O 2016, Correlated extra-reductions defeat blinded regular exponentiation. in B Gierlichs & AY Poschmann (eds), Cryptographic Hardware and Embedded Systems, CHES 2016 - 18th International Workshop, Proceedings. Lecture Notes in Computer Science, vol. 9813 LNCS, Springer Verlag, pp. 3-22, 18th International Conference on Cryptographic Hardware and Embedded Systems, CHES 2016, Santa Barbara, United States, 17/08/16. https://doi.org/10.1007/978-3-662-53140-2_1

Correlated extra-reductions defeat blinded regular exponentiation. / Dugardin, Margaux; Guilley, Sylvain; Danger, Jean Luc et al.
Cryptographic Hardware and Embedded Systems, CHES 2016 - 18th International Workshop, Proceedings. ed. / Benedikt Gierlichs; Axel Y. Poschmann. Springer Verlag, 2016. p. 3-22 (Lecture Notes in Computer Science; Vol. 9813 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Correlated extra-reductions defeat blinded regular exponentiation

AU - Dugardin, Margaux

AU - Guilley, Sylvain

AU - Danger, Jean Luc

AU - Najm, Zakaria

AU - Rioul, Olivier

N1 - Publisher Copyright: © International Association for Cryptologic Research 2016.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - Walter and Thomson (CT-RSA ’01) and Schindler (PKC ’02)It should be emphasized that that have shown that extra-reductions allow to break RSA-CRT even with message blinding. Indeed, the extrareduction probability depends on the type of operation (square, multiply, or multiply with a constant). Regular exponentiation schemes can be regarded as protections since 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 feeds the second. 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 investigate various attack strategies depending on the context— known or unknown modulus, known or unknown extra-reduction detection probability, etc.—and implement them on two devices: a single core ARM Cortex-M4 and a dual core ARM Cortex M0-M 4.

AB - Walter and Thomson (CT-RSA ’01) and Schindler (PKC ’02)It should be emphasized that that have shown that extra-reductions allow to break RSA-CRT even with message blinding. Indeed, the extrareduction probability depends on the type of operation (square, multiply, or multiply with a constant). Regular exponentiation schemes can be regarded as protections since 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 feeds the second. 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 investigate various attack strategies depending on the context— known or unknown modulus, known or unknown extra-reduction detection probability, etc.—and implement them on two devices: a single core ARM Cortex-M4 and a dual core ARM Cortex M0-M 4.

KW - Extra-reduction leakage

KW - Message blinding

KW - Montgomery modular multiplication

KW - Regular exponentiation

KW - Side-channel analysis

U2 - 10.1007/978-3-662-53140-2_1

DO - 10.1007/978-3-662-53140-2_1

M3 - Conference contribution

AN - SCOPUS:84981321254

SN - 9783662531396

T3 - Lecture Notes in Computer Science

SP - 3

EP - 22

BT - Cryptographic Hardware and Embedded Systems, CHES 2016 - 18th International Workshop, Proceedings

A2 - Gierlichs, Benedikt

A2 - Poschmann, Axel Y.

PB - Springer Verlag

T2 - 18th International Conference on Cryptographic Hardware and Embedded Systems, CHES 2016

Y2 - 17 August 2016 through 19 August 2016

ER -

Correlated extra-reductions defeat blinded regular exponentiation

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this