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?