7
$\begingroup$

Can someone explain me this please I am a bit confused? It's from a texbook I am reading (block cipher companion) it says that:

each weak key has $2^{32}$ fixed points $m$ where $\operatorname{DES}_w(m) = m$ ( $w$ is a DES weak key). In other words encrypting a fixed point gives exactly the same point. To see this consider the $2^{32}$ ciphertexts after 8 rounds of encryption for which the two 32 bit halves are equal. For a weak DES key, the round keys of the eighth and ninth rounds are equal. Thus the intermediate texts after seven rounds and after nine rounds of encryption will be equal. Since the round keys of the 7th and the 10th rounds are equal, the intermediate texts after 6 rounds and after 10 rounds of encryption will be equal. Continuing like this it follows that the plaintext will be equal to the ciphertext.

Now did not quite get :

  1. Why are there $2^{32}$ fixed points? And why after the eighth round of encryption the two halves must be equal?
  2. What does the author mean by the intermediate texts exactly? And how are they being equal?

P.S.: This question is not asking for what the weak keys are. I am asking for "fixed points" not exactly weak keys. For this reason I think it is not a duplicate of any other question. There is one similar question to what I've asked for which I have checked and saw that no satisfactory answer has been given there either. Here is the similar question with no proper answers:

What is the fixed point attribute of DES with weak keys?

$\endgroup$
  • 1
    $\begingroup$ @kelalaka it is very similar but not the same question. That post you' ve mentioned, did not have the answer to my question. I am not asking the same thing i.e. weak keys but "fixed points" $\endgroup$ – esra Oct 24 '18 at 19:29
  • $\begingroup$ @Maarten Bodewes I' ve just edited and linked the the question. Thanks $\endgroup$ – esra Oct 24 '18 at 20:23
8
$\begingroup$

I answer in hopefully didactic order.

What does the author mean by the intermediate texts exactly?

The intermediate texts after $n$ rounds are the 64-bit quantities $L_n\mathbin\|R_n$, numbering these per the specification of DES. $L_n$ and $R_n$ are the halves.


Why after the eighth round of encryption the two halves must be equal?

I do not know if the two halves must be equal. But we can prove that it is enough that the two halves are equal, which is what the quoted text does.

Ignoring $\mathsf{IP}$ and $\mathsf{IP}^{-1}$, the normal equations of DES encryption are, for $1\le n<16$: $$\begin{align} L_n&=R_{n-1}&&&R_n&=L_{n-1}\oplus f(R_{n-1},K_n)\\ L_{16}&=L_{15}\oplus f(R_{15},K_{16})&&&R_{16}&=R_{15} \end{align}$$ As a consequence of the values of the four weak keys $z$, all bits in register $C$ are identical. Therefore $C$ remains invariant as it rotates during encryption. The same applies for $D$. Hence $K_1=K_2=\ldots=K_{15}=K_{16}$. Thus for $1\le i\le16$ we can replace $f(R_i,K_i)$ by a function $f_z(R_i)$ identical in all the rounds, for fixed $w$. The above DES equations turn into $$\begin{align} L_n&=R_{n-1}&&&R_n&=L_{n-1}\oplus f_z(R_{n-1})\\ L_{16}&=L_{15}\oplus f_z(R_{15})&&&R_{16}&=R_{15} \end{align}$$ If $L_8=R_8$ (that is equals halves after round 8) then, by plugging this into the equations for $n=8$ and $n=9$, we get $$\begin{align} L_8&=R_7&&&L_8&=L_7\oplus f_z(R_7)\\ L_9&=L_8&&&R_9&=L_8\oplus f_z(L_8) \end{align}$$ We plug the top two equations into the bottom ones, and get $$\begin{align} L_9&=R_7&&&R_9&=\bigl(L_7\oplus f_z(L_8)\bigr)\oplus f_z(L_8)\\ &&&&&=L_7\oplus\bigl(f_z(L_8)\oplus f_z(L_8)\bigr)\\ &&&&&=L_7\oplus0^{32}\\ &&&&&=L_7 \end{align}$$ We used associativity of $\oplus$, that $f_z$ is a function (and identical in all rounds), that for all 32-bit $X$ it holds $X\oplus X=0^{32}$ (the bitstring of 32 zero bits), which is the neutral for $\oplus$.

Wrapping up, we get $L_7=R_9$ and $R_7=L_9$. Thus "the intermediate texts after seven rounds and after nine rounds of encryption will be equal" within an inversion of left and right that the quotation mistakenly sidesteps.

We plug these results into the equations for $n=7$ and $n=10$, and get $$\begin{align} R_9&=R_6&&&L_9&=L_6\oplus f_z(R_6)\\ L_{10}&=R_9&&&R_{10}&=L_9\oplus f_z(R_9)\\ \end{align}$$ After simplification as previously, we get $L_6=R_{10}$ and $R_6=L_{10}$. And so on, up to $L_1=R_{15}$ and $R_1=L_{15}$. For the next step we must take care that the the equations for the last round reverse $L_{16}$ and $R_{16}$ compared to others. We obtain $L_0=L_{16}$ and $R_0=R_{16}$.

The 64-bit plaintext $P$ is such that $\operatorname{IP}(P)=L_0\mathbin\|R_0$ and the 64-bit ciphertext block $C$ is such that $\operatorname{IP}^{-1}(L_{16}\mathbin\|R_{16})=C$. It follows that $P=C$. Call that quantity $m$ and we have $\operatorname{DES}_w(m)=m$, Q.E.D.


Why are there $2^{32}$ fixed points?

There are $2^{32}$ possible values for $L_8$, thus for intermediate text $L_8\mathbin\|R_8$ with $L_8=R_8$. By the above reasoning, each gives a value of $m$ with $\operatorname{DES}_w(m)=m$ for a given weak key $w$. And the values thus obtained must be distinct: DES encryption is deterministic for a given key $w$, thus the same input value can't give different intermediate texts after 8 rounds.

Hence there are at least $2^{32}$ fixed points $m$ for a given weak key $w$. I do not know how many more there might be, for each of the four $w$. However, we can tell that the counts are the same for the all-zero and all-one $w$ (ignoring parity bits); same for the two other weak keys. That follows from DES's complementation property.


How to find fixed points for DES weak keys

One option is to modify some DES encryption code to start at round 8 with $L_8=R_8$. The ciphertext will be a fixed point for the weak key used. We can find $2^{32}$ of these for a given weak key $w$, by using a counter for $L_8$. When that's done for a weak key $w$, we can derive fixed points for the complement of $w$ by using DES's complementation property.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.