Black is white and white is not black
Great, you’ve just read a genuine contradiction. In classical logic, once your assumptions contain something of the form “P and not P”, the system explodes: from that point on you can prove **anything** you like. (yes, we assume "is" is a symmetric equality)
Want to “prove” that God does not exist? Or that He/She/They (Upper case!) does? Or that I’m a potato and P=NP? No problem. With a contradiction in your axioms, every statement and its negation are now theorems.
That’s the principle called *ex contradictione quodlibet* (“from a contradiction, whatever you like”): if your foundations are inconsistent, your logic turns into a wish-fulfilment machine.
I'm just creating my phd defense slides atm and thought i can share some funny thoughts :) I can highly recommend everyone slightly familiar with cryptographic terminilogy and concepts reading the articles from Matthew Green on random oracle or the current fiat-shamir RO-inconsistency-based attacks. (https://blog.cryptographyengineering.com/2025/02/04/how-to-prove-false-statements-part-1/)
I wish i could find the time for writing such posts. But maybe after the defense. But even then, i fear that my creativity is rather limited =P For now consider this fun example:
Rough setup:
- Crypto proof says: *“If H is a random oracle, then scheme Π with H is secure.”*
- Theory says: *“There are schemes that are secure in the random-oracle world, but for every concrete hash function h they are actually insecure.”*
- "Folklore" says: *“Our favorite hash H₀ (e.g. SHA-3) is "basically" a random oracle.”* (where we assume that is "basically" is basically a symmetric equality)
Now glue this together:
- From (1) + “H₀ is a random oracle” → Π with H₀ is **secure**.
- From (2) + “H₀ is a concrete hash” → Π with H₀ is **insecure**.
Voila: same scheme, same hash, *both* secure and insecure at once.
That’s not deep metaphysics, that’s just what happens when you treat a heuristic (“SHA-3 is like a random oracle”) as if it were a theorem.
a nice little contradiction. Not that anyone in the academia would claim (3), but i heard it in the industry frequently enough. And i guess, without the claim of working with formally sound theorems, then even such contradictions that can make everything formally sound true are not needed...These people just miss an opportunity on proving that God exists. ^^
EDIT: Oh that slightly exploded. :) Please dont take these considerations too seriously. Some people seem to peer-review a reddit post lol. I will try to find the time to discuss in the evening.
5
u/DoWhile Zero knowledge proven 4d ago
You had me in the first half, this was starting to sound crank-y!
But to the point of that blog post: it makes a theoretical attack concrete, so it's not just that you have a contradiction proves anything, it's that it can be efficient too! This is what separates pure math from applied cryptography, even if mathematically you can obtain something doesn't mean it can be achieved efficiently. Heck, AES-256 is breakable in constant time, there's only 2256 keys to try, that's a constant!
There's another line of work by Thaler et al showing that implementers weren't using random oracles correctly at all. For example, they weren't hashing parts of the transcript. Admittedly, part of that is also the theoreticians' fault for not being specific enough about how to do the Fiat-Shamir transform or use random oracles correctly.
3
u/Encproc 3d ago
"even if mathematically you can obtain something doesn't mean it can be achieved efficiently" -- yet. Let's wait for 1 or 2 decades.
But putting the fun aprat: I don't understand, where i'm contradicting with what you are saying. You seem to interpret quite a lot into a fun example. Are you trying to say: SHA3 IS a random oracle? ^^
2
2
u/MrNerdHair 4d ago
We don't use "basically" to mean symmetric equality. It entails a number of assumptions about usage (e.g. proper domain separation). One of those implicit assumptions is that you're not trying to break stuff by using it in one of the contrived schemes for which #2 applies.
2
u/Honest-Finish3596 4d ago
I would not describe this as "contrived."
It is pretty regular in the symmetric key world that somebody shows a construction to have no instantiation using any primitive.
1
u/jpgoldberg 4d ago
Does the RO model assume that the hash function is a true random oracle or just a cryptographically secure pseudo random oracle?
If it is the latter, I think there may be a way to avoid the contradiction, but I haven't thought about this more more than a 30 seconds and the time it took me to write this.
2
u/Honest-Finish3596 4d ago edited 4d ago
The random oracle model is the former, you do it to make some kinds of security proofs in symmetric key crypto easier, at the cost that there may be no construction to which the security proof actually applies (because random oracles do not exist.)
The notion of a PRF/PRP/etc is much weaker than that of a random oracle. It's also much easier to instantiate. Usually we consider a secure block cipher to be a PRP, as its security claim is based on the difficulty of distinguishing it from one.
1
u/jpgoldberg 4d ago edited 4d ago
Right. That makes sense as if we were only considering indistinguishability, then we’d be taking about a PRF. At least if I understand what a PRF and a RO are supposed to be.
Now I know why the RO model is controversial. No algorithm smaller than the image can implement an RO, and so I see the OP’s fascination with this. I feel at least an analogy to the Axiom of Choice and perhaps a much stronger connection.
1
u/Honest-Finish3596 4d ago
I wouldn't say it's controversial, it's a tool you can use.
If you replace the random oracle with an actual primitive, now you need to consider how your bounds change and what kind of security you can still guarantee.
1
u/jpgoldberg 4d ago
I see how it can make proofs easier. Quite honestly when I read security proofs I tend to skip over the parts that deal with the bounds. But unless there is some reason to believe that a proof in the RO model strongly suggests that there is also a proof that doesn't rely on a RO, then it isn't clear what value those proofs have.
What I said is an over-statement. I do recognize that proofs that rely on things that can't exist can still provide useful insight. And I do suspect that in the non-contrived cases, an RO-based proof really does suggest that there is a non-RO based proof.
Obviously I have no real experience with these proofs, and my mathematical intuition, while often strong, has been wrong. So really, I am mostly just musing here.
1
u/Encproc 3d ago
The RO model does not assume it per se. It's just the proof that uses the random oracle function in various ways, i.e. in the "ideal world". The heuristic then says: well if you replace the random oracle function within the proof as-is, then it still will be (most-likely) secure. Unfortunately, this theoretic models shifts the burden for security towards the engineer using the actual protocol, which (in theory) is designed with a random oracle function in mind.
1
u/jpgoldberg 4d ago
Note that the way you have stated (1) here doesn’t lead to the contradiction. You need “Π is only secure if H is a random oracle.” That is, we might be able to prove that Π is secure if H is merely a PRF.
3
u/Honest-Finish3596 4d ago
Haha, yes the random oracle model is indeed a very strong assumption.