# Rijndael S-Box Permutation Group

Does the AES S-Box belong to the group of alternating permutions: A_{n} ?

How does an identity S-Box effect the security of the algorithm?

-

I believe Yuval is correct: the S-box is odd.

Much of the security in block ciphers comes down to the S-box design. When the NSA got a hold of DES back in the 70s, they altered the S-boxes without comment. Paranoids thought surely the NSA had purposely added a backdoor to DES, but later we figured out that they had actually improved the cipher by making it more resistant to differential cryptanalysis (the NSA had already discovered differential cryptanalysis, but we didn't know about it until years later).

If you lobotomize AES's S-boxes the cipher becomes nearly-linear or, worse, entirely linear. It is then trivial to break. In fact, in cryptography courses I will often give the class a DES or AES with trivial S-boxes and have them discover the key from plaintext-ciphertext pairs. If you make the DES S-boxes the identity function (it's actually 6-bits to 4-bits, so you do something that makes it equivalent to the identity function) you can discover the 56-bit DES key from a single plaintext-ciphertext pair. It boils down to a 64x56 matrix over GF$(2^{64})$ that has full rank.

Some people have criticized the simplistic construction of the AES S-boxes saying that a more intelligent design would have dispensed with the scary algebraic attacks we saw around 2003 by Courtois et al.

-

For your first question, as far as I can remember the S-box is a product of 127 transpositions, and so an odd permutation.

For your second question, without the S-box, the entire cipher is linear.

-

Well, it's not too hard to write a program to compute the cycle structure of the S-box, the output I got is:

cycle starting with 00 has length 59

cycle starting with 01 has length 81

cycle starting with 04 has length 87

cycle starting with 0b has length 27

cycle starting with 73 has length 2

(we have them all). So now you can tell whether the permutation is even or not (can you?).

If the S-box were the identity, the whole encryption would come done to an affine transformation, essentially. Think about why this is not such a good idea.

-