Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Understanding how AES encryption works

nakabonne.dev

Post reply on HN
Print view View original

21–30 of 41 posts

Re: Understanding how AES encryption works

#21

Post by cryptXTS »

maqp wrote: post #10
RaitoBezarius wrote: post #3

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

cryptsetup -c serpent-xts-plain64 -s 512 -h sha512 -i 123456 luksFormat /dev/ice /path/to/8M/dev/urandom/keyfile

(serpent wasn't chosen by NSA because it's the best, if you want inferior AES, then change serpent to AES.)

Re: Understanding how AES encryption works

#22

Post by JoachimSchipper »

arcticbull wrote: post #17
riobard wrote: post #12

Earlier quoted context omitted.

Is there any software-base implementation of AES that is NOT vulnerable to timing attacks and other side channel weakness and with reasonable performance (to the limit of the hardware)?

I was under the impression there were, but I'm no expert. [1] [1] https://www.iacr.org/archive/ches2009/57470001/57470001.pdf

Yes, that's the generic solution. They claim ~7 cycles per byte for 4096-byte blocks on the newest CPU tested, but I don't know what the performance would be on CPUs from 2020. (For context, per https://eprint.iacr.org/2018/392, AES-NI is more than ten times faster.)

Of course, AES-NI is generally preferable if you have it; and people use ChaCha on mobile platforms that don't have AES-NI but do have NEON (or another SIMD).

Re: Understanding how AES encryption works

#23

Post by SAI_Peregrinus »

This is called "Understanding How AES Encryption Works", but it doesnt describe that.

AES is a "block cipher", a primitive that approximates a pseudorandom permutation (PRP) and can be used to build a variety of functions. E.g. AEADs like AES-CCM and AES-GCM, encryption like AES-CTR, message authentication codes like CMAC, hash functions like Whirlpool (that uses a modified AES), and random number generators like AES-DRBG. In theory one could even build a public-key signature scheme from AES: use it in a Sponge construction to make a hash function, then use that to construct a hash-based signature scheme. The only thing I don't know how to build using just a PRP is a Key Encapsulation Mechanism.

This article is a bit like writing "How To Program In C" and talking about NAND gates and ALUs and instruction decoders.

Re: Understanding how AES encryption works

#24

Post by shuringai »

tptacek wrote: 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

Re: Understanding how AES encryption works

#25

Post by opheliate »

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 useful in understanding AES, and explains where some of the operations described in the blog linked here actually come from (i.e: S-Boxes used in AES are derived from inversion in finite fields).

Re: Understanding how AES encryption works

#26

Post by dragontamer »

> 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. Instead of "choosing better numbers", Mathematicians "choose better addition/multiplies". That's right, you change the definition of addition / multiply to better suit your mathematical needs.

2. All operations in a finite-field self-feed back into the same finite-field... I joke that its a "human centipede" of math because you can just keep feeding yourself the same crap! Addition, Subtraction, Multiplication, Division, Logarithm, Exponent, Square-roots, Cube-Roots, etc. etc. All operations are GUARANTEED to return to the finite field specified. In the case of AES, the 2^8 field (256 "numbers", usually labeled 0 through 255) is chosen. No matter how crazy the math gets, you always return to the finite-field at every step.

2.5 -- Technically, they're not actually numbers... they're polynomials. But because they're represented by 0x00 through 0xFF, you can think of them as numbers with weird add/multiply rules.

2.75 -- Knuth notes that real numbers are just polynomials anyway. 525600 == 5 * 10^5 + 2 * 10^4 + 5 * 10^3 + 6 * 10^2. If you're having issues thinking about "GF polynomials are pretending to be numbers", just think about normal numbers, which always have a polynomial representation. The radix-point / decimal-point is just where the 10^0 is located, and then 10^-1, 10^-2 (etc. etc) move forward. Then, instead of having "10" as a specified radix, the radix is now "x" (the polynomial's variable).

3. Finite Field division is very, very similar to "normal" division. As you may remember from elementary school, division "mixes up the numbers real good". Well, in Finite Field arithmetic, all divisions can be optimized to a multiplication. This matches your elementary-school level thinking: 5/7 is "5 divided by 7", but ALSO "5 times 1/7th" in normal math. The same is true in Finite Fields, EXCEPT 5/7th is actually a number (erm... polynomial) in the 0x00 to 0xFF space. Also 5/7 == 5 * (1/7) == 5 * 7^-1.

3.5 -- The magic of making 5/7 == 5 * 1/7 == 5 * 7^1 is WHY cryptographers use Galois Fields. When the math / arithmetic becomes more important than the numbers themselves, its very natural to just switch to GF-field representation.

4. Well... hold on. We have GF(2^8) "numbers" (erm... 8-bit polynomials) but AES is over 128-bits. Well... GF(2^8) is more efficient to implement in software because you only need a lookup table of size 256. (From a software perspective: you can either make addition or multiplication efficient on computers. The other operation needs a lookup table. Most programmers choose "XOR" to be the efficient add, and then a lookup table for multiply/divide).

4.5 Because we're stuck with GF(2^8) (because it's the mid 90s and GF-instructions don't exist on CPUs yet and you want tiny lookup tables that fit inside of tiny L1 caches of tiny 90s computers), we extend the GF(2^8) == 8-bit by making a 4x4 matrix (128-bits total for the full 4x4 matrix, each column a 32-bit integer).

5. Instead of just doing one or two multiply / divide operations per element, lets "mix up the numbers real good" with a Matrix-multiplication.

6. As you may remember from linear algebra class: the inverse of a matrix doesn't necessarily exist. But Galois Fields make it easier to find matrix-inverses. In particular, division is always possible, so its far easier to find an inverse of a matrix.

6.5 Assume we were using "normal 8-bit integers" instead of GF(2^8), and we have a simple [[1 0] [0 2]] 2x2 Matrix. To invert the matrix, you need to divide by 2, but what is 1/2 in integer math? Well, it doesn't exist (0.5, or "one half" is NOT an integer), so you run into problems pretty quickly. GF(2^8) has a definition for 1/2, because all addition/subtraction/multiplication/division/logarithms/exponents/square-roots/etc.etc. have a precise solution.

Re: Understanding how AES encryption works

#27

Post by SAI_Peregrinus »

tptacek wrote: 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.

Exactly. This article is titled "Understanding how AES encryption works", but it doesn't describe how AES encryption works! It only describes how AES works.

AES is a block cipher, basically an approximation of a "Pseudorandom Permutation" (PRP).[1]

A PRP can be used for secure (authenticated) encryption, eg in AES-CCM or AES-GCM. PRPs can be used for semi-secure (unauthenticated) encryption, eg AES-CTR or AES-CBC. PRPs can be used to make a Message Authentication Code, eg CMAC. PRPs can be used to make a hash function (no direct example with AES, but Whirlpool uses a modified AES, and one could also use it in a Sponge construction, and Keccak uses an internal PRP). PRPs can be used to make a CSPRNG (random number generator), eg AES-DRBG. PRPs can even be used to make a public-key signature scheme: make a hash function (say, via a Sponge construction) and then make a Merkle hash-based signature scheme! The only common operation I don't know how to make with AES (or another PRP) as the main component is a Key Encapsulation Mechanism.

Calling this an article on how "AES Encryption" works is a bit like writing an article "How Programming in C works" and then describing NAND gates, ALUs, instruction decoding, and other bits of how a CPU works. It's the wrong level entirely given the title.

[1] A PRP is a sort of keyed super-shuffle. I'll use decks of cards for this analogy. A PRP is a bit like shuffling 52 decks of cards (in a deterministic way based on the state of an input deck) and taking the top card from each, then returning the resulting 52 cards as a "deck" of output. There can be repeated cards. A deck of all one card (say, ace of spades) will come out totally different, while a normal shuffle would just get you back 52 ace of spades. The determinism lets you repeat this process by knowing the input deck's state.

Re: Understanding how AES encryption works

#28

Post by jjice »

opheliate wrote: post #25

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…

We used Christof Paar's book in my crypto class this past semester. The book was great (much better than my professor) and the explanations of how number theory makes up the majority of the math our modern encryption uses were great. I had never heard of a Galois field until that course, and his text book did a great job explaining what they are and why it makes AES possible.

In general, encryption algorithms are so neat. We take some obscure (at least to me) math topics and we can use them in ways to create these incredible algorithms.

Right now, the most exciting thing in the world of crypto for me is the NIST competition for a post-quantum crypto algorithm. I'm very excited to see what comes out on top.

Re: Understanding how AES encryption works

#29

Post by some_furry »

tptacek wrote: 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.

If anyone is interested in this topic, here's a comparison between the different modes/constructions of AES and other popular ciphers: https://soatok.blog/2020/07/12/comparison-of-symmetric-encry...

Re: Understanding how AES encryption works

#30

Post by SAI_Peregrinus »

cryptXTS wrote: post #21
maqp wrote: post #10

Earlier quoted context omitted.

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

cryptsetup -c serpent-xts-plain64 -s 512 -h sha512 -i 123456 luksFormat /dev/ice /path/to/8M/dev/urandom/keyfile (serpent wasn't chosen by NSA because it's the best, if you want inferior AES, then change serpent to AES.)

I disagree that serpent is superior to AES. The evidence that it's secure is much flimsier than that for AES. It's seen far less analysis, and suffers from many of the same implementation issues as AES (hard to make both constant time and fast without hardware support, and has no hardware support). I'd have agreed with you 10 years ago, but there have been a lot more (failed) attack attempts on AES in the intervening decade than there have been on Serpent, which increase my confidence in AES.
Post reply on HN