(A play in 4 acts. Please feel free to exit along with the stage character that best represents you. Take intermissions as you see fit. Click on the stage if you have a hard time seeing it. If you get bored, you can jump to the code. Most importantly, enjoy the show!)
Act 1: Once Upon a Time...
Act 2: Crypto Basics
Act 3: Details
Act 4: Math!
Epilogue
I created a heavily-commented AES/Rijndael implementation to go along with this post and put it on GitHub. In keeping with the Foot-Shooting Prevention Agreement, it shouldn't be used for production code, but it should be helpful in seeing exactly where all the numbers came from in this play. Several resources were useful in creating this:
The Design of Rijndael is the book on the subject, written by the Rijndael creators. It was helpful in understanding specifics, especially the math (although some parts were beyond me). It's also where I got the math notation and graphical representation in the left and right corners of the scenes describing the layers (SubBytes, ShiftRows, MixColumns, and AddRoundKey).- The FIPS-197 specification formally defines AES and provides a good overview.
- The Puzzle Palace, especially chapter 9, was helpful while creating Act 1. For more on how the NSA modified DES, see this.
- More on Intel's (and now AMD) inclusion of native AES instructions can be found here and in detail here.
- Other helpful resources include Wikipedia, Sam Trenholme's AES math series, and this animation.
Please leave a comment if you notice something that can be better explained.
Update #1: Several scenes were updated to fix some errors mentioned in the comments.
Update #2: By request, I've created a slide show presentation of this play in both PowerPoint and PDF formats. I've licensed them under the Creative Commons Attribution License so that you can use them as you see fit. If you're teaching a class, consider giving extra credit to any student giving a worthy interpretive dance rendition in accordance with the Foot-Shooting Prevention Agreement.
235 comments:
1 – 200 of 235 Newer› Newest»Wow. That's just awesome. Great job!
...Claps Heartily...
BRAVO!
ENCORE ENCORE!
Seriously awesome comic! Although I mentally exited when we got to the math, I thought it was a very good and unique primer to encryption.
Very sweet. Very impressive. Very.
yay Grok! I remember that book... the human from mars who was raised by martians?
...but the math was interesting too. haha
Best stick figure comic ever. So funny & insightful at the same time!
I wondered if you would mention the block cipher modes since avoiding the bad ones is important -- but you did! (Act III, scene xxi!)
You are my hero.
can you explain why AES is superior to other forms of encryption? comic was very good at explaining the mechanics, but would like more fundamental understanding, perhaps comparison or explanation of breaking a code? a lot of working probably. thanks! read the whole thing!
I'd love to hear more about AES's resistance to linear and differential cryptanalysis and everything else in the third to last slide!
This was fun to wake up to. Thanks!
Excellent! Thanks very much! :-)
Beyond great. Should be part of every CISSP prep class. Thanks.
Very nice explanation. I probably need to get a primer book on math. I've forgotten most of it since I don't use it.
I noticed the license looks like the MIT/X11 license.
Very Cool! Very entertaining stick figure comic.
This was so much better then reading source. Wonderfully done
Whoa way cool dude, I like it!
RT
www.online-privacy.us.tc
Amazing! Fantastic post, thanks!
I wish you had written all of my engineering math textbooks.
Fantastic! Thanks for the wonderful work on the details.
Oh man!! This is so awesome!
Thanks for putting this together. I hope to see more like this.
wow, this is great! Thanks for sharing :)
I really want the AES crib sheet as a t-shirt.
Intel and AMD are just now getting on the bandwagon with something that Via has had for a long time (See their Padlock engine)
You are my hero
Great post! Crib Shirt++
I'll be poking around the linked project since my eyes glossed over during the math section.
Thanks :-)
Thanks man! Neat comic. The only problem is that I am now more interested in math.
really fun explanation, just what cryptography needed!
Well thought out - not an easy subject to put into that context. Kept me interested thru the end. Thanks for sharing!
Absolutely wonderful. Thank you!
Wonderful! Thank you so much for this!
Having finished reading (most of) The Design of Rijndael a couple months ago and seeing the notation used in Act 3, I'm not at all surprised to see that book at the top of your resource list.
Also, that Foot Shooting Prevention Disclaimer should be generalized to any cryptographic algorithm, not just AES.
Dude, that's just awesome!
JD, BenC, Anonymous #1, Der, Justin Etheredge, Anonymous #4, Gav, Shieldzee, Jeff Barnes, Anonymous #6, Harold Fowler, Markus Olsson, Anonymous #7, paisleyboxers, Edward, John Currah, Sushant Srivastava, Bas, Anonymous #8, MuslimDad, Konstantine: Thanks for all the kind words, I really appreciate the encouraging words and you taking the time out of your day to read this and comment on it.
TH: I believe "grok" comes from the book "Stranger in a Strange Land." I haven't read it personally, but have just picked up the word to be a colorful way of saying "understand."
Daniel Meyer: Yeah, ECB is a bad choice. CBC isn't perfect, but it's better than ECB. I wanted to describe something like EAX mode, but it would have been larger than half a frame.
Anonymous #2: "superior" is a challenging word. At a minimum, the crypto basics covered in Act 2 must be met in any non-toy cipher. Act 1, Scene 16 covers more-or-less how the finalists were "judged." Most people agree that any of them would have been "ok" as AES. Beyond good security, you have to look at pragmatic things like ease of implementation and speed.
Anonymous #3: The Design of Rijndael book I mentioned covers those in detail. I had a hard time understanding the details of it, so I didn't want to even attempt to explain it to others :) Feel free to create your own addendum slides and link them here if you make it.
Anonymous #5: The attached source code is indeed the MIT/X11 license. I tried to make it as open as I reasonably could. Feel free to contact me if it needs to be more open :)
Robert Talbert: I'll gladly buy you lunch if you make a t-shirt of it and wear it in public... so long as I get a picture :)
X-Istence: Perhaps, but Intel and AMD's marketshare is huge and will be a boon to generic SSL/TLS connections and OpenSSL servers out there.
Ben: Feel free to post any questions that come up about the code here.
Jonathan Kohls: Hooray! :)
Paul Kuliniewicz: You're right, the math and layer notation came from The Design of Rijndael. They helped me visualize what was going on better and it was something that I didn't see anywhere else.
As for the general applicability of the Foot-Shooting Prevention agreement, I fully support that.
Jeff: "Grok" is indeed from Stranger in a Strange Land. It's worth reading if you're in to Heinlen-esk sci-fi.
I love that you included the "math is hard, lets go shopping" bit. Some of my less-geeky friends use that to let the others of us know that we're boring everyone else. Sometimes they'll also pull out the old "PI is exactly 3!" card too. Good times.
Absolutely awesome post! A lot of creative thought went into this. It really helps make AES a little easier to understand.
That's a splendid way of explaining the tough points. Very nice work. Thanks.
Awesome. It's been a looong time since I've done math like that. Fantastic work!
Where does the initial key come from?
I can't believe I read through the whole thing. I am noticing a trend using simple comics to describe technical issues. Google Chrome did something similar, and I think this format makes reading technical details a lot more fun than a Wiki or other documentation.
Amazing, I really enjoyed this, thanks for sharing.
My mind is so blown. Reading this sort of stuff makes me want to go back to school to figure out what you're talking about and / or give up my career as a programmer and rescue cats from trees or something.
Phwew.
Can I just throw in this for a prequel of sorts:
Stick 1: "Jrypbzr gb gur pynff ba EBG-13"
Stick on chair: "Nope, I'm auditing this class"
Seriously though, great work. Prepare youtube for our interpretations.
I can't wait for your play on md5.
Poor AES... Your efforts are underrated... I feel for you man. Hehehe...
Awesome job! Loved the distributed.net reference.
This was excellent!
Great Job Jeff. Though I couldn't make it beyond the math thing, but you have got me completely intense to get back to my math studies and dig deeper into AES. Thanks a ton!
Wow! Keep it up! That's really really well done and helpfull. Please do cover other hard core cs math stuff in that way. pleeeeease!
Thanks alot for this.
amazing thanks
Great morning reading, found you on Twitter. Very entertaining and informative!
Nice job! Thumbs up
That's really nice, explains everytihng really well :) But aes isn't as secure as depicted.
Have a look at this article. It explains it pretty well
http://chargen.matasano.com/chargen/2009/7/22/if-youre-typing-the-letters-a-e-s-into-your-code-youre-doing.html
Damn that was geeky.
At the beginning of act 4, do Ashley and stick figure #3 ever get together? The suspense is killing me!
In a word: awesomeness!
Thanks very much for sharing this with the world :)
DSAOI FGVAG OISDF OIGOS AIDGO SDGIA SSASI ODOIA SDGOI ASDFF!
This is awesome! I love it! The world is better for people like you who can, and do, simplify things like this so that people like me can begin to understand it. I wish I had taken more math courses in college.
A couple of points:
I think the real names, "substitution" and "translation" are just as easy to understand as "confusion" and "diffusion" even though they don't rhyme.
Key Expansion Part 1 is really the overview, part 2a, b, etc. are the details of part 1, so I'd call them Part 1 and part 1a, 1b, etc.
Key Expansion Part 3:
Instead of, "I just xor the previous column with the same column of the previous round key"
I think you meant to say, "I just xor EACH column with the same column of the previous round key"
I love the "Shift Rows" graphic. That made me smile. I did this with a musical instrument layout and always had trouble explaining it to people: http://organicdesign.org/peterson/glass_organ/layout.html Scroll down to "Vertically collapsed".
And the math part - well, that's just crazy stuff. I can't even appreciate how awesome that is.
Anyway, thanks again for posting this. I understand this much, much better as a result.
Fantastic!
+1 crib-sheet T-shirt! You should make a skirt too, with it printed upside-down on the front for easier reference and to encourage more women into the field. ThinkGeek should carry these!
I have been reading crypto algorithm descriptions since before the birth of DES. This is the best presentation I have ever seen.
Thank you.
Best thing is, you know that anyone who read to the bottom of this, is like you, a complete geek... Either that, or working in the Info Security Industry (like me)...
Great comic tho and a very thorough explanation of AES, you should consider doing more of these for advanced topics, I think you might have a real audience...
Second comment to say:
Crib Sheet T-Shirt +1
I would buy one without hesitation...
Simply fabulous. Thank you so much. I love the stick figures and the crib sheet.
wonderful explaination !!
insprires people like me who have just started to know whats encryption. thanks much.
i read the subject completely and ALSO the comments completely...
as everyone said, the subject is beyond appreciation - i agree...
and comment1: to have the stick figure on the T-shirt - im in for this idea too.
comment 2: Ashley and stick figure 3 did they meet question - the suspense is killing that guy and making me to smile - as this person looked at the thinnest details of your slides.
great effort, well done and please keep such things coming - we would get a chance to go through them if we are lucky.(rather have the key to decrypt your encrypted subject)
Glen.K.Peterson,
"Confusion" & "diffusion" are the end properties that are desirable from a block cipher. They are the "motive".
"Substitution" and "translation" are just two techniques used to achieve those properties (respectively) in an iterated block cipher. They are the "means".
Amazing, its like a massive XKCD
I just want to know if Ashley went out with the bored student..
Outstanding! Clear, informative, and entertaining!
I am a non computer, non math, non technical person. I just enjoyed your narration and pics. Now I know what AES is. I am going to boast it in my next party... whoa...
Excellent job!
Can you explain magnets to me?
At the risk of being a jerk , you may want to revise act_4_scene_04. The first line of the equation should read:
=((x^7)+(x^5)+(x^3)+x) ((x^6)+(x^4)+(x^2)+1)
[extra parentheses added for clarity and multiplication is implied due to limitations of plain text comments]
If this has been noted already pleases disregard.
From the guy behind ScoreVoting.net:
"Even if this break breaks due to the underlying models inadequately approximating the real world, we explain how AES still could contain ``trapdoors'' which would make cryptanalysis unexpectedly easy for anybody who knew the trapdoor. If AES's designers had inserted such a trapdoor, it could be very
easy for them to convince us of that. But if none exist, then it is probably infeasibly difficult for them to convince us of that."
http://www.math.temple.edu/%7Ewds/homepage/wdsAES.pdf
simply awesome... :)
So what ever happened to Alice & Bob?
Bravo. Well done.
I have taught a course in cryptology for gifted and talented junior high students during the summer for the past several years. I usually didn't say too much about DES and AES since the details of the algorithm are tricky to explain. Your comic has inspired me to give DES and AES more attention when I teach the course again.
Thanks for taking the time to put this together. The inside jokes are great!
very good. very informative.
I would like to print this out. Do you have a printer friendly version lying around anywhere?
absolutely great...!
it's still not exactly clear to me but it's outside my field of expertise - and that's okay.
the core concept that confusion, diffusion, and one ?-bit key will always encrypt AND decrypt to the same message lingers on, but i grew up with a sci-fi "there's always another possibility somewhere" attitude and a "my kids will learn more than i ever knew" understanding of knowledge.
In Act 4 Scene 8, the first version of the remainder has the following term
(b3+b7)x^3
But it should be
(b2+b7)x^3
This is excellent.
My math has been all but lost for years and yet I could follow it to the end.
Very nicely done!
Sorry if this was already mentioned, but there's a wee typo in the intermediate step of the division in act IV scene 8, although the last step is fine:
Is:
b₆x⁷ ⊕ b₅x⁶ ⊕ b₄x⁵ ⊕ (b₃ ⊕ b₇)x⁴ ⊕ (b₃ ⊕ b₇)x³ ⊕ b₁x² ⊕ (b₀ ⊕ b₇) ⊕ b₇
Should be:
b₆x⁷ ⊕ b₅x⁶ ⊕ b₄x⁵ ⊕ (b₃ ⊕ b₇)x⁴ ⊕ (b>₂< ⊕ b₇)x³ ⊕ b₁x² ⊕ (b₀ ⊕ b₇)>x< ⊕ b₇
Great article, but it's kinda one-sided. Yes, the NSA suggested a shorter key length, and they manipulated the S-boxes, but you neglected to mention that their S-box manipulations are what made DES abnormally strong against differential cryptography -- a technique not discovered in the private sector until 15 years later!
Insanely long comic which should be a manga anyway !
Sarwar Faruque, niranjan, Tigerbeard, Anonymous #9, Anogar, simoncpu, digo, Kristofer Pettersson, Galilyou, Anonymous #10, Alan, Anonymous #11, Abhimanyu Grover, Fake51,Guruprasad Kini (Guru), myer nore, mikero, Phil, Anonymous #17, Kumar, Satish, Anonymous #19: Thanks everyone for the encouragement. I really appreciate all the feedback.
fiXedd: Thanks for the SIASL confirmation. As for your friends, I say math is more fun than shopping.
5h4rk: The initial key comes from the outside and is given to AES. It could be derived from some password the user types in.
ABS: Thanks for reading it ;). Google Chrome's intro comic was one inspiration for this post, but there was no way I could draw like Scott McCloud can, so I stuck with stick figures.
Mark: I think one play on this blog is probably enough ;). MD5 is under serious attack now, the new SHA-3 under development is the next Cinderella story.
pointernil: Thanks! I've been trying to cover core CS things on occasion (e.g. regular expressions. It just depends on what seems interesting that month (or three).
Anonymous #12: Like Paul mentioned, the Foot-Shooting Agreement can be applied to most crypto things in general. It's better to use TLS/SSL or something like Keyczar which exposes a higher level interface that can get the details right.
Anonymous #13/#16: "My sources say no."
Mister Enigma: I'm afraid I don't have the key :(.
Glen.K.Peterson: Thanks for the detailed comment. A few points: Confusion and Diffusion are the principles, substitution and transposition are just one means to the end (as mentioned by mikero). As for the key expansion scenes, you're right in that I made the ordering fairly arbitrary. As for part 3, the wording you suggested would be incorrect. Imagine we're creating round key 2, column 3. We create this by xoring round key 2, column 2 (a.k.a. the previous column) and round key 1, column 3 (the same column of the previous round key). I can't say "xor EACH column with the same column of the previous round key", because the column has yet to be initialized. This is why creating column 'c' requires 'c-1' xor 'c-4'.
Shift Rows was one of my favorites as well. The karate kick immediately came to mind. Interesting to see your musical relation.
Interesting +1 on the skirt idea... that'd be a serious math girl ;)
Anonymous #14: Thanks. I'm sure you have stories to tell on DES. I tried to cover the real basics. Feel free to add any links you think might be helpful to others.
Jordan: I envisioned myself leaving just before the end as that's where I struggled with in the Rijndael book.
NoWine: Thanks for putting in the effort. Hopefully this was helpful. Please feel free to subscribe to the RSS feed and come back.
Anonymous #15: It was long, but I tried as best as I could to compress things without missing parts that gave me an "a ha!". Thanks for the honest feedback though.
Graeme: Magnets are hard, Let's go shopping.
John: Great catch! You're absolutely right, there was a typo. I've fixed this. Please reload. Thanks again!
broken ladder: Thanks for the link. In general it's hard to prove that something is secure, only evidence over time by many eyeballs seems to matter.
abnerg: They're being held captive by Mallory.
Anonymous #17: Thanks for sharing your story. Feel free to use any material in this post if you think it would help your students.
Anonymous #18: I don't have a printer friendly version yet (other than my original hand-drawn slides.) Perhaps if there's interest I could create a PDF of the high-resolution versions of each slide?
Anonymous #20/Jonathan: Excellent catches! I've gone ahead and fixed this scene. Please reload to see it.
Silas Snider: I tried to be balanced. In Act 1, Scene 8 I highlighted the "stronger" s-box (even drew radiating lines coming off it :)). I agree that the NSA was at least 15 years of the public at that time. I tried to highlight the basics of this with a simple picture, but you're right that there's a lot more details that had to be cut for space reasons.
epsos: I can't draw eyes... ;)
Muchas gracias. He aprendido y me he reido un montón. Enhorabuena por tu manera de contar historias "difíciles"...
Thanks you very much. I have learnt and laughed a lot. Congratulatios for your way to tell "hard" stories...
Have you think about translations????
Luis
Reliable sources say this great article has been making the rounds at RSA Security. ;-)
Awesome!!!
I posted it in CISSP's LinkedIn Group
If you don't mind, I'd like to use it in my CISSP CBK Training - Crypto Domain material and put the credit for you.
Thanks in advance.
Best regards,
Gildas Deograt
http://think.securityfirst.web.id
This is totally awesome ! You should make an illustrated book with it :D
If you've agreed, it'll give me (and students) much more fun in my training classes.
Thanks again!
Gildas Deograt
Simply great !!!!!
This is a classic ! Awesome work ..
- Rahul
Luis: Yo estaría encantado de ver las traducciones de esta obra. Eres libre de hacer cualquier traducción que usted desea. Mi única petición es que se ponga un enlace a esta página en alguna parte. Gracias!
I would be delighted to see translations of this play. You're free to make any translation you want. My only request is that you put a link back to this page somewhere. Thanks!
covert.c: Cool! However, as a company that contributed an AES finalist themselves, I'm sure they knew all of this and much more :)
Anonymous 21: That'd be great if you used it in your CISSP CBK training. It'd be an honor for me if it helps anyone understand the material better.
NinjaCross: At 67 slides, it's probably a mini-book already ;).
Gildas Deograt: Yes, please feel welcome to share it in your classes. Consider giving extra credit to anyone who creates the interpretive dance specified by the Foot-Shooting Agreement and posts it on YouTube.
SuperJosemi, rahulnet: Thanks!
Awesome stuff. Really enjoyed it. Great job Jeff!!!
Very good explanation, it is brilliant and funny, many thank you.
Way to go Mr. Big Time Code Dude,
Now the bad guys will know how to hack into Coke and steal the formula. Who knows what will happen then. They may change the formula and your stick guy will gain weight. (ha)
I love the logic...
Thx...
Fantastic, that AES Crib Sheet's definitely going on the cubefarm wall.
Nagyon fain! / Great!
OMG, this was fantastic! Had me laughing + it's so well super well illustrated. love it. a flip book animation would be the only thing that would make it better.
Mix columns panel equation has one x missing next to parentheses in the bottom-left corner.
Pavan Alampalli, Borh, George, Hussain, Anonymous #22, MissXu: Thanks!
Anonymous #23: Another good catch! I've gone ahead and fixed it. Please reload the page.
Jeff, it's absolutly fantastic. I do crypto stuff since early 1980's, but I've never seen such an easy to understand explanation. Thank you for sharing this.
This is really cool. Well done with making difficult material accessible... and fun! Do the PPT and PDF links work? They don't for me.
Great post. Thank you!
urgestein: Thanks. It was my goal to share my interest in the details with the world.
drewster: Please refresh the page and try again to download the PPTX and/or PDF. I've updated the links to go to an indirect SkyDrive page. It seems that direct links with SkyDrive are problematic. Let me know if you have any further problems.
jideel: Thanks!
Links are working for me. Thank you!
Excellent work. I think I will use it for teaching purposes - with the interpretive dance extra credit of course.
Thumbs up, thanks a lot... THAT was easy ;) LOL
just awesome, thank you!
thanks! making hard compsci seem easy is always greatly appreciated. <3
Err, I think that's the most equations I've ever seen in one cartoon =P
Nice comics.
You should know that XOR gate can be created much esier that from 4 subgates (in fact it is separate gate created by just 3 or 4 transitors). It is also used because of it's reversibility. (a + k) + k == a. It have also good diffusive properties. This makes it nice building block of crypto.
Nice.
It's worth noting that Sun has been doing this in their Niagara CPUs for some time.
Haha, really god job! Enjoyed whole comic!
Just want to mention that the Sun Microsystems UltraSPARC T2 also have AES built in (since 2+ years...)
thanks for the great post! However, downloading the pdf fails (the link opens a page which complains of an error in parsing xml)
download link shows the following error:
XML Parsing Error: not well-formed
Location: http://cid-8509553b6d92361d.skydrive.live.com/self.aspx/Moserware/A%20Stick%20Figure%20Guide%20to%20the%20Advanced%20Encryption%20Standard%20%5E5AES%5E6.pdf
Line Number 120, Column 20:for (var i = 0; i < selfPageData.items.length; i++)
-------------------^
alvinx, Anonymous #24/#25/#26, Mike e cigs: Thanks guys!
Luke Hebbes: Excellent!
Glowing Face Man: Is that bad? :)
Witek: Are you referring to this 4 transistor xor? That's neat, I hadn't seen that before. You also make good points about xor's properties. I tried to share some of those in the play by saying that addition and subtraction were equivalent (I called in "new way" in the play). This makes the math more convenient.
Paul and Thommy M. Malmström: Fair points. I was more excited about Intel's implementation because of the larger marketshare (e.g. more likely to hit the massive amounts of people/end-users).
Mrinal Kant: Sorry about all of the download errors. I've gone ahead and switched where I'm hosting it. Can you refresh the page (to get the new links) and try again?
As a backup, I've also uploaded them to the Internet Archive.
Please let me know if it works now and if you have any further problems. Thanks!
If this PC had an APL keyboard, I could show you that AES takes just one line of code.
Excellent!
Great job !!
I've read the rijndael paper bu couldnt get it completely... but now... thank you sooo much!!! i appreciate it...
I would like to thank you for this guide to AES. It was very informative and equally entertaining.
However, there is an error in Act 4, Scene 12. The sum of the polynomials should be: x⁷ ⊕ x⁵ ⊕ x⁴ ⊕ 1
Still, that was a very good and unique guide to AES. I plan on mentioning everything that I liked about it on my blog. I look forward to reading any other material that you will post here in the future.
Anonymous #28 and can: Thanks!
Anonymous #27: Have you seen the J language? It's very APL-ish, but without the need for special characters. Feel free to submit an AES implementation in it as a comment. :-D
Jake Kasprzak: Another great catch! Thanks for letting me know. I've gone ahead and fixed this scene. Please reload and let me know if you find any further problems.
In addition, I've fixed this error in the PowerPoint and PDF slide versions mentioned at the bottom of the post (along with the Internet Archive version)
Wow, IMPRESSIVE!!!
For a second i tought i could show it to my ex boss to let him understand a little what cryptography means, but when i saw the logarithms i realized that he will not understand even the difference between ECB and CBC, so ill try to find a comic with S-DES hehee
very nice! i loved it & you put it simple.
Thanks again for the post. The download links work now. I needed them because I hope to find them useful in introducing AES/encryption during training in my organization.
phenominal
Meh, Intel is now copying VIA
after just how many years?
(I wonder if Intel will now
also be putting a decent RNG
into their CPUs directly. VIA’s
only bad part is that it uses
the FPU registers etc.)
AWESOME, SIMPLY AWESOME!
Awesome post !!
It's better illustrated than our class room AES slides :)
Where's Bruce's beard?
Excellent. Just go on. Congratulations
agh.. math.. my brain hurts...
anyways, good way in explaining it.
fgvyy, EBG13 vf sha gbb. :)
tbbq jbex
just simply awesome....
hilarious...
Yes, great stuff, BUT, this is dubious:
"5h4rk: The initial key comes from the outside and is given to AES. It could be derived from some password the user types in."
Why ? Because short passwords only have so many possiblities. For example, there are only 10,000 4 digit passwords, and it may be possible to try all of them. Better to use a randomly generated key which has 2 to the power of number of bits in the key possibilities. Store the key in a password protected device such as a smartcard. But avoid using a key derived from a password in a known manner.
TL;DR
=)
omid8bimo, Anonymous #29, AAA, praveen, Olivier, Anonymous #31, Patel: Thanks!
Mrinal Kant: Great! I'd love to hear how the training goes and if there's anything I can do to clarify things.
mirabilos: Imitation is a sincere form of flattery, no? :)
Anonymous #30: The guy on the far right in Act 1, Scene 13 was meant to represent the whole Twofish team, not just Bruce :-).
Anonymous #32: EBG13 vf sha sbe cebgrpgvat fbzrguvat sebz lbhat xvqf be bofphevat grkg, ohg V jbhyqa'g hfr vg sbe nalguvat orlbaq gung ;) Gunaxf sbe fgbccvat ol
AndrewDover: Good point to clarify. I was just giving one example of how the key could be obtained. You're right that it's much better to have a key with high amounts of true entropy. In my post on TLS/SSL, I explained how TLS uses a Pseudo-Random Function (PRF) to generate random keys and initialization vectors. The handshake process that generates a session key that is used only once is much better than the 4 digit password process you described. As Paul Kuliniewicz suggested in an above comment, the Foot-Shooting Prevention Agreement should be applied to the whole implementation (random number generation, key derivation/exchange, etc), not just the encryption algorithm. The security is, unfortunately, only as strong as the weakest link.
Gonzoo: Hey... it was mostly pictures :)
If only i got my hands on this when i made cryptography disciplin...
This is the most informative thing I've ever read on the internet. Awesome job.
Wow awesome explanation! Math part was a bit complicated for me though..Think I need to grab my math books again :D
I have a really noobish question regarding AES if anyone would care to anwser: If someone knows the plain text and the corresponding cipher text, can they figure out the encryption key?
Anonymous #33 and Brian: Thanks you!
robinmitra1: Great question! If you look at Act 2, Scene 4, you'll see "Big Idea #3: Secrecy Only in the Key." The key is the only thing kept secret. This means that any good algorithm (especially AES) must protect the key from a "known-plaintext" attack. This is really important in the web world because a lot of files have a very predictable header. It's not uncommon for a webserver or OS to determine the file type from the header bytes. In the case of AES, the core round function does such a good job at confusion and diffusion that it's really hard to find a "trail" back to the key. If you only had a single round, you could probably have a good chance of finding the key in a reasonable amount of time, but each additional round makes it much harder.
One commenter on Reddit, had a good analogy of relating it to a prisoner escaping jail and accidentally stepping in paint. The further you run, the more the paint wears off and it's harder to track you down. The same idea applies to being able to infer the key. There's a huge field of study called differential cryptanalysis where you can control the input and output to get at the key. AES was specifically designed to be resistant against the known attacks at the time. Unfortunately, the math gets hard proving it and I had a hard time following it (and that's where I stepped out ;-) )
-- Comments from other places ---
mikezs on Digg made a good point that my use of the word "implement" in the Foot-Shooting Prevention Agreement in Act 3, Scene 2 can be confusing. I was not saying that you shouldn't use AES in production code, but rather that you shouldn't write the code that actually does the operations described in Acts 3 and 4. Effectively, this means that if you're going to use AES then you should use a well-tested and trusted library. Examples include Microsoft's Cryptography API (CAPI) and OpenSSL. There are even good arguments to be made that using AES directly is a bad idea. Nate Lawson gave a good talk on cryptography highlighting that if at all possible, get up as high as you can on a good crypto stack. Instead of dealing with specific algorithms (like AES), you should try hard to design your code to just use TLS GPG, or something like KeyCzar and trust that the designers of those implementations get all of the other things right (e.g. good random session keys, etc). I think that's reasonable advice to follow unless you really understand the consequences of all the choices.
Surlethe on StarDestroyer.Net BBS asked about the "specially crafted polynomial" in the MixColumns layer in Act 4, Scene 16. This was an engineering decision as several different ones could have worked. It basically came down to speed. You'll notice the numbers in the encryption version are 3 or less. You can implement small multiplies quicker than bigger ones in the AES finite field. This is also explains why decryption in AES is slower. Notice how Inverse Mix Columns on the cheat sheet show bigger numbers and thus it takes longer to perform. This also explains why removing the step in the last round can help speed things up, even just a little as it's the most expensive layer. Many more details about MixColumns (and this polynomial) can be found in The Design of Rijndael book starting on page 39.
--
As always, let me know if you have any questions on any other scene or concept. Thanks to everyone who read this far :-)
I love it. You need to consider teaching man. Hopefully i'll get some time to blog about this later and point people over your way so they can take a look at this. Great job!
SIMPLY AMAZING! Thank you so much.
what a lucid explanation!!
Thank you....
Thanks for the reply! I feel better safer now :D
BTW, your prison-paint example doesn't precisely demonstrate the issue because the issue is if the hacker knows the cipher text AND the plain text. So, that would means that the police knows the prison cell from where he escaped AND the place where he ended up :D But I get your point lol..
A video of this would be wicked cool !!
Wow. Excellent.
Amazing work. Your funny little cartoon really helped me getting to understand aes a lot better.
Thanks a lot
In a clear and simple way,you succeed in getting involved about the history of DES and its evolution towards AES.
I think that the idea of a comic to study the basic of cryptographic tool is very interesting rather than amusing
What i have to tell more?
Compliments a great job bu i think that you have to improve your comic art (i'm joking!)
Bye
Actually, the UltraSPARC T2 has several interesting aspects linked to the AES implementation.
It's an 8 core processor... and each core has a crypto-core with the AES acceleration code.
Also, the processor is open source ( see http://opensparc.net/ ) so you can look for yourself how it's implemented in verilog RTL.
Gilles
really fun-tastic job ! This was just great, I hope you win Oscar ! LOL
Fantastic strip presentation! Bravo.
Your AES is hero of the day in our site. Your brilliant work has been translated to russian language today.
Enjoy! https://www.pgpru.com/biblioteka/statji/aesvkartinkah
//somebody known as "Unknown" from PGPru.com team.
Mike Parks, Anonymous #34/#35, Girish Narayanan, Joseph, Eugenio, Shreyas, Kristanna, and Mario Munda: Thanks for the comments and for reading the guide.
robinmitra1: Physical analogies can only go so far... ;)
praveen: Perhaps I could convince a high school drama team to put it on?
Gilles Gravier: Nice. Here's a direct PDF link to a presentation on it. It's interesting that they have other crypto operations (e.g. public key, hash, and elliptical curve crypto). If GPUs are any indication, I wouldn't be suprised if we have more heterogeneous cores with specialities.
"Unknown": Thanks for your translation work! I mean, Большое спасибо за перевод этого на русский язык. :-)
Thank you, very well explained! :D
First tow Acts were great and very easy to understand but the Act about the math... complete garbage. You are making far too big leaps between the concepts and you don´t show the connection between them. You should also explain at every stept WHY you´re showing this to the reader.
Most of the time i was simply wondering why you were going through this at all. You are also using concepts from logarithms in this comic you haven´t explained in the panel where you were "explaining" logarithms.
Badly done.
Having implemented TDEA in Electronic Codebook Mode per NIST's spec a "few" years back (in APL), I promise I really could read and understand this (a degree or two's worth of math also helped). Better yet, I was well and truly amused by the presentation.
You are an übergeek of the first water.
awesome great job!
i was exited at the simplicity of the presentation..
am looking forward for next level!
Prasad
I find this... awesome.
Wow, just wow! I'm not huge on math, so the first round of explanation was all I realy understood. Cool stuff!
Zim, Prasad, and Niels Callesøe: Thanks!
quaelgeist: Thanks for the feedback; sorry that it disappointed you so much. My goal with the stick figure guide was to compress as many of the "a ha!" moments I had into the smallest space that I could (and even then it's longer than I would have liked). I cut out a bit of transitional material that could have helped explain more of the "whys" because the frame count was getting too high and I didn't want to drag people too deep, but at the same time I wanted a guide that had enough detail that you could write a working implementation. Specifically, with logarithms, I tried to highlight that they make multiplication in the Rijndael finite field much easier by reducing things to xor addition. I could easily have spent a lot more time. If you look at the code that I wrote to go along with the post, you'll see in Program.cs that I wrote several examples of using the logarithms. In addition, I tried to link to further resources that give a much more complete treatment of the topic. In the end, I had to make cuts for brevity. You're right to point out that this left many opportunities for depth. If you're still interested in AES, perhaps you might enjoy the links I linked to better. If those aren't helpful, please consider leaving links you think provide a better treatment of the topic.
Razzle Dazzle: Glad to hear you were able to follow. I'm curious, how would you have drawn Triple DES? Drawing three knights was the best I could come up with at the time I drew it, but it totally misses the fact that tripling the key size has an exponential factor instead of a linear factor on the keyspace, but it's hard to draw exponentially more of them ;)
Is it better than this cryptosystem?
Beautiful. Thank you!
I Loved it ... thanks!!
A cool comic that teachers
University and students will have to read and enjoy.
Gretings from Lima Perú.
That's totally awesome man ! Good job !
BTW, do you have a PDF that I really wanna print it out ?
thanks
Eldar, Felipe C, and Atilio: Thanks!
jspenguin: A little ;) Perhaps someone can set AES to music. Any ideas?
Marco Ramili: There is a PDF and PowerPoint version of it. The links are at the bottom of the post (see Update #2)
My brain sort of switched off in the middle of math part, but still... Impressive bro...
Jeff - a number of us at Galois loved your cartoon. Very accessible, but also full of deep insights. You (or your readers) might want to check out the implementation of AES in Cryptol, a domain-specific language for cryptography. The implementation is a part of the trial download available here.
brad: Speed was one aspect (see Act 1, Scene 16). It's also important that people be able to implement it correctly (among others). Most people said that any of the finalists would have been ok. That said... speed is important given how much it is used.
NTN: That's ok -- thanks for stopping by. Let me know if there's anything I can clarify.
Dylan McNamee: Interesting idea of a DSL for crypto. I talked about similar DSLs in a post awhile ago. That said, I'd probably still be too paranoid about shooting myself in the foot that I'd just use a good library myself. However, for things like embedded devices where no libraries might exist, I can see the usefulness.
Jeff - You're right - one can certainly write buggy programs even in a DSL. Cryptol was intended to help folks like crytpo-library writers eliminate those bugs. It can generate formal models that can be used with verification tools (such as SAT/SMT-solvers) to prove that generated programs are equivalent to the high-level specification. Cryptol has been used in just this environment to verify that VHDL implementations are equivalent to their Cryptol specification. This means it's very important to get the Cryptol spec correct in the first place, but the hope is that's easier to do in a DSL than in, say, C or VHDL.
Awesome comic
Jeff: you are so patient in explaining this so nicely... kudos!
kals
A picture is worth thousand words! that was just awesome :), loved it!
So i got caught looking at this at work. My boss is like "why are you looking at comics?!?" Then i let him read a few slides and waited for it to sink in...
Yeah! I'm not afeared [sic] of AES anymore.
I learned. I laughed. I want to tell other afeared peepuhl!
Thanks for the GREAT work.
Sparky
Many thanks for a great job. I will post a link to it on my Information Security 101 course web page so all the students can enjoy ...
That was fantastic.. :) AES is clear now. The human power is in math. I never doubted that.
Thank you,
Amine Guennoun
Thank-you! Very entertaining and informative.
hi sir
you presented excelently
thank you
but in the diagram of mixcolums you did not explained the concept compleately .i e mixcoulms with what and how.
if you can add it will be helpfull to other persons
thanking you sir by
good luck & thanks
Great work. I love it. Unfortunately this was not available when I had to revise for my Network Security exam :).
It was unbelievable to find this explanation for AES. Just thank you !
excellent! hope to see more comics from you soon :-)
I am actually having a problem understanding your mixcolumns slide (http://2.bp.blogspot.com/_Zfbv3mHcYrc/SrvUUSXTBTI/AAAAAAAAB0c/opkYXSJmzKE/s1600-h/aes_act_4_scene_16_mix_columns_math_1100.png)
i uploaded an 'annotated' version with the parts i don't understand. when i manually calculate it as you write at the top of the slide i get different results :/
http://img709.imageshack.us/img709/1161/aesact4scene16mixcolumn.jpg
figured out what the red/blue/green things are, but can't reproduce it.
http://img709.imageshack.us/img709/1161/aesact4scene16mixcolumn.jpg
besides, i think the red one is just false, how would you get x^6 twice?
Rumko, Kalpagam, MUDD, Sparky, Chris Mitchell, Christopher R. Jones, Anonymous #36/#37: Thanks for all of the continued encouraging comments on the post.
Dylan Mcnamee: I can agree that having a tool that generates verifiable code to create a library for a device where no better library already exists can be a good thing. The hard part then transitions to making sure the model that it generates from is correct. Point taken though.
Raffi: Nice.
Amine Guennoun: Math isn't all the power, but it sure helps :)
rajesh: As I'll note on thomas's comment below, there was a slight math error on that slide that I fixed, but I think your question is broader. For more details, see the code where I implemented MixColumns for explicit details on how to use that matrix. The idea is that the MixColumns step works on the state matrix. In particular, MixColumns operates on each column of this state matrix. Note that each column of the state can be thought of as describing 4 coefficients of a polynomial. We then multiply the matrix that I derived in Act 4, Scene 16 by each column that represents coefficients. The result of this (4x4) * (4x1) multiplication is a (4x1) column that is "mixed." The result of all of this is 4 mixed columns that become the new state.
Does that help?
Nam LE: Sorry about that, feel free to share this with future students to pay it forward.
thomas: Superb catch! You probably had a hard time understanding that slide because there was a superscript error. When I was cleaning up the scanned scene in Paint.NET, I accidentally turned the "2" into a "6". The correct version for the red bit is "03a_3 x^6 + 03a_3 x^2". If you refresh the post, you'll see the updated versions. Does it make sense now?
The top part you circled in blue, "03a_3 x^2 + (3a_2 + a_3)x + (3a_1 + a_2 + a_3)" is what I'm multiplying by the green part, "x^4 + 1". I chose the numbers in blue so that when I multiplied them by the green part, it'd end up cancelling some of the bigger terms. In particular, multiplying "3a_3 x^2" by "x^4 + 1" gives "03a_3 x^6 + 03a_3 x^2" (what you circled in red). Now, if you take "03a_3 x^6 + 03a_3 x^2" and add it to the part directly above it (which is b(x) = c(x) * a(x)), you'll get the part directly below the red box. Be sure to see that the part just below the blue had a "03a_3 x^6" and if I "add" in another "03a_3 x^6", these parts will cancel each other out in the new math (also known as a Galois Field). Note also how I tacked the leftover "03a_3 x^2" on to the end and got rid of the zero making it "3a_3 x^2". You can see the full result of adding this first term of the blue*green below the red. The result of the other terms of the blue * green is on the subsequent lines.
The only other tricky part is that I regrouped the terms at the end to make it fit a matrix form.
As a sanity check, I performed the full division out on paper and rechecked everything. I found another small error where I forgot an a_0 at the bottom on the x^3 term. That is, it was "(2a_3 + a_2 + a_1 + 3)x^3" and it should have been "(2a_3 + a_2 + a_1 + 3a_0)". I fixed this as well and updated the PowerPoint and PDF attachments (and on the Internet Archive and Sky Drive).
Thanks again! Let me know if you find any other problems.
All: Some people have asked about updates to this blog. I've been working hard on my next post for a few months now. It has involved writing a bit of code and simplifying some difficult math. I'm hoping to post it within a few weeks.
Jeff, thank you very much for the answer, appreciate it. now i understand how you get all the lines and let me tell you, it is completely different to how we learned how to do it. but it is way faster too ;)
thanks again.
This is a gift and very well done. Thank you.
Great work. It reminds me of the notes I took in crypto class a couple of decades ago...
... except that your math actually makes sense...
...and your artwork is better....
...MUCH better.
Anyway, thanks for posting it.
This was a fun blog
very good... even a layman can understand this stuff... its a really a very good explanation that i ever come across thank you
Should be be in the preface of CS cryptography textbooks! Terrific
No one will be able to explain Encryption (a complex subject for most of us) in such a simple manner.
Thanks and appreciate the effort to put this together.
Krishnaprabhu Balakrishnan
Very good work!
A very impressive work. Thanx a lot.
I was the 11,000 profile visitor. As a mathematician, that's pretty special for me. Thanks for the explanation, Jeff.
Awesome great job, thanks for taking the time to share :)
thank you so much for the comic. Actually I didn't plan to go into AES for my script, but after reading through the play I'll be well prepared for any question (in the last resort I would just recommend them to read through your story themselves ;-))
That really is a great way to understand the AES! Thanks a lot!
Post a Comment