How to prove false statements: Practical attacks on Fiat-Shamir

The time is given as "last October," and the work they were unfamiliar with is presumably "contrived proof protocols that are vulnerable to attack, no matter which hash function you use" as stated in the immediately preceding sentence.

I don't believe the "this work" that the article is talking about here is GKR, but work that is referenced earlier in the article:

> In the early 2000s, computer scientists showed how to do just that, contriving interactive proof protocols that were specifically designed to fail when they underwent Fiat-Shamir

Indeed, the artcile points out that targeting GKR was the idea of the Ethereum Foundation researcher.

> Soukhanov had the idea to target a Fiat-Shamir proof system based on something called the GKR protocol

Extremely theoretically, and the article is very sensational.

The paper is half a year old, and hasn't made a splash; if this were significant news, I would expect to be able to find more coverage on it.

I did find this more nuanced take here: https://blog.cryptographyengineering.com/2025/02/04/how-to-p...

I haven't seen much of Quanta "Magazine", but I feel all of it has been stuff like this?

From my cursory reading, it doesn't seem related to Bitcoin at all, but it might affect some more complex Ethereum protocols. Doesn't seem related to Ethereum itself, but it seems related to some zero-knowledge proofs.

edit: it seems to be related to something called "GKR protocol" that some cryptocurrencies use (?) - can use (?) - for somehow proving ... something? mining?.. using zero-knowledge proofs.... like here - https://www.polyhedra.network/expander (as usual in cryptocurrency, hard to tell what is actually being done/sold)

what I take from this, as a laic, is that... experimental ZK-proofs are indeed experimental.

No, this could not allow for faking Bitcoin or Ethereum TXs. This type of vulnerability mainly concerns "zero-knowledge" proof methods, which do not occur inside the Bitcoin or Ethereum base layers. Some teams are building ZK proofs on top of these and other blockchains though, so those systems could be vulnerable, though they are still largely experimental.

(Take this with a grain of salt as I only learned about the Fiat-Shamir heuristic via this HN thread last week https://news.ycombinator.com/item?id=44458168, and I only have basic experience in theoretical cryptography)

There exists the concept of a zero-knowledge proof: check out the Wikipedia page for some intuitive examples of how these work in an interactive context. Basically, by asking someone who wants to prove something (the prover) a bunch of questions (challenges), you can get probabilistic confidence that they actually know that thing: https://en.wikipedia.org/wiki/Zero-knowledge_proof#Abstract_...

You want it to be interactive because that makes it much harder for the prover to "fake it" on the spot. But it would be more convenient if you didn't need to be online and actively talking to each other - so we want a non-interactive way to do the same thing.

The Fiat-Shamir transform (or heuristic) says that we can transform interactive protocols into non-interactive ones by relying on "random" challenges. If the prover can't control the randomness, then it's about as good as you interactively challenging them (and you can e.g. make them do more challenges to make up for it).

How do we get randomness? In computing we don't really have anything totally random, but cryptographic hash functions are believed to be very difficult to predict the output to. So, in cryptography there's the "random oracle model" where you say, "Well, I don't know if this protocol is safe with these real-life hashes. But if the hash function was a truly random oracle, I can prove it's safe." (The Fiat-Shamir transform is only provably secure if you believe in the random oracle model).

In the past, researchers have constructed new protocols that are safe in the random oracle model, but once you use a real hash function they're breakable because of real-world implementation details. As the abstract of this paper says, "So far, all of these examples have been contrived protocols that were specifically designed to fail." See https://crypto.stackexchange.com/q/879 for some discussion of the mechanics of how it might happen, once you choose a real hash function.

This new paper advances the field by showing an attack that targets a real-world protocol that people actually use, GKR. It shows (and again, take my interpretation with a grain of salt) that when you pick a real hash function, the attacker can construct an input (circuit) that results in whatever output the attacker wants.

---

What's the real-world impact?

There do exist real non-interactive zero-knowledge proof systems, mainly used in blockchains. Instead of publicly exposing all the info to the world and doing computation on the (slow) blockchain, you can protect privacy of transactions and/or bundle a bunch of updates into a cheaper one (ZK-rollups). Theoretically these could be attacked using the methods described in the paper.

It's unclear to me whether those are affected here (though my guess is no, since they could have mentioned it if so).

Probably - but you are likely to be caught as eventually someone will verify your work with a non-broke program. I'm not clear exactly how likely that is (I'm not interested enough in cryptocurrency to bother to dig into the algorithm, but IIRC several different parties need to agree on a transaction before it is considered real - or something like that, I hope I sound confused), but if you are doing a lot of bitcoin fraud someone will notice.

I'm not sure if they can trace the fraud to you.

A security researcher showed me years ago that blockchains were hackable. I don’t remember the proof, but since then have had low interest in crypto or blockchains. I’d like to make money off of it, but it’s insecure.

I think the thing that you're missing here is that the "malicicous program" being discussed here isn't malicious from the usual point of view of what "malicious" means. It's truly functionally identical to the original program -- it returns the same outputs on the same inputs, there isn't some secret input that makes it do something wrong.

Despite that, it's nonetheless "malicious" in that, with the modifications made to it, FS can be made to "prove" false things about it. So you can "prove" that M(x)=y, even though when you actually run M(x), you find that you don't get y.

Yes, what you are missing is that attacks on Fiat Shamir were very contrived up to now.

However the paper shows that there in fact exists a pretty simple way to break the Fiat Shamir heuristic, for a protocol operating in the RO model. And such kind of efficient attacks are rather concerning in cryptography land.

So this isn't about the attack per se, rather it's about the existence of such an easy one.

The “choosing the program” part is vague, but in many practical cases the user gets to choose the program by choosing input data.

This goes back to the rather fuzzy distinction between “data” and “program” you may remember from your early CS days. More precisely, from a theoretical CS perspective, there is no solid difference between data and program.

Almost all practical ZK schemes require the user to choose some input (eg the root of the merkle tree representing the “current state” of the blockchain and secrets like keys and the amount of a transaction).

From some perspective, you get a different program for each different input; sometimes people call this “currying” or “partial evaluation”.

So yeah, it’s more serious than it seems at first blush.

That's a completely different and unrelated type of vulnerability, though.

Implementation mistakes leading to mass coin theft would certainly be cryptocurrency news, but they would not be crypto(graphy) news. Breaking an actual peer-reviewed zero knowledge proof scheme would be.

But once you've made a function that "cannot be used to produce the material described by the hash", you've also made a very good pseudo-randomizer. In fact, if a cryptographic hash function cannot be trusted for its ability to produce apparent randomness, then it cannot be trusted for its "intended purposes". You get both properties or neither.

You may want to stay away from all modern CSPRNGs then. Eg Yarrow and Fortuna rely on sources of random input data being mixed in but using a strong hash function (nowadays sha-256) to produce the output at arbitrarily fast rates without consuming entropy.

And to your criticism that this is just programmers who don’t know what they’re doing, these algorithms were developed by Bruce Schneier, Niels Ferguson, and John Kelsey.

I was so frustrated as a noob trying to understand why people were using hashes this way. Even a professional told me "yeah but a collision is really unlikely," and compared it to neutrino interference. How is that supposed to be good enough?

You realize all signatures in use today basically use hash functions as randomness

You should look into the HyperLogLog algorithm, where fair hash "randomness" is required for the algorithm to work. There are use cases where the pseudo-randomness of hashes is useful, is what I'm trying to say.

I'm sorry, but this comment is very vague and unclear.

Cryptographers know that hashes (even cryptographically strong ones!) are deterministic. Yet, it is possible that in going from an interactive proof to a non-interactive one, one does not actually need randomness. Indeed, for some class of protocols, we know how to design hash functions satisfying a particular property (correlation intractability) so that the resulting non-interactive proof is sound. It's just that (a) these hashes are inefficient, and (b) until now no one had found a non-contrived protocol where using standard hashes leads to an attack.

I also had to just go to the paper. It was really difficult trying to get through the article. Needlessly hyped language like "proving lies" and hyperfixations on things like leaking boats... felt like the author was either out of their element or inexperienced with math comms. However, the article still provides a bit of context that the paper doesn't.

That said, this is honestly just a bad article that is needlessly sensationalized and fails to impart any real knowledge.

I recommend this whiteboard session as well o.o https://blog.zksecurity.xyz/posts/pudding3/

They do at least link to that in the 4th paragraph of the article. Many of these summary articles don't do that.

That's the case with many cryptographic explanations for laypeople, in my experience (as mostly a layperson).

Maybe all these elaborate analogies of Alice walking into a cave and Bob yelling which exit she should come out of, Alice wanting to sell Bob a Hamiltonian cycle trustlessly, Alice and Bob mixing buckets of paint and shipping them via the mail back and forth etc. are working for some people, but it's not me.