정보보안:: Block Ciphers & DES

Block Ciphers & DES (Data Encryption Standard)

Block Cipher vs Stream Cipher

• Stream ciphers : 각각의 bit를 암호화한 결과
• Block ciphers : 전체 block (bit의 집합)을 암호화한 결과

---

Stream cipher

Encryption & Decryption with Stream Ciphers

• 암호화 / 복호화 연산은 modulo 2 덧셈 (= XOR)으로 한다.

Synchronous vs Asynchronous Stream Cipher

• Synchronous Stream Cipher : key stream이 오직 key에만 의존
• Asynchronous Stream Cipher : key stream이 key + ciphertext에 의존

mod 2 덧셈(XOR)을 사용하는 이유

• 난수성 : 0, 1이 50% 확률로 나오기 때문 > Random한 key stream의 특성이 ciphertext에도 그대로 반영됨

Stream cipher 예시

LFSR (Linear Feedback Shift Register)

LFSR 구조 및 x_m+3 = x_m+1 XOR x_m인 이유

• 평문과 암호문의 관계가 선형적이기 때문에 암호학적으로 매우 취약하다.
• 2n길이의 연속적인 값만 가지고 있어도 key를 파악할 수 있다.

key의 길이를 무한대로 하는 알고리즘인 OTP(one-time pad)를 이용하면 연산 결과가 반복되지 않을 수도 있지만 현실적으로 불가능하다. 따라서 key의 길이가 n이면 Generated sequence의 길이는 2^n - 1보다 작거나 같아서 결과가 반복될 수 있고 이로 인해 쉽게 key의 길이를 얻을 수 있다.

 

공격

• 우리는 LFSR의 크기를 모르는 상황이다.
• 따라서 레지스터의 크기를 가정하여 방정식의 계수를 알아내고
  이 방정식을 통한 결과가 sequence랑 일치한지 비교하면서 크기를 알아내고자 한다.

 

GSM A5/1 Stream cipher

• C1, C2, C3에서 1, 0이 많이 나온 것을 값으로 가지는 방법 > 비선형적

Trivium

• 3개의 AND gate를 통해 비선형성을 만듦.
  AND gate는 0을 만나면 나머지 값을 무의미하게 만들어 비선형을 만듦

---

Block ciphers

• 모든 대칭 블럭 암호는 Feistel Cipher Structure을 기반으로 한다.

Substitution & Permutation

• Substitution (S-box) : 치환 - confusion : ciphertext와 key의 관계를 복잡하게 만드는 특성
• Permutation (P-box) : 전치 - diffusion : 난수성

두가지를 묶어서 S-P network라고 칭하고 이를 Claude Shannon이라는 사람이 아이디어를 발표함.

Feistel Cipher Structure

block cipher를 이루는 기본 구조

• L_i = R_i-1 (왼쪽은 이전 오른쪽 값 그대로)
• R_i = L_i+1 XOR f(R_i-1, K_i-1) (오른쪽 값은 왼쪽 값과 오른쪽 값에 함수를 취한 결과를 XOR한 연산 결과)

---

DES (Data Encryption Standard)

• Key 길이 : 56bit + 8bit의 parity bit
• 기본 연산
  • substitution
  • transpostion
  • linear operation(XOR)

세부적인 흐름

전체

Encryption 개요

Round 흐름

f 함수

1. Plaintext 절반인 32bits와 key 48bits 연산을 위해 32bits를 48bits로 Expansion
2. 48bit의 subkey와 XOR 연산
3. 8개의 S-box에 넣기 위해 6bit씩 나눔
4. 6bit가 S-box에 의해 4bit로 바뀜
5. P-box를 지나 32bit 결과값을 출력함

---

Detail - Initial Permutation

 

위의 표를 통해 입력값이 섞이게 된다.

예) 입력값의 7번째 비트는 64번째 비트로 출력된다.

 

Detail - Expansion Permutation E

f함수에서 32bit를 48bit로 expansion하는 과정이 있었다.

입력값을 반복하여 48bit로 확장하는 원리이다.

이때 확장하면서 입력값의 위치를 바꾸는 permutation 과정이 있음을 확인할 수 있다.

 

Detail - S-Boxes

6bit를 4bit로 치환하는 과정

• 맨 첫번째 비트, 마지막 비트 > Row 선택
• 나머지 비트는 십진수로 변환 > Column 선택

Detail - P-Boxes

 

 

 

Key Schedule

56bit의 key를 48bit로 만드는 로직

Cryptanalysis (암호학적 분석)

• Key Size = 56bit 즉, 2^56의 key space를 가짐
  하지만 최근에는 Brute force search로 22시간만에 뚫을 수 있음
• Timing Attacks : key란 얼마나 같은지에 따라 계산 시간이 달라짐 즉, 입력값에 따라 연산시간이 달라진다.
• Analytic Attack (이론적 공격)
  • differntial cryptanalysis : 16bit 차이나게 하는 입력 비트를 두어 key 변화나 통계적 특성을 찾는 것
  • linear cryptanalysis
    - key space가 2^47 감소
  • related key attacks