제12장 해쉬 알고리즘 12.1 MD5 12.2 Seure Hash Algorithm (SHA) 12.3 RIPEMD-160

Presentation on theme: "제12장 해쉬 알고리즘 12.1 MD5 12.2 Seure Hash Algorithm (SHA) 12.3 RIPEMD-160"— Presentation transcript:

1 제12장 해쉬 알고리즘 12.1 MD5 12.2 Seure Hash Algorithm (SHA) 12.3 RIPEMD-160 12.4 HMAC

2 12.1 MD5 – 안전한 해쉬코드의 일반적 구성 CV0 = IV = 초기 n 비트 값
CVi = f(CVi-1, Yi-1) 1 ≤ i ≤ L H(M) = CVL 해쉬 함수의 입력값은 Y0, ..., YL-1 블록들로 구성된 메시지 M

3 12.1 MD5 MIT의 Ron Rivest에 의해 개발 RFC1321에 등록되어 있음 지난 몇년동안 가장 널리 사용됨
RSA 개발자 중의 한 사람 RFC1321에 등록되어 있음 지난 몇년동안 가장 널리 사용됨

4 12.1 MD5 – MD5 로직 MD5 로직 5단계로 구성 입력 : 임의의 길이의 메시지 처리단위: 512-비트 블럭
출력 : 128 비트 메시지 다이제스트 5단계로 구성 1. 패딩 비트의 추가 2. 메시지 길이의 부가 3. MD 버퍼의 초기화 4. 512비트(16워드) 블록의 메시지 처리 5. 출력

5 12.1 MD5 - MD5 로직 MD5를 이용한 메시지 다이제스트(MD) 생성
패딩 (1~512bit) 메시지 길이 (K mod 264) LY 512bits = NY 32bits K bits 메시지 Y Y Yq YL-1 ABCD HMD HMD bit HMD HMD5 128bit digest

6 12.1 MD5 – MD5 로직 1단계 : 패딩 비트 부가 메시지 길이=> 448 mod 512 되도록 패딩
패딩비트 범위 : 1 ~ 512 비트 패딩된 메시지 길이: (L * 512) - 64 비트 1로 시작한 0들의 조합으로 패딩 : 100∙∙∙0 메시지가 원하는 길이일지라도 패딩은 항상 부가

7 12.1 MD5 – MD5 로직 2단계 : 메시지 길이의 부가 패딩 이전 본래 메시지의 길이를 64비트로 표현하여 부가
1, 2단계에 의해 길이가 512비트의 정수배가 되는 메시지를 얻음 확장된 메시지 길이 전체: L * 512 = { Y0, Y1, …, YL-1} = L * 16 * 32 = (L * 16) 워드

8 12.1 MD5 – MD5 로직 3단계 : MD 버퍼의 초기화 버퍼의 용도 : 해수함수의 중간과 최종 결과 보관
버퍼 : 버퍼는 4개의 32비트 레지스터(A,B,C,D)로 표현 레지스터들은 다음과 같은 16진수의 값으로 초기화 A= B= EFCDAB89 C= 98BADCFE D= Little-endian 방식으로 저장 A = B = 89ABCDEF C = FEDCBA98 D =

9 12.1 MD5 – MD5 로직 4단계 : 512(16단어)블럭의 메시지 처리
입력 : 512비트 블럭, 128비트 버퍼값 (A,B,C,D), 사인 함수로 구성되는 64개 요소(T[1] ~ T[64]중 16개씩 적용) Algorithm : 4개의 라운드 처리로 구성된 모듈 같은 함수구조를 가지면서 서로 다른 기약함수에 의존(F,G,H,I) T[i]에서 i번째 요소는 232 * abs(sin(i))의 정수 부분과 일치

10 12.1 MD5 – MD5 로직 단일 512비트 블록의 MD5 처리(MD5 압축 함수)

11 12.1 MD5 – MD5 로직 5단계 : 출력 L개의 512비트 입력블록이 처리되고, L번째 단계의 128비트 메시지 다이제스트 출력 MD5의 과정 CV0 = IV CVq+1 = SUM32(CVq, RFI[Yq, RFH[Yq, RFG[Yq, RFF [Yq , CVq]]]]) MD = CVL IV: ABCD버퍼의 초기값 Yq: 메시지의 q번째 블록 L: 메시지의 블록 수 CVq : 메시지의 q번째 블록과 처리되는 체인 변수 RFX: 기약 논리함수 MD: 마지막 단계의 메시지 다이제스트 SUM32: 입력 각 쌍의 워드에 수행되는 법 232 덧셈

12 12.1 MD5 – MD5 압축 함수 각 라운드는 버퍼 ABCD 상에서 처리하는 16단계 연속으로 구성
a  b + CLSS(a + g(b,c,d) + X[k] + T[i]) a,b,c,d : 버퍼의 4단어 g: 기약 함수 F, G, H, I의 하나 CLSS : 32비트에서 s비트 순환 좌측 쉬프트(로테이션) X[k] : 메시지의 q번째 512비트 블록 중에서 k번째의 단어(32비트) T[i] : 행렬 T에서 i번째 단어(32비트) [표12.1 (b) 참조] + : 법 232 의 덧셈

13 12.1 MD5 – MD5 압축 함수 처리 결과 32비트 단어 배열 {X[0], …, X[15]}는 현재 처리되고 있는 512비트 블럭값을 가진다. 한개 512-비트 블록은 16회 반복을 통하여 X[0] 부터 X[15]까지 처리 T[i]를 순서대로 16개씩 적용 입력의 각 32비트 단어는 라운드마다 한 번씩 4번 사용되고, 사인함수의 64개의 32비트 단어 요소의 각각은 정확히 한번 사용된다. 각 단계에 대하여 버퍼의 4바이트중 하나만이 갱신 각 단계는 워드 단위의 순환 우측 쉬프트 수행(그림 참조)

14 12.1 MD5 – MD5 압축 함수 MD5의 기본동작(한 개의 단계)

15 12.1 MD5 – MD5 압축 함수 각 라운드에 사용되는 기약함수 g AND: , OR: , NOT: ~, XOR: 
g(b, c, d) 1 F(b, c, d) (bc)  (~bd) 2 G(b, c, d) (bd)  (c~d) 3 H(b, c, d) b  c  d 4 I(b, c, d) c  (b~d)

16 12.1 MD5 – MD4 MD5의 개발에 앞서 Ron Rivest가 개발 (1990년 10월 최초 소개, 1992년 4월 RFC1320으로 발표) MD5와 MD4의 차이 MD4는 16단계의 3라운드를 사용하나, MD5는 16단계의 4라운드를 사용한다. MD4는 각 라운드에서 한 번씩 3개의 기약함수를 사용한다. 그러나 MD5는 각 라운드에서 한번씩 4개의 기약 논리 함수를 사용한다. MD5의 각 단계는 이전 단계의 결과에 부가된다. MD4는 마지막 단계의 부가를 포함하지 않는다.

17 12.1 MD5 – MD5의 강도 해쉬코드는 모든 입력 비트의 함수 결과
기본함수(F, G, H, I)는 잘 혼합된 결과의 효과를 유도 같은 MD를 갖는 두개의 메시지 찾기: 264 주어진 MD를 갖고 메시지 찾기: 2128 모듈러 연산방식이 XOR 방식보다 강한 것으로 인식 생일 공격의 가능성 증가 안전성 향상을 위하여 보다 긴 해쉬 코드의 필요성 증가

18 12.2 Secure Hash Algorithm (SHA)
Secure Hash Algorithm: NIST에서 개발 1993년: FIPS PUB 180(Federal Information Processing Standard)로 공포 1995년: FIPS PUB 개정 버전 발행(SHA-1) SHA는 MD4 알고리즘에 기반을 두고 유사하게 설계

19 12.2 SHA – SHA-1 논리 최대 264비트 미만의 길이 메시지 입력 512비트의 블록 단위로 처리 160비트 메시지 다이제스트 출력 MD5의 구조를 따르고, 유사한 처리 과정을 수행

20 단계 3: MD버퍼의 초기화(big endian 형태 저장)
12.2 SHA – SHA-1 논리 단계 1: 패딩 비트의 부가 단계 2: 메시지 길이의 부가 단계 3: MD버퍼의 초기화(big endian 형태 저장) A= B= EFCDAB89 C= 98BADCFE D= E= C3D2E1F0

21 12.2 SHA – SHA-1 논리 단계 4: 1개의 블록 처리 20단계의 4라운드 처리로 구성
4개의 각 라운드는 f1, f2, f3, f4 로 표현되는 4가지의 기약 논리함수 사용 80개의 덧셈 상수 사용(4가지의 숫자) 0  t  19 Kt = 5A827999 20  t  39 Kt = 6ED9EBA1 40  t  59 Kt = 8F1BBCDC 60  t  79 Kt = CA62C1D6 마지막 단계의 출력에 CVq를 더하여 CVq+1을 생성

22 12.2 SHA – SHA-1 논리 단일 512비트 블록의 SHA-1 처리 (SHA-1 압축 함수)

23 12.2 SHA – SHA-1 논리 단계 5: 출력 CV0 = IV CVq+1 = SUM32 (CVq, ABCDEq)
MD = CVL IV : ABCDE 버퍼의 초기값 ABCDEq : q번째 메시지의 블록처리의 마지막 라운드에서의 출력 L : 메시지의 블록 수 (패딩과 길이 필드 포함) SUM32 : 입력쌍의 각 워드에 대해 분리하여 실행하는 법 232에서의 덧셈 MD: 메시지 다이제스트

24 12.2 SHA – SHA-1 압축함수 각 라운드의 형식 A  (E+ f(t,B,C,D) + s5 (A) + Wt + Kt)
B  A C  S30(B) D  C E  D A, B, C, D, E : 버퍼의 5워드 t : 단계 수; 0<= t <= 79 f(t, B, C, D) : 단계 t에 대한 기약 논리 함수 Sk : k비트에 의한 현재 32비트 매개변수의 순환 좌측 쉬프트 Wt : 현재 입력 블록으로 만들어진 32비트 워드 Kt : 덧셈 상수; 미리 정해진 4개의 다른 값 + : 법 232 덧셈

25 12.2 SHA – SHA-1 압축함수 SHA-1의 기본 동작 (한 개의 단계)

26 12.2 SHA – SHA-1 압축함수 단일 블록의 SHA-1 처리에서 80워드 입력 생성

27 12.2 SHA – SHA-1과 MD5의 비교 양쪽 다 MD4로부터 나왔기 때문에, SHA-1과 MD5는 서로 아주 유사함. 따라서 그들의 강도와 특성도 비슷 MD5와 SHA의 비교 MD5 SHA-1 다이제스트 길이 처리의 기본단위 처리 단계수 최대 메시지 크기 기약 논리 함수 덧셈 상수 128비트 512비트 64 (16 * 4) 무한대 4 64 160비트 80 (20 * 4) 264

28 12.3 RIPEMD-160 유럽의 RIPE(RACE Integrity Primitives Evaluation) 프로젝트의 일환으로 개발[DOBB96b,BOSS97] MD4, MD5에 대한 공격을 부분적으로 성공한 팀이 RIPEMD 128비트 버전 개발 RIPE 일원이 아닌 H. Dobbertin이 RIPEMD, MD4, MD5의 허점 발견 RIPE 멤버와 H. Dobbertin 공동으로 RIPEMD 보완개발 입출력 길이 입력 : 임의의 길이의 메시지를 512 비트-블록 단위 처리 출력 : 160비트

29 12.3 RIPEMD-160 - RIPEMD-160 논리 단계1 : 패딩비트 부가 단계2 : 메시지 길이 부가
메시지는 비트의 길이가 512를 법으로 하여 448과 합동이 되도록 패딩 패딩은 항상 부가, 패딩비트수 : 1~512비트, One-Zero-Leading방식 단계2 : 메시지 길이 부가 원래 메시지의 길이 계산 64비트 블록에 길이 정보 부가, 부호없는 정수형 Little-Endian 규칙을 따름.

30 12.3 RIPEMD-160 - RIPEMD-160 논리 단계3 : MD 버퍼의 초기화
160비트 버퍼는 해쉬의 중간결과와 최종 결과를 저장 5개의 32비트 레지스터(A,B,C,D,E) 각 레지스터들은 고정된 값으로 초기화 A = B = EFCDAB89 C = 98BADCFE D = E = C3D2E1F0 SHA-1에서 사용된 값과 동일, Little-Endian형태로 저장 A = B = 89ABCDEF C = FEDCBA98 D = E = F0E1D2C3

31 12.3 RIPEMD-160 - RIPEMD-160 논리 단계4 : 512비트 블록 메시지 처리 단계5 : 출력
16단계로 되어 있는 10라운드의 처리 10라운드는 두개의 5라운드로 나뉘어 병행처리 각 라운드는 각각의 f1,f2,f3,f4,f5 기약 논리함수 사용(표 9.4) 각 라운드는 서로 다른 9가지(0의 값 포함)의 덧셈상수(Kj) 사용(표9.3) 좌,우 5번째 라운드에서 CVq+1을 생성하기 위해 모듈러 232 덧셈수행 단계5 : 출력 160비트 메시지 다이제스트 생성

32 12.3 RIPEMD RIPEMD-160 압축 함수 단일 512비트 블록에 대한 RIPRMD-160 처리 (RIPEMD-160 압축 함수)

33 12.3 RIPEMD-160 - RIPEMD-160 논리 기본 RIPRMD-160 동작 (한 개의 단계) 메시지 Xi ,
상수 Kj rol10 : 10bit회전

34 12.3 RIPEMD-160 – MD5, SHA-1과의 비교 RIPEMD-160 – MD5, SHA-1과의 비교 MD5
다이제스트 길이 128비트 160비트 처리의 기본 단위 512비트 단계 수 64 (16번의 4라운드) 80 (20번의 4라운드) 160 (16번의 5병행 라운드) 최대 메시지 크기  264-1 비트 기약 논리 함수 4 5 덧셈상수 64 9 Endianness Little-endian Big-endian

35 12.3 RIPEMD-160 – MD5, SHA-1과의 비교 해쉬함수의 상대적 성능 알고리즘 Mbps MD5 26 SHA-1
850-MHz Celeron 에서 C++ 코딩 경우 알고리즘 Mbps MD5 26 SHA-1 48 RIPEMD-160 31

36 12.4 HMAC (Hashed-MAC) FIPS PUB 113 : 대칭 블록 암호에 기반한 MAC 계산(데이터 인증)
암호 해쉬 함수가 대칭 블록 암호보다 빠름 암호 해쉬 함수에 대한 라이브러리 코드의 입수 용이 암호 해쉬 함수에 대한 수출 제한 없음. MD5와 같은 해쉬 함수는 비밀키에 의존하지 않음 비밀키를 기존의 해쉬 알고리즘에 결합[BELL96a,BELL96b] HMAC RFC 2104로 발행 IP보안을 위한 MAC 의무 구현사항으로 선정(SSL에서 사용)

37 12.4 HMAC - HMAC 설계 목표 RFC 2104의 HMAC 설계 목표 기존의 해쉬 함수를 변경 없이 사용 가능해야 함
해쉬 함수는 소프트웨어로 구현 가능, 무상입수 용이 내장 해쉬 함수 교체 용이 (해쉬 함수의 블랙 박스화) 성능 저하 없이 해쉬 함수의 원래 성능 계속 유지 간단한 방법으로 키 조작 인증 메커니즘의 암호학적 분석 이해 가능

38 12.4 HMAC - HMAC 알고리즘 HMACK(M) = H[(K+  opad) || H[K+  ipad) || M]]
H : 내장된 해쉬 함수 (MD5, SHA-1, RIPEMD-160 etc.) M : 입력메시지(패딩포함) Yi : M의 i번째 블록 L : M의 블록수 b : 블록내에 있는 비트 수 n : 산출된 해쉬코드의 길이 K : 비밀키 K+ : b비트가 되도록 왼쪽을 0으로 채운 K ipad : 을 b/8번 반복 (0과1이 각 4개로 구성) opad : 을 b/8번 반복(0과1이 각 4개로 구성)

39 12.4 HMAC - HMAC 알고리즘 HMAC 구조

40 12.4 HMAC - HMAC 알고리즘 처리과정 1. b비트 스트링 K+ 생성 2. b비트 블록 Si를 생성
K+ 와 ipad를 XOR 3. M을 Si에 추가 Msg1 = [Si  M] ; 대상 메시지에 Si 를 붙여서 해쉬 처리에 입력 4. 3단계의 Msg에 해쉬를 적용 n비트 다이제스트를 갖는 해쉬알고리즘 사용 5. b비트 블록 S0를 생성 K+ 와 opad를 XOR 6. 단계 4에서 만들어진 해쉬함수 적용결과에 S0를 추가 Msg2 = [S0  H(Msg1)] 7. 6단계의 결과에 해쉬함수를 다시 적용 한 결과 HMACK (M) = H[(K+  opad)  H[(K+  ipad)  M]]

41 12.4 HMAC - HMAC 알고리즘 1단계 2단계와 5단계 2개의 값은 미리 계산 가능
K=160, b=512 경우, 첨가 비트= 352비트 개의 “0” ( = 352) 2단계와 5단계 ipad 및 opad 에 의해 키 값의 절반을 뒤집는 결과 (XOR을 사용) 2개의 값은 미리 계산 가능 f(IV, (K+  ipad)) f(IV, (K+  opad)) f(cv, block) ; n비트 체인변수와 b비트의 블록을 입력으로 n비트 체인변수를 생성 이 값은 시작 단계와 키가 변경될 때만 계산 필요 미리 계산하여 해쉬함수에 IV로 제공 가능

42 12.4 HMAC - HMAC 알고리즘 HMAC의 효과적 구현 (f함수 미리 계산)

43 12.4 HMAC - HMAC의 안전성 (주어진 시간, 메시지ㅡMAC 짝)에서 HMAC에 대한 공격 성공 확률
공격자는 해쉬 알고리즘과 디폴트 IV값을 알고있음. 그러나, K(비밀키)를 모르기 때문에 메시지와 코드의 짝을 생성할 수 없음. 128비트 길이의 해쉬코드 공격을 위해서는 동일한 키로 생성된 264의 블록 (272 bit)을 필요 250,000년 동안 키의 변경없이 연속적인 메시지 스트림 조사필요 속도가 중요한 경우, 내장 해쉬함수로 SHA-1이나 RIPEMD160 보다 MD5 사용이 바람직