Introduction Modulus fault attacks Experiments and refinements Conclusion

pages

English

Documents

Écrit par
Eric Brier1

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

English

Poids de l'ouvrage

1 Mo

Introduction Modulus fault attacks Experiments and refinements Conclusion Modulus Fault Attacks Against RSA–CRT Signatures Eric Brier1 David Naccache2 Phong Q. Nguyen2,3 Mehdi Tibouchi2 1Ingenico 2Ecole normale superieure 3INRIA CHES 2011, Nara, 2011–09–30

signature scheme

most widely used

attacks against

used improvement

introduction modulus

fault attacks

Voir

Publié par

pefav

Nombre de lectures

Langue

English

Poids de l'ouvrage

1 Mo

Ingenico Digital signature

Introduction

Modulus fault attacks

Experiments and reﬁnements

Modulus Fault Attacks ainst RSA–CRT Signatures

E´ricBrier1David Naccache2 Phong Q. Nguyen2,3Mehdi Tibouchi2

1Ingenico

2´esal´euplecormno E rieure

CHES

3INRIA

2011, Nara, 2011–09–30

Conclusion

Introduction

Modulus fault attacks

Modulus fault attacks Basic idea Using orthogonal lattices

Experiments and reﬁnements

Outline

Experiments and reﬁnements Simulation and experiments Solving theN′problem

Conclusion

Introduction

•

• •

•

Modulus fault attacks

Experiments and reﬁnements

Signing with RSA–CRT

RSA signatures:

σ=µmdmodN

Conclusion

For suitable padding functionsµ(e.g. FDH, is a this PSS...) provably secure signature scheme. Remains the most widely used signature scheme today. Implemented in many embedded applications (esp. smart cards). However, modular exponentiation is rather slow. Very commonly used improvement: using the Chinese Remainder Theorem. 1.σp=µmdmodp−1modp 2.σq=µmdmodq−1modq 3.σ=CRTσp, σqmodN Roughly 4-fold speed-up.

Introduction

•

• •

•

Modulus fault attacks

Experiments and reﬁnements

Signing with RSA–CRT

RSA signatures:

σ=µmdmodN

Conclusion

For suitable padding functionsµ PSS...)(e.g. FDH, is a this provably secure signature scheme. Remains the most widely used signature scheme today. Implemented in many embedded applications (esp. smart cards). However, modular exponentiation is rather slow. Very commonly used improvement: using the Chinese Remainder Theorem. 1.σp=µmdmodp−1modp 2.σq=µmdmodq−1modq 3.σ=CRTσp, σqmodN Roughly 4-fold speed-up.

Introduction

•

• •

•

Modulus fault attacks

Experiments and reﬁnements

Signing with RSA–CRT

RSA signatures:

σ=µmdmodN

Conclusion

For suitable padding functionsµ PSS...) this(e.g. FDH, is a provably secure signature scheme. Remains the most widely used signature scheme today. Implemented in many embedded applications (esp. smart cards). However, modular exponentiation is rather slow. Very commonly used improvement: using the Chinese Remainder Theorem. 1.σp=µmdmodp−1modp 2.σq=µmdmodq−1modq 3.σ=CRTσp, σqmodN Roughly 4-fold speed-up.

Introduction

•

• •

•

Modulus fault attacks

Experiments and reﬁnements

Signing with RSA–CRT

RSA signatures:

σ=µmdmodN

Conclusion

For suitable padding functionsµ this is a(e.g. FDH, PSS...) provably secure signature scheme. Remains the most widely used signature scheme today. Implemented in many embedded applications (esp. smart cards). However, modular exponentiation is rather slow. Very commonly used improvement: using the Chinese Remainder Theorem. 1.σp=µmdmodp−1modp 2.σq=µmdmodq−1modq 3.σ=CRTσp, σqmodN Roughly 4-fold speed-up.

Introduction

•

• •

•

Modulus fault attacks

Experiments and reﬁnements

Signing with RSA–CRT

RSA signatures:

σ=µmdmodN

Conclusion

For suitable padding functionsµ(e.g. FDH, is a PSS...) this provably secure signature scheme. Remains the most widely used signature scheme today. Implemented in many embedded applications (esp. smart cards). However, modular exponentiation is rather slow. Very commonly used improvement: using the Chinese Remainder Theorem. 1.σp=µmdmodp−1modp 2.σq=µmdmodq−1modq 3.σ=CRTσp, σqmodN Roughly 4-fold speed-up.

Introduction

• •

•

Modulus fault attacks

Experiments and reﬁnements

The Boneh-DeMillo-Lipton fault attack (1997)

Conclusion

The problem with CRT:fault attacks. A fault in signature generation makes it possible to recover the secret key! 1.σp=µmdmodp−1modp 2.σ′q≠µmdmodq−1modq←fault 3.σ′=CRTσp,σq′modN←faulty signature Thenσ′eisµmmodpbut not modq, so the attacker can then factorN: p=gcdσ′e−µm,N

This attack applies to any deterministic padding, including “provably secure” ones like FDH.