keeping my distance keeping our distance yep standing up for the first time this is a more
sort of moving around kind of a computer file um yeah yeah we're on campus we're
doing some recording anyway let's let's do a video i thought today we could talk about
a cool cipher that sees quite a bit of use and is i suppose i suppose one of the only
real current rivals in terms of its prevalence to aes and that's the cha-cha 20 cipher right
so it's not a dance but it kind of mimics a dance i guess is the idea
so this was written in about 2008 daniel bernstein wrote this one it's very cool very very elegant
very lightweight which makes it really useful on low powered devices and along with aes
or the advanced encryption standard that we've covered in a previous video
remember this is going to be an iterative process and what we want to do is move
these things around and permute them it's one of the only algorithms recommended for use in the
modern transport layer security 1.3 right which is the encryption that we use mostly on the web
so i guess a bit of background is that you know almost everything uses aes right and that's
because um nist ratified it as a standard and just everyone implemented it and and now everyone uses
aes now there's nothing wrong with aes as far as i can tell um the the attacks on aes have mostly
been theoretical they can't actually be applied at the scale necessary to break it most machines
have a library that supports aes and so browsers understand it web servers understand it
but the point is sometimes made that having just one algorithm isn't a fantastic idea because what
if someone incredibly smart like me releases a paper tomorrow um that completely breaks aes right
let's put aside the ludicrousness of that you know theoretically it could happen right not for me but
you know someone could find a mathematical weakness or some other weakness in aes that
we don't know about or some kind of attack that's very difficult to stop and if that happens we need
a backup algorithm right and currently one of the only you know major players in this space i guess
is cha-cha right there are other albums of course but this one's been a little bit tested and looks
pretty good now unlike aes cha-cha is a stream cipher right now in practice that doesn't make
a lot of difference in terms of implementation but basically um it uses what is essentially a
hash function to mix up the key and your number used wants and your block number producing random
key stream and that's used with xor to encrypt our data so if you remember what we had you know i'm
using a board today because you know the paper's not here we had some sort of stream cipher so this
is our key stream generator key stream generator or pseudo-random function or whatever i don't
think ksg is a real thing i've just written that down and then you have a key that comes in here
so this is your secret key which in the case of aes is 256 bits what will happen here we also put
in a nonce right which is a number used once and that's used to make sure that if you don't change
this key you can generate different key streams and that's quite important and we also put in
our block number or counter and that allows us to jump halfway through a file if we want to based on
this this iterates and produces a series of key bits so k naught k1 k2 and we xor that with our
message so m naught m one m two and out comes our ciphertext ciphertext one ciphertext two
subjects naught so this is in general how a stream cipher works feeds a specific
perhaps a char chart but the idea is that the encryption for decryption happened exactly like
this so if we want to decrypt this we just go this way so we just put our ciphertext in x
or it with the same key and out it comes so the question then is just simply what is it
that's interesting about what char char does in here how does it take these and turn them into
key streams this is the problem with i can't just tear up a piece of paper i have to
right so char char is a bit like a hash function in the sense that it takes a block of data and
it mixes it up and it uses that for its keystream so we have a block and we'll talk about what goes
in there in a moment but it looks a little bit like the aes block except it's bigger
so this is a 4x4 block and each of these is 32 bits right so in total this is 512 bits all right
so we're going to fill that with some data then we're going to put it through a big round function
so this is our round function and i've run out of space because this is the most ludicrous aspect
ratio of a thing i've ever seen so it comes out also with four by four also of the same size and
this is all mixed this is our mixed block and so this is essentially this but completely jumbled up
and then we add these two together right there we go and out comes our key stream bit so knot k1 and
these are going to come out in 512 bit blocks but it's not a block cipher because we just take that
key stream and we xor it with the message and so it's a stream cipher so what happens in this
round function well the cool thing about this round function is it only uses three operations
the implementation of aes is actually quite complicated i mean it's not in the sense that
a lot of it boils down to bit shifting and and all and things but mathematically aes is quite
complicated all that char chart does it's a sort of it's what we call an arx cipher so it's add
rotate and xor now add is mod 32 edition so basically you're just adding two integers together
and you don't carry any bits right so if it overflows it just wraps back around
xor is obviously xor we've covered this a lot before and rotate
is a bit shift and you wrap it back around so for example if we were wrapping around 001
and we were doing a rotate one to the left then we would i think actually in the paper using this
is the notation then we would see something like 0011 right which is where this one has
come over here and everything's shifted to the left this is a bit like the color blocks in the
aes video where everything kind of mixes up yeah it's a bit like that yeah but this is happening
on an integer or you know on a bit level for these bits are moving along and what that's going to do
is move ones and zeros from somewhere in these values to somewhere else in these values
which over time when you combine it with xor in addition it's going to start mixing up all of this
a lot right and that's kind of the idea you don't want to be able to reverse any of this process
because if you can you're going to be able to read what the key was like because the key goes in here
so what goes in here well there's this there's four constants because if you had zero key that
and this was all zero the output will be all zero that would be a problem so there's four constants
that come in here then you have 256 bits worth of key so key here is where i write a lot of k's
right these are the key bits and then down at the bottom we have the block number
which is sometimes 64 bits and the nonce here right which is this like this now sometimes it's
64 bits in the current standard you tend to do something like this where the nonce is a little
bit bigger right there's implementation reasons why you would change the size of these two things
so your secret key goes in here this is the number used once to make sure that your keystream
is nice and interesting and this is where in the stream we are in in our 512 bit chunks
so if you're watching a streaming movie and you want to skip the boring bits and go to the good
stuff right where you know the terrorists are taking over nakatomi plaza then you can set this
block to the right place and jump straight ahead right that's the idea okay so what happens in here
so we have these blocks right which start off obviously with our key in and end up being
totally mixed up and what we're going to do is we're going to do 20 rounds of mixing some of
the rounds we do in columns so we mix a b c and d and then we mix this column and then we mix this
column a b c and d in this column so sometimes we mix diagonals so it'll be a b c d or a b c
d and you know down with diagonals and the reason you do this is because you want to jumble up
the bits and bytes should we say between here in these columns but you also want to do it in
a diagonal so that bits over here affect bits over here effect bits over here and so you're this is
what you have you have good diffusion right which is the changes in in here propagates to changes
in everywhere right which makes it very hard to understand what's happened and break this cipher
so what happens well each of these is a quarter round so four of these this one this one this one
and this one will be one round four of these would be one round and we do eat we do one of
these and then one of these one of these and then one of these and we do that 20 times so 10 of each
um as far as i know attacks on on char char i've managed to get some information out at maybe eight
rounds right and it's currently operating at 20 rounds so and i'm you know that's off the top
of my head so the security margin is pretty high right so what happens in here well we have these
these are our integer words so we have a b c d right and then you have quite a
complicated process for each quarter round so the first thing you do is you take b
and you add it to a right like this then you take this from a and you come all the way over here
and you xor it with d this is just a start then you come in here and you and you rotate d
16 bits to the left and of course it wraps back round right then d comes in here and it's oops
summed with c right and then let's just finish the whole diagram like rather than walk through it so
this comes down here xored with b and then b is rotated 12. i should add i don't know it's off by
heart right because this is difficult to remember right then b comes in i'm going to run out of
sheet and then i'm going to have to start drawing on these plugs so a comes down here like this
yep then a just comes out here like so so a comes along here like this and is xor back again with d
d is rotated eight to the left then d comes in here and is summed again with c
and c comes out here b is xord c and then that's rotated come on draw the plug
this looks this looks like trouble if i draw on this right i've reached the end it's something
like this but this will look great when we do it in the video because you'll have animated
all this and it will look fantastic right even though i've totally botched up the ending let's
just finish that off actually i know what it is it's instagram format isn't it yeah yeah so
that's a sum right without carry that's an xor and that's a rotation so what's basically happening is
b is coming in here and being added to a and so those two are now affecting this xor with
d which is being rotated and affecting c and you see that this is going to propagate bits and bytes
around very very quickly and we're doing this over columns and then over diagonals and the result is
a very very good cipher right the there's a few positives to doing this over doing something like
aes right there are some negatives as well but basically the the nice thing about only using
add rotate and xor is that it always takes exactly the same amount of time to run this
there's no table lookups or clever polynomial division or anything like this that you have to do
there's no conditional branching which means that basically no matter what your key is if your keys
are zeros or it's half zeros it doesn't matter this will take exactly the same amount of time
so coding this in a safe way for a cryptography point of view is quite straightforward right
you know i'm sure my code wouldn't do a great job but you get the idea
with aes although it's not that difficult to get an implementation of aes that technically works
it can be quite difficult to make it but it's secure enough because things like the time
that it takes to go into the cache and the time it takes to develop certain operations
and power consumption things that you can leak little bits of information about what's going
on in the inner workings which can give the game away right but this isn't really an issue here
the other thing is that aes is helped somewhat by the fact that modern cpus have gallowa field
arithmetic built into them as actual instructions whereas chancellor doesn't need any of that so if
you have a very low powered or old device or a smart card or something that doesn't really have
clever instructions this is going to be very very quick right so it's only marginally slow of an
aes and that's on a system that was built to run aes as fast as possible right so it's pretty cool
um and it has a cool name when you started it you mentioned something about putting constants in
because if zeros yeah totally forgot to tell you what they were yeah okay so all right well let's
just quickly quickly we'll fix that shall we so yes i mentioned that in the at the beginning of
the block you have the key in here the nonce and the id inside the counter up here we have
constants now the reason the constants are there is just basically so that zeroes don't you know
completely break it um they're not a secret the constants are just a string the string is
expand 32 uh byte k all right so we've got four space counts so that's four
that's four and that's four right and then these get encoders ascii and stuck in here right and
that's enough my sleeve number so you remember that video we did where if these were sort of
weird numbers you'd think well hang on a minute where'd they come from are they some kind of back
door well no they're just a sentence like expand the first two by key which is what this does right
as long as it's something obvious you know they're just there to mix it up a bit they're not a secret
are you doing the chartres steps as you walk back and forth uh yeah i mean what
is a charger anyway i don't know some sort of dance let's not have me dancing on the internet
people don't need to see that this is a edited version of a cypher called salsa which is edited
i think of rumble and so on so there's lots of different algorithms along this theme shall we say
[MANUAL PUBLISH]