Encryption Techniques

Course Information

• The teams code is 9w1s1bq
• Refer to the posts for reference material
• Grading breakdown: Final (40%), Midterm (20%), Attendance (5%), and Assignments (35%)
• This lecture references Professor Kak's Lectures 2, 3, and 8

Lecture Outline

• Vocabulary related to encryption
• Building blocks for classical encryption techniques
• Early encryption approaches
• Ideal Block Cipher and Feistel Structure components
• The Advanced Encryption Standard (AES

Vocabulary

• Plaintext represents the data that needs to be encrypted
• Ciphertext represents the encrypted data
• Enciphering/Encryption is the process of converting plaintext into ciphertext
• An encryption algorithm is the sequence of data processing steps used to transform plaintext into ciphertext
• A secret key is a parameter used by the encryption algorithm
• Deciphering/Decryption is recovering plaintext from ciphertext
• A decryption algorithm is the data processing steps that transform ciphertext back into plaintext
• Cryptography encompasses many schemes for encryption and decryption
• Cryptographic System (Cipher) represents a single scheme for encryption and decryption
• Block Cipher processes input data in blocks, producing ciphertext blocks of the same size
• Stream Cipher encrypts data on the fly, processing one byte at a time
• Cryptanalysis is the process of "breaking the code"

Ciphers

• Encryption and decryption algorithms are made public
• Keeping algorithms secret can have negative consequences
• Classical cryptography uses the same secret key for both encryption and decryption, known as symmetric key cryptography
• Modern cryptographic algorithms use different encryption and decryption keys, with one placed in the public domain, known as asymmetric key or public key cryptography

Cryptanalysis Techniques

• Cryptanalysis requires knowledge of the encryption algorithm and the structure of the plaintext
• The goal is reconstruction of the plaintext from ciphertext
• The goal is also to infer the key for future decryption
• Key Space represents the total number of possible keys in a cryptographic system
• A brute-force attack involves trying every possible key on ciphertext until an intelligible translation is obtained
• A codebook attack involves acquiring as many mappings between plaintext and ciphertext symbols
• An algebraic attack involves expressing the plaintext-to-ciphertext relationship as a system of equations and solving for the encryption key

Time-Memory Tradeoff

• Brute-force attacks need very little memory
• Brute-force attacks can require long times to scan through all possible keys
• Codebook attacks can yield results instantaneously
• Codebook attacks can have humongously large memory needs
• Cryptography and cryptanalysis together constitute cryptology

Classical Encryption Techniques

• The two building blocks are substitution and transposition
• Substitution replaces plaintext elements with ciphertext elements
• Transposition/Permutation rearranges the order of plaintext elements
• Modern algorithms use multiple rounds of transposition and substitution

Caesar Cipher

• Represents each alphabet letter with an integer corresponding to its position
• Each character is replaced by the character three positions down the alphabet
• Cipher formula: c = E(3, p) = (p + 3) mod 26
• A more general version is to use a secret key k
• Encryption formula: c = E(k, p) = (p + k) mod 26
• Decryption formula: p = D(k, c) = (c – k) mod 26

Monoalphabetic Cipher

• Uses the same substitution rule for each letter of the plaintext message
• Substitution letters should be a random permutation of the 26 letters in the alphabet
• There are 26! permutations of the alphabet
• Results in an extremely large key space (larger than 4 × 10^26)

Statistical Attack

• When plaintext is plain English, this involves measuring frequency distribution
• Frequency distribution is used for single characters, pairs, and triples of characters
• Distributions are compared with statistics of English
• Digrams are pairs of adjacent characters
• Trigrams are triples of characters

Playfair Cipher

• Select an encryption key without duplicate characters
• Place key characters in a 5x5 matrix, left-to-right and top-to-bottom
• Fill the matrix with remaining characters
• I and J share the same cell
• Chosen filler letter is inserted between repeating letters in the plaintext
• Plaintext is then scanned in pairs of consecutive characters
• If plaintext letters fall in the same row of the 5x5 matrix, they are replaced by letters to the right (circularly)
• If plaintext letters fall in the same column, they are replaced by letters below (circularly)
• Otherwise, each plaintext letter is replaced by the letter in the same row but in the column of the other letter
• The Playfair cipher was used by the British Army in World War 1, and the U.S. Army along with other Allied forces in World War 2
• The cipher alters relative frequencies, but not sufficiently

Hill Cipher

• An integer is assigned to each letter of the alphabet
• Encryption key K consists of a 3 × 3 matrix of integers
• Transforms three plaintext letters at a time, p1, p2, and p3, into three ciphertext letters c1, c2, and c3
• Despite being extremely secure against ciphertext-only attacks, security is compromised plaintext-ciphertext pairs are known

Vigenere Cipher

• A monoalphabetic cipher uses the same substitution rule at every character position
• A polyalphabetic cipher changes the substitution rule continuously from one character position to the next per encryption key.
• The encryption key is first aligned with the plaintext message
• If the plaintext message is longer than the encryption key, repeat the key
• Each letter denotes a shifted Caesar cipher, with the shift corresponding to the letter of the Key
• Key length is relevant because the longer the encryption key the greater the masking of the plaintext structure is
• Best possible key equals plaintext message length
• Best possible key consists of a purely random permutation of the 26 alphabet letters
• In the context of the estimated key length N, the cipher comprises N monoalphabetic substitution ciphers
• Enigma Machine is the best-known example is of a polyalphabetic cipher
• The German military used the Enigma Machine in World War 2

Transposition Techniques

• Message is written along matrix rows of some size
• Ciphertext is generated by reading along the columns
• Column order is influenced by the use of an encryption key

Ideal Block Cipher

• It replaces a block of N bits from the plaintext with one from the ciphertext
• The relationship between the input and output is completely random
• It must be invertible for decryption to work
• Its encryption key is the codebook itself, mapping input blocks to output blocks
• For a 64-bit encryption example, each possible input block is specified as one of 2^64 integers with an output 64-bit block
• A 64 bit system codebook size would be: 64 x 2^64 ≈ 10^21
• Key size makes this impractical

Feistel Structure

• Named after IBM cryptographer Horst Feistel
• Employs the same algorithm for both encryption and decryption
• DES is based on the Feistel Structure
• It consists of multiple processing rounds
• Each round is a substitution step followed by a permutation step

Feistel Structure Encryption

• The input block to each round divides into two halves, L and R
• In each round, R is unchanged
• L undergoes an operation dependent on R and the encryption key (Feistel Function)
• The permutation step swaps the modified L and the unmodified R
• Round key Ki is derived from the main encryption key
• LEi/REi indicates the output half-blocks at the end of the i-th processing round
• F symbolizes the operation that “scrambles” REi-1 with the round key Ki

Feistel Structure Decryption

• The decryption algorithm is identical to the encryption one
• The round keys are used in reverse order

Data Encryption Standard (DES)

• NIST adopted DES in 1977
• DES uses the Feistel Cipher structure with 16 processing rounds
• A 64-bit block size/56-bit encryption key is used
• DES was found not as strong as originally believed prompting further AES development by NIST

Key Aspects of DES

• The goal of the substitution step is to introduce diffusion in the generation of the output from the input
• Diffusion means a change in any plaintext bit propagates out to as many ciphertext bits as possible
• Each key affects many bits to introduce confusion into the encryption process
• Confusion means that every bit of the key affects the ciphertext block
• Both effects are referred to as the avalanche effect

Brute Force Attacks on DES

• A 56-bit key equals a key space of size 2^56 ≈ 7.2 × 10^16
• A machine which processes 1000 keys per microsecond would take 13 months to break the code by trying half the keys
• With parallel processing, one million keys simultaneously can break in 10 hours

Advanced Encryption Standard (AES)

• AES is a block cipher that is 128 bits in block length
• AES uses key lengths of 128, 192, or 256 bits
• Encryption comprises 10 processing rounds for 128-bit keys
• Each processing round uses: one single-byte based substitution step, row-wise permutation step, column-wise mixing step, and the round key addition

AES Key Concepts

• AES uses a 4 × 4 array of bytes known as the "state array"
• AES processing rounds involve an input state array to produce an output state array
• Round Key comes from a user-supplied encryption key
• Decryption algorithm is substantially different from encryption
• AES applies a byte-level substitution-permutation network, unlike DES, which uses a bit-level process
• DES requires bit-level access for substitution, while AES is purely byte-level

Round Keys

• There are four bytes in a word (32 bits)
• Arranged in an array of 4 × 4 bytes where The key fills the first column
• 44 words expansion schedule
• Each round uses four words from the key schedule
• Round-based processing happens when the input state adds the fist four words, with the 40 remaining words used for the ten rounds

AES Structure

• Bypasses the input array, XORed with the first four words of the key schedule for encryption
• In decryption, the ciphertext array is XORed with the last four words of the key schedule
• Encryption involves 1) Substitute bytes, 2) Shift rows, 3) Mix columns, and 4) Add round key in each round
• For decryption each round consists of 1) Inverse shift rows, 2) Inverse substitute bytes, 3) Add round key, and 4) Inverse mix columns
• The last encryption round does not Mix Columns
• The last decryption round’s Inverse Mix Columns step is skipped

AES Processing: Step 1: SubBytes

• Apply byte-by-byte substitution to replace bytes in the input state
• Replacement is determined by using entries in a 16 x 16 lookup table
• It applies multiplicative inverses in GF(2^8) combined with bit scrambling, avoiding correlations inside each byte
• InvSubBytes performs this during decryption

AES Processing: Step 2: ShiftRows

• Rows are subject to shifting during the forward process
• Aim is to scramble the byte order in each 128-bit block
• InvShiftRows performs this during decryption

AES Processing: Step 3: MixColumns

• Bytes in each column are separately mixed
• Mixing furthers scrambling in the 128-bit input block with this forward process
• InvMixColumns performs this during decryption
• Avalanche Effect in MixColumns where if one bit of plaintext shifts with the MixColumns step, it causes effects spanning all 128 bits of ciphertext block
• Changing a single bit with DES affects 31 bit positions, but this does not occur with AES

AES Processing: Step 4: AddRoundKey

• Round Key adds to the output process during the forward process
• InvAddRoundKey for inverse add round key transformation performs this during decryption

SubBytes and InvSubBytes

• To locate a table cell, the substitute byte for a given byte, two 4-bit patterns are formed
• From the two 4-bit patterns, each generates a value between 0 and 15 (0 – F)
• The hex values determine row and column index in the 16 x 16 lookup table
• For each cell, we replace the value using a multiplicative inverse
• Calculation is done in GF(2^8) using irreducible polynomial 𝑥^8 + 𝑥^4 + 𝑥^3 + 𝑥 + 1
• For the multiplicative inverse, 0x00 is replaced by itself

SubBytes Lookup Table

• Byte storage in each table cell to b7b6b5b4b3b2b1b0
• As a notable example, (9,5) equals 0𝑥95 inverse, to 0𝑥8𝐴 or 10001010
• Each bit receives 𝑏𝑖 transformation with 𝑐𝑖, the ith bit of byte 𝑐. a value of 0x63 (expressed as 01100011)
• Without 𝑐, bit scrambling would leave input 0x00 unchanged

InvSubByets Lookup Table

• The tables in the lookup are reversals for decryption purposes
• Bit-level decryption scramble uses 0x05 (expressed as 00000101) for each transformation cell bit, 𝑑𝑖
• Each byte receives an inverse multiplicative cell-by-cell, in GF(2^8)

ShiftRows

• A byte transformation
• ShiftRows process scrambles the byte order

InvShiftRows

• A byte transformation for AES
• InvShift processes scramble the cell order

MixColumns

• Multiplications use "times" operator
• Additions use Plus operator
• Calculations apply to GF(2^8) arithmetic

InvMixColumns

• Inverse Mix Columns equation

Key Expansion

• Algorithm design ensures if there is a change with the encryption keys that several rounds are affected
• The round keys can be reconfigured if needed
• Arrangement of First 16 bits occurs in 4x4 array bytes