1
$\begingroup$

I am looking into an article about 32bit CPU/MCU software implementation of AES and there are some weird changes over there. Like shift-rows. It seems that the shift-rows in the 32bit implementation is shift columns instead.

So my guess is that the 32bit implementation returns different output than the 8bit implementation (the original).

Can you correct me ? or at least explain why it is still equal ?

The article : "Efficient Software Implementation of AES on 32-Bit Platforms"

Improve this question
$\endgroup$
8
$\begingroup$

So my guess is that the 32bit implementation returns different output than the 8bit implementation (the original). Can you correct me ? or at least explain why it is still equal ?

Of course, it's equal. The AES function (for a specific plaintext, key) is well defined; and if you generate any other result, you're not doing AES correctly.

Of course, while processing, the implementation may decide to lay things out in a different order than what you might naively expect; as long as it generates the same final output, all is well (and, in fact, that is what they did)

It seems that the shift rows in the 32bit implementation is shift columns instead.

No, in their implementation, they decided to lay the 4x4 matrix in memory so that a 32 bit value contains the 4 bytes in a specific row (and not a column). That is, the matrix is 'transposed' compared to the representation you would normally expect. This means that a 'shift row' operation involves rotate operations within the individual 32 bit values (or three of them; the top one remains unchanged), and that the 'mix columns' operation involves logical operations over all 4 32 bit row values.

They did that because doing that made things somewhat more efficient for them than the alternative ordering. As long as they handle the plaintext->matrix, the matrix->ciphertext operations correctly, and the transpose the key schedule bytes appropriately, everything works precisely as expected. At every point, the bytes in their transposed state are precisely the same model as the corresponding bytes in the (nontransposed) AES state.

Improve this answer
$\endgroup$
21
  • 1
    $\begingroup$ @VivekanandV: not more secure; more efficient. OpenSSL combines the subbytes, mix columns and shift rows into their tables, and so a single lookup does all three. $\endgroup$ – poncho May 1 '20 at 3:45
  • 1
    $\begingroup$ @VivekanandV: that looks like an attempt; however it's not perfect (because you can still task switch between the prefetch256t() and the actual read (with the cache possibly being flushed then), hence leaking some data). $\endgroup$ – poncho May 2 '20 at 4:07
  • 1
    $\begingroup$ @VivekanandV: again, that would be limited, as different CPU cores (which run the different threads) share the same L2 cache. What it would provide some protection is that the other thread wouldn't be exactly certain where the AES thread is during the processing stage; however I wouldn't want to depend on that... $\endgroup$ – poncho May 2 '20 at 12:41
  • 1
    $\begingroup$ @VivekanandV: yeah, I wrote up an AES implementation that tried to avoid any LUTs (instead, using logical, arithmetic operations and shifts for everything); what I ended up with ran about 10x slower than OpenSSL. I didn't think anyone would be interested, so I never published... $\endgroup$ – poncho May 2 '20 at 13:38
  • 1
    $\begingroup$ @VivekanandV: well, assembly would rather foil your 'a run-everywhere implementation'. In addition, you don't know nearly as much about the CPU microarchitecture as the compiler writers do, and so (until you learn a lot more) your assembly code will likely run slower, unless you take advantage of instructions the compiler doesn't have access to, such as AVX or NI. Still, both have already been done; if you want to learn, that's a viable option; if you just want a fast AES implementation, you can google for a better implementation that what you can write at this point in your learning $\endgroup$ – poncho May 2 '20 at 15:00

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.