# Performing differential cryptanalysis for randomly generated S-boxes

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 ?

• As far as I remember, the reordered s-boxes for DES were known to the attacker. – Nova Mar 3 '15 at 13:37
• The main question is: how do you want to use S-boxes, which are unknown to the attacker, but can be used by a legitimate user? And if you present today a cryptosystem, where it is required that the s-boxes are unknown to the attacker, people will rightfully say "we don't want security by obscurity". – tylo Mar 6 '15 at 17:13
• @tylo: If the s-boxes are key dependent then they are unknown to an attacker. Blowfish does that in an easy way. – Nova Mar 8 '15 at 15:18
• Key dependent s-boxes can surely be done, but what does random imply then? And then there's the question, whether the (sub)key just chooses from a fixed set of s-boxes or generates it based on the key. This is all unclear from the question, but will make a difference in cryptanalysis. And if you just say "random s-box", then it quite surely will have some weakness. Good s-boxes require precice design, because nonlinearity and all the other properties are not so easy to balance out. – tylo Mar 9 '15 at 10:45
• @Nova I too have the same question. Just to give a clear idea Assume that we use the key to perform a uniform permutation to generate a sbox. We know that to perform differential and linear attack the DDT and LAT should be handy. If we make the sbox key-dependent and every distinct key results a distinct sbox(best case). Now if someone tries to perform a differential/ linear cryptanalysis then will it be logical to consider the Bruteforce complexity of guessing the proper sbox? If it is logical then what should be the approach to such an attack? – Radium Nov 25 '20 at 11:58

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.

• Thanks for the elaboration . So let me be more specific , for ciphers like Twofish , how would an attacker preform an attack without knowing the S_box content ? – HSN Mar 3 '15 at 23:42
• @HSN they would need to know the basic cipher design (or figure it out) as well as a bunch of plaintext/ciphertext pairs all generated under the same key. For DES it was many gigabytes, for Twofish it would be 20 billion trillion terabytes, minimum, of CHOSEN plaintexts. And lots of processing power. Then some kind of differential attack could be performed that would recover the s-boxes and round keys. – Richie Frame Mar 4 '15 at 2:06
• And the same concept applies for Linear attacks ? Since linear attacks also requires the calculation of Bias based on the s_box's content – HSN Mar 4 '15 at 3:03