Known-plaintext attack on 1-round Feistel networks

Question

Consider a simple, 1-round Feistel network.

Because the ciphertext is essentially $(L_1,R_1)$, if one knows the plaintext $(L_0,R_0)$, the only unknown left is $K$.

However round functions in Feistel networks are not necessarily invertible. For example, one could in principle use a cryptographic hash as a round function.

The Feistel network equation would become:

$R_1=L_0 \oplus \operatorname{sha2}(R_0,k_1)\\L_1=R_0$

One could XOR $R_1$ (known ciphertext) and $L_0$ (known plaintext), thus obtaining $\operatorname{sha2}(R_0,k_1)$, but this would not yield the key unless one uses brute force.

Clearly brute force is always possible - and there are other issues with a 1-round Feistel network, for example it leaks half of the plaintext - but I was wondering.

When one talks about KPA against 1-round Feistel networks, is it implicit that brute force can be used in the end to obtain $k$, for non-invertible round functions?

Answer 1

Regardless of the specific $f$ function, you already observe that you can obtain $$ R_1\oplus L_0=f(R_0,k_1) $$ where $k_1$ the first round subkey is your target.

But $R_0$ is also a part of the known plaintext. So you have a system of equations for the bits of $k_1$ which you can systematically attempt to solve. For a normal Feistel function $f$ (which is one to one or the cipher wouldn't be invertible) this is straightforward.

Exactly how $sha_2(R_0,k_1)$ is defined plays a part here:

Possibilities include $sha_2(R_0||k_1),$ or $sha_2(R_0 \oplus k_1)$ (possibly with padding or repeating of $k_1$ to make it the same length as $R_0.$).

In any case you can try to use the $sha_2$ equations, noting that the effective input length is essentially at most the length of $R_0$ plus the length of $k_1$ and hence a strong hash function is most likely one to one for such inputs. Using the random oracle model, a randomly chosen function from an input of length, say, 128 bits, to the full digest size for sha_2 of 512 bits is one to one with overwhelming probability (see birthday paradox, addressed in many answers to questions on crypto stackexchange).

Answer 2

first of all, We should know that the Feistel Network is not anything rather than a pseudorandom permutation, it means that when you give an input to this network, fist it splits it into two parts and then by the help of F function, it maps this two separate inputs into two other separate outputs that one part is left without change but the other part is changed via going through the F function. This F function should be chosen in a manner that after one round, the output of it has the indistinguishable property, means any output of F, indistinguishable of the input of F, but in this case, this function will need much computation and will be heavy; the designers, instead of this heavy F function, use light Functions that can somehow produce this indistinguishability but they use this function in many rounds, that in these rounds together gave enough power of indistinguishability to the whole cipher and this structure will be safe against most of the attacks like brute force and so. Ther is no need for this F function be invertible and the important issue is the power of its indistinguishability after some rounds.

Answer 3

I think it will recover some different K if the length of K is longer than R_1.