Paper 2018/396

New Bleichenbacher Records: Fault Attacks on qDSA Signatures

Akira Takahashi, Mehdi Tibouchi, and Masayuki Abe


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.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in TCHES 2018
Digital SignatureFault AttackBleichenbacher's Nonce AttackSchroeppel-Shamir AlgorithmqDSACurve25519
Contact author(s)
mtibouchi @ gmail com
2018-07-31: revised
2018-05-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Akira Takahashi and Mehdi Tibouchi and Masayuki Abe},
      title = {New Bleichenbacher Records: Fault Attacks on qDSA Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2018/396},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.