1 Chap 3. 관용 암호 방식 현대적 기법

2

3 목차  3.1 단순 DES  3.2 블록 암호 기법의 원리  3.3 DES  DES  DES 의 공격 방법  DES 작동 모드

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

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

6

7  기본 함수  IP (Initial Permutation) : 초기순열  함수 f K 전치 (transposition) 치환 (substitution)  SW : 데이터의 두 절반을 상호 교환하는 함수  함수 f K  IP -1 (Inverse Initial Permutation) : 초기 순열의 역인 순열 함수  암호화 / 복호화  Ciphertext = IP -1 (f K2 (SW(f K1 (IP(Plaintext)))))  Plaintext = IP -1 (f K1 (SW(f K2 (IP(Ciphertext)))))

8

9  키생성  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 입력 : 출력 : ex : Key( ) --> ( )

10  LS-1 : 1 비트 Circular Left Shift 연산 ex : (10001) --> (00011) 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) P

12

13

14  암호화 과정  입력 : 8 비트  출력 : 8 비트  IP( 초기 순열 ) 과 IP -1 ( 역 초기 순열 ) M = (IP -1 (IP(M)) IP 입력 : 출력 : IP -1 출력 :

15  함수 f K  전치 (transposition)  치환 (substitution)  입력 8 비트 L (Left most 4 bits) R (Right most 4 bits)  처리 f K = ( L XOR F( R, SK ), R ) SK (Sub Key = K1 or K2) 함수 F() 사용

16

17  E/P (Expansion/Permutation)  입력 : 4 비트  출력 : 8 비트  P4 E/P P

18  S-Box  입력 : 4 비트 ( )  처리 행 : 1 번째와 4 번째 비트 ( 1 0 ) 열 : 2 번째와 3 번째 비트 ( 0 1 ) S0S

19

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

21  10 개의 미지수 ( 키 ) 를 갖는 8 개의 비 선형 방정식 (p, c) 으로 나타낼 수 있음  (p 0,0, p 0,1, p 0,2, p 0,3 )=(a,b,c,d)  (p 1,0, p 1,1, p 1,2, p 1,3 )=(w,x,y,z)  4 비트 출력 = (q,r,s,t)  q=abcd+ab+ac+b+d  r=abcd+abd+ab+ac+ad+c S0

S0 S

블록암호 기법의 원리  스트림 암호와 블록 암호 기법  스트림 암호 기법 한번에 1 비트 혹은 1 바이트의 디지털 데이터 스트림을 암 호화 Vigenere 암호, Vernam 암호  블록 암호 기법 평문 블록 전체를 가지고 같은 크기의 암호문 블록을 생성 전형적으로 64 비트를 사용 스트림 암호보다 더 넓은 범위에 응용 가능 대부분의 네트워크 암호는 블록 암호 방식을 따름 Feistel 블록 암호 기법의 구조에 따름

24  Feistel 암호 구조의 유도  입력 : n 비트  출력 : n 비트  암호화가 역이 성립하기 위한 조건 Reversible Mapping PC Irreversible Mapping PC

25  N=4 일때 블록 치환 작은 블록으로 인해 취약 점 존재  적당한 크기의 n 설정 방법 크면 클수록 암호화 강도 는 높아짐 작으면 작을수록 구현과 성능 면에서는 좋음 => 적당한 암호학적 강도를 갖 고 구현이 용이할 정도의 크 기선택

26  Feistel 암호방식  적 (product) 암호의 개념을 이용하여 단순한 치환 암호를 개략 적으로 설계할 수 있음을 제안 적암호 : 두 개 이상의 기본 암호가 연속적으로 수행되도록 하여 어떤 요소의 암호방식보다 암호해독적으로 강하도록 하는 암호 개념  치환과 순열을 번갈아 수행하는 암호 방식의 사용을 제안  혼돈 (confusion) 함수와 확산 (diffusion) 함수를 번갈아 수행  현재 사용하고 있는 모든 중요한 대칭 블록 암호의 기본구조

27  확산과 혼돈  통계적 분석에 기초한 암호 해독 방지법 => Claude Shannon 에 의해 소 개된 방법 매우 이상적인 암호는 암호문에 대한 모든 통계적 정보가 사용된 키와 독립적이어야 한다.  확산 (diffusion) 평문의 통계적 구조가 암호문의 광범위한 통계 값에 분산되어 버 리는 방식 각 평문 숫자 (digit) 가 다수의 암호문 숫자 값에 영향을 주게 함으 로서 가능 예 > 문자 메시지 M = m 1 m 2 m 3 … 를 통하여 하나의 암호 문자 y n 을 생성하는 방식 y n = sum( 1 <= i <= k ) m n+i mod 26

28  혼돈 (confusion) 키를 발견하기 어렵게 하기 위한 방법 암호문에 대한 통계 값과 암호 키 값 사이의 관계를 가능한 복잡하게 만드는 것 복잡한 치환 알고리즘을 사용함으로 가능

29 Plaintext(2w bits) w bits XORF F F Ciphertext(2w bits) Round1 L0R0 L1R1 K1 Roundi LiLiRiRi KiKi Roundn LnLnRnRn KnKn Ln+1Rn+1 Feistel 암호구조

30  Feistel 암호 구조  왼쪽 반의 데이터에 치환 (substitution) 이 수행됨  치환 다음에는 데이터의 두 개의 반을 교환하는 순열 (permutation) 이 수행됨  S-DES 와 Feistel 의 차이점  알고리즘이 순열 함수로 시작되고 종료됨 IP IP -1

31  Feistel 네트워크의 매개변수  블록크기 : 64 비트의 블록 크기면 적당  키 크기 : 64 비트 또는 그 이하의 키 크기는 부적절하며 128 비 트가 일반적  반복 수 : 단일 과정은 보안에 부적절하지만 다중 반복 과정은 보안성을 증가시킴, 전형적인 반복 횟수는 16 회  서브키 생성 알고리즘 : 알고리즘이 복잡할수록 암호해독이 어려워짐  반복 함수 : 역시 함수가 복잡할수록 일반적으로 암호 해독에 더 강해짐

32 Plaintext(2w bits) w bits XORF LE0RE0 K1 XORF K2 RE1LE1 XORF LE14RE14 K15 XORF K16 RE15LE15 LE16RE16 LE16 Ciphertext(2w bits) Plaintext(2w bits) w bits K1 K2 K15 K16 XORF F F F LD0=RE16RD0=LE16 Ciphertext(2w bits) RD1=LE15LD1=RE15 LD2=RE14RD2=LE14 LD14=RE2RD14=LE2 RD15=LE1LD15=RE1 LD16=RE0RD16=LE0 LD16=RE0RD16=LE0

33  암호화 과정  LE16 = RE15  RE16 = LE15 XOR F(RE15,K16)  복호화 과정  LD1 = RD0 = LE16 = RE15  RD1 = LD0 XOR F(RD0,K16) = RE16 XOR F(RE15,K16) = LE15 XOR F(RE15,K16) XOR F(RE15,K16) XORF LE14RE14 K15 XORF K16 RE15LE15 LE16RE16 LE16 Ciphertext(2w bits) K15 K16 XORF F LD0=RE16RD0=LE16 Ciphertext(2w bits) RD1=LE15LD1=RE15 LD2=RE14RD2=LE14

34  암호화 i 번째 반복과정  LEi = REi-1  REi = LEi-1 XOR F(REi-1,Ki)  이에 대한 복호화 과정  REi-1 = LEi  LEi-1 = REi XOR F(REi-1,Ki) = REi XOR F(LEi,Ki) -> 복호화 그림에서 (i-1) 번째 복호결과를 만들기 위한 (i) 번째 입 력 형식 증명 XORF LE14RE14 K15 XORF K16 RE15LE15 LE16RE16 LE16 Ciphertext(2w bits) K15 K16 XORF F LD0=RE16RD0=LE16 Ciphertext(2w bits) RD1=LE15LD1=RE15 LD2=RE14RD2=LE14

35  특징  IBM 에서 Lucifer System 을 개선하여 만듬  1977 년 미 상무성의 국립 표준국 (NBS) 에서 표준 암호 알고리 즘으로 채택 FIBS PUB46  64 비트 블럭 암호 알고리즘  56 비트 키를 사용 64 비트 중 8 비트는 parity check 로 사용  기본 구조 round 수 : 16 round 복호화는 암호화의 역순  최근에는 DES 암호화를 세 개의 키로 세 번 반복함으로써 암 호의 강도를 높인 Triple-DES 를 사용 3.3 DES (Data Encryption Standard)

36  DES 의 역사  전용 암호시스템 : 타 그룹간의 통신에 불리 ==> 데이터 암호 화 표준이 필요  공개암호 표준 : 미국 연방 정부가 움직임  표준화 검토 (1972), 적합한 암호 알고리즘 조사  1973 년 5 월 : 암호방식 공모 (1 차 )  1974 년 8 월 : 2 차 공모 ==>IBM 이 요건을 갖춤 ==>NBS 가 요건을 NSP 에 의뢰

37  조사에 대한 요구 1. It must provide a high level of security. 2. It must be completely specified and easy to understand. 3. The security provided by the algorithm must not be based on the secrecy of the algorithm. 4. It must be all users and suppliers.

38  조사에 대한 요구 ( 계속 ) 5. It must be adaptable for use in diverse applications. 6. It must be economical to implement in electronic devices and be efficient to use. 7. It must be amenable to validation. 8. It must be exportable.

39  DES 의 역사 ( 계속 )  1975 년 ~1977: 일반 comment, 계약 체결  1977:NBS(NIST) 가 DES 를 표준 암호 알고리즘으로 채택  U.S.banks have been adopted DES  NBS postponed guarantee term of DES from till 1988 to till 1993  NSA proposed CCEP(Commercial COMSEC Endorsement Program; 상용 통신 안전 보증 계획 )instead of DES  U.S. bank expect to continue the use of DES

DES 암호화  DES 의 알고리즘의 일반적 모형 일반적 모형  평문 : 64bit  키 : 56bit + 8bit( 패리티 )  처리 단계  초기순열 단계 (IP)  16 라운드 반복  좌우 교환단계  역초기순열 단계 (IP -1 )

DES  DES 의 기본 구조 ( 데이타 암호화부 ) 입 력입 력입 력입 력 K1 K2 :::: 초기 치환 L0L0L0L0 L1L1L1L1 L2L2L2L2 R0R0R0R0 R1R1R1R1 R2R2R2R2 :::: f f R 16 L 16 f 역초기 치환 출 력출 력출 력출 력 K16 L i = R i-1 R i = L i-1 XOR f (R i-1, K i )

42  초기 치환 IP

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

44  f 함수의 구성도  8 개의 S-box 로 구성  각 S-box 는 6 비트 입력, 4 비트 출력 생성 R(32bit) 확장순열 E 48bit K (48bit) S1S2S8S7.. 치환 P 32 bit S-box table

45  확장순열  치환 P

46  S-box Table S 예 ) 비트 입력 행 (3 행 ) 열 (6 열 ) 진수 ‘1’ 를 4 비트로 출력 :

47  DES 의 기본 구조 ( 키 생성부 ) 키 순열선택 1 c0c0c0c0 좌측 시프트 c1c1c1c1 c2c2c2c2 c 15 좌측 시프트 d0d0d0d0 d1d1d1d1 d2d2d2d2 d 15 좌측 시프트 순열선택 2 K1 K2 K16 :::: :::: ::::

48  순열선택 1(PC1) 64 비트 -> 56 비트 C0, D0 : 각 28 비트  순열선택 2(PC2) 56 비트 ->48 비트 48 비트 키 출력 생성

49  쉬프트 스케줄 라운드 수 좌측 쉬프트 수

DES 복호화  서브키를 역순으 로 사용  암호화와 같은 알 고리즘 사용  Feistel 구조

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

52  DES 는 강한 쇄도 효과 (Avalanche Effet) 를 갖는다.  DES 에 관한 우려사항  미 정부의 채택이후 DES 의 보안 수준에 대한 우려가 지속. 알고리즘의 성질을 이용한 암호 해독의 가능성 – 예 ) s - box 의 약점에 대한 공격 가능성 주장 제기됨 그러나, 약점을 발견한 사람은 현재 존재 하지 않음 키 길이에 관한 우려 –Key Serarch Machine ( 기지 평문 공격 ) Cost Expected search Time $ 100,000 35hours $1,000, hours $10,000,000 21minutes

53 –Brute force Attack ; 1970 년대 /80 년대 --- low computing power 90 년대 --- high computing power – 미국 수출 허용 기준인 40 비트의 키 : Michael Wienerd 의 key search machine 으로 0.2 초만에 해독 가 능 Key size Number of One Encryption 10 6 Encryption Key size Number of One Encryption 10 6 Encryption Alternative Keys per micro sec per micro sec 32bits 2 23 = 4.3 * minutes 2.15ms 32bits 2 23 = 4.3 * minutes 2.15ms 56bits 2 56 = 7.2 * years 10.01h 56bits 2 56 = 7.2 * years 10.01h 128bits = 3.4 * years 5.4 * years 128bits = 3.4 * years 5.4 * years

DES 의 공격 방법  공격 방법  차분 암호 해독 (Differential Cryptanalysis) DES 에 적용해서 널리 알려짐 2 55 미만의 복잡도로 DES 를 해독 2 47 의 선택평문을 가지고 2 47 차수로 DES 를 해독  선형 암호 해독 (Linear Cryptanalysis) 2 47 기지 평문으로 해독가능 기지 평문이 선택 평문보다 구하기 쉽지만 DES 공격으로 서의 선형 암호 해독은 가능성이 없다. 선형 암호 해독의 타당성의 주장이 약하다.

DES 작동 모드 DES 작동 모드

56  ECB (Electronic Codebook) 모드의 특징  평문은 64 비트씩 처리  마지막 비트가 64 비트 미만이면 나머지 비트를 채운 후 진행  동일한 블록이 입력되면 암호문도 같다. --> 해독될 위험성이 있다.  중요 데이타가 같은 위치에 있을 때 취약블럭이 상호 결합하 지 않음 => 연속적인 블럭 암호화법 ; Chaining 기법

57  ECB (Electronic Codebook) 모드  암호화 DES 암호화 P1P1 C1C1 K DES 암호화 P2P2 C2C2 K DES 암호화 PNPN CNCN K... DES 복호화 C1C1 P1P1 K 4 복호화 DES 복호화 CNCN PNPN K DES 복호화 C2C2 P2P2 K...

58  CBC (Cipher Block Chaining) 모드의 특징  하나의 암호화 스텝의 출력을 사용하여 다음 입력으로 수정  각각의 암호 블럭은 서로 영향을 받음  선행하는 평문 블럭 전체에 좌우됨  C n : 모든 평문 블럭 P 1, P 2,..., P n 의 함수  암호화 : C n =E k (P n +C n-1 )  복호화 : Q n =D k (C n ) + C n-1 =P n  Padding  Self-Recovering 기능  첫번째 암호화에 적용할 IV 값은 송수신자가 미리 알아야 함  전송상의 암호문의 결함은 복호화 과정에서 오류 발생

59  CBC (Cipher Block Chaining) 모드  암호화 4 복호화 DES 복호화 C1C1 P1P1 K  DES 암호화 P2P2 C2C2 K  DES 암호화 PNPN CNCN K ... C N-1 DES 암호화 P1P1 C1C1 K  DES 복호화 C2C2 P2P2 K  DES 복호화 CNCN PNPN K  C N-1...

60  CFB (Cipher Feedback) 모드의 특징  문자의 길이 : m(1<m<64)  암호화 하기 위한 m 비트 : DES 출력의 m 비트  DES 알고리즘이 회선 양단에서 암호화로서 사용  Shift Register : 매번 새로운 비트로 교체  암호문은 선행하는 평문 모두의 함수  DES 를 스트림 암호 방식으로 사용

61  CFB (Cipher Feedback) 모드  암호화 64 비트 레지스터 DES 암호화 선택 j 비트 K  P1P1P1P1 C1C1C1C1 64 비트 레지스터 DES 암호화 선택 j 비트 K  P2P2P2P2 C2C2C2C2 64 비트 레지스터 DES 암호화 선택 j 비트 K  PNPNPNPN CNCNCNCN... C N-1 4 복호화 64 비트 레지스터 DES 암호화 선택 j 비트 K  P1P1P1P1 C1C1C1C1 64 비트 레지스터 DES 암호화 선택 j 비트 K  P2P2P2P2 C2C2C2C2 64 비트 레지스터 DES 암호화 선택 j 비트 K  PNPNPNPN CNCNCNCN... C N-1

62  OFB (Output Feedback) 모드의 특징  CBC, CFB 의 Error Extention 에 대한 응용  Vernam type  키 스트림 : 주기성이 있음  Feedback 의 출발 위치를 제외하고는 CFB 와 유사

63  OFB (Output Feedback) 모드 64 비트 레지스터 DES 암호화 선택 j 비트 K  P1P1P1P1 C1C1C1C1 64 비트 레지스터 DES 암호화 선택 j 비트 K  P2P2P2P2 C2C2C2C2 64 비트 레지스터 DES 암호화 선택 j 비트 K  PNPNPNPN CNCNCNCN... O N-1 64 비트 레지스터 DES 암호화 선택 j 비트 K  P1P1P1P1 C1C1C1C1 64 비트 레지스터 DES 암호화 선택 j 비트 K  P2P2P2P2 C2C2C2C2 64 비트 레지스터 DES 암호화 선택 j 비트 K  PNPNPNPN CNCNCNCN... O N-1 4 복호화 4 암호화

64