5
$\begingroup$

I was examining how AES provides diffusion and noticed that indices of the shiftRows transposition step can be modeled as inputs/outputs of a 4x4 table:

`0123 4567 89AB CDEF -> 0123 5674 AB89 4567`

Where the input is the index of each byte of the 4x4 state, and the output is the destination index that the byte will be transposed to.

I was curious about the effect of changing the above mapping to one with strong cryptographic properties, like those found in this paper.

I have seen this question and this answer which discuss what purposes the shiftRows operation fulfills.

There is the requirement that each column should be spread evenly across the state, so as to ensure diffusion. I found that only certain S-Boxes in the above paper fulfill this property.

The first S-Box I found that does fit that criteria was the third S-Box from the second variation of the Hummingbird cipher (found in the appendix of the paper above). It looks like this:

0123 4567 89AB CDEF -> F458 9721 A30E 6CDB

If I understood the paper correctly, this mapping is among those that offer ideal differential, linear, and branch count properties. We can refer to this operation as shuffleBytes, as it's a generalization of shifting rows.

How would I go about calculating the branch count and active S-Boxes with AES using the proposed shuffleBytes operation in place of the shiftRows operation, with all the operations otherwise the same?

Is there some (obvious) reason this would be bad, assuming the transposition + mixColumns operations still ensures diffusion at least the same rate?

Addendum

After further testing, the complete diffusion over two rounds is only realized with certain configurations of bytes, and not in all cases. Maybe stacking a combination of multiple ideal S-Boxes over multiple rounds might be applied. But with just the one S-Box, diffusion does take longer then two rounds in some cases, so it probably won't be considered an improvement.

$\endgroup$
  • 2
    $\begingroup$ shiftrows is specifically to move bytes into the correct order for the next mixcolumns transformation, so that 2 rounds provides complete diffusion. It is probable other shift combinations exist that do this, I do not know if this is one of them, but it should not be hard to check $\endgroup$ – Richie Frame Jun 1 '16 at 21:08
  • $\begingroup$ @RichieFrame Right, the first two 4x4 S-Boxes I tried did not fulfill that requirement. The specific example of S-Box 3 from HummingbirdV2 does happen to move the bytes into the correct position so as to facilitate complete diffusion over the two rounds when combined with mixColumns. I did attempt to ensure that property was maintained. $\endgroup$ – Ella Rose Jun 1 '16 at 23:04
0
$\begingroup$

AES ShiftRows operations ensures that each new column contains one byte from one of the 4 old columns. Thus it achieves Full diffusion in 2 rounds.

You are right that there could have been other arrangement / shuffle of bytes to meet this criteria too. But if we analyze AES design, we will find that speed and memory requirement on all types of platforms were also given due attention in designing AES components. For example

  1. MixColumn Matrix values are kept to minimum possible, like 01,02 and 03, which are fastest to implement as 01 is element itself, 02 is just left shift by One 03 is Exclusive OR of 02 and 01

  2. Only one Sbox was used for substituting all state bytes

  3. RCons in key schedule were kept minimum possible with simple in values.

  4. The Shift Rows in 32 bit processor is just (i*8) left rotations of ith row where i=0,1,2,3. In case of 8bit processor, the first row elements remain unmoved and others are shifted based on index.

so if you try to do random permutation or some fixes shuffle bytes, you will end up needing more resources/time on some or all platforms.

But if you dont plan to run you AES variation on all platforms, then you can introduce your own platform specific operation (offcourse security of which still needs to be vetted by experts)

$\endgroup$

Your Answer

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

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