let's delve into aes and talk about you
know what's good about it how it works
and why it was judged good enough to be
the advanced encryption standard
so why aes is a yes what yeah why is aes
well why ryan diaz have you heard
of reindoll ryan doll no no okay so in
that perhaps slightly infuriating way i
managed to not say anything about how it
works in the last video at all
let's start with a few numbers that we
briefly mentioned in the last video
right aes is a
128-bit symmetric block cipher that
means it takes 128 bits of message and
it encrypts it into 128 bits of
ciphertext with some key now that key
can either be 128
192 or 256 bits and that gives you just
varying amounts of security right from
loads to ridiculously lows right in my
opinion all right so don't worry about
it if you if you find your browser's
using 128 bit that's okay these were
specified as part of the aas standard so
random had to adhere to this but just
think that we're taking 16 bytes that's
128 bits and we're doing something to it
that turns it into some ciphertext
and because this is an sp network we're
going to be doing some amount of
substitution or bringing in some
confusion and some amount of permutation
moving things around to add diffusion
you don't want just like the enigma
machine you don't want to have one bite
in one bite out because
that's got to be easier to analyze
and in historically of course it is
instead of having a long line of of
bytes or bits
like most
ciphers might arrange things aes likes
to arrange things in a grid a 4x4 grid
for 128 bit so we have our message which
is 128 bit that's 16 bytes as a 4x4 grid
every time i try and draw a grid it
always goes wrong so byte naught is
going to be in here and by one and by
two and by three and then four five six
seven says column major order so
actually what we're doing is we're
taking our 128 bit message and we're
just laying it out in this order like
this and then we're going to start doing
our sp network we're going to permute
we're going to substitute bytes and then
we're going to transform this into some
way where an attacker can't read what
the message used to be so there are a
few
different operations that aes will do
but remember that everything in aes
happens on this 4x4 grid all right so
what we're going to do remember we've
got the sp network we're going to have
substitution permutation and we're going
to add our key in as well at some point
so this is our plain text and we're
going to first bring in a part of our
key and we're going to perform an xor
operation right we remember we put in
our key
intermediate between the rounds to
um that's our secrecy right the rest of
the algorithm is fully published in
public then we're going to do our round
so that's going to be substitute bytes
then we're going to shift rows and then
finally we're going to mix columns
and this is going to be our substitution
and this is going to be our permutation
and finally at the end of each round
we're going to add our key add
our round key like this and then this is
going to be one round and the only thing
to mention is that the mixed columns is
in all arounds except for the last one
because this permutation has no effect
on the last round it just promotes the
output doesn't make doesn't make any
difference so it's exactly like this
except for this one is missing on the
last round when you've got 128-bit key
you have 10 of these rounds when you
have 192-bit key you have 12 of these
rounds and when you have a 256-bit key
you have 14 of these rounds but in all
other regard they're exactly the same so
this is also an xor down here add round
key we don't put the same key in every
time what we do is we take the original
key
and as i mentioned in the sp network
video we expand it using something
called a key schedule into different
round keys so this would be sort of key
naught perhaps this would be key one key
two and so on depending on which round
we were in and so there'll be a key
that's expanded for every round
um we won't talk in too much detail
about the key schedule it's quite simple
uh an effect it's just meant to be fast
mainly it just takes your your shorter
key and expands it sufficiently such
that you can put it in at these
different rounds that's an overview of
what aes does this is a much much much
better version i mean i can't stress
this enough a much much better version
than the one i designed or showed in my
sp network video right we're
substituting and then we're going to
permute and then we're going to mix in
our round key and we're going to do this
over and over again until we have a
cipher text so i guess the question then
becomes what happens here here and here
of interest what's particularly nifty
for me about
aes is that it doesn't use the same kind
of operations that you might expect so
exor of course happens everywhere in
cryptography but actually
all of the operations within aes
are essentially mathematical operations
on what we would call a finite field so
dave talked a little bit about galway
fields in his reed solomon video and the
answer is by using galwa field theory
over finite fields and doing lots and
lots of long divisions
and additions so a finite field or
galway field which are interchangeable
names
they
what you have in a field is you have
some some number of elements so let's
say all the numbers between naught and
ten for example right and you have
different operations you can perform on
that field so in reindeer we have a
galois field
of two to the eight elements and then in
this field we can do addition
subtraction
multiplication and division or x to the
minus one inversion the important thing
to remember about a finite field if we
don't go any further with the math at
all
is that two to the eight elements is a
is a byte right so each element in this
galwa field is just a byte so we start
with naught naught naught naught naught
naught naught we go all the way to one
one one one one one one and so there are
256
of these elements in this particular
finite field and the one take-home
message you need to know about this even
if you don't ever look at it again is
that whichever of these operations we do
we produce another element in this field
right we never leave the field we never
overflow we never underflow and go you
know into negative numbers or anything
there's no float representation or
anything like this if we take one of
these numbers and we add them to another
one we find a different one and if we
multiply them or inverse invert them or
divide we go to a different one right
which makes it quite nice for
implementing a cipher because a lot of
these have an opposite so for example
addition and subtraction undo each other
multiplication and inversion or dividing
they undo each other and we can move
around this field but we never actually
leave our eight bytes if we've got our
four by four byte representation of our
data path in aes this is our 128-bit
block we can perform operations on here
within this finite field and by the end
we'll still be in the finite field we
won't have gone over to 130 bits or 140
bits or some disaster like that all
right so we'll bring the diagram back
and with that in mind we will talk about
what each of these does substitute bytes
fatsar substitution box is literally a
lookup table it's a cleverly designed
lookup table they haven't just made this
up each byte is mapped to a different
byte based on a function in this field
but most importantly there's a few
there's a few things that they've done
to try and design it to be as
complicated as possible right so it's
very non-linear so it's very difficult
to kind of represent this as a
mathematical function exactly what it is
that it does in fact let's just do one
and then we can we can see right
so we've got our grid let's put this
here uh we've got our grid which i've
now drawn many times this is b0 this is
b1 all the way up to b 15. now what
we're going to do is we're going to take
this byte we're going to look it up in
our table and we're going to replace it
with a different one right so our
substituted byte like that and we're
going to do that individually for each
of these to make this function more
confusing it's been designed such that
there are no fixed points that means no
bite is substituted with itself so you
don't start with a 15 and end up with a
15 and there are no opposite fixed
points which means all the bits flip so
for example the opposite of 101.0 would
be 0101 right and this is for a whole
byte they don't exist in this it's been
designed that way so this substitution
box is really quite powerful and and
it's one of the reasons why this is a
really good algorithm as it happens also
it's just a lookup table so it's nice
and quick that's the first thing what so
we've substituted our bytes we've taken
our plain text we put in part of our
round key or this is our initial key and
then at the beginning around we'll make
some bite substitutions using os box
then we're going to shift the rows this
is really straightforward so we're just
going to take
the first row and do nothing to it
we're going to take the second row we're
going to move it one to the left so b1
goes all the way back over to here right
so we wrap around this moves this way
and this moves this way and this moves
this way and this obviously goes to the
end this row moves two so this goes to
here
this goes to here this goes round back
to here
and so on and this moves three right
which is another way of saying it moves
that way but you know so this one goes
all the way over to here this one goes
over to here and so and so on remember
this is going to be an iterative process
and what we want to do is move these
things around and permute them so if
this is our data path with our columns
by sharing bytes around the different
columns when we combine it with the
mixed column step which we'll do in a
minute you'll see that actually we're
mixing everything up so within just a
couple of rounds
everything is very very jumbled up and
that's obviously a really good thing
because it's going to be much much
harder to break right so we're just
taking bites and we're putting them in a
different place in this grid so that
brings us to mixed columns which goes
along with this right so now that we've
moved things into different columns what
we're going to do is we're going to take
this column here and we're going to mix
these right up we're going to take this
column and mix these right up and this
one and this one separately so this is a
column wise
operation so this bite has gone over to
here and then been mixed into this
column this one has gone over to here
and been mixed into this column so these
two operations together
are you know they're doing a good job of
jumbling everything up right will be my
technical way of putting it this is
going to be done using a matrix
multiplication so let's just turn it off
i'm going through a lot of your paper
today for some column let's say c naught
c one c two c three we're going to
multiply it as a vector by a matrix
right now we've dealt with major
multiplications occasionally computer
file we're not gonna spend too much time
talking about it now but this matrix is
two three one one one two three one one
one two three
and
three one one two now these numbers
they're big enough and jumbled enough
that something interesting happens here
but they're small enough that this is
quite fast right on harder
implementations and things like this if
this was 50 you made your algorithm
slower so if you remember from sort of
linear algebra a matrix multiplication
is going to produce another vector out
so it's going to replace this column
with another one and it's going to be a
combination of all of these so this one
times this one plus this one times this
one plus this one times this one plus
this one times this one and then we
repeat this process for each of the
values so we're taking bits and bytes
from all of these in this column
jumbling them up moving them around
shifting them and there is a reverse
inverse matrix that does the exact
opposite when you want to decrypt as
well so although this is doing a good
job of jumbling everything up we can
actually also undo it the only thing to
mention of course is this is not a
normal multiplication in the sense that
we're inside this finite field so our
add operation
is an xor and our multiplication
operation is a multiplication inside
this finite field right which is modulo
a polynomial and you know we'll we'll
sort of leave that for someone to look
into or we'll talk about it in some
extra bits so so i guess like once once
more from the top
um we take our plain text and we xor it
with the first part of our expanded key
and then we're going to repeat this
process over and over again so we're
going to substitute some bytes using our
nicely designed s box we're going to
shift the rows along and then we're
going to mix all the columns up so we're
going to substitute and then permute
our data in this grid
then each time we're going to add the
round key which in this case is xor and
then we're going to repeat this process
except for the last round where we don't
bother to mix the columns because it
doesn't really help us and then at the
end we add in our final round key and
that's the end
and out comes the 128-bit block of total
gibberish this can be described as kind
of a random permutation that is to say
it takes some input and it performs what
appears to be complete randomly
producing an output when in fact
actually obviously it's had quite a lot
to do with this key if you have the key
you can then undo it each of these steps
has an exact opposite step that we can
go back up through to undo this whole
process does this ever go wrong
you mean
uh how so well it just seems to be so
many stages and so many oh yeah that's
true
so that's a very good question because i
guess there's two answers to that
question one is technically no because
they have what we would call um test
vectors which are this is all zeros when
you put this in with this key this is
what you should get so you can test your
algorithm quite a lot before you would
put it into production um but in terms
of sort of security issues actually yes
right so if you get this implementation
wrong you can kind of undermine the
security of this whole cipher there have
been things like cache timing attacks
and side channel attacks where
bits of key have been leaked because
people have not given due care to how
this is implemented one of the neat
things about aes is because it's a
standard
it's now in cpu hardware so there are
aes instructions to perform one round to
perform a final round and things on an
intel and an amd chip and on others and
they are impervious to these kind of
attacks and they're also ridiculously
fast so if you're using as on a
well-equipped cpu with the right
instructions we can be talking gigabits
per second of encryption um which is you
know pretty good uh so that's why
something like bitlocker or some kind of
on-disk encryption you won't notice it
you click a file it's already decrypted
it and shown it to you before you can
sort of realize what's happened and it's
because of the speed of this kind of
stuff
well perhaps we'll talk a little bit
more about galois fields because i mean
i like the name so first first of all
please look up galois everest galwa on
wikipedia because he's fascinating
didn't he die in a jewel he died in a
jewel right having published three
landmark papers on finite fields and
polynomials and things right so i mean
i'm not a mathematician so i don't know
the whole history but this is this is a
guy