How 2 rounds in AES achieve full diffusion?

Question

I have read somewhere that 2 rounds is AES provide full diffusion. So I looked it up to find out what it exactly meant. In The Design of Rijndael page 41, section 3.5 and it states that:

Two rounds of Rijndael provide 'full diffusion' in the following sense: every state bit depends on all state bits two rounds ago, or a change in one state bit is likely to affect half of the state bits after two rounds.

How does that happen. I would say that it's related with the fact that MixColumns is MDS but why this is achieved in two rounds?

Answer 1

AES diffusion is taking cared of by 3 main functions:

• SubBytes
• Shift Rows
• Mix Columns

SubBytes works as a 8-bit S-box. Thus if one bit change, the 8 bits of the byte are likely to change. With this step, each bit of a byte depend of each other.

This modification on the byte is then translated through the state via Shift Rows (still 1 byte affected) and then through the column (we moved from 1 byte affected to 4 bytes affected).

With one round, we therefore impacted on 4 bytes.

By doing it once again we will be affecting $4 \times 4$ bytes or the full state due to the nice coverage provided by Shift Rows and Mix columns.

Thus after 2 rounds, each bit has an influence on the full state.

This could be summarized by the following image where $\star$ represent a modification of a bit (and then byte).