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.

  • 2
    $\begingroup$ This feels immensely as a homework drop. What have you tried and where are you stuck? $\endgroup$
    – Maarten Bodewes
    Commented Mar 18, 2017 at 10:36

1 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.


Your Answer

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

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