[HN Gopher] How to prove false statements: Practical attacks on ...
___________________________________________________________________
How to prove false statements: Practical attacks on Fiat-Shamir
Paper: https://eprint.iacr.org/2025/118
Author : nsoonhui
Score : 190 points
Date : 2025-07-10 09:48 UTC (13 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| tempodox wrote:
| Does 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 wrote:
| 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?
| yorwba wrote:
| The nuanced take was also discussed here at the time:
| https://news.ycombinator.com/item?id=42939312
| verandaguy wrote:
| Quanta 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 wrote:
| usually 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 wrote:
| Quanta is "pop science" for smart lay people who might also
| read, for instance, the New Yorker.
| karel-3d wrote:
| 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.
| lxgr wrote:
| Schnorr signatures, which Bitcoin uses, are based on the
| Fiat-Shamir transform, but I don't know enough about this
| attack to be able to tell whether there's any problem with
| that particular instance of it.
| baobun wrote:
| So the way Ethereum comes in is that the community at large
| is moving user activity to "L2s" - separate blockchains
| (sidechains) usually rolled up in and therefore secured by
| Ethereum Mainnet. Some of the newer L2s where apparently
| using this. So it affects Ethereum to the extent that its
| users could be bridging witg unsane protocols and
| implementations.
|
| There are usually "bridge contracts" deployed on Mainnet to
| allow briding assets/tokens between them. This (besides obv
| exchanges) is where most of the ridiculous hacks and online
| theft of past few years have happened. The Axie/Ronin hack
| was a huge facepalm and should have been a lesson to be more
| wary of handwavy security claims of these more experimental
| networks.
| bluGill wrote:
| 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.
| fract0l wrote:
| 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.
| mckirk wrote:
| The major blockchains are basically billion-dollar bug bounty
| programs. If they were hackable that easily, we'd probably
| know already.
| bluGill wrote:
| That depends on the hack. If the hack is something that is
| traceable to you then the hack becomes fraud and the police
| will be at your door. This assumes that the likes of Russia
| and North Korea have decided that there is more value in
| bitcoin remaining operational than the one time haul of
| money they can get from the fraud (which to be fair seems
| unlikely since it is prisoners dilemma where the defector
| chooses the final round)
| __MatrixMan__ wrote:
| I dislike bitcoin, but you gotta admit that that's a
| rather clever aspect of it: Anybody with the power to
| destroy it is better off participating in it instead.
|
| We'll need to find our way out of that logic eventually.
| Scarcity in general and proof of work in particular are
| terrible bases for an economy. But it is a respectable
| foe.
| bluGill wrote:
| it is a prisoner dilemma where the defector controls when
| the final round is. If you know of a flaw you can win
| more long term by not exploiting it - but if someone else
| exploits it bitcoin becomes worthless. Thus if you know
| of a flaw there is pressure to exploit it first before
| someone else gets the benifits of defecting and ends the
| game
| __MatrixMan__ wrote:
| It depends on the flaw, for most of the attack surface
| that bitcoin has, your "flaw" is just an unfair advantage
| against the other miners, which you'll likely keep secret
| and keep on mining. That's not exactly a "bitcoin becomes
| worthless" scenario, it's not really that different from
| a halving, which are block-height-scheduled events built
| into the protocol.
| lxgr wrote:
| > If the hack is something that is traceable to you then
| the hack becomes fraud and the police will be at your
| door.
|
| That would be somewhat ironic, given the "code is law"
| mentality of many blockchain proponents.
|
| I don't doubt that many people would file police reports
| and lawsuits if any fundamental paradigm of blockchain
| cryptography were to suddenly be revealed as insecure,
| but I'd be following the lawsuits with a big bowl of
| popcorn.
| cypherpunks01 wrote:
| North Korea recently executed what I believe is the
| largest known theft in history, $1.5 billion in ETH
| stolen from the ByBit exchange. It was easily traceable
| to a state-run North Korean hacking group. No police at
| the door, and ETH only had a temporary dip.
|
| I'd think that if NK was sitting on a $1-10 billion
| Bitcoin bug, they'd execute it too before it got fixed or
| exploited by someone else.
| bobbiechen wrote:
| (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).
| cypherpunks01 wrote:
| 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.
| austin-cheney wrote:
| Hashes 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 wrote:
| 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?
| Tyyps wrote:
| Hash 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.
| raxxorraxor wrote:
| Every 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.
| bawolff wrote:
| Whether hashes are appropriate depend on the details of the
| usecase.
|
| However, if the negligible chance of a collision is what you
| are worried about, those also happen with random numbers.
| thrance wrote:
| 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.
| austin-cheney wrote:
| This is why you should NEVER trust software developers to
| make security decisions unless certified to do so. True
| randomness is challenging to achieve, because computers are
| inherently predictable. Pseudo-randomness is an intended
| process to intentionally achieve randomness in spite of this
| high predictability, often through use of physical or
| electromagnetic criteria outside the computing machine.
|
| Hash algorithms are none of that. They are not pseudo-
| randomness merely because a software developer merely wishes
| them to be so. Hash algorithms are intentionally designed to
| achieve high reproducibility in that a given set of input
| should always result in the same hash sequence as output.
| That intended reproducibility is by definition not random.
| simiones wrote:
| You don't understand what pseudo-randomness means.
| Virtually all PRNGs, even many CSPRNGs, have a way to
| initialize the algorithm with a seed, and its outputs are
| fully predictable based on that seed. Choosing a truly
| random seed, such as one produced by RNG hardware, will
| lead to a usefully random sequence - but the algorithm is
| still fully deterministic based on that seed.
| rapatel0 wrote:
| >True randomness is challenging to achieve, because
| computers are inherently predictable
|
| Most modern CPUs now contain a true RNG. They usually use
| some combination of a metastable latch, or thermal
| randomness through some kind of analog amplification. Bit
| strings from this are passed into a pseudorandom number
| generator to amplify the amount of random data generated.
|
| There probably attacks on this too but it's much harder.
| kbolino wrote:
| 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.
| austin-cheney wrote:
| This is broken logic.
|
| There is an untested assumption that hashes achieve
| randomness because they appear to be a random collection of
| characters. Hash sequences are completely reproducible given
| a set of input, and that is by definition not random.
|
| I think you are confusing loss of prediction as randomness.
| Never in mathematics or logic is that line of thinking
| correct. This can be described by equivocation, fallacy of
| composition, inductive fallacy, and more.
| gotoeleven wrote:
| he said pseudo-randomness
| austin-cheney wrote:
| And this still wrong for the same reasons. See:
| https://news.ycombinator.com/item?id=44521194
| gotoeleven wrote:
| You're saying something being reproducible implies that
| it is not pseudo-random. This is a definition of pseudo-
| random that exists only in your head.
|
| The first sentence of the wikipedia entry on pseudo-
| randomness is:
|
| "A pseudorandom sequence of numbers is one that appears
| to be statistically random, despite having been produced
| by a completely deterministic and repeatable process."
| austin-cheney wrote:
| That misses a factor called _good enough_ , or degree of
| predictability. Ultimately everything eventually becomes
| predictable if analyzed deeply enough. Another word for
| that is entropy. That is what my linked comment referred
| to. For security concerns, such as PRNGs, the appearance
| of randomness is not enough.
|
| This is why security analysis requires a higher threshold
| than software employment at large.
| maxbond wrote:
| > Ultimately everything eventually becomes predictable if
| analyzed deeply enough.
|
| How would this apply to hash algorithms, but not CSPRNGs?
| kbolino wrote:
| A hash function cannot _create_ entropy. Let 's be clear
| about that.
|
| A good hash function will _preserve_ entropy, up to the
| length of its output. If the input X has K bits of
| entropy and H is an N-bit cryptographic hash function,
| then the entropy of H(X) is min(K, N). In simpler terms,
| GIGO.
|
| However, a hash function also _scrambles_ its input,
| which means the output is _indistinguishable_ from
| (uniform) random noise. This is the randomizing property
| I was talking about. It is _good enough_ for hash
| functions to be used to build stronger primitives, like
| HMACs, PBKDFs, CSPRNGs, etc. There are many
| formalizations of this property, but one of the simplest
| is that given any K bits of the output, you cannot
| predict the other N-K output bits any better than
| guessing, even knowing the algorithm.
|
| Of course, if you know the input to a hash function, you
| can predict the output perfectly. But if you don't know
| the input, the hash _looks like_ random noise, and for
| cryptographic hash functions, this is a very strong and
| fundamental guarantee indeed.
| austin-cheney wrote:
| I agree that hash functions do not create entropy. That
| is what I have been saying all along.
| jadamson wrote:
| > There is an untested assumption that hashes achieve
| randomness because they appear to be a random collection of
| characters.
|
| lol, no. Cryptographic hash functions are specifically
| designed to achieve this property.
|
| > Never in mathematics or logic
|
| Let's not get ahead of ourselves. Start with English - what
| does "pseudo" mean?
|
| > This can be described by equivocation, fallacy of
| composition, inductive fallacy, and more.
|
| For example, what is a pseudo-intellectual?
| austin-cheney wrote:
| > lol, no. Cryptographic hash functions are specifically
| designed to achieve this property.
|
| That completely ignores the definition of the word
| _random_.
|
| What I find most interesting about this thread of
| comments is that the article explains the failure of
| using hashes as a means of randomness and despite that
| failure people are eager to ignore what hashes are
| otherwise used for to invent oppositional arguments. it's
| weird.
| Tyyps wrote:
| I think you are mixing the function itself and it's output,
| if for a given input to the function the output is
| uniformly random, then this is a way to derive randomness.
| The fact that the function itself is deterministic tells
| you nothing about the distribution of it's output.
| GTP wrote:
| You started your comment with a correct distinction, but
| got the wrong conclusion. Asking if somthing is random is
| actually a question about the _process_ used to obtain
| some value and not the value itself. If I ask you if 42
| is a random number, can you actually answer? I can get
| that number with an intrinsically random process based on
| some quantum effect, or I can say it from the top of my
| head because I just read a very famous book. You can
| indeed use an hash function to extract randomness, but,
| to be precise, we are talking about pseudo-randomness.
| The crucial difference here is that, if I 'm measuring
| photons' polarization to get a random number, then an
| attacker repeating the same process will (very likely)
| obtain a different number. If I'm instead hashing some
| data, an attacker passing the same data through the same
| hash function will get the same result. Another example:
| if I hash the digits of pi, I will get a sequence that
| will pass statistical tests for randomness. But an
| attacker that knows how I am generating such sequence can
| easily reproduce it.
| baby wrote:
| You realize all signatures in use today basically use hash
| functions as randomness
| austin-cheney wrote:
| That is wrong. Most digital signatures in use today use
| certificates trusted through a certificate trust chain. The
| algorithms are different.
| jcalvinowens wrote:
| It's not wrong. The only thing preventing me from forging
| your certificate is my inability to generate a new cert
| which hashes to the same digest as what is in your cert's
| signature. I don't actually need the keys if I break the
| hash.
|
| EDIT2: I'm doing a bad job of explaining this... you
| obviously need the keypair associated with the cert to
| initiate connections with it and not trigger MITM alerts.
| But if you break the hash function, you don't need the
| private key from the root cert, the verbatim signature from
| the original cert will appear to be valid when spliced into
| your forged cert if the hash digest computation on the
| forged cert is the same.
| GTP wrote:
| And checking the validity of a certificate involves
| checking a signature of... The certificate's hash. If you
| can break the underlying hash function, then the trust
| chain is broken.
| less_less wrote:
| Internally, most signature algorithms use hash functions.
| RSA-PSS, EdDSA and ML-DSA use them to provide something
| like randomness, and the security analysis of those
| signature schemes includes arguments assuming (in some very
| particular, technical ways) that the hash function outputs
| "look random".
|
| Classical DSA and ECDSA do not use hash functions this way,
| but in my opinion they aren't stronger for it: they're
| basically assuming instead that some other mathematical
| function "looks random", which seems riskier than assuming
| that about a hash function. I've heard that the reason for
| this is to get around Schnorr's patent on doing it with
| hash functions, which has since expired.
|
| The SHA3 and SHAKE hash functions (underlying e.g. ML-DSA)
| are explicitly designed to "look random" as well.
|
| There are some signature schemes that try not to make such
| strong assumptions: in particular SLH-DSA targets
| properties more like first- and second-preimage resistance,
| target-collision-resistance, and so on.
| austin-cheney wrote:
| All the algorithms you mention are PKI. RSA uses two
| large prime numbers. I don't see what hash sequences have
| to do with this at all.
|
| PKI isn't even really about randomness. RSA does use a
| kind of randomness to generate its large primes, but that
| is beneficial and not required. The primary consideration
| is the math to reverse guess a factor of two primes or
| the square root of a large number, or something else
| computers currently find cheap to compute in one way but
| extremely expensive to reverse.
| kurikuri wrote:
| What? You've managed to mangle so many terms in so few
| words... Signatures can refer to two things: integrity checks
| on a file or authentication checks for a recieved file. In
| the integrity check situation a hash function (e.g., SHA) is
| often used. In the authentication check situation, we usually
| use a public/private keypair for asymmetric encryption; the
| hash function is only part of the process. The key material
| used to make this keypair (should) comes from some random
| number generator...
|
| The 'hash' function is a deterministic transform, not a
| source of randomness.
| Tyyps wrote:
| He is technically not wrong, most signatures can be seen
| has a public coin interactive proof system where you prove
| knowledge of a private key. They are then compiled into an
| non-interactive proof system via the Fiat-Shamir transform
| that uses a random oracle concretely instantiated using a
| hash function (easy to see in Schnorr signature). So at the
| end you are using a Hash function to generate your random
| coin.
| Ar-Curunir wrote:
| 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.
| vlovich123 wrote:
| 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.
| karel-3d wrote:
| I find the actual paper more readable and understandable than
| this summarization.
|
| https://eprint.iacr.org/2025/118
| soulofmischief wrote:
| 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.
| some_furry wrote:
| > 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 wrote:
| (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 wrote:
| They do at least link to that in the 4th paragraph of the
| article. Many of these summary articles don't do that.
| baby wrote:
| I recommend this whiteboard session as well o.o
| https://blog.zksecurity.xyz/posts/pudding3/
| lxgr wrote:
| 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.
| catfacts wrote:
| I 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 wrote:
| 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.
| doodlebugging wrote:
| >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 wrote:
| Why would they not simply, assign 10 problems?
| pas wrote:
| presumably 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 wrote:
| Presumably 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 wrote:
| There 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.
| deadbabe wrote:
| Maybe professors should flip the script, instead of testing
| a student, have the student convince the professor they
| know the material. You will not pass until the professor
| feels confident.
| doodlebugging wrote:
| Sounds a dissertation format maybe.
| tossandthrow wrote:
| Now calculate the probability that the professor _at random_
| selects the exact 10 problems that were solved correctly.
|
| Your Eureka moment seems to be misinformed - I hope you can
| have it returned for another occasion.
| doodlebugging wrote:
| It's just a random decaffeinated thought here this morning.
| Considering that it must be true that even a blind squirrel
| gets a nut once in a while it is also likely to be true that
| a professor at random can select the exact 10 problems that
| were solved correctly.
|
| There's a difference between something with a probability of
| being true and another thing that is proven to be true. There
| are no doubts remaining after the proof whereas the
| probability always leaves wiggle room even if that wiggle
| room is a pretty tight space.
| tossandthrow wrote:
| We should be careful about using probable and possible
| interchangeable.
|
| You are right - it is _possible_ that is happens but not
| _probable_.
|
| However, overly focusing on this really deprives you of a
| lot of great intellectual stimuli from randomized
| algorithms and, like here, a large chunk of cryptography.
| doodlebugging wrote:
| >However, overly focusing on this really deprives you of
| a lot of great intellectual stimuli from randomized
| algorithms and, like here, a large chunk of cryptography.
|
| I agree with your first points about using probable and
| possible carefully. I originally posted a bit of a tongue
| in cheek, carefully selected example, from the full text
| of the article since that example fit the point that I
| hoped to make in jest. It was my carefully selected
| random example.
|
| I think the focus of the article is on demonstrating that
| a tool used in cryptography to verify truth was widely
| assumed to be infallible and it turns out that is
| unfortunately not true since it can be manipulated to
| identify false results as true. This tool uses
| probabilities as a tool to minimize compute times that
| would be enormous if one had to verify absolutes so it is
| an important tool. Now that it is demonstrated that it
| can be successfully attacked, the basis of the system of
| verification is vulnerable and in the case of Ethereum at
| least, monetary losses can result.
| pas wrote:
| they were shit all along, but the energy (and productivity)
| surplus allowed for decades of amazing growth, which created
| the feeling of prosperity
|
| unfortunately most people doesn't understand (and as a
| consequence doesn't appreciate) how little wealth we have
| compared to capacity, in other words how much upkeep we do to
| maintain that wealth
|
| and now that it's time to scale back the waste a bit people are
| up in arms
| doodlebugging wrote:
| As the caffeine sweeps through my system activating latent
| stores of energy and powers of analysis, I find that I
| appreciate this response without needing to understand all of
| it. It's a bit like assuming that the remaining 90/100
| answers are correct after only verifying 10 of them.
|
| I feel like I have accomplished more than I actually have and
| so I have plenty of incentive now to sweep through all the
| work of the day hoping that each randomly selected set of
| results yields similar levels of perfection and that all the
| inaccurate answers assumed to be correct do not cause the
| student to make assumptions in later life about things that
| are not supportable by facts.
| t_mann wrote:
| If the questions are randomly chosen, the probability of the
| true score being 10/100 in that scenario is 10!/(100!/90!) ~
| 6e-14
| doodlebugging wrote:
| I'll accept your math this morning with the note that without
| checking the other 90/100 answers you have no way outside of
| accepting probabilities to know whether your random examples
| are representative of the quality of the full set. It becomes
| a "trust me bro" situation.
|
| I processed hundreds of thousands of miles of seismic data in
| my career. The first thing we needed to do for any processing
| project was to select a subset of the data for use in
| defining the parameters that would be used to process the
| full volume of data. We used brute stacks - a preliminary
| output in the process - to locate interesting areas with
| complex attributes to make sure we could handle the volume's
| complexities. In industry slang these were "carefully
| selected random examples".
|
| It was inevitable that we would find a situation during the
| processing for which our parameters were not optimized
| because we had missed that edge case in selecting the
| examples used for testing.
|
| In the same way in real life if you only demonstrably know
| that 10% of the test answers are correct then it is also true
| that some edge case in the 90% of untested answers could
| leave all or part of that untested space false or sub-
| optimum.
|
| If there was a point to my original post it is this. You only
| know something is true when you have proven it to be true. A
| maximum likelihood of truth is not a guarantee of truth it is
| only a guarantee that it is likely to be true. You won't know
| how sharp the sting will be until you peel the onion.
| t_mann wrote:
| Having checked an answer also doesn't guarantee anything
| with certainty. Which, coincidentally, is the actual topic
| of the OP, the grading was just a tangential example and
| not a description of something actually happening anywhere
| in practice. But sticking with the grading example, the
| failure modes could be much more benign, such as the
| examiner failing to spot a mistake, or the answer being
| copied,...
|
| Probabilities aren't a matter of faith, they're mathematics
| and as such represent a logical trueism. Your critiques are
| just nitpicking for the sake of it and void of substance.
| Have a coffee and leave this topic.
| doodlebugging wrote:
| >they're mathematics and as such represent a logical
| trueism
|
| I'm a full pot in now and find that I agree with this.
|
| The fact is though that the article demonstrates that
| something previously considered logically true or a
| maximum likelihood was proven false.
|
| It's great to see that there are people, whether they're
| mathematicians or cryptographers, who will take a look at
| something that has been a useful part of a stable process
| of verification and try to find cracks or instabilities.
| The fact that they found an edge case that could be
| exploitable undermines trust in an important part of the
| process.
|
| Trust - but verify, wins again. Logically, this is the
| best way.
| metaesn wrote:
| What 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 wrote:
| this is a lie
| nicman23 wrote:
| source?
| metaesn wrote:
| Please understand the restrictions of Newton's Laws of
| Motion, many years ago, some people think they are right in
| every environments. My point here is it is difficult to get
| the truth for somethings. the title means proving everythings
| whether they are lies.
| zsoltkacsandi wrote:
| > 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 wrote:
| You 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 wrote:
| > 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.
| monkeyelite wrote:
| I think this is a good example of a lie because you and your
| son both have a shared understanding of the world and he is
| deliberately saying something he does not believe to be true
| (that does not match his own internal recall of events).
|
| There is a physical component to this lie but it seems to me
| that the social part dominates.
| lilerjee wrote:
| Yes, They have the same understanding of the meanings of
| the words "I", "was", "not" and "there", and the sentence.
| blueprint wrote:
| Your question is very simple to solve for someone who has done
| enough real philosophy lol :) a lie is when you tell something
| differently than it is. the truth means "what exists as it is".
|
| If you say that "it is difficult to find the truth", aside from
| the blatant subjectivity of your claim, then , if we believe
| your statement, then that itself must be a "truth". And yet you
| invalidate your own claim immediately by saying "different for
| different persons". Well, if that statement is true, then it
| invalidates itself as well.
|
| You cannot disprove the existence of truth by using a system
| that relies on truth and falsehood.
| metaesn wrote:
| You seem to have some misunderstandings about truth. Many
| truths are our understanding of real existence, not existence
| itself. Obviously, our understanding of complex things may be
| different, but complex things do exist.
|
| For example, the movement of things exists, but Newton's
| understanding of this existence is different from Einstein's
| understanding of the same existence (or the movement of more
| things).
| sesm wrote:
| There is a famous "4 theories of truth" classification:
| Correspondence, Coherence, Consensus and Pragmatic.
|
| In this case they are talking about mathematical truth, which
| is a case of Coherence truth.
| metaesn wrote:
| For mathematical truth, there is an example, please search
| "The Limitations of Euclidean Geometry"
| JanisErdmanis wrote:
| Can you recommend a book that expands on this classification?
| sesm wrote:
| I'm not aware of any book about this, but I've read it in
| several blog posts, like this one:
| https://commoncog.com/four-theories-of-truth/
| bawolff wrote:
| In context, these terms have specific definitions where this is
| not an issue.
| PretzelPirate wrote:
| > 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 wrote:
| 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.
| PretzelPirate wrote:
| That'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 wrote:
| 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
| bluGill wrote:
| My 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 wrote:
| Here's a whiteboard session going over that but
| https://blog.zksecurity.xyz/posts/pudding3/
| GTP wrote:
| The 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 wrote:
| 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.
| ShroudedNight wrote:
| What 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 wrote:
| By "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
| yorwba wrote:
| The attack does not require a fixed point of the hash
| function to be integrated into the program, it merely
| involves an _implementation_ of the hash function included
| in the program, being fed the exact same input as the hash
| function used as part of the protocol. This is possible
| because the input is entirely attacker-controlled, so it 's
| easy to duplicate some values as necessary.
| GTP wrote:
| I understand that this is the claim being made, but I think
| I'm still missing what is the attack's heart. From the
| article, it seems to boil down to "if you use a malicious
| program, then Fiat-Shamir is broken". But to me it seems more
| like that Fiat-Shamir would still give a correct proof of the
| program's output, it's just that the output itself was wrong
| from the start (I'm referring to the point in the article
| where they say such a malicious program behaves differently
| than intended when it detects its own hash being used). Is
| this attack actually letting you generate a valid proof for
| an output that the program doesn't generate under the given
| input?
| less_less wrote:
| As I understand the paper, the point is that Fiat-Shamir
| does *not* give a correct proof of the program's output.
|
| They gave a (maliciously constructed) program whose outputs
| are pairs (a,b) where certainly a != b (instead the program
| is constructed such that a = b+1 always). But you can get
| the corresponding Fiat-Shamir protocol to accept the
| statement "I know a secret x such that Program(x) = (0,0)",
| which is clearly a false statement.
| nyrikki wrote:
| I haven't done a real review yet, but skimming it seems to
| relate to Arthur-Merlin[0] oracles and public fair coins.
|
| If you view random numbers as normal numbers, they will
| seem to be algorithmically random, or at least exceed the
| complexity of any proof, or even practical proof.
|
| Basically the work of Chatlin, where given the kolmogorov
| complexity of your verifier, you only have a limited number
| of bits in any L that you can prove anything.
|
| Probably simpler to think about the challenges of proving a
| fair coins is fair.
|
| They just have to produce an unfair coin that looks fair as
| a flawed analogy.
|
| Fiat-Shamir depends on interactive proofs, which equals
| PSPACE, which seems huge, but it can be a hay in the
| haystack, and if you are using a magnet to reach into the
| haystack you will almost never pull out a piece of hay.
|
| They are basically choosing the magnet for you.
|
| [0] https://complexityzoo.net/Complexity_Zoo:A#am
| quantumgarbage wrote:
| The protocol is in charge of producing the proof. Fiat
| Shamir is a heuristic, some kind of rule of thumb, which
| consists in using a hash function as a source of
| randomness.
|
| Cryptographic protocols often feature coin tosses. The idea
| is that if we replace a hash function in place of the
| protocol coin tosses, it should still be hard for a
| malicious prover to craft a false statement with an
| accepting proof - making the protocol unsound.
|
| Roughly, the meat of the attack consists in baking in the
| statement being proven the ability for the prover to
| predict upfront how the hash function is going to behave -
| hereby breaking the Fiat Shamir heuristic and making the
| prover able to craft a false statement with an accepting
| proof.
|
| That's it, this is "How to Prove False Statements"!
| GTP wrote:
| Yes, I happened to study how the Fiat-Shamir transform
| works a couple years ago, but I only saw it in the
| context of using it to transform an interactive zero
| knowledge proof into a digital signature scheme.
|
| So, if the prover can know beforehand how an hash
| function behaves, wouldn't this make it a more general
| attack on hash functions (so potentially even worse than
| how it is presented in the article) and the Fiat-Shamir
| transform is only broken as a consequence of it relying
| on an hash function? If not, why?
| _alternator_ wrote:
| 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.
| Groxx wrote:
| It seems to be pretty explicit that the "program" being run
| contains the full hashing algorithm used (to output the
| correct answers most of the time) _plus_ additional logic to
| allow cheating.
|
| That rather clearly goes _wildly_ beyond what most ZK schemes
| use. That 's arbitrary code execution of your choice, either
| as input or as part of selecting the program. Which seems
| like it puts this somewhere near "if you allow `eval` on user
| input in your script, it could do anything", doesn't it?
|
| Plus like. They fixed it. That seems to imply it's more of an
| implementation flaw than a fundamental, even if it may be a
| surprisingly achievable one.
| _alternator_ wrote:
| So the proofs I'm most familiar with embed programs as
| polynomials over finite fields. Input data also corresponds
| to choosing some coefficients, and if you can choose enough
| coefficients (enough to embed the hash function) then the
| attack may be feasible.
|
| The problem is compounded because the hash functions are
| typically chosen to have extremely short polynomial
| representations.
| GTP wrote:
| So, in the end, what is the core concept of the attack? Were
| they able to generate a program (maybe exloit the fuzzyness
| of the distinction between data and program to generate a
| program) that contains the hash of itself? I doubt that this
| is it, as if this were the case, then it would be likely to
| be an issue with a specific hash function and not a general
| issue. Unless they are using some trick like the one I
| presented above, but then it seems to me that the problem
| wouldn't be with Fiat-Shamir itself.
| trod1234 wrote:
| My read of this is:
|
| There were parts of the process that check whether its a
| valid proof, which were previously thought to be
| equivalent, which were in fact not the case. Computer
| scientists involved knew of cases where this was not the
| case but moved ahead anyway because no one would design the
| systems in the ways the attacks would work.
|
| Attacks only get better.
|
| The original process included the original hash in such
| systems inputs, but also allowed additional malicious
| features which could be included to rearrange the output in
| a way that passes the proof scheme checks despite it being
| incorrect.
|
| By placing a constraint on input entropy they believe
| they've mitigated the issue, but it also breaks many
| applications; with no good alternative.
|
| Imo, This is a weak assertion considering finite fields are
| used. The title is really misleading.
|
| It should be "Fiat Shamir is broken"; Practical attacks.
|
| These are finite fields so the token output generated
| doesn't necessarily correspond to the specific path taken.
|
| There may be an infinite many paths, and computation has
| classical problems of computer science with being able to
| automatically derive decidable paths from tokens given;
| potentially leading to the same issues of discovering
| simple breaks.
| Sniffnoy wrote:
| 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.
| EGreg wrote:
| The key to why this even works (and didn't work before) is here:
| 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).
___________________________________________________________________
(page generated 2025-07-10 23:00 UTC)