In Matsui's paper (Linear Cryptanalysis Method for DES cipher), lemma 1.

  1. $NS(a, b)$ is even
  2. if $a=1,32$,or $33$, then $NS(a,b)=32$ for all $b$

He said that the following lemma is now trivial from the definition of S-boxes.

  • But I can't prove this lemma. How can I prove this lemma?

1 Answer 1


The following apply to all DES Sboxes.

  1. Note that $\overline{a}\cdot \overline{x}$ and $\overline{b}\cdot \overline{S(x)}$ are both linear boolean functions which thus have truth tables with even Hamming weight. The xor of the two quantities is also even, since if they have hamming distance $d$ this is 64 minus (the difference of two even hamming weights) by inclusion exclusion.

  2. The $a=1,32,33$ masking patterns are the ones where either LSB or MSB or both of input bits in the corresponding vector $\overline{a}$ are set to one while the remaining bits are set to zero. Recall that for each of the four such possibilities ($a=0$ as well) the DES Sbox output is a permutation of four bits. This also gives a balanced hamming weight, for all output masks $b$.


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.