Random Oracles and Other Idealized Models

A good hash function's outputs don't seem to follow any obvious pattern; distinct inputs produce unrelated-looking outputs. One might be tempted to describe these outputs as pseudorandom.

This chapter discusses why a conventional hash function cannot have pseudorandom outputs, but also why it can be useful to “pretend” otherwise.

12.1. Defining the random oracle model

Pseudorandom outputs for a hash function? Suppose $H$ is an unsalted hash function with $n$ output bits (the presence of salt doesn't change the conclusions in this section). How could we formalize the idea that $H$ has pseudorandom outputs? Perhaps we should use the same approach that we used for pseudorandom functions, and say that the following two libraries must be indistinguishable:

Unfortunately, these libraries can never be indistinguishable; no hash function can have pseudorandom outputs. Unlike a PRF, a conventional hash function has no secret inputs. As such, an adversary does not need the library's help to evaluate $H$. Consider the following trivial attack:

This calling program simply compares the library's return value to the output of $H$ that it can compute on its own. The two values always match in one library and match only with probability $1/2^n$ in the other, so the attack succeeds.

And yet, we pretend: Despite this unequivocal limitation of hash functions, cryptographers frequently prove things about hash functions with pseudorandom outputs.

An example: PRFs in the random oracle model: Let's gain some intuition about random oracles by considering the problem of constructing a PRF in the random oracle model. A PRF is meant to be indistinguishable from a lazy random dictionary. If a random oracle is a lazy random dictionary, then what is the point of constructing PRFs in the random oracle model?

A random oracle is unkeyed; it is meant to model a public random function that anyone can evaluate. A PRF is a keyed primitive; it is (indistinguishable from) a random function that only someone who knows the key can evaluate. Access to a PRF is mediated through its secret key. If a PRF construction wants to take advantage of a random oracle, it must access the random oracle in a way that makes nontrivial use of a key.

Thus, we formalize the random oracle model by taking the usual security definition and adding a lazy random dictionary $\ro$ to both libraries. As another example, security of encryption in the random oracle model is defined as follows:

Philosophy: The statistician George Box once said,

His quote applies well to the random oracle model:

• The random oracle model is a model, but all security proofs are with respect to some simplified model of real-world attack scenarios. A security proof can refer to libraries that model a realistic attack scenario or an absurd one.

• The random oracle model is demonstrably “wrong” as a model of reality. No real-world hash function can behave entirely like a random oracle, for the reasons discussed above. A security proof that models $H$ as a random oracle does not necessarily guarantee security in the standard model, when $H$ is merely a plain CRHF.

• Despite that, the random oracle model has proven useful. We know of many constructions in the random oracle model which are simpler/more efficient than our best constructions in the standard model. And many real-world constructions, whose security we do not know how to establish in the standard model, are “explained” by a security proof in the random oracle model.

12.2. Using random oracles

In this section we introduce some techniques and concepts used for security proofs in the random oracle model.

12.2.1. PRFs from random oracles

In section 10.4 we showed that $F(\key,X) = H(\key \| X)$ is not a secure variable-input-length PRF, if $H$ is an unsalted Merkle-Damgård hash. On the other hand, it is secure if $H$ is a random oracle.

This proof illustrates a common strategy for proofs in the random oracle model. The random oracle is called in two ways:

• The adversary can make direct calls to the random oracle through the library's $\ro$ interface.

• The construction also makes internal calls to the random oracle. The adversary may have some control over these calls, through its choice of inputs to the construction, but usually not full control. In the previous example, the adversary could choose inputs $X$ to the PRF, which would then call the random oracle on $\key \| X$, for a value $\key$ that the adversary did not know.

A standard strategy in a security proof is to show that no internal call is also made as a direct call (except with negligible probability).

12.2.2. CRHFs from random oracles

Random oracles are meant to model hash functions, so it is natural to ask whether a random oracle is collision-resistant. Section 10.1 went to great lengths to motivate the need for salt in a collision-resistant hash function. The purpose of salt was to introduce variability that is chosen after the adversary is fixed, that the adversary cannot predict. But the random oracle is already chosen after the adversary is fixed, so salt is not needed in the random oracle model.

12.3. ☆ The ideal permutation model

The random oracle model thinks of a deterministic object (a public hash function) as an inherently randomized one (a random oracle). We therefore say that a random oracle is an idealized object, where in this context “ideal” means “too good to be true.” No real-world hash function can literally be a random oracle.

We can use similar idealized objects to model other cryptographic primitives as well. In this section we introduce the ideal permutation model, and in the next section the ideal cipher model.

An ideal permutation is a public object; anyone can evaluate it in both directions. Below is a construction that uses an ideal permutation to build a keyed PRP, which can be evaluated only by someone who knows the key.

Both random oracles and PRFs involve lazy random dictionaries in their definition. But a bare random oracle is not a PRF, because a random oracle is public while a PRF should be computable only with its secret key. Similarly, both ideal permutations and PRPs are defined in terms of lazy random permutations, but a bare ideal permutation is not a PRP. Just as there are simple ways to build a PRF from a random oracle, there are also simple ways to build a PRP from an ideal permutation:

Key-alternating ciphers: The Even-Mansour construction is the second paradigm we've seen for building a PRP; the previous was the Feistel construction (construction 7.3.3). To build a PRP with the Feistel construction, you need a good PRF for the round function. To build a PRP with the Even-Mansour construction, you need a good public, unkeyed permutation.

The Even-Mansour construction is the simplest instance of a key-alternating cipher, in which we alternate between xor'ing the key and applying a fixed, public permutation:

You can consider the Even-Mansour security analysis as justification for the overall key alternation design methodology for PRPs.

Advanced Encryption Standard (AES) is the world's most widely used PRP/block cipher. It was standardized in 2001 as a replacement for DES, and is designed as a key-alternating cipher and alternates between xor'ing a key and applying a fixed, public permutation.

Admittedly, it is a bit of a stretch to characterize the Even-Mansour security proof as justification for the security of AES. Its “permutation” step would be a poor choice for an ideal permutation, since it has too much predictable structure. But what AES lacks in similarity to an ideal permutation, it makes up for with additional rounds.

12.3.1. Permutation-based cryptography and sponges

Symmetric-key cryptography in practice has traditionally been built on a foundation of PRPs (block ciphers). Starting with a secure PRP, we have standard constructions (many of them shown and proven secure in the previous chapters) of PRGs, variable-length PRFs, encryption, and more. The security of all these primitives rests on the security of the underlying PRP, and so the most effort has gone into designing, analyzing, and standardizing good PRPs.

However, a recent trend has been to base cryptographic primitives on unkeyed permutations, usually with large blocklengths (e.g., a recent standard has blocklength 1600 bits). Starting with such a permutation, there are standard constructions of PRGs, PRFs, hash functions, and other primitives, whose security is proven by modeling the permutation as an ideal one. Thus, the security of all these primitives relies on the how well this underlying permutation emulates an ideal permutation.

The hope of permutation-based cryptography is that it may be easier to design and acquire confidence in an unkeyed object like a permutation than in a keyed primitive like a PRP. Many candidate PRPs have been broken or had weaknesses demonstrated based on how they incorporate the key into their computation. Permutation-based cryptography avoids this possibility. The candidate permutation is unkeyed, so any constructions that use the permutation must incorporate a key in a provably secure manner.

The Sponge Methodology: The most common way to construct symmetric-key primitives from a public permutation is with the sponge methodology, whose name is inspired by the metaphor of a sponge absorbing input and squeezing output. When using an ideal permutation with blocklength $n$, a sponge function maintains an internal state of $n$ bits. The state is divided into a top part and bottom part, and we write the state as $T \| B$. Usually the bottom is $\secpar$ bits and the top is longer.

There are two basic operations in the sponge methodology:

• In an absorbing step, take the next block of input $X$ (with the same length as $T$) and update the current state as:

  $T' \| B' := \Pi^+\Bigl( (T \oplus X) \| B \Bigr).$

• In a squeezing step, append the current value of $T$ to the output and update the current state as:

  $T' \| B' := \Pi^+\bigl( T \| B \bigr).$

Using these steps, the basic sponge function works as follows: Starting from an all-zeros state, first absorb the entire input; then squeeze as much output as needed.

Thus, a sponge function supports inputs of any (block-aligned) length, and produces as much output as requested. For this reason, sponge functions are also called extensible output functions (XOFs).

A sponge function can be used to build all sorts of cryptographic primitives:

• PRG: Absorb the input seed and squeeze as much output as needed.

• PRF/MAC: Absorb the key and second PRF input $X$ (concatenated together) and squeeze an output.

• CRHF: Absorb the entire input and squeeze one output block.

It is even possible to directly construct CPA/CCA/AE encryption from a sponge function, by alternating between absorbing (to consume plaintext input) and squeezing (to generate ciphertext output). All of these simple constructions can be proven secure in the ideal permutation model (see exercises 12.11–12.13 for the simplest cases).

SHA-3: SHA-3 (Secure Hash Algorithm) is the most recent standardized hash function from the US National Institute of Standards & Technology. It is designed using the sponge methodology, centered around an underlying 1600-bit permutation called Keccak-$f$. The standard defines many variants, but the most basic version divides the 1600-bit block into a 1088-bit “top” part and 512-bit “bottom” part. Thus, hashing requires one call to the permutation for each 1088 bits of input.

12.4. ☆ The ideal cipher model

We can model block ciphers as idealized objects as well. In the security definition for a (strong) PRP, $F(\key,\cdot)$ and $F^{-1}(\key,\cdot)$ are indistinguishable from a random permutation and its inverse, when the key is chosen uniformly and kept secret. In the ideal cipher model, $F(\key,\cdot)$ and $F^{-1}(\key,\cdot)$ behave like an ideal permutation for every choice of $\key$. An ideal cipher is like a PRP that is somehow secure, even when the adversary chooses its key!

Collision-resistance from ideal ciphers: A collision-resistant hash function has no secrets, and this fact makes it hard to construct one from a keyed primitive like a PRF or PRP. However, there is a way to construct a CRHF from an ideal cipher.

Below is a method for constructing a fixed-input-length, collision-resistant hash function from an ideal cipher. Such a primitive can be extended to a variable-input-length CRHF using the Merkle-Damgård construction (construction 10.4.3). In this idealized model, salt is not required for collision resistance.

Exercises

1. Let $\ro$ be a hash function with $\secpar$-bit inputs, and define $F(\key,X) = \ro(\key \oplus X)$. Prove that $F$ is a secure PRF in the random oracle model.

2. Prove that a random oracle with $2\secpar$ output bits is a PRG. In other words, prove that $G(\seed) = \ro(\seed)$ is a secure PRG in the random oracle model.

3. Prove that the function $G(\seed) = \ro(\seed) \| \ro(\overline{\seed})$ is a secure PRG in the random oracle model, when $\ro$ is a random oracle with $\secpar$ input/output bits. “$\overline{\seed}$” is the bitwise complement of the string $\seed$.

4. Prove that the function $G(\seed) = \ro(\seed) \| \ro(\seed+1)$ is a secure PRG in the random oracle model, when $\ro$ is a random oracle with $\secpar$ input/output bits. “$\seed+1$” means addition mod $2^\secpar$.

5. Let $\ro$ be a random oracle with $\secpar$ input bits and $2\secpar$ output bits. Prove that the following function is a secure PRG.

   $\subname{G}(\seed)$:

   $X \| Y := \ro(\seed)$

   return $(X \oplus \seed) \| Y$

6. h In this problem you will construct an encryption scheme that is secure in the random oracle model but is insecure if the random oracle is replaced by any public function.

   1. Prove that the following two libraries are indistinguishable. In other words, it is hard to write a program that agrees with the random oracle, on a uniformly sampled input, when the random oracle has input and output length $\secpar$:

      $\lib{ro-predict-real}$

      $\subname{challenge}(P)$:

      $R \gets \bits^\secpar$

      $S := \mynull$

      interpreting $P$ as a Python program,

      run $P$ on input $R$ for $|P|$ clock cycles;

      if $P$ successfully terminates in that time:

      assign its output to $S$

      return $S == \ro(R)$

      $\ro(A)$:

      if $\rotable[A]$ undefined:

      $\rotable[A] \gets \bits^\secpar$

      return $\rotable[A]$

      $\indist$

      $\lib{ro-predict-ideal}$

      $\subname{challenge}(P)$:

      return $\myfalse$

      $\ro(A)$:

      if $\rotable[A]$ undefined:

      $\rotable[A] \gets \bits^\secpar$

      return $\rotable[A]$

      There is nothing particularly special about Python programs here; what's important is that the adversary provides a program that will terminate in a predictable (and polynomial) amount of time. Imagine the program is self-contained, and run in a virtual machine, so it has no mechanism by which to call the library's $\ro$ subroutine.

   2. Let $\Sigma$ be a CPA-secure encryption scheme that has $\secpar$-bit keys and supports arbitrary-length plaintexts. Prove that the following scheme is a CPA-secure encryption scheme if $\ro$ is modeled as a random oracle:

      $\Enc^*(\key,\ptxt)$:

      $\ctxt := \Sigma.\Enc(\key,\ptxt)$

      $R \gets \bits^\secpar$

      interpreting $\ptxt$ as a Python program,

      run $\ptxt$ on input $R$ for $|\ptxt|$ clock cycles

      if $\ptxt$ successfully terminates in that time

      ... and its output equals $\ro(R)$:

      $\ctxt' := \key$

      else:

      $\ctxt' \gets \bits^\secpar$

      return $\ctxt \| \ctxt'$

      $\Dec^*(\key,\ctxt\| \ctxt')$:

      // ignore final $\secpar$ bits

      return $\Sigma.\Dec(\key,\ctxt)$

   3. Show that if $\ro$ is implemented by any efficiently computable function, then the scheme is not CPA-secure.

   It's important that $R$ is chosen uniformly, after $P$ is chosen. Understand what would go wrong if $R$ was a fixed, public value, say, $R = \bit0^\secpar$.

7. Prove that the following function is collision-resistant in the random oracle model:

   $F( X_1 \| X_2) = \ro(\bit{0}\|X_1) \oplus \ro(\bit{1}\|X_2).$

   Assume that each $X_i$ has exactly $n$ bits. What would be your recommendation for a suitable output length of $\ro$?

8. The Even-Mansour cipher incorporates the key before and after the ideal permutation. Both of these steps are necessary.

   1. Show that $F(\key,X) = \Pi^+(X) \oplus \key$ is not a secure PRP if $\Pi^\pm$ is an ideal permutation.

   2. Show that $F(\key,X) = \Pi^+(X \oplus \key)$ is not a secure PRP if $\Pi^\pm$ is an ideal permutation.

9. Prove that the Even-Mansour cipher is a secure strong PRP (definition 7.5.1) in the ideal permutation model.

10. Suppose we construct a hash function $H(X)$ using the sponge methodology in the ideal permutation model: $H$ absorbs each block of $X$ and squeezes one block of output. Does $H$ have the same length-extension property of Merkle-Damgård hash functions? Explain your answer.

11. Let $\Pi^\pm$ be an ideal permutation with blocklength $2\secpar$. Prove that the following sponge function $G$ is a secure PRG:

    $G(\seed)$:

    $T_1 \| B_1 := \Pi^+( \seed \| \bit0^\secpar )$

    $T_2 \| B_2 := \Pi^+( T_1 \| B_1 )$

    return $T_1 \| T_2$

    Each of the variables $T_1, T_2, B_1, B_2, \seed$ is $\secpar$ bits long.

12. Let $\Pi^\pm$ be an ideal permutation with blocklength $2\secpar$, and define the following sponge function:

    $F(\key,X)$:

    $T_1 \| B_1 := \Pi^+( \key\| \bit0^\secpar )$

    $T_2 \| B_2 := \Pi^+\bigl( (T_1 \oplus X) \| B_1 \bigr)$

    return $T_2$

    Each of the variables $T_1, T_2, B_1, B_2, \key, X$ is $\secpar$ bits long.

    1. Prove that $F$ is a secure PRF.

    2. Show that if $F$ is modified to return all of $T_2\|B_2$, then the result is not a secure PRF.

13. h$\star$ Let $\Pi^\pm$ be an ideal permutation with blocklength $2\secpar$. Prove that the following sponge function is a secure variable-input-length PRF, for block-aligned inputs:

    $F(\key,X_1 \| \cdots \| X_\ell)$:

    $T \| B := \Pi^+( \key \| \bit0^\secpar )$

    for $i=1$ to $\ell$:

    $T \| B := \Pi^+\bigl( (T \oplus X_i) \| B \bigr)$

    return $T$

    Each of $\key, T, B, X_1, \ldots, X_\ell$ is $\secpar$ bits long.

    Keep track of the $B$-values seen during computations of $F$. Trigger a bad event if the adversary ever encounters one of these $B$-values in a direct call to $\Pi^\pm$.

14. Let $\Pi^\pm$ be an ideal permutation with blocklength $\secpar$. Prove that $H(X) = \Pi^+(X) \oplus X$ is collision-resistant.

15. Let $H$ be the Davies-Meyer compression function $H(X\|Y) = \ic^+(X,Y)\oplus Y$. Show how to efficiently compute an input $X\|Y$ such that $H(X\|Y) = Y$. Why doesn't this contradict collision-resistance?

16. Prove that the function $H(X\|Y) = \ic^+(X,Y) \oplus X \oplus Y$ is collision-resistant in the ideal cipher model.