제3장 관용암호: 현대적 암호기법 2007. 9.

목 차 3.1 단순 DES (Simplified DES) 3.2 블록 암호 원리 (Block Cipher Principles) 목 차 3.1 단순 DES (Simplified DES) 3.2 블록 암호 원리 (Block Cipher Principles) 3.3 DES (Data Encryption Standard) 3.4 DES의 강점 (The Strength of DES) 3.5 차분 및 선형 암호 해독 (Differential and Linear Cryptanalysis) 3.6 블록 암호의 설계 원리 (Block Cipher Design Principles) 3.7 블록 암호의 운용 모드 (Block Cipher Modes of Operation) 2

3.1 Simplified DES 3.1.1 S-DES 개요 3.1.2 S-DES 키의 생성 3.1.5 S-DES와 DES 비교 3

3.1.1 S-DES 개요 (1/2) 알고리즘 알고리즘 구성 암호문 복호문 8비트 평문, 10비트 키 8비트 암호문 생성 초기순열(IP) 순열, 치환 이용 fk 순열 함수 SW 역 순열(IP-1) 암호문 IP-1(fk2(SW(fk1(IP(평문))))) 복호문 IP-1(fk1(SW(fk2(IP(암호문))))) 4

3.1.1 S-DES 개요 (2/2) 5

3.1.2 S-DES 키의 생성 (1/4) K1 = P8(Shift(P10(key))) K2 = P8(Shift(Shift(P10(key))) 그림 3.2 S-DES를 위한 키 생성 6

3.1.2 S-DES 키의 생성 (2/4) K1 = P8(Shift(P10(key))) 10 비트 키 = (k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) P10 = (k3, k5, k2, k7, k4, k10, k1, k9, k8, k6) P10 3 5 2 7 4 10 1 9 8 6 1 2 3 4 5 6 7 8 9 0 예 제 10 비트 key = ( 1 0 1 0 0 0 0 0 1 0 ) P10(key) = ( 1 0 0 0 0 0 1 1 0 0 ) 7

3.1.2 S-DES 키의 생성 (3/4) K1 = P8(Shift(P10(key))) (Shift(P10(key))): LS-1[키의1st 5비트] & LS-1[키의 2nd 5비트] 앞 다섯 비트와 뒤 다섯 비트 좌로 순환 이동(1트 좌측 순환이동) P10 =( k3, k5, k2, k7, k4, k10, k1, k9, k8, k6 ) Shift =( k5, k2, k7, k4, k3, k1, k9, k8, k6, k10 ) 예제) P10 = ( 1 0 0 0 0 0 1 1 0 0 ) LS-1 = ( 0 0 0 0 1 1 1 0 0 0 ) 1 2 3 4 5 6 7 8 9 0 8

3.1.2 S-DES 키의 생성 (4/4) K1 = P8(Shift(P10(key))) = P8(LS-1) P8(LS-1) = P8( 0 0 0 0 1 1 1 0 0 0 ) 10 비트에서 8비트 선택 치환 K1 = ( 1 0 1 0 0 1 0 0 ) K2 = P8(Shift(Shift(P10(key)))) = P8(Shift(LS-1)) = P8(LS-2) LS-2 = Shift(LS-1) : LS-1의 결과에 2비트 좌측 순환 이동 K2 = P8(LS-2) = P8( 0 0 1 0 0 0 0 0 1 1 ) = ( 0 1 0 0 0 0 1 1 ) 9

3.1.3 S-DES 암호 알고리즘 초기 및 최종 순열 함수 예제) 입력: 8비트 블록 평문 초기순열(IP) 최종 순열 IP-1(IP(X)) = X 예제) X = ( 1 0 1 1 0 0 1 1 ) IP(X) = ( 0 0 1 1 1 1 0 1 ) IP-1(IP(X)) = ( 1 0 1 1 0 0 1 1 ) 최종 순열 1 2 3 4 5 6 7 8 10

함수 fk (1/4) 순열, 치환 함수 조합 L( Left )  왼쪽 4비트 R( Right )  오른쪽 4비트 fk( L, R ) = (L  F( R, SK ), R ) F 함수(확장 순열) n n3 4 2 1 n4 평문 R: (n1, n2, n3, n4) 11

함수 fk (2/4) 8비트 서브키 K1 = (k11, k12, k13, k14, k15, k16, k17, k18) XOR S-Box n k 13 14 17 18 2 4 3 1 11 12 15 16 p 0,0 1,0 0,1 1,1 0,2 1,2 0,3 1,3 12

함수 fk (3/4) 예제) P = (0100 0111) 이라면 S0: 행 00, 열 10 ; 1/4 요소  행, 2/3 요소  열 S1: 행 01, 열 11 ; 5/8 요소  행, 6/7 요소  열 S0 = 11, S1 = 11 이 된다. (치환 효과) 13

함수 fk (4/4) P4 순열 P4출력은 함수 F의 출력이 된다. 스위치 함수(SW) fk는 왼쪽 4비트만 변경 두 번째 fk에서는 K2만 다름 14

3.1.4 S-DES의 분석 Brute-force 공격 가능 10비트 키 210= 1024 기지 평문/암호문 쌍 평문: ( p1, p2, p3, p4, p5, p6, p7, p8) 출력 암호문: ( c1, c2, c3, c4, c5, c6, c7, c8 ) 미지의 키: (k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) 기지 평문 공격: 각 ci는 pj와 kj의 다항식 함수햐 알고리즘은 10개의 미지수를 갖는 8개의 비선형 방정식 알고리즘에서 각각의 순열과 합 연산은 선형 사상 S박스를 통하여 비선형성을 도출 선형 사상 비선형 사상: 암호해독을 난해하게 하는 효과 15

3.1.5 S-DES와 DES 비교 단순 DES 표준 DES 8-비트 블록, 2단계 처리 64-비트 블록, 16단계 처리 IP-1 · fk2 · SW · fk1 · IP (평문) IP-1 · fK16 · SW · fK15 · SW · … … · SW · fK1 IP(평문) 10비트 키 2개 8-비트 서브키 생성 키 56비트 16개의 48-비트 서브키 생성 F 함수는 4비트 연산 F함수는 32비트 연산 4행 4열의 2개의 S 박스 사용 4행 16열의 8개의 S박스 사용 16

3.2 블록암호 기법의 원리 3.2.1 스트림 암호와 블록 암호 기법 3.2.2 Feistel 암호 구조의 유도 확산과 혼돈 암호 구조 복호 알고리즘 17

3.2.1 스트림 암호와 블록 암호 기법 스트림 암호 한번에 1비트 혹은 1 바이트 Vigenere 암호, Vernam 암호 평문 블록 전체(64비트 – 전형적) 다양한 작동모드 사용 스트림 방식에 비해 응용 범위 넓음 대부분 네트워크 기반 관용 암호 방식에 사용 18

3.2.1 스트림 암호와 블록 암호 기법 일반 블럭 암호 스트림 암호 평문: M=m1m2m3… 암호문: C= EK(m1) EK(m2) EK(m3)… 암호 알고리즘 n 비트 평문 암호문 m 비트 키 평문: M=m1m2m3… 암호문: C= EZ1(m1) EZ2(m2) EZ3(m3)… 초기값 이진 키수열 이진 평문 수열 일반 블럭 암호 스트림 암호 19

3.2.2 Feistel 암호 구조의 유도 n비트 블록처리: n비트 평문을 입력으로 n비트 암호문 출력 4비트입력을 치환에 의하여 16개 값 중 하나 대응 4비트 출력 20

3.2.3 Feistel 암호 방식 (1) 두 개 이상의 기본 암호 연속적 수행 확산과 혼돈 치환, 순열 반복 수행 확산과 혼돈 클로디 샌노(Claude Shannon)가 소개 통계적 분석에 기초한 암호 해독 방지 Shannon: “매우 이상적인 암호는 암호문에 대한 모든 통계적 정보가 사용된 키와 독립적이어야 한다.” 21

3.2.3 Feistel 암호 방식 (2) 확산(diffusion) 평문의 통계적 구조가 암호문에 광범위하게 분산(평문과 암호문 관계 복잡) 각 평문 숫자가 다수의 암호문 숫자 값에 영향 yn = mn+i (mod 26) ; M = m1, m2, m3, … :문자 메시지 혼돈(confusion) 암호문의 통계적 구조와 암호 키 값 사이의 관계 복잡 키를 이용한 암호문 생성 방법 복잡( 키 추론 어려움) 22

3.2.3 Feistel 암호 방식 (3) 평문(2w) 암호문(2w) LE0(w) RE0(w) LEi(w) REi(w) LEn–1(w) REn–1(w) LEn(w) REn(w) f K1 K i K n 그림 3.5 고전 Feistel 구조 23

Feistel 암호 구조 Feistel 암호 구조 Feistel 암호의 반복 구조 길이 2w 비트인 평문 블록(L0, R0) 분할 처리 K로부터 유도된 n개의 키(Ki) 사용 n회의 동일한 반복 구조 실행 Feistel 암호의 반복 구조 오른 쪽 반 R0에 반복 함수 F 적용 반복 서브키 K1 적용(K  Ki) 왼쪽 반 L0와 XOR(치환 작용) 좌우 양쪽 결과를 교환(순열 작용) 24

Feistel 암호 구조 Feistel 암호 특성 블록 크기(64비트) 키 크기(128비트) 반복 수 서브키 생성 알고리즘 큰 블록은 보안 강화하지만 암/복호 속도는 저하 암/복호 속도를 고려 64비트 일반적 키 크기(128비트) 큰 키는 보안 강화 하지만 암/복호 속도는 저하 암/복호 속도고려 128비트 일반적(64비트 이하 해독 용이) 반복 수 다중 반복과정은 보안성 강화 16회 반복이 일반적 서브키 생성 알고리즘 서브키 생성 방법이 복잡할수록 강력 반복함수 적용되는 반복함수가 복잡할수록 강력 25

Feistel 복호 알고리즘 암호화 마지막 반복 복호화 과정 LE16 = RE15 RE16 = LE15  F(RE15, K16) 복호화 과정 암호화과정의 역 순서 처리 첫 반복 LD1 = RD0 = LE16 = RE15 RD1 = LD0  F(RD0, K16) = RE16  F(RE15, K16) = [LE15  F(RE15, K16)] F(RE15, K16) = LE15 26

Feistel 복호 알고리즘 A  B  B = A 복호화 과정 i 번째 반복 과정은 LEi = REi-1 REi = LEi-1  F(REi-1, KI) 역으로 정리하면 REi-1 = LEi LEi-1 = REi  F(REi-1, Ki) = REi  F(LEi, Ki) 그림에서 ( i-1 ) 번째 복호결과 위한 ( i )번째 입력형식 증명 A  B  B = A 27

3.3 표준 DES 3.3.1 DES 암호화 초기 순열 단일 반복 처리 과정 키 생성 3.3.2 DES 복호화 3.3.3 쇄도 효과 28

3.3 표준 DES DES (Data Encryption Standard) 공모 1차 1973년 NBS(현 NIST) 공개 모집 2차 1974년 NBS 공개 모집 IBM Tuchman, Meyer 응모 1977년 FIPS-46 등록 1983, 1988, 1993년 안전성 검토 29

3.3 표준 DES 특징 64비트 블럭 암호 알고리즘 56비트 키를 사용 64비트 중 8비트는 parity check로 사용 기본 구조 round 수 : 16 round 복호화는 암호화의 역순 최근에는 강도를 높인 3중 DES(Triple-DES)를 사용 30

3.3 표준 DES 동작 원리 암호화 복호화 : 암호화를 역으로 하면 된다. 평문 64비트 블록 M 초기 치환 IP IP(M) IP-1(F(IP(M)))=C 64비트 블록 M 평문 IP(M) F(IP(M)) 암호문 16회전 Feistel 연산 초기 치환 IP 역치환 IP-1 31

3.3.1 DES 암호화 암호화 평문 M(64) 역전치 IP –1 LE0(32) RE0(32) LE1(32) RE1(32) K1 K2 K3 f 초기전치 IP 암호문 C(64) K16 암호화 32

3.3.1 DES 암호화 초기전치 IP (initial permutation) 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 33

3.3.1 DES 암호화 역전치 IP –1 (inverse of initial permutation) 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 34

DES의 기본 구조 (단일 반복 과정) 35

f 함수 8개의 S-box로 구성, 각각 6비트 입력, 4비트 출력 생성 36

f 함수 확대전치 E : 32  48 32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 37

f 함수 평형전치 P 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 38

f 함수 S-Box b1 b2 b3 b4 b5 b6 b1 b6 : row b2 b3 b4 b5 : column S1 Sb1 Sb2 Sb3 Sb4 S1-Box table Sb1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 7 39

f 함수 S-Box 예 1 0 1 0 1 1 b1 b6 : row b2 b3 b4 b5 : column S1 1 0 0 1 1 0 1 0 1 1 1 0 0 1 b1 b6 : row b2 b3 b4 b5 : column 1 : row 3 0 1 0 1 : column 5 S1-Box table Sb1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 7 40

DES의 키 생성 키 생성 구조 키 (64) C0(28) D0(28) LS1 C1(28) D1(28) LS2 C2(28) PC2 K1 PC1 K2 K16 41

DES의 키 생성 전치 PC-1 8, 16, 24, 32, 40, 48, 56, 64 제거 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 42

DES의 키 생성 축약전치 PC-2 9, 18, 22, 25, 35, 43, 54 제거 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 43

DES의 키 생성 키 스케쥴러 LS 위치 시프트 LS1 1 LS9 LS2 LS10 2 LS3 LS11 LS4 LS12 LS5 44

3.3.2 DES 복호화 서브키 역순 사용 암호화와 같은 알고리즘 사용 Feistel 구조 45

3.3.2 DES 복호화 복호화 과정 LD0 = RE16 = LE15  f (RE15, K16) RD0 = LE16 = RE15 LD1 = RD0 = LE16 = RE15 RD1 = LD0  f (RD0, K16) = RE16  f (RD0, K16) = LE15  f (RE15, K16)  f (LE16, K16) = LE15  f (RE15, K16)  f (RE15, K16) = LE15 LD16 = RE0 RD16 = LE0 46

3.3.3 쇄도 효과(Avalanche Effect) 평문이나 키의 작은 변화가 암호문에 대하여 중요한 변화 발생 47

3.4 DES의 강점 3.4.1 56 비트 키 사용에 대한 우려 미정부 채택 후 DES의 보안 수준에 대한 우려가 지속. 3.4.1 56 비트 키 사용에 대한 우려 미정부 채택 후 DES의 보안 수준에 대한 우려가 지속. 알고리즘의 성질을 이용한 암호 해독의 가능성 키 길이에 관한 우려 Key Search Machine ( 기지 평문 공격 ) Cost Expected search Time $ 100,000 35 hours $1,000,000 3.5 hours $10,000,000 21 minutes 48

3.4 DES의 강점 Brute force Attack 키크기 키의 수 1암호화 106암호화 미국 수출 허용 기준인 40비트의 키 키크기 키의 수 1암호화 106암호화 32bits 232 = 4.3 * 109 35.8 minutes 2.15ms 56bits 256 = 7.2 * 1016 1142 years 10.01h 128bits 2128 = 3.4 * 1038 1024 years 5.4 * 1018 years 49

3.4.2 DES 알고리즘의 성질에 대한 우려 DES 알고리즘 자체 성질을 이용한 해독 가능성 8개의 치환 표 또는 S-box 알고리즘의 설계기준에 대한 비공개. S-box약점 인지 공격자 해독 가능성 의혹 제기 S-box의 수많은 정규성과 예측 못할 동작이 발견 S-box에 대하여 치명적인 약점을 발견한 사람 없다. 그러한 발견이 공개된 적은 아직까지 없다. 50

3.5 차분 및 선형 암호 해독 3.5.1 차분 암호 해독 (Differential Cryptanalysis) DES에 적용해서 널리 알려짐 255 미만의 복잡도로 DES를 해독 247의 선택평문을 가지고 247 차수로 DES를 해독 3.5.2 선형 암호 해독 (Linear Cryptanalysis) 247 기지 평문으로 해독가능 기지 평문이 선택 평문보다 구하기 쉽지만 DES공격으로서의 선형 암호 해독은 가능성이 없다. 선형 암호 해독의 타당성이 약하다. 51

3.7 블록 암호의 운용 모드 52

3.7.1 전자 코드북(ECB) 전자 코드북 (ECB : Electronic Codebook) 모드 메시지를 64비트 블록 단위로 나누어 처리 각 64비트 평문 64비트 암호문 코드 북 유사 마지막 평문 블록< 64비트 이면 나머지 비트를 채움 동일한 블록이 입력되면 암호문도 동일 안전성 저해 요소 메시지가 긴 경우는 동일한 블록이 출현할 확률 증가 메시지가 항상 정규화 된 필드로 시작시 해독위험 53

3.7.1 전자 코드북(ECB) 54

3.7.2 암호 블록 연결(CBC) 암호 블록 연결(CBC : Cipher Block Chaining) 모드 앞 단계의 암호문 출력 다음 암호단계의 입력에 반영됨 동일한 평문 블록이 입력되어도 상이한 암호문 생성효과 암호문: Cn = Ek (C n-1  Pn ) 복호화: Dk (Cn) = Dk [ Ek (C n-1  Pn ) ] = (C n-1  Pn ) Pn = C n-1  Dk (Cn) = C n-1  (C n-1  Pn ) = Pn 암호화에 적용할 IV 값은 송수신자가 미리 인지 필요 IV는 키와 동등하게 보호시작에 ECB로 암호화하여 전송가능 기밀성 외에 인증목적으로 활용가능 전송상에서 암호문의 결함은 복호화 과정에 오류 발생 55

3.7.2 암호 블록 연결(CBC) 56

3.7.3 암호 피드백(CFB) J비트 암호 피드백CFB) 모드 DES는 본질적으로 블록 암호 방식 CFB 또는 OFB모드를 사용하여 스트림 암호방식 전환가능 스트림 암호방식은 블록이 64비트 정수배가 되도록 패딩 불필요 CFB는 문자지향 스트림 암호화 형식으로 실시간 작동가능 8-비트 문자 전송경우 8비트 단위로 암호화 전송 암호화 과정(전송단위를 j비트로 가정, 일반적으로 j=8) 첫번째 암호과정 입력: IV로 초기화된 64비트 이동 레지스터 키를 적용하여 64비트 전체 암호화 좌측 j 비트를 평문의 첫 단위 P1 과 XOR 한 결과가 암호문 C1 암호문 C1 은 다음 단계의 암호화를 위하여 레지스터의 우측에 J비트 입력 전송중의 비트 오류가 전체적으로 전파 57

3.7.3 암호 피드백(CFB) 58

3.7.3 암호 피드백(CFB) 59

3.7.4 출력 피드백(OFB) 전송중의 비트 오류는 해당 암호단위 하나에 제한 CFB보다 메시지 스트림 변조공격에 취약 암호문의 연계성 부족원인 암호문 변조와 오류 검출부를 동시 조작가능 키 스트림: 주기성이 있음 Feedback의 출발 위치를 제외하고는 CFB와 유사 60

J비트 출력 피드백(OFB)모드 61

J비트 출력 피드백(OFB)모드 62