Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

How were these chosen?

share|improve this question
    
I'm just trying to get interested in this, but it seems quite a strange subject. –  jokoon Aug 10 '11 at 18:54

2 Answers 2

up vote 21 down vote accepted

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.

share|improve this answer

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:

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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