14 ms·
How to prove false statements: Practical attacks on Fiat-Shamir
Paper: https://eprint.iacr.org/2025/118 https://eprint.iacr.org/2025/118
- bsenftner 1y ago[flagged]
- deleted 1y ago[deleted]
- jeffhuys 1y agoThat piece of information about Ethereum's cryptographers does not mean "all of crypto is a fraud".
- procaryote 1y agoNo, but if crypto was generally legit, one might expect the people working on Ethereum cryptography to know their area of specialisation...
- xyzzy123 1y agoTwo of the authors of the paper listed their affiliation as the Ethereum foundation. It seems more like the project was doing due diligence?
- gardenhedge 1y agoHow about Silvio Micali in the Algorand world? How does ethereum make Algorand not legit?
- jeffhuys 1y agoAgain, you mean "if Ethereum was". You're conflating things.
- procaryote 1y agonot really. Ethereum is pretty big and sometimes central to other crypto projects.
- naikrovek 1y agoyou're right. "all of crypto is fraud" and the Ethereum cryptographers not knowing about this important detail are two statements that are true separately.
- actionfromafar 1y agoMade me laugh, then chuckle. Both funny and logic joke funny.
- diggan 1y ago> Ethereum’s cryptographers are not cryptographers I guess I'll bite, what are they then? If they're focusing on the cryptography of a project, doesn't that make them cryptographers? Or you mean they aren't "real cryptographers"? > It's a wish club of technical yes people. Isn't that basically one of the ways doing innovation? Instead of saying "No, that's not possible" when someone asks if they can build something faster than a horse and carriage, a bunch of people get together to see if there any way of doing that, trying to avoid any per-concieved ideas about if it's actually possible or not.
- teiferer 1y agoIt's the old "we use first principles thinking" approach. Too often it means "we don't actually know or care what came before us, we just move fast and break things, how hard can it be lol yolo" Then that's what you get, insufficiently educated folks re-inventing the wheel, repeating mistakes others have done before. Yes, sometimes you need to break out from pre-conceived notions, evaluating whether conditions have changed and earlier assumptions are maybe not valid anymore. But that's no excuse to be ignorant.
- blueflow 1y ago> Isn't that basically one of the ways doing innovation? Instead of saying "No, that's not possible" when someone asks if they can build something faster than a horse and carriage, a bunch of people get together to see if there any way of doing that, trying to avoid any per-concieved ideas about if it's actually possible or not. This does not take real-world limits into account. There are limits to information theory (which includes crypto), thermodynamics and mechanics that make certain things generally impossible. Like a perpetuum mobile. Social or intelligence factors do not matter. Knowing your field also includes understanding those "hard" limits.
- lr4444lr 1y agoIsn't that basically one of the ways doing innovation? Instead of saying "No, that's not possible" when someone asks if they can build something faster than a horse and carriage, a bunch of people get together to see if there any way of doing that, trying to avoid any per-concieved ideas about if it's actually possible or not. Yes, but if people graduate from engineering schools that explicitly teach the concepts of the combustion engine, and the carriage manufacturers claiming to be engineers are unaware of basic principles like the 4 stroke cycle, you have a completely different kind of problem.
- arbll 1y agoOne anecdote => All Ethereum’s cryptographers are a fraud => All crypto is a fraud You're deducing a lot from this one quote lol
- naikrovek 1y ago"all crypto is fraud" stands alone just fine. It's very clear that the blockchain is 100% BS to anyone who is not incentivized to see it as valid.
- db48x 1y ago> It's very clear that the blockchain is 100% BS… Hmm. The blockchain is actually a very clever solution to a very old coordination problem. In that sense it is not BS at all. But I agree that it is an open question whether it can directly support a useful economy the way a currency can. It doesn’t seem to have the throughput for that, to start with. But maybe it could be useful for interbank settlements, if for some reason traditional methods weren’t working.
- reactordev 1y agoThis has been known for a long time that in order for crypto backed securities to work, Bitcoin’s blockchain would need to be the clearing house for assets tied to it. We’re in derivatives of derivatives of indexed derivatives land. Banks have already started exploring using it as the clearing house and recent US policy has cleared the path for more.
- pwndByDeath 1y agoMy hot take, crypto(currency) is for pure peer markets, since all individuals are accounted for by a government its not especially useful for people. However, governments are essentially peers without some disinterested third party with the power of enforcement. This is place where crypto lives.
- 1y ago
- Sophira 1y ago> This is why all of crypto is a fraud... Are you using "crypto" here to mean "cryptocurrency", rather than "cryptography"? Because if so, that's not obvious considering you just mentioned cryptographers in the previous sentence. If, on the other hand, you mean "all of cryptography is a fraud", then I'm curious to know what makes you think that.
- deleted 1y ago[deleted]
- bsenftner 1y agoSorry, "cryptocurrency".
- john_alan 1y agolol. I work in Applied cryptography and I don’t know a harder distributed system built on such a broad spectrum of primitives which has seen such high uptime. Are you qualified to speak on this topic?
- vintermann 1y agoCryptography is big enough that you can't expect every academic cryptographer to be intimately familiar with every obscure theoretical result. Yes, all cryptocurrency is basically a scam, but that's independent from whether the Ethereum foundation's experts know X or not.
- sophia000 1y ago[flagged]
- tempodox 1y agoDoes that mean you can fake Bitcoins or cryptocurrency transactions? What exactly could be affected by these vulnerabilities? Is there a better article anywhere that actually spells it out for the layman?
- sheiyei 1y agoExtremely 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-prove-false-statements-part-1/ 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?
- yorwba 1y agoThe nuanced take was also discussed here at the time: https://news.ycombinator.com/item?id=42939312 https://news.ycombinator.com/item?id=42939312
- verandaguy 1y agoQuanta is a pretty popular, popular science outlet. It tends to be closer to the theory than (capital P, S) Popular Science magazine, but ultimately much of what they publish is digested to a degree for lay consumption. They had an article just the other day about a more optimal sphere packing that was up my alley as a technical (programmer) person with a casual interest in broader pure math. They do sensationalize a bit as a side effect of their process though, no argument there.
- pas 1y agousually they are very thorough (for a magazine targeting curious well-motivated, but of course still a virtually completely laymen audience), but it seems recently their volume has increased whil quality stayed constant :)
- intalentive 1y agoQuanta is “pop science” for smart lay people who might also read, for instance, the New Yorker.
- austin-cheney 1y agoHashes should never be a source of randomness. Randomness makes assumptions far outside their intended use case. Hashes should only be a reproducible label that cannot be used to produce the material described by the hash. When used for their intended purposes hashes serve as the strongest point of integrity until value collisions are discovered.
- ted_bunny 1y agoI 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?
- Tyyps 1y agoHash functions are used to instantiate a random oracle (which is a theoretical object that can't be instantiated because it would be of infinite size but makes it easy to reason about) because it doesn't seems crazy as an assumption that if finding a collision between 2 hashes is hard it should be hard to predict the output of the so called hash function. However it is well known that there was some contrive counter example for protocols that are secure under the Random Oracle model and unsecure when instanciated with any hash function. The problem with this paper is that the protocol it described isn't so contrive anymore. Cryptography is a matter of assumptions and what you believe in or not. You might want to not use random oracle but you will therefore have to restrict yourself in what you can concretely build. And the reason behind the problem outlined in the paper isn't a biased randomness problem but the fact that you can represent the hash function compared to a RO.
- deleted 1y ago[deleted]
- raxxorraxor 1y agoEvery hash function will have collisions as long as the input is larger than the resulting hash. Some are designed that changing a bit has a massive influence on the resulting hash, others do the opposite.
- karel-3d 1y agoI find the actual paper more readable and understandable than this summarization. https://eprint.iacr.org/2025/118 https://eprint.iacr.org/2025/118
- soulofmischief 1y agoI 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.
- some_furry 1y ago> That said, this is honestly just a bad article that is needlessly sensationalized and fails to impart any real knowledge. There's a joke to be made here, since the issue is with zero-knowledge proof systems.
- hinterlands 1y ago(Note: the original title was "Computer Scientists Figure Out How To Prove Lies" before being changed by the admin) I honestly think that Quanta Magazine just found the perfect formula to farm HN traffic. The titles are clearly carefully engineered for this audience: not the outright clickbait of university press releases, but vague profoundness that lets us upvote without reading the whole thing and then chime in with tangential anecdotes. I don't think they're bad people, but I honestly think they end up on the front page multiple times a week not on the quality of the articles alone.
- tyingq 1y agoThey do at least link to that in the 4th paragraph of the article. Many of these summary articles don't do that.
- baby 1y agoI recommend this whiteboard session as well o.o https://blog.zksecurity.xyz/posts/pudding3/ https://blog.zksecurity.xyz/posts/pudding3/
- deleted 1y ago[deleted]
- catfacts 1y agoI recall someone creating a crypto system and then forgetting to protect the constructor of the initial object so other could change the constructor and do whatever they wanted with that crypto system, but in the end the creators were just web developers with a little training in crypto. In those circumstances those millions of coins flying in or out are not a tragedy (at least for me) but a very plausible outcome.
- lxgr 1y agoThat'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.
- PontingClarke 1y ago[flagged]
- doodlebugging 1y ago>if a professor has assigned 100 problems for homework but doesn’t want to grade a student’s entire assignment, she can randomly choose 10 problems to grade. In the language of computer scientists, she is making 10 “random challenges” to the student’s homework. If the answers to those 10 problems are correct, the professor can feel confident that most of the other answers are correct too. Eureka! I found the reason that so many things in society have gone to shit in the last few years. Far too many professors are so overworked or maybe just lazy and are using this type of tool to grade student work and the end result is that we have too many students passing through the system who have demonstrably only been able to score a 10/100. I'm over 60 now and if I had scored lower than my current age back in the day I would fail and need to repeat the grade/course. Now they just kick the can('ts) on down the road and hope no one ever notices. Too bad some of these failures end up in positions of influence where their uncharted deficiencies have the power to disrupt or destroy functional systems. Or maybe I'm joking. I'll know once the caffeine hits.
- deadbabe 1y agoWhy would they not simply, assign 10 problems?
- pas 1y agopresumably they glance at the other 90 too, and they then do a thorough verification on that random 10 the analogy is not great, but in cryptography something similar is at play (easy to get/check trivial properties and then hard to achieve/produce/fake the interesting ones)
- Winsaucerer 1y agoPresumably more questions can cover a wider variety of skills/techniques/topics. If the student doesn't know in advance which 10 will be selected, they either have to pray they're lucky, or work diligently on all problems.
- doodlebugging 1y agoThere is a risk here that the professor who only assigns 10 problems will only check one of them for correctness. If 5/10 of the answers are wrong but the professor verifies a correct answer for one of the 5/10 with a correct solution then their conclusion that the other 9/10 answers are correct due to some likelihood or probability function is invalid and a dimwit makes the grade.
- metaesn 1y agoWhat is a lie? what is the truth? It is very difficult to find the truth, and the descriptions of the same thing are different for different persons. So the title and its content is a lie.
- librasteve 1y agothis is a lie
- zsoltkacsandi 1y ago> and the descriotions of the same thing are different for different persons When my son says, "I wasn't there" when the glass broke, it's not just a matter of differing descriptions, it's a clear denial of a fact. There are facts, and when someone deliberately twists or denies them, that's not just a different perspective. That's a lie.
- metaesn 1y agoYou are right, for somethings, the truth is clear, but for other things, it is difficult to find the last truth, only reach its truth over time
- zsoltkacsandi 1y ago> it is difficult to find the last truth, only reach its truth over time The fact that is difficult to find out the truth, does not mean that something was or wasn't a lie. Paradoxically this is an attribute of a "good" lie: it is difficult to find out that it wasn't the truth.
- PretzelPirate 1y ago> When he shared his thoughts with Ethereum’s cryptographers, he was startled to learn that they were unfamiliar with this work It would be nice if the article included timelines. Ethereum researchers have been talking about GKR since 2020,so it's hard to imagine the lack of familiarity.
- yorwba 1y agoThe 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.
- PretzelPirate 1y agoThat's confusing to me because back in 2020 when they were looking into GKR inside of a Snark, they were worried about these attacks. Following up in 2022, Ethereum researchers were talking about attacking GKR by forging proofs and not having sufficient randomness/collision resistant. It's hard to align what's being researched on Ethresar.ch and this statement.
- shkkmo 1y agoI 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
- bluGill 1y agoMy initial prediction is they just divided by zero someplace - just like every other undergrad in any degree program that requires some advanced math has. I'm happy to see they didn't make this obvious mistake.
- baby 1y agoHere's a whiteboard session going over that but https://blog.zksecurity.xyz/posts/pudding3/ https://blog.zksecurity.xyz/posts/pudding3/
- seriousmountain 1y ago[dead]
- GTP 1y agoThe article is lacking a lot of details, so maybe I'll check the paper if I have the time in the coming days. But, my understanding from the article is that this attack works by breaking a premise of the considered protocols that doesn't have much to do with the random oracle model. They basically say that, if you agree on a program to use and you hash it as part of your commitment, then you can use the Fiat-Shamir transform to prove claims regarding the program's output. But it seems natural to me that, if you are tricked into accepting the use of a malicious program, then the protocol breaks. After all, the hashing of the program at the beginning is meant to ensure that you're using a specific binary you agreed upon, but it does nothing to show that such a binary works as intended. This has to be verified outside of such protocol. Am I missing something? Or maybe the point is that, under the random oracle model, it should be hard to write a program that contains its own hash? But then again, would the trick of reading the hash from an external configuration file that isn't considered as part of the hashing be fair game?
- quantumgarbage 1y agoYes, 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.
- ShroudedNight 1y agoWhat does "easy" mean in this context? From my [ignorant] reading, it sounds like it requires being able compute a fixed point for the hash function in order to be able to integrate it into the program and respond differently under test. I thought that was one of the things cryptographically secure hash functions explicitly made difficult?
- quantumgarbage 1y agoBy "easy" I mean straightforward. Previous examples which showed how instantiating Fiat Shamir leads to an unsound protocol were so contrived that people use to think that they were a testament to how unlikely breaking FS would be [1]. In "How to Prove False Statements", you can actually build what they show. [1]: e.g. see https://eprint.iacr.org/1998/011.pdf https://eprint.iacr.org/1998/011.pdf
- deleted 1y ago[deleted]
- EGreg 1y agoThe key to why this even works (and didn’t work before) is here: https://community.intercoin.app/t/paper-shows-relying-on-hash-based-random-oracles-aren-t-enough/2922 https://community.intercoin.app/t/paper-shows-relying-on-has... Simply put, a reliable random oracle in an adversarial environment should be based on sources of randomness from multiple sources and participants, usually the sources are the participants’ meaningful actions to prevent collusion. It has been known for quite a while that if the space of inputs being hashed is small, the hashing is relatively useless for most benefits of a true one-way function (eg hashing a phone number in USA).