Can someone explain to me the relevance of the static matrix used for the mixcolumns operation in aes encryption.i.e the relevance of why the byte is multiplied by 2 + next byte multiplied by 3 + next byte +next byte

  • $\begingroup$ Not a programming problem. Flagged to move to crypto. $\endgroup$ – erickson Aug 2 '12 at 17:16
  • $\begingroup$ Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to software development (the topic of Stack Overflow), and being fully on-topic here. Please register your account here, too, to be able to comment and accept an answer. $\endgroup$ – Paŭlo Ebermann Aug 7 '12 at 17:16

Well, how that matrix works is important for the security properties of AES. To see why it is important, we need to consider state differences, that is, if we consider two different inputs to AES and how they both flow through the cipher, how does those two differ in the internal state of the cipher at various places.

The important property of the mixcolumn operation is that it is a Maximum Distance Separable (or MDS) operation. That is, if we consider two distinct inputs to a single column of the mixcolumn operation, and the two inputs differ in $A$ bytes, and if the two corresponding outputs differ in $B$ bytes, then $A+B \ge 5$.

This implies that if two consider two inputs to a single column of the mixcolumn, if those two inputs differ in a single byte (that is, $A=1$), then the two outputs will always have different values for each byte (that is, $B=4$).

If you go through how this applies to AES, that means that if round $I$, two encryptions has an internal state that differs in a single byte, then at round $I+2$, the two encryptions will have states that differs in all 16 bytes (and hence AES has wonderful avalanche).

More generally, this behavior allows us to prove strength against differential and linear attacks; in that any differential or linear characteristic will necessarily go through a large number of sboxes; the resulting probability that the differential/linear characteristic will survive all those sboxes is negligible.

All this may not be true (or, at least, would be considerably harder to prove), if we replace the mixcolumn operation with an operation that is not MDS.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy