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.

  • $\begingroup$ 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 $\endgroup$ Dec 11 '13 at 8:27
  • $\begingroup$ can you elaborate "function value" ? $\endgroup$
    – johnny
    Dec 11 '13 at 8:29
  • 1
    $\begingroup$ @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. $\endgroup$ Dec 11 '13 at 8:34
  • $\begingroup$ 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 $\endgroup$ 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.
  • 2
    $\begingroup$ Rather than start a discussion in the comments I thought I'd post a follow up question: crypto.stackexchange.com/questions/12268/… $\endgroup$
    – user9070
    Dec 11 '13 at 18:14
  • $\begingroup$ 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. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.