From Heuristic Hashes to the Random Oracle Model

A proof that a signature scheme is unforgeable usually proceeds by reduction: if an attacker forges, then a simulator uses that attacker to solve a hard problem. The reduction has to answer the attacker’s hash queries, and it has no hash function to answer them with. What it has is freedom to define the answer, provided the answers are consistent, uniformly distributed, and unrelated to anything else. That freedom is the random oracle model, and it is a proof technique whose relationship to deployed hash functions is weaker than its name suggests.

The oracle as a formal object

A random oracle is a function from arbitrary-length strings to a fixed-length range, chosen uniformly at random from all such functions, with the crucial property that it cannot be evaluated on a new point without querying a table that records every previous answer. In the model, both the honest algorithm and the attacker are given access to this table, and every evaluation costs a query.

Three consequences follow. First, the output on a new point is independent of all previous outputs, so the attacker learns nothing about it in advance. Second, a collision exists but finding one requires the birthday work, since the oracle is a random function. Third, the attacker cannot evaluate the function on points they have not queried, and the reduction can therefore see every point the attacker evaluated.

That last property is the one that does the work. In a proof, the reduction plants challenge values as answers to specific queries and later learns which query the attacker used them from. The technique is impossible with a real hash, where the solver cannot invert or monitor anything.

A related idealisation is the ideal cipher, a random keyed permutation with an inverse. The ideal cipher is what a proof about a block cipher assumes, and it is used in analyses of modes of operation. The two models are not interchangeable and a scheme proved in one is not automatically secure in the other, though arguments exist for translating between them in specific cases.

A reduction, traced

Take the standard use of a hash in a signature scheme. To sign m, compute H(m), apply the private key operation to the digest, and publish. To verify, recompute H(m) and check the public operation.

A reduction against the RSA assumption plants a challenge y and hopes the attacker’s forgery produces a hash value whose preimage under the private operation is y. In the random oracle model the reduction answers the attacker’s hash query on m* by programming the oracle to return y^e mod N, which it can compute with the public key. The attacker signs m* without noticing, and if the scheme’s structure lets the reduction recover y from the signature, the RSA problem is solved.

The proof works because the oracle could be programmed after the query, an operation with no analogue for a real hash. With SHA-256, the reduction cannot force H(m*) to be a particular value without first finding a preimage of it, which is the hard problem it was trying to solve.

reduction, random oracle model
  1. receive challenge y = x^e mod N
  2. on hash query m*:  answer H(m*) = y            [programming, impossible in reality]
  3. on other queries:  answer uniformly at random
  4. receive forgery (m*, s) with s^e = H(m*)
  5. output s, which satisfies s^e = y, solving for x

the same reduction with a real hash fails at step 2: an
implementation cannot set the output of SHA-256 to a chosen value

Two facts about that trace matter more than the mechanics. The programming step is used at most once in the simple version, and each use consumes one of the attacker’s queries, so the success probability of the proof carries a factor of the number of hash queries. A proof that loses a factor of q_h is still a proof, but it means the security claim degrades with the number of queries the attacker makes, which is a real property of the scheme and not an artifact.

And the reduction is tight only in the best cases. For RSA signatures the standard result loses another factor related to the size of the message space for a deterministic scheme, which is why full-domain hashing was replaced in practice by hashes with a random salt, the PSS construction, whose proof is tight. The choice between schemes with the same asymptotic security and different tightness is a decision about key sizes and signature lengths, and it is invisible unless the reduction is read.

From model to deployment

The model is a proof technique and an interface. As an interface it is a specification of what a hash must do: be indistinguishable from a random function for the inputs the scheme uses. The interface is what lets the analysis be modular, and it is why a scheme proved in the model can be described without naming a hash.

The modelling assumption is that SHA-256, SHA-3, and their peers behave enough like a random oracle for the proof to transfer. That assumption has no proof and cannot have one: a real hash is a fixed algorithm, so a statement that it is indistinguishable from a random function is either false for a specific distinguisher or an empirical claim about the absence of such distinguishers. FIPS 186-5, which specifies the signature schemes in use, states requirements on the hash rather than claiming oracle behaviour, and the gap between the two is the honest position.

The gap has been exploited in specific ways. Length extension is the clearest: a random oracle is not vulnerable to it, because a new point requires a new query and the attacker cannot derive the answer from a previous one. A scheme whose proof uses the oracle’s resistance to extension is therefore proved for an object that deployed SHA-256 does not instantiate, which is exactly the failure described in length extension and prefix-free encodings.

Joux multicollisions are the second. A random oracle has only the birthday collisions; an iterated hash has exponentially many once one compression-function collision is found, and a scheme that reasons about “the probability that two messages share a digest” is reasoning about the oracle rather than about the construction.

The separation results and what they mean

Canetti, Goldreich, and Halevi showed that the random oracle model is not sound in general: there exist signature schemes that are provably secure in the model and insecure under every instantiation by any real hash, provided the scheme is allowed to be constructed adversarially. The schemes are contrived, and no deployed scheme of that shape is known. The result is a statement about what the model can promise, not a prediction that a particular scheme will break.

The practical reading is layered. A proof in the model rules out every attack that works against the oracle, which is a large and well-understood class. It does not rule out attacks that exploit the specific structure of the instantiation, and those are exactly the attacks that have historically succeeded, against MD5, SHA-1, and against several schemes that named a hash the designers assumed was oracle-like.

The one construction that escapes the argument is not a hash but a different primitive: a scheme proved in the standard model, with no idealisation. Full-domain hash is a model-based construction. Signature schemes with proofs in the standard model exist, built on stronger assumptions than the bare RSA problem, and they are priced accordingly in key sizes, signature lengths, and message constraints. A scheme that needs no oracle is preferable where those constraints allow it.

Reading a hash-based proof

Four questions determine what a proof is worth.

Is the oracle used only for collision resistance, or for programming? A proof that uses the oracle as a random function for collision bounds is on firmer ground than one that programs outputs, because collision resistance is a property that a real hash can be tested for, while programming is not.

What is the loss? A reduction losing a factor of the hash query count turns an 80-bit problem into a 60-bit one at a million queries, which changes the required key size. Tightness is a cryptographic parameter, not a stylistic one.

Does the scheme use the hash in a way that exposes its iteration structure? If the proof requires the attacker cannot compute H(x || y) from H(x), the instantiation must be checked for length extension. If it requires that collisions are rare, the instantiation must be checked for multicollisions.

Is the idealisation over a hash or over a group? A proof that models the hash as a random oracle but leaves the group generic may be modelling the weaker object, and the choice of curve then matters as much as the choice of hash. The same question recurs wherever a hash is used inside a larger structure. When the structure is a tree, the proof assumes the tree’s encoding is injective, and the encoding is where the assumption is most often broken, as domain separation in Merkle trees sets out.