Can the round function $F$ in a Feistel Network be practically any non-invertible function?

This question might seem silly, but how true is the fact that the round function $F$ does not have to be invertible?

I am curious to know this, because non-invertible functions can be very lossy, i.e., can lose much of the information related to the input, hash functions for example.

• Yes you can plug a hash function (or something like HMAC) in as the round function for a feistel network.
– SEJPM
Oct 18 '15 at 16:53
• @SEJPM How can I use the keys? Should I use the keys as some value in the hash function or could i just append the key with the input block?
– user17887
Oct 18 '15 at 16:58
• The round function $F$ does not loose any information of the plain-/ or ciphertext, since the portion of the text that is linked with the $F$ function is forwarded past the function too. Giving a good gues appending the key is as good as using it as a value for the hash function (depending on how you manage you key expansion). Oct 18 '15 at 17:02
• Please refer to the proof here crypto.stackexchange.com/questions/18611/… Oct 20 '15 at 9:11

Yes you could use a hash function as round function, but if you are using the "same key" over all rounds, you are vulnerable to slide attacks. Using a hash function is not a very good idea.

Your round function should not introduce biases, should not lead to special differences (attack: differential cryptanalysis), and it should also not be writable as a linear equation (attack: linear cryptanalysis). You should take care of how your round function will work when the round keys are slightly modified (attack: related key attacks), and you should take care of impossible differentials. If you got all that right, you can use any $F$ which passed these criterions.

Short answer is, $F$ needs to be carefully selected. And “yes” you are interested, that $F$ will "loose as much information about the input" as possible.

This question might seem silly, but how true is the fact that the round function $F$ does not have to be invertible?

Your round function does not need to be invertible, because the classic balanced Feistel construction will create two halves, where only one half is modified, and the other kept in clear text/unmodified. After each round both halfes are exchanged and the modified half becomes the fixed one and the previously unmodified half is now encrypted. If you now reverse the order of the keys/rounds you can decrypt the message again. The Feistel construction itelf is invertible.

• Is there an example of a feistel cipher that uses a hash algorithm as a round function
– user17887
Oct 19 '15 at 11:23
• No I am not aware of such a construction, nor a paper or book discussing that. But there is an Article on "constructing vil macs from fil macs" in the Crypto 99 conference proceedings, which states: "An appropriately keyed version of the compression function of any existing cryptographic hash function can play the role of $f$" - but is discussed in conjunction with calculating MACs. Oct 19 '15 at 19:06
• I've made such a beast to do format preserving encryption for use in game development (security wasn't needed). That let me generate a large number of random numbers ($2^{32}$) ensuring that there were no repeats. Oct 20 '15 at 2:54