To completely miss the point though, ChaCha's standard round count (20) makes its security margin significantly more than AES. To have a similar margin, eight rounds of ChaCha should be sufficient.
In my cryptology lecture, there were two lectures given by a guest lecturer, he was introduced by name, but nothing more. He talked a bit about the history and the ideas behind modern symmetric cryptography (we had been doing RSA and prime stuff before that). He mentioned ChaCha20 and Poly-1305, but mostly talked about DES and AES... Until: "Oh, and maybe I should mention that I am actually the designer of ChaCha20 and Poly-1305." Name of the guest lecturer? Daniel J Bernstein.
Lucky you, he also designed Curve25519 which is an alternative to RSA and is quickly accelerated in adopting for the likes of its smaller key sizes (128-bit curve25519 = 2048-bit RSA)
I can think of another 16 character constant string that might have been appropriate: ‘DanielJBernstein’. If artists can sign beautiful creations, why not mathematicians?
There will probably be people talking trash and complaining about something something egotistical something [insert your profanity of choice]. So I respect his choice. But on the other hand, maybe he could learn a thing or two from Linus Torvalds on dealing with morality disagreements...
Depending on your logic family, you may still have to do extra work to make this constant time or power. Mainly because carry chains will take different time to complete depending on values. But for a typical synchronous processor with constant clock rate, it's constant time.
I have a question, on the receiver's side, since there's no guarantee that they'll receive the blocks in order, how does it determine the block number for decryption?
@@Brainstorm4300 The transport layer protocol such as Transmission Control Protocol (TCP) would deal with putting the message in order before the decryption is performed.
Ohh finally! This one is my favourite, far simpler than AES but even faster (without hardware acceleration), if you are implementing any symmetric cipher (or crypto RNG) yourself go for this!
@@oscarsmith3942 ChaCha is far simpler and without risks of side attacks compared to AES, it can already do wonders as a crypto quality RNG with just 8 rounds! I'm more in favour of cryptography that's simpler and harder to screw up rather than forbidding everyone from ever getting into the field, practice is important and not every project has dire consequences if gotten wrong
3:51 When I were a stoont, we had blackboards which were wraparound flexible sheets on rollers. So you just pulled on them to roll on to a new section. Eventually you wrapped round again to the part you previously wrote on, of course, so you had to erase it anyway, but in the meantime it could be left visible as reference.
AES has stood as king of the hill for 27 years now… with the smartest people on earth trying to break it. So don’t hold your breath on this happening any time soon.
Most of this seems like it's just describing the process for converting any hash function into a stream cipher. The question becomes why use this as the hash function over something like SHA-256. This seems like it needs to be just as secure as any hash algorithm, because I assume one of the attacks we're protecting against is a known-plaintext block giving await the key for the rest of the stream, which would be possible if you reversed the hash... I assume this is faster than SHA-256, but speed can be a bad thing for hash algorithms, since it makes brute force reversal easier.
A few misconceptions: 1. A hash function has multiple meanings. In a hash table, for instance, all you expect is diffusion. The construct you expect for a *cryptographic* hash function is called a collision-resistant compression function. In the case of ChaCha, you don’t need that, because you don’t care about compression nor about collision resistance. Just diffusion. 2. Cryptographic hashes do try to be as fast as possible (while offering collision resistance). But their properties are only useful when the input is random. Thus hashes cannot be used for low-entropy inputs (less than 1 bit of entropy per bit), such as passwords. For those, we need to purposefully slow down a brute-force attack, by using a specific KDF such as Argon2.
Have you seen the peer to peer software Briar? Looks pretty cool for digital privacy especially journalists in the field because it supports communication over bluetooth and wifi, its all end to end encrypted and when connected to internet everything is routed through tor. I would really love to see Mike do a video on that to signal boost it hopefully to people that really need it!
Every cipher which is using look up tables for example AES (Rijndael) are suspectable to side channel timing attacks because they take variable time when doing look up however this is not the case with Chacha 20 because it takes constant time for XOR, Addition and Rotate
Besides "its shuffled around" its really obvious why this actually works. To understand cryptography first is to understand the importance of XOR. If you combine two bits you cant bias either without revealing information and the opposite of XOR is the same as the input. Put another way XOR given a random key and non-random plaintext givens the same distribution as the random key. You cant glean any information without the key. So with just XOR and a random key that is intractable (the key cant be easily brute forced.) You have a robust cipher. The problem is sharing random data is hard. The key needs to be predictable to trusted parties and appear completely random to everyone else.
Great video! Was just wondering about this cipher recently and why I was seeing it often in the product description for a few embedded security modules.
The main advantage over salsa20 is, that it runs very efficiently using SSE (2 of the bit rotates can be replaced by byte shuffles, since multiples of 8 are used): void round(m128i &a, m128i &b, m128i &c, m128i &d) { m128i R8 = {3, 0, 1, 2, 7, 4, 5, 6, 11, 8, 9, 10, 15, 12, 13, 14}; m128i R16 = {2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13}; m128i e; a = paddd(a, b); d = pxor(d, a); d = pshufb(d, R16); // rol 16 c = paddd(c, d); b = pxor(b, c); e = pslld(b); // rol 12 b = psrld(b); // rol 12 b = por(b, e); // rol 12 a = paddd(a, b); d = pxor(d, a); d = pshufb(d, R8); // rol 8 c = paddd(c, d); b = pxor(b, c); e = pslld(b); // rol 7 b = psrld(b); // rol 7 b = por(b, e); // rol 7 }
I have a background in Computer Science, but "oh, man", those operation diagrams are difficult to follow when programming. But, anyway, we wait for another episode of Dr. Mike and his outstanding topics about number and computing. Thanks, Computerphile and Dr. Mike!
Could you make a video about "ecs" or "Entity component Systems"? I wonder what the benefits of ecs are in compare to standard computing. I heard ecs is using a data oriented Architecture instead of an object oriented.
I have RFC 8439 compliant Chacha20 written in hand tuned PIC assembler. When run on a 64Mhz (16M C/s) PIC18 it hits the mid to high hundreds of KB/s throughput, almost 1MB/s. So I concur, it's very lightweight.
Most processors, even RISC processors have AES instructions, making it very, very fast to execute. It's easy to implement in hardware. Anything else will have a very high computing overhead. AES is literally 16 cpu instructions after loading the key and message into the registers.
What’s the reason for using the 4 constant blocks, and using 2 blocks for both the index (stream position) and nonce? Why not just use 4 blocks for the index and nonce each? Considering the 20 rounds of shuffling, it shouldn’t matter that most of the index (position) bits will initially be zero in most cases?
I made a system similar to this one but with a 256-long byte array and using each value as a pointer to an index in the array, so that changing the data changes where in the data will be changed next
I mean quantum computers are simply ripping through our current encryption algorithms so it's not hard to believe it will be cracked at some point in the future
Well, I like your Dr. Mike, of course! But you can watch this thing only for entertainment, if you don't go and put it to use afterwards. I know because while watching I remember having watched the bit on AES when it came out and although I completely understood it that time, I don't remember anything of it now. (disclaimer: I own the Schneier book for more then 20 years now)
hey. I know it's out of scope but why do not get someone professional to talk about TDD (testing technique), and advanced topics in embedded systems because I really love your channel. thanks in advance
are u next to the tv because the cypher called shasha ....maaan i know these cypher algos are kinda efficient but since punlic they r backdoors meant to be left or somthing you know the secure thing is a custom cypher
Since you mentioned the paper: do you actually use this paper for printing or is it left over stock from 30 years ago? Cause it looks like the paper I used on my needle printer in the 90‘s :-)
I am little bit confused about how NONCE works and how to use them in AES or ChaCha in this case. Right now, I used the key as a seed for RNG, thus I could get same output for both side. Or should I set this "seed for NONCE" up during key-exchange process?
The nonce is not a secret (unlike the 256bit key), just a source of randomness in the process, so that you can use the same 256bit key for more messages. so you randomly generate a nonce, use it during encryption, and send it along with the encrypted data.
@@franatrturcech8484 the way CTR and GCM modes work seems a bit weird to me. You should be able to reuse the IVs if your message is different if you encrypt the message too, but they only encrypt the iv+counter and then XOR the message, which is a problem.
Where do we save the nonce?? It is part of the key input. So we have to know it if we want to decrypt an encrypted stream! Is it saved with the output stream?
Sometimes when you’re facing a particularly difficult problem, you need to take a step back. And then a step forward. And then a step back. And now you’re chacha’ing. (h/t to the movie “Real Genius”)
Wait. So if you XOR some bytes by a key then XOR those bytes by the same key, you get the original bytes back out? Why did I never realize symmetric encryption is so simple?
Because it is vulnerable to bit flipping, and then you'll need a Message Authentication Code to garantee everything is correct. And even so, repeating your IVs is a problem, so that's why I believe the message should be encrypted too, and not only XORed with the IV + Counter as in CTR and GCM modes.
While not the fastest or most robust cipher, many computer scientists confidently assert the ChaCha as being real smooth.
See whatcha did there
that's a real smooth joke
If AES was broken that would be a turnaround
hahahahhaa, how Dr. Mike explains things is just amazing!. I can barely hold my cup of tea while enjoying his lectures.
To completely miss the point though, ChaCha's standard round count (20) makes its security margin significantly more than AES. To have a similar margin, eight rounds of ChaCha should be sufficient.
In my cryptology lecture, there were two lectures given by a guest lecturer, he was introduced by name, but nothing more. He talked a bit about the history and the ideas behind modern symmetric cryptography (we had been doing RSA and prime stuff before that). He mentioned ChaCha20 and Poly-1305, but mostly talked about DES and AES... Until: "Oh, and maybe I should mention that I am actually the designer of ChaCha20 and Poly-1305." Name of the guest lecturer? Daniel J Bernstein.
Lucky you, he also designed Curve25519 which is an alternative to RSA and is quickly accelerated in adopting for the likes of its smaller key sizes (128-bit curve25519 = 2048-bit RSA)
Too bad he's an asshole
I guess we were in the same lecture then. It was after the lecture that I looked him up and discovered that he was quite influential indeed.
@@sundhaug92 no that's you mate
@@y8fpe I linked my source, but I'm not seeing it here atm
I can think of another 16 character constant string that might have been appropriate: ‘DanielJBernstein’. If artists can sign beautiful creations, why not mathematicians?
When I saw it was a 16 character string I thought it was going to be "chacharealsmooth" and that's how it got its name. Slightly disappointed!
There will probably be people talking trash and complaining about something something egotistical something [insert your profanity of choice]. So I respect his choice.
But on the other hand, maybe he could learn a thing or two from Linus Torvalds on dealing with morality disagreements...
@@scheimong "Nvidia, ... F*@€ you!"
Wait? He has legs? I just assumed he was a torso attached to a server simulating humanity.
They clearly added more computing power.
Mike: KSG is not a real thing
My brain: "Kerbal Space Grogram"
"someone incredibly smart like me", lmao humble Mike
but is he wrong...
@@ethansimmons82 I'm now half-expecting the next issue of the Journal of Cryptology to publish a new paper by Mike...
1:43
now we all waiting for that paper drop. you know Mike just bought hella cha cha stocks too
Let's put aside the ludicrousness of that
So good.
Tiny nit: in the animations XOR is denoted with circled times ⊗ but the operator for XOR is circled plus ⊕.
Depending on your logic family, you may still have to do extra work to make this constant time or power. Mainly because carry chains will take different time to complete depending on values. But for a typical synchronous processor with constant clock rate, it's constant time.
There's Mike on the background.
*me:* click
Oh boy, it's Dr. Pound back again!
Aww yiss, take me to Pound town
Always my favourite videos
Very illustrative, thanks again. Mike, could you do a video talking about SHA-3 or the Keccak construction? It would be very helpful.
Yes I’d love to see this as well 👍
"Let's not have me dance on the internet; people don't need to see that"
I disagree; people definitely need to see that.
Exactly! We would love to see it!
I looked into chacha last semester for a project, ended up not using it but I'm happy our fav prof made a video on it! 😊
I have a question, on the receiver's side, since there's no guarantee that they'll receive the blocks in order, how does it determine the block number for decryption?
@@Brainstorm4300 The transport layer protocol such as Transmission Control Protocol (TCP) would deal with putting the message in order before the decryption is performed.
@@andrewanyplace Ah of course! Thank you!
Man, 'nonce' is a really unfortunate term to use for 'number used once' 😶🔫
thats exactly what i thought haha
Should be nuonce...
oh wait
I've got a non techie friend who is really sensitive to stuff like that, when I told him he was disgusted 🙃
@@nuthinnew Wait, explain: what offensive thing do I not know about?
@@LoganKearsley According to the urban dictionary it's slang for paeophile. I did not know about this meaning of nonce either
Ohh finally! This one is my favourite, far simpler than AES but even faster (without hardware acceleration), if you are implementing any symmetric cipher (or crypto RNG) yourself go for this!
Counter point: If you are implementing a symmetric cypher yourself, don't.
@@oscarsmith3942 ChaCha is far simpler and without risks of side attacks compared to AES, it can already do wonders as a crypto quality RNG with just 8 rounds! I'm more in favour of cryptography that's simpler and harder to screw up rather than forbidding everyone from ever getting into the field, practice is important and not every project has dire consequences if gotten wrong
Thank you, Dr Mike Pound!
Yes he's my favorite prof!
3:51 When I were a stoont, we had blackboards which were wraparound flexible sheets on rollers. So you just pulled on them to roll on to a new section. Eventually you wrapped round again to the part you previously wrote on, of course, so you had to erase it anyway, but in the meantime it could be left visible as reference.
Brady, a youtuber: "It's Instagram format"
Smart person not knowing what's he talking about: "yeah, yeah, yeah"
10:20
Maybe it's cause I was watching at 2x speed, but as a parent I felt about 95% confident that Dr. Pound has to pee.
Awesome one again! Please add a playlist with only Mike videos!
The ludicrousness of that...
Mike so has that paper ready to publish.
I think if I ever go back to school, I would love to study cryptography. Great explanation Dr. Pound!
I can see Mike secretly hopes AES is broken/superseded, so he can tell everyone to go "do the Chacha" for his job. XD
AES has stood as king of the hill for 27 years now… with the smartest people on earth trying to break it. So don’t hold your breath on this happening any time soon.
@@CharlesHepburn2 Oh, I totally get that... he'd just "hope" so he can go home early that day. ;)
Most of this seems like it's just describing the process for converting any hash function into a stream cipher. The question becomes why use this as the hash function over something like SHA-256. This seems like it needs to be just as secure as any hash algorithm, because I assume one of the attacks we're protecting against is a known-plaintext block giving await the key for the rest of the stream, which would be possible if you reversed the hash... I assume this is faster than SHA-256, but speed can be a bad thing for hash algorithms, since it makes brute force reversal easier.
A few misconceptions:
1. A hash function has multiple meanings. In a hash table, for instance, all you expect is diffusion. The construct you expect for a *cryptographic* hash function is called a collision-resistant compression function. In the case of ChaCha, you don’t need that, because you don’t care about compression nor about collision resistance. Just diffusion.
2. Cryptographic hashes do try to be as fast as possible (while offering collision resistance). But their properties are only useful when the input is random. Thus hashes cannot be used for low-entropy inputs (less than 1 bit of entropy per bit), such as passwords. For those, we need to purposefully slow down a brute-force attack, by using a specific KDF such as Argon2.
Have you seen the peer to peer software Briar? Looks pretty cool for digital privacy especially journalists in the field because it supports communication over bluetooth and wifi, its all end to end encrypted and when connected to internet everything is routed through tor. I would really love to see Mike do a video on that to signal boost it hopefully to people that really need it!
I looked it up you did not published a Paper the next day!
Just read about it yesterday while researching AES. Neat.
Thanks for bringing smiles to videos, and sir you are really "SMART",
Love from India....
Thanks for free sharing knowledge...
Every cipher which is using look up tables for example AES (Rijndael) are suspectable to side channel timing attacks because they take variable time when doing look up however this is not the case with Chacha 20 because it takes constant time for XOR, Addition and Rotate
Can we get a video about how a nonce works? Like do you need to keep a list of all previous numbers used so you don't use it again?
Besides "its shuffled around" its really obvious why this actually works. To understand cryptography first is to understand the importance of XOR. If you combine two bits you cant bias either without revealing information and the opposite of XOR is the same as the input. Put another way XOR given a random key and non-random plaintext givens the same distribution as the random key. You cant glean any information without the key. So with just XOR and a random key that is intractable (the key cant be easily brute forced.) You have a robust cipher. The problem is sharing random data is hard. The key needs to be predictable to trusted parties and appear completely random to everyone else.
Wow this cipher is real smooth
@3:48 ...and this concludes Mike's arm exercises for the year... 😂
Please, do a video to explain BIP-32 deterministic key derivation process. Would be amazing!
Great video! Was just wondering about this cipher recently and why I was seeing it often in the product description for a few embedded security modules.
The main advantage over salsa20 is, that it runs very efficiently using SSE (2 of the bit rotates can be replaced by byte shuffles, since multiples of 8 are used):
void round(m128i &a, m128i &b, m128i &c, m128i &d) {
m128i R8 = {3, 0, 1, 2, 7, 4, 5, 6, 11, 8, 9, 10, 15, 12, 13, 14};
m128i R16 = {2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13};
m128i e;
a = paddd(a, b);
d = pxor(d, a);
d = pshufb(d, R16); // rol 16
c = paddd(c, d);
b = pxor(b, c);
e = pslld(b); // rol 12
b = psrld(b); // rol 12
b = por(b, e); // rol 12
a = paddd(a, b);
d = pxor(d, a);
d = pshufb(d, R8); // rol 8
c = paddd(c, d);
b = pxor(b, c);
e = pslld(b); // rol 7
b = psrld(b); // rol 7
b = por(b, e); // rol 7
}
No Mike, we would like to see you dance.
This sounds like a threat lol
"Dance" we said.
😊 😊 🙏
thanks for sharing these videos. this series is such a delight!
I have a background in Computer Science, but "oh, man", those operation diagrams are difficult to follow when programming. But, anyway, we wait for another episode of Dr. Mike and his outstanding topics about number and computing. Thanks, Computerphile and Dr. Mike!
A Die Hard reference. Noice, smort!
Could you make a video about "ecs" or "Entity component Systems"? I wonder what the benefits of ecs are in compare to standard computing.
I heard ecs is using a data oriented Architecture instead of an object oriented.
This seems like it’d be very easy to implement in digital logic, which might be the point.
"Chacha" in Hindi means "dad's younger brother" ("dad's elder brother" is a different word).
So when I first read the title, I thought about my uncle.
I have RFC 8439 compliant Chacha20 written in hand tuned PIC assembler. When run on a 64Mhz (16M C/s) PIC18 it hits the mid to high hundreds of KB/s throughput, almost 1MB/s. So I concur, it's very lightweight.
Pound for pound, great explanation
Thank you Dr Mike Pound, love your videos!
While Rjndael cipher has a 256 bit version, the AES is defined as 128 bit block and key size.
don't be a coward. we ABSOLUTELY need a video of Dr Pound dancing on the internet. :D
"and it has a cool name" I'm sold.
The man, the legend ...
He is back
Nice explanation.
Suggestion: a video about the general pros and cons of stream and block ciphers.
Nowadays, people mostly use block ciphers in CTR (or GCM) mode, which is basically the same as stream ciphers. So there's no big difference anymore.
Most processors, even RISC processors have AES instructions, making it very, very fast to execute. It's easy to implement in hardware. Anything else will have a very high computing overhead. AES is literally 16 cpu instructions after loading the key and message into the registers.
You can make a pretty secure encryption algorithm using sha3 and xor.
What’s the reason for using the 4 constant blocks, and using 2 blocks for both the index (stream position) and nonce?
Why not just use 4 blocks for the index and nonce each? Considering the 20 rounds of shuffling, it shouldn’t matter that most of the index (position) bits will initially be zero in most cases?
I made a system similar to this one but with a 256-long byte array and using each value as a pointer to an index in the array, so that changing the data changes where in the data will be changed next
1:36 - why does this sound like he actually did break AES and is about to release the paper and this isn't hypothetical.... ☹️
I mean quantum computers are simply ripping through our current encryption algorithms so it's not hard to believe it will be cracked at some point in the future
I definitely got that feeling too. I guess we'll wait and see.
Fitting the process on one whiteboard is a real cha-cha-challenge.
Thank you! Gonna jump in to the editor and try to program this in JavaScript or Python idk
Featuring Dr Mike Pound and the last whiteboard marker in Nottingham
Welcome back Mike 😌
Well, I like your Dr. Mike, of course! But you can watch this thing only for entertainment, if you don't go and put it to use afterwards. I know because while watching I remember having watched the bit on AES when it came out and although I completely understood it that time, I don't remember anything of it now. (disclaimer: I own the Schneier book for more then 20 years now)
> *complains the board is vertical aspect*
> *runs out of hight*
13:27 Is there some kind of filter?
Close up of face check,
But where will we find an arrow?
Brady, rhymes with brilliancy
hey. I know it's out of scope but why do not get someone professional to talk about TDD (testing technique), and advanced topics in embedded systems because I really love your channel. thanks in advance
It seems to me like this would be very easy to implement in digital logic.
Woo hoo going to Pound Town!!
Imagine having Mike as your university teacher!
are u next to the tv because the cypher called shasha ....maaan i know these cypher algos are kinda efficient but since punlic they r backdoors meant to be left or somthing you know the secure thing is a custom cypher
Will you talk also SVD (singular value decomposition)?
Welcome back to the best presenter by far.
Please go back to the printer paper - the whiteboard is useless for viewers.
Especially with the anemic marker!
Welcome back Legend.😘
why to not use a more random constant like some cypher use a round constant base on Pi
You should cover Blowfish.
Cool, so how does the skipping of blocks work? because with a stream cipher you normally initialize "ksg" once right?
Since you mentioned the paper: do you actually use this paper for printing or is it left over stock from 30 years ago? Cause it looks like the paper I used on my needle printer in the 90‘s :-)
There's also coloured paper available in markets. It's a wood colour dye coated on it
Read Captcha on the title, came in and ended up staying haha
I like this Pound guy
So does ChaCha use perfect forward secrecy?
I'll be here the entire day waiting for that paper
This guy is Chacha(Father's brother is known as Chacha in Hindi) Computer
Can you make a video about side channel attack on RSA?
this is an awesome video and an awesome comment for the algorithm.
Yes it's Mike!!
Smarter than the average bear!
I am little bit confused about how NONCE works and how to use them in AES or ChaCha in this case. Right now, I used the key as a seed for RNG, thus I could get same output for both side. Or should I set this "seed for NONCE" up during key-exchange process?
The nonce is not a secret (unlike the 256bit key), just a source of randomness in the process, so that you can use the same 256bit key for more messages. so you randomly generate a nonce, use it during encryption, and send it along with the encrypted data.
@@franatrturcech8484 the way CTR and GCM modes work seems a bit weird to me. You should be able to reuse the IVs if your message is different if you encrypt the message too, but they only encrypt the iv+counter and then XOR the message, which is a problem.
A video about Dr Mike Pound dancing.... I'll watch that.
Yes, but Cha-Cha almost brought the Umbrella Academy to its knees.
Where do we save the nonce?? It is part of the key input. So we have to know it if we want to decrypt an encrypted stream! Is it saved with the output stream?
i think you would just send it along with the encrypted data, as nonce is generally not a secret (unlike the key).
Man like Mike!
So when is salsa video coming out??
7:12 Yeah... Nakatomi Plaza...
Sometimes when you’re facing a particularly difficult problem, you need to take a step back. And then a step forward. And then a step back. And now you’re chacha’ing.
(h/t to the movie “Real Genius”)
I thought that "board" was just a cupboard. Is Dr Mike a secret street artist?
Wait. So if you XOR some bytes by a key then XOR those bytes by the same key, you get the original bytes back out? Why did I never realize symmetric encryption is so simple?
Because the _real_ work is in getting the key.
Because it is vulnerable to bit flipping, and then you'll need a Message Authentication Code to garantee everything is correct. And even so, repeating your IVs is a problem, so that's why I believe the message should be encrypted too, and not only XORed with the IV + Counter as in CTR and GCM modes.
I dont know who coined the bame but ChaCha in hindi means uncle
For extra safety you could double-dutch it by rolling some cha cha over your aes
It would be cool if you had Bernstein in one of your videos!