Introduction Modulus fault attacks Experiments and refinements Conclusion

Eric Brier1

Description

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

Sujets

• Ingenico
• Digital signature

Informations

• Publié par: pefav
• Nombre de lectures: 36
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Introduction

Modulus fault attacks

Experiments and refinements

Modulus Fault Attacks ainst RSA–CRT Signatures

Ag

E ´ ricBrier 1 David Naccache 2 Phong Q. Nguyen 2,3 Mehdi Tibouchi 2

1 Ingenico

2 ´ esal´euplecormno E rieure

CHES

3 INRIA

2011, Nara, 2011–09–30

Conclusion

Introduction

Introduction

Modulus fault attacks

Modulus fault attacks Basic idea Using orthogonal lattices

Experiments and refinements

Outline

Experiments and refinements Simulation and experiments Solving theN ′ problem

Conclusion

Introduction

•

•

• •

•

Modulus fault attacks

Experiments and refinements

Signing with RSA–CRT

RSA signatures:

σ=µm d modN

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−1 modp 2.σ q =µm dmodq−1 modq 3.σ=CRTσ p , σ q modN Roughly 4-fold speed-up.

Introduction

•

•

• •

•

Modulus fault attacks

Experiments and refinements

Signing with RSA–CRT

RSA signatures:

σ=µm d modN

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−1 modp 2.σ q =µm dmodq−1 modq 3.σ=CRTσ p , σ q modN Roughly 4-fold speed-up.

Introduction

•

•

• •

•

Modulus fault attacks

Experiments and refinements

Signing with RSA–CRT

RSA signatures:

σ=µm d modN

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−1 modp 2.σ q =µm dmodq−1 modq 3.σ=CRTσ p , σ q modN Roughly 4-fold speed-up.

Introduction

•

•

• •

•

Modulus fault attacks

Experiments and refinements

Signing with RSA–CRT

RSA signatures:

σ=µm d modN

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−1 modp 2.σ q =µm dmodq−1 modq 3.σ=CRTσ p , σ q modN Roughly 4-fold speed-up.

Introduction

•

•

• •

•

Modulus fault attacks

Experiments and refinements

Signing with RSA–CRT

RSA signatures:

σ=µm d modN

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−1 modp 2.σ q =µm dmodq−1 modq 3.σ=CRTσ p , σ q modN Roughly 4-fold speed-up.

Introduction

• •

•

•

Modulus fault attacks

Experiments and refinements

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−1 modp 2.σ ′ q ≠µm dmodq−1 modq←fault 3.σ ′ =CRTσ p ,σ q ′ modN←faulty signature Thenσ ′e isµ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.

Introduction

• •

•

•

Modulus fault attacks

Experiments and refinements

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−1 modp 2.σ ′ q ≠µm dmodq−1 modq←fault 3.σ ′ =CRTσ p ,σ q ′ modN←faulty signature Thenσ ′e isµ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.