4 ms·

A stick figure guide to the Advanced Encryption Standard (AES) (2009)

70 points by ropable 5y ago

dang 5y ago
Past related: A Stick Figure Guide to the Advanced Encryption Standard (AES) (2009) - https://news.ycombinator.com/item?id=16722368 https://news.ycombinator.com/item?id=16722368 - March 2018 (2 comments) A Stick Figure Guide to the Advanced Encryption Standard (AES) - https://news.ycombinator.com/item?id=2898718 https://news.ycombinator.com/item?id=2898718 - Aug 2011 (24 comments) A Stick Figure Guide to the Advanced Encryption Standard (AES) - https://news.ycombinator.com/item?id=836761 https://news.ycombinator.com/item?id=836761 - Sept 2009 (8 comments)
Moodles 5y ago
This is a beautifully succinct animation of how AES works: https://youtu.be/gP4PqVGudtg https://youtu.be/gP4PqVGudtg
DyslexicAtheist 5y ago
AES gets all the marketing glory. You ask the company how are they doing security? Marketing person says: "It's secure we're using AES.". AES is often the only technical word they use when they say it's secure in product brochures because they know this is going to satisfy a clueless CISO with a purchasing budget to cover their behind. But fast forward from 2009 take a look at OTR and their decision to switch from AES to ChaCha20 (see https://github.com/otrv4/otrv4/blob/master/architecture-decisions/001-security-level.md https://github.com/otrv4/otrv4/blob/master/architecture-deci...) - the document nicely highlights why AES might not be the best choice: > We use ChaCha20 as the encryption stream cipher because it is faster than AES in software-only implementations, it is not sensitive to timing attacks and has undergone rigorous analysis ([3], [4] and [5]). We chose this over AES as future advances in cryptanalysis might uncover security issues with it, its performance on platforms that lack dedicated hardware is slow, and many AES implementations are vulnerable to cache-collision timing attacks [[6]]. But AES is so much faster because some SSD's can offload it to hardware right? See: 256-bit AES encryption broken in SandForce SSD controllers: https://techreport.com/news/23096/256-bit-aes-encryption-broken-in-sandforce-ssd-controllers/ https://techreport.com/news/23096/256-bit-aes-encryption-bro... Self-encrypting SSDs can easily be cracked: https://portswigger.net/daily-swig/self-encrypting-ssds-can-easily-be-cracked https://portswigger.net/daily-swig/self-encrypting-ssds-can-... Crucial and Samsung SSDs' Encryption Is Easily Bypassed: https://www.tomshardware.com/news/crucial-samsung-ssd-encryption-bypassed,38025.html https://www.tomshardware.com/news/crucial-samsung-ssd-encryp... ... Also in practice it's not the crypto that gets attacked but the implementation of said crypto. So it seems that if I have a large number of architectures and devices my software might be running on which is outside my control then the ability to predict how my crypto implementation will affect the performance of my device is a good enough reason alone to not use AES. But I might be wrong maybe others can throw in some thoughts.
- causi 5y ago
  But AES is so much faster because some SSD's can offload it to hardware right? See: AES hardware on SSD controllers is just marketing. CPUs have had hardware AES support since 2010.
  - fomine3 5y ago
    Still saves CPU cycles. We're talking about max 7GB/s for PCIe Gen4x4. Software based encryption also add small latency.
  - MonaroVXR 5y ago
    Only the higher-end CPUs like i5 and i7 in laptops. IIRC and no clue about AMD
- api 5y ago
  There's a lot of FUD and misunderstanding here. Phrases like "we are secured with AES" are just marking babble by people who don't understand the details. AES is significantly faster in hardware if there is support. The vast majority of non-embedded chips (and some embedded) now have AES support in the CPU core including virtually all x64 and aarch64 chips sold today. AES is slower than ChaCha without hardware support but constant time "bit slicing" implementations exist that are fast enough for most use cases. The broken crypto you cite was due to bad implementations or improper use. AES was not broken. You're definitely right that the implementation almost always is what gets attacked, but that's as true with ChaCha as it is with AES. Any crypto can be used incorrectly and any software can have bugs. Nothing wrong with ChaCha, but don't spread FUD.
  - NohatCoder 5y ago
    Included in the box when you buy an AES are several different cipher modes, many of them are most useful for injecting slugs of metal into you own feet. The one you should use, AES-GCM, wasn't even in the original box, but was MacGyvered later.
    - 5y ago
dragontamer 5y ago
Confusion / S-Boxes are easy enough, but very subtle. The cartoon (purposefully) skips over differential cryptography and the design of S-Boxes. In effect: S-Boxes may be a simple step, but designing the S-Box is anything but simple. --------- In contrast, the MixColumns step looks difficult and requires a lot of words. But conceptually its much easier to understand (!!!!). I don't like how the cartoon goes over it however, so here's my attempt. Finite Fields / Galois Field arithmetic is a form of mathematics where "addition" and "multiplication" have been redefined for new features. The mechanics are simple, but take a lot of words. Finite Fields have a number of properties: * Addition exists. * Negation exists for all numbers. 1 + (-1) == 0. 2 + (-2) == 0. For all X, the number (-X) exists. * Multiplication exists. * Reciprocals exist for all numbers except 0. That is: 2 * (1/2) == 1. 3 * (1/3) == 1 for all numbers. For all X, the number (1/X) exists... except (1/0), which never exists. * There are a _finite_ number of... numbers. In AES, we use GF(2^8), aka 8-bits, numbers between 0 to 255. GF(2^8) was chosen because 8-bit numbers are common in computers. The number 256 does NOT exist in GF(2^8). * Wait wait wait: how does negation or reciprocals exist? What is -0x53? What is 1/0x53? Apologies, but Imma skip that. This is the part that requires too much text and discussion and I'm already getting to verbose. That being said: -0x53 == 0x53. Every number is its own inverse in addition. 1/0x53 == 0xCA. Don't ask me how I got it, but rest assured that 0x53 * 0xCA == 1, and all the properties of multiplication / reciprocals exist and work how you'd expect. Magically. ------------ Okay, so this multiplication -- and reciprocal thing. This is the important bit. This means that you can "diffuse" and "inverse-diffuse" with the following methodology: Multiply by X to "diffuse" the bits around. When you're decryptiong, Multiply by 1/X to undo the encryption process. ------- That's it. Yeah, I spent a wall of text on this subject, but its really that simple. Multiply by X to perform encryption-diffusion. Multiply by 1/X to undo the step. But it can't be "normal" multiplication or "normal" addition (!!!). After all, 1/5 (that is, 0.2) does NOT exist in the realm of numbers between 0 to 255 (aka: 8-bit numbers). You need to do the "magical" GF(2^8) multiply. In "Magical" GF(2^8) land... the number 1/5 exists and is 0x52. Creation of this multiplication table is kinda difficult, but if you "believe" me, you can just look at the table and see how it works: https://tratliff.webspace.wheatoncollege.edu/2016_Fall/math202/inclass/sep21_inclass.pdf https://tratliff.webspace.wheatoncollege.edu/2016_Fall/math2... -------- One last step: MixColumns actually operates over 32-bit numbers, not 8-bit numbers. But each MixColumns operation is just a GF(2^8) multiplication or addition, or a trivial "movement" of bits. Once you understand the "times X" to encrypt vs "Times 1/X" to decrypt thing, all the steps of MixColumns individually make sense. Wait, what is "X" ?? That's the *key* of course. Data * key == ciphertext. Ciphertext * (1/key) == data. Well, effectively that's what it comes down to. A lot of complicated steps to get there, but that's it.

70 points by ropable 5y ago

dang 5y ago

Past related: A Stick Figure Guide to the Advanced Encryption Standard (AES) (2009) - https://news.ycombinator.com/item?id=16722368 https://news.ycombinator.com/item?id=16722368 - March 2018 (2 comments) A Stick Figure Guide to the Advanced Encryption Standard (AES) - https://news.ycombinator.com/item?id=2898718 https://news.ycombinator.com/item?id=2898718 - Aug 2011 (24 comments) A Stick Figure Guide to the Advanced Encryption Standard (AES) - https://news.ycombinator.com/item?id=836761 https://news.ycombinator.com/item?id=836761 - Sept 2009 (8 comments)

Moodles 5y ago

This is a beautifully succinct animation of how AES works: https://youtu.be/gP4PqVGudtg https://youtu.be/gP4PqVGudtg

DyslexicAtheist 5y ago

AES gets all the marketing glory. You ask the company how are they doing security? Marketing person says: "It's secure we're using AES.". AES is often the only technical word they use when they say it's secure in product brochures because they know this is going to satisfy a clueless CISO with a purchasing budget to cover their behind. But fast forward from 2009 take a look at OTR and their decision to switch from AES to ChaCha20 (see https://github.com/otrv4/otrv4/blob/master/architecture-decisions/001-security-level.md https://github.com/otrv4/otrv4/blob/master/architecture-deci...) - the document nicely highlights why AES might not be the best choice: > We use ChaCha20 as the encryption stream cipher because it is faster than AES in software-only implementations, it is not sensitive to timing attacks and has undergone rigorous analysis ([3], [4] and [5]). We chose this over AES as future advances in cryptanalysis might uncover security issues with it, its performance on platforms that lack dedicated hardware is slow, and many AES implementations are vulnerable to cache-collision timing attacks [[6]]. But AES is so much faster because some SSD's can offload it to hardware right? See: 256-bit AES encryption broken in SandForce SSD controllers: https://techreport.com/news/23096/256-bit-aes-encryption-broken-in-sandforce-ssd-controllers/ https://techreport.com/news/23096/256-bit-aes-encryption-bro... Self-encrypting SSDs can easily be cracked: https://portswigger.net/daily-swig/self-encrypting-ssds-can-easily-be-cracked https://portswigger.net/daily-swig/self-encrypting-ssds-can-... Crucial and Samsung SSDs' Encryption Is Easily Bypassed: https://www.tomshardware.com/news/crucial-samsung-ssd-encryption-bypassed,38025.html https://www.tomshardware.com/news/crucial-samsung-ssd-encryp... ... Also in practice it's not the crypto that gets attacked but the implementation of said crypto. So it seems that if I have a large number of architectures and devices my software might be running on which is outside my control then the ability to predict how my crypto implementation will affect the performance of my device is a good enough reason alone to not use AES. But I might be wrong maybe others can throw in some thoughts.

causi 5y ago
But AES is so much faster because some SSD's can offload it to hardware right? See: AES hardware on SSD controllers is just marketing. CPUs have had hardware AES support since 2010.
- fomine3 5y ago
  Still saves CPU cycles. We're talking about max 7GB/s for PCIe Gen4x4. Software based encryption also add small latency.
- MonaroVXR 5y ago
  Only the higher-end CPUs like i5 and i7 in laptops. IIRC and no clue about AMD
api 5y ago
There's a lot of FUD and misunderstanding here. Phrases like "we are secured with AES" are just marking babble by people who don't understand the details. AES is significantly faster in hardware if there is support. The vast majority of non-embedded chips (and some embedded) now have AES support in the CPU core including virtually all x64 and aarch64 chips sold today. AES is slower than ChaCha without hardware support but constant time "bit slicing" implementations exist that are fast enough for most use cases. The broken crypto you cite was due to bad implementations or improper use. AES was not broken. You're definitely right that the implementation almost always is what gets attacked, but that's as true with ChaCha as it is with AES. Any crypto can be used incorrectly and any software can have bugs. Nothing wrong with ChaCha, but don't spread FUD.
- NohatCoder 5y ago
  Included in the box when you buy an AES are several different cipher modes, many of them are most useful for injecting slugs of metal into you own feet. The one you should use, AES-GCM, wasn't even in the original box, but was MacGyvered later.
  - 5y ago

dragontamer 5y ago

Confusion / S-Boxes are easy enough, but very subtle. The cartoon (purposefully) skips over differential cryptography and the design of S-Boxes. In effect: S-Boxes may be a simple step, but designing the S-Box is anything but simple. --------- In contrast, the MixColumns step looks difficult and requires a lot of words. But conceptually its much easier to understand (!!!!). I don't like how the cartoon goes over it however, so here's my attempt. Finite Fields / Galois Field arithmetic is a form of mathematics where "addition" and "multiplication" have been redefined for new features. The mechanics are simple, but take a lot of words. Finite Fields have a number of properties: * Addition exists. * Negation exists for all numbers. 1 + (-1) == 0. 2 + (-2) == 0. For all X, the number (-X) exists. * Multiplication exists. * Reciprocals exist for all numbers except 0. That is: 2 * (1/2) == 1. 3 * (1/3) == 1 for all numbers. For all X, the number (1/X) exists... except (1/0), which never exists. * There are a _finite_ number of... numbers. In AES, we use GF(2^8), aka 8-bits, numbers between 0 to 255. GF(2^8) was chosen because 8-bit numbers are common in computers. The number 256 does NOT exist in GF(2^8). * Wait wait wait: how does negation or reciprocals exist? What is -0x53? What is 1/0x53? Apologies, but Imma skip that. This is the part that requires too much text and discussion and I'm already getting to verbose. That being said: -0x53 == 0x53. Every number is its own inverse in addition. 1/0x53 == 0xCA. Don't ask me how I got it, but rest assured that 0x53 * 0xCA == 1, and all the properties of multiplication / reciprocals exist and work how you'd expect. Magically. ------------ Okay, so this multiplication -- and reciprocal thing. This is the important bit. This means that you can "diffuse" and "inverse-diffuse" with the following methodology: Multiply by X to "diffuse" the bits around. When you're decryptiong, Multiply by 1/X to undo the encryption process. ------- That's it. Yeah, I spent a wall of text on this subject, but its really that simple. Multiply by X to perform encryption-diffusion. Multiply by 1/X to undo the step. But it can't be "normal" multiplication or "normal" addition (!!!). After all, 1/5 (that is, 0.2) does NOT exist in the realm of numbers between 0 to 255 (aka: 8-bit numbers). You need to do the "magical" GF(2^8) multiply. In "Magical" GF(2^8) land... the number 1/5 exists and is 0x52. Creation of this multiplication table is kinda difficult, but if you "believe" me, you can just look at the table and see how it works: https://tratliff.webspace.wheatoncollege.edu/2016_Fall/math202/inclass/sep21_inclass.pdf https://tratliff.webspace.wheatoncollege.edu/2016_Fall/math2... -------- One last step: MixColumns actually operates over 32-bit numbers, not 8-bit numbers. But each MixColumns operation is just a GF(2^8) multiplication or addition, or a trivial "movement" of bits. Once you understand the "times X" to encrypt vs "Times 1/X" to decrypt thing, all the steps of MixColumns individually make sense. Wait, what is "X" ?? That's the *key* of course. Data * key == ciphertext. Ciphertext * (1/key) == data. Well, effectively that's what it comes down to. A lot of complicated steps to get there, but that's it.