2
$\begingroup$

In AES, the MixColumns operation involves a linear transformation from GF(2^8)^4 to GF(2^8)^4. The branching factor for this transformation in the original AES is 4, and it is considered secure against differential cryptanalysis with 4 rounds, where the differential probability falls below 2^(-128).

If we replace this linear transformation with a linear transformation having a branching factor of 3, how many rounds do we need to fall the differential probability below 2^(-128)?

$\endgroup$

2 Answers 2

2
$\begingroup$

The full answer will depend on the exact diffusion pattern and the exact pattern of nonzero entries in the diffusion matrix.

My answer here uses the fact that the full weight distribution of MDS codes are known to address this question.

Another answer with more details here.

Edit: I think you need to play around with the concept to understand it better, i.e., it will depend on the exact pattern of the three nonzero bytes since a whole column is not turned on. There is a nice image in this answer that describes what happens as a combination of the shiftrows and mixcolumns for the branch number 4. So try to think of "worst case" and "best case" diffusion when it is actually 3.

Have fun!

enter image description here

$\endgroup$
2
  • $\begingroup$ thank you for answering! and could you tell me finally at least how many rounds do we need in order for the differential probability to fall below 2^(-128) when we set branch number to 3? $\endgroup$ Jul 6, 2023 at 13:42
  • $\begingroup$ @HarutoKimura The answer seems to have been changed according to your comment. Does that sufficiently answer the question? If so please accept one of the answers! $\endgroup$
    – Maarten Bodewes
    Apr 2 at 0:43
2
$\begingroup$

Well, here is a potential 1-round differential with 4 active sboxes; the differential starts with

+-+-+-+-+
|*| |*| |
+-+-+-+-+
| | | | |
+-+-+-+-+
|*| |*| |
+-+-+-+-+
| | | | |
+-+-+-+-+

(where * designates the active matrix locations; that is, the bytes where the differential is nonzero).

The bytesub doesn't change the differential (other than being the 4 active sboxes)

The shiftrow leaves the differential unchanged (the top row is left alone; the lower active row shifts by two, leaving the same bytes active)

The active columns both see a |X| |X| | differential; with a branching factor of 3, this may result in another |X| |X| | differential (and whether it can would depend on the actual pseudo-MDS).

And, the final addroundkey also leaves the diffential alone, resulting in the same differential we started with.

Again, the existence of this differential is consistent with everything you suggested; whether it is actually possible (again) would depend on the mixcolumns pseudo-MDS.

Assuming that the best long term differential in this modified AES is to concatenate this 1-round differential, and we don't have to worry about multiple trails or partial differentials (I don't have a proof of either; the second assumption sounds fishy to me), then we get $4r$ active sboxes after $r$ rounds; 5 rounds would give us 20 active sboxes, which appears to be sufficient.

However, given the uncertainties in the above logic, it would appear to be prudent to assume it is somewhat larger if you are using this as a security assumption.

$\endgroup$

Your Answer

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

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