AES: How to Design Secure Encryption
Vložit
- čas přidán 22. 05. 2024
- In 1997, a contest began to develop a new encryption algorithm to become the Advanced Encryption Standard. After years of debate, one algorithm was chosen as the AES. But how does AES work? And what makes for a secure encryption algorithm?
***
Spanning Tree is an educational video series about computer science and mathematics. See more at spanningtree.me
To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.substack.com/
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.
***
0:00 The Contest
1:02 Encryption
3:57 Confusion and Diffusion
5:44 Block Cipher
6:55 KeyExpansion
7:34 AddRoundKey
8:14 Substitution Cipher
8:55 SubBytes
11:30 MixColumns
12:53 ShiftRows
13:21 The Algorithm
It would be really interesting to explain some of the candidates that didn't make it. For example show why some of the rejected algorithms weren't secure.
The remaining 5 were all considered "secure enough". Rijndael was the winner for simplicity, speed and hardware/software friendlyness. Serpent was chosen as backup since it resembles DES in its design (but uses 32 rounds, making it pretty slow), as it mitigated the risk of choosing Rijndael (with GF(2^8) arithmetic, relatively unstudied in the early 2000s). RC6, Twofish and the last one I can't remember were all also fine, but not preferred.
@yuvalne Chacha is much newer. From NIST: "The AES finalist candidate algorithms were MARS, RC6, Rijndael, Serpent, and Twofish". The AES competition started in 1998 and finished in 2001. Salsa was developed in 2005, and Chacha was created in 2008.
Runner-ups aren't created a decade after the competition. That's not how time works.
It would be particularly nice to see a similar animation of Serpent. That algorithm was actually considered MORE secure than Rijndael, but it was slower to run.
@@dascandy Also Chacha is a stream cipher, which works in a completely different way. Essentially, it's a cryptographically secure pseudorandom number generator that you seed with the key and a nonce (number used once), and it generates arbitrarily long random bit sequences. The actual encryption is just a XOR of the Chacha output stream and the plaintext. If you reuse the same nonce then you get the same output stream which is really bad (but AES has the same problem, as mentioned at the end of the video you can't just encrypt each block in parallel with the same key, otherwise identical plaintext blocks will result in identical ciphertext blocks which is also bad).
@@marc-andreservant201
> Chacha is a stream cipher, which works in a completely different way
In its initial design, yes. But practically nobody (
Finally a simple enough yet comprehensive explanation of AES. I always wondered how this algorithm worked and you layed it out so well!
it's way too verbose
@@boohba It's 15 minutes of your time.
I think that's endurable.
@@cameron7374 15 minutes is a lot
@@boohba most competent loli enjoyer
The clever use of graphics to illustrate the processes elevates the learning experience to a whole new level! Very well done!
The use of the little robots is so engaging! SubBytes is oddly adorable in their mannerisms :D
Great! Now continue with why simple AES encryption (ECB) is not enough in case of messages longer than 128bits. That's why cipher mode such as CBC exists.
They can also talk about authentication / AES-GCM which is the recommended version to use most of the time or so I've heard
this is like the only video explaining AES that i totally understand XD
Also the visualize with box make my brain learn faster
Good video as always, thanks you and the robots so much
The underlying round function of AES also has the nice property of generalisation, namely, it can easily be adapted to a public key one or a hashing function just by modifying how the key modifies the input in AddRoundKey.
😊
I love how you used 'robots' to describe functions, and the way you arranged them at the end!
I can't say how grateful I am, cause I was breaking my head to find good videos which I could understand easily, algorithm like MD5 and Sha 256 which teaches me and not just the same old crap. Thank you ❤❤
Best channel on youtube. Videos are always so clear and great subject matter.
Great video! Very clear explanation. Would've loved to hear more about how key expansion works
Loved that this guy has not stopped yet!! Thanku so much sir
Back in '95 I designed a password encryption algorithm based on XOR (exclusive or) logic. The company, AT&T NCR was sutilably impressed.
wou
combined it with aes
Wow, a very informative and easily understandable explanation! Well done!
Ironically almost all cipher modes still use one-time pads as shown in the beginning, and we use AES or other keyed mixing algorithms to generate a consistent but unique random key stream.
I guess it was concluded that diffusion of the plaintext isn't a useful property in the end. This only works securely if each message starts with a unique "initialisation vector" aka "nonce" though, to ensure each one-time pad sequence for each key-message pair is unique and can't be statistically analysed
Interesting indeed.
This also made me start looking into a better method of just one- pass id's for archives like zip, rar, 7z, lzh etc.
In theory, by randomly changing the byte order in non-destructive areas of the file, the password field will still reject the correct password even it it were uncovered by tools such as Hashcat.
The user lands up with a garbled extraction without the Byte Order Manipulation Key for that specific archive.
Let's just call this the BOM-key for sake of explanation.
I tried this yesterday on a simple lzh archive containg a PNG image.
Without unlocking the correct byte order sequence, the extracted file was just a black square consisting of 1 color only. Yet the original image consists of 256 colors.
After applying the byte order key
(L4C361nf) for this specific file, the original image is extracted to its true representation.
This is a work in progress but so far looks promising. I'm not aware of any current hack tools that can unpack a random BOM method, seeing that it's not based on any algorithm as such, making it difficult to determine a set obfuscation pattern.
Your thoughts are welcome... 🙂
@@lancemarchetti8673 I wouldn't recommend coming up with a fancy non-cryptographic scheme like that. I would generally recommend using a stronger key.
Designing from modern standards, I would use argon2ID13 to derive a large 256bit key from a password. You can configure the argon2 algorithm to take at least 1 second to derive on modern hardware and use large amounts of memory to make GPU based attacks redundant. I would then use AES-GCM-SIV or XChaCha20Poly1305 stream cipher algorithms to encrypt the files based on that key and a random initialisation vector. This is a fairly trivial construction and almost impossible to screw up assuming you have access to good libraries like NaCl (libsodium)
We nowadays look for a good keyed stream of pseudorandom bytes, which is then XORed with the plaintext to create the ciphertext. You can use any good block cipher in a construct like CTR or GCM to get exactly that. New designs will use the benefit of not needing a reversible setup (which Rijndael has, and was created with a Feistel network in the past to make designing it easier) to make them faster and/or better.
@@lancemarchetti8673 This approach relies on people not knowing or understanding the thing you're doing. Just changing the order of bytes is typically easily countered by statistics. I recommend cryptopals for its exercises to learn why these things are not a good design.
A one-time pad is more than just using XOR, he didn't really explain that well. It's true that the common AES modes do use XOR but because they are not using a true-random key the same length as the plaintext they are not one-time pads.
A real one-time pad is completely 100% unbreakable, AES is "just" practically unbreakable.
Your videos are consistently great. I wish you would do them full time.
Great explanation with great animation, as always.
The best explanation of aes I've ever heard
Excellent explanation and animations!
Great explanation- Seriously underrated channel. Happy I discovered you today. Subbed 😊
Really excellent presentation! Thanks.
Amazing channel. Thank you!
Beautiful explanation
This is such a concise explanation and the animation is so cute! Thank you so much for your hard work!
I haven't posted a single comment for a few years probably, but this video works so well for me that I have to say - very good explanation and thank you for this vid :)
Great easy explanation
Excellent tutorial. Thanks
Thank you very much, the explanation was great
Great explanation!!
Started watching this channel and immediately recognized the voice from CS50 🤣 love your lectures, thank you!
Excellent work 👏👏👏
You are one of my favourite teachers on cs50❤❤❤❤❤
Amazing video !
The Galaxy Cipher Machine: Unbreakable encryption using the Kaliko encryption method.
Set up:
A disc cipher machine on a spindle, the discs are like checkers in that they have notches to fit into each other. 1st wheel is the set disc with the numbers 1-80 scrambled, etched around the side, and on the top edge are three alphabets, scrambled the same, with two empty spaces to make 80 digits around the top. Each letter on the top is over a number on the side. There are 26 body discs, each having two rows (top and bottom) of 1-80 on their sides.
The first message is a four number code: 1234. This is first a security check. The number 23 on the disc, 4 to the right, plus 1, gives you the security response.
For the set up: The number one represents which set disc is to be used. The 23 is the number on the set disc that is under the letter on the top "E". This letter is the first body disc to be put on the spindle under the set disc. Depending on what the users invented for themselves, an even number goes left, odd/right. So the order of the body discs is the E first, then of right for the rest of the letter order for the discs. The body discs are like checkers in that they have notches for them to fit into each other. There is a dot on the bottom of the set disc somewhere between two numbers, and a dot on each side of each body disc as well. The last number of the 1234, the 4, is how many (left or right) notches to shift the discs as they are being put on using the dots as beginning points. 4 was invented to mean right for the dots so each disc has their dots spaced 4 notches to the right of the one above it. It is also decided/invented which discs go on up-side down. Once all discs are in place a tightening bolt is screwed on the spindle to secure the discs.
Operation:
In the coded message sent, the first 30 numbers are still part of the set up. The message follows after them. In these 30 numbers you have invented the pattern that if there are two number 6s in the 5th, 13th, 18th, and 29th numbers, the message is authentic. If there are more or less than two number 6s the message is bogus and is disregarded. In the first 30 numbers, you take the 4th and 9th numbers to know which algorithms to use, in this case both numbers are 12,34. You have invented at least 10 algorithms. The first message letter is O. Find an O on the top of the set disc in one of the alphabets (using another alphabet for the next O), and go down to the number below it on the edge, say 57. Now the first four algorithms are made up by the two users of the machines so they can be anything their imaginations can come up with. Like, from 57, down five discs to the top row of 1-80 where the number is 32, find 32 on the bottom row and go down 7 more discs and do the same, then go straight up to the set disc. 2nd algorithm is a diagonal angling down to the right 8 discs to the lower number on that disc-46, then finding the 46 on the top row, and straight up the to the top set disc. 3rd algorithm is another imaginative pattern ending at the top number 78 on the set disc. 4th algorithm now has a sleeve that fits over the machine with holes randomly drilled into its side lining up with each disc's number lines, 15 holes per line. Now look again to the first 30 numbers and see the 18th and the 62nd numbers are 36, and 84. So now the 78 is lined up with the 3rd disc's top number 6 hole, this shows the number 69 in the bottom number row hole 8. This continues for 4 discs to the last number 51 that is sent in to the other communicating person. (36, 84 is third disc, holes 6 and 8, for 4 discs)They run it all backwards to find the letter O.
Throughout the sent message there are many OOs. The pattern invented is that you go six numbers beyond the OO to see if there is a number 5 in that number (75). If there is, you know it is a body disc shift. The other number is how many notches to shift each dot.(Odd numbers one way, even the other). Do this at least once every message. If there is a 2 in that number (27) it means to replace the set disc with another one, in this case the number 7 set disc. You replace the old one and just line up the dots of the new set disc directly over the dot beneath it on the first body disc. Do this at least once every message for both set and body discs.
Another code invented tells you to change the entire order of the set up with a 4 digit set up number following it. Another code tells you to change the number of algorithms to use.
Golden rules: 1) Never use the same set up code more than once. 2) Always send at least 15 phony messages for every one authentic message. 3) Always shift both the set disc and body discs at least once every message. This cipher machine has ever changing/shifting number patterns, an infinite number of invented algorithms that are used in different orders, a large number of algorithms to constantly change, and every set of machines has a different operation. Each operating set of machines have virgin discs no other machines have.
This cipher machine cannot be broken, not even by the largest computers in the world if used correctly. The confirmation that a code has been broken is that the message appears. With a 500 letter message, if 500 GCMs are used where each machine only encrypts one letter, there is no confirmation the letter that comes up when trying to break it is the actual letter that is in the message. Every letter has a machine with different discs, different algorithms, and different operators encrypting it. So the most any attempt to break the code can do is acknowledge that each letter position could be any of the letters in the entire alphabet (A-Z). To write out the possibilities on paper would be to have an entire alphabet under letter position #1, then another one under #2, an so on. In the end there would be 500 alphabets in a row as the only clue to what the message says. A wall of alphabets. Its like telling the hackers there are 500 letters in the message and the words are in the dictionary. With this small bit of information it is IMPOSSIBLE to even begin to try to find the message. Not even the biggest computer in the world, working on it for 10,000 years could find the message.
This encryption form is called KALIkO ENCRYPTION, it is unbreakable, and is perfectly suited for the Galaxy Cipher Machine.
The best way to explaine ever ... thank you
Great Video
Amazing explanation. Really appreciate the background on confusion and diffusion. Really puts context behind each step!
Nice video !😀
Thank you!
I like your explanation of how the XOR gate works, I've never thought of it like that, thank you :D
Also good for the various types of "masks" you can apply to a set of bits. (XOR bits) then (add 1) is the fastest way hardware can make a signed (2's complement) negative.
8:45 Any block cipher that is always able to turn the encrypted data back to normal is just a big substitution cipher where for an input of any block combination it will substitute a different block combination.
such a nice content you don't see everyday on youtube nowadays :)
great video
You couldn’t of uploaded this at a better time
Damn ! That's some good ass content, i can research for days and wouldn't come close to underestand stuff like that
I love this kind of video please do more...
Yay!, We got a new video 🎉
Nice explanation. Can you add a followup to how many rounds are chosen, with regards to full diffusion in N rounds and bidirectional impossible differential cryptanalysis?
very informative video, thanks! do you plan to make a video about the fact that some encryption can be reversed via the same exact key? (i mean the technical requirements for that).
Thanks for this cute video that lays out the subject so well, which I've found to be interesting but intimidating. The li'l robots are 👌
I loved thisñ
Great job
Yeay, a new video to learn from Brian. Thank you!
Cool video but i wish it showed the decryption step. As is, AES seems like a fancy hash. I cant fathom how youd do all of that backward again!
Amazing Brian
9:25 Knew those values looked familiar :)
Thank you goddammit
Another condition you need to add to make the system at 2:41 "perfectly secure" is that the key needs to be strong. In particular, I think it should have high entropy over all suitably short intervals. How short depends on how much the adversary knows about the plaintext. If the attacker knows absolutely nothing about the plaintext (i.e. considers it to be just random bits with no apparent meaning), then this isn't a problem. But that scenario isn't realistic--usually the plaintext has some obvious structure that the attacker is capable of predicting and recognizing (such as being English sentences), so a randomly chosen OTP key that just happens to contain a low-entropy burst can reveal a burst of information about the plaintext. Modern ciphers like AES avoid that issue by mixing up the bits instead of only XORing them with a (pseudo)random sequence.
@@dsdsspp7130 Ok, I randomly choose the key 0100000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000110000000000000000000000000000000000000000010000 for my OTP. Still perfectly secure?
How does the attacker know it's a "low entropy burst"? For that matter what is a low entropy burst? Is it when the key is like 111111? That's fine because the attacker has no idea if it was 111111 or 111112
@@thewhitefalcon8539 By "low entropy burst", I mean an interval of the key that has much lower entropy than expected. The attacker can know you have a weak key when (a portion of) the ciphertext has something in common with what he knows (or assumes) about the plaintext. For example in the case of OTP, if the ciphertext looks like random garbage except for a patch which looks a lot like plaintext, then you probably have a weak key. In general, a weak key makes a cipher easier to crack (the details of how depend on the cipher).
@geoffmcqueen9955 when you have something that's truly random it's only natural that there are going to be "low entropy bursts" trying to avoid them would make the key less random and hence less secure.
as long as the key is random, the cipher is going to be random and even if there is something that matches with what he knows, well that's just pure coincidence and not a leak.
it's like the library of babel, it's random. does it contain the world's biggest secrets? yeah sure, but is there a way to distinguish between garbage and actual secrets? no, because it's random.
@@dsdsspp7130 Unfortunately, a key is not automatically strong simply because it was chosen at random. Various algorithms have their own kinds of weak keys, but what they all have in common is that they undermine the security of the cipher. If you XOR an English language novel with a random key and the ciphertext ends up containing a complete English sentence about what Harry Potter did at Hogwarts, we are going to take that as evidence that you somehow fucked up the encryption (e.g. by using a bad key)--the odds that this happened due to pure chance (and that Harry Potter is NOT part of the plaintext [or, accidentally, the key]) are far lower.
How to decrypt all this sounds like a nightmare. Is AES key also an clue for how many rounds it took and what was shifted?
It's funny that XOR-OTP is 100% guaranteed secure, but AES is only secure in practice, not in theory. Nobody knows if AES has some *hidden vulnerability* that reduces its effective security by orders of magnitude.
Some small vulnerabilities have been found, but they reduce the effective security by ~5 key bits, not half of all bits
Are you planning to do a video like this about TLS? I'd be perfect.
I'd love to see a video explaining how quantum computers break encryption standards, and how other algorithms can work to protect against quantum computing.
AIUI, it is mostly public key cryptography systems (where instead of one key used for both encrypting and decrypting, there is a public-knowledge key used for encrypting, and where there is a separate secret key which is supposed to be needed to decrypt the messages) that quantum algorithms have been found to break.
I think all of these quantum based attacks (so far) use the quantum Fourier transform? But I’m not sure.
Men, youuuu arrrrre awesome ❤
Wait, at about 10:10 it occurred to me that the process sounds a lot like a neural network, with sequences of linear and nonlinear transformations!
Interesting. Why is the substitution important for confusion? Wouldn't just applying the round keys do a similar job?
👌
Kesini gegara direkom mbak luth
If I am correct, key is weakest point of that security system. It is in need to deliver it somehow to encrypet message reciever.
By hearing his voice was about to comment its brian from CS50 then in description foind out ohh its him 😅
Great video.
One note, it's pronounced RHINE-dahl, not RAIN-dahl.
[ˈrɛindaːl]
How is the key sent to the person you want to be able to “read” the message?
Currently? Diffie-hellman key exchange. As this method is vulnerable to quantum computers, there are alternatives being worked out. The most likely candidates are known as krystal kyber for key exchange, and Krystal dilithium for signatures.
@@Andrew-jh2bn Do you have a reference for DH being susceptible to quantum computers? Is that general DH or DH based on RSA problem?
@@dascandy I don't have a specific reference handy, but the method used is called shor's algorithm, I would start there. My understanding is that all diffie hellman key exchanges are vulnerable, not just rsa. Hence, the national institute of standards is in the process of selecting new quantum resistant key exchange methods.
The robots look like they're Wall-E and Eve's kids
the “uh” sounds at the end of your words are excrutiating
can you make an animation about JWT authentication tokens? i still cant wrap my head around using it for logging in and logging out!
4:16 One really non-performant way to do it with just the simple XOR algorithm is to make the key an transcendental number that can be computed one digit at a time, then send a second piece of data for what digit you're on and so long as they don't know the transcendental number you can iterate through the digits of your number forever without them being any wiser this will of course be limited by how accurately you're computing and the number of bits used to tell the digit you're on, and you'd have to come up with a new transcendental number each time you want a new key.
good animation :)
Seems like mix columns is pretty similar to the key expansion?
They're related operations; both use multiplications in GF(2^8) to modify the input values.
0:35 The phrase "One algorithm - Rijndael - won the competition" does sound like "One algorithm reigned all - won the competition". I cannot imagine this is an accident. Well done!
Do for Boyer moore algorithm like
Fighting
My brain has a very strong confusion algorithm
But how to share the key between the two actors ?
Computerphile has a video on Diffie-Hellman key exchange algorithm.
Really, use TLS1.3. The difference between SSHv1, v2, v3, TLS1.0, 1.1, 1.2 and 1.3 is getting that key exchange unhackable, and it's *really hard*.
Please upload java course +dsa
why can't AES be generalized to higher sizes, like 512 bytes or 1024 etc etc?
is the narrator from CS50?
Best of the best
12:41 The cyclic group with 256 elements is not a field since 256 is not prime.
It's a field still, a Galois field specifically (GF(2^8)).
6:56 multiple xor lol
"I'm gonna go get the papers, get the papers."
Now I know AES mix and modifies the bits and bytes of data, and thus it's very secure. I wonder how can we decrypt it...
every step is designed to be reversible. So you just do everything again, but backwards.
For ShiftRows, you shift in the opposite direction. For sub-bytes, you have a different table that maps the encrypted byte to what originally made it. For AddRoundKey, you can actually just do the exact same thing (since XOR is its own inverse). The only weird one in reversing MixColumns, but you can think of it as *essentially* a matrix multiply, so you can actually find the inverse matrix and multiply by that to get back to where you started.
well the trick is that you don't know the key, and so you can't reverse the add round key step
Well, and this example is also specific to a 16 byte plaintext. If your pay load is larger than that (which it often is), you'll have even more transforms
@@haniyasu8236That is what it originally was meant to do, but funnily enough modern AES implementations don't even need to bother implementing decryption at all. Look up CTR and GCM to understand why.
How to decrypt with key (or without 😏)
When it won the NIST contest, Rijndael reigned all.
The best thing is that the target is confusion
The explanation is good but without explaining the reversing operation it's seems just as hashing and not encrypting
Reversing it just requires doing all the steps in reverse order. You unmix columns by doing another MixColumns with the inverse matrix. You unshift rows by sliding the rows the other way. You unsub bytes by passing them through the substitution array backwards. You unadd the key by doing AddRoundKey again - that step reverses itself. The end result is your original plaintext.
The biggest issue with making an AES I would say is the "S" section. Need to stop knowing the AES from working as the sole needed tool to break through it.
and that's faster than rsa??? It already looks so expensive to run
I was some day trying to serch up this stuff and i culdnt find anything usful so thanks wery much
What blows my mind is how the designer of AES guaranteed that the algorithm could be reversed so you can decrypt that giant mess of ciphertext back to the plaintext. Lots and lots of complex math I'll probably never understand.
You didn't mention the IV at all. How does CTR block chaining work exactly? It's almost magical, makes the block cipher behave exactly like a stream cipher.
AES used in ECB (like this example, one block at a time) does not use an IV. IVs are specific to chained modes of operation, like CBC. CTR does not have anything to do with CBC, it does have an IV but it's used entirely differently.
CTR (and indirectly GCM) use a block cipher and a counter value. They encrypt the counter value to generate 16 bytes of key stream and increment the counter. This is repeated until the key stream is the same length as the plaintext, and then it's used like a one time pad. The IV in CTR is used as part or the whole starting counter value. Since it basically emulates a one-time pad key stream, you have to never reuse the same IV with the same key, or you get the same problems.
Plain CTR is unsafe to use, because anyone can flip bits in your plaintext by flipping the corresponding bit in the ciphertext and you wouldn't be any the wiser. GCM keeps a running hash and checks the integrity of your data before returning it, so you either get "this is the data and it's uncorrupted" or "it's not good".
AES is so damn complex for nothing, it's very hard to write correctly in order to avoid timing attacks and it's slow-ish without specialized hardware instructions.
The fact that there's a lot of videos trying to explain all its inner workings and there's still people wanting more speaks for this!
ChaCha20 is a perfect replacement, it's much simpler (20 lines of C, no S-Box) and even faster, its 8 rounds version (ChaCha8) is so quick it can be used for videogames and it still good enough for cryptographic use.
cha cha real
CHA CHA CHA CHA CHA CHA CHA
@@kakyoindonut3213smooth
Faster and thus better adapted to streaming data, but not necessarily as secure as AES. And nobody is using AES as a streaming cipher anyway. Apples and oranges.
@@magicmulder It is as secure as AES as it's a cryptographic cipher, it has been heavily studied too and is currently being used for TLS by Google.
Also you're wrong about AES not being used as a stream cipher, checking out the https certificate I'm using on youtube with firefox, it's running on AES_GCM, GCM (Galois Counter Mode) is a streaming cipher version that is adapted for AES so you can calculate the authentication together with the encryption.