It seems like the S-boxes in DES have essentially random values.
How were these chosen?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
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.
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:
On The Design Of S-Boxes by A. F. Webster , S. E. Tavares.
S-Box Modifications and Their Effect in DES-like Encryption Systems by Joe Gargiulo.
Cryptography and Privacy by Horst Feistel.