The AES block cipher (14 min)

Over the years it became clear that DES
and triple DES are simply not designed for

modern hardware and are too slow. As a
result, NIS started a new process to

standardize in a new block cypher called
the Advanced Encryption Standard or AES

for short. Nis started it's effort in 1997
when it requested, proposals for a new

block cipher. It received fifteen
submissions a year later. And finally in

the year 2000, it adopted the cypher
called Rindall as the advanced encryption

standard. This was a cypher designed in
Belgium. We already said that it's block

size is 128 bits and it has three possible
key sizes. 128 bits, 192, and 256. Now,

the assumption is that the larger the key
size is, the more secure the block cipher

is as a pseudo random permutation. But
because it also has more rounds involved

in its operation. The slower the cipher
becomes. So the larger the key supposedly,

the more secure the cipher, but also the
slower it becomes. So for example, AES 128

is the fastest of these ciphers and AES
256 is the slowest. Now AES is built as

what?s called a substitution permutation
network. It's not a Faistl network.

Remember that in a Faistl network, half
the bit were unchanged from round to

round. In a substitution permutation
network all the bits are changed in every

round. And the network works as follows,
so here we have the first round of the

substitution permutation network, where
the first thing we do is we X or the

current state with the round key. In this
case the first round key. Then we go thru

a substitution layer, where blocks of Date
are replaced with other blocks based on

what the substitution table says. And then
we go through a permutation layer where

bits are permuted and shuffled around. And
then we do this again. We XR with an X

round key, we go thru a substitution
phase, and we're permute to dance around.

And so on, and so on, and so forth Until
we reach the final round where we x or

with the very last around key, and then
out comes the output. Now, and important

point about this design. Is that, in fact,
because of how it's built, every step in

this network needs to be reversible, so
that the whole thing is reversible. And so

the way we would, decrypt, essentially, is
we would take the output and simply apply

each step of the network in reverse order.
So we start with the permutation step, and

we have to make sure that step is
reversible. Then we look at the

substitution layer, and we have to make
sure this step is reversible. And this is

very different from DES. In DES, if you
remember, the substitution tables were not

reversible at all. In fact, they
map six bits to four bits. Whereas

here, everything has to be reversible,
otherwise it would be impossible to

decrypt. And of course the x or with the
round key is reversible as well. Okay? So

inversion of a substitution permutation
network is simply done by applying all of

the steps in the reverse order. So now
that we understand the generic

construction. Lets look at the specifics
of AS. So AS operates on a 128 bit block.

Which is sixteen bytes. So what we do with
AS is we write those sixteen bytes as a

four by four matrix. Each cell in the
matrix contains one byte. And then we

start with the first round so we X over
with the first round key and then apply a

certain function. That, includes
substitutions and permutations and other

operations on the state. And again, these
three functions that are applied here have

to be invertible so that in fact the
cypher can be decrypted. And then we xor

with the next round key and we do that
again. Again we apply the round function

and xor the round key. And we do that
again and again and again. We do it ten

times. Although interestingly in the last
round, the mix column step is actually

missing. And then finally, we XOR with the
last rounds key, and out comes the output.

Again, in every phase here, we always,
always, always keep this four by four

array. And so the output is also four by
four, which is sixteen bytes, which is 128

bits. Now the long key themselves of
course come from a sixteen byte AS key

using key expansion. So the key expansion
maps from a sixteen bytes AS key

into eleven keys, each one being sixteen
bytes. So these keys themselves are also a

four by four array that's XORed into the
current state. Okay, so that's the

schematic of how AES works. And the only
thing that's left to do is specify these

three functions, byte sub, shift row, and
mixed column. And those are fairly easy to

explain. So I'm just gonna give you the
high level description of what they are.

And, those interested in the details can
look it up online. So the way byte

substitution works, is literally it's one
S box containing 256 bytes. And

essentially, what it does is it applies
the S box to every byte in the current

states. So, let me explain what I mean by
that. So the current state is gonna be

this four by four, table. So here we have
the four by four table. And to each

element in this table, we apply the S box.
So let's call it the A table. And then

what we do is, essentially, for all four
by four entries, essentially, the next

step, Aij. Becomes the current step
evaluated at the look up table. So we use

the current cell as an entry, as an index,
into the look up table. And then the value

of the look up table is what's output.
Okay. So, that's the first step. The next

step that happens is a shift pro step,
which is basically just a permutation. So

essentially we kind of do a stick lick
shift on each one of the rows. So you can

see the second row is stick lick shifted
by one position. This third row is

[inaudible] shifted by two positions and
the third row is [inaudible] shifted by

three positions. And the last thing we do
is mix columns where literally we apply a

linear transformation to each one of these
columns. So there's a certain matrix that

multiplies each one of these columns and
it becomes, the next column. So these

linear transformation is applied
independently to each one of the columns.

Now, I should point out that, so far,
shift rows and mixed columns are very easy

to implement in code. And I should say
that the [inaudible] institution itself is

also easily computable, so that you can
actually write code that takes less than

256 bytes to write. And you can kind of
shrink the description of AES by literally

storing code that computes the table
rather than hardwiring the table into your

implementation. And in fact, this is kind
of a generic fact about AES, that if you

can have allowed no pre computation at
all, including computing the S box on the

fly. Then in fact you get a fairly small
implementation of AES, so it, it could fit

on very constrained environments where
there isn't enough room to hold,

complicated code. But of course, this will
be the slowest implementation, because

everything is computed now on the fly, and
as a result, the implementation,

obviously, is gonna be, slower than things
that were pre-computed. And then there is

this trade off. For example if you have a
lot of space, and you can support large

code. You can actually precompute quite a
bit of the three steps that I just

mentioned. In fact, there are multiple
options of pre-computation, you can build

a table that's only four kilobyte big. You
can build a table that is even longer,

maybe 24 kilobytes. So basically you will
have these big tables in your

implementation. But then your actual
performance is going to be really good,

because all your doing is just table
look-ups and XORs. You're not doing

any other complicated arithmetic. And as a
result, if you can do a lot of

pre-computation, these three steps here,
[inaudible] should. [inaudible] and mixed

columns can be converted just into a
number, a small number of table lookups

and some [inaudible]. All you can do is
just compute the S box, so now your

implementation would just have 256 bytes.
Hard coded The rest would just be code

that's actually computing these three
functions. The performance would be slower

than in the previous step but the code
footprint would also be smaller. So in

overall, there's this nice tradeoff
between code size and performance. So on

high-end machines, on high-end servers,
where you can afford to have a lot of

code, you can precompute and store these
big tables and get the best performance.

Whereas on low-end machines like eight
byte smart cards or think of like an eight

byte wristwatch, you would actually have a
relatively small implementation of AES.

But as a result of course it won't be so
fast. So here's an example that's a little

unusual, suppose you wanted to implement
AES in Javascript so you can send an AES

library to the browser and have the
browser actually do AES by itself. So in

this case what you'd like to, to is you'd
like to both shrink the code size, so that

on the network there's minimum traffic to
send a library over to the browser but, at

the same time, you'd like the browser
performance to be as fast as possible. And

so this is something that we did a while
ago essentially the idea is that the code

that actually gets send to the browser
doesn't have any pre computer table and as

a result is fairly small code. But then
the minute it lands on the browser, what

the browser will do is actually pre
compute all the tables. So in some sense

the code goes from just being small and
compact. It gets bloated with all these

precomputed tables. But those are stored
on the laptop, which presumably has a lot

of memory. And then once you have the
precomputed tables you actually encrypt

using them. And that's how you get the
best performance. Okay? So if you have to

stand in implementation AES over the
network, you can kind of get the best of

all worlds. Whereas, the code over the
network is small, but when it reaches the

target client, it can kind of inflate
itself. And then get the best performance

as it's doing encryption on the clients.
Now AES is such a popular block cipher,

now essentially when you build crypto into
products essentially your supposed to be

using AES, and as a result Intel actually
put AES support into the processor itself.

So since Westmere there are special
instructions in the Intel processor to

help accelerate AES. And so I listed these
instructions here. They come in two pairs,

aesenc and aesenclast. And then, there's aesekygenassist. So, let me explain

what they do. So, aesenc essentially
implements one round of AES. Namely, apply

the three functions in the XOR with the
round key. And aesenclast basically

implements the last round of AES.
Remember, the last round didn't have the

mix columns phase. It only had the subs
bytes and shift rows. And so that's why

the aesenclast does. And the way you
call these instructions is using 128 byte

registers which correspond to the states
of AES. And so you would have one register

containing the states and one register
containing the current round key. And then

when you call AES on these two registers,
basically, they would run one round of AES

and place the result inside of this XMM
one state register. And as a result if you

wanted to implement the whole AES. All you
would do is, call aesenc nine times. Then

you would call aesenclast one time. These
ten instructions are basically the entire

implementation of AES. That's it. It's that
easy to implement AES on this hardware

and they claim because these operations
are now done inside the processor not

using external instructions that are
implemented in the processor. They claim

that they can get a fourteen X speedup
over say an implementation that's running

in the same hardware but implementing AES without these special instructions. So

this is quite a significant speed up and
the facts are now lots of. Products that

make use of these special instructions.
And let's just say that this is not

specific to Intel, if you're in
[inaudible], and they also implemented

exactly kinda similar instructions in
their bulldozer architecture and further

and future architectures. Okay, so let's
talk about the security of AES. I wanna

mention just two attacks here. Obviously,
AES has been studied quite a bit. But the

only two attacks on the full AES are the
following two. So, first of all, if you

wanted to do key recovery, the best
attack, basically, is only four times

faster than exhaustive search. Which mean
that instead of a hundred and. 28 bits

key, really you should be thinking of AES.
Is 126 bit key. Cause exhaustive search,

really it's gonna four times faster than
it should. Of course due to the 126, it's

still. More time than we have to compute,
and this really does not hurt the security

alias. The more significant attack is,
actually, on AES-256. It turns out there's a

weakness in the key expansion design of
aes which allows for, what's called a

related key attack. So, what's a related
key attack? Essentially, if you give me

about two to the 100 input output pairs
for aes, but from four related keys. So,

these are keys that are very closely
related, namely key number one. Is just

one bit flip of key #two, which is just
one flip, bit flip of key #three, which is

just one flip bit flip of key #four. These
are very closely related keys, if you like

your [inaudible] distances very short. But
if you do that, then, in fact, there is a

two to the 100 attack. Now you should say,
well, two to the 100 is still impractical.

This is still more time than we can
actually run today. But nevertheless, the

fact that it's so much better than an
exhaustive search attack, it's so much

better than two to the 56, is kind of a
limitation of the cipher. But generally,

it's not a significant limitation, because
it requires related keys. And so, in

practice, of course, you're supposed to be
choosing your keys at random, so that you

have no related keys in your system. And
as a result, this attack wouldn't apply.

But if you do have related keys, then
there's a problem. So this is the end of

the segment, and in the next segment we're
gonna talk about more provably secure

constructions for block ciphers.