Talk by Akira Takahashi on New Bleichenbacher Records: Fault Attacks on qDSA Signatures

2018.09.14 | Malene Bisgaard Blaabjerg Andersen

Date Wed 19 Sep
Time 14:30 15:30
Location Nygaard Building, room 295

Title: New Bleichenbacher Records: Fault Attacks on qDSA Signatures

Joint work with: Mehdi Tibouchi (NTT) and Masayuki Abe (NTT)

Abstract: Signature generation in (EC)DSA and other Schnorr-like schemes uses ephemeral secret values known as nonces. It is well known that nonces should be sampled uniformly in a certain interval and should never be revealed; if the actual distribution of nonces deviates from the uniform distribution or nonces are partially exposed, there exist attacks on these schemes that can, in the worst case, yield to the recovery of the entire secret  signing key, and hence fully compromise the security of the signature scheme.

In this talk, we present our two recent contributions to the study of attacks against nonces in Schnorr-like schemes: 1) highly optimized version of Bleichenbacher's attack technique against biased nonces, and  2) novel fault attacks on a recent, high-profile Schnorr-like scheme of Renes and Smith (ASIACRYPT 2017), called quotient Digital Signature (qDSA), when instantiated over the Curve25519 Montgomery curve.

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. The targeted parameters (in terms of the number of leaked bits and signature security level) were previously considered out of reach, and we thus set new records in the implementation of Bleichenbacher’s attack.

Akira Takahashi will join the Cryptography & Security Group at CS as a PhD Student from January, 2019.

Public/media, Featured, CS frontpage