2
$\begingroup$

Two of the properties that lead to the design of DES S-Boxes are:

  1. For any non-zero 6-bit difference between inputs, no more than 8 of the 32 pairs of inputs exhibiting that difference may result in the same output difference.

  2. This is a criterion similar to the previous one, but for the case of three S-boxes.

The book i am reading (Understanding Cryptography from Christof Paar and Jan Pelzl) translates the second one to: A collision (zero output difference) at the 32-bit output of the eight S-boxes is only possible for three adjacent S-boxes.

Can anyone explain me the first property? I have searched for that property on google but the statement is always the same and i can't understand it. At first i thought that the non-zero 6-bi difference was between two different inputs to an s-box. But then it talks about 8 pairs of the 32 pairs (the only 32-bit input is the one before the expansion) that exhibit the 6-bit difference. Am i the only one finding this explanation confuse as hell?

As for the second criterion and assuming the book explanation i assume that you can't have something like (O = output of s box):

O(s1) = O(s2) = O(s3) = O(s4) = O(s5) = O(s6) = O(s7) = O(s8)

but you can have:

O(s1) = O(s2) = O(s3) && O(s4) = O(s5) = O(s6) or some combination of three adjacent s-boxes.

I hope you understand my questions and you can help because i would like to clarify this.

$\endgroup$
  • $\begingroup$ Have you read coppersmith94.pdf? The criteria for (S-7) (your 1) is given in the section entitled Discussion of Criteria and puts an upper bound (on the probability of a linear approximation. (S-8) (your 2) is the three active S box case described there. You haven't cited references or specified the book. $\endgroup$ – user1430 Sep 7 '14 at 10:41
  • $\begingroup$ Thank you for you answer. I edited the question to add the book. Didn't see this document. Still, this documents helps me as much as any other i read. The problem is that property 8 depends on the understanding of 7 and i don't understand 7. If you understand it please explain me because i have read the property a thousand times and still makes no sense. It first talks about what i assume as a 6 bit difference between two inputs two an s-box but then it talks about an 8-bit pair of inputs with a 6-bit difference??? Makes no sense to me $\endgroup$ – BrunoMCBraga Sep 7 '14 at 11:10
2
$\begingroup$

First property says- If you consider a 6-bit Inpput Difference(Difference means XOR in case of DES).i.e 6-bit binary number which is the xor of two inputs(obviously both 6 bits).When you enter both of these inputs to Sbox and get two outputs each of 4 bits and xor the outputs what you get is called Output Difference.

Total 64 inputs are possible hence 32 pairs having a same difference.

So this property says for any non-zero 6-bit input difference there can be maximum 8 possible different 4 bit output difference and not more than that.

Hope i am clear

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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