As far as I know, performing differential or linear cryptanalysis always requires a knowledge of the S-boxes' content and order. Yet in Bruce Schneier's Applied Cryptography, it is stated that random key dependent S-boxes and/or randomly reordered S-boxes for DES can make the algorithm weaker.
So my question is, how would an attacker perform such attacks on a cipher without knowing the content of the S-boxes ?
With DES, the issue is the size of the s-box. The DES s-boxes are highly tuned for their security properties, but if you compare their nonlinearity to the larger AES s-box, the are quite inferior.
Note than random s-boxes and key dependent s-boxes are not the same thing. Random = fixed random, key dependent = permuted s-boxes based on the key. A random set of key dependent s-boxes is a different story, essentially, you are generating random s-boxes using key material.
If you tried to apply random key dependent s-boxes to DES, it can indeed make the whole algorithm weaker. With enough ciphertext/plaintext pairs, and knowledge of the the algorithm less s-boxes and keys, it is quite possible to perform key recovery. The biases are substantially larger with inferior s-boxes. I believe it reduced the data requirements of a differential attack by more than 10000X. Since the attack is much more effective than brute force, the additional complexity of using key material to generate the s-boxes does not strengthen it enough, only by about 32 times vs fixed random. See CS0816 for more detail.
A variant of DES exists where extra key material is used to reorder the standard s-boxes into one of 32 orders known to increase the strength of the algorithm, it is similar to having a key dependent s-box, and it does make the DES variant stronger.
With larger s-boxes and better design (and more importantly, larger keys), key dependent s-boxes work. Twofish is a great example of this. The key dependent s-boxes are not random, they are generated in a specific way from the key material as to be strong. However from a purely mathematical perspective they are not as strong as the AES s-box, but they have the advantage of not being known to the attacker. This may or may not be an advantage in the face of improving attacks. The additional advantage Twofish has is multiple s-boxes, which leaves less attack surface is one of the s-boxes does have a problem, but increases implementation complexity.
Another example is Khufu and Khafre, which are quite similar, but Khufu has key dependent s-boxes, and is more secure.
Overall, Twofish is thought to have better security than AES, and the key dependent s-boxes are one of the reasons why. DES in comparison, is not designed for key dependent s-boxes, which is why using them can weaken it more than it can strengthen it. The modified order however does work, and combined with DES-X style whitening, makes DES essentially invulnerable to linear and differential analysis, since the amount of plaintexts would be at least $2^{60}$ for linear, maybe more, and exceed the codebook for differential.
EDIT
Here is a new paper where AES variants with a secret s-box are attacked. Integral cryptanalysis was the method of attack.
