//img.uscri.be/pth/405880863cf8100364d635208a10994088a28ebd
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Introduction Modulus fault attacks Experiments and refinements Conclusion

De
93 pages
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 plus Voir moins
Introduction
Modulus fault attacks
Experiments and refinements
Modulus Fault Attacks ainst RSA–CRT Signatures
Ag
E´ricBrier1David Naccache2 Phong Q. Nguyen2,3Mehdi Tibouchi2
1Ingenico
2´esal´euplecormno E rieure
CHES
3INRIA
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 theNproblem
Conclusion
Introduction
Modulus fault attacks
Experiments and refinements
Signing with RSA–CRT
RSA signatures:
σ=µmdmodN
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=µmdmodp1modp 2.σq=µmdmodq1modq 3.σ=CRTσp, σqmodN Roughly 4-fold speed-up.
Introduction
Modulus fault attacks
Experiments and refinements
Signing with RSA–CRT
RSA signatures:
σ=µmdmodN
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=µmdmodp1modp 2.σq=µmdmodq1modq 3.σ=CRTσp, σqmodN Roughly 4-fold speed-up.
Introduction
Modulus fault attacks
Experiments and refinements
Signing with RSA–CRT
RSA signatures:
σ=µmdmodN
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=µmdmodp1modp 2.σq=µmdmodq1modq 3.σ=CRTσp, σqmodN Roughly 4-fold speed-up.
Introduction
Modulus fault attacks
Experiments and refinements
Signing with RSA–CRT
RSA signatures:
σ=µmdmodN
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=µmdmodp1modp 2.σq=µmdmodq1modq 3.σ=CRTσp, σqmodN Roughly 4-fold speed-up.
Introduction
Modulus fault attacks
Experiments and refinements
Signing with RSA–CRT
RSA signatures:
σ=µmdmodN
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=µmdmodp1modp 2.σq=µmdmodq1modq 3.σ=CRTσp, σqmodN 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=µmdmodp1modp 2.σqµmdmodq1modqfault 3.σ=CRTσp,σqmodNfaulty signature Thenσeisµmmodpbut 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=µmdmodp1modp 2.σqµmdmodq1modqfault 3.σ=CRTσp,σqmodNfaulty signature Thenσeisµmmodpbut 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.