5장. 현대 대칭키 암호 소개 경일대학교 사이버보안학과 김현성 교수

목차 5.1 현대 블록 암호 5.2 현대 스트림 암호

5.1 현대 블록 암호 한번에 n-비트 평문 블록을 암호화/복호화 암호/복호 알고리즘은 동일한 k-비트 비밀키를 사용 평문이 n 비트보다 크면 분할, 작으면 n 비트가 되도록 패딩 보통, n = 64, 128, 256, 512비트 등 암호/복호 알고리즘은 동일한 k-비트 비밀키를 사용 복호 알고리즘은 암호 알고리즘의 역함수 연산의 단위가 문자가 아니라 비트로 수행

고전암호 vs 현대암호 contemporal traditional

5.1 현대 블록 암호 (계속) [예제 5.1] 만약 인코딩 과정에서 8-비트 ASCII 코드를 이용하고 64-비트 블록 암호를 이용하여 암호화하기를 원한다면, 100개의 문자로 구성된 메시지는 몇 비트가 덧붙이기(패딩) 되어야 하는가? [풀이] 100개의 문자를 8-비트 ASCII 코드로 인코딩 하면 800-비트의 메시지가 된다. 평문은 64로 나누어져야만 한다. 만약 |M|와 |Pad|를 각각 메시지 길이와 덧붙이기 길이라고 한다면 다음을 만족한다.

5.1 현대 블록 암호 (계속) Data padding

5.1 현대 블록 암호 - 대치와 전치 현대 블록 암호 대치(Substitution) 암호와 전치(Transposition) 암호를 조합하여 동작하도록 설계 현대 블록 암호는 전수조사 공격에 안전하기 위하여 대치 암호를 사용하여 설계 전치 암호로만 설계되었다면 평문과 암호문에서 0과 1의 개수가 동일하게 됨 암호문과 0과 1의 개수가 동일한 평문에 대해서만 전수조사하여 대응하는 평문을 찾아낼 수 있음

5.1 현대 블록 암호 – S-DES DES (Data Encryption Standard) 단순 DES IBM에서 Lucifer System을 개선하여 만듬 1977년 미 상무성의 국립 표준국(NBS)에서 표준 암호 알고리즘으로 채택 64비트 블럭 암호 알고리즘 56비트 키를 사용 64비트 중 8비트는 parity check로 사용 기본 구조 round 수 : 16 round 복호화는 암호화의 역순 단순 DES 교육용 알고리즘 Santa Clara 대학의 Edward Schaefer 개발 8비트 평문 블럭 과 10비트 키를 사용

Simplified DES

5.1 현대 블록 암호 – S-DES 기본 함수 암호화/복호화 IP (Initial Permutation) : 초기순열 함수 fK 전치(transposition) 치환(substitution) SW : 데이터의 두 절반을 상호 교환하는 함수 IP-1 (Inverse Initial Permutation) : 초기 순열의 역인 순열 함수 암호화/복호화 Ciphertext = IP-1(fK2(SW(fK1(IP(Plaintext))))) Plaintext = IP-1(fK1(SW(fK2(IP(Ciphertext)))))

Key Generation

5.1 현대 블록 암호 – S-DES 키생성 S-DES는 10-bit Key를 사용 두개의 8-bit sub key 생성 P10( k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) =( k3, k5, k2, k7, k4, k10, k1, k9, k8, k6) P10 입력 : 1 2 3 4 5 6 7 8 9 10 출력 : 3 5 2 7 4 10 1 9 8 6 ex : Key(1010000010) --> (1000001100)

5.1 현대 블록 암호 – S-DES LS-1 : 1비트 Circular Left Shift연산 P8 ex : (10001) --> (00011) P8 입력 : 10비트 출력 : 8비트 P8( k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) =( k6, k3, k7, k4, k8, k5, k10, k9) P8 6 3 7 4 8 5 10 9

1 0 0 1 0 0 1 1 1 0 1 2 3 4 5 6 7 8 9 10 3 5 2 7 4 10 1 9 8 6 0 0 0 1 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 2 3 4 5 6 7 8 9 10 6 3 7 4 8 5 10 9 1 1 1 1 1 0 0 0 1 1 0 0 0 1 0 0 1 1 1 2 3 4 5 6 7 8 9 10 6 3 7 4 8 5 10 9 1 0 0 0 0 0 1 1 Key Generation

Simplified DES

Simplified DES Data Encryption

5.1 현대 블록 암호 – S-DES 암호화 과정 입력 : 8비트 출력 : 8비트 IP(초기 순열)과 IP-1(역 초기 순열) M = (IP-1(IP(M)) IP 입력 : 1 2 3 4 5 6 7 8 출력 : 2 6 3 1 4 8 5 7 IP-1 출력 : 4 1 3 5 7 2 8 6

5.1 현대 블록 암호 – S-DES 함수 fK 전치(transposition) 치환(substitution) 입력 8비트 L (Left most 4 bits) R (Right most 4 bits) 처리 fK = ( L XOR F( R, SK ), R ) SK (Sub Key = K1 or K2) 함수 F() 사용

5.1 현대 블록 암호 – S-DES E/P (Expansion/Permutation) 입력 : 4비트 출력 : 8비트 P4 4 1 2 3 2 3 4 1 P4 2 4 3 1

5.1 현대 블록 암호 – S-DES S-Box 입력 : 4비트 ( 1 0 1 0 ) 처리 입력 : 4비트 ( 1 0 1 0 ) 처리 행 : 1 번째와 4번째 비트 ( 1 0 ) 열 : 2 번째와 3번째 비트 ( 0 1 ) S0 S1 1 2 3 1 2 3

5.1 현대 블록 암호 – S-DES S-DES분석 Brute force 공격 가능 암호해독 가능 10비트 키로 단지 2^10 = 1024 가지의 가능성 암호해독 가능 기지 평문 공격 : 단일평문과 그 출력 암호문이 알려져 있을때 10개의 미지수(키)를 갖는 8개의 비 선형 방정식(p, c)으로 나타낼 수 있음 => 공격 가능

5.1 현대 블록 암호 – S-DES 10개의 미지수(키)를 갖는 8개의 비 선형 방정식(p, c)으로 나타낼 수 있음 (p0,0, p0,1, p0,2, p0,3)=(a,b,c,d) (p1,0, p1,1, p1,2, p1,3)=(w,x,y,z) 4비트 출력 = (q,r,s,t) q=abcd+ab+ac+b+d r=abcd+abd+ab+ac+ad+c+1 S0 1 2 3

5.1 현대 블록 암호 – S-DES 다음을 S-DES를 이용하여 암호하시오 평 문 : “k” 암호키 : 511(10진수)

S0 S1 1 2 3 1 2 3 3 5 2 7 4 10 1 9 8 6 2 6 3 1 4 8 5 7 6 3 7 4 8 5 10 9 4 1 2 3 2 3 4 1 6 3 7 4 8 5 10 9 2 4 3 1 4 1 3 5 7 2 8 6

과제물 단순 DES 의 암호화/복호화 단순 DES 프로그래밍 입력 제출방법 : A4에 손으로 암호화 과정 및 복호화 과정 평문 : 본인의 영문 이름 키 : 본인의 학번 끝에서 3자리 사용(예 : 10 0110 0001) 제출방법 : A4에 손으로 암호화 과정 및 복호화 과정 단순 DES 프로그래밍

5.1 현대 블록 암호 한번에 n-비트 평문 블록을 암호화/복호화 암호/복호 알고리즘은 동일한 k-비트 비밀키를 사용 평문이 n 비트보다 크면 분할, 작으면 n 비트가 되도록 패딩 보통, n = 64, 128, 256, 512비트 등 암호/복호 알고리즘은 동일한 k-비트 비밀키를 사용 복호 알고리즘은 암호 알고리즘의 역함수 연산의 단위가 문자가 아니라 비트로 수행

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 현대 블록암호 확산과 혼돈과 같은 성질을 만족시키기 위하여 전치요소(P-박스로 불림)와 대치요소(S-박스로 불림)와 그 밖의 구성 요소들(XOR, Shift, Swap 등)을 결합하여 설계

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) P-Box 문자 단위로 수행하였던 고전 전치 암호를 비트 단위로 수행 세 종류 단순(Straight) P-박스 확장(Expansion) P-박스 축소(Compression) P-박스

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 단순 P-박스 (Straight P-Box) n-비트를 입력 받고 n-비트를 출력하는 치환 함수 n! 개의 대응이 존재

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 단순 P-박스 (계속) [예제 5.5] 3×3 P-박스의 6가지 가능한 모든 경우의 대응 P-박스는 보통 키가 없으며 그 대응은 사전에 정의됨 만일 P-박스가 소프트웨어로 구현된다면 치환테이블로 구현되며, 테이블의 성분 값은 입력값을 뜻하고 각 성분의 위치는 출력값

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 단순 P-박스 (계속) [표 5.1] n이 64인 단순 P-박스에 대한 치환 테이블의 예 64개의 성분을 가지며 64개의 입력값에 대응하고, 성분의 위치는 출력값에 대응 첫 번째 값은 58이기 때문에 첫 번째 비트 출력값은 58번째 비트 입력 값임

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 축소 P-박스 (Compression P-Box) n-비트를 입력 받아 m-비트를 출력하는 P-박스 (n > m) 입력 비트 중 특정 비트는 소실 키가 사용되지 않으며 비트를 전치하기 위한 규칙은 치환 테이블로 정의

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 축소 P-박스 (계속) [표 5.2] 32×24 축소 P-Box의 예 7, 8, 9, 16, 23, 24, 25번째 입력 값은 소실

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 확장 P-박스 (Expansion P-Box) n-비트를 입력 받아 m-비트를 출력하는 P-박스 (n < m) 특정 입력 비트는 한 개 이상의 출력 비트와 연결 키가 사용되지 않으며 전치 비트에 대한 규칙은 치환 테이블로 정의

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 확장 P-박스 (계속) 확장 P-박스에 대한 테이블은 m개의 성분을 가지며 m-n개의 성분이 반복적으로 사용 [표 5.3] 확장 P-박스에 대한 테이블의 예 1, 3, 9, 12번째 입력 값은 두 개의 출력 값으로 대응

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) P-Box의 역함수 존재성 (Invertibility) 단순 P-박스는 역함수가 존재 축소 P-박스와 확장 P-박스는 역함수가 존재하지 않음

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) P-Box의 역함수 존재성 (계속) [예제 5.7] 다음은 1차원 테이블로 표현된 치환 테이블의 역을 어떻게 구성하는지를 보여줌

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) P-Box의 역함수 존재성 (계속) [그림 5.7] 역함수가 존재하지 않는 축소 P-박스와 확장 P-박스

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) P -Box에 대한 프로그래밍?

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) P -Box에 대한 프로그래밍? 입력 출력 처리 1 1 입력/출력에 대한 표현법? 하나의 변수 or 배열

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) P -Box에 대한 프로그래밍(배열) 선언 int in[6] = { 0, 0, 1, 0, 1, 0 } int out[6] = { 0, 0, 0, 0, 0, 0 } int pbox[6] = { 0, 2, 5, 4, 1, 3 } 처리 for (i=1; i<=5; i++) out[i] = in[pbox[i]];

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) P -Box에 대한 프로그래밍(하나의 변수) 선언 int in =10; int out = 0; int pbox[6] = { 0, 2, 5, 4, 1, 3 } 처리 어떻게 원하는 위치의 비트값을 찾을 수 있는가? 찾은 비트값을 어떻게 원하는 위치에 놓을 수 있는가?

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) P -Box에 대한 프로그래밍(하나의 변수) 정수 변수의 크기 ? 4 bytes in =10 원하는 비트의 위치 찾기 ? 끝에서 3번째 비트 오른쪽으로 2번 쉬프트 정수값 1과 and, or, xor ? 0000 0000 0000 1010 10 0000 0000 0000 0010 0000 0000 0000 1010 0000 0000 0000 0101 AND 0000 0001 0000 0000

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 5 4 3 2 1 5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 5 4 3 2 1 P -Box에 대한 프로그래밍(하나의 변수) 선언 int in =10; int out = 0; int pbox[6] = { 0, 4, 1, 2, 5, 3 } 처리 for (i=1; i<=5; i++){ temp = in >> (pbox[i]-1); temp = temp & 1; temp = temp << (5-i); out = out ^ temp; }

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) S-Box S-박스는 대치 암호 S-박스는 입력과 출력의 개수가 달라도 됨 S-박스는 m×n 대치 단위, 단 m과 n이 같을 필요는 없음 S0 S1 1 2 3 1 2 3

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) S-Box (계속) [예제 5.8] 다음은 3-비트를 입력 받아 2-비트를 출력하는 S-박스임 a1,1 = a1,2 = a1,3 = a2,1 = 1, a2,2 = a2,3 = 0 이기 때문에, 위의 S-박스는 선형 위 관계식은 행렬로 표현 가능

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) S-Box (계속) [예제 5.9] 다음은 3-비트를 입력받아 2-비트를 출력하는 S-박스임 여기서 곱과 덧셈은 GF(2)에서 정의됨 입력 값과 출력 값 사이에 선형 관계식이 존재하지 않으므로 위의 S-박스는 비선형임

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) S-Box (계속) [예제 5.10] 다음 표는 3×2의 S-박스에 대한 입출력 관계식을 정의 입력 값의 왼쪽 최상위 비트는 열을 정의하고 입력 값의 오른쪽 하위 두 비트는 열을 정의 출력 두 비트는 선택된 열과 행이 교차되는 성분의 값임 입력이 010이면 01이 출력되고, 입력 101은 출력 00을 출력

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) S-Box의 역함수 존재성 (Invertibility) S-박스는 입력 값과 출력 값 사이의 관계가 테이블 혹은 수학적 관계로 정의되는 대치암호 S- 박스는 역함수가 존재할 수도 있고, 존재하지 않을 수도 있음 역함수가 존재하는 S-박스는 입력 비트와 출력 비트의 개수가 동일

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) S-Box의 역함수 존재성 (계속) [예제 5.11] 다음 그림은 역함수가 존재하는 S-박스의 예를 보여줌 왼쪽은 암호 알고리즘에서 사용되고, 오른쪽은 복호 알고리즘에서 사용 입력 값의 왼쪽 최상위 비트는 행을 정의하고 ,다음 두 비트는 열을 정의 출력은 입력 값의 열과 행이 교차되는 값

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) S-Box에 대한 프로그래밍 입력 출력 처리 비트열 1 비트열 1 S0 S1 1 2 3 1 2 3

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) S0 1 2 3 5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) S-Box에 대한 프로그래밍 선언 int s0[4,4] = {1, 0, 3, 2, 3, 2, 1, 0, 0, 2, 1, 3, 3, 1, 3, 2} 처리 입력을 통해 어떻게 행의 조합을 찾을 수 있는가? 입력을 통해 어떻게 열의 조합을 찾을 수 있는가? => Shift, AND, XOR

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) S0 1 2 3 5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) S-Box에 대한 프로그래밍 int s0[4,4] = {1, 0, 3, 2, 3, 2, 1, 0, 0, 2, 1, 3, 3, 1, 3, 2} int in = 7; int row, col; int out; 행 계산 (7(10)=> 0111(2)) row = in; row = (row >> 3) << 1; row = row ^ (in & 1); 열 계산 col = in; col = col & 6; col = col >> 1; 결과값 out = s0[row][col];

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 배타적 논리합(Exclusive-OR) 현대 블록암호에서 중요한 구성요소 체 GF(2n) 상에서의 덧셈과 뺄셈 연산은 배타적 논리합(XOR)으로 불리는 단일 연산에 의하여 수행됨 체 GF(2n) 상에서의 배타적 논리합 연산의 다섯 가지 성질은 이 연산이 블록 암호에 사용될 경우 매우 흥미로운 구성요소임을 보여줌 닫힘(closure) 결합법칙(associativity) 교환법칙(commutativity) 항등원의 존재성(existence of identity) 역원의 존재성(existence of inverse)

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 배타적 논리합의 역(Inverse)

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 순환 이동(Circular Shift) 현대 블록 암호에 주로 사용되는 또 다른 구성요소는 순환이동 연산(circular shift operation) [그림 5.10] 8 비트 워드에서의 왼쪽 혹은 오른쪽 순환이동

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 스왑(Swap) 스왑 연산(swap operation)은 k = n/2인 순환이동 연산의 특수한 경우이다. [그림 5.11] 8 비트 워드에서의 스왑 연산

5.1 현대 블록 암호 - 현대 블록암호의 구성요소 (계속) 분할과 결합(Split and Combine) 특정 블록 암호에서 발견되는 또 다른 두 개의 연산은 분할과 결합임 [그림 5.12] 8 비트 워드에서의 분할 연산과 결합 연산

5.1 현대 블록 암호 - 합성 암호 합성 암호(product cipher) Shannon에 의해 소개된 개념 대치, 치환, 그리고 기타의 구성요소들을 결합한 복합적인 암호 설계된 블록 암호가 확산과 혼돈 성질을 갖도록 하는 것

5.1 현대 블록 암호 - 합성 암호 (계속) 확산(Diffusion) 혼돈(Confusion) 암호문과 평문 사이의 관계를 숨김 통계 테스트를 사용해 암호문에 대한 평문을 찾고자 하는 공격을 어렵게 함 암호문의 각각의 비트나 문자가 평문의 모든 비트나 특정 비트에 의하여 종속적으로 결정되도록 함 즉, 평문의 단일 비트가 바뀐다면, 암호문에 있는 특정 비트나 모든 비트가 바뀌게 함 혼돈(Confusion) 암호문과 키의 관계를 숨김 암호문을 이용하여 키를 찾고자 하는 공격을 어렵게 함 키의 단일 비트가 변하면 암호문의 거의 모든 비트들이 변하게 함

5.1 현대 블록 암호 - 합성 암호 (계속) 라운드(Rounds) 확산과 혼돈은 각 S-박스, P-박스, 기타 구성 요소들의 결합을 의미하는 합성 암호를 반복적으로 사용하여 얻어짐 이때, 반복적으로 사용되는 합성 암호를 ‘라운드’라 함 각 라운드 키로부터 키 스케줄 또는 키 생성 알고리즘을 통하여 생성된 서로 다른 라운드키(서브키)를 사용 각 라운드에서 생성되는 값을 ‘중간 상태 값(middle text)라 함

5.1 현대 블록 암호 - 합성 암호 (계속) [그림 5.13] 두 라운드로 구성된 합성 암호

5.1 현대 블록 암호 - 합성 암호 (계속) [그림 5.14] 블록 암호의 확산과 혼돈

5.1 현대 블록 암호 - 합성 암호 (계속) 라운드 (계속) 실제 암호시스템에서 확산과 혼돈을 향상시키기 위하여 더 큰 데이터 블록, 더 많은 S-Box, 더 많은 라운드를 사용 암호문을 더욱 난수처럼(유사난수) 되게 함 암호문과 평문 사이의 관계를 더욱 알아내기 힘들게 함(확산) 라운드 수의 증가는 라운드 키의 개수를 증가시키고, 결과적으로 암호문과 키의 관계를 찾기 어렵게 함(혼돈)

S-DES 프로그래밍 S0 S1 1 2 3 1 2 3 3 5 2 7 4 10 1 9 8 6 2 6 3 1 4 8 5 7 6 3 7 4 8 5 10 9 4 1 2 3 2 3 4 1 6 3 7 4 8 5 10 9 2 4 3 1 4 1 3 5 7 2 8 6

5.1 현대 블록 암호 – 두 종류의 합성 암호 현대 블록 암호 => 합성 암호 Feistel 암호 역함수가 존재하는 구성요소와 역함수가 존재하지 않는 구성요소 모두를 사용하여 설계 예) DES Non-Feistel 암호 단지 역함수가 존재하는 구성요소만을 사용하여 설계 예) AES

5.1 현대 블록 암호 – 두 종류의 합성 암호(계속) Feistel 암호 Feistel이 매우 지적이고 흥미로운 암호를 설계 세 가지 타입의 구성요소로 구성 자기 자신을 역으로 갖는 것(self-invertible) 역함수가 존재하는 것(invertible) 역함수가 존재하지 않는 것(noninvertible) 역이 존재하지 않은 구성요소를 결합하고, 암호 알고리즘과 복호 알고리즘에서 동일한 구성요소를 사용

5.1 현대 블록 암호 – 두 종류의 합성 암호(계속) Feistel 암호 (계속) 초기 구조 어떻게 역이 존재하지 않은 구성요소로 설계한 암호 알고리즘과 복호 알고리즘이 서로 역관계가 될 수 있는가? 기본아이디어 암호알고리즘에서 역함수가 존재하지 않는 구성요소의 효과가 복호화 알고리즘에서 상쇄되도록 함 예) 배타적 논리합(XOR)을 사용

5.1 현대 블록 암호 – 두 종류의 합성 암호 (계속) Feistel 암호 (계속) 초기 구조 (계속) 암호화 : C1 = P1  f(K) 복호화 : P2 = C2  f(K) = P1  f(K)  f(K) = P1 Feistel 구조에서 믹서는 자기 자신을 역함수로 갖음

5.1 현대 블록 암호 – 두 종류의 합성 암호 (계속) Feistel 암호 (계속) 초기 구조에 대한 향상 함수의 입력을 키와 평문으로 복합적으로 구성 이를 위해 평문을 두 부분으로 나눔 암호 알고리즘과 복호 알고리즘은 여전히 서로 역관계 R4 = R3 = R2 = R1 L4 = L3  f(R3, K) = L2  f(R2, K) = L1  f(R1, K)  f(R1, K) = L1

5.1 현대 블록 암호 – 두 종류의 합성 암호 (계속) Feistel 암호 (계속) 최종 구조 이전 버전은 평문의 오른쪽이 암호화되지 않음 스와퍼(swapper)를 추가하여 각 라운드의 왼쪽과 오른쪽을 교환 두 라운드로 구성 두 개의 라운드 키 K1, K2를 사용하며, 복호화에서는 역순으로 사용

5.1 현대 블록 암호 – 두 종류의 합성 암호 (계속) Non-Feistel 암호 역함수가 존재하는 요소만을 사용하여 설계 암호화를 구성하는 각 요소는 복호화를 구성하는 각 요소에 대응됨 예) S-Box는 적절하게 동일한 입출력 개수를 가져야 함 축소 혹은 확장 P-Box는 역함수가 존재하지 않기 때문에 사용할 수 없음 평문이 반씩 분할될 필요 없음

5.1 현대 블록 암호 – 두 종류의 합성 암호 (계속) Non-Feistel 암호 (계속) XOR, 역이 존재하는 2 x 2 S-Box, 역이 존재하는 단순 P-Box 만을 구성요소로 이용 복호화에는 라운드 키를 역순으로 이용

5.1 현대 블록 암호 – 블록 암호에 대한 공격 현대 블록 암호에 대한 공격 고전 암호의 공격들이 사용될 수 있음 대부분의 공격에 대하여 안전 예로, 키 사이즈가 매우 크기 때문에 키 전수조사 공격에 안전 최근 블록 암호의 구조에 기반한 새로운 공격 방법들이 개발됨 차분 분석 선형 분석

5.1 현대 블록 암호 – 블록 암호에 대한 공격 (계속) 차분 분석(Differential Cryptanalysis) Eli. Biham과 Adi. Shamir에 의해 소개됨 선택 평문 공격을 이용 Eve는 Alice의 컴퓨터에 어떤 방법으로든 접근하여 자신이 선택한 평문에 대한 암호문을 획득함 이 공격의 목적은 Alice의 암호화 키를 찾아내는 것 분석 순서 알고리즘 분석 선택 평문 공격의 시작 키 값의 추측

5.1 현대 블록 암호 – 블록 암호에 대한 공격 (계속) 차분 분석 – 1) 알고리즘 분석 먼저 암호 알고리즘을 분석해야 함 특정 암호는 Eve가 키를 알지 못해도 평문의 차분과 암호문의 차분 사이의 관계를 찾을 수 있는 구조적 취약점을 갖음 [예제 5.13] 암호가 단지 배타적 논리합 연산으로만 구성된다고 가정하자. 키의 값을 알지 못하더라도, 평문의 차분을 P1 Å P2 으로 정의하고 암호문의 차분을 C1 Å C2으로 정의하면, Eve는 평문 차분과 암호문의 차분 사이의 관계를 쉽게 발견할 수 있다. 다음은 C1 Å C2 = P1 Å P2를 증명한다.

5.1 현대 블록 암호 – 블록 암호에 대한 공격 (계속) 차분 분석 – 1) 알고리즘 분석 (계속) [예제 5.14] 예 5.13에 S-박스를 추가해보자. X1과 X2의 차분과 P1과 P2의 차분을 이용 X1  X2 = P1  P2

5.1 현대 블록 암호 – 블록 암호에 대한 공격 (계속) 차분 분석 – 1) 알고리즘 분석 (계속) [예제 5.14] (계속) Eve는 암호가 각 평문의 차분에 대하여 얼마나 많은 암호문 차분을 발생시키는지(확률적 관계)를 분석하기 위해 다음 표를 만듦 [표 5.4] 예 5.14의 암호에 대한 입·출력 차분

5.1 현대 블록 암호 – 블록 암호에 대한 공격 (계속) 차분 분석 – 1) 알고리즘 분석 (계속) [예제 5.15] 예 5.14의 결과는 다음 차분 분포표와 같이 Eve에게 확률적 정보를 제공한다. S-Box의 구조적 취약점 때문에 각 성분의 확률이 균일한 분포를 따르지 않음을 보여줌

5.1 현대 블록 암호 – 블록 암호에 대한 공격 (계속) 차분 분석 – 2) 선택 평문 공격의 시작 Eve는 공격을 위해 필요한 평문의 차분을 선택 Eve는 차분 확률 분포표를 참조해 가장 높은 확률을 갖는 평문의 차분을 선택할 수 있다. 차분 분석 – 3) 키 값의 추측 Eve는 키 값을 추측하기 위하여 선택한 특정 평문과 암호문 쌍을 찾음 선택 암호문 공격을 통하여 암호문 C로부터 평문 P가 생성되도록 수행

5.1 현대 블록 암호 – 블록 암호에 대한 공격 (계속) 차분 분석 (계속) [예제 5.16] 표 5.5를 통하여, Eve는 0.5(50%)의 확률로 P1 Å P2 = 001이면, C1 Å C2 = 11 을 만족함을 알 수 있다. Eve는 암호문 C1 = 00 에 대한 평문 P1 = 010 을 얻는다(선택 암호문 공격). 또한, 암호문 C2 =11 에 대한 평문 P2 = 011 을 얻는다(또 다른 선택 암호문 공격). 두 쌍을 이용하여, 역으로 분석을 시도한다. 위 두 개의 분석을 통하여 K = 011 이거나 K =101임을 확인할 수 있다.

5.1 현대 블록 암호 – 블록 암호에 대한 공격 (계속) 블록 암호에 대한 차분 분석은 S-박스의 비 균일 차분 분포표에 기반한다. 좀 더 자세한 차분 분석은 부록 N에 제시한다.

5.1 현대 블록 암호 – 블록 암호에 대한 공격 (계속) 선형 분석(Linear Cryptanalysis) 1993년 Mitsuru Matsui에 의하여 소개 알려진(기지) 평문 공격을 이용 [그림 5.20] 선형 S-박스를 갖는 간단한 암호

5.1 현대 블록 암호 – 블록 암호에 대한 공격 (계속) 선형 분석 (계속) 3개의 미지수에 대한 해를 구하면, 다음을 만족한다. 위 수식을 통하여 3 번의 기지 평문 공격으로 k0, k1, k2 의 값을 알 수 있다.

5.1 현대 블록 암호 – 블록 암호에 대한 공격 (계속) 선형 분석 (계속) 실제 블록 암호 위와 같이 간단하지 않음 더 많은 구성요소들을 복합적으로 사용 S-Box는 선형이 아님

5.1 현대 블록 암호 – 블록 암호에 대한 공격 (계속) 선형 근사식(Linear Approximation) 현대 블록 암호에서 S-박스는 완전한 선형함수가 아님 S-Box는 특정 선형함수에 의해 확률적으로 근사적으로 될 수 있음 n 비트 평문과 암호문, m 비트 키가 주어지면, 다음 형태를 갖는 수식을 찾을 수 있음 단 1 ≤ x ≤ m, 1 ≤ y ≤ n, 1 ≤ z ≤ n 을 만족 가로챈 평문과 암호문의 비트는 키를 찾기 위하여 사용될 수 있음 각 수식은 확률 1/2 +  으로 만족 (는 편차) 이 큰 수식은 이 작은 수식보다 더 효과적임 좀 더 자세한 선형 분석은 부록 N에 제시

5.2 현대 스트림 암호 현대 스트림 암호 암호화와 복호화는 동시에 r 비트를 생성 평문 비트 스트림, 암호문 비트 스트림, 키 비트 스트림을 각각 P = pn…p2 p1, C = cn…c2 c1, K = kn…k2 k1 라 할 때(pi, ci, ki는 r-비트 워드) 암호화 ci = E(ki, pi), 복호화 pi = D(ki, ci)

5.2 현대 스트림 암호 (계속) 현대 스트림 암호 (계속) 특징 종류 블록 암호보다 속도가 빠름 하드웨어 구현이 블록 암호보다 용이 이진 스트림 단위의 암호화가 필요하고 고정된 속도로 암호화된 데이터를 전송하고자 할 때 스트림 암호는 더없이 좋은 선택 전송 도중 비트의 변조에 강인 키 스트림 K = kn … k2 k1 를 어떻게 생성하는지가 현대 스트림 암호의 주된 관심 종류 동기식 스트림 암호 (Synchronous Stream Ciphers) 비동기식 스트림 암호(Nonsynchronous Stream Ciphers)

5.2 현대 스트림 암호 - 동기 스트림 암호 동기식 스트림 암호 (Synchronous Stream Ciphers) 키 스트림은 평문 혹은 암호문과 독립 즉, 키는 평문/암호문과 어떤 관계도 없이 생성되고 사용됨

5.2 현대 스트림 암호 - 동기 스트림 암호 (계속) One-time pad 가장 간단하고 안전한 동기식 스트림 암호 Gilbert Vernam에 의해 설계되고 특허화됨 실제적으로 사용되기 매우 어려움 Alice가 Bob에게 키 스트림을 전달할 수 있는 안전한 채널이 존재해야 하므로, 구현이 불가능

5.2 현대 스트림 암호 - 동기 스트림 암호 (계속) [예제 5.17] 다음 경우 각각에 대하여 one-time pad 암호의 암호문의 패턴은 무엇인가? a. 평문이 n개의 0으로 구성되는 경우 b. 평문이 n개의 1로 구성되는 경우 c. 평문이 0과 1로 교차되어 구성되는 경우 d. 평문이 랜덤 스트림 비트인 경우

5.2 현대 스트림 암호 - 동기 스트림 암호 (계속) [예제 5.17] (계속) [풀이] a. 0 Å ki = ki 이므로, 암호문 스트림은 키스트림과 같다. 만약 키 스트림이 랜덤하다면, 암호문 또한 랜덤하다. 평문의 패턴은 암호문에서 유지되지 않는다. b. ki 를 ki 의 보수라고 할 때, 1 Å ki = ki 이므로 암호문 스트림은 키 스트림의 보수와 같다. 만약 키 스트림이 랜덤하다면, 암호문 또한 랜덤하다. 다시 말하자면, 평문의 패턴은 암호문에서 유지되지 않는다. c. 이 경우, 암호문 스트림의 각 비트는 키 스트림에 대응되는 비트와 같거나 보수이다. 그러므로 키 스트림이 랜덤하다면 평문 또한 랜덤하다. d. 이 경우, 두 개의 랜덤 비트에 대하여 배타적 논리합 연산을 수행하였으므로 암호문은 완전하게 랜덤하다.

5.2 현대 스트림 암호 - 동기 스트림 암호 (계속) 귀환 쉬프트 레지스터(Feedback Shift Register: FSR) One-time pad의 절충안 소프트웨어와 하드웨어 환경에서 모두 구현될 수 있지만, 하드웨어 구현이 더욱 용이 Shift 레지스트와 귀환(feedback) 함수로 구성

5.2 현대 스트림 암호 - 동기 스트림 암호 (계속) 귀환 쉬프트 레지스터 (계속) 선형 귀환 쉬프트 레지스터(LFSR) bm은 b0, b1, …, bm-1의 선형 함수 f의 결과임 예) bm = cm-1bm-1 + … + c2b2 + c1b1 + c0b0 (c0 ≠ 0) bm = cm-1bm-1  …  c2b2  c1b1  c0b0 (c0 ≠ 0) 와 동일

5.2 현대 스트림 암호 - 동기 스트림 암호 (계속) [예제 5.18] b5 = b4 Å b2 Å b0 을 만족하고 5개의 셀을 갖는 선형 귀환 쉬프트 레지스터를 설계하라. 만약 ci = 0이면 bi는 bm의 계산에 어떠한 영향도 주지 않는다. 즉, bi가 귀환 함수에 연결되지 않음을 뜻한다. 만약 ci = 1이면, bi 는 bm 의 계산에 영향을 준다. 예를 들어 c1 과 c3 가 0이라면, 귀환 함수에 단지 세 개의 셀만이 연결되는 것을 뜻한다. 그림 5.24는 물음에 만족하는 선형 귀환 쉬프트 레지스터를 보여준다. [그림 5.24] 예 5.18에 대한 LFSR

5.2 현대 스트림 암호 - 동기 스트림 암호 (계속) [예제 5.19] b4 = b1 Å b0을 만족하고 4개의 셀을 갖는 선형 귀환 쉬프트 레지스터를 설계하라. 만약 seed가 (0001)2일 때, 20번의 변환에 대한 출력 값을 보여라. [그림 5.25] 예 5.19에 대한 LFSR

5.2 현대 스트림 암호 - 동기 스트림 암호 (계속) [예제 5.19] (계속) [표 5.6] 예 5.19에 대한 셀 값과 키 수열

5.2 현대 스트림 암호 - 동기 스트림 암호 (계속) [예제 5.19] (계속) [표 5.6] 예 5.19에 대한 셀 값과 키 수열

5.2 현대 스트림 암호 - 동기 스트림 암호 (계속) [예제 5.19] (계속) 키 스트림이 100010011010111 10001…임을 알 수 있다. 언뜻 보기에 이 수열은 난수열처럼 보이지만, 만약 좀 더 키 스트림을 생성하면 키스트림이 주기를 갖는 것을 알 수 있다. 아래에 보이는 바와 같이 15비트가 반복한다: LFSR에 의하여 생성된 키 스트림은 수열이 N 비트 이후에 반복되는 의사난수열이다. LFSR의 최대 주기는 2m − 1이다.

5.2 현대 스트림 암호 - 동기 스트림 암호 (계속) [예제 5.20] 예 5.19에서의 LFSR에 대한 특성 다항식은 원시 다항식인 (x4 + x + 1)이다. 표 4.4(4장)는 이 다항식이 기약 다항식임을 보여준다. 이 기약 다항식은 또한 e = 23 − 1 = 7인 (x7 + 1) = (x4 + x + 1) (x3 + 1)을 나눈다.

5.2 현대 스트림 암호 - 동기 스트림 암호 (계속) 귀환 쉬프트 레지스터 (계속) 선형 귀한 쉬프트 레지스터 (계속) LFSR에 대한 공격 LFSR의 구조를 알고 있다면, Eve는 가로챈 n 비트 암호문의 분석을 통하여 미래의 암호문을 모두 예측할 수 있음 LFSR의 구조를 모른다면, Eve는 암호를 깨기 위하여 2n 비트의 알려진 평문 공격을 이용할 수 있음

5.2 현대 스트림 암호 - 동기 스트림 암호 (계속) 귀환 쉬프트 레지스터 (계속) 비선형 귀한 쉬프트 레지스터(NLFSR) 비선형 함수를 사용하여 안전한 스트림을 암호를 설계할 수 있음 간단한 비선형 함수의 예 b4 = (b3 AND b2) OR (b1 AND ~b0) NLFSR 을 설계하기 위한 수학적 기초지식이 알려져 있지 않기 때문에 NLFSR이 널리 사용되지는 않음 LFSR과 NLFSR의 결합 선형과 비선형 구조를 결합하여 사용 가능

5.2 현대 스트림 암호 - 비동기 스트림 암호 비 동기식 스트림 암호 (Nonsynchronous Stream Ciphers) 키 스트림의 각 비트는 이전의 평문이나 암호문에 종속적으로 결정됨(8장)