Saturday, January 28, 2017

Implementing AES

I've been working for the last 10 days or so on cryptography.  Some time ago I came across the cryptopals website, but I quit after 10 challenges or so.  I stopped about the time that they asked me to implement AES (wikipedia).

In the last week or so I've written Python code to do both DES and AES.  I'm not going to post any of it here, though the repo is here if you're interested.  Also posted there are a number of write-ups about various aspects of the project.  It's still very much a work in progress.

What I really do think will be useful for anyone interested in this topic are links to some resources I found on the web.

Prof. Kak has lectures (here).  Lecture 8 describes implementation of AES and the ones before that describe the peculiar math of Galois fields that is central to AES.

When I was getting started with this problem I found the tables showing multiplication in the field by 2,3,9,11,13,and 14 at wikipedia here.  These copy and paste nicely.  Eventually I learned enough to be able to generate them myself from first principles.

I still cannot say exactly why multiplying a word (4 bytes) by this matrix

[[2, 3, 1, 1],
 [1, 2, 3, 1],
 [1, 1, 2, 3],
 [3, 1, 1, 2]]

can be inverted by multiplying by this matrix:

[[14, 11, 13,  9],
 [ 9, 14, 11, 13],
 [13,  9, 14, 11],
 [11, 13,  9, 14]]

but I am starting to understand how irreducible polynomials work.

A source for the S-boxes that is well-behaved for copying is the official U.S. document here, which also describes the algorithm in complete detail.

Another especially useful reference is a detailed description of what data to expect as AES runs.   They provide intermediate snapshots of the state for every step, including generation of the round keys.  That was a huge help in debugging my code.

My results match theirs, and the end result is provably correct:

> openssl aes-128-ecb -e -nopad -K "5468617473206d79204b756e67204675" -in msg.txt | xxd -p
29c3505f571420f6402299b31a02d73a
>

A last great resource is a discussion here about the process of multiplication.  I found the discussion of the field generator 0x03 tremendously enlightening.  The page includes a table of exponentials and logarithms with 0x03 as the base.  That table alone would allow you to do any multiplication you need, including finding multiplicative inverses, for which another table is provided as well.

I haven't really looked at the whole book yet, but it also promises to be great.