DES anti-fixed points for semi-weak keys

Question

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)

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.

Explanation:

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?