Paper 2023/691

Weak Fiat-Shamir Attacks on Modern Proof Systems

Quang Dao, Carnegie Mellon University
Jim Miller, Trail of Bits
Opal Wright, Trail of Bits
Paul Grubbs, University of Michigan–Ann Arbor
Abstract

A flurry of excitement amongst researchers and practitioners has produced modern proof systems built using novel technical ideas and seeing rapid deployment, especially in cryptocurrencies. Most of these modern proof systems use the Fiat-Shamir (F-S) transformation, a seminal method of removing interaction from a protocol with a public-coin verifier. Some prior work has shown that incorrectly applying F-S (i.e., using the so-called "weak" F-S transformation) can lead to breaks of classic protocols like Schnorr's discrete log proof; however, little is known about the risks of applying F-S incorrectly for modern proof systems seeing deployment today. In this paper, we fill this knowledge gap via a broad theoretical and practical study of F-S in implementations of modern proof systems. We perform a survey of open-source implementations and find 36 weak F-S implementations affecting 12 different proof systems. For four of these---Bulletproofs, Plonk, Spartan, and Wesolowski's VDF---we develop novel knowledge soundness attacks accompanied by rigorous proofs of their efficacy. We perform case studies of applications that use vulnerable implementations, and demonstrate that a weak F-S vulnerability could have led to the creation of unlimited currency in a private blockchain protocol. Finally, we discuss possible mitigations and takeaways for academics and practitioners.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published elsewhere. IEEE S&P 2023
Keywords
Fiat-Shamirproof systemsweak Fiat-Shamirattacksblockchaincryptocurrencies
Contact author(s)
qvd @ andrew cmu edu
james miller @ trailofbits com
opal wright @ trailofbits com
paulgrub @ umich edu
History
2023-05-16: approved
2023-05-16: received
See all versions
Short URL
https://ia.cr/2023/691
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/691,
      author = {Quang Dao and Jim Miller and Opal Wright and Paul Grubbs},
      title = {Weak Fiat-Shamir Attacks on Modern Proof Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2023/691},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/691}},
      url = {https://eprint.iacr.org/2023/691}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.