[컴퓨터보안] Computer-based Symmetric Key Cryptographic Algorithms(Part 1)

Cryptography Algorithm Types and Modes

Cryptography Algorithms

• 암호화 알고리즘은 메시지를 안전하게 전송하기 위한 암호화 및 복호화 과정을 정의하는 메커니즘
  • Algorithm types modes는 알고리즘의 두 가지 주요 측면
  • Algorithm types:  알고리즘이 한 번에 몇 비트의 평문을 암호화하는지를 정의
  • Algorithm modes: 알고리즘 유형이 결정된 후 암호화 알고리즘의 세부 사항을 정의

Algorithm Types

• Stream Cipher
  • 비트 단위로 암호화와 복호화를 수행하는 방식 (한 비트씩 암호화)
  • stream key를 생성하여 plaintext XOR 연산을 수행하여 암호화함
• Block Cipher
  • 데이터를 블록 단위로 암호화하고 복호화하는 방식 (일정 크기의 데이터 블록이 한 번에 암호화)
  • 고정된 크기의 블록에 대해 동작하며, 데이터가 블록의 크기에 맞게 패딩되어야 할 수 있음

Stream Cipher

Block Cipher

Algorithm 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

• The same key used for encryption and decryption
• Quite popular and fast
• Examples: DES, AES, IDEA, Blowfish, RC4/5

Symmetric Key Modern Block Ciphers

• 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

• Combination of transposition units (called P-box), substitution units (called S-box)
• 예시)
  • 64비트(n = 64)인 블록 암호가 있다고 가정하자. 암호문에 1이 10개인 블록 암호가 들어 있다고 할 때, 다음 각 경우에서 가로챈 암호문에서 평문을 복구하기 위해 이브가 시행착오 테스트를 몇 번 해야 합니까?
    • A. The cipher is designed as a substitution cipher.
      • 이브는 평문에 몇 개의 1이 있는지 모르기 때문에 가능한 2^64개의 64비트 블록을 모두 시도해야 한다.
        • Substitution cipher는 각 문자를 다른 문자나 기호로 대체하는 암호화 기술이기 때문에 이브가 평문에 있는 1의 수를 알더라도 각 문자 어떤 문자로 대체되었는지 알려주진 않기 때문이다.
    • B. The cipher is designed as a transposition cipher.  
      • 이브는 평문에 정확히 1이 10개 있다는 것을 알고 있다. 이브는 정확히 10개의 블록을 가진 64비트 블록만을 사용하여 brute-force attack을 할 수 있다.
        • 문자를 대체하는 것이 아니라 순서를 바꾸는 것이기 때문에 1이 몇 개 인지는 알 수 있기 때문이다.

P-Box (permutation box)

• 문자의 자리를 바꾸는 traditional transposition cipher 장치
• 단순(Straight) , 축소(Compression), 확장(Expansion) 세 방식이 존재
• Straight P-box
  • 입력개수: N, 출력개수:M, N=M, 역함수 존재(invertible)
  • 입력 메세지: HELLO -> 출력 메세지: EOLHL
• Compression P-box
  • 입력개수: N, 출력개수:M, N>M, 역함수 존재하지 않음(non-invertible )
  • 입력비트 중 특정 비트가 소실됨
  • 입력 메세지: HELLO -> 출력 메세지: HLO
• Expansion P-box
  • 입력개수: N, 출력개수: M, N<M, 역함수 존재하지 않음(non-invertible )
  • 입력비트 중 특정비트는 한 개 이상의 출력비트와 연결됨
  • 입력 메세지: DOG -> 출력 메세지: DGGDO

•  Invertibility (원래 상태로 되돌릴 수 있는 특징)
  • Straight P-box is invertible
    1. Original permutation table: [6, 3, 4, 5, 2, 1]
    2. Add indices
       • 각 요소의 위치(인덱스)를 나타내는 배열을 만드는 단계
       • index array: [1, 2, 3, 4, 5, 6]
    3. Swap contents and indices
       • Original table의 요소와 인덱스 배열의 값을 서로 교환
       • 예를 들면, 원본 테이블의 첫 번째 요소인 6과 인덱스 배열의 첫 번째 값 0을 서로 교환
       • 교환 후의 original table: [1, 2, 3, 4, 5, 6]
       • 교환 후의 index array: [6, 3, 4, 5, 2, 1]
    4. Sort based on indices
       • 인덱스 배열 기준으로 원본 테이블을 정렬
       • 정렬 후의 original table: [6, 5, 2, 3, 4, 1]
       • 정렬 후의 index array: [1, 2, 3, 4, 5, 6]
    5. Inverted table: [6, 5, 2, 3, 4, 1]

• Compression and expansion P-boxes are non-invertible

S-Box (substitution box)

• 문자를 수학적인 관계 규칙에 의해 치환하는 substitution cipher 장치
• 입출력 개수가 달라도 상관없음
• P-Box와 마찬가지로 입출력 개수가 같을 경우에만 역함수 존재
• S-box may or may not be invertible.
  • 역함수를 가지는 S-box (Invertible S-box):
    • 입력 비트의 수와 출력 비트의 수는 동일함 (one-to-one 관계)
    • 원본 데이터를 정확하게 복원할 수 있음
  • 역함수를 가지지 않는 S-box (Non-invertible S-box):
    • 입력 비트의 수와 출력 비트의 수는 다를 수 있음 (one-to-many or many-to-one 관계)
    • 원본 데이터의 일부 정보가 손실될 수 있어 정확하게 복원할 수 없음
    • 보안성을 높이기 위해 일부 정보를 숨기거나 희생시키는데 사용될 수 있음

S-Box 종류

• XOR (Exclusive-or)
  • XOR operation is reversible
    • When XOR is used twice, it produces the original values. (invertible)
    • An important component in most block ciphers is the XOR operation.

• Circular Shift

Circular Shift

• Swap

• Split and Combine

Product Cipher

• A product cipher is a complex cipher combining substitution, permutation, and other components
• Diffusion (확산)
  • To hide the relationship between the ciphertext and the plaintext
    • ciphertext에 대한 단서를 제공하지 않는 것
• Confusion (혼돈)
  • To hide the relationship between the ciphertext and the key
    • 키를 유추하지 못하도록 하는 것
• Round
  • Diffusion and confusion can be achieved using iterated product ciphers where each iteration is a combination of S-boxes, Pboxes, and other components.
    • Diffusion과 confusion을 여러번 반복할 수 있음
• 예시)
  • Diffusion
    • In the first round
      1. bit 8 affects two bits (bits 7 and 8) through S-box 4.
      2. Bit 7 is permuted and becomes bit 4. bit 8 is permuted and becomes bit 2
      3. After the first round, bit 8 has affected bits 2 and 4.
    • In the second round
      1. bit 2 affects two bits (bits 1 and 2) through S-box 1.
      2. Then bit 1 is permuted and becomes bit 6. bit 2 is permuted and becomes bit 1.
      3. After the second round, bit 8 has affected bits 1, 3, 6, and 7.
  • Confusion
    • The four bits of ciphertext, bits 1, 3, 6, and 7, are affected by three bits in the key.
    • The relationship between ciphertext bits and key bits is obscured.

Two Classes of Product Ciphers

• Feistel ciphers
• Non-Feistel ciphers

Feistel Ciphers

• 대칭 키 암호화 알고리즘 종류
• A Feistel cipher can have three types of components: self-invertible, invertible, and non-invertible.
  • Self-Invertible(자기 역함수): 입력을 받아들이고 동일한 component를 거쳐 출력으로 내보낼 때 역함수를 가진다. 즉, 동일한 component를 통과하면 입력을 그대로 복원할 수 있다.
  • Invertible(역함수): 입력을 받아들이고 출력을 생성할 때 역함수를 가진다. 이 component를 통과하면 입력을 역으로 복원할 수 있다.
  • Non-Invertible(비역함수): 입력을 받아들이고 출력을 생성할 때 역함수를 가지지 않는다. 이러한 component를 통과하면 입력을 역으로 복원하는 것은 불가능하다.

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.