1 round Feistel with birthday attack

Question

This is a reprise of an earlier question of mine, and I'm sorry if it's repetitious; I'm going at it with a different strategy.

In an exercise I was given a 1-round Feistel network which uses $H(k \oplus x)$ as a round function. The key is 128 bits and the block length 256 bits, but we're asked to find the key in roughly $2^{64}$ work.

My intuition is the following. Since the hash takes inputs and outputs of size 128 bits, it seems likely that a collision resistant hash would be roughly 1-1, so we could expect that if we find $H(x) = H(x')$ then we would probably have $x = x'$. In roughly $2^{64}$ time, if I query the hash $2^{64}$ times on random inputs $x_i$ and query the round function $F(x) = H(k \oplus x)$ $2^{64}$ times on random inputs $y_i$, then I expect to have a collision in the hash owing to the "birthday attack" results, where $H(x_i) = F(y_j)$. But then by the earlier hash property, we expect $H(x_i) = H(k \oplus y_j)$ $ \implies x_i = k \oplus y_j$. This (probably) gives us the key, in $O(2^{64})$ time.

Am I correct? Is there a better analysis that makes more sense?

Answer 1

Assuming the Hash function is "good" (say it obeys the random oracle model, for concreteness) its restriction to 128 bit inputs should behave as like a random function.

This means that it will "miss" roughly a fraction $(1-e^{-1})$ of the $2^{128}$ binary strings in its range. Also, it will, with high probability have a point $y$ in its range (see, e.g., Mitzenmacher's Probability and Computing book), such that $$|H^{-1}(y)|\approx \frac{\log n}{\log\log n}:=M,$$ where $n=2^{128}.$

In fact, iterating this argument, since the remaining points in the range can be considered to come from a random function on $2^{n}-M$ points which would then have a point in its range with inverse image size $$\approx \frac{\log (n-M)}{\log\log (n-M)}$$ and so on.

This is probably not "almost one to one", but it looks like your attack may work with some fixed probability bounded away from zero, if you use multiple P/C pairs to deduce intersections of possible key sets corresponding to the clustered points in the range.