[remark] Misusing random oracles for practical purposes

by Ciprian Dorin Craciun (https://volution.ro/ciprian) on 

Experimenting with various real-world instantiations of cryptographic random oracles, with applicability from multi-factor encryption, to database record encryption.

// permanent-link // Lobsters // HackerNews // index // RSS

Why this article? Because I believe that cryptographic "random oracles" are such a wonderful construct that should be known and used even outside the theoretical cryptography domain, where they are used mainly to prove the security of various cryptographic constructs "in the random oracle model".

(And because, as feedback to my article from yesterday about multi-factor encryption, I've received a few comments that stated I've made a mess of things, mixing "theoretical constructs such as oracles used in proofs" with real world encryption.)

What are cryptographic "random oracles"?

In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time that query is submitted.

Stated differently, a random oracle is a mathematical function chosen uniformly at random, that is, a function mapping each possible query to a (fixed) random response from its output domain.

[Wikipedia article on "Random oracle"]

Why are they important, and how are they used?

I strongly recommend reading Matthew Green's series on the topic:

[...] Even though everyone is allowed to compute the hash function, they can't do it by themselves. Hashing is done by a new magical party called the "oracle". If any party needs to hash something, they ship the message (over an imaginary secure channel) to the oracle, who computes the hash and sends it back to them.

[...] We'll place two restrictions on the random oracle. First, it must implement a genuine random function (sampled at the beginning of the game), with the same input/output profile as a realistic hash function we might use (e.g., 256-bit output strings if we're eventually going to implement with SHA256).

Secondly, the responses given by the oracle must be consistent. In other words, just as hashing Peter Piper through SHA1 will always produce 1c6244929dc8216f5c1024eebefb5cb73c378431, regardless of who does it, sending a given string through the random oracle will produce the same result, regardless of which party asks for it.

To summarize all of the above, a cryptographic random oracle has the following properties:

!!! WARNING !!!
I am not a cryptographer, or even a security expert!, at best I am a hobbyist applied-cryptography developer, thus take everything I say with a large grain of salt and lots of circumspection.

Before I go and describe how we can use them, I want to give a few examples of real-world instantiations of such oracles:

Once these "random oracles" have been demystified, and once we've seen that most real world instantiations are nothing more than implementations (or misusages) of existing cryptographic algorithms, we could ask ourselves why focusing on them beyond their purpose in theoretical cryptography?

Indeed, they are completely useless in practical terms (as opposed to just reusing their backing primitives), unless we take into account one key element: they are distinct entities, running outside our software, perhaps even on a remote machine or security enclave! Thus, just as many two-factor authentication mechanisms have nothing special in them, except the disconnect between them and the user's device.

Thus, we can think of such oracles as second factors that we could use in our cryptographic constructs. Ones which, if properly secured, might thwart at least brute-force attacks, or require the attacker a much wider foothold in the user's environment.

Where could we use them: for anything that accepts as input a password or shared key; for example we could use them to:

For example I use them as additional encryption factors in my own z-tokens project, as currently implemented in z-tokens/exchange/crypto.rs.

How can one actually use these?

Assuming an oracle is embodied as a function oracle (bytes) -> (bytes), and assuming we have a sequence of such functions in an array (oracles), we need to:

(Other constructs are possible, like for example allowing parallel execution, but I believe executing them serially yields the strongest security.)

Why do I use the derive function extensively?

What are the properties of such a construct:

!!! WARNING !!!
I am not a cryptographer, and I have not verified the algorithm above. I did ponder and developed this algorithm over the course of the last 5 months, and I do believe it doesn't hide anything nefarious. But I wouldn't trust this with important data before someone with experience takes a look!

In conclusion, I would have liked to discover this wonderful construct much earlier, especially since it's nothing magical about it, and also because it has many practical applications (like for example database record encryption, multi-factor encryption, etc.).

As always, any feedback (criticism or ideas alike) is welcome, and please get in touch with me as described in the feedback section.

As a bonus, here are a few open-source projects (which I haven't reviewed or endorse) that use the ssh-agent as such a random oracle: