# 1 round Feistel with birthday attack

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?

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.