Why are cyclic keys in Feistel Networks insecure?

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?

• 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. Commented Nov 30, 2019 at 21:26
• 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. Commented Dec 1, 2019 at 9:49