Now i know that the F function doesn't have to be injective, but is it NEVER injective? or is it possible to have an injective F function?
3
-
$\begingroup$ It can be any function but that will need a new security analysis. $\endgroup$– kelalakaCommented May 28, 2020 at 14:30
-
1$\begingroup$ Hints for self-answering: $F$ has not changed since publication of FIPS PUB 46 in 1975, thus "NEVER" must have some meaning not directly related to time. Towards grasping that: what are the inputs and outputs of $F$? Count these, and find that's incompatible with the usual definition of an injective function. Twist this definition so that at least, $F$ could be injective without changing the rest of DES, and "NEVER" starts to make sense. Now it remains to determine if $F$ matches this definition.Which is not trivial, but is accessible to experience with a computer, or analysis. $\endgroup$– fgrieu ♦Commented May 28, 2020 at 17:30
-
$\begingroup$ I have posted a related question without an ambiguity discussed in comments to kodlu's answer. $\endgroup$– fgrieu ♦Commented May 29, 2020 at 6:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
There is nothing that stops a Feistel cipher from having injective Sboxes.
One could remove the $32$ to $48$ bit expansion map $E$ in the DES $F-$function and have an injective Sbox layer made up of $4\times4$ Sboxes and thus an injective $F-$ function for a modified DES. It would need round keys of $32$ bits and thus use less randomness and be weaker.
Also, there are many Feistel and generalized Feistel ciphers out there, including AES finalists MARS and RC5. Studying them may help you understand $F-$ function design better.
-
1$\begingroup$ If I get the answer right, it studies changing $F$ of DES to $F'$ with other S-boxes and round key turned $32$-bit, such that $\forall K\in\{0,1\}^{k'}$, the function $G'_K:\,\{0,1\}^{32}\to\{0,1\}^{32},\ R\mapsto G'_K(R)=F'(R,K)$ is injective. Another reading of the question is that it asks: with $F$ as defined in DES, does it hold that $\forall K\in\{0,1\}^{48}$, the function $G_K:\,\{0,1\}^{32}\to\{0,1\}^{32},\ R\mapsto G_K(R)=F(R,K)$ is not injective?. That's a reading of "is $F$ NEVER injective?" that I find a better fit for a homework question. $\endgroup$– fgrieu ♦Commented May 28, 2020 at 20:35
-
$\begingroup$ @fgrieu yes that is how i meant it. Anyway, if we take the 6 to 4 bit s boxes to simply ignore than last 2 bit of the 6 bit, then we would have a injective F, am i correct? $\endgroup$– Prawns82Commented May 28, 2020 at 22:33
-
$\begingroup$ @prawn82: in my comment above, " the answer" is that of kodlu. What you describe in your "if we take.." is correct, and does not need reducing $K$ as kodlu does (your construction ignores 16 bits of $K$). But again changing the S-boxes changes $F$, thus this line of thought answer "do cats NEVER bark" by NO, exhibiting of a barking dog as proof. $\endgroup$– fgrieu ♦Commented May 28, 2020 at 22:44
-
$\begingroup$ @fgrieu What i meant was, your interpretation of my question was correct. But i wouldn't say i was changing F, since out of all the F's there will be some that ignore the last 2 bit (or leave them unused), and so is injective? $\endgroup$– Prawns82Commented May 28, 2020 at 22:52
-
$\begingroup$ The question's title is: "DES $F$ function never injective?", and the question contains "the F function". I have read that as meaning that $F$ is as defined in DES, complete with the values of the S-boxes, which as I pointed nver have changed. Then, the question can be understood as: is the restriction of $F$ to a fixed $K$ NEVER injective?. That's a well defined, falsifiable question, and the answer requires some thought. $\endgroup$– fgrieu ♦Commented May 28, 2020 at 23:03