The small key-search circuit for brute-force of Bernstein

Question

I'm trying to understand Understanding brute force by Bernstein. I couldn't understand how the described machine can brute force the AES.

The attacker builds a very small key-search circuit. The key-search circuit has three inputs: a 12-byte string $\beta$, a 4-byte integer $n$, and a 16-byte string $s$. The key-search circuit has one output: a 16-byte string $Z(\beta, n, s)$ defined recursively by $Z(\beta, 0, s) = s$ and $Z(\beta, n + 1, s) = Z(\beta, n, H(s \oplus (\beta, n))$.

Answer 1

The crucial part is not just the definition of $Z$, which is a random walk in possible keys. It's also how you use it, on the next page:

1. Search for $Z(\beta, 2^{23}, r_j)$ among $Z(\beta, 0, H(k_i)),$ $Z(\beta, 1, H(k_i)),$ $Z(\beta, 2, H(k_i)),$ $\dots,$ $Z(\beta, 2^{23} - 1, H(k_i))$.
2. If you find that $Z(\beta, 2^{23}, r_j) = Z(\beta, \ell, H(k_i))$, then you have a candidate trail to follow!
3. In this case, start over computing $Z(\beta, 2^{23}, r_j)$, but only go $2^{23} - \ell - 1$ steps until the state $(\beta, \ell + 1, s)$ rather than all the way down to $(\beta, 0, s')$.
4. If $H(s \oplus (\beta, \ell)) = H(k_i)$, you've found a candidate for $k_i$, namely $s \oplus (\beta, \ell)$.

One way to look at it is as follows: The function $H$ (e.g., $k \mapsto \operatorname{AES}_k(18238)$) represents a directed graph where each node $k$ has exactly one successor $H(k)$. Imagine the graph as a network of rivers on a terrain. They're not all connected, but they flow in only one direction.

1. You're teleported onto a node in the middle of a river, and you're trying to find the node just behind you, but you can't look there.
2. You shoot out a scattershot of cheap drones. They will record the node where they landed, and then flow down the river exactly $2^{23}$ steps before stopping and embedding themselves in the river bed.
3. You go to sleep for the night. In the morning, you trawl down the river looking for a drone. If you find one after $\ell$ steps, you go to the point where it started and move forward by $2^{23} - \ell - 1$ steps, and see if the next one is the node you were sitting on at the beginning.

Of course, the drone you find could have come down a different tributary of the river, so you might have to retry with another drone.

This is the rough idea: the model breaks down because rivers are never cyclic, and the advantage comes either from (a) precomputing where the drones landed (as in precomputed rainbow tables) so that you can save effort by reusing them for many trawlings, or (b) simultaneously trawling and shooting out drones in parallel, and then searching for a collision by sorting the nodes where the drones landed together with the nodes you trawled through.