3
$\begingroup$

So everyone seems to agree that recurring round keys in a Feistel network (eg. using the same key for every round) are a massive security leak. When researching this, the only thing I found is the Slide Attack (https://en.wikipedia.org/wiki/Slide_attack), in which a slid pair is found, which can be used as a plaintext-ciphertext pair of the PRF used in the network (which is the same / repeated in the network).

My problem with using this attack to prove that key reuse is insecure, is that this only works if the PRF is vulnerable to known-plaintext attacks, ie. the key / part of the key can be recovered if a plaintext-ciphertext pair is known. Now, my understanding is that if one was to just use a keyed PRF which does not leak parts of the key from a cipher-/plaintext pair, the whole network would be secure, which I am relatively sure is not the case.

In addition, what I do not get is why a Slide attack completely breaks the algorithm; according to all sources I have found, one still has to find $2^{n/4}$ cipher-/plaintext pairs, which of course is significantly less than the original $2^n$, but still not polynomial, ie. I can just quadruple the block size to get the same amount of security.

What information am I missing that invalidates my claims, so that cyclic keys really make a Feistel network insecure?

$\endgroup$
  • $\begingroup$ Good question, but "I can just quadruple the block size to get the same amount of security." ... I don't see the justification for the word "just" in there. $\endgroup$ – Maarten Bodewes Nov 30 '19 at 21:26
  • $\begingroup$ Usually, the Feistel structure is not instantiated with a PRF at all. It's just a common way to design block ciphers, and in that case the round function is almost always a simple function (often a permutation in fact). Also, in the real world, you will be asked to fix the security parameter. At that point, "polynomial running time" becomes void. Even from a theoretical point of view (not that this really matters), your security parameter is the length of the key -- not the block size $n$. So it might be a polynomial attack if you make the key long enough. $\endgroup$ – Aleph Dec 1 '19 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.