Paper 2020/803

Lattice-based Fault Attacks on Deterministic Signature Schemes of ECDSA and EdDSA

Weiqiong Cao, Hongsong Shi, Hua Chen, Jiazhe Chen, Limin Fan, and Wenling Wu

Abstract

The deterministic ECDSA and EdDSA signature schemes have found plenty of applications since their publication and standardization. Their theoretical security can be guaranteed under certain well-designed models, while their practical risks from the flaw of random number generators can be mitigated since no randomness is required by the algorithms anymore. But the situation is not completely optimistic, since it has been gradually found that delicately designed fault attacks can threaten the practical security of the schemes. We present a lattice-based fault analysis method to the deterministic ECDSA and EdDSA algorithms. The underlying fault injection model is a special case of the random fault model in~\cite{MMF2019}. By noticing the algebraic structures of the deterministic algorithms, we show that, when providing with some valid faulty signatures and an associated correct signature of the same input message, some instances of lattice problems can be constructed to recover the signing key. This makes the allowed faulty bits close to the size of the signing key, and obviously bigger than that of the existing differential fault attacks. Moreover, the lattice-based approach supports much more alternative targets of fault injection when comparing with the existing approaches, which further improves its applicability. Experiments are performed to validate the effectiveness of the key recovery method. It is demonstrated that, for 256-bit deterministic ECDSA/EdDSA, the signing key can be recovered efficiently with significant probability even if the targets are affected by 250 (or 247) faulty bits. This is, however, impractical for the existing faulty pattern enumerating approaches.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. The Cryptographer’s Track at the RSA Conference 2022
Keywords
Side channel attackFault attackLattice-based attackDeterministic ECDSAEdDSA
Contact author(s)
caoweqion @ 163 com
History
2022-03-21: last of 5 revisions
2020-06-30: received
See all versions
Short URL
https://ia.cr/2020/803
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/803,
      author = {Weiqiong Cao and Hongsong Shi and Hua Chen and Jiazhe Chen and Limin Fan and Wenling Wu},
      title = {Lattice-based Fault Attacks on Deterministic Signature Schemes of ECDSA and EdDSA},
      howpublished = {Cryptology ePrint Archive, Paper 2020/803},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/803}},
      url = {https://eprint.iacr.org/2020/803}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.