PRF Oracle RoomTell the keyed function from pure chance
Start with the ideal object cryptographers wish they had, a truly random function. Then see the practical stand-in they build instead, a pseudorandom function. Then play two games: first try to predict a row you haven't seen, then take the formal test of telling the two apart.
Part 1 · The ideal
A truly random function
A function here takes an 8-bit input x (0–255) and returns an 8-bit output. Any such function is just a table with 256 rows, one output written next to each input.
A truly random function is the table you get by flipping 8 fair coins for every row. Nobody chooses the outputs.
Two things follow. Every output is uniformly random and independent of every other, so learning f(3) tells you nothing about f(4). And once the table is written it's fixed: ask for f(3) twice and you get the same answer both times. It's random, but it's still a function.
The whole table · darker = bigger output
Point at a cell to read its row.
Row x sits at column x mod 16, row ⌊x/16⌋. Reflip as often as you like: there's never a pattern, because nothing produced one.
The catch is size. To use a random function you have to store the whole table, and to share it you have to send the whole table. At 8 bits that's already 2,048 bits. With 128-bit inputs, the size AES uses, the table would take 2135 bits, far more than all the storage on Earth.
Rows
256
Bits to store it
2,048
Possible tables
22048
Part 2 · The stand-in
A pseudorandom function
Instead of storing the table, store a short secret keyK and a public recipeF. Row x of the table is computed on demand as FK(x). Change the key and you get a different table.
F is a pseudorandom function if, for a random key K, no efficient program that can ask for rows of the table can tell FK apart from a truly random function, except with negligible probability.
The recipe is public; only K is secret. A 128-bit key can reach at most 2128 tables, a vanishing sliver of all 22048. That's the surprise a good PRF delivers: the table is far from random, but without the key nobody can tell. Try the recipes below. The weak ones show their structure right away.
Recipe
Point at a cell to read its row.
Why it matters: the key is small enough to store and share, any row takes microseconds to compute, and anything proven secure using a truly random function stays secure, up to a negligible loss, when you swap in the PRF. AES and HMAC-SHA256 are the PRFs used in practice.
Bits to store it
128
Tables it can reach
≤ 2128
Share of all tables
2−1920
Truly random function
Pseudorandom function FK
How it's made
Flip fresh coins for every row
Pick a random key once, then compute rows with a public recipe
What you store
The entire table
Just the key (for example, 128 bits)
Same input twice
Same output: it's a table
Same output: it's a deterministic recipe
Looks random to
Everyone, always
Anyone who doesn't have K and has only limited computing power
Use in practice
Impossible at real sizes, but ideal for proofs
Everywhere: MACs, key derivation, encryption
Part 3 · Predict the unseen row
Can you guess a row you haven't looked at?
The game circles one input x* in yellow and hides its row. You can look up to 5 other rows, then guess the 8 bits of f(x*). Play against a truly random function, a PRF, and three broken recipes, and compare your score with blind guessing.
The table · rows you've seen are shaded
Click any cell to look up that row.
Before you guess, only the rows you asked for are visible. Afterward the whole table is revealed, so you can see whether there was a pattern to exploit.
Round 1 · Truly random function
Look-ups left
Your challenge
Predict f(0)
You can't look up this row itself. Every other row is fair game.
Your guess for the 8 bits · click to flip
Your results so far
Function
Rounds
Exact
Bits right
Blind guessing
—
0.4%
4.0
"Bits right" is the average number of your 8 bits that matched. A coin toss gets 4 of 8, and an exact hit happens 1 time in 256 (0.4%).
Why this matters
With the truly random function, nothing you look up can help: the hidden row is fresh coin flips. A good PRF has to be just as hard to predict, even though it's a fixed recipe. That's what makes FK(message) a secure authentication tag: predicting it means forging it.
Predicting also breaks the formal test in Part 4. If you could guess f(x*), you'd ask the box for x* and check your guess. A match points to the PRF, a miss to the random box.
Part 4 · The formal test
Can you tell them apart?
Predicting is one way to break a PRF, but the official definition in Part 2 covers every way: any difference you can detect counts. You're the adversary. Each round a hidden coin b decides which box you're questioning: a keyed recipe or a truly random table. Ask it a few inputs, then guess. If you can win reliably, that recipe is not a PRF. Levels 1–4 are broken recipes you can beat. Level 5 is one you can't.
b = 1 · Real world
x→FK→y
A fixed recipe with a secret key. Same key, same x, same y.
b = 0 · Random world
x→notebook→y
A new x gets 8 fresh coin flips, written down. Ask again, get the same line back.
The rules, as a cryptographer writes them
Game PRFF
Initialize
K ←$ KeySpace
b ←$ {0, 1}
Fn(x)
if T[x] = ⊥ then
if b = 1: T[x] ← FK(x)hidden
else: T[x] ←$ {0,1}8hidden
return T[x]
Finalize(b′)
return (b′ = b)
The highlighted lines show where the game is right now. The two lines covered by bars depend on b, so they stay covered until you commit to a guess. The table T is why both boxes repeat themselves: asking the same x twice tells you nothing.
Your advantage is Adv = | Pr[b′=1 | b=1] − Pr[b′=1 | b=0] |. It's 0 if you're guessing blindly and 1 if you're never wrong. A PRF is secure when every efficient adversary's advantage is negligible.