Disarming Fiat-Shamir footguns

Malware News
1

By Opal Wright

The Fiat-Shamir transform is an important building block in zero-knowledge proofs (ZKPs) and multi-party computation (MPC). It allows zero-knowledge proofs based on interactive protocols to be made non-interactive. Essentially, it turns conversations into documents. This ability is at the core of powerful technologies like SNARKs and STARKs. Useful stuff!

But the Fiat-Shamir transform, like almost any other cryptographic tool, is more subtle than it looks and disastrous to get wrong. Due to the frequency of this sort of mistake, Trail of Bits is releasing a new tool called Decree, which will help developers specify their Fiat-Shamir transcripts and make it easier to include contextual information with their transcript inputs.

Fiat-Shamir overview

Many zero-knowledge proofs have a common, three-step protocol structure1:

  1. Peggy sends Victor a set of commitments to some values.
  2. Victor responds with a random challenge value.
  3. Peggy responds with a set of values that integrate both the committed values from step (1) and Victor’s random challenge value.

Obviously, the details of steps (1) and (3) will vary quite a bit from one protocol to the next, but step (2) is pretty consistent. It’s also the only part where Victor has to contribute anything at all.

It would make things much more efficient if we could eliminate the whole part where Victor picks a random challenge value and transmits it to Peggy. We could just let Peggy pick, but that gives her too much power: in most protocols, if Peggy can pick the challenge, she can customize it to her commitments to forge proofs. Worse, even if Peggy can’t pick the challenge, but can predict the challenge Victor will pick, she can still customize her commitments to the challenge to forge proofs.

The Fiat-Shamir transform allows Peggy to generate challenges but with the following features:

  • Peggy can’t meaningfully control the result of the generated challenges.
  • Once Peggy has generated a challenge, she cannot modify her commitment values.
  • Once Victor has the commitment information, he can reproduce the same challenge value Peggy generates.

The basic mechanism of the Fiat-Shamir transform is to feed all of the public parts of the proof (called a transcript of the proof) into a hash function, and use the output of the hash function to generate challenges. We have another blog post that describes this in better detail.

Having a complete transcript is critical to the secure generation of challenges. This means that implementers need to clearly specify and enforce transcript requirements.

Failure modes

There are a couple of Fiat-Shamir failure patterns we see in practice.

Lack of implementation specification

We often observe that customers’ transcripts are ad-hoc constructions, specified only by the implementation. The list of values added to the transcript, the order of their inclusion in the transcript, and the format of the data can be ascertained only by looking at the code.

Being so loosey-goosey with such an important component of a proof system is bad practice, but we see it all the time in our code reviews.

Incorrect formal specification

Papers describing new proof techniques or MPC systems necessarily reference the Fiat-Shamir transform, but how the authors of those papers discuss the topic can make a big difference in the security of implementation.

The optimal situation occurs when authors provide a detailed specification for secure challenge generation. A simple, unambiguous list of transcript values is about as easy as it gets, and will be accessible to implementers at all levels of experience. Assuming the authors don’t make a mistake with their spec, implementers have a good chance of avoiding weak Fiat-Shamir attacks.

When authors wave their hands and say little more than “This protocol can be made interactive using the Fiat-Shamir transform,” the nitty-gritty details are left to the implementer. For savvy cryptographers who are up to date with the literature and understand the subtleties of the Fiat-Shamir transform, this is labor-intensive, but workable. For less experienced developers, however, this is a recipe for disaster.

The worst of both worlds is when authors are hand-wavy, but try to give unproven examples. One of our other blog posts includes a good example of this: the Bulletproofs paper. The authors’ original paper referenced the Fiat-Shamir transform, and suggested what a challenge generation might look like. Many cryptographers used that example as the basis for their Bulletproofs implementation, and it turned out to be wrong.

Lack of enforcement

Even when a transcript specification is present, it can be hard to verify that the spec is followed.

Proof systems and protocols in use today are incredibly complex. For some zkSNARKS, the Fiat-Shamir transcript can include values that are generated in subroutines of subroutines of subroutines. A protocol may require Peggy to generate values that meet specific properties before they can be used in the proof and thus integrated into the transcript. This leads to complicated call trees and a lot of conditional blocks in the software. It’s easy for a transcript value that’s handled in an “if” block to be skipped in the corresponding “else” block.

Also, the complexity of these protocols can lead to intricate architectures and long functions. As functions grow longer, it becomes hard to verify that all the expected values are being included in the transcript. Transcript values are often the result of very complex computations, and are usually added to the transcript shortly after being computed. That means transcript-related calls can be dozens of lines apart, or buried in subroutines in entirely different modules. It’s very easy for a missed transcript value to get lost in the noise.

Not by fiat, but by decree

Trail of Bits is releasing a Rust library to help developers avoid these pitfalls. The library is called Decree, and it’s designed to help developers both create and enforce transcript specifications. It also includes a new trait designed to make it easier for transcript values to include contextual information like domain parameters, which are sometimes missed by developers and authors alike.

The first big feature of Decree is that, when initializing a Fiat-Shamir transcript, it requires an up-front specification of required transcript values, as well as a list of the expected challenges. Trying to generate a challenge before all of the expected values have been provided gets flagged as an error. Trying to add a value to the transcript that isn’t expected in the specification gets flagged as an error. Trying to add a value to the transcript that has already been defined gets flagged as an error. Trying to request challenges out of order… you get the idea.

This specification and enforcement mechanism is provided by the Decree struct, which builds on the venerable Merlin library. Using Merlin means that the underlying hashing and challenge generation mechanisms are solid. Decree is designed to manage access to an underlying Merlin transcript, not to replace its cryptographic internals.

As an example, we can riff a bit on our integration test that implements Girault’s identification protocol. In our modified example, we’ll start by making the following call:

let mut transcript = Decree::new("girault",
     &["g", "N", "h", "u"], &["e", "f"]);

This initializes the Decree struct so that it expects four inputs named g, N, h, and u, and two outputs named e and f. (For the Girault proof, we only need e; f is included purely for illustrative purposes.)

We can add all of these values to the transcript at the same time, or we can add them as they’re calculated:

transcript.add_serial("h", &h)?;
transcript.add_serial("u", &u)?;
transcript.add_serial("g", &g)?;
transcript.add_serial("N", &n)?;

Notice that the order we added the values to the transcript doesn’t match the ordering given in the declaration. Decree doesn’t update the underlying Merlin transcript until all of the values have been specified, at which point the inputs are fed into the transcript in alphabetical order. Changing up how you order your Decree inputs doesn’t impact the generated challenges.

We can then generate our challenges:

let mut challenge_e: [u8; 128] = [0u8; 128];
let mut challenge_f: [u8; 32] = [0u8; 32];
transcript.get_challenge("e",
    &mut challenge_e)?;
transcript.get_challenge("f",
    &mut challenge_f)?;

When we generate challenges, order does matter: we are required to generate e first, because e is listed ahead of f in the declaration.

A Decree struct is not limited to single-step protocols, either. Once all of the challenges in a given specification have been generated, a Decree transcript can be extended to handle further input values and challenges, carrying all of the previous state information with it. For multi-stage proofs, the extension calls help delineate when protocol stages begin and end.

The ability to include contextual information is provided by the Inscribe trait, which is derivable for structs with named members. When deriving the Inscribe trait, developers can specify a function that provides relevant contextual information, such as elliptic curve or finite field parameters. This information is included alongside deterministic serializations of the struct members. And if a struct member supports the Inscribe trait, then its contextual information will be included as well.

We can use the Inscribe trait to simplify handling of a Schnorr proof:

/// Schnorr proof as a struct
    #[derive(Inscribe)]
    struct SchnorrProof {
        #[inscribe(serialize)]
        base: BigInt,
        #[inscribe(serialize)]
        target: BigInt,
        #[inscribe(serialize)]
        modulus: BigInt,
        #[inscribe(serialize)]
        base_to_randomized: BigInt,
        #[inscribe(skip)]
        z: BigInt,
    }

After we’ve filled in the base, target, modulus, and base_to_randomized values of a SchnorrProof struct, we can simply add it to our transcript, generate our challenge, and update the z value:

let mut transcript = Decree::new(
    "schnorr proof", &["proof_data"], 
&["z_bytes"]).unwrap();
transcript.add("proof_data", &proof)?;

let mut challenge_bytes: [u8; 32] = [0u8; 32];

transcript.get_challenge(“z_bytes”,

&mut challenge_bytes)?;

let chall = BigInt::from_bytes_le(Sign::Plus,

&challenge_bytes);

let proof.z = (&chall * &log) + &randomizer_exp;

By setting the #[inscribe(skip)] flag on the z member, we set up the struct to automatically add every other value to the transcript; adding z to the proof makes it ready to send to the verifier.

In short, the Decree struct helps programmers to define, enforce, and understand their Fiat-Shamir transcripts, while the Inscribe trait makes it easier for developers to ensure that important contextual data (such as elliptic curve identifiers) is included by default. While getting a Fiat-Shamir specification wrong is still possible, it’ll at least be easier to spot, test, and fix.

So give it a shot, and let us know what you think.

1Many of the more complicated proof systems have multiple instances of this structure. That’s okay; our ideas here extend to those systems.

Article Link: Disarming Fiat-Shamir footguns | Trail of Bits Blog