4
$\begingroup$

In the AES encryption process, there are various sub-operations, like SubByte, MixColumns, ARK etc. My question is which of these operations is more expensive? In a video lecture by Dan Boneh, it is mentioned that the lookup table implementation of AES is faster than the implementation where the MixColumns function is performed using finite field multiplication.

I do not find any information on how much faster it is? Also, is there any relation between the individual sub-operations in terms of individual CPU time?

Improve this question
$\endgroup$
5
  • $\begingroup$ Depends on context. Some CPUs have carryless multiplication instructions which can speed up MixColumns. Some CPUs outright have AES encryption/decryption instructions that perform an entire round of computations. $\endgroup$
    – Nayuki
    Dec 25 '20 at 18:02
  • $\begingroup$ Yes, I see that using AES-NI isa have instructions for whole round encryption and last round encryption. Can you comment on, which operation is faster? ARK or SubByte? @Nayuki $\endgroup$
    – Radium
    Dec 25 '20 at 18:27
  • $\begingroup$ It depends on what you're trying to measure: Number of logic gates, maximum latency path, silicon area... $\endgroup$
    – Nayuki
    Dec 25 '20 at 18:35
  • $\begingroup$ I am trying to find the comparative time complexity of a SubByte, ARK, and MixColumn operations. Maybe, all operations will be performed in an 8-bit architecture. @Nayuki $\endgroup$
    – Radium
    Dec 25 '20 at 18:48
  • $\begingroup$ Any sort of these 'how do the performance of these separate operations compare' are very implementation dependent (and often are dependent on other factors as well; there are often no good answer) $\endgroup$
    – poncho
    Jan 10 at 17:42
6
$\begingroup$

The table lookup implementations usually combine the SubBytes and ShiftRows steps with the MixColumns step.

Different implementations/hardware/etc make general statements impossible, but this paper gives some benchmarks and information on a table-lookup implementation.

It won't necessarily be quicker across all systems. As per this paper:

It must be noted, anyway, that using a large amount of memory for the look-up tables is too expensive for small systems, like for instance smart cards, and is considered unsafe, as monitoring the accesses to the look-up tables may in some cases allow to infer the key.

As an aside, another (better) way to speed up AES is to have the instructions built into the hardware

Improve this answer
$\endgroup$
4
$\begingroup$

If you are doing a software implementation, the MixColumns would take the longest because you have to do a multiply after pulling from memory and then putting it back. Generally speaking, in software you would use lookup tables for the naive approach, so everything that is not cached would be expensive. I say this is naive because it is susceptible to timing attacks, such as in this paper. The sbox will almost always be a lookup table in the "homework" problem type of implementation.

If you want to make an actual AES implementation in software, you must first understand how AES can be affected by timing and how caches do not run in constant time. You will like explicitly calculate everything.

If you have hardware, we look at expense a Joules, and that's not what anyone outside of device physics talks about. There's answers on this site where I talk about the power required for different choices. From the "software" point of view, if you have AES-NI instructions, there's no difference in cost of the steps because they are all abstracted for you.

Improve this answer
$\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.