[Cryptography] Attacks on Fiat-Shamir transformation (Pseudorandom Oracles based on Hash Functions)

[Ray Dillinger]

Are people aware of this paper? It came out in January but I hadn't 
heard of it yet.

https://eprint.iacr.org/2025/118

Researchers at the Ethereum Foundation have formulated an attack on 
"Random Oracles" formulated as hash functions on nonrandom data. This is 
applicable to the specific case where such a Pseudorandom Oracle is used 
for the randomness needed to construct cryptographic proofs-of-knowledge.

The attack allows the construction of non-interactive solutions to such 
proofs-of-knowledge, meaning essentially that someone can "prove they 
know" something which they do not in fact know.

I haven't done the math in detail but I don't see anything that would 
indicate it's a non-feasible attack given the capabilities of an 
ordinary desktop computer.  It could still turn out to be a false alarm 
if the authors are wrong.  The authors call it a "practical attack" but 
acknowledge that as far as they know, no protocols in widespread use 
depend on this particular construction.

This could break a couple of block chain designs I've heard of but I 
don't know whether those designs were implemented nor which are affected 
if they were. It definitely does not affect Bitcoin or Ethereum.  It 
affects a capability that someone was considering adding to Ethereum, 
but which had not been deployed.

Any block chains enabling transactions that rely on this construction 
are either dead in the water, or if they still exist urgently need 
redesign. But it looks like nothing else breaks right now (or broke in 
January) even if the authors are right about the attack.

It would become the latest example of constructions formerly thought 
secure, which pros have to look out for.  In-house and homebrew crypto 
implementors basing their work on everything published before this 
attack became widely known, will be very confidently getting it wrong 
for the next decade at least.

Meanwhile attention must be paid to making sure that the authors are 
right. If they are right, then attention must be paid to putting 
warnings about it into the next generation of textbooks, updating the 
errata for current textbooks, combing the archives for papers that must 
be rebutted or retracted, updating widely available crypto tools and 
libraries to specifically detect and/or prevent this use of the 
Fiat-Shamir, and trying to find ways to extend the attack or apply it in 
different domains (and thus finding other constructions that must be 
warned against, rebutted, or retracted).

Whatever else is good, bad, or ugly about block chain protocols, they 
have spurred a surprising amount of research and practical experience 
with things that were up to now fairly esoteric and theoretical 
cryptographic constructions.

Bear

---

"Well, that's the problem, isn't it?" Burroughs said. "You've got your 
toves out of control all over the place, and when you go ask the 
Borogroves for some help, you find that they've gone all mimsy on you. 
Seems to happen at about this time every year."