26
$\begingroup$

It seems like the S-boxes in DES have essentially random values.

How were these chosen?

$\endgroup$
  • $\begingroup$ I'm just trying to get interested in this, but it seems quite a strange subject. $\endgroup$ – jokoon Aug 10 '11 at 18:54
28
$\begingroup$

There is a good article from Coppersmith which explains it. Basically, the designers of DES had envisioned differential cryptanalysis (a good 15 years before differential cryptanalysis was rediscovered by Biham and Shamir, and published); they could measure how well DES could resist differential cryptanalysis for a given set of S-boxes.

So they generated a huge bunch of random S-boxes, measured them all and kept the best.

It turns out that although the DES designers did not know of linear cryptanalysis (discovered in 1993 by Matsui), having S-boxes which resist differential cryptanalysis kinds of defeats linear cryptanalysis as well.

$\endgroup$
  • $\begingroup$ +1 Thanks for the excellent explanation. The link is off, you would have some link to the same article? $\endgroup$ – Avelino Mar 25 '16 at 23:07
  • $\begingroup$ I found it back on the Internet Archive Wayback Machine. $\endgroup$ – Thomas Pornin Mar 26 '16 at 0:49
23
$\begingroup$

Before it was the standard, the NSA proposed some changes to the S-boxes and didn't explain them. The explanation (which turned out to be correct when differential cryptanalysis was "rediscovered" by the non-spy community) was that if you changed a single bit of the input, every bit of output should have a 50% chance of changing (this is called the "strict avalanche criteria").

Or, to phrase it another way, changing any one bit in the input is sufficient to produce an output that is not obviously correlated in any way (if you don't know the key). The idea is that given one plaintext input and another non-identical plaintext input and the ciphertext of the first plaintext, you can generally predict nothing about the ciphertext for the second plaintext, even if the two plaintexts differ by only a single bit.

This desirable property of the whole cipher (for each fixed key) is also wanted for the S-box components. Some of the earlier (when it was still called "Lucifer") s-boxes designs did not share this property, so a change of a single bit of input might only change a few bits of output.

Some reading materials on the designs of S-boxes are:

$\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.