The Rijndael S-Box design generates a permutation cycle of type $2+27+59+81+87$. What effect would replacing that permutation with a cycle of type $256$ have on the security of AES?
-
1$\begingroup$ I assume your question has an implicit "holding other cryptographic properties constant", since an sbox of [1,2,...,255,0] has cycle type 256, but would make a fairly poor sbox. You may want to make this explicit. $\endgroup$– Jack LloydCommented Jul 13, 2011 at 18:07
1 Answer
The security of a block cipher is, based on what we know, invariant to the permutation cycles of the S-box. This is because the values are always transformed (by a fixed function or a keyed function) before going through the S-box again in the next round. Furthermore, many S-boxes are functions not permutations (i.e., output size is different from input size), so the property does not apply.
The permutation cycles of the entire cipher (with respect to a fixed key) are of interest. I am aware of a number of papers that examine this for DES (see last paragraph of page 277 in Handbook of Applied Cryptography).
The AES S-box does have a design behind it, both in terms of the steps take to generate it and in terms of its structure with respect to linear/differential/algebraic attacks. If you maintained these properties and only modified the permutation cycles, the security should be equivalent.
There is some work on using permutation polynomials to create s-boxes that may have some further insight into whether it is generally a good or bad approach. However I am not familiar enough to comment.