I am interested in the following snippet from the paper New Impossible Differential Attacks on AES.

Analysis of Steps 3–4 of the 7-Round Attack in the 8-Round Attack

The most time consuming steps of the new 8-round attack are Steps 3–4 of the 7-round attack. This step is repeated $2^{128}$ times, where each time the attacker has to analyze $2^{57.7}$ pairs under $2^{64}$ possible subkey guesses. However, the time complexity of these steps can be further reduced.
 We observe that if $\Delta^{MC}_{A_{4,SR}(Col(0))}$ has a zero difference (recall that the attack is repeated four times, once for each possible shifted column), and if $x^{MC}_{4}$ has eight bytes with a zero difference, there are $2^8 - 1$ possible differences in each of the two columns of $x^{MC}_{4}$. As there is a difference only in two bytes of each column, we deduce that there are only $2^{16} \cdot (2^8 - 1) \approx 2^{24}$ different pairs of actual values in the two active bytes in the pair (rather than $2^{32}$). Thus, for $x^{MC}_{4,SR^{-1}(Col(2,3))}$ there are $2^{96}$ possible pairs of intermediate encryption values which satisfy the required differences. As we are dealing with the actual values, we can partially encrypt these values through the $\text{SubBytes}$ operation, and the following $\text{ShiftRows}$ operation and $MC$ (applied to Columns $(2,3)$ of $x^{SR}_5$). Given the value of $k_{5,Col(2,3)}$, the attacker is able to further compute the actual values which enter the $\text{SubBytes}$ of round 6, and its outputs.

Where does the number $2^8-1$ come from? I think it should be $(2^8-1)^2$.



Your Answer

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