Comment by GTP
4 days ago
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?
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.
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?
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.
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
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“!
2 replies →
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?
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
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.
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.
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.
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.
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.
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.