A stick figure guide to the Advanced Encryption Standard (AES) (2009) | Hacker News Reader

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

moserware.com

70 pointsropable14 comments

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

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

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.

Still saves CPU cycles. We're talking about max 7GB/s for PCIe Gen4x4. Software based encryption also add small latency.

Only the higher-end CPUs like i5 and i7 in laptops. IIRC and no clue about AMD

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.

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.

I'm not convinced that people who aren't able to learn enough to use AES properly will fare that much better with ChaCha20, Poly1305, and asymmetric key agreement. ChaCha doesn't make the key agreement stuff easier and if they're going to blow their feet off it's probably going to be there.

GCM wasn't "MacGyvered" any more than ChaChaPoly. ChaCha doesn't give you authentication by itself, and you need authentication. You could in theory do ChaCha/GMAC or AES-CTR/Poly1305 and be okay if you engineered it properly. I think NaCl already has AES-CTR/Poly1305 in it.

What does asymmetric key agreement have to do with using ChaCha?

There are definitely ways in which GCM is more brittle than ChaCha; in particular, you can use random nonces with XChaCha, and you technically can't safely do that with GCM. But really, throw a dart, your outcome will be the same either way.

You mean this?

https://crypto.stackexchange.com/questions/42982/safety-of-r...

I personally prefer the SIV modes, but using a sequential nonce within a session is pretty much always better due to birthday attack stuff.

Cryptography does advance over time. When GCM was introduced it was when everyone realized that you must always have authentication and they wanted a faster auth mode than HMAC.

Makes me wonder what new understandings might be coming down the road other than the obvious quantum computing factor. The most recent one I remember is the risk of combining compression with crypto if the attacker can influence anything in the compressed data.

> AES is significantly faster in hardware if there is support.

this means relying on something that you might not be able to influence: borked HW implementations. you are essentially saying rolling out to unknown broken devices is fine because the majority of users where HW isn't broken can benefit from better performance. that's a hell of a trolley problem and precisely why OTR switched to ChaCha/Poly.

I'm not talking about one being better than the other but implementation matters and those projects (like OTR) where security is the only value proposition, then maybe AES is a risky choice?

Sure AES is maybe the victim of it's own success and if chips get ChaCha implementations in HW then we'd also have broken implementations at scale. But that wasn't my point.

Broken AES hardware would be extremely obvious via tests against known test vectors. Intentionally backdoored hardware is possible but that's a concern no matter what you are running. If your hardware is hostile you are screwed.

Past related:

A Stick Figure Guide to the Advanced Encryption Standard (AES) (2009) - 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 - Aug 2011 (24 comments)

A Stick Figure Guide to the Advanced Encryption Standard (AES) - https://news.ycombinator.com/item?id=836761 - Sept 2009 (8 comments)

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

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

Reply on news.ycombinator.com