Q:

S-box design criteria and random sboxes

What are the disadvantages of using random s-boxes?
In AES, the s-boxes had to obey certain mathematical rules, which? And why?
What security does using hidden s-boxes (GOST) or generating them from the key (Khufu) add?, and how do these secret and generated s-boxes defend against differential and linear cryptanalysis or other unknown attacks?

A:

What are the disadvantages of using random s-boxes?

This relates to the "why" behind some of the rules for s-boxes. AES, for example, requires an invertible s-box. A random s-box will not necessarily be invertible. In an s-box we also want non-linearity to thwart linear and differential cryptanalysis. This might not be the case with a random s-box.

In AES, the s-boxes had to obey certain mathematical rules, which? And why?

According to "The Design of Rijndael" the design criteria was 1) non-linearity, specifically "the maximum input-output correlation amplitude must be as small as possible" and "the maximum difference propagation probability must be as small as possible". This is to prevent linear and differential cryptanalysis. And 2) algebraic complexity. This was to prevent algebraic attacks.
They achieve 1) by choosing an s-box that was studied in Differentially uniform mappings for cryptography. This particular s-box however is algebraically simple. Thus, the AES designers added an affine transformation which would be easy to describe yet algebraically complex.
One additional restriction they placed was that there were no fixed points and no opposite fixed points.

What security does using hidden s-boxes (GOST) or generating them from the key (Khufu) add?, and how do these secret and generated s-boxes defend against differential and linear cryptanalysis or other unknown attacks?

Full disclosure, I'm not too familiar with these ciphers. From what I saw on wikipedia, the s-box in GOST can but doesn't have to be kept secret. The effect of this is an increase in the key size. Secret s-boxes would have to have properties similar to those of AES's s-box in order to thwart differential and linear cryptanalysis.
Generated s-boxes, I'm assuming must have some algorithm to setup an s-box using keying material that still meets the necessary properties. I'm guessing this is why Khufu has an expensive setup operation.

