DES의 개요와 기본 구조
DES의 개발 역사
- DES: 대칭키 블록 암호
- 초안에 대한 비판
- 56비트 키 사이즈 -> 전수조사 공격에 대해 취약
- 2000년, DES를 대체하기 위한 최신 블록 암호 표준 AES를 제정
- 세계 최초로 표준화된 상용 암호
DES의 구조
평문으로부터 암호문을 생성할 때, DES알고리즘이 혼돈(confusioin)과 확산(diffusion)이라는 성질을 만족시키기 위해 Feistel암호를 어떻게 사용하였는가?
- DES 암호화와 복호화 과정
- 두 개의 치환(P-box)와 16개의 Feistel 라운드 함수로 구성
- 두 개의 치환(P-box)와 16개의 Feistel 라운드 함수로 구성
초기 치환과 최종 치환
- 초기 치환(IP)과 최종 치환(FP or IP^-1)
- 서로 역의 관계가 성립
- 키가 없는 단순 p-box, 즉 단순 치환 연산
- 초기 치환과 최종 치환 예)
- 평문 비트열의 첫 번째 비트는 초기 치환 단계에서 40번째 비트로 이동됨
- 이후 16번의 라운드를 거친 후 생성된 비트열에서 40번째 비트의 값은 다시 첫 번째 비트로 이동됨
- 초기 치환과 최종 치환은 키와 관련이 없는 이미 고정된 하나의 함수이므로 암호학적으로 중요하지 않음
예제1) 입력 값이 다음과 같은 16진수일 때 초기 치환에 의한 출력은?
예제2) 최종 치환의 입력 값이 다음과 같을 경우, 최종 치환의 출력 값을 찾음으로 두 치환이 서로 역 관계임을 증명하라
0x0000 0080 0000 0002
- 25번째와 63번째 비트 값만 1이고, 나머지 비트 값들은 모두 0임
- 치환 표에 의해 최종 치환에서 입력값의 25번째 비트는 출력 밧의 64번째 비트가 되고, 입력값의 63번째 비트는 출력값의 15번째 비트가 됨
- 따라서 16진수로 나타낸 결과는
0x0002 0000 0000 0001
- 결과적으로 두 치환은 서로 역관계임을 확인할 수 있음
라운드 함수
- DES에서는 총 16번의 라운드 함수를 사용
- 각 라운드 함수는 Feistel 암호임
- 각 라운드는 혼합기(mixer)와 스와퍼(swapper) 그리고 몇 가지 비가역적 요소들로 구성됨
- DES 라운드의 특징
- 스와퍼는 주어진 비트 열의 절반을 교환함
- 혼합기는 두 비트 열에 대해 xor연산을 수행함
- 따라서 역 연산이 가능함
- 그 외 비가역적 요소들은 함수 f(Rl-1, kl)안에 포함
라운드 함수 - DES 함수
- 라운드 함수에 사용된 f(Rl-1, kl)를 의미함
- 32비트 길이의 워드를 출력하기 위해 오른쪽 32비트(Rl-1)에 48비트 키를 적용함
확장 p-box
- 확장 p-box 테이블로 표현한 32비트 워드의 48비트 확장법
Key Whitener(XOR)
- 키 화이트닝이란 중복 블록 암호의 보안성을 높이기 위한 암호 기법
- 키와 데이터의 일정 부분이 혼합되는 단계로 구성됨
- DES 함수에서는 확장 치환을 적용한 이후에 생성되는 48비트 출력 워드에 라운드 키(k1)를 xor 연산
- 확장 치환의 출력 워드와 라운드 키 값 모두 48비트
- 라운드 키(k1)는 이 연산에서만 사용됨
S-박스
- DES에서 S-박스는 48비트 워드의 각 비트들을 섞어주는 용도 -> Confusion
- S-박스에서 섞어진 48비트 워드는 32비트의 워드로 출력됨
- 이를 위해, 6비트의 입력 값과 4비트의 출력 값을 갖는 S-박스 8개를 사용함
S-박스 규칙
- 두 번째 연산의 결과인 48비트 데이터를 8개의 6비트 값으로 분할
- 각각의 6비트 값을 하나의 S-박스에 입력
- 각 S-박스의 결과는 4비트 값 -> 따라서 8개의 S-박스에서 출력되는 결과는 32비트 값
- S-박스에서의 대치 연산
- 4 x 16 S-박스 표를 기반으로 수행
- 이를 위해 8개의 S-박스 표가 사용됨
예제3) S-박스 1의 입력이 100011이다. 출력은 무엇인가?
예제4) S-박스 8의 입력이 000010이다. 출력은 무엇인가?
단순 치환 (Straight Permutation): 마지막에 한 번 섞어주는 거
- DES 함수에서의 마지막 연산
- 32비트의 워드를 입력으로 받아 아래의 단순 치환 표의 규칙에 따라 각 비트들에 대한 치환 연산을 수행한 후 32비트 길이의 워드를 출력함
- 단순 치환 표 -> 앞의 치환 테이블과 동일한 규칙
- 입력 워드에서 7번째 비트의 값 -> 출력 워드에서 2번째 비트로 이동
- 입력 워드에서 25번째 비트의 값 -> 출력 워드에서 32번째 비트로 이동
혼합기(mixer)과 스와퍼(swapper)
- DES 함수에서 16라운드를 갖는 암호 알고리즘과 복호 알고리즘을 구성하기 위해 사용됨
- 마지막 라운드 (Round 16)함수를 스와퍼가 없고 혼합기만 존재하도록 설계함
암호/복호화 알고리즘
- DES 암호화 과정에 대한 의사코드 나중에 확인하기!
라운드 키 생성기
라운드 키 생성 (Round-key Generator)
- 56비트 길이의 암호키를 입력으로 받아 48비트 길이의 라운드 키 16개를 생성함
- 라운드 키 생성기의 구성 요소
- 축소 P-박스에 의한 패리티 비트 제거
- 비트 이동 연산 (left)
라운드 키 생성기의 기본 구조
- 64비트 암호키 워드에 대한 패리티 비트 제거
- 축소 P-박스에 의해 수행됨
- 패리티 비트 제거 후 64비트의 암호키 워드는 56비트로 축소됨
- 28비트의 암호키 워드에 대한 순환 이동 비트량
- 각 라운드 별로 암호키 워드에 대한 순환 이동 비트 수가 다르게 정의됨
축소 치환 (P-박스)
- 56비트 워드를 최종적으로 48비트의 워드로 출력하기 위해 사용
- 48비트로 출력되는 워드는 한 라운드의 라운드 키로 사용
- 키 비트의 축소를 위한 P-박스 테이블
라운드 키 생성 의사코드 나중에 확인하기!
예제5) 16라운드 수행 예제
- 마지막 라운드를 제외한 나머지 모든 라운드에는 mixing, swapping 연산이 수행됨
- 특징
- 각 라운드의 출력 값의 오른쪽 부분은 다음 라운드의 출력 값의 왼쪽 부분과 동일함
- 마지막 라운드에는 스와퍼가 없으므로 R15가 L16이 되지 않고 그대로 R16이 됨
DES 설계 원리
쇄도 효과와 완비성 효과
- 블록 암호에서 요구되는 2가지 성질
- 쇄도 효과 (avalanche effect)
- 완비성 효과 (completeness effect)
쇄도 효과
- 평문(또는 키)에서 작은 변화가 암호문에서는 상당한 변화를 야기하는 것
완비성 효과
- 암호문의 각 비트는 평문의 많은 비트들에 의존할 필요가 있다는 것
- DES에서 P-박스와 S-박스에 의해 야기된 확산과 혼돈은 매우 강한 완비성 효과를 보여줌
DES의 설계 기준
S-박스
- 각 라운드로부터 그 다음 라운드까지 혼돈의 성질은 만족하게끔 설계
- 입력 값의 한 비트를 바꾸면 출력 값은 두 비트 이상이 변하도록 하여 확산의 성질을 만족함
- 비선형 함수로 설계
- S-Box 없으면 단순 xor 연산이므로 선형 연산이 됨
P-박스
- 32비트 입력에서 32비트 출력으로 가는 하나의 단순 P-박스와 32비트의 입력에서는 48비트의 출력으로 가는 하나의 확장 P-박스로 구성됨
- P-박스는 비트들을 동시에 확산시킴
라운드 수가 왜 16인가?
- DES에 대한 여러 공격을 통해 16라운드보다 작은 DES버전들은 전수 조사 공격보다 기지 평문 공격에 더 취약한 것으로 분석됨
