Live data from Hacker News

Understanding how AES encryption works

nakabonne.dev

31–40 of 41 posts

Re: Understanding how AES encryption works

#31
post #2

I don't want to snipe but it's a peeve of mine: every article about AES talks about SubBytes and ShiftRows or whatever, which is information you will never, ever use , even if your career takes a turn into cryptography engineering, but nobody talks about block cipher modes, which are basically the most important thing you can know about block cryptography.

But it’s an article about AES, which is the block cipher. Block cipher modes are important to a larger solution built on AES, but they are orthogonal and not even specific to AES.

No, this is about "How AES encryption works". Emphasis mine. AES internals are interesting, but they're not specific to how AES encryption works. EG AES-CTR-DRBG is a CSPRNG using AES, not an encryption system. AES-CMAC is a MAC using AES, not an encryption system. AES can be used for lots of non-encryption tasks, so the author should have either dropped "encryption" from the title or included information on what's needed to turn AES from a block cipher into an encryption algorithm.

Re: Understanding how AES encryption works

#32
post #10

Earlier quoted context omitted.

To be fair, I'm not in cryptography engineering and had to understand all those details for an implementation security review. But I completely agree on the block cipher modes thing, a lot of people don't realize what they are doing and just use whatever sounds good, even if it is ECB and it is not relevant in the context.

It's always this: AES-CBC with 1) no authentication whatsoever, or 2) fixed IV, "but it's random, I threw the dices myself!!", or 3) fixed key, no forward secrecy of any kind

With modern CPU-cores hitting 2x AES-instructions per clocktick, CBC-mode is going obsolete. CBC-mode cannot perform 2-AES iterations in parallel. You need to use CTR-mode.

CTR-mode however has been largely subsumed by GCM (Galois Counter Mode), and all of a sudden you need to learn Galois fields anyway (which AES is an excellent case-study in GF(2^8)).

------

AVX512 performs 4x AES-instructions per clock tick by the way, to fill up the entire 512-bit register. You're only reaching that parallelism with CTR mode or GCM mode.

Re: Understanding how AES encryption works

#33

> It involves multiplication operations in a finite field, hence this step is a bit tough to describe. See Wikipedia for more details. Woah woah woah!!!! MixColumns is incredibly important to understanding AES! I don't think it should be glossed over, or just pointed to Wikipedia (which is... sub-par IMO... as an explanation source). Lets break things down: 1. Galois Fields / Finite Fields are a special number system…

Addendum:

If anyone's curious about Galois Theory, this looks like a good place to start: https://www.gfuzz.de/AES_1.html

Re: Understanding how AES encryption works

#35

> It involves multiplication operations in a finite field, hence this step is a bit tough to describe. See Wikipedia for more details. Woah woah woah!!!! MixColumns is incredibly important to understanding AES! I don't think it should be glossed over, or just pointed to Wikipedia (which is... sub-par IMO... as an explanation source). Lets break things down: 1. Galois Fields / Finite Fields are a special number system…

Addendum: If anyone's curious about Galois Theory, this looks like a good place to start: https://www.gfuzz.de/AES_1.html

I dunno if its just "how I learned it", but experiments over the GF(5) prime field, followed by the GF(2) then GF(2^x) extension fields has always made the most sense in my brain.

GF(5) is a prime field and is much easier to think about. You have 0, 1, 2, 3, 4 as your numbers (and they're "true numbers", not yet polynomials).

The most natural generator is 2.

* 2^0 == 1 mod 5

* 2^1 == 2 mod 5

* 2^2 == 4 mod 5

* 2^3 == 8 mod 5 == 3

* 2^4 == 2^3 * 2 == 3 * 2 == 6 mod 5 == 1 == 2^0

Because 2^4 == 2^0 == 1, you have your loop. All non-zero elements are created by this sequence (because 2 is an appropriate generator). Define multiplication to be consistent with these numbers (and it happens to line up with normal multiplication).

For example:

* 2^4 * 2^3 == 1 * 3 == 2^7 == 2^4 * 2^3 == 2^0 * 2^3 == 3.

-------

Extend the cycle over the negative numbers, and you remain consistent:

* 2^0 == 1 mod 5

* 2^-1 == 3 mod 5

* 2^-2 == 4 mod 5

* 2^-3 == 2 mod 5

* 2^-4 == 1 mod 5 == 2^0

By extending into the negative exponents, we've invented division that's 100% consistent with all other math. Notice that 2^-1 == 3, which is 2's inverse.

2^2 == 2^-2, which is its own inverse. Notice that 4 * 4 == 2^2 * 2^2 == 2^4 == 1. Any number times 4 twice equals itself.

Remember, GF(5) is just simple mod-5 arithmetic. We've redefined multiplication to the above attributes, but it works out how you'd expect. Lets take some random examples of multiplicative inverses / division in GF(5), but "extended" over normal integers outside of the modular space to show you this really is amazing and it works.

* 3 * 2 == 6 mod 5 == 1.

* 4 * 2 * 3 == 24 mod 5 == 4 (notice: 2 * 3 is 1, so when 4 * 1 == 4)

* 4 * 4 == 16 mod 5 == 1

* 2 * 4 * 4 == 32 mod 5 == 2 (notice: 4 is equal to 1/4. So 2 * 4/4 == 2 * 4 * 4 == 2)

-----

A similar exercise can be done over addition. Then a similar exercise can be done over distributive property and even polynomials / quadratic equation / cubics and more!

Logarithms, Square Roots. Everything. All the math you ever learned: shrunk down into the exact space of {0, 1, 2, 3, 4} numbers.

--------

GF(5) is awkward for computers however. To make this "reasonable" for computers, we need to convert it into bits and bytes. Shrink the space down to GF(2) (0 and 1), then extend the space into GF(2^8). Extension fields (taking a "power" of the prime) are... complicated. Very complicated.

An extension field is the GF-version of "complex numbers". You invent a polynomial over "x" (or some indeterminate variable). Complex numbers call it "i", electrical engineers call it "j". In the Complex world, i^4 == 1 (the 4th root of 1 is i). But in GF-version, the variable depends on the size of your field. A GF(2^8) will have x^255 == 1... so you have a much larger "loop" so to speak, but otherwise functions very similar to the Complex i.

But hopefully the experiments in GF(5) show why cryptographers love to use GF() fields in general. Its very useful to have all numbers "loop" back into themselves.

Re: Understanding how AES encryption works

#36
post #2

I don't want to snipe but it's a peeve of mine: every article about AES talks about SubBytes and ShiftRows or whatever, which is information you will never, ever use , even if your career takes a turn into cryptography engineering, but nobody talks about block cipher modes, which are basically the most important thing you can know about block cryptography.

Block ciphers are modelled formally as indexed permutation groups, which you do round-by-round, irrespective of the mode of operation. ShiftRows and SubBytes heavily impact this formal model while the mode of operation is not. Your thinking is too practical and "close to code" and as usual, it makes the false claim that the mathematical rigor is unnecessary in cryptology

Why do you think tptacek's thinking "makes the false claim that the mathematical rigor is unnecessary in cryptology"? It doesn't seem to me like either the article or the comment talk about mathematical rigor.

Re: Understanding how AES encryption works

#37

Oaw, that was an awful read. I think I prefer pure math, as described in original paper than ...this, whatever was that. The worse article I've read this month.

Ok, but please don't be a jerk on HN.

Edit: it looks like we've had to ask you this many times. Would you please review https://news.ycombinator.com/newsguidelines.html and take the intended spirit of this site more to heart? I don't want to ban you, but comments like this poison the community here.

Re: Understanding how AES encryption works

#38

While we're here, Christof Paar's 'Introduction to Cryptography' lecture series (freely available on YouTube here in English: https://www.youtube.com/channel/UC1usFRN4LCMcfIV7UjHNuQg , originally delivered at Ruhr University Bochum) is a really excellent explanation of the internals of a number of crytographic algorithms. The lecture on Galois Fields ( https://www.youtube.com/watch?v=x1v2tX4_dkQ ) is especially usefu…

I love the shoutout. As a grad student at WPI somewhere around 2000 or so when AES was first, I took his "Cryptography and Data Security" course and my end of class project was a complete implementation (in C) of Rijndael. (I later found out that others in the class chose to implement portions of the cipher and not the whole thing.) It was definitely one of my favorite grad classes.

Re: Understanding how AES encryption works

#39
post #2

I don't want to snipe but it's a peeve of mine: every article about AES talks about SubBytes and ShiftRows or whatever, which is information you will never, ever use , even if your career takes a turn into cryptography engineering, but nobody talks about block cipher modes, which are basically the most important thing you can know about block cryptography.

I disagree.

- There is plenty of talk of block cipher modes. What do you mean "nobody talks about" them?

- Block cipher modes are critically important but a lot of them are fairly straightforward and standard.

- Understanding how to design a pseudorandom permutation is where most of the ingenuity of cryptography is.

- If you are doing cryptanalysis, you definitely want to know about SubBytes and ShiftRows, etc.

Re: Understanding how AES encryption works

#40
post #37

Oaw, that was an awful read. I think I prefer pure math, as described in original paper than ...this, whatever was that. The worse article I've read this month.

Ok, but please don't be a jerk on HN. Edit: it looks like we've had to ask you this many times. Would you please review https://news.ycombinator.com/newsguidelines.html and take the intended spirit of this site more to heart? I don't want to ban you, but comments like this poison the community here.

heya dang, long time no see. How you doing man? Glad to see you still doing a great job, keep it up. When was last time you slapped me? Must be over a year, right?

OK, promise you this - in 2021 you'll have no worries about me, but c'mon, let me have one slip in 2022, yes? Just to see you're still around ;).

Post reply on HN