12
$\begingroup$

I was trying to understand the internal structure of AES (Advanced Encryption Standard)

The Standard order of steps within a round:

  1. Substitute Bytes
  2. Shift Rows
  3. Mix Columns
  4. Add Round Key

Substitute Bytes, Shift Rows & Mix Columns satisfies the two most important properties required for a secure cipher i.e confusion and diffusion

Substitute Bytes provides Confusion i.e. that each binary digit (bit) of the ciphertext should depend on several parts of the key.

Shift Rows along with Mix Column provides Diffusion i.e. if we change a single bit of the plaintext, then (statistically) half of the bits in the ciphertext should change

Changing the order of Step 1 and Step 2 won't have any effect. But to what extent can we change the order of other steps? Does it weakens the security of AES, and if so, how?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
14
$\begingroup$

Short answer

Changing the order of the operations does not weaken the security of $\mathop{AES}$ (nor does it increases it).

Long answer

Remark: While ShiftRows and SubBytes are commutative ($f\ g : A \rightarrow A,\ f \circ g = g \circ f$). They are not commutative MixColumns. Therefore changing the order of operations will not produce the same result. But this is not relevant because we are looking from the security point of view.

The order of the operations inside the round function does not matter. This can be shown by observing the propagation of the byte dependence over 2 application of the round function.

enter image description here

In this analysis I'm ignoring the key addition because this operation can be placed anywhere in between all the operations given some tweaking. Thus we can see that the diffusion of a difference is the same as the one in the original specifications. The main reason of this result is due to the strong alignment in Rijndael.

Also this is further explained in Chapter 3 and 5 of The Design of Rijndael by their implementors.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I know it's not necessarily part of the scope of the question asked, but do you have any details on why the creators of Rijndael/AES chose that order of operations? If the order doesn't matter and doesn't affect security, I wonder if alternative ordering of the steps might provide some significant performance benefit under certain architectures (despite not being strictly an AES implementation). $\endgroup$
    – Polynomial
    Oct 27, 2016 at 14:55
  • 4
    $\begingroup$ @Polynomial I did ask Joan about 3 hours ago. He told me that they had to chose an order and that another order would not change anything to the propagation of the dispersion after 2 rounds (such as 4th or 6th order). $\endgroup$
    – Biv
    Oct 27, 2016 at 14:57
  • 5
    $\begingroup$ He also mentioned the fact that the MixColumns had to be the last step so that you can apply it to the key and therefore have a similar structure for encryption and decryption (also explained in the end of Chapter 3 of his book). $\endgroup$
    – Biv
    Oct 27, 2016 at 14:58
  • $\begingroup$ Oh, nice. Wasn't expecting an answer straight from the horse's mouth, so to speak. That makes sense; I guess when the order doesn't matter outside a few constraints you just pick one and run with it. $\endgroup$
    – Polynomial
    Oct 27, 2016 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.