Computer Security: AES Encryption

Course Overview

• The lecture covers computer and networks security, focusing on the Advanced Encryption Standard (AES).
• Grading is based on final exam (40%), midterm (20%), assignments (35%), and attendance (5%).
• This lecture is based on Professor Kak’s Lectures 2, 3, and 8

Vocabulary

• Plaintext is the data to be encrypted.
• Ciphertext is the encrypted result.
• Enciphering/Encryption turns plaintext into ciphertext.
• Encryption Algorithm is the procedure for transforming plaintext into ciphertext.
• Secret Key is a parameter used by the encryption algorithm.
• Deciphering/Decryption recovers plaintext from ciphertext.
• Decryption Algorithm transforms ciphertext back into plaintext.
• Cryptography encompasses various encryption and decryption methods.
• Cryptographic System (Cipher) refers to a specific encryption/decryption scheme.
• Block Cipher processes data in fixed-size blocks.
• Stream Cipher encrypts data byte by byte, on the fly.
• Cryptanalysis is the process of "breaking the code".

Ciphers and Cryptanalysis

• Encryption and decryption algorithms are generally made public.
• Classical cryptography uses the same secret key for encryption and decryption, known as symmetric key cryptography.
• More recent algorithms use different keys for encryption and decryption, with one key made public, known as asymmetric key cryptography or public key cryptography.
• Cryptanalysis relies on knowledge of the encryption algorithm and plaintext structure.
• The goals of cryptanalysis include reconstructing plaintext from ciphertext and inferring the key for future message decryption.
• Key Space refers to the total possible keys in a cryptographic system.

Cryptanalysis Attacks

• Brute-force attack involves trying every possible key until intelligible plaintext is obtained.
• Codebook attack aims to acquire mappings between plaintext and ciphertext symbols.
• Algebraic attack expresses the plaintext-to-ciphertext relationship as equations to solve for the encryption key.

Security Tradeoffs

• Brute-force attacks require minimal memory but can be time-intensive.
• Codebook attacks can be fast but require large memory resources.
• Cryptography and cryptanalysis are combined to form the field of cryptology.

Classical Encryption Techniques

• Classical encryption relies on substitution and transposition.
• Substitution replaces plaintext elements with ciphertext elements.
• Transposition/Permutation rearranges the order of plaintext elements.
• Modern algorithms combine multiple rounds of transposition and substitution.

Caesar Cipher

• The Caesar Cipher represents each letter with an integer based on its position.
• Each character is replaced by the character three positions down the alphabet.
• A more general form uses a secret key, k to shift characters:
  • Encryption: c = E(k, p) = (p + k) mod 26
  • Decryption: p = D(k, c) = (c – k) mod 26
• The Caesar cipher shifts each letter of the plaintext by a fixed number of positions.

Monoalphabetic Cipher

• Monoalphabetic ciphers use the same substitution rule for each letter throughout the message.
• These ciphers can use a random permutation for each letter of the alphabet
• Monoalphabetic ciphers provide a large keyspace of 26! permutations, making brute force attacks difficult.
• A nanosecond attempt per key would still take eons to crack even half the keyspace.

Statistical Attack

• Statistical analysis of English plaintext measures frequency distribution for single, double (digrams), and triple (trigrams) letter combinations.
• Frequency distributions are then compared to statistics for English.

Playfair Cipher

• A Playfair cipher encryption key is chosen ensuring there are no repeating characters.
• Key characters are entered in a 5x5 matrix from left to right and top to bottom, starting at the top-left corner.
• The rest of the matrix cells are filled with remaining alphabet letters, where 'I' and 'J' share a cell.
• A filler letter, such as 'x', should be inserted between repeating letters in the plaintext.
• Pairs of consecutive characters in the plaintext are then scanned.
• For letters in the same row in the matrix, each letter is replaced by the one to its right (circularly).
• If the two letters fall in the same column, replace each with the letter below it (circularly).
• Otherwise, for each plaintext letter in a pair, it is replaced with the letter that is in the same row but in the column of the other letter.
• Playfair was used by the British Army in World War 1 and by the US Army and its allies during the second World War.
• The Playfair cipher modifies individual letter frequencies as well as with digrams and trigrams though it does not modify them sufficiently.

Hill Cipher

• Each letter of the alphabet is assigned an integer.
• The encryption key is a 3x3 matrix, K, of integers.
• The Hill Cipher transforms three plaintext letters at a time where the letters are represented by p1, p2 ,and p3, into the ciphertext letters c1, c2, and c3.
• It is extremely secure against ciphertext only attacks, However has zero security when plaintext-ciphertext pairs are known.

Vigenere Cipher

• A monoalphabetic cipher uses the same substitution rule at each character’s position in the plaintext message.
• A polyalphabetic cipher changes the substitution rule continuously.
• The “align” the encryption key with the message first aligning them.
• If the message is larger than the encryption key, repeat the encryption key.
• Each letter of the encryption key denotes the Caesar cipher and the shift correlates to the encryption’s key letter.
• A polyalphabetic cipher, the Enigma Machine, was used by the German military in The Second World War.
• A longer encryption key will provide more masking of the structure of the plaintext.
• The most ideal key would match the message, consisting of 26 letters/permutations.
• If the estimated key length is N, then the cipher contains N substitution ciphers.

Transposition Techniques

• Plaintext is written along the rows of a matrix.
• Ciphertext is read along the columns.
• An encryption key determines the order in which to read the columns.

Ideal Block Cipher

• The ideal block cipher replaces the plaintext’s N block bits with an N bit block from the ciphertext.
• The relationship between blocks is completely random in the ideal block cipher.
• Ideal block ciphers need to be invertible for it to work.
• The encryption key is the codebook which is a table containing all the block relationships.
• An impracticality with ideal block ciphers is the key size (64 x 2^64 ≈ 10^21).

Feistel Structure

• Feistel structure was named after Horst Feistel, from IBM Cryptography.
• The algorithm used is the same for decryption and encryption.
• The Data Encryption Standard, DES, algorithm is based on this structure.
• The multiple rounds of the Feistel Structure have a substitution step and a permutation step involved in its processing.
• The input block is divided in half (L and R) per round, where R is unchanged.
• L needs to run an operation using the encryption key and R (Feistel Function).
• The modified L and unmodified R need to swap by the end of each round in a permutation step.
• The main encryption key derives the round key, Ki.
• Let LEi and REi denote the output half-blocks at the end of the ith round of processing.
• The symbol F denotes the operation that "scrambles" REi-1 of the previous round with the round key Ki.
• The round keys are used in reverse order with the decryption algorithm having the same steps as encrypting.

DES (Data Encryption Standard)

• DES was made standard in 1977 by NIST.
• The structure DES uses is the Feistel Cipher.
• 64 bits is the block size in DES using its 56 bits encryption key.
• New data was needed to follow NIST’s development due to DES being not as strong.
• AES (Advanced Encryption Standard) was the result.

Why DES Is Strong

• The substitution step's goal is to introduce a diffusion in the produced output with the given input.
• Any plaintext change should spread the changes across many ciphertext changes (diffusion).
• An encryption process with confusion is meant to use the strategy used to make the keys from the main key.
• The confusion is that the output ciphertext should have many bits affected with each key’s bits.
• The avalanche effect is used to refer to both of the effects.
• With its key being 56 bit, DES's key space size is 2 to the power of 56, or about 7.2 *10 to the power of 16.
• It would take roughly 13 months for a machine processing 1000 keys/microsecond to break the code (half the keys) with brute-force.
• Processing 1 million keys at once with a parallel processing machine would reduce 13 months to about 10 hours.

AES Features

• AES uses blocks with a 128 bits length
• Key lengths will be assumed to be 128 bits, but AES allows 128, 192, or 256 bits key lengths.
• Ten processings are used for encryption with a 128 bits key length
• Single byte that has been substituted
• Row, column mixing, and permutation of the round key are all processing steps.
• After each round, state occurs with input where the output state is derived with each keys.
• In AES, both decryption and encryption algorithms are substantially different.
• In AES, substitution-permutation usage is more general than Feistel network usage.
• AES are uses the bit-level operation, while DES uses the byte-level operation.

AES Round Keys

• 4 bytes is the equivalent of one word (32 bits).
• an array of 4x4 is also the format the key is arranged into. In that array/format, the first word fills the first column.
• The key array's four column words expand into a schedule of 44 words.
• Out of that schedule, each round uses four words.
• The first four are use to add to the state before any step and there's also 40 words remaining for 10 other rounds.

AES Overall Structure

• Before the start of round processing with encryption, an XOR would occur the schedule’s first four words in state's input array.
• However with decryption it's the schedule's last four words in cipher’s text state array with the same occurrence.
• After step 4 (Add Round Key) or the round key being added, substitution from 1), shift rows from 2), and the Mix Columns's 3). The mentioned, but it’s the substitutions (inverse shift rows from 1)) from which decryption's rounds inverse.
• There is no steps where we mix columns for the last round with encryption and no step where the mixes column inversely for encryption

AES Round Processing Steps

• STEP 1 SubBytes: Look up in the input state array where a one byte has been subbed in a 16*16
• Using multiplicative inverses and the GF destruction, use bit scrambling to avoid any correlations at the bit level in the bytes to form table entries.
• For decryption’s inverse the InvSubBytes is used to call itself.
• STEP 2 Shiftrows: Mix up that byte order by moving them during the process.
  • Use InvShiftRows during decryption for corresponding transitions
• STEP 3 MixColumns: Every column mixing to help arrange bytes during its forward process to help process the bits in a scrambled input block.
  • The inverse of the MuxColums for decryption (InvMixColumns is denoted)
  • MixColumns helps shift rows to change bits (one bit) for the average of 128 bit of cipher when it does avalanche (bit spans).
  • MixColumns has less than half bits changed compared to DES so to the statement above.
• STEP 4 AddRoundKey: Addition of keys is to make process to work well.
  • (InvAddRoundKey) = inverse addition of key transformation/rotation
  • Find input in 4-pattern where integers range from a hex values to 0 to 1
  • Hex values are now row indexes since these are also in those table by lookup in x * x tables.
  • When that hex value is not as 0, each cells would replace inverse.
  • All cells where replaced where 0 is the only value where all element is the same to not have inverses.

SubBytes and InvSubBytes

• SubBytes and InvSubBytes work by finding a replacement byte by dividing the input byte into two 4-bit patterns resulting in an integer value of 0–15 (0–F).
• One hex value serves as a column index and the other as the row index to locate the byte in the 16 x 16 lookup table.
• Each value is then replaced by its relative multiplicative inverse in GF(28 based the irreducible polynomial x8+x4+x3+x+1. The hex value 0x00 has no multiplicative Inverse and is thus replaced by itself.

SubBytes LookUp Table

• Let b7b6b5b4b3b2b1b0 be the byte stored in a cell of he table.
• For instance, (9,5) cell is stored with one of the most tables named inverses of 0x95, (0x8A (10001010 in value)).
• You must then apply all the scrambling in every bits each key.
• Where c is (62 (01100011 is its value where 0x63)) specially.
• By the end without C, there bits would avoid having the hex be 0x00.

InvSubByets Lookup Table

• The table needs the reversed steps to make lookup process be decrypted if needs it.
• Bit would transfer in code if needed a level of key where decryption need key in bits with value as 0x00 (00000101).

ShiftRows

• Used to shift any rows in code in a forward pattern/sequence in order to make byte codes get scrambled by end

InvShiftRows

• Invshiftrows

MixColumns

• Implied multiplication and additions are carried out in GF(28) arithmetic.

InvMixColumns

• The InvMixColumns does not work in arithmetic

Key Expansion

• If any one of the encryption bit changes, the algorithms would not have any problems making it still be secure to not let any key bits let happen in circle.
• We only need to have 16 key bytes that's make 4*4 array.