2021-09-27-현대암호학-4주차.md

4. Data Encryption Standard (DES)

---

DES (Data Encryption Standard)

• DES (Data Encryption Standard)
  • 미국 연방 표준국(현 NIST)의 대칭키 암호에 대한 표준 알고리즘 공모 (1973)
  • IBM의 Lucifer 를 수정하여 DES로 선정(1977)
    • FIPS 46-3
  • 미국 국가 안보국(NSA)의 수정된 버전
    • 키 길이: 128비트 → 56비트
    • S-Box 형태 변경 (설계 원리 비공개)
    • 백도어(backdoor) 논란
  • AES로 대체되며 DES 표준은 공식적으로 철회 (2005)
    • NIST는 2030년까지 정부 문서에 3-DES를 사용하는 것을 허용
• DES 기술 개요 (1)
  • 혼돈 & 확산의 곱 암호 (product cipher)
  • 64비트 (데이터) 블록 암호: $M=C= \{0,1\}^{64}$
  • 56비트 길이 키: $K = \{0,1\}^{56}$
    • 최대 $2^{56}$번으로 올바른 키 추측 가능 (=56비트 안전성)
    • 현재 128~256비트 안전성이 적당함
• DES 기술 개요(2)
  • $M=C= \{0,1\}^{64}$
  • $K = \{0,1\}^{56}$
  • 알고리즘 구성

    • 초기 순열 (Initial Permutation, IP)

    • 최종 순열 (Finial Permutation, FP)

    • 16개 라운드의 페이스텔(Feistel) 구조

    • 키 스케줄링 함수

      

Background

• 부호화(encoding)
  • 문자열을 비트(0 또는 1)로 대응
  • ex. ASCII, UTF-8, EUC-KR, ...
• 베타적 논리합 (exclusive or, XOR, $\oplus$)
  • 비트간 XOR: 2개의 입력 비트가 같으면 0, 다르면 1을 출력

Confusion(혼돈) and Diffusion(확산)

• Shannon의 혼돈과 확산 이론
  • 블록암호 설계의 기본 원리
  • 혼돈(Confusion): 키(K)와 암호문(C) 관계를 감추는 성질
    • 주로 치환(Substitution, S-box)를 이용
  • 확산(Diffusion): 평문(P)과 암호문(C) 관계를 숨기는 성질
    • DES: 전치(Permutation, 순열)를 이용
    • AES: 발전된 형태인 MixColumn 사용
• 곱 암호 (product cipher)
  • 혼돈과 확산을 결합
  • 라운드(round) 부분이 여러 번 반복되는 구조
• 곱 암호의 형태
  • S-Box에 1비트가 다른 두 값이 입력되면 두 출력값은 2비트 이상이 달라야 함
  • 하나의 S-Box에서 출력된 비트들은 다음 라운드에서 모든 S-Box의 입력 값으로 확산되어 들어갈 수 있도록 순열이 구성되어야 함
  • 현대 블록 암호는 평문의 한 비트가 바뀌면 평균적으로 암호문 비트의 반 정도가 바뀜
    • n비트 블록이면 최소 (n-1)라운드 구성

Feistel Cipher

• 페이스텔(Feistel) 암호
  • 곱 암호의 대표적인 구조
  • 가역(invertible) 요소와 비가역(non-invertible) 요소를 모두 사용
    • 비가역 요소까지 이용함으로써 자유로운 설계 가능
  • XOR 연산을 기본 원리로 이용
  • 암호화 과정과 복호화 과정이 동일
    • 암호화와 복호화를 동일 프로그램으로 효율적으로 구현 / 관리
  • DES, SEED 등
• 비페이스텔(Non-Feistel) 암호
  • 가역 요소만 사용
  • AES, ARIA 등
• 1라운드 페이스텔(Feistel) 구조
  • 함수 $F$가 비가역 요소여도 문제가 없음
  • 입력의 오른쪽 반은 암호화/복호화가 되지 않음
    • 암호화: $L_1 = L_0 \oplus F(k, R_0); R_1 = R_0$
    • 복호화: $L_0 = L_1 \oplus F(k, R_1) = L_0 \oplus F(k, R_0) \oplus F(k, R_1); R_0 = R_1$
• 다중 페이스텔(Feistel) 구조
  • 라운드 마지막에 왼쪽 부분과 오른쪽 부분을 교차(swap)함
    • 마지막 라운드 제외
  • 페이스텔 2라운드는 비 페이스텔 구조 1라운드와 같은 안전성
    • 상대적으로 많은 라운드수가 필요함
  • 암호화 복호화 과정은 동일하고 라운드 키가 역순으로 사용
  • $F$ 함수의 안전성에 의존함

DES Components

• 초기 순열(Initial Permutation, IP)과 최종 순열(Final Permutation, FP)
  • 초기 순열과 최종 순열은 서로 역관계에 있음 ($FP = IP^{−1}$)
  • 64비트를 입력받아 비트 단위의 자리바꿈이 일어남
• 라운드 함수
  • 혼합(Mixer):
    1. 오른쪽 32비트 값과 라운드 키를 이용하여 F 함숫값 계산
    2. 계산 한 함숫값을 왼쪽 32비트 값과 XOR 연산
  • 교환 (Swapper):
    1. XOR 연산 결과를 오른쪽으로 이동
    2. 처음 입력된 값의 오른쪽 값을 왼쪽으로 이동
• 라운드 함수 - $F$ 함수

  • {확장 순열, 라운드 키 결합, 치환 테이블 8개, 고정 순열}로 구성

  • 라운드 입력 값의 오른쪽 32비트 $R_{i-1}$와 48비트 라운드 키 $K_i$를 입력받음

    • 각 라운드 키는 키 스케줄링 함수에 의해 생성됨

  • 32비트 값을 출력함

    

  • 확장 순열 (expansion P-Box)

    1. 32비트 입력값을 4비트씩 8개 묶음으로 나눔
    2. 정해진 규칙으로 각 4비트를 6비트로 확장
       • 즉 32비트를 입력받아 48비트를 출력함

  • 라운드 키 결합(XOR)

    • 확장 순열의 출력값 48비트는 라운드 키와 XOR 연산

  • 치환 테이블 (S-Box)

    1. 48비트 입력값을 6비트씩 8개 묶음으로 나눔
    2. 각 6비트를 순서대로 8개의 S-Box에 입력
    3. 각 S-Box는 6비트를 입력받아 4비트로 축소한 값을 출력
    • 입력된 6비트 중 첫번째와 여섯번째 비트를 붙여 행(row)을 결정
    • 나머지 두번째부터 다섯번째까지 4비트는 열(column)을 결정
    • DES 내부에서 유일하게 비선형성을 만족함

      $S(A) \oplus S(B) ≠ S(A \oplus B)$

  • 고정 순열 (straight P-Box)

    • 치환 테이블 과정에서 출력된 32비트 값을 자리바꿈 함
• 키 스케쥴링

  • {패리티비트 제거, 쉬프트, 압축 순열}로 구성

  • 64비트 비밀키를 입력으로 받음

    • 오류검사를위한 패리티 비트 제거
    • 패리티 비트는 안전에 기여하지 않음
    • 실제로는 56 비트만 사용

  • 16개의 48비트 라운드 키 출력
    - 비밀키 56비트의 각 비트가 16라운드 중 14번 정도 사용되도록 설계

    

  • 패리티 비트 제거 (parity bit drop)

    • 오류를 검사하기 위하여 패리티 비트를 사용
      • Ex) 데이터 1010101에 대하여 전체 1의 개수가 홀수가 되도록 패리티 비트를 1로 설정
    • 64비트 중 8개의 패리티 비트는 8의 배수(8, 16, 24, 32, 40, 48, 56, 64)번째에 위치
    • 패리티 비트를 제거하고 주어진 표에 의하여 자리를 바꿈

  • 쉬프트(shift)

    1. 입력으로 들어온 56비트를 왼쪽 28비트 / 오른쪽 28비트로 나눔
    2. 각 28비트를 라운드에 따라 1비트(또는 2비트)만큼 왼쪽으로 순환 쉬프트

  • 압축 순열 (compression P-Box)

    • 56비트 입력값을 48비트로 출력

DES Encryption and Decryption

• 암호화/복호화 과정이 동일
  • 16라운드 이후 교환 과정 없음
  • 라운드 키를 역순으로 입력
• 비가역 요소들은 XOR로 제거
  • $F$ 함수, 확장 P-Box, S-Box
  • 구성요소에 상관없이 XOR 연산을 한번 더 함으로써 복호화 가능

Analysis

• 취약 키 (weak key): 동일한 라운드 키 생성

  • 패리티 비트를 제거한 56비트 중 28비트가 모두 0이거나 1인 경우

  • 라운드 키가 모두 동일하게 생성됨

    • 패리티 비트 제거 → 쉬프트 → 압축 순열
    • 암호화를 두 번 하면 평문 메시지가 다시 나오게 됨
    • 즉, $m = Enc_k(Enc_k(m))$

  • $2^{64}$가지 중 4가지 존재

    

• 준 취약 키 (semi-weak key): 2 종류의 라운드 키 생성
  • $k_1$으로 암호화하고 $k_2$로 다시 암호화하면 평문을 얻을 수 있는 키 쌍
    • 총 6쌍(=12개) 존재
• 가능한 취약 키 (possible weak key): 4 종류의 라운드 키 생성
  • 총 48개 존재
• Remark. DES 구현 시 키 입력 단계에서 취약키 여부를 검사하며, 이러한 키들을 선택할 확률은 대략 $(4+12+48) / 2^{56} \approx 8.8 \times 10^{-16}$
• 전사적 공격 (brute force attack)
  • 개발 당시 환경에서는 안전하다고 판단
    • 당시 기기로 전수조사를 실시하는 경우 1000년 이상 소요
    • 수백만 대 기기를 구성하여도 수천만 달러가 필요했음
  • 1990년대 중반 이후 기술 발달에 의해 전수 조사가 가능해짐
• 보수 특성 (complementation property)
  • 입력되는 비밀키와 평문이 서로 보수 관계이면 암호문도 보수가 되는 성질
    • 보수 : $\overline 1 = 0; \overline 0 = 1$
  • $c = Enc_k(m) → \overline c = Enc_{\overline k}(\overline m)$
  • 보수 특성을 이용하여 전수조사의 복잡도를 절반($=2^{55}$)로 낮출 수 있음
• 차분 분석 (differential cryptanalysis)
  • 두 평문의 차분과 암호문의 차분의 관계를 분석
    • 선택 평문 공격 (CPA)
    • S-Box의 입출력에 대하여 차분 분석표를 작성
  • $2^{47}$개의 평문/암호문 쌍을 가지고 $2^{47}$의 계산량으로 비밀 키 추측 가능
• 선형 분석 (linear cryptanalysis)
  • 주어진 평문과 암호문으로 비밀키를 평문과 암호문에 대한 선형식으로 표현
    • 알려진 평문 공격 (KPA)
  • $2^{43}$개의 평문/암호문 쌍을 얻을 수 있다면 높은 확률로 선형 표현식을 얻음

Multiple DES

• 이중 DES (double DES)
  • 서로 다른 2개의 키를 이용하여 DES를 두 번 사용
    • $k_1$으로 암호화 한 결과를 다시 $k_2$를 이용하여 재 암호화
    • $c = Enc_{k_2}(Enc_{k_1}(m))$
  • 56비트인 DES의 짧은 키를 보완하고 112 비트 안전성을 기대함
    • But 중간 일치 공격에 의해 57비트 안전성만 제공
• 중간 일치 공격 (meet-in-the-middle attack)
  • Fact. 이중 DES에서 $m$을 $k_1$로 암호화한 결과는 $c$를 $k_2$로 복호화한 결과와 같다:
    • $Enc_{k_1}(m) = Dec_{k_2}(c)$
  • 알려진 평문 공격(KPA)으로 $(m, c)$를 얻었을 때,
    1. $2^{56}$번의 연산으로 $m$에 대한 모든 암호문 저장
    2. $2^{56}$번 연산으로 $c$에 대한 모든 평문 저장
    3. 같은 중간 값을 가지는 $k_1$, $k_2$를 찾음
  • $2^{56}$ 저장메모리와 $2^{57} = 2 × 2^{56}$ 번의 연산으로 공격을 성공할 수 있음
    • $k_1$, $k_2$를 찾기 위한 정렬/검색 연산 포함 시 $2^{63}$번의 연산
• 삼중 DES (triple DES)
  • 기존 DES를 3번 사용
    • 2TDES: 첫번째 키 $k_1$과 세번째 키 $k_3$가 같은 경우
    • 3TDES: 모든 키가 모두 다른 경우
  • 적어도 $2^{112}$ 계산량이 필요할 것으로 기대