Can you please explain weak keys of the following 2-round DES?

Question

2-rounds DES (M-DES)

• $|M|=|P|=|K|=2^4$;

• S-boxes: $S_1 = [1 0]$ and $S_2 = [11]$;

• The initial and the final permutation are the identity permutation;

• The expansion function is the identity function;

• The key schedule function is defined as follows: For a key $K = (k_1k_2k_3k_4)$, the round 1 key is $K_1 = (k_4k_1)$ and the round 2 key is $K_2 = (k_2k_3)$.

A key $K$ is called a weak key for the cipher $E$ if $E_{K_1}(E_{K_2}(x)) = x$ for all $x \in M$.

Please explain M-DES Weak Keys.

Answer 1

The definition of weak key in the question is a mixup with that of semi-weak key pair, or/and semi-weak key. Let's put these definitions straight.

We'll consider a block cipher $E$ over set $M$, with a key set $\mathcal K$.

The defining property of a weak key $K\in\mathcal K$ is: $\forall x\in M,\,E_K(E_K(x))=x$. In other words, encryption and decryption with $K$ are the same.

The defining property of a semi-weak key pair $(K_1,K_2)\in\mathcal K^2$ is: $\forall x\in M,\,E_{K_1}(E_{K_2}(x))=x$. In other words, encryption with one key in the pair is the same as decryption with the other.

The defining property of a semi-weak key $K\in\mathcal K$ is that there exists $K_2\in\mathcal K$ such that $(K,K_2)$ is a pair of semi-weak keys. In other words, the key occurs in a semi-weak key pair.

---

The M-DES block cipher in the question is a symmetric Feistel cipher with 4-bit message space $M$ and 4-bit key space $\mathcal K$; and a structure similar to that of DES, but simplified to caricature. In particular

• The S-boxes have 1-bit input and 1-bit output (one is bit inversion, the other has constant output 1). Complete linearity follows: within polarity, any ciphertext bit is the XOR of whatever few plaintext and key bits influence it.
• Expansion E is removed; and, beyond a mysterious and probably unrelated $|P|=2^4$, we are not told about a permutation P. Complete lack of diffusion between odd and even bits of the message space would follow that both are gone.

Reducing M-DES to equations, then applying the definition to find weak keys, is left as an exercise to the OP. A computer is not useful.