I am looking for some "real examples" of anti-fixed points for DES semi-weak keys. As I know, there are $2^{32}$ anti-fixed points for 4 of the 12 semi-weak keys each. One or two examples of these points may help.

Anti-fixed points: For 4 of the (known) DES semi-weak keys, there exist $2^{32}$ plaintexts such that $E_k(x)=\overline{x}$

More info about DES weak keys, semi-weak keys, fixed points and anti-fixed points in the Handbook of Applied Cryptography, fact 7.90 (alternate link)


1 Answer 1

K = 01FE01FE01FE01FE   P = 771DF32699DF2F2A   C = 88E20CD96620D0D5
K = 01FE01FE01FE01FE   P = 668493768A3D5786   C = 997B6C8975C2A879
K = 01FE01FE01FE01FE   P = 6F52785BC50C62BE   C = 90AD87A43AF39D41
K = 01FE01FE01FE01FE   P = DFFE8B7E72E5CFED   C = 200174818D1A3012

will do. I found that by a randomized search after about $2^{34}$ DES operations, which tends to confirm the order of magnitude of the $2^{32}$ stated in the question.


For $i\in[1,16]$, note $L_{i-1}$ and $R_{i-1}$ the 32-bit contents of the $L$ and $R$ registers before encryption round $i$; note $R_{16}$ and $L_{16}$ the output of the last round after a swap (even if that swap is undone by an extra final swap, or equivalently is not done); note $K_i$ the 48-bit sub-key for round $i$. We have $L_i=R_{i-1}$ and $R_i=L_{i-1}\oplus F(E(R_{i-1})\oplus K_i)$, where $E$ is the expansion, and $F$ represents the S-boxes and permutation $P$ combined.

For the four keys $K$ 01FE01FE01FE01FE, FE01FE01FE01FE01, 1FE01FE00EF10EF1, E01FE01FF10EF10E, it holds that $K_i=\overline{K_{17-i}}$.

If it happens that $L_{8}=\overline{R_{8}}$, using that $E(\overline X)\oplus \overline{K_i}=\overline{E(X)}\oplus \overline{K_i}=E(X)\oplus K_i$, it follows that the input of function $F$ (S-boxes and permutation $P$) at rounds 8 and 9 are the same, thus their output are the same. By induction we get that the input of $F$ at round $i$ and $17-i$ are the same, and $L_i=\overline{R_{16-i}}$. Thus $L_{16}=\overline{R_0}$ and $R_{16}=\overline{L_0}$, thus $E_K(P)=\overline P$ for the $P$ corresponding to $L_0$ and $R_0$.

We could efficiently construct $2^{32}$ plaintexts $P$ with that property by performing the last 8 rounds of decryption and final permutation of DES, starting from the $2^{32}$ values of $L_{8}=\overline{R_{8}}$.

Unsettled: does there exist a DES key $K$ with more than $2^{32}$ anti-fixed points?


Your Answer

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

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