tags: cryptography
Even though we see that the key size is at least the double of DES, the AES is exponentially more secure than DES. The number of rounds depends on the key size as we can see from the slide. AES-256 is considered military grade encryption.
The main difference between Rijndael and AES that Rijndael allowed multiple block sizes, AES only allows 16 byte blocks but can use different key sized.
A question that I currently have is that how does the add round work if the key is not the same size as the block.
The structure of data
is the most significant byte, AES is much more byte focused not bit focused. If it is not clear, this is column-major representation. The TA said that this representation is Big-endian (i.e. the most significant byte gets the lower address or place) but current CPUs are little-endians
Shift rows in AES is reversible, SubBytes is also reversible. Every operation in AES is reversible
S-Box in AES has a mathematical model, it is not fixed like in DES
These are the transformations that happen in the first N-1 rounds. There is also an initial transformation that happens before rounds transformations, it can be considered round 0.
Only the Add Round Key transformation uses the key, that’s why a cipher round starts and ends with an add round key transformation. Any other transformation, applied at the beginning or end is reversible without the knowledge of the key and this would add no security. The other three stages together provide confusion, diffusion, and non-linearity, but by themselves would provide no security because they do not use the key.
Transformation is also a synonym to stage.
Check ^4749c3 for the definition of confusion and diffusion
AES Parameters for a 4 word size key
Changing the key size would change the number of round
AES Structure
In the S-Box, every byte in substituted by a byte in a 16 x 16 matrix, the leftmost 4 bits of the original bytes represent the row and the rightmost 4 bits represents the column of where to index in the matrix.
The absence of the MixColumns operation the last stage allows the creation of the equivalent inverse cipher, the same algorithm with the same steps but with the inverse operation for decryption.
S-box construction
Create a 16x16 matrix and fill it as follows, row 0 = 00 → 0F, row 1 = 10 → 1F and so on, then replace every byte by its multiplicative inverse in . Lastly apply the following for each byte:
Calculation of the inverse S-Box, Proof of invertability is in the book at page: 160
AES Operations
Shift Rows
The ShiftRows operation moves every byte in a column a distance multiple of 4 bytes in the State, it also ensures that the bytes of a column are all distributed to different columns.
Mix Columns
It is a matrix multiplication that happens in and it is defined by the following matrix multiplication
The mix column operation with the shift rows ensures after few round that all output bits depend on all input bits. This probably achieve diffusion.
Key Expansion
The original key which is 16-bytes is copied to 4 words, each 4-byte column of the key is transformed to be a word, then a key-expansion algorithm is applied to get more words. The code of the algorithm that is applied is below
All the operations that happen in
The round constant is actually a left shift of the round before this one.
Implementation Details
Equivalent inverse cipher
Due to the structure of AES, to do exact 1 to 1 decryption with the same sequence of steps we can’t use the exact equivalent of the AES round block, this leads to non efficient hardware and software implementation.
We can see from the picture that the stage before the add round key is shift rows so to do exact inverse we have to do inverse shift, but the AES starts with SubBytes. Well, it tends out that we can switch the positions between substitution and shifting since the S-Box only works on individual bytes and the column doesn’t really matter here.
The only problem is when we switch the positions between MixColumns and Add round key, when the MixColumns comes before add key in the decryption process the operation happens on the data XORed with the key, but it tends out that the operation has a linear nature, i.e it the same as MixColumns applied on the key xor MixColumns applied on the data. After that in the add key operation instead of XORing with the key only, xor with the MixColumns applied on the key.
Implementation on 8-bit processors
The matrix multiplication that happens in the MixColumns stage, can be defined as:
We used the identity to get these equations. The multiplication by 2 is a shift left operation and maybe an xor(^641207), this can cause time differences in some operations, and this information is valuable for crypt-analysts.
Since this is an 8-bit processor, single bytes look-ups are cheap and fast, we can sacrifice some storage and make a 256 table that represents the operation of multiplication by 2. The complete proof is in slide 49.
32-bit processor implementation
The same idea as in 8-bit processors, reducing the heavy operations to table look-ups is a lot cheaper, we just sacrifice the memory. (Proof is in the reference, page: 177)
The operations are reduces to 4-table look-ups and 4 Kbytes to store the table.