Tuesday, September 22, 2009

A Stick Figure Guide to the Advanced Encryption Standard (AES)

(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...

introsadaes act 1 scene 03 cinderellaaes act 1 scene 04 startedaes act 1 scene 05 judgeaes act 1 scene 06 nbs decreeaes act 1 scene 07 luciferaes act 1 scene 08 anoint desaes act 1 scene 09 des ruledaes act 1 scene 10 des defeatedaes act 1 scene 11 triple desaes act 1 scene 12 nist decreeaes act 1 scene 13 ralliedaes act 1 scene 14 rijndaelaes act 1 scene 15 voteaes act 1 scene 16 wonaes act 1 scene 17 intelaes act 1 scene 18 crypto question

Act 2: Crypto Basics

aes act 2 scene 01 three big ideasaes act 2 scene 02 confusionaes act 2 scene 03 diffusionaes act 2 scene 04 key secrecyaes act 2 scene 05 aes details question

Act 3: Details

aes act 3 scene 01 sign thisaes act 3 scene 02 agreementaes act 3 scene 03 state matrixaes act 3 scene 04 initial roundaes act 3 scene 05 xor tributeaes act 3 scene 06 key expansion part 1aes act 3 scene 07 key expansion part 2aaes act 3 scene 08 key expansion part 2baes act 3 scene 09 key expansion part 3aes act 3 scene 10 intermediate round startaes act 3 scene 11 substitute bytesaes act 3 scene 12 shift rowsaes act 3 scene 13 mix columnsaes act 3 scene 14 add round keyaes act 3 scene 15 final roundaes act 3 scene 16 more rounds the merrieraes act 3 scene 17 tradeoffsaes act 3 scene 18 security marginaes act 3 scene 19 in picturesaes act 3 scene 20 decryptingaes act 3 scene 21 modesaes act 3 scene 22 questions what really happensaes act 3 scene 23 math

Act 4: Math!

aes act 4 scene 01 algebra classaes act 4 scene 02 reviewing the basicsaes act 4 scene 03 algebra coefficientsaes act 4 scene 04 remember multiplication growthaes act 4 scene 05 cant go biggeraes act 4 scene 06 clock mathaes act 4 scene 07 clock math polynomialsaes act 4 scene 08 divide by mxaes act 4 scene 09 logarithmsaes act 4 scene 10 using logarithmsaes act 4 scene 11 polynomial as byteaes act 4 scene 12 byte operationsaes act 4 scene 13 byte inversesaes act 4 scene 14 sbox mathaes act 4 scene 15 round constantsaes act 4 scene 16 mix columns mathaes act 4 scene 17 crib sheetaes act 4 scene 18 got it nowaes act 4 scene 19 so much moreaes act 4 scene 20 gotta goaes act 4 scene 21 the end

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:

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»
JD said...

Wow. That's just awesome. Great job!

BenC said...

...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.

Anonymous said...

Very sweet. Very impressive. Very.

TH said...

yay Grok! I remember that book... the human from mars who was raised by martians?

...but the math was interesting too. haha

Der said...

Best stick figure comic ever. So funny & insightful at the same time!

Daniel Meyer said...

I wondered if you would mention the block cipher modes since avoiding the bad ones is important -- but you did! (Act III, scene xxi!)

Justin Etheredge said...

You are my hero.

Anonymous said...

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!

Anonymous said...

I'd love to hear more about AES's resistance to linear and differential cryptanalysis and everything else in the third to last slide!

Anonymous said...

This was fun to wake up to. Thanks!

Gav said...

Excellent! Thanks very much! :-)

Shieldzee said...

Beyond great. Should be part of every CISSP prep class. Thanks.

Anonymous said...

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.

Jeff Barnes said...

Very Cool! Very entertaining stick figure comic.

Anonymous said...

This was so much better then reading source. Wonderfully done

Harold Fowler said...

Whoa way cool dude, I like it!

RT
www.online-privacy.us.tc

Markus Olsson said...

Amazing! Fantastic post, thanks!

Anonymous said...

I wish you had written all of my engineering math textbooks.

paisleyboxers said...

Fantastic! Thanks for the wonderful work on the details.

Edward said...

Oh man!! This is so awesome!

Thanks for putting this together. I hope to see more like this.

John Currah said...

wow, this is great! Thanks for sharing :)

Robert Talbert said...

I really want the AES crib sheet as a t-shirt.

X-Istence said...

Intel and AMD are just now getting on the bandwagon with something that Via has had for a long time (See their Padlock engine)

Sushant Srivastava said...

You are my hero

Ben said...

Great post! Crib Shirt++

I'll be poking around the linked project since my eyes glossed over during the math section.

Thanks :-)

Jonathan Kohls said...

Thanks man! Neat comic. The only problem is that I am now more interested in math.

Bas said...

really fun explanation, just what cryptography needed!

Anonymous said...

Well thought out - not an easy subject to put into that context. Kept me interested thru the end. Thanks for sharing!

MuslimDad said...

Absolutely wonderful. Thank you!

Konstantine said...

Wonderful! Thank you so much for this!

Paul Kuliniewicz said...

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.

अभिषॆक् said...

Dude, that's just awesome!

Jeff Moser said...

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.

fiXedd said...

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.

Sarwar Faruque said...

Absolutely awesome post! A lot of creative thought went into this. It really helps make AES a little easier to understand.

niranjan said...

That's a splendid way of explaining the tough points. Very nice work. Thanks.

Tigerbeard said...

Awesome. It's been a looong time since I've done math like that. Fantastic work!

5h4rk said...

Where does the initial key come from?

ABS said...

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.

Anonymous said...

Amazing, I really enjoyed this, thanks for sharing.

Anogar said...

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.

Mark said...

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.

simoncpu said...

Poor AES... Your efforts are underrated... I feel for you man. Hehehe...

digo said...

Awesome job! Loved the distributed.net reference.

Kristofer Pettersson said...

This was excellent!

Galilyou said...

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!

pointernil said...

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.

Anonymous said...

amazing thanks

Alan said...

Great morning reading, found you on Twitter. Very entertaining and informative!

Anonymous said...

Nice job! Thumbs up

Anonymous said...

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

Abhimanyu Grover said...

Damn that was geeky.

Anonymous said...

At the beginning of act 4, do Ashley and stick figure #3 ever get together? The suspense is killing me!

Fake51 said...

In a word: awesomeness!

Thanks very much for sharing this with the world :)

Mister Enigma said...

DSAOI FGVAG OISDF OIGOS AIDGO SDGIA SSASI ODOIA SDGOI ASDFF!

Glen.K.Peterson said...

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.

Guruprasad Kini (Guru) said...

Fantastic!

Glen.K.Peterson said...

+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!

Anonymous said...

I have been reading crypto algorithm descriptions since before the birth of DES. This is the best presentation I have ever seen.
Thank you.

Jordan said...

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...

Jordan said...

Second comment to say:

Crib Sheet T-Shirt +1

I would buy one without hesitation...

myer nore said...

Simply fabulous. Thank you so much. I love the stick figures and the crib sheet.

NoWine said...

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)

mikero said...

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".

Phil said...

Amazing, its like a massive XKCD

Anonymous said...

I just want to know if Ashley went out with the bored student..

Anonymous said...

Outstanding! Clear, informative, and entertaining!

Kumar said...

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...

Graeme said...

Excellent job!

Can you explain magnets to me?

John said...

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.

broken ladder said...

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

Satish said...

simply awesome... :)

abnerg said...

So what ever happened to Alice & Bob?

Bravo. Well done.

Anonymous said...

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!

Anonymous said...

very good. very informative.

I would like to print this out. Do you have a printer friendly version lying around anywhere?

Anonymous said...

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.

Anonymous said...

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
 

chudpi said...

This is excellent.
My math has been all but lost for years and yet I could follow it to the end.
Very nicely done!

Jonathan said...

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₇

Silas Snider said...

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!

epsos said...

Insanely long comic which should be a manga anyway !

Jeff Moser said...

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.

Jeff Moser said...

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... ;)

Luis said...

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

covert.c said...

Reliable sources say this great article has been making the rounds at RSA Security. ;-)

Anonymous said...

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

NinjaCross said...

This is totally awesome ! You should make an illustrated book with it :D

Gildas Deograt said...

If you've agreed, it'll give me (and students) much more fun in my training classes.

Thanks again!

Gildas Deograt

SuperJosemi said...

Simply great !!!!!

rahulnet said...

This is a classic ! Awesome work ..

- Rahul

Jeff Moser said...

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!

Pavan Alampalli said...

Awesome stuff. Really enjoyed it. Great job Jeff!!!

B0rh said...

Very good explanation, it is brilliant and funny, many thank you.

George said...

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...

Hussain said...

Fantastic, that AES Crib Sheet's definitely going on the cubefarm wall.

Anonymous said...

Nagyon fain! / Great!

MissXu said...

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.

Anonymous said...

Mix columns panel equation has one x missing next to parentheses in the bottom-left corner.

Jeff Moser said...

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.

urgestein said...

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.

drewster said...

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.

jideel said...

Great post. Thank you!

Jeff Moser said...

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!

drewster said...

Links are working for me. Thank you!

Luke Hebbes said...

Excellent work. I think I will use it for teaching purposes - with the interpretive dance extra credit of course.

alvinx said...

Thumbs up, thanks a lot... THAT was easy ;) LOL

Anonymous said...

just awesome, thank you!

Anonymous said...

thanks! making hard compsci seem easy is always greatly appreciated. <3

Glowing Face Man said...

Err, I think that's the most equations I've ever seen in one cartoon =P

Witek said...

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.

Paul said...

Nice.

It's worth noting that Sun has been doing this in their Niagara CPUs for some time.

Anonymous said...

Haha, really god job! Enjoyed whole comic!

Thommy M. Malmström said...

Just want to mention that the Sun Microsystems UltraSPARC T2 also have AES built in (since 2+ years...)

Mrinal Kant (मृणाल कान्त) said...

thanks for the great post! However, downloading the pdf fails (the link opens a page which complains of an error in parsing xml)

Mrinal Kant (मृणाल कान्त) said...

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++)
-------------------^

Jeff Moser said...

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!

Anonymous said...

If this PC had an APL keyboard, I could show you that AES takes just one line of code.
Excellent!

Anonymous said...

Great job !!

can said...

I've read the rijndael paper bu couldnt get it completely... but now... thank you sooo much!!! i appreciate it...

Jake Kasprzak said...

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.

Jeff Moser said...

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)

Anonymous said...

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

omid8bimo said...

very nice! i loved it & you put it simple.

Mrinal Kant (मृणाल कान्त) said...

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.

Anonymous said...

phenominal

mirabilos said...

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.)

AAA said...

AWESOME, SIMPLY AWESOME!

praveen said...

Awesome post !!
It's better illustrated than our class room AES slides :)

Anonymous said...

Where's Bruce's beard?

Olivier said...

Excellent. Just go on. Congratulations

Anonymous said...

agh.. math.. my brain hurts...

anyways, good way in explaining it.

Anonymous said...

fgvyy, EBG13 vf sha gbb. :)
tbbq jbex

Patel said...

just simply awesome....
hilarious...

AndrewDover said...

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.

Gonz00 said...

TL;DR
=)

Jeff Moser said...

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 :)

Anonymous said...

If only i got my hands on this when i made cryptography disciplin...

Brian said...

This is the most informative thing I've ever read on the internet. Awesome job.

robinmitra1 said...

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?

Jeff Moser said...

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.

Jeff Moser said...

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 :-)

Mike Parks said...

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!

Anonymous said...

SIMPLY AMAZING! Thank you so much.

Girish Narayanan said...

what a lucid explanation!!
Thank you....

robinmitra1 said...

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..

praveen said...

A video of this would be wicked cool !!

Joseph said...

Wow. Excellent.

Anonymous said...

Amazing work. Your funny little cartoon really helped me getting to understand aes a lot better.

Thanks a lot

Eugenio said...

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

Gilles Gravier said...

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

Shreyas said...

really fun-tastic job ! This was just great, I hope you win Oscar ! LOL

Mario Munda said...

Fantastic strip presentation! Bravo.

Anonymous said...

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.

Jeff Moser said...

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, Большое спасибо за перевод этого на русский язык. :-)

Zim said...

Thank you, very well explained! :D

quaelgeist said...

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.

Razzle Dazzle said...

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.

Prasad said...

awesome great job!
i was exited at the simplicity of the presentation..
am looking forward for next level!

Prasad

Niels Callesøe said...

I find this... awesome.

BK said...

Wow, just wow! I'm not huge on math, so the first round of explanation was all I realy understood. Cool stuff!

Jeff Moser said...

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 ;)

jspenguin said...

Is it better than this cryptosystem?

Eldar said...

Beautiful. Thank you!

Felipe C said...

I Loved it ... thanks!!

Atilio said...

A cool comic that teachers
University and students will have to read and enjoy.

Gretings from Lima Perú.

Marco Ramilli said...

That's totally awesome man ! Good job !
BTW, do you have a PDF that I really wanna print it out ?

thanks

Jeff Moser said...

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)

NTN said...

My brain sort of switched off in the middle of math part, but still... Impressive bro...

Dylan McNamee said...

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.

Jeff Moser said...

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.

Dylan McNamee said...

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.

Rumko said...

Awesome comic

Kalpagam said...

Jeff: you are so patient in explaining this so nicely... kudos!
kals

MUDD said...

A picture is worth thousand words! that was just awesome :), loved it!

Raffi said...

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...

Anonymous said...

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

Chris Mitchell said...

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 ...

Anonymous said...

That was fantastic.. :) AES is clear now. The human power is in math. I never doubted that.
Thank you,
Amine Guennoun

Christopher R. Jones said...

Thank-you! Very entertaining and informative.

rajesh said...

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

Nam LE said...

Great work. I love it. Unfortunately this was not available when I had to revise for my Network Security exam :).

Anonymous said...

It was unbelievable to find this explanation for AES. Just thank you !

Anonymous said...

excellent! hope to see more comics from you soon :-)

thomas said...

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

thomas said...

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?

Jeff Moser said...

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.

Jeff Moser said...

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.

thomas said...

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.

7 said...

This is a gift and very well done. Thank you.

willdye said...

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.

Kelly said...

This was a fun blog

Shivashankar B said...

very good... even a layman can understand this stuff... its a really a very good explanation that i ever come across thank you

Anonymous said...

Should be be in the preface of CS cryptography textbooks! Terrific

Krishnaprabhu Balakrishnan said...

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

Adam said...

Very good work!

JR said...

A very impressive work. Thanx a lot.

David's Holla Atchya! Blog said...

I was the 11,000 profile visitor. As a mathematician, that's pretty special for me. Thanks for the explanation, Jeff.

Anonymous said...

Awesome great job, thanks for taking the time to share :)

Anonymous said...

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 ;-))

H.V. said...

That really is a great way to understand the AES! Thanks a lot!

«Oldest ‹Older   1 – 200 of 235   Newer› Newest»