Security of Hedged Fiat-Shamir Signatures Under Fault Attacks

Diego F. Aranha, Claudio Orlandi, Akira Takahashi, Greg Zaverucha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Deterministic generation of per-signature randomness has been a widely accepted solution to mitigate the catastrophic risk of randomness failure in Fiat–Shamir type signature schemes. However, recent studies have practically demonstrated that such de-randomized schemes, including EdDSA, are vulnerable to differential fault attacks, which enable adversaries to recover the entire secret signing key, by artificially provoking randomness reuse or corrupting computation in other ways. In order to balance concerns of both randomness failures and the threat of fault injection, some signature designs are advocating a “hedged” derivation of the per-signature randomness, by hashing the secret key, message, and a nonce. Despite the growing popularity of the hedged paradigm in practical signature schemes, to the best of our knowledge, there has been no attempt to formally analyze the fault resilience of hedged signatures.
We perform a formal security analysis of the fault resilience of signature schemes constructed via the Fiat–Shamir transform. We propose a model to characterize bit-tampering fault attacks, and investigate their impact across different steps of the signing operation. We prove that, for some types of faults, attacks are mitigated by the hedged paradigm, while attacks remain possible for others. As concrete case studies, we then apply our results to XEdDSA, a hedged version of EdDSA used in the Signal messaging protocol, and to Picnic2, a hedged Fiat–Shamir signature scheme in Round 2 of the NIST Post-Quantum standardization process.
Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part I
EditorsAnne Canteaut, Yuval Ishai
PublisherSpringer, Cham
Pages644-674
Number of pages31
DOIs
Publication statusPublished - 1 May 2020
Event39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2020 - Online
Duration: 11 May 202015 May 2020
Conference number: 39
https://eurocrypt.iacr.org/2020/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Cham
Volume12105
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2020
Abbreviated titleEUROCRYPT 2020
Period11/05/2015/05/20
Internet address

Fingerprint

Dive into the research topics of 'Security of Hedged Fiat-Shamir Signatures Under Fault Attacks'. Together they form a unique fingerprint.

Cite this