AES ShiftRow Confusion

Question

I'm implementing AES and I'm getting confused in the ShiftRows step. So far, my key expansion and SubBytes works and I get the same output as specified by the NIST publication.

For the ShiftRows Steps, if we refer to the test vector below from NIST, the output is incorrect according to this:

Round 1, from NIST page 35:

--------------------------------------------------------------
state:      63cab7040953d051cd60e0e7ba70e18c <-- SubBytes() 
state:      6353e08c0960e104cd70b751bacad0e7 <-- ShiftRows()
--------------------------------------------------------------

If we consider the matrix below:

$$\begin{pmatrix} S_{00} & S_{01} & S_{02} & S_{03} \\ S_{10} & S_{11} & S_{12} & S_{13} \\ S_{20} & S_{21} & S_{22} & S_{23} \\ S_{30} & S_{31} & S_{32} & S_{33} \\ \end{pmatrix}$$

$$\begin{pmatrix} \texttt{63} & \texttt{ca} & \texttt{b7} & \texttt{04} \\ \texttt{09} & \texttt{53} & \texttt{d0} & \texttt{51} \\ \texttt{cd} & \texttt{60} & \texttt{e0} & \texttt{e7} \\ \texttt{ba} & \texttt{70} & \texttt{e1} & \texttt{8c} \\ \end{pmatrix}$$

Then the output is clearly different.

$$\begin{pmatrix} \texttt{63} & \texttt{ca} & \texttt{b7} & \texttt{04} \\ \texttt{53} & \texttt{d0} & \texttt{51} & \texttt{09} \\ \texttt{e0} & \texttt{e7} & \texttt{cd} & \texttt{60} \\ \texttt{8c} & \texttt{ba} & \texttt{70} & \texttt{e1} \\ \end{pmatrix}$$

Answer 1

The state must be written/read along the columns:

63cab7040953d051cd60e0e7ba70e18c $\mapsto$ $ \begin{bmatrix} 63 & 09 & cd & ba \\ ca & 53 & 60 & 70 \\ b7 & d0 & e0 & e1 \\ 04 & 51 & e7 & 8c \end{bmatrix} $

shift rows $\mapsto$ $ \begin{bmatrix} 63 & 09 & cd & ba \\ 53 & 60 & 70 & ca \\ e0 & e1 & b7 & d0 \\ 8c & 04 & 51 & e7 \end{bmatrix} $ $\mapsto$ 6353e08c0960e104cd70b751bacad0e7

See Figure 3 in FIPS SP 197, 3.4 (http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf).