# Efficient AES - Use of T-tables

I'm really in trouble! I'm trying to understand how the T-tables in AES encryption work. But I don't know if I get the point. What I understood is that they are used to reduce the whole computation of the iteration of AES just looking at the T-boxes and the XOR operation. Now, what I got is that:

    State                 M Matrix
┏             ┓       ┏             ┓
┃ d4 e0 b8 1e ┃       ┃ 02 03 01 01 ┃
┃ bf b4 41 27 ┃       ┃ 01 02 03 01 ┃
┃ 5d 52 11 98 ┃       ┃ 01 01 02 03 ┃
┃ 30 ae f1 e5 ┃       ┃ 03 01 01 02 ┃
┗             ┛       ┗             ┛


I have my State matrix and M matrix composed by 4X4 bytes. Each t-table should receive in input one byte and give in output 4 bytes. Now, in order to create the t-tables i will have in the first table:

T0=(d4*02)+(d4*01)+(d4*01)+(d4*03)
(e0*02)+(e0*01)+(e0*01)+(e0*03)
(b8*02)+(b8*01)+(b8*01)+(b8*03)
(1e*02)+(1e*01)+(1e*01)+(1e*03)


Then the second table should be:

T0=(bf*03)+(bf*02)+(bf*01)+(bf*01)
(b4*03)+(b4*02)+(b4*01)+(b4*01)
(41*03)+(41*02)+(41*01)+(41*01)
(27*03)+(27*02)+(27*01)+(27*01)


And so on...until I'll have 4 tables. Am I right? Now...How can I use these tables?

(You should take a look at page 18 of FIPS 197 where it describes the MixColumns transform).

You're close. Swap the order of your matrices so that you have:

|02 03 01 01| |d4 e0 b8 1e|
|01 02 03 01| |bf b4 41 27|
|01 01 02 03| |5d 52 11 98|
|03 01 01 02| |30 ae f1 e5|


And then you compute the new columns. i.e. the new first column is:

|02 03 01 01| |d4|
|01 02 03 01| |bf|
|01 01 02 03| |5d|
|03 01 01 02| |30|


Which equals:

|02*d4 + 03*bf + 01*5d + 01*30|
|01*d4 + 02*bf + 03*5d + 01*30|
|01*d4 + 01*bf + 02*5d + 03*30|
|03*d4 + 01*bf + 01*5d + 02*30|


And so on.

Do you See the pattern in the sum? Each column in the matrix is multiplied by an element in the column and then they are summed. We can precompute these columns, and compute the above sum using 4 table lookups and 32-bit XOR operations.

The tables will be arrays of 32-bit values which look like this ("|" denotes byte concatenation):

T0[00] = 02*00 | 01*00 | 01*00 | 03*00
T0[01] = 02*01 | 01*01 | 01*01 | 03*00
...
T0[FF] = 02*FF | 01*FF | 01*FF | 03*FF

T1[00] = 03*00 | 02*00 | 01*00 | 01*00
T1[01] = 03*01 | 02*01 | 01*01 | 01*01
...
T1[FF] = 03*FF | 02*FF | 01*FF | 01*FF

T2[00] = 01*00 | 03*00 | 02*00 | 01*00
T2[01] = 01*01 | 03*00 | 02*00 | 01*00
...
T2[FF] = 01*FF | 03*FF | 02*FF | 01*FF

T3[00] = 01*00 | 01*00 | 03*00 | 02*00
T3[01] = 01*01 | 01*01 | 03*01 | 02*01
...
T3[FF] = 01*FF | 01*FF | 03*FF | 02*FF


Using four tables, you can compute the new state matrix with 16 table look-ups and 12 32-bit XOR operations.

Using T-Tables in software renders your AES open to sidechannel attacks. If you're doing AES in SW, compute it directly with shifts and xors. Don't use tables. Do use SBOX masking.

The Boyar-Peralta SBOX construction is a very good option. https://rd.springer.com/article/10.1007/s00145-012-9124-7

Here is a python implementation that shows the logical operations. Write a C version of this with parallel operations and you will have an efficient and side channel resistant version that runs in constant time and keeps the intermediate state in registers.

boyar_peralta_sbox.py

#!/usr/bin/env python2

# x is a list of 8 bits - the input to the sbox
def boyar_peralta_sbox(x):
s = [0,0,0,0,0,0,0,0]
y = dict()
z = dict()
t = dict()
x = list(reversed(x))

# Upper Transform

y[14] = x[3] ^ x[5]
y[13] = x[0] ^ x[6]
y[9] = x[0] ^ x[3]
y[8] = x[0] ^ x[5]
t[0] = x[1] ^ x[2]
y[1] = t[0] ^ x[7]
y[4] = y[1] ^ x[3]
y[12] = y[13] ^ y[14]
y[2] = y[1] ^ x[0]
y[5] = y[1] ^ x[6]
y[3] = y[5] ^ y[8]
t[1] = x[4] ^ y[12]
y[15] = t[1] ^ x[5]
y[20] = t[1] ^ x[1]
y[6] = y[15] ^ x[7]
y[10] = y[15] ^ t[0]
y[11] = y[20] ^ y[9]
y[7] = x[7] ^ y[11]
y[17] = y[10] ^ y[11]
y[19] = y[10] ^ y[8]
y[16] = t[0] ^ y[11]
y[21] = y[13] ^ y[16]
y[18] = x[0] ^ y[16]

# Middle Transform
t[2] = y[12] & y[15]
t[3] = y[3] & y[6]
t[4] = t[3] ^ t[2]
t[5] = y[4] & x[7]
t[6] = t[5] ^ t[2]
t[7] = y[13] & y[16]
t[8] = y[5] & y[1]
t[9] = t[8] ^ t[7]
t[10] = y[2] & y[7]
t[11] = t[10] ^ t[7]
t[12] = y[9] & y[11]
t[13] = y[14] & y[17]
t[14] = t[13] ^ t[12]
t[15] = y[8] & y[10]
t[16] = t[15] ^ t[12]
t[17] = t[4] ^ t[14]
t[18] = t[6] ^ t[16]
t[19] = t[9] ^ t[14]
t[20] = t[11] ^ t[16]
t[21] = t[17] ^ y[20]
t[22] = t[18] ^ y[19]
t[23] = t[19] ^ y[21]
t[24] = t[20] ^ y[18]

t[25] = t[21] ^ t[22]
t[26] = t[21] & t[23]
t[27] = t[24] ^ t[26]
t[28] = t[25] & t[27]
t[29] = t[28] ^ t[22]
t[30] = t[23] ^ t[24]
t[31] = t[22] ^ t[26]
t[32] = t[31] & t[30]
t[33] = t[32] ^ t[24]
t[34] = t[23] ^ t[33]
t[35] = t[27] ^ t[33]
t[36] = t[24] & t[35]
t[37] = t[36] ^ t[34]
t[38] = t[27] ^ t[36]
t[39] = t[29] & t[38]
t[40] = t[25] ^ t[39]

t[41] = t[40] ^ t[37]
t[42] = t[29] ^ t[33]
t[43] = t[29] ^ t[40]
t[44] = t[33] ^ t[37]
t[45] = t[42] ^ t[41]
z[0] = t[44] & y[15]
z[1] = t[37] & y[6]
z[2] = t[33] & x[7]
z[3] = t[43] & y[16]
z[4] = t[40] & y[1]
z[5] = t[29] & y[7]
z[6] = t[42] & y[11]
z[7] = t[45] & y[17]
z[8] = t[41] & y[10]
z[9] = t[44] & y[12]
z[10] = t[37] & y[3]
z[11] = t[33] & y[4]
z[12] = t[43] & y[13]
z[13] = t[40] & y[5]
z[14] = t[29] & y[2]
z[15] = t[42] & y[9]
z[16] = t[45] & y[14]
z[17] = t[41] & y[8]

# Bottom Transform
t[46] = z[15] ^ z[16]
t[47] = z[10] ^ z[11]
t[48] = z[5] ^ z[13]
t[49] = z[9] ^ z[10]
t[50] = z[2] ^ z[12]
t[51] = z[2] ^ z[5]
t[52] = z[7] ^ z[8]
t[53] = z[0] ^ z[3]
t[54] = z[6] ^ z[7]
t[55] = z[16] ^ z[17]
t[56] = z[12] ^ t[48]
t[57] = t[50] ^ t[53]
t[58] = z[4] ^ t[46]
t[59] = z[3] ^ t[54]
t[60] = t[46] ^ t[57]
t[61] = z[14] ^ t[57]
t[62] = t[52] ^ t[58]
t[63] = t[49] ^ t[58]
t[64] = z[4] ^ t[59]
t[65] = t[61] ^ t[62]
t[66] = z[1] ^ t[63]
s[0] = t[59] ^ t[63]
s[6] = 1-(t[56] ^ t[62])
s[7] = 1-(t[48] ^ t[60])
t[67] = t[64] ^ t[65]
s[3] = t[53] ^ t[66]
s[4] = t[51] ^ t[66]
s[5] = t[47] ^ t[65]
s[1] = 1-(t[64] ^ s[3])  # inverter
s[2] = 1-(t[55] ^ t[67]) # inverter

# bit reverse to render LE
return reversed(s)

for i in range(16): # Test the function.
for j in range(16):
xs = (i*16)+j
x = [((xs >> shft) & 1) for shft in range(8)]
s = boyar_peralta_sbox(x)
ss = 0
for place,bit in enumerate(s):
ss = ss + (bit << place)
if (i== 15) and (j == 15):
print "%02x" % ss
elif (j==15):
print "%02x," % ss
else:
print "%02x," % ss,


This outputs the sbox..

# python2 boyar_peralta_sbox.py
63, 7c, 77, 7b, f2, 6b, 6f, c5, 30, 01, 67, 2b, fe, d7, ab, 76,
ca, 82, c9, 7d, fa, 59, 47, f0, ad, d4, a2, af, 9c, a4, 72, c0,
b7, fd, 93, 26, 36, 3f, f7, cc, 34, a5, e5, f1, 71, d8, 31, 15,
04, c7, 23, c3, 18, 96, 05, 9a, 07, 12, 80, e2, eb, 27, b2, 75,
09, 83, 2c, 1a, 1b, 6e, 5a, a0, 52, 3b, d6, b3, 29, e3, 2f, 84,
53, d1, 00, ed, 20, fc, b1, 5b, 6a, cb, be, 39, 4a, 4c, 58, cf,
d0, ef, aa, fb, 43, 4d, 33, 85, 45, f9, 02, 7f, 50, 3c, 9f, a8,
51, a3, 40, 8f, 92, 9d, 38, f5, bc, b6, da, 21, 10, ff, f3, d2,
cd, 0c, 13, ec, 5f, 97, 44, 17, c4, a7, 7e, 3d, 64, 5d, 19, 73,
60, 81, 4f, dc, 22, 2a, 90, 88, 46, ee, b8, 14, de, 5e, 0b, db,
e0, 32, 3a, 0a, 49, 06, 24, 5c, c2, d3, ac, 62, 91, 95, e4, 79,
e7, c8, 37, 6d, 8d, d5, 4e, a9, 6c, 56, f4, ea, 65, 7a, ae, 08,
ba, 78, 25, 2e, 1c, a6, b4, c6, e8, dd, 74, 1f, 4b, bd, 8b, 8a,
70, 3e, b5, 66, 48, 03, f6, 0e, 61, 35, 57, b9, 86, c1, 1d, 9e,
e1, f8, 98, 11, 69, d9, 8e, 94, 9b, 1e, 87, e9, ce, 55, 28, df,
8c, a1, 89, 0d, bf, e6, 42, 68, 41, 99, 2d, 0f, b0, 54, bb, 16


T-table is an optimization for AES on 32-bit platforms introcuded by the designer of AES and explained in their book: J. Daemen and V. Rijmen, The Design of Rijndael, Berlin, 2002, p.56-59. A similar further optimization is feasible which is done in my AES C-code of 2003 (http://www.mokkong-shen.privat.t-online.de/).

• Link does not exist – hola May 6 '19 at 2:04

You can use one table instead of four tables, as the 2nd table is the first rotated by one byte and so on.