What do y'all think of the Random Oracle Model?
@wolf480pl What's a random oracle model?
@coded_artist it's not a, it's the.
The Random Oracle Model is a way of thinking about cryptographic hash functions.
It says that for each hash function H, you can imagine a global oracle. And every time you calculate H(x), it's as if you sent x to the oracle and asked for a result. And if this is the first time in the universe that anyone asked the oracle about x, it will give you a fresh random number y, and note down that H(x) = y.
1/
@coded_artist and if anyone else asks it again for the hash of the same x, the oracle will look up its previous answer and return the same y.
And anyone who hasn't sent the exact vakue of x to the oracle can't learn anything about H(x), even if he can ask about hashes of different values, oossibly related to x.
A lot of cryptographic schemes can be proven secure if you assume Random Oracle Model, but not if you only assume hashes are collision-resistant.
2/
@coded_artist
The problem is that Random Oracles don't exist in reality.
And recently there have been papers that shown that if you replace the Random Oracle with any locally computable function, some cryotographic schemes break down, and are provably insecure even though their version with Random Oracles was proven secure.
@coded_artist And the problem with collision-resistant functions is that they don't tell you anything about the output of a hash function.
For example, if you want to use hash output as an encryption key - as many real-life schemes do - you need to know that it's "random-looking".
Collision-resistance doesn't guarantee that. But in practice, we believe the outout of SHA-256, etc. is quite "random-looking", we just need a definition of what that means.
@wolf480pl I see.
So it's an idealized, and one to one, hash function.
When your field is security, making assumptions about your system being secure is the worst possible thing you could do.
I cast my vote on BS.
Collisions avoidance is the best we have, and it's something that needs to be accounted for.
Cryptography isn't an 11th grade physics problem, you can't just ignore reality and expect to get the grade.
Thanks for the explanation.
@coded_artist but we don't know that our hash functions are cillision-resistant - that is also an assumption.
All proofs ha e some assumptions -and that includes security proofs in cryptography. Nobody can prove TLS is secure. But they can prove that eg. any successful attack on TLS must've broken either AES, SHA256, ECDSA, or ECDH.
@wolf480pl
True, but some assumptions are reasonable to make, such as "reality is not a simulation", while others are not, such as "my system is perfect, actually ☝️🤓".
@coded_artist how is eg. "chacha20 allows you to turn 256 bit of randomness into an infinite amount of pseudorandom bits that noone will be able to differentiate from actual random bits with probability greater than 2^-256" not a "my system is perfect" type of assumption?
@wolf480pl Entirely depends on your use-case, and I don't have enough knowledge in this field to make the call.
In the end of the day, due to the limitations of digital computations, it's all approximations, and you have to make the call if the approximation will suffice.
If you assume perfection, you're skipping this step, and invite disaster.
Like you said: "no one will be able to differentiate from actual random bits", is a decision to accept the approximation as good enough, and that may be a good call to make (depends on use-case of course).
An example from my field of simulations:
Is "float" a good enough data type to differentiate two points in space?
Sure... as long as you don't position anything 10k units away from the origin, where floating point precision issues arise.
Then if later someone demonstrates that a particular cipher in question does not meet the definition, i.e. shows an attack, the cryptographers agree that that cipher is not secure, and everyone should switch to a better one.
2/2
@wolf480pl Yeah, that's all of technology basically.
Even asbestos and leaded fuel were good enough, until they weren't.
Even deeper than that, it's on the level of the abstract.
What is a good idea?
One that works.
But what if it stops working some time in the future?
Well, we don't know that, so a good idea is one that works... for now.
That's why prototyping is all about "fail faster".
@coded_artist right, but my point is, it's not like floats where you can have an exact mathematical description of their flaws and limitations.
And the problem with hash functions is that it's hard to express what it is that makes them useful in something like HMAC or HKDF. Collision resistance is not enough for that to work.
"Random Oracle Model" is the first, most naive attempt at formalizing it.
I guess my question is, should we give up in our search for something better?
@wolf480pl Yeah, all of this is a "we don't know what we don't know" sort of situation.
And for the same reason, we always search for something better.
@coded_artist no, that's not how this works.
The way this works is a bunch of cryptographers agree that "no one will be able to differentiate from actual random bits" is a good goal for a stream cipher primitive to try to meet, a.k.a. a definition of what it means for a stream cipher to be secure.
Then they build more complex schemes on top of that building block, and prove that if the cipher used meets the security definition, then the whole scheme is secure.
1/