Paper 2019/956

Security of Hedged Fiat-Shamir Signatures under Fault Attacks

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

Abstract

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 fault 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 in the literature. 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 against hedged Fiat-Shamir type signatures, 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 a concrete case study, we then apply our results to Picnic2, a recent Fiat-Shamir type signature scheme using the hedged construction.