Chacha Cipher - Computerphile

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]

Channel: Computerphile

Views: 121,081

Rating: 4.9783783 out of 5

Keywords: computers, computerphile, computer, science, University of Nottingham, Dr Mike Pound, ChaCha, Cipher, Infosec, AES, Crypto, Cryptography

Id: UeIpq-C-GSA

Length: 13min 45sec (825 seconds)

Published: Fri Feb 19 2021