# AES column mixing and S-Box confusion

I am trying to understand the AES encryption algorithm. I know that we process 128 bits at a time for a 128 bit key in a 4x4 octet form, but am confused by the following:

1. How does the substitution subround work, as the size of the Rijndael's S-box is 16x16 Octets and size of the input is 4x4?
2. How does the mixed column operation work on the 4-octet column?
-

You should think of Rijndael's S-box as a function that maps bytes to bytes, where a byte (octet) is considered to be a member of a finite field of size $2^8$ (with xor as addition). It's not seen as a 16x16 octet array, really.

The substitution is then just done byte-wise: every octet in the 4x4 block is replaced by its function value under the S-box table.

The mix column is just a matrix multiplication of the column with a 4x4 matrix, all in the field of size $2^8$. See the wikipedia entry for a worked example.

-
I don't think the first sentence is as helpful as the rest of your answer - it doesn't matter what field you think of the bytes as being members of for running the S-box. The other two sentances answer the question –  figlesquidge Dec 11 '13 at 8:27
can you elaborate "function value" ? –  johnny Dec 11 '13 at 8:29
@figlesquidge Well, the S-box is defined in terms of the field operation ($\frac{1}{ax+b}$, for some $a,b$, defining $\frac{1}{0}$ as $0$...) But I mentioned it because I need it for the mix column anyway. –  Henno Brandsma Dec 11 '13 at 8:34
Fair enough, and I realise the definition of the S_box requires such methods, I just meant that as far as an s-box implementation goes you 'just' think of the value as an unsigned integer –  figlesquidge Dec 11 '13 at 8:36

standard AES disclaimer: Given the questions you've asked, you should not implement AES yourself in a real-world system because there are lots of security considerations when implementing ciphers.

1. Think of the S-box as a function from byte $\to$ byte. So, to look up the image of $x$ under the s-box transformation, you simply use $S_\text{box}(x)$, which is nice and easy to implement since you can literally use array lookups. [note: easy implementations will almost certainly leak to sidechannels].
2. The mix columns is matrix multiplication of the column in question with a specific matrix, over the finite field $\mathbb{F}_{2^8}$, with field polynomial $x^8+x^4+x^3+x+1$. What this means in practice is you do 'standard' matrix multiplication, but using $\oplus$ instead of traditional addition (because all coefficients are modulo $2$), and each time the multiplication leads to a term in $x^8$ or higher, use the rule $x^8=x^4+x^3+x+1$ to reduce it modulo the field polynomial. You may well find this example useful for your implementation.
-
Rather than start a discussion in the comments I thought I'd post a follow up question: crypto.stackexchange.com/questions/12268/… –  TruthSerum Dec 11 '13 at 18:14
Good question there. Just for closure's sense: my comment referred more to the dangers of letting bugs slip in or that a naive implementation will almost certainly have sidechannel weaknesses. However, your question (which basically asks 'How do I know someone's crypto implementation isn't malicious?') is much more interesting imo. –  figlesquidge Dec 11 '13 at 20:11

Item 2 has been answered satisfactorily, so this will focus on point 1: the s-box.

The size of the s-box is not a 16x16 array unless it is viewed as such. The s-box is actually an 8-bit non linear transformation of the input, and is only viewed as a 16x16 array if you arrange it as a table of such dimensions. This array would then be a 1 to 1 representation of all 8-bit inputs and outputs of the transformation, with the axes being the 4-bit halves of the input. It can just as easily be viewed as a 1x256 array.

Not all AES implementations use a table lookup for the s-box, some actually perform the calculation from scratch in hardware for security purposes, and it can be pipelined 16-wide for performance. Memory constrained 8-bit platforms also may perform the entire calculation (slowly), since storing a 256 byte table in memory is too expensive.

See How are the AES S-Boxes calculated? for details of the transformation.

The 4x4 array of input bytes is transformed 1 byte at a time to give the 4x4 output array. The s-box is also used to transform single bytes during key scheduling.

-