Number of Sbox in a Cipher

Question

Camellia has 4 SBOX and so does the TwoFish(key dependent 4 Sboxes). Where as AES uses only one. Would it have made AES more secure if AES had 4 or more SBOX too? Does using more Sbox with similar Properties (Non Linearity, Differential Probability, Linear Probability, Strict Avalanche Criteria etc) increase the security as compared using just one for all possible byte positions? What security impact it will gain if 16 Different SBOX are used?

Answer 1

Coincidentally I had the Twofish and Camellia design papers open on my computer when you asked this question.

S-boxes in the ciphers

Both are Feistel ciphers, and the way the s-boxes are used is quite different when compared to AES. The s-boxes are used almost identically in Twofish and Camellia, but key mixing and post s-box diffusion are quite different. I assume you know the general structure of the ciphers so I will not go over that here.

Camellia uses each s-box twice per round, and runs the entire 64-bit input through those s-boxes in parallel, then mixes them together. Key material is added to the input prior to the s-boxes. Twofish uses each s-box twice per round in parallel, then mixes each 32-bit half, then mixes those halves together, followed by addition of key material.

AES of course uses the same s-box on all 16 input bytes prior to mixing, followed by diffusion and key mixing.

S-box design

The way the s-boxes in these ciphers are generated is also different. AES uses its single s-box generated from finite field inversion followed by affine transformation and addition of a constant.

Camellia uses 4 AES-like s-boxes (finite field inversion), S2 S3 and S4 are generated from S1, which has a base design optimized for minimum hardware resources. A time-memory tradeoff can be made in implementations where only the table of S1 is in memory, and the permutation to the other s-boxes is done at runtime, which is composed of fixed rotations. Minimal hardware resources and a Feistel design (same decrypt hardware, less data processed per round) can make Camellia more efficient than AES in dedicated hardware. The key schedule is more complex than AES, and it reuses the round function to generate key material.

Twofish s-boxes are made from 2 different permutations and key material. The permutations themselves are made from 4 fixed 4-bit s-boxes each. A time-memory -storage tradeoff can be made in implementations where only the tables of 4-bit s-boxes are stored in code, and the permutations are generated and stored in memory during key scheduling, where the s-boxes are generated. Twofish has a much more complex and expensive key schedule by design.

S-boxes and security

When it comes to the question of security, Camellia is a more modern cipher than AES, with a complex key schedule more resistant to related key attacks, but a more simple round structure which requires more rounds to meet its required security bound. Twofish has a very complex key schedule along with a complex round structure which requires 32-bit addition, limiting performance on platforms with only simple logical operations. Twofish was considered to be more secure than AES but lost out due to its slow key schedule and implementation issues due to 32-bit addition on non 32-bit platforms.

Because Twofish and Camellia are a completely different structure than AES, the way the s-boxes contribute to security is different. Round counts in all ciphers are chosen to keep known security properties within the margin defined by the key size. At this time, out of the 3 only AES is known to have a security level under any condition lower than the key size, and only in a related key model, and it is not a practical attack.

It is certainly possible than the use of additional s-boxes could have eliminated such an attack, but at the expense of an additional s-box, possibly making storage requirements on constrained platforms such as 8-bit microprocessors and smartcards substantially larger, which is quite small for AES when compared to other ciphers of similar security and performance on a variety of platforms.

There are multiple ways additional s-boxes could have been added to AES. You could have 2 s-boxes, one for odd rounds and one for even rounds. A different s-box could be used in the key schedule. You could have multiple s-boxes in each round like Camellia and Twofish. You could have a combination of these using 4 s-boxes, like 1 and 3 on odd rounds, then 2 and 4 on even rounds. If the s-boxes have similar or identical properties to the original, the full cipher would have similar or identical security against some attacks, and most likely superior security against some others.

The other problem with adding more s-boxes is that security proofs and analysis gets more complicated, using a single highly nonlinear s-box allowed initial analysis on Rijndael to use very simple and easy to analyze descriptions, which gave confidence in the algorithm under intense scrutiny. This same simple description is also one reason why people are looking for alternatives. S-boxes based on finite field inversion are also under scrutiny due to CCZ-equivalence, which may be exploited to reduce the complexity of attacks.

With 15 years since AES was chosen to replace DES, much of block cipher design has been focused on smaller faster designs as opposed to more secure designs, and on designs immune to side channel attacks, which have been the bane of many AES implementations. S-box table lookups are a problem for cache timing consistency, they can reveal plaintext or key material. Multiple s-boxes can make it more difficult to mount such an attack, but s-box free designs can eliminate them. Since the AES s-box is already as nonlinear as you can get with an 8x8 s-box, adding more s-boxes will not improve overall linear properties, only a larger s-box will do that, or addition of more nonlinear steps to the round function.

Conclusion

This question is similar to "If I add more pistons to an engine, will the car go faster?" My 6cyl car is much faster than my old V8, but its also turbo charged, and direct injected and the V8 was not, so there is more to a car than just the piston count of the engine. There is also more to a car than just speed, just as there is more to a cipher than just security.

Adding more s-boxes to an AES derivative will probably increase security, but since AES is still considered secure for use, even for top secret US government use, that is not a good use of resources. An improved key schedule will improve resistance to many attacks at the expense of performance, with less hardware and software resources required when compared to an additional s-box, and way less when compared to multiple s-boxes, unless it was done in the way the Camellia s-boxes are created, which are permuted from a single s-box.

Using maybe 2 or 4 different types of s-boxes and increasing the round count by 1 or 2 rounds would most likely result in the the best balance of security, performance, and implementation resources based on adding s-boxes alone. By different types I mean those with a more complex algebraic description or those without CCZ-equivalence, like the Skipjack s-box for example.

Answer 2

I think using two or more different s-boxes is ad-hoc design beleiving that the the security increases against differential/ linear probability or other attacks.

it has been mathematically proved that using distinct matrices (multi-diffusion rounds or so-called diffusion switching mode) in Feistel structure increases the number of active s-boxes and therefore higher immunity against differential and linear attacks or providing required security in less rounds.

CLEFIA is an example that uses diffusion switching mode. References:

The Provable Constructive Effect of Diffusion Switching Mechanism in CLEFIA-type Block Ciphers

Sony Develops "CLEFIA" - New Block Cipher Algorithm Based on State-of-the-art Design Technologies

On Feistel Structures Using a Diffusion Switching Mechanism