Paper 2020/803

Lattice-based Fault Attacks against Deterministic Signatures ECDSA and EdDSA

Weiqiong Cao and Hongsong Shi and Hua Chen and Wei Xi and Haoyuan Li and Limin Fan and Wenling Wu

Abstract

Deterministic ECC-based signatures including deterministic ECDSA and EdDSA are becoming popular to be applied to blockchain and Internet of Things. Their security has received a considerable attention, and there have existed some differential fault attacks against them. However, the attacks have some problems such as high computational complexity and strict requirement of fault injection. In this paper eight efficient lattice-based fault attacks(and one differential fault attack) against deterministic ECDSA and two ones against EdDSA are proposed. All the fault models of such attacks are the random storage faults of intermediate values during signature, by which some faulty and one correct signatures are obtained to construct the models of lattice attacks(or the equations with two unknown) and thereby recover the private key. Unlike the previous differential fault attacks based on storage faults, our attacks do not need to guess the number and location of the faulty bits, and are still effective while the previous attacks are computationally infeasible. Moreover, compared with the previous lattice-based fault attacks against the non-deterministic signatures with random nonces, our attacks have more fault models besides the faulty nonce k, and only need random fault injection. We demonstrate the effectiveness of the attacks by simulations, which shows our attacks pose real threats to deterministic signature. The upper bound of the number of the faulty bits is just slightly less than the key length. We also discuss the corresponding countermeasures against our attacks.