1 Chap 7. 암호 알고리즘

2 목 차목 차 1. MD5 메시지 다이제스트 알고리즘 2. 안전한 해쉬 알고리즘 3. 국제 데이터 암호 알고리즘 (IDEA) 4. SKIPJACK 5. LUC 공개키 암호

3 1. MD5 메시지 다이제스트 알고리즘 MIT 의 Ron Rivest 에 의해 개발 (RSA 개발자 중의 한사람 ) MD5 로직 – 입력 : 임의의 길이의 메시지 – 출력 : 128 비트 메시지 다이제스트 5 단계로 구성

4 그림 7.1 MD5 를 이용한 메시지 다이제스트 생성 페딩 (1-512bit) 메시지 길이 (K mod 2 64 ) L Y 512bits = N Y 32bits K bits 메시지 Y 0 Y Yq Y L ABCD HMD5 HMD5 128bit HMD5 HMD5 128bit digest

5 1 단계 : 패딩 비트 부가 – 패딩비트 범위 : 비트 – 하나의 1 과 원하는 길이의 0 으로 패딩 – 메시지가 원하는 길이일 지라도 패딩은 항상 부가 2 단계 : 부가된 길이 – 본래 메시지에 64 비트가 첨가 –1, 2 단계에 의해 길이가 512 비트의 정수배가 되는 메시지를 얻음 3 단계 : MD 버퍼의 초기화 – 버퍼의 용도 : 해수함수의 중간과 최종 결과 보관 – 버퍼 : 버퍼는 4 개의 32 비트 레지스터 (A,B,C,D) 로 표현 – 레지스터들은 다음과 같은 16 진수의 값으로 초기화 A = B = 89ABCDEF C = FEDCBA98D =

6 4 단계 : 512(16 단어 ) 블럭의 메시지 처리 입력 : 512 비트 블럭, 128 비트 버퍼값 (A,B,C,D), 사인 함수로 구성되는 64 비트 요소. Algorithm : 4 개의 라운드 처리로 구성된 모듈 같은 함수구조를 가지면서 서로 다른 기약함수에 의존 테이블중에 각 라운드마다 1/4 를 사용 T[i] 에서 i 번째 요소는 2 32 * abs(sin(i)) 의 정수 부분과 일치 압축 함수 : F(U,V,W) = (U  V) V (~U  W) G(U,V,W) = (U  V) V (U  ~W) H(U,V,W) = U+V+W I (U,V,W) = V+ V (U  ~W) 3 개의 32 비트단어를 입력으로 취하고 하나의 32 비트 단어 출력

7 5 단계 : 출력 512 비트 입력으로 128 비트 출력이 나옴 단계 연산 설명 - ABCD 에서 16 단계 처리 계열로 구성 A := B + CLS S (A+G(B,C,D) + X[k] + T[i]) A,B,C,D : 버퍼의 4 단어 G : 기약 함수 F,G,H,I 의 하나 CLS S : 32 비트에서 s 비트 순환 좌측 쉬프트 ( 로테이션 ) X[K] : 메시지의 q 번째 512 비트 블럭에서 k 번째의 32 비트 단어 T[i] : 행렬 T 에서 i 번째 32 비트 단어 + : 법 2 32 의 덧셈

8 32 비트 단어 배열 는 현재 처리되고 있는 512 비트 블럭값을 가진다. 입력의 각 32 비트 32 비트 단어는 라운드마다 한 번씩 4 번 사용되고, 의 64 개 의 32 비트 단어 요소의 각각은 정확히 한번 사용된다. 각 단계에 대하여 버퍼의 4 바이트중 하나만이 갱신. 각 바이트는 라운드 동안 16 번 갱신.

9 [PIC3. MD5 의 기본 동작 ] ABCD G + + X[k] + T[i] CLS S +

10 MD4 해쉬함수 출력 : 128 비트 입력 : 512 비트 메시지 블럭 (16 개의 32 비트 워드 ) 과 상수 초기값 : IV0= EFCDEAB89 98BADCFE 패딩 : 패딩은 (512 의 배수 - 64) 가 될 때까지 한다. 추가 패딩 : 메시지의 길이의 64 비트 표현으로 남은 64 비트를 채운다. 상수 : K1 = 5A827999, K2 = 6ED9EBA1 압축 함수 : F(U,V,W) = (U  U)V(~ U  W) G(U,V,W)= (U  U)V(~U  W)V(V  W) H(U,V,W) = U+V+W 단계 연산 :FF(a,b,c,d,Z,s) | a := (a + F(b,c,d) + Z)<<s FF(a,b,c,d,Z,s) | a := (a + F(b,c,d) + Z)<<s

11 MD4 와 MD5 의 차이점 비교  MD4 는 16 단계의 3 라운드를 사용하나, MD5 는 16 단계의 4 라운드를 사용한다.  MD4 는 각 라운드에서 한 번씩 3 개의 기약함수를 사용한다. 그러나 MD5 는 각 라운드에서 한번씩 4 개의 기약 논리 함수를 사용한다.  MD5 의 각 단계는 이전 단계의 결과에 부가된다.

12 2. 안전한 해쉬 알고리즘 (SHA, SHS) 출력 : 160 비트 해쉬 입력 : 512 비트 메시지 블럭과 상수 초기값 : A= B=EFCDAB89 C=98BADCFE B= E=C3D2E1F0 패딩 : 패딩은 (512 의 배수 - 64) 가 될 때까지 한다. 추가 패딩 : 메시지의 길이의 64 비트 표현으로 남은 64 비트를 채운다. 상수 :0 t 19 Kt = 5A t 39 Kt = 6ED9EBA1 40 t 59 Kt = 8F1BBCDC 60 t 79 Kt = CA62C1D6 압축함수 : F(U,V,W) = (U  V) V(~U  W) (0<=t<=19) G(U,V,W) = U+V+W (20<=t<=39,60<=t<=79) H(U,V,W) = (U  V) V (U  W) V (V  W) (40<=t<=59)

13 단계 연산 FF(a,b,c,d,e,Xt,Kt) | a := (a <<5 + F(b,c,d)+e+Xt+Kt) b := a c := b <<30 d := c e := d GG(a,b,c,d,e,Xt,Kt) | a := (a <<5 + G(b,c,d)+e+Xt+Kt) b := a c := b <<30 d := c e := d HH(a,b,c,d,e,Xt,Kt) | a := (a <<5 + H(b,c,d)+e+Xt+Kt) b := a c := b <<30 d := c e := d

14 SHA 해쉬함수 [PIC. SHA 를 이용한 메시지 다이제스트 ] 패딩 (1-512bit) 메시지 길이 (K) Ly 512bits = Ny 32bits K bits 메시지 Y0 Y Yq Y L ABCDE H SHA H SHA 160bit H SHA H SHA 160bit digest

15 [PIC 2. 단일 512 비트 블럭의 SHA 처리 ] Yq(512bit) MDq(160bit) ABCDE ROUND 0 (ABCDE, Yq, K 0 ABCDE ROUND 1 (ABCDE, Yq, K 1 : ABCDE ROUND 79 (ABCDE, Yq, K bit MD q +1

16 [PIC. SHA 기본 동작 ] ABCDE f 1 + CLS W T CLS 30 + K T A B CDE

17 SHA 와 MD5 의 차이점 비교 양쪽 다 MD4 로부터 나왔기 때문에, SHA 와 MD5 는 서로 아주 유사하다. 따라서 그들의 강도와 특성도 비슷하다. MD5 와 SHA 의 비교 MD5 SHA 다이제스트 128 비트 160 비트 처리의 기본단위 64(16 번의 4 라운드 ) 80 최대 메시지 크기 무한대 2 64 기약 논리 함수 4 3 덧셈 상수 64 4

18 3. IDEA(International Data Encryption Alg.) Xuejia Lai, James Massey( 스위스 연방 기술 기관 ) DES 를 대치하기 위한 알고리즘의 하나 가장 성공적인 DES 의 대치 알고리즘 – 대부분의 암호 공격으로부터 안전 – 널리 사용됨 (PGP 에 포함 ) 설계 원리 – 블록암호 : 64 비트 블록 / 128 비트 키 – 강한 강도 – 쉬운 구현

19 암호학적 강도 블록 길이 : 64 비트 ( 통계적 분석 방지 가능 ) 키 길이 : 128 비트 ( 전사적 공격에 안전 ) Confusion ( 혼돈 ) – 암호문의 통계적 성질과 평문의 통계적 성질의 관계를 난해하게 만 드는 성질 –IDEA 는 세가지 연산을 사용하여 confusion 을 달성 –DES 에서는 이러한 성질을 XOR 연산과 비선형 s-box 에 의존 Diffusion( 확산 ) – 각각의 평문 비트와 키 비트는 모든 암호문 비트에 영향을 주어야 한 다. – 이것은 평문의 통계적 구조를 감출 수 있다. –IDEA 는 효율적인 확산을 지원한다.

20 IDEA 의 Confusion / Diffusion Confusion : 세가지 연산을 이용 –XOR, 2 16 (mod 65535) 상에서의 덧셈, 곱셈 – 각각 , +, 로 표기 –XOR 에만 의존하는 DES 보다 암호해독이 어려움 Diffusion – 곱셈 / 덧셈 (MA) 구조에 의해 제공 입력 : 평문에서 유추된 두개의 16 비트, 키에서 유추된 두개의 16 비트 서브키 출력 : 두개의 16 비트 결과 – 효율적인 확산을 위해 8 번 반복

21 곱셈 / 덧셈 (MA) 구조 F1F1 F2F2 Z5Z5 Z6Z6 G1G1 G2G2

22 IDEA 암호화 입력 : 64 비트 평문, 128 비트 키 / 출력 : 64 비트 암호문 8 라운드 입력을 4 개의 16 비트 서브블럭으로 분해 각 라운드는 4 개의 서브 블록을 입력으로 받고, 4 개의 16 비트 결 과물을 생성 모든 서브키는 초기 128 비트 키에서 생성 – 총 52 개의 서브키가 사용됨

23 IDEA 전체 구조 Round 1 Round 2 64bit 평문 … Z1Z1 Z6Z6 … Z7Z7 Z 12 Round 7 출력 변환 … Z1Z1 Z6Z6 … Z7Z7 Z 비트 암호문 Y 서브키 생성기 128 비트 키 Z Z1Z1 Z

24 Round 1 네개의 서브키 (Z 1 ~ Z 4 ) 네개의 입력 블록 (X 1 ~X 4 ) 덧셈, 곱셈연산을 이용해서 키와 입력 블록을 조합 ( 변환과정 ) 조합된 결과를 XOR 두번째와 세번째의 결과 교환 (Confusion 증가 및 차분해독에 견딜 수 있는 성질 )

25 출력 변환 1 라운드의 맨 처음 처리과정과 동일한 단계 즉, 8 라운드의 끝 부분에서 교환을 하지 않은 것과 동일 – 암호화 / 복호화가 동일한 구조를 가지기 위함

26 IDEA 동작 모드 DES 와 유사한 4 가지 동작 모드 ECB –64 비트의 각 평문 블록이 독립적으로 암호화 – 작은 블록의 데이터 암호화에 유용 CBC – 평문의 다음 64 비트와 암호문의 이전 64 비트에 대한 XOR – 같은 64 비트 평문이라도 매번 다른 암호문 생성 CFB – 입력은 한번에 J 비트로 처리 – 이전 암호문은 의사난수 (pseudo random) 값 생성을 위한 입력으로 사용되고, 다 음 평문과 XOR OFB(Output feedback) – 이전 IDEA 의 결과를 입력으로 사용 – 잡음이 있는 채널에서의 스트링 전송에 유효

27 4. SKIPJACK 1993 년 4 월 클린턴 행정부 “ 법 시행의 합법적 필요성을 허 용하는 범위 내에서 전화 통화의 보안성과 프라이버시를 향상 시키기 위한 연방 정부의 참여 ” 선언 합법적인 전자적 감시를 통해 사회를 보호하면서도 국가의 다른 이해관계와 충돌하지 않는 안전체계를 제공하려함. Clipper Project 암호를 사용하는 개인 통화 내용의 감청 허용 DES 보다 강한 암호 알고리즘 비공개 사용은 자유 선택

28 Clipper I ( ) 민간 부분의 암호장비 사용을 가능케 함으로써 개인적인 커뮤니케이션을 보호하는 동시에 정부가 적법한 절차에 의할 때 복호화키에 대한 접근권을 갖음 알고리즘 : SKIPJACK( 비공개 ) 전화 통화에 대한 도청 (wiretap), H/W 적 구현 1 년의 comment 시기 : NIST 가 EES(Encrypted Escrow Standard) 로 표준 (FIPS - 185) 키 위임 정책에 대한 반대 의견 : 민간 privacy 침해, 키 위임을 선호하지 않음 Clipper 에 대한 반대 의견 (Diffie 등 ) : 알고리즘의 비공개 : trapdoor 의 존재 가능성 : NSA 가 주도 : H/W 의존성 : 비용, 호환성 문제

29 Clipper II ( ) 상업적 키 위임 (Commercial key escrow) 법집행 능력의 유지가 아님 키 손질에 따른 데이타 복원 키 보관을 민간 기관도 가능 암호장비 수출 규제에 대한 산업계의 반발 40 비트키 64 비트 이하의 키 ( 키 위임 포함 ) S/W 적으로도 실현 가능한 방식으로 함 민간 부분의 동의를 얻지 못함 ; Clipper Chip : 키 사이즈 80 비트 수출 제한 완화와 키 위임을 결합

30 Clipper III ( ) 공개키 암호 방식의 중요성 인식 키 관리 기반 (KMI, Key Management Infrastructure) 방식 도입 CA (Certification Authority) PAA (Policy Approving Authority) 키 위임기관이 필요 키 관리와 키 위임이 결합 PKI 의 개념과 상이 위임기관의 기준에 대한 언급 결여 키 위임의 강제성이 강화

31 Clipper IV ( ) White House 가 Key escrow 의 최신 버젼을 공포 Key escrow Key recovery 수출 규정 완화 56 비트 암호 시스템의 수출 허용 향후 2 년간 ( 단, key escrow 시스템 개발 ) 그 이후는 금지 관장기관이 State Department 에서 Commerce Department 로

32 SKIPJACK Interactive block cipher 블럭 사이즈 : 64 비트, 키 사이즈 : 84 비트 ECB, CBC, OFB, CFB 모드 사용 가능 32 라운드 1985 ~ 1990 ( NSA ) Capstone ( MYK - 80 ) NSA 에서 개발 Skipjack algorithm (ECB, CBC, CFB, OFB 모드 사용 ) Public - key Exchange Algorithm (Diffie - Hellman Scheme) Digital Signature Algorithm Secure Hash Algorithm For secure electronic commerce and other computer - based application

33 Clipper chip 평가 (by NIST) 민간인 5 명 (Denning, Brckell, 등 ) 30 ~ 40 년간 Exhaustive Search 의 우려가 없음 Shortcut attack 으로 skipjack 이 해독될 우려는 없음 Skipjack 의 안전성은 알고리즘의 비공개와 무관

34 SKIPJACK K F UID A KU A Chip KSKSKSKS K F UID A KU A Chip KSKSKSKS 협약된 세션키 M E K S [M] 암호화된 메시지 법 시행필드 (LEAF) E K F [UID A || E KU A (K S ) || P A ] 법 시행 복호기 UID A E K 1 (KU A 1 ) UID A E K 2 (KU A 2 ) 에스크로우 기관 1 에스크로우 기관 2 DD+DDD K1K1K1K1 K2K2K2K2 M 가로챔 KU A KSKSKSKS E KU A (K S ) A 키 요소 요구 송신자 A 의 안전장치송신자 B 의 안전장치 M 메시지

35 매개 변수 K F = 80 비트 집단키. 집단으로 지정된 모든 장치들에 저장. 그것은 LEAF 를 만드는데 사용된다. UID = 특별한 SKIPJACK 칩에 대한 유일한 식별자 KU = 장치 유일키. 칩과 함께 암호화된 모든 메시지를 푸는데 사용되는 특별한 SKIPJACK 칩에 대한 유일한 암호화 키 KU 1, KU 2 = 키 요소의 쌍. 다음의 항등식을 가진다. KU = KU 1 KU 2 K 1, K 2 = 암호화 비밀키 K S = 세션키 P A = 인증코드. LEAF 가 인정되지 않은 방법으로 비뀌거나 수정되지 않았다는 것을 확신하는데 사용되는 LEAF 에서의 필드 LEAF( 법 시행 필드, Law Enforcemnet Field) = E K F (UID A II EKU A (K S ) II P A )

36 Clipper Mechanism 법 시행 기관 1. 키 구성 요소를 복원한다. KU A 1 = DK 1 [E K 1 (KU A 1 )] KU A 2 = DK 2 [E K 2 (KU A 2 )] 2. 기기 유일키를 생성하다. KU A = KU A 1 + KU A 2 3. 세션키를 복원한다. K S = D KU A [E KU A (K S )] 4. 메세지를 복원한다. M = D K S [E K S (M)]

37 Clipper 의 문제점 Escrow 기관이 모두 행정부 소속 Clipper Chip 의 효용성에 대한 의문 법 제도의 미비 합법적인 도청을 규제하는 법률 미비 도청 허가 신청이 거부된적이 없음 합법적 도청 허가 기간이 끝난 후도 도청이 가능 Clipper Chip 의 Reverse-engineering

38 5. LUC 공개키 암호 뉴질랜드 출신 연구가 집단이 공동개발 암호화, 서명 등에 사용 Lucas 수열 이용 음이 아닌 정수 P 와 Q 를 선택하고 다음과 같은 2 차 방정식을 계산 X 2 - PX + Q = 0 근 : 방정식의 두 근을 ,  라고 하면 다음과 같은 관계 성립  +  = P,   = Q,  -  = 판별식 D

39 Lucas 수열의 정의 LUC 공개키 알고리즘 – 키 생성 소수 p, q 선택 N = pq 계산 정수 e 계산 gcd[(p-1)(q-1)(p+1)(q+1), e] =1 D 계산 D=P 2 -4 S(N) 계산 S(N) = d 계산 d=e -1 mod S(N) 공개키 KU={e, N} 개인키 KR={d, N}

40 암호화 복호화 평문 : P < N 암호문 : C = V e (P, 1) (mod N) 암호문 : C 평문 : P = V d (C, 1) (mod N)

41 LUC 암호화의 예 1. 소수 p=1949, q=2089 선택 2. N=pq = * 2088 * 1950 * 2090 과 서로소인 e= 평문 P = 선택 5. D = (11111) 2 -4= , S(N)=lcm[(1949+1), )] = d=e -1 mod = C=V 1103 (11111, 1) mod = P =V ( , 1) = 11111