2
$\begingroup$

From what I've looked up on various AES projects, the impression I get is the lookup table is hardcoded with the values from this Wikipedia entry page:

https://en.wikipedia.org/wiki/Rijndael_S-box

Am I correct in this assumption or is the lookup table on that page just for initialization and the table gets updated once further rounds are done in AES?

$\endgroup$

2 Answers 2

5
$\begingroup$

When doing an implementation based on tables, yes, it is customary to hardcode the table. Some extra notes:

  • Usual table-based implementations of AES merge the S-box application step ("SubBytes") with the subsequent linear operation ("MixColumns"). In that case, the hardcoded table has 256 entries of 32 bits each (and some implementations use four distinct tables to merge "ShiftRows" as well, in order to avoid computing rotations).

  • In some languages where there is an explicit initialization step, such as Java or C#, it is customary to use it to recompute the tables instead of hardcoding them; this makes the source code clearer and the binary size smaller, at the expense of some extra CPU cost when first using the code in the application. You can find an example of that in BoarSSL, a C# SSL library (used to serve as test system for BearSSL, which is written in C); the table building is done in the static class initialization code (lines 326 to 430).

Not all AES implementations are based on tables, though. In fact, using lookup tables is problematic because of cache attacks (memory accesses at addresses that depend on secret data may leak information based on how memory caches in the CPU are impacted). "Constant-time" implementations avoid making such accesses, and instead will evaluate the S-box with non-table operations. For these, the algebraic structure of the S-box definition is very convenient, because it helps making a more efficient circuit. In 2009, Boyar and Peralta have worked out a nice circuit of boolean gates that evaluates the AES S-box in 115 boolean operations; it has been used in a bitslice context by Käsper and Schwabe to make a very efficient and constant-time implementation of AES (in CTR mode): their code is not only robust against cache attacks, but it is also about twice faster than classic AES implementations that use tables.

For more information on constant-time cryptographic implementations, see this page.

$\endgroup$
0
3
$\begingroup$

Yes, the lookup table does not change throughout the algorithm. If you check the AES algorithm description, you'll see that the table is only read and never written.

(Obligatory caveat: implementations based on lookup tables can be vulnerable to cache timing attacks)

$\endgroup$

Your Answer

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

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