A Stick Figure Guide to the Advanced Encryption Standard (AES)(moserware.com)
moserware.com
A Stick Figure Guide to the Advanced Encryption Standard (AES)
http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html?
9 comments
Thank you for the explication of the algorithm; Your pedagogical style is so easy to follow that when I first encountered it, despite not having a strong background in math I was able to follow along and actually build an understanding in a subject I probably could not have easily understood at the time! That ability to make information more easily accessible is truly a gift. So all I can say is thank you for sharing, it's most appreciated.
Please do continue - your blog is one of the very few that I consistently read all posts from. Really great stuff.
Some nits:
* "Deep Crack" and Distributed.net came after DES was fatally injured by differential and linear cryptanalysis.
* At no point was the only alternative to the broken DES "Triple-DES"; we had (for instance) IDEA since 1991, which is what PGP used.
* Speed isn't the biggest reason we ditched DES-EDE; the tiny block size and key size restrictions are bigger reasons. Similarly, "at least as strong as Triple-DES" is misleading; nobody was satisfied with Triple-DES' security bounds.
Just nits. The AES math stuff is great. But don't go trying to use any of this; this is just a fraction of the detail you need to safely use an AES library.
* "Deep Crack" and Distributed.net came after DES was fatally injured by differential and linear cryptanalysis.
* At no point was the only alternative to the broken DES "Triple-DES"; we had (for instance) IDEA since 1991, which is what PGP used.
* Speed isn't the biggest reason we ditched DES-EDE; the tiny block size and key size restrictions are bigger reasons. Similarly, "at least as strong as Triple-DES" is misleading; nobody was satisfied with Triple-DES' security bounds.
Just nits. The AES math stuff is great. But don't go trying to use any of this; this is just a fraction of the detail you need to safely use an AES library.
What do you recommend as a good reference on implementing AES encryption?
There isn't one. Even _Practical Cryptography_, my favorite of the encryption books, misses details (some of them recent discoveries, others older) that can completely wreck the security of an application that depends on AES for security; also, as well-written as the book is, it's organized in a way that makes it possible to miss some of the key details that it does document.
If you need encryption in your application, you should use TLS or GPG/PGP to get it.
If you need encryption in your application, you should use TLS or GPG/PGP to get it.
http://chargen.matasano.com/chargen/2009/7/22/if-youre-typin... is the best reference.
(Don't do it!)
(Don't do it!)
That's just a few of the issues; we wrote that to talk to other pentesters about how to look for flaws, not how to build something secure.
This has been around for a good while but still gets me reading it every time.
It's also a great example of taking an incredibly complex subject and cutting it down to various levels of understanding.
It's also a great example of taking an incredibly complex subject and cutting it down to various levels of understanding.
this is great article for someone to undertand how cryptography and AES works - but as all great explanations - it fails to explain some key concepts that take it from 0 - to "got it!" for me (hacker with absolutely no idea of how cryptography works other than simple caesar ciphers and stuff from childhood books) - this actually reminds me of the article in rjlipton's blog that also made it up HN a couple of weeks ago (http://rjlipton.wordpress.com/2011/08/05/give-me-a-lever/) about the lever in any mathematical explanation. I'm going to use that a little leniently here and go so far as to say - the algorithm makes sense - but for someone who doesn't get cryptography - its the "key" that's the lever. I get the diffusion and confusion and most of the rest - that math is not the hardest bit. But how the key actually comes into being - and how the Standard ensures that only the 2 people in the conversation have the key - is what would really crack the entire thing for me.
You're right that there's more to it to build a full working implementation (including generating and sharing keys). I tried to show that by dissecting HTTPS (TLS): http://www.moserware.com/2009/06/first-few-milliseconds-of-h...
I didn't use stick figures in that post, but I used actual traffic with https://amazon.com. Amazon uses RC4, but could just as easily use AES.
I didn't use stick figures in that post, but I used actual traffic with https://amazon.com. Amazon uses RC4, but could just as easily use AES.
Cryptography is one of those things in life that never ceases to humble me.
This may be a stupid question but considering if you have the key you can get the original data, where is the boost in security in AES versus a simple obfuscation using a key? Is it in the complexity and variations of the underlying algorithm and not having many people that can reproduce it? Or is it the time factor of having to run through the algorithm thus increasing the sheer amount of time it takes for an attack?
The boost comes from when the attacker does not have the key; and when the attacker knows the plaintext, key recovery is still difficult. AES is designed to be fast.
Encryption is based on two principles: confusion and diffusion.
Confusion means that the process drastically changes data from the input to the output. For example, by translating the data through a non-linear table created from the key. We have lots of ways to reverse linear calculations (starting with high school algebra), so the more non-linear it is, the more analysis tools it breaks.
Diffusion means that changing a single character of the input will change many characters of the output. Done well, every part of the input affects every part of the output, making analysis much harder. No confusion process is perfect: it always lets through some patterns. Good diffusion scatters those patterns widely through the output, and and if there are several patterns making it through they scramble each other. This makes patterns vastly harder to spot, and vastly increases the amount of data to analyze to break the cipher.
AES has both excellent confusion and diffusion. Its confusion look up tables are very non-linear and good at destroying patterns. Its diffusion stage spreads every part of the input to every part of the output: changing one bit of input changes half the output bits on average. Both confusion and diffusion are repeated several times for each input to increase the amount of scrambling. The secret key is mixed in at every stage so that an attacker cannot precalculate what the cipher does.
None of this would happen if you used a simple one-stage scramble based on a key. Input patterns would flow straight through to the output. It might look random to the eye but analysis would find obvious patterns and the cipher could be broken.
Confusion means that the process drastically changes data from the input to the output. For example, by translating the data through a non-linear table created from the key. We have lots of ways to reverse linear calculations (starting with high school algebra), so the more non-linear it is, the more analysis tools it breaks.
Diffusion means that changing a single character of the input will change many characters of the output. Done well, every part of the input affects every part of the output, making analysis much harder. No confusion process is perfect: it always lets through some patterns. Good diffusion scatters those patterns widely through the output, and and if there are several patterns making it through they scramble each other. This makes patterns vastly harder to spot, and vastly increases the amount of data to analyze to break the cipher.
AES has both excellent confusion and diffusion. Its confusion look up tables are very non-linear and good at destroying patterns. Its diffusion stage spreads every part of the input to every part of the output: changing one bit of input changes half the output bits on average. Both confusion and diffusion are repeated several times for each input to increase the amount of scrambling. The secret key is mixed in at every stage so that an attacker cannot precalculate what the cipher does.
None of this would happen if you used a simple one-stage scramble based on a key. Input patterns would flow straight through to the output. It might look random to the eye but analysis would find obvious patterns and the cipher could be broken.
I guess I had always assumed attacks were brute force input = output. But you seem to be implying that patterns would be looked for that would make the encryption/decryption vastly easier. That would probably be the piece that I wasn't grasping because if you have:
a -> f(a) -> b
vs.
a -> g(a) -> b
Then brute force really wouldn't be affected by complexity unless it was a time factor and thus either of the functions should be identical in security. But if analysis was the key to a good attack then this makes perfect sense. Thanks for the info.
a -> f(a) -> b
vs.
a -> g(a) -> b
Then brute force really wouldn't be affected by complexity unless it was a time factor and thus either of the functions should be identical in security. But if analysis was the key to a good attack then this makes perfect sense. Thanks for the info.
Yes. As a simple example, if you XORd your input text with a 1-byte key, the letter frequency of english text would be unchanged.
So your most common byte in your output would be likely to be the encrypted char 'e'. You could then recover the key by XOR 'e' with that most common byte.
More complex systems have more complex patterns, but that's what cryptopgraphers do - try and spot weaknesses in an algorithm.
As always, this is a great read: http://chargen.matasano.com/chargen/2009/7/22/if-youre-typin...
Search for "Garbling a block to confuse an app" and read on from there for a real-world use of output patterns (used when you can partially control the input).
So your most common byte in your output would be likely to be the encrypted char 'e'. You could then recover the key by XOR 'e' with that most common byte.
More complex systems have more complex patterns, but that's what cryptopgraphers do - try and spot weaknesses in an algorithm.
As always, this is a great read: http://chargen.matasano.com/chargen/2009/7/22/if-youre-typin...
Search for "Garbling a block to confuse an app" and read on from there for a real-world use of output patterns (used when you can partially control the input).
Multibyte XOR keys are almost as trivial to break as single-byte XOR keys, for what it's worth. And if you know how to do that, there are "best practices" AES modes in which common implementation errors lead to the same attack.
Happen to have, or know of, a version of that that has the images intact? I'm getting broken ones on every single item in the post.
You can brute force AES just like anything else. But AES keys are at least 2128 bits long, so you're racing the lifespan of the solar system to attempt it.
This is exceptional! The work of a really clear thinker.
http://laika1957.wordpress.com/2010/12/18/the-performance-of...
I was once again reminded of this blog entry when I saw the AES finalists' scoreboard slide.
I was once again reminded of this blog entry when I saw the AES finalists' scoreboard slide.
Some general thoughts looking back at my post two years later:
* I drew every cell with a sheet of paper and a sharpie and then scanned everything in. My living room was covered with all of the cells of this comic. If I did it again, I'd probably just use my drawing tablet. However, it worked out well being low-tech with paper because I drew a lot of the cells on vacation (i.e. imagine me drawing these scenes on a picnic table next to family by the lake thinking I was a bit crazy). Unfortunately, one unforeseen consequence of doing it by hand was that it became very clear that my handwriting was too hard to read, so I had to manually erase all the writing and redo it using a decent looking font. This took a lot of time. I had originally thought about using comic-sans but am very glad I decided to use the Marker SD font instead. You can see my actual handwriting in the "crib sheet" cell at the end. It was going to be way too much work to make it look pretty.
* I was most surprised by how many college professors use my comic in their computer security classes. Hopefully it helps the students.
* I tried to emphasize Rijndael's state matrix by having the stick figure guy carry it everywhere as a briefcase, but I don't think that came across very clear.
* Although I was inspired by XKCD's style, I didn't copy the critical part of a witty comment in the hover text. If I had to do it again, I probably would have done so.
Thanks for all the feedback; it's what encourages me to invest so much time in making posts like this.