Top

Published in:

2016 | OriginalPaper | Chapter

Correlated Extra-Reductions Defeat Blinded Regular Exponentiation

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

Published in: Cryptographic Hardware and Embedded Systems – CHES 2016

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Walter and 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 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-M4.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

next chapter Horizontal Side-Channel Attacks and Countermeasures on the ISW Masking Scheme

Available only for authorised users

A complete version containing auxiliary information is available in [8].

\(\rho (X_{M_i},X_{S_{i-1}})=\frac{\mathbb {C}ov(X_{M_i}, X_{S_{i-1}}) }{\sigma _{X_{M_i}}\sigma _{X_{S_{i-1}}}} =\frac{\mathbb {P}(X_{M_i}=1,X_{S_{i-1}}=1)-(\mathbb {P}(X_{M_i}=1)\times \mathbb {P}(X_{S_{i-1}}=1))}{\sqrt{\mathbb {P}(X_{M_i}=1)(1-\mathbb {P}(X_{M_i}=1))}\sqrt{\mathbb {P}(X_{S_{i-1}}=1)(1-\mathbb {P}(X_{S_{i-1}}=1))}}\).

Proof of this theorem is given in [8].

\(\hat{\rho }(X_{M_i},X_{S_{i-1}})=\frac{\hat{\mathbb {C}ov}(X_{M_i}, X_{S_{i-1}}) }{\hat{\sigma }_{X_{M_i}}\hat{\sigma }_{X_{S_{i-1}}}} =\frac{\hat{\mathbb {P}}(X_{M_i}=1,X_{S_{i-1}}=1)-(\hat{\mathbb {P}}(X_{M_i}=1)\times \hat{\mathbb {P}}(X_{S_{i-1}}=1))}{\sqrt{\hat{\mathbb {P}}(X_{M_i}=1)(1-\hat{\mathbb {P}}(X_{M_i}=1))}\sqrt{\hat{\mathbb {P}}(X_{S_{i-1}}=1)(1-\hat{\mathbb {P}}(X_{S_{i-1}}=1))}}\).

Notice that in some cases, e.g. if the key bits happen not to be balanced, \(\hat{\mathbb {E}}_i\hat{\mathbb {P}}(X_{M_i}, X_{S_{i-1}})\) can be estimated in a less biased way using \(\max _i\{\hat{\mathbb {P}}(X_{M_i},X_{S_{i-1}})\} - \min _i\{\hat{\mathbb {P}}(X_{M_i},X_{S_{i-1}})\}\).

Latest stable version at the time of submission.

Latest version at the time of submission.

Acıiçmez, O., Schindler, W.: A vulnerability in RSA implementations due to instruction cache analysis and its demonstration on openSSL. In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 256–273. Springer, Heidelberg (2008)CrossRef

Aciiçmez, O., Schindler, W., Koç, Ç.K.: Improving Brumley and Boneh timing attack on unprotected SSL implementations. In: Atluri, V., Meadows, C., Juels, A. (eds.) CCS 2005, pp. 139–146. ACM, New York (2005)

Bauer, A., Jaulmes, É., Prouff, E., Reinhard, J.-R., Wild, J.: Horizontal collision correlation attack on elliptic curves - extended version. Cryptogr. Commun. 7(1), 91–119 (2015)MathSciNetCrossRefMATH

Belgarric, P., Bhasin, S., Bruneau, N., Danger, J.-L., Debande, N., Guilley, S., Heuser, A., Najm, Z., Rioul, O.: Time-frequency analysis for second-order attacks. In: Francillon, A., Rohatgi, P. (eds.) CARDIS 2013. LNCS, vol. 8419, pp. 108–122. Springer, Heidelberg (2014)

Bernstein, D.J., Lange, T.: Explicit formulas database. http://www.hyperelliptic.org/EFD/

Clavier, C., Feix, B., Gagnerot, G., Roussellet, M., Verneuil, V.: Horizontal correlation analysis on exponentiation. In: Soriano, M., Qing, S., López, J. (eds.) ICICS 2010. LNCS, vol. 6476, pp. 46–61. Springer, Heidelberg (2010)CrossRef

Courrège, J.-C., Feix, B., Roussellet, M.: Simple power analysis on exponentiation revisited. In: Gollmann, D., Lanet, J.-L., Iguchi-Cartigny, J. (eds.) CARDIS 2010. LNCS, vol. 6035, pp. 65–79. Springer, Heidelberg (2010)CrossRef

Dugardin, M., Guilley, S., Danger, J.-L., Najm, Z., Rioul, O.: Correlated extra-reductions defeat blinded regular exponentiation - extended version. Cryptology ePrint Archive, Report 2016/597 (2016). http://eprint.iacr.org/2016/597

Fouque, P.-A., Réal, D., Valette, F., Drissi, M.: The carry leakage on the randomized exponent countermeasure. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 198–213. Springer, Heidelberg (2008)CrossRef

10.

Hanley, N., Kim, H.S., Tunstall, M.: Exploiting collisions in addition chain-based exponentiation algorithms using a single trace. In: Nyberg, K. (ed.) CT-RSA 2015. LNCS, vol. 9048, pp. 429–446. Springer, Heidelberg (2015)

11.

Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)

12.

Kocher, P.C.: On certificate revocation and validation. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 172–177. Springer, Heidelberg (1998)CrossRef

13.

Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996). http://www.cacr.math.uwaterloo.ca/hac/ CrossRefMATH

14.

Peter, L.: Montgomery: modular multiplication without trial division. Math. Comput. 44(170), 519–521 (1985)CrossRefMATH

15.

Sato, H., Schepers, D., Takagi, T.: Exact analysis of montgomery multiplication. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 290–304. Springer, Heidelberg (2004)CrossRef

16.

Schindler, W.: A timing attack against RSA with the Chinese Remainder Theorem. In: Paar, C., Koç, Ç.K. (eds.) CHES 2000. LNCS, vol. 1965, pp. 109–124. Springer, Heidelberg (2000)CrossRef

17.

Schindler, W.: A combined timing and power attack. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 263–279. Springer, Heidelberg (2002)CrossRef

18.

Schindler, W.: Exclusive exponent blinding may not suffice to prevent timing attacks on RSA. In: Güneysu, T., Handschuh, H. (eds.) CHES 2015. LNCS, vol. 9293, pp. 229–247. Springer, Heidelberg (2015)CrossRef

19.

Schindler, W., Koeune, F., Quisquater, J.-J.: Improving divide and conquer attacks against cryptosystems by better error detection/correction strategies. In: Honary, B. (ed.) Cryptography and Coding 2001. LNCS, vol. 2260, pp. 245–267. Springer, Heidelberg (2001)CrossRef

20.

Schindler, W., Walter, C.D.: More detail for a combined timing and power attack against implementations of RSA. In: Paterson, K.G. (ed.) Cryptography and Coding 2003. LNCS, vol. 2898, pp. 245–263. Springer, Heidelberg (2003)CrossRef

21.

Walter, C.D., Thompson, S.: Distinguishing exponent digits by observing modular subtractions. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 192–207. Springer, Heidelberg (2001)CrossRef

22.

Whitnall, C., Oswald, E.: A comprehensive evaluation of mutual information analysis using a fair evaluation framework. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 316–334. Springer, Heidelberg (2011)CrossRef

23.

Whitnall, C., Oswald, E., Standaert, F.-X.: The myth of generic DPA..and the magic of learning. In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 183–205. Springer, Heidelberg (2014)CrossRef

24.

Witteman, M.F., van Woudenberg, J.G.J., Menarini, F.: Defeating RSA multiply-always and message blinding countermeasures. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 77–88. Springer, Heidelberg (2011)CrossRef

Title: Correlated Extra-Reductions Defeat Blinded Regular Exponentiation
Authors: Margaux Dugardin
Sylvain Guilley
Jean-Luc Danger
Zakaria Najm
Olivier Rioul
Publisher: Springer Berlin Heidelberg
Book: Cryptographic Hardware and Embedded Systems – CHES 2016
Print ISBN: 978-3-662-53139-6

Electronic ISBN: 978-3-662-53140-2

Copyright Year: 2016
DOI: https://doi.org/10.1007/978-3-662-53140-2_1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner