3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Yes you can plug a hash function (or something like HMAC) in as the round function for a feistel network. $\endgroup$
    – SEJPM
    Commented Oct 18, 2015 at 16:53
  • $\begingroup$ @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? $\endgroup$
    – user17887
    Commented Oct 18, 2015 at 16:58
  • 2
    $\begingroup$ 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). $\endgroup$
    – Fleeep
    Commented Oct 18, 2015 at 17:02
  • $\begingroup$ Please refer to the proof here crypto.stackexchange.com/questions/18611/… $\endgroup$
    – sashank
    Commented Oct 20, 2015 at 9:11

1 Answer 1

Reset to default
4
$\begingroup$

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.

Your second question:

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is there an example of a feistel cipher that uses a hash algorithm as a round function $\endgroup$
    – user17887
    Commented Oct 19, 2015 at 11:23
  • $\begingroup$ 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. $\endgroup$
    – thepacker
    Commented Oct 19, 2015 at 19:06
  • $\begingroup$ 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. $\endgroup$
    – Alan Wolfe
    Commented Oct 20, 2015 at 2:54

Your Answer

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