Cryptography: AES - S-Box

How is the S-box constructed? 
 

         1. Initialize the S-box with the byte values in ascending sequence row by row. The first row contains {00}, {01}, {02}, etc., the second row contains {10}, {11}, etc., and so on. Thus, the value of the byte at row x, column y is {xy}.

         2.   Map each byte in the S-box to its multiplicative inverse in the finite field GF(28); the value {00} is mapped to itself.

         3.   Consider that each byte in the S-box consists of 8 bits labeled (b7, b6, b5, b4, b3, b2, b1, b0). Apply the following transformation to each bit of each byte in the S-box:

                                                    

where ci is the ith bit of byte c with the value {63}; that is, (c7c6c5c4c3c2c1c0) = (01100011). The prime (') indicates that the variable is to be updated by the value on the right.

Cryptography: Advanced Encryption Standard - Facts

1. What was the original set of criteria used by NIST to evaluate candidate AES ciphers?

• Security: Actual security; randomness; soundness, other security factors.
• Cost: Licensing requirements; computational efficiency; memory requirements.
• Algorithm and Implementation Characteristics: Flexibility; hardware and software suitability; simplicity.

1. What was the final set of criteria used by NIST to evaluate candidate AES ciphers?

General security; software implementations; restricted-space environments; hardware implementations; attacks on implementations; encryption vs. decryption; key agility; other versatility and flexibility; potential for instruction-level parallelism. 

1. What is the difference between Rijndael and AES 

The basic idea behind power analysis is the observation that the power consumed by a smart card at any particular time during the cryptographic operation is related to the instruction being executed and to the data being processed.

Cryptography: THE FOUR STEPS IN EACH ROUND OF AES PROCESSING

STEP 1: (called SubBytes for byte-by-byte substitution during the forward process) (The corresponding substitution step used during decryption is called InvSubBytes.)

    This step consists of using a 16 × 16 lookup table to find a replacement byte for a given byte in the input state array.

    The entries in the lookup table are created by using the notions of multiplicative inverses in GF(2^8) and bit scrambling to destroy the bit-level correlations inside each byte.

STEP 2: (called ShiftRows for shifting the rows of the state array during the forward process) (The corresponding transformation during decryption is denoted InvShiftRows for Inverse Shift- Row Transformation.)

The goal of this transformation is to scramble the byte order inside each 128-bit block.

STEP 3: (called MixColumns for mixing up of the bytes in each column separately during the forward process) (The corresponding transformation during decryption is denoted InvMixColumns and stands for inverse mix column transformation.) The goal is here is to further scramble up the 128-bit input block.

The shift-rows step along with the mix-column step causes each bit of the ciphertext to depend on every bit of the plain- text after 10 rounds of processing.

NOTE: The avalanche effect from our discussion on DES in Lecture 3. In DES, one bit of plaintext affected roughly 31 bits of ciphertext. But now we want each bit of the plaintext to affect every bit position of the ciphertext block of 128 bits. [The sentence does NOT say that if you change one bit of the plaintext, the algorithm is guaranteed to change every bit of the ciphertext. (Changing every bit of the ciphertext would amount to reversing every bit of the block.) Since a bit can take on only two values, on the average there will be many bits of the ciphertext that will be identical to the plaintext bits in the same positions after you have changed one bit of the plaintext. However, again on the average, when you change one bit of the plaintext, you will see its effect spanning all of the 128 bits of the ciphertext block. On the other hand, with DES, changing one bit of the plaintext affects only 31 bit positions on the average.]

STEP 4: (called AddRoundKey for adding the round key to the output of the previous step during the forward process) (The corresponding step during decryption is denoted InvAddRound-Key for inverse add round key transformation.) 

     

Cryptography: THE OVERALL STRUCTURE OF AES

• The number of rounds shown in Figure, 10, is for the case when the encryption key is 128 bit long. (the number of rounds is 12 when the key is 192 bits, and 14 when the key is 256.)
• Before any round-based processing for encryption can begin, the input state array is XORed with the first four words of the key schedule. The same thing happens during decryption — except that now we XOR the ciphertext state array with the last four words of the key schedule.
• For encryption, each round consists of the following four steps: 1) Substitute bytes, 2) Shift rows, 3) Mix columns, and 4) Add round key. The last step consists of XORing the output of the previous three steps with four words from the key schedule.
• For decryption, each round consists of the following four steps: 

1) Inverse shift rows,
2) Inverse substitute bytes,
3) Add round key, and
4) Inverse mix columns.
The third step consists of XORing the output of the previous two steps with four words from the key schedule. Note the differences between the order in which substitution and shifting operations are carried out in a decryption round vis-a-vis the order in which similar operations are carried out in an encryption round.

• The last round for encryption does not involve the “Mix columns” step. The last round for decryption does not involve the “Inverse mix columns” step.

Cryptography: AES - THE ENCRYPTION KEY AND ITS EXPANSION

• Assuming a 128-bit key, the key is also arranged in the form of a matrix of 4 × 4 bytes. As with the input block, the first word from the key fills the first column of the matrix, and so on.
• The four column words of the key matrix are expanded into a schedule of 44 words.Each round consumes four words from the key schedule.
• Figure 1 on the next page depicts the arrangement of the encryption key in the form of 4-byte words and the expansion of the key into a key schedule consisting of 44 4-byte words.

Cryptography: SALIENT FEATURES OF AES

AES is a block cipher with a block length of 128 bits.

• AES allows for three different key lengths: 128, 192, or 256 bits. Most of our discussion will assume that the key length is 128 bits. [With regard to using a key length other than 128 bits, the main thing that changes in AES is how you generate the key schedule from the key — an issue I address at the end of Section 8.8.1. The notion of key schedule in AES is explained in Sections 8.2 and 8.8.]
• Encryption consists of 10 rounds of processing for 128-bit keys, 12 rounds for 192-bit keys, and 14 rounds for 256-bit keys.
• Except for the last round in each case, all other rounds are iden- tical.
• Each round of processing includes one single-byte based substi- tution step, a row-wise permutation step, a column-wise mixing
• step, and the addition of the round key. The order in which these four steps are executed is different for encryption and decryption.
• To appreciate the processing steps used in a single round, it is best to think of a 128-bit block as consisting of a 4 × 4 matrix of bytes, arranged as follows:

byte0    byte4    byte8      byte12
byte1    byte5    byte9      byte13
byte2    byte6    byte10    byte14
byte3    byte7    byte11    byte15

• Therefore, the first four bytes of a 128-bit input block occupy the first column in the 4 × 4 matrix of bytes. The next four bytes occupy the second column, and so on.
  The 4×4 matrix of bytes shown above is referred to as the state array in AES.

• AES also has the notion of a word. A word consists of four bytes, that is 32 bits. Therefore, each column of the state array is a word, as is each row.
  Each round of processing works on the input state array and produces an output state array.
  The output state array produced by the last round is rearranged into a 128-bit output block.
• Unlike DES, the decryption algorithm differs substantially from the encryption algorithm. Although, overall, the same steps are used in encryption and decryption, the order in which the steps are carried out is different, as mentioned previously.
  AES, notified by NIST as a standard in 2001, is a slight variation of the Rijndael cipher invented by two Belgian cryptographers Joan Daemen and Vincent Rijmen.

• Whereas AES requires the block size to be 128 bits, the original Rijndael cipher works with any block size (and any key size) that is a multiple of 32 as long as it exceeds 128. The state array for the different block sizes still has only four rows in the Rijndael cipher. However, the number of columns depends on size of the block. For example, when the block size is 192, the Rijndael cipher requires a state array to consist of 4 rows and 6 columns.
• AES uses is a substitution- permutation network in a more general sense. Each round of processing in AES involves byte-level substitutions followed by word-level permutations. Speaking generally, DES also involves substitutions and permutations, except that the permutations are based on the Feistel notion of dividing the input block into two halves, processing each half separately, and then swapping the two halves.
• The nature of substitutions and permutations in AES allows for a fast software implementation of the algorithm.
• The AES standard is described in the following official document: 
• http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf