IACR Transactions on Cryptographic Hardware and Embedded Systems · 2018 · 14 citations · 14 references
ComputingComputer EngineeringComputer ScienceComputer SecurityCryptographyFault-tolerant ComputingAuthenticated EncryptionCryptographic ComplexityElliptic Curve CryptographyEmbedded System SecurityDigital Signature SchemesFault Attack MitigationFault-based AttacksMicrocontroller Fault AttacksMontgomery CurvesSchnorr SignaturesSecret RecoverySignature Schemes
In this paper, we optimize Bleichenbacher’s statistical attack technique against (EC)DSA and other Schnorr-like signature schemes with biased or partially exposed nonces. Previous approaches to Bleichenbacher’s attack suffered from very large memory consumption during the so-called “range reduction” phase. Using a carefully analyzed and highly parallelizable approach to this range reduction based on the Schroeppel–Shamir algorithm for knapsacks, we manage to overcome the memory barrier of previous work while maintaining a practical level of efficiency in terms of time complexity.As a separate contribution, we present new fault attacks against the qDSA signature scheme of Renes and Smith (ASIACRYPT 2017) when instantiated over the Curve25519 Montgomery curve, and we validate some of them on the AVR microcontroller implementation of qDSA using actual fault experiments on the ChipWhisperer-Lite evaluation board. These fault attacks enable an adversary to generate signatures with 2 or 3 bits of the nonces known.Combining our two contributions, we are able to achieve a full secret key recovery on qDSA by applying our version of Bleichenbacher’s attack to these faulty signatures. Using a hybrid parallelization model relying on both shared and distributed memory, we achieve a very efficient implementation of our highly scalable range reduction algorithm. This allows us to complete Bleichenbacher’s attack in the 252-bit prime order subgroup of Curve25519 within a reasonable time frame and using relatively modest computational resources both for 3-bit nonce exposure and for the much harder case of 2-bit nonce exposure. Both of these computations, and particularly the latter, set new records in the implementation of Bleichenbacher’s attack.
14
New directions in cryptography
Whitfield Diffie, Martin E. Hellman · IEEE Transactions on Information Theory · 1976 · 14.4K citations
The Design and Implementation of FFTW3
Matteo Frigo, Steven G. Johnson · Proceedings of the IEEE · 2005 · 5.2K citations
Efficient signature generation by smart cards
C. P. Schnorr · Journal of Cryptology · 1991 · 2.8K citations · Full text