My question is: given the ability to sample a single bit at random, can't we use that to construct a random oracle? Suppose we want to simulate a random function $H:\{0,1\}^m \rightarrow \{0,1\}^n$. Just sample $n$ bits for the output, and keep a log so that all future queries are consistent.
Sure. You could design a signature scheme where there is a central party—a gnome sitting in a standard box flipping coins—and everyone on the planet has a telephone line directly to the gnome that cannot be intercepted so that everyone gets the same values from the gnome. That's not a particularly practical way to design a cryptosystem—we might like to be able to sign and verify messages offline, for example—but more importantly, it's not really what the random oracle model is about.
The random oracle model is not a just model for hash functions, but a model for adversaries. Let's take an example: in the signature game EUF-CMA—existential unforgeability under chosen-message attack—an adversary $A$ is by definition a random algorithm with access to a signing oracle and a public key: $A(S, \mathit{pk})$. The adversary wins if they can find any $(m, \sigma)$ pair that passes signature verification for any message $m$ they did not pass to the signing oracle $S$. This is sometimes called the ‘standard model’.
In the random oracle model, we consider a family of signature schemes indexed by a uniform random choice of function $H$. To make it clear that it depends on the hash function, we might label the signing oracle $S_H$. For example, in RSA-FDH signature, a public key is a large integer $n$ and a signature on a message $m$ is an integer $\sigma$ such that $$\sigma^3 \equiv H(m) \pmod n.$$ The signing oracle for a legitimate user is typically defined by $$S_H(m) := H(m)^d \pmod n,$$ where the secret exponent $d$ solves $3d \equiv 1 \pmod{\lambda(n)}$. Then, in the random oracle model, the adversary gets not just a signing oracle and public key as in $A(S, n)$ in the ‘standard model’, but also the hash oracle as in $A(H, S_H, n)$.
A ROM theorem is a statement of the following form:
- If there is a random algorithm $A(H, S_H, n)$ which, when $H$ is uniformly distributed, returns a forgery with high probability, then there is an algorithm $A'(y, n)$ which, when $y$ is uniformly distributed, returns a cube root of $y$ modulo $n$ with high probability.
The proof of the theorem is a definition of the algorithm $A'$, which constructs a hash oracle and signing oracle that have the correct distribution to fool the forger, but additionally do enough bookkeeping to extract a cube root out of whatever computations the forger does—without using the secret knowledge of $d$ that the legitimate user would have.
Obviously, internally the random algorithm $A'$ will involve flipping coins just like you described, to implement the hash oracle and the signing oracle. See my earlier ROM answer for details of the proof, and for more background, history, and literature references; see also the standard Bellare & Rogaway paper for the original proof of the RSA-FDH theorem in particular.
In other words, the random oracle model is an assumption about how adversaries are structured. Rather than using the somewhat confusing term ‘random oracle model’, some authors prefer to say that the theorem quoted above is simply a theorem about $H$-generic adversaries, meaning adversaries that are defined generically in terms of an arbitrary hash function rather than adversaries that exploit details of a particular hash function like collisions in MD5.
MD5-specific forgers have been exhibited, of course—for example, they figured prominently in an international incident of industrial sabotage by the United States and Israel against Iran—but they do not contradict this theorem, because such forgers only work with extremely low probability when $H$ is uniformly distributed. In other words, if an RSA-FDH signature scheme instantiated with MD5 goes bad, it's not because the fancy math of RSA-FDH went bad—rather, it's because MD5 went bad, and there's a good chance that using SHAKE128 instead will be fine.
