[ Security ] Ch03. Symmetric Key Cryptographic Algorithms

Cryptography Algorithm Types and Modes

• Algorithm types and modes are two key aspect of cryptography
  • Mechanisms that decides the process of encryption/decryption
• Algorithm type defines what size of plain text should be encrypted in each step of algorithm
• Algorithm mode defines the details of the cryptographic algorithm, once the type is decided

Algorithm Types

• Stream cipher
  • Bit-by-bit encryption / decryption
  • The plain text is encrypted one bit at a time

• Block cipher
  • Block-by-block encryption / decryption
  • A block of bits is encrypted at one go

Algorithm Modes

• An algorithm modes is a combination of a series of the basic algorithm steps on block cipher, and some kind of feedback from the previous step
  • Add randomness to block cipher
  • Otherwise, block cipher becomes predictable
• Four main modes
  • Electronic Code Book (ECB)
  • Cipher Block Chaining (CBC)
  • Cipher Feedback (CFB)
  • Output Feedback (OFB)
    • Counter (CTR)

---

Components of Symmetric Key Cryptography

• Symmetric Key Cryptography
  • Same key used for encryption and decryption
  • Quite popular and fast
  • Examples: DES, AES, IDEA, Blowfish, RC4/5, ChaCha20

• Symmetric Key Modern Block Ciphers
  • A symmetric-key modern block cipher encrypts an n-bit block of plaintext or decrypts an n-bit block of ciphertext.
  • The encryption or decryption algorithm uses a k-bit key

Components of Modern Block Cipher

• Modern block ciphers are usually made of combination of transposition units (called P-box), substitution units (called S-box), and some other units.
  • Example: Suppose that we have a block cipher where n = 64. If there are 10 1’s in the ciphertext, how many trial-and-error tests does Eve needs to do to recover the plaintext from the intercepted ciphertext in each of the following cases?
    • A. The cipher is designed as a substitution cipher.
      • Eve has no idea how many 1’s are in the plaintext. Eve needs to try all possible 264 64-bit blocks to find one that makes sense.
    • B. The cipher is designed as a transposition cipher.
      • Eve knows that there are exactly 10 1’s in the plaintext. Eve can launch an exhaustive-search attack using only those 64-bit blocks that have exactly 10 1’s.

P-Boxes

• P-Boxes: A P-box (permutation box) parallels the traditional transposition cipher for characters. It transposes bits.

P-Boxes: Straight P-Boxes

• Straight P-box has n! possible mappings

P-Boxes: Compression P-Boxes

• Compression P-box is a P-box with n inputs and m outputs where m < n

P-Boxes: Expansion P-Boxes

• Expansion P-box is a P-box with n inputs and m outputs where m > n

P-Boxes: Invertibility

• Straight P-box is invertible
  • Following figure shows how to invert a permutation table represented as a one-dimensional table.
• Compression and expansion P-boxes are non-invertible
  • In a compression P-box, an input can be dropped during encryption, the decryption algorithm does not have a clue how to replace the dropped bit.
  • In an expansion P-box, an input mat be mapped to more than one output during encryption, the decryption algorithm does not have a clue which of the several inputs are mapped to an output
• However, there are ciphers that use compression or expansion P-boxes in the encryption cipher. The effects of these are canceled in the decryption cipher

S-Boxes

• S-box (substitution box) can be thought of as a miniature substitution cipher.
• S-box is an m × n substitution unit, where m and n are not necessarily the same.
  • Example: The following table defines the input/output relationship for an S-box of size 3 × 2. The leftmost bit of the input defines the row; the two rightmost bits of the input define the column. The two output bits are values on the cross section of the selected row and column.
  • Based on the table, an input of 010 yields the output 01. An input of 101 yields the output of 00.

S-Boxes: Invertibility

• S-box may or may not be invertible
  • In an invertible S-box, the number of input bits should be the same as the number of output bits.
  • Following figure shows an example of an invertible S-box. For example, if the input to the left box is 001, the output is 101. The input 101 in the right table creates the output 001, which shows that the two tables are inverses of each other.

Exclusive-OR (XOR)

• Exclusive-or (XOR) operation is reversible
  • When XOR is used twice, it produces the original values
  • An important component in most block ciphers is the XOR operation
• The five properties of the exclusive-or operation in the GF(2$^n$) field makes this operation a very interesting component for use in a block cipher: closure, associativity, commutativity, existence of identity, and existence of inverse

Circular Shift

• Another component found in some modern block ciphers is the circular shift operation.Q: Is circular shift invertible? → YES

Swap

• Swap operation is a special case of the circular shift operation where k = n/2.

Split and Combine

• Two other operations found in some block ciphers are split and combine.

Product Cipher

• Shannon(S-P network) introduced the concept of a product cipher.
• A product cipher is a complex cipher combining substitution(S), permutation(P), and other components discussed in previous sections.
• Product cipher have two important properties – diffusion(확산) and confusion(혼동, 혼란)

Diffusion, Confusion, and Rounds

• Diffusion: The idea of diffusion is to hide the relationship between the ciphertext and the plaintext.
  • Example
    • In the first round, bit 8 affects two bits (bits 7 and 8) through S-box 4. Bit 7 is permuted and becomes bit 4; bit 8 is permuted and becomes bit 2. After the first round, bit 8 has affected bits 2 and 4.
    • In the second round, bit 2 affects two bits (bits 1 and 2) through S-box 1. Then bit 1 is permuted and becomes bit 6; bit 2 is permuted and becomes bit 1.
    • After the second round, bit 8 has affected bits 1, 3, 6, and 7.
• Confusion: The idea of confusion is to hide the relationship between the ciphertext and the key
  • Example
    • The four bits of ciphertext, bits 1, 3, 6, and 7, are affected by three bits in the key (bit 8 in K1 and bits 2 and 4 in K2).
    • The relationship between ciphertext bits and key bits is obscured.
• Rounds: Diffusion and confusion can be achieved using iterated product ciphers where each iteration is a combination of S-boxes, P-boxes, and other components.

Two Classes of Product Ciphers

• Modern block ciphers are all product ciphers, but they are divided into two classes.
• 1. Feistel ciphers
• 2. Non-Feistel ciphers

Feistel Ciphers

• Feistel designed a very intelligent and interesting cipher that has been used for decades.
• A Feistel cipher can have three types of components: self-invertible(XOR), invertible, and non-invertible.
• A Feistel cipher combines all non-invertible elements in a unit and uses the same unit in the encryption and decryption algorithms.
• The question is how the encryption and decryption algorithms are inverse of each other if each has a non-invertible unit. Feistel shows that they can be canceled out
  
  

• The first thought in Feistel cipher design
  

• Improvement of the previous Feistel design
  

• Final design of a Feistel cipher with two rounds

Feistel Cipher Structure

• Horst Feistel devised the feistel cipher
• Partitions input block into two halves
  • process through multiple rounds
  • split data into two parts
  • different operations on each side
  • then have permutation swapping halves
• Implements Shannon’s S-P net concept

Feistel Cipher Design Elements

• Block size: increasing size improves security, but slows cipher
• Key size: increasing size improves security, makes exhaustive key searching harder, but may slow cipher
• Number of rounds: increasing number improves security, but slows cipher
• Subkey generation algorithm: greater complexity can make analysis harder, but slows cipher
• Round function: greater complexity can make analysis harder, but slows cipher
• Fast software en/decryption: more recent concern for practical use
• Ease of analysis: for easier validation & testing of strength

Non-Feistel Ciphers

• A non-Feistel cipher uses only invertible components
• A component in the encryption cipher has the corresponding component in the decryption cipher.

---

Data Encryption Standard (DES)

• Most widely used block cipher in world
• Adopted in 1977 by NBS (now NIST)
  • as FIPS PUB 46
• Encrypts 64-bit data using 56-bit key
• Has widespread use
• Has been considerable controversy over its security
  
  ※ NIST(National Institute of Standards and Technology)
  ※ FIPS(Federal Information Processing Standards Publication)

DES History

• IBM developed Lucifer cipher
  • by team led by Horst Feistel in late 60’s
  • used 64-bit data blocks with 128-bit key
• Then redeveloped as a commercial cipher with input from NSA and others
• In 1973 NBS issued request for proposals for a national cipher standard
• IBM submitted their revised Lucifer which was eventually accepted as
  the DES

Conceptual View of DES

• DES is a block cipher

Broad Level Steps in DES

• The encryption process is made of two permutations (P-boxes), which we call initial and final permutations, and sixteen Feistel rounds

Rounds

• DES uses 16 rounds. Each round of DES is a Feistel cipher.

Key Generation

• The round-key generator creates sixteen 48-bit keys out of a 56-bit cipher key.
• Initial 64bit key is transformed into a 56-bit key. Then 8 extra parity bits (bit 8, 16, 24, … 64) are dropped before the actual generation process.
• 56-bit key is divided into two halves, each of 28 bits. These halves are circularly shifted left by one or two positions, depending on the round

DES Cipher and Reverse Cipher

DES Weaknesses

1. Weaknesses in S-boxes → 역으로 유추될 수 있는 취약점
2. Weaknesses in Key

• Critics believe that the most serious weakness of DES is in its key size. To do brute-force attack8 on a given ciphertext block, the adversary needs to check 2$^{56}$ keys. → 56 bits는 너무 작다
• Computer network can simulate parallel processing. In 1997 a team of researchers used 3,500 computers attached to the Internet to find a key challenged by RSA Lab. in 120 days.
• If 3,500 networked computers can find the key in 120 days, a secret society with 42,000 members can find the key in 10 days.

3. Differential and linear Cryptoanalysis
   → 비선형 함수인 S-BOX의 잘못된 설계에 의해 분석이 가능함
4. Timing attack

Multiple Encryption & DES

• Clear a replacement for DES was needed
  • Demonstrated exhaustive key search attacks
• AES is a new cipher alternative
• Prior to this alternative was to use multiple encryption with DES implementations
  • Double DES: Perform DES twice with two different keys
  • Triple DES with Three Different Keys
  • Triple DES with Two Different Keys
• Triple-DES is the chosen form

Double-DES

• Could use 2 DES encrypts on each block
  $C = E_{K2}(E_{K1}(P))$
• Issue of reduction to single stage
• And have “meet-in-the-middle” attack
  • works whenever use a cipher twice
  • since $X = E_{K1}(P) = D_{K2}(C)$
  • attack by encrypting P with all keys and store
  • then decrypt C with keys and match X value
  • can show takes O(2*2$^{56}$)steps → not 2$^{112}$

Triple-DES with Two-Keys

• Hence must use 3 encryptions
  • would seem to need 3 distinct keys
• But can use 2 keys with E-D-E sequence
  • $C = E_{K1}(D_{K2}(E_{K1}(P)))$
  • if K1=K2 then can work with single DES
• Standardized in ANSI X9.17 & ISO8732
• No current known practical attacks
  • several proposed impractical attacks might become basis of future attacks→ Complexity problem

Triple-DES with Three-Keys

• Although are no practical attacks on two-key Triple-DES have some indications
• Can use Triple-DES with three-keys to avoid even these
  $C = E_{K3}(D_{K2}(E_{K1}(P)))$
• Has been adopted by some Internet applications, e.g., PGP, S/MIME

---

Advanced Encryption Standard (AES)

History

• Clear a replacement for DES was needed
  • Can use Triple-DES, but slow in software, has small blocks
• US NIST issued call for ciphers in 1997
  • The criteria defined by NIST: Security, Cost, Implementation
• 15 candidates accepted in Jun 1998
• 5 were shortlisted in Aug 1999
• Rijndael was selected as the AES in Oct 2000
• Issued as FIPS PUB 197 standard in Nov 2001

The AES Cipher: Rijndael

• Designed by Rijmen-Daemen in Belgium
• Non-Feistel cipher
  • iterative rather than feistel cipher
• Block length of 128 bits
• Uses 10, 12, 14 rounds
• Key size can be 128, 192, 256 bits
  • depends on the number of rounds
• Designed to be:
  • resistant against known attacks
  • speed and code compactness on many CPUs
  • design simplicity

General Design of AES

• AES Encryption cipher

Data Units in AES

• Byte: 8 bits
• Word: 32 bits
• Block: 128 bits
• State: 4x4 bytes
  
  

• Block-to-state and state-to-block transformation

• Example: changing plaintext to state

Structure of Each Round

• To provide security, AES uses four types of transformations
  • Substitution
  • Permutation
  • Mixing
  • Key-adding

Transformations: Substitution → Invertible

• SubBytes
  • To substitute a byte, we interpret the byte as two hexadecimal digits
  • The SubBytes operation involves 16 independent byte-to byte transformations.
• InvSubBytes
  • InvSubBytes is the inverse of SubBytes.
    
• Example
  → Note that if the two bytes have the same values, their transformation is also the same
• Pseudocode for SubBytes transformation

Transformations: Permutation

• ShiftRows
  • In the encryption, the transformation is called ShiftRows.
• InvShiftRows
  • In the decryption, the transformation is called InvShiftRows and the shifting is to the right.
• Pseudocode for ShiftRows transformation
• Example

Transformations: Mixing

• We need an interbyte transformation that changes the bits inside a byte, based on the bits inside the neighboring bytes.
• We need to mix bytes to provide diffusion at the bit level

• MixColmns
  • The MixColumns transformation operates at the column level; it transforms each column of the state to a new column.
• InvMixColumns
  • The InvMixColumns transformation is basically the same as the MixColumns transformation.

• Pseudocode for MixColumns transformation

• Example

Transformations: Key Adding

• AddRoundKey
  • AddRoundKey proceeds one column at a time.
  • AddRoundKey adds a round key word with each state column matrix; the operation in AddRoundKey is matrix addition.
  • The AddRoundKey transformation is the inverse of itself

Transformations

Key Expansion

• To create round keys for each round, AES uses a key expansion process.
• If the number of rounds is N$_r$ , the key-expansion routine creates N$_r$ + 1 128-bit round keys from one single 128-bit cipher key.
  • Words for each round

Key Expansion in AES-128

• RotWord
  • Similar to the ShiftRows but it is applied to only one row.
  • The routine takes a word as an array of four bytes and shifts each byte to the left with wrapping.
• SubWord
  • Similar to the SubBytes but it is applied to only to four bytes.
  • The routine takes each byte in the word and substitutes another byte for it.

• Round Constants (RCon)
  • Each round constant, RCon, is a 4-byte in which the rightmost three bytes are always zero.
  • The key-expansion routine can either use the table below when calculating the words or use the GF(2$^8$) field to calculate the leftmost byte dynamically, as shown below (prime is the irreducible polynomial):

• Pseudocode for key expansion in AES-128

• Example
  • The 128-bit cipher key agreed upon by Alice and Bob is
    (24 75 A2 B3 34 75 56 88 31 E2 12 00 13 AA 54 87)$_{16}$
    
  • The two sets of round keys can be created from two cipher keys that are different only in one bit.
    
  • The concept of weak keys, as we discussed for DES in previous section, does not apply to AES. Assume that all bits in the cipher key are 0s. The following shows the words for some rounds:
  • The words in the pre-round and the first round are all the same. In the second round, the first word matches with the third; the second word matches with the fourth. However, after the second round the pattern disappears; every word is different.

Key Expansion in AES-192 and AES-256

• Key-expansion algorithms in the AES-192 and AES-256 versions are very similar to the key expansion algorithm in AES-128, with the following differences
• In AES-192, the words are generated in groups of six instead of four.
  • The cipher key creates the first six words (𝒘$_0$ to 𝒘$_5$).
  • If 𝑖 mod 6 ≠ 0, 𝒘$_𝑖$ ← 𝒘$_{i−1}$ + 𝒘$_{i−6}$; otherwise, 𝒘$_𝑖$ ← 𝒕 + 𝒘$_{𝑖−6}$
• In AES-256, the words are generated in groups of eight instead of four.
  • The cipher key creates the first eight words (𝒘$_0$ to 𝒘$_7$).
  • If 𝑖 mod 8 ≠ 0, 𝒘$_𝑖$ ← 𝒘$_{𝑖−1}$ + 𝒘$_{i−8}$; otherwise, 𝒘$_𝑖$ ← 𝒕 + 𝒘$_{𝑖−8}$
  • If 𝑖 mod 4 = 0, but 𝑖 mod 8 ≠ 0 , then 𝒘$_𝑖$ = 𝑆𝑢𝑏𝑊𝑜𝑟𝑑 𝒘$_{𝑖−1}$ + 𝒘$_{𝑖−8}$

Ciphers: Original Design

• In the standard, the encryption algorithm is referred to as the cipher and the decryption algorithm as the inverse cipher
• The code for the AES-128 version

Ciphers: Alternative Design

• Invertibility of SubBytes and ShiftRows combinations
• Invertibility of MixColumns and AddRoundKey combination→ Complexity↓
• Changing KeyExpansion Algorithm
  • Instead of using InvAddRoundKey transformation in the reverse cipher, the keyexpansion algorithm can be changed to create a different set of round keys for the inverse cipher.

Examples → 한번 따라 가보기!

• The following shows the ciphertext block created from a plaintext block using a randomly selected cipher key
• State entries in on round 7
• One may be curious to see the result of encryption when the plaintext is made of all 0s. Using the cipher key in previous example yields the ciphertext

Analysis of AES

• Security
  • AES was designed after DES. Most of the known attacks on DES were already tested on AES.
  • Brute-Force Attack
    • AES is definitely more secure than DES due to the larger-size key.
  • Statistical Attacks
    • Numerous tests have failed to do statistical analysis of the ciphertext.
  • Differential and Linear Attacks
    • There are no differential and linear attacks on AES as yet.
• Implementation
  • AES can be implemented in software, hardware, and firmware.
  • The implementation can use table lookup process or routines that use a welldefined algebraic structure.
• Simplicity and cost
  • The algorithms used in AES are so simple that they can be easily implemented using cheap processors and a minimum amount of memory

---

Cryptography Modes

→ 그림보고 구분가능해야함

• Block ciphers encrypt fixed size blocks
  • eg. DES : 64-bit blocks, AES : 128-bit blocks
• Need some way to en/decrypt arbitrary amounts of data (say, b-bit block)
• NIST SP 800-38A defines 5 modes
• To cover a wide variety of applications
• Can be used with any block cipher, including triple DES and AES

Electronic Code Book (ECB)

• Message is broken into independent blocks which are encrypted
• Each block is a value which is substituted, like a codebook
• Each block is encoded independently of the other blocks
  $C_i = E_K(P_i)$
  $P_i = D_K(C_i)$
• Usage: secure transmission of single values

• Encryption in ECB Mode→ Same key, 마지막 블록은 padding으로 채워줌
• Decryption in ECB Mode

• Advantages and limitations of ECB
  • Message repetitions may show in ciphertext
    • If aligned with message block particularly with data such graphics or with messages that change very little, which become a codebook analysis problem
  • Weakness is due to the encrypted message blocks being independent
    • Ciphertext blocks 1, 3, and 7 are same. One block is revealed, rest of the blocks are also revealed.
    • If Eve knows that block 8 always conveys specific information, she can replace this block with the corresponding block in the previously intercepted message.
  • The error in a single block does not have any effects on the other blocks.
    • A single error in transmission can create errors in several in the corresponding block.
  • Main use is sending a few blocks of data

Cipher Block Chaining (CBC)

• Message is broken into blocks
• Linked together in encryption operation
• Each previous cipher blocks is chained with current plaintext block
• Use Initialization Vector (IV) to start process
  $C_0 = IV$
  $C_i = E_K(P_i ⨁ C_{i-1})$
  $P_i = D_K(C_i) ⨁ C_{i-1})$
• Usage: bulk data encryption, authentication→ Parallel processing 불가능→ Parallel processing 가능

• Initialization Vector(IV)
  → Random value, 비밀일 필요는 없음, but sender / reciever 동일해야함
  • Protection of IV
  • If an opponent can predictably change bits in IV, the corresponding bits of the received value of P1 can be changed.

• Advantages and limitations of CBC
  • If two messages are equal, their encipherment is the same for same IV.
    • Some people recommend the use of timestamp as an IV.
  • A single error in C$_j$ may create error in most bits in P$_j$ during decryption and toggles only one bit in P$_{j+1}$(영향을 줌). P$_{j+2}$ to P$_N$(영향권 밖) are not affected

Cipher FeedBack (CFB)

• Message is treated as a stream of bits and added to the output of the block cipher
• Used when the plaintext or ciphertext block size (e.g., plaintext is
  ASCII) is smaller than cipher block size (DES: 64bits, AES:128bits)
• Encrypt/decrypt the contents of a shift register instead of encrypting the plaintext or decrypting the ciphertext.
• The shift register S$_i$ is made by shifting the shift register S$_{i-1}$ s bits to the left and filling the rightmost s bits with C$_{i-1}$
• Standard allows any number of bit (1,8, 64 or 128, etc) to be feed back
  • Denoted CFB-1, CFB-8, CFB-64, CFB-128, etc

• Encryption in CFB-s Mode
• Decryption in CFB-s Mode
• Advantages and Limitations of CFB
  • Appropriate when data arrives in bits/bytes
  • Most common stream mode
  • Note that the block cipher is used in encryption mode at both ends
  • Errors propagate for several blocks after the error

Output Feedback (OFB)

• Similar to CFB, but each bit in the ciphertext is independent of the previous bit or bits. This avoids error propagation
• Encryption in OFB mode
• Decryption in OFB mode

Counter (CTR)

• A “new” mode, though proposed early on
• Similar to OFB but encrypts counter value rather than any feedback value
• Must have a different key & counter value for every plaintext block (never reused)
• Usage: high-speed network encryptions

• Encryption in Counter Mode
• Decryption in Counter Mode
• Advantages and Limitations of CTR
  • Efficiency
    • can do parallel encryptions in H/W or S/W
    • can preprocess(counter) in advance of need
  • Random access to encrypted data blocks
  • Provable security (good as other modes)
  • Only the implementation of the encryption algorithm is needed
  • But must ensure never reuse key/counter values, otherwise could break

Summary

HGU 전산전자공학부 고윤민 교수님의 24-2 컴퓨터 보안 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.