Comment by GTP
4 days ago
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.