# What are the requirements from a Round function in Feistel network?

Let's assume a balanced network with many (dozens?) rounds. And a simple (selecting key bits) key schedule. What does it take from the round F function to make a secure block cipher? obviously we need non linearity and some avalanche. But is this sufficient, how can this still fail? Does a high round count compensate for any mild weaknesses in the F function?

What does it take from the round F function to make a secure block cipher?

• The ability of providing resistance to most common attacks like differential, linear, algebraic, slide and others mainly depend on the features of S-box (if used). * Simon does not use an S-box.
• To design F-function, it depends on the structure of your Feistel cipher Type I, II, III and others (which differ in term of number of branches, number of F-function, internal structure of F-function).

• The size of plaintext (64,128) could also influence the size of box (4-bit or 8-bit), like piccolo vs Clefia. Therefore, the differential probability, linear probability and algebraic immunity differ, 8-bit S-box provide higher immunity features, therefore lower number of active S-boxes needed to provide minimum immunity, hence lower number of rounds.

• The internal structure of F-functions such as SP vs SPS influences diffusion (in term of number active-box). In addition, the use of different MDS matrices in r-rounds (multiple round diffusion or diffusion switching mechanism (DSM)) provide higher diffusion compared to using 1 MDS matrix. CLEFIA employs DSM.

• On the other hand, 8-bit s-boxes such as those in AES are expensive in term of masking against side channel attacks. One way is to use smaller s-boxes (easy to mask) to build larger s-boxes or using 4 bit S-box.

Does a high round count compensate for any mild weaknesses in the F function?

• I don't think if you have self-similarity F-function, it will be vulnerable to slide attack, increasing the number of rounds will not providing compensate for weakness. To solve the self-similarity of F-rounds it is recommended to add constants. For how to chose round constants for simple key scheduling, I recommend to read

Proving Resistance against Invariant Attacks: How to Choose the Round Constants

There are others structures of internal F-function (not only SP, SPS) such as ARX (e.g. the Simon cipher) that have been design in a triangle of security, performance and size, and resistance to both mathematical and implementation attacks (such as timing, DPA).

• You say self similarity won't be solved by more rounds? But what about the basic structure of the F function, if I have small or otherwise sub-par S-Boxes, If I have to strong linear/differential property in my F function, can I add more rounds (with proper constants) and shrug it off? – Meir Maor Jul 4 '18 at 8:33
• what do you mean basic structure ? give me an example substation permutation (SP) , substitution-permutation-substution(SPS) , is the permutation using MDS matrix or shuffling ? secondly adding more rounds strengthen the differential/linear immunity of the whole cipher not the F-function, to strengthen the F-function , as i said you need to know the size of S-box as one aspect. – hardyrama Jul 4 '18 at 8:57

Since the decryption of Feistel donot need inverse of round function, we only need to consider the design of round functions and round number.

For the round function, I think it need a good diffusion and confusion, it even doesnot need to be an 1-1 function, you can even use a hash function. Since you may not design a block cipher, you may design a hash function using Feistel.

Since the criteria for a symmetry cipher is the number of rounds it can resist for some typical attack, e.g., differential and rebound, we may consider all the attack model in history to deal the round number.

Does a high round count compensate for any mild weaknesses in the F function?

This may be the case, and this is (perhaps) tangential evidence. A Feistel network forms a block cipher with a number of rounds, often using a simple compressive (F) function. Whilst not a Feistel network, the Threefish block cipher is part of the Skein family of hash functions, and is associated with this quote from it's design paper:-

"The core design principle of Threefish is that a larger number of simple rounds is more secure than fewer complex rounds. "

I include this quote as it specifically relates to increased round count. Threefish's compressive MIX function has geometric similarities with an F function. It would not be a huge leap to assume that the principle of additional rounds providing additional security holds. It is certainly not evidence to the contrary, and I can't recall any professional construct that is safer when shorter.

Plus, the Wikipedia article on Fiestel networks seems to suggest that you're correct. Whilst additional rounds make not immunise a network from all possible attacks, it seems like common sense that more rounds generally increase the overall security when all other things are equal. It must at least increase diffusion if nothing else.

• Threefish's compressive MIX function has geometric similarities - Threefish's mix function is not compressing, it is a bijection and a one-to-one mapping. Aside from that, what does "geometric similarities" mean? – Ella Rose Jul 5 '18 at 0:11
• The constants are part of the circuit/algorithm, and not part of the state. By your line of reasoning, a NOT gate $y = x \oplus 1$ is also compressive. Clearly such a conclusion is absurd. – Ella Rose Jul 5 '18 at 16:48
• @EllaRose Well if your function was made generic as $y = x \oplus z$, and $z$ was an input variable, which is similar to Figure 1 in the paper, it would be wouldn't it? Three arrows in, two arrows out. That's one less arrow out than in, and thus suggestive of compression. Is this a wee bit too much dissection of a playful and loose analogy, rather than concentrating on the core design... quote and question? – Paul Uszak Jul 5 '18 at 21:09
• "Compressive function" has a specific meaning in information theory (and cryptography). You cannot claim a function is compressive and call that terminology a "playful and loose analogy". You are incorrect anyway. The mix function takes $(x_0, x_1)$ and returns $(y_0, y_1)$. That is, it takes in one tuple and spits out one tuple. The actual function can be described as $y_0 = x_0 + x_1 \mod 2^{64}$ and $y_1 = (x_1 \lll R_{(d \bmod 8)j}) \oplus y_0$. That is not compressive. A constant is not an input. – forest Jul 6 '18 at 0:10
• @PaulUszak Regarding $y = x \oplus z$, it would only be compressive if both $x$ and $z$ were inputs. If $x$ was a constant and only $z$ was an input then no, it would not be compressive by any meaning of the word. Or would you also claim that $f(x) = x + 1$ is compressive because of the $1$? – forest Jul 6 '18 at 0:16