5
$\begingroup$

I'm doing a lot of reading about Feistel networks. Something occurred to me a bit ago that I hadn't realized previously, namely that in any Feistel construction there are bits of the plaintext that are never given as input to the round function without having been mixed with the previous round function's output.

For example, in the first round of a balanced Feistel network $L_0$ is XORed with $F_k(R_0)$ to get $R_1$. Thus, $L_0$ is never used by itself as input to $F_k$, which could violate the diffusion property of the cipher.

Is it even possible to get around this limitation, perhaps with a modified first round?

I don't think this is a real vulnerability in e.g. DES or Blowfish, for the record. Rather, I'm wondering whether this could be used to craft a successful attacker in a game against a reduced-round variant of these kinds of ciphers.

Improve this question
$\endgroup$
4
  • $\begingroup$ What makes you think this "could violate the diffusion property of the cipher"? It looks to me like that's where your reasoning went awry, but without further details, I'm not able to diagnose with any more specificity what would help clarify this. $\endgroup$
    – D.W.
    Sep 25, 2013 at 3:35
  • $\begingroup$ I wasn't sure it did, that's part of what I wanted to clarify. Do we still say those bits have properly diffused if they're XORed with something else first? $\endgroup$
    – pg1989
    Sep 25, 2013 at 9:02
  • $\begingroup$ pg1989, Ahh, now I see: you are uncertain about the definition of diffusion. The definition of diffusion is that each bit of the input affects all bits of the output. For instance, if you flip one bit in the input to the block cipher, then about half of the bits of the output of the block cipher should change. Notice that this doesn't impose any restrictions on what happens internally, inside the block cipher; it only has to do with how the inputs ultimately affect the final outputs of the cipher. See the strict avalance criterion. $\endgroup$
    – D.W.
    Sep 25, 2013 at 16:59
  • $\begingroup$ Another thing I just realized: If $F_k$ exhibits diffusion it doesn't matter if $L_0$ is XORed first. $\endgroup$
    – pg1989
    Sep 25, 2013 at 18:54

2 Answers 2

Reset to default
9
$\begingroup$

If such a network had only a single round, then you might have a valid concern. This is why there needs to be least three rounds, so that every bit from L can potentially affect every other bit from L (via R from the second round).

It isn't a structural flaw, because multiple rounds are assumed. Changing this round structure would mean that it was no longer a Feistel network, and you would lose the reversibility of each round (when the key is known).

Improve this answer
$\endgroup$
8
$\begingroup$

No, this is not a structural weakness of Feistel networks. For instance, we know it can't hurt diffusion properties. Actually, we know that it's not a structural weakness. How do we know that? Because we have a proof of security for Feistel networks (under certain conditions and assumptions). Those proofs imply that there is not a structural weakness in the Feistel approach.

The proof of security never relies upon claiming that "every input bit is used as input directly to some F-function without having been mixed with any other F-function's output". That condition, it turns out, is not necessary for security. I'm not sure why you thought that condition is necessary (which makes it harder for me to help you understand why this isn't a problem), so all I can say is: we know that condition isn't necessary for security.

Therefore, there is no need for a modification to the Feistel framework. The approach is fine. There is no actual vulnerability here.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.