제11장 해쉬 알고리즘 The Hash Algorithm 2007. 11.

목 차 11.1 해쉬함수 정의 및 분류 11.2 전용 해쉬 알고리즘 11.3 기타 해쉬 알고리즘 2

암호 이론의 상관관계 3

11.1 해쉬함수 정의 및 분류 11.1.1 해쉬함수 정의 11.1.2 해쉬함수 분류 11.1.3 해쉬함수 일반모델 11.1.4 Birthday Paradox 11.1.5 해쉬함수 종류 4

11.1.1 해쉬함수 정의 해쉬함수(hash function) 임의의 길이에 이진 문자열을 고정된 길이의 이진 문자열(해쉬값, 메시지 다이제스트, 메시지 지문)로 매핑하여 주는 함수 임의의 비트열 고정 비트열 Hash function 5

11.1.1 해쉬함수 정의 (계속) 해쉬 함수의 두 가지 기본성질 compression - 임의의 유한 길이의 입력 비트 스트링 x를 고정된 길이의 출력 비트 스트링 h(x)로 변환한다. ease of computation - 주어진 h와 x에 대하여 h(x)를 계산하기 쉽다. 해쉬함수 일방향 해쉬 함수(one-way hash function) 충돌 회피 해쉬 함수(collision resistant hash function) 6

11.1.1 해쉬함수 정의 (계속) 해쉬 함수 세 가지 특성 (1) preimage resistance - 주어진 출력에 대하여 입력값을 구하는 것이 계산상 불가능하다. (2) 2nd-preimage resistance - 주어진 입력에 대하여 같은 출력을 내는 또 다른 입력을 찾아 내는 것이 계산상 불가능하다. (3) collision resistance - 같은 출력을 내는 임의의 서로 다른 두 입력 메시지를 찾는 것이 계산상 불가능하다. 7

11.1.1 해쉬함수 정의 (계속) 일방향 해쉬 함수(one-way hash function) (1) compression - 임의의 유한 길이의 입력 비트 스트링 x를 고정된 길이의 출력 비트 스트링 h(x)로 변환한다. (2) ease of computation - 주어진 h와 x에 대하여 h(x)를 계산하기 쉽다. (3) preimage resistance - 주어진 출력에 대하여 입력값을 구하는 것이 계산상 불가능하다. (4) 2nd-preimage resistance - 주어진 입력에 대하여 같은 출력을 내는 또 다른 입력을 찾아 내는 것이 계산상 불가능하다. 8

11.1.1 해쉬함수 정의 (계속) 충돌 회피 해쉬 함수(collision resistant hash function) (1) compression - 임의의 유한 길이의 입력 비트 스트링 x를 고정된 길이의 출력 비트 스트링 h(x)로 변환한다. (2) ease of computation - 주어진 h와 x에 대하여 h(x)를 계산하기 쉽다. (3) 2nd-preimage resistance - 주어진 입력에 대하여 같은 출력을 내는 또 다른 입력을 찾아 내는 것이 계산상 불가능하다. (4) collision resistance - 같은 출력을 내는 임의의 서로 다른 두 입력 메시지를 찾는 것이 계산상 불가능하다. 9

11.1.2 해쉬함수 분류 10

11.1.2 해쉬함수 분류 (계속) MDCs (Manipulation detection codes) 일방향성(one-wayness) 입력을 모르는 해쉬값 y가 주어졌을 때, h(x’)=y를 만족하는 x를 찾는 것은 계산적으로 어렵다. (OWHF) 약한 충돌회피성(weak collision-resistance) h(x)가 주어졌을 때 h(x’)=h(x)인 x’( ≠x)을 찾는 것은 계산적으로 어렵다. 강한 충돌회피성(strong collision-resistance) h(x’)=h(x)인 서로 다른 임의의 두 입력 x와 x’을 찾는 것은 계산적으로 어렵다. (CRHF) 11

11.1.2 해쉬함수 분류 (계속) 메시지 인증 코드(MACs: Message authentication codes) MACs는 비밀키(secret key) 를 파라미터로 가지며, 다음 특성을 만족하는 함수이다. (1) compression - 임의의 유한 길이의 입력 비트 스트링 x를 고정된 길이의 출력 비트 스트링 h(x)로 변환한다. (2) ease of computation - 주어진 hk와 입력 x, 비밀키 k에 대하여 hk(x)를 계산하기 쉽다. 이 계산 결과를 MAC-value 혹은 MAC이라고 부른다 (3) computation-resistance - 즉, 키 를 모르는 공격자가 임의의 메시지에 대한 MAC값을 위장하는 것이 계산상 불가능하다. 12

11.1.3 해쉬함수 모델 13

11.1.3 해쉬함수 일반모델 (계속) 패딩(padding) 메시지가 블록의 상수배가 되게 정보를 추가하는 것을 말한다. 가장 간단한 패딩 방법은 메시지의 끝에 “0”추가 메시지의 끝에 하나의 “1”을 추가, 이어서 “0” 추가 추가된 “0” 설명+이어서 “0” 추가 메시지의 설명+ 이어서 “0” 추가 14

11.1.4 Birthday Paradox 생일 역설 (Birthday Paradox) : 생일이 같은 날일 확률이 ½이려면 몇 명의 사람이 있어야 하나? Prob = 1-(N명의 사람이 모두 생일이 다를 확률) 가정: 사람들의 생일이 균일하게 분포되어 있다. 이 확률이 50%이상이 되기 위한 N의 최소값은? 23명 15

11.1.4 Birthday Paradox (계속) 증명 M개의 통에 N개의 구술을 임의로 넣는다. Prob = 1-(N개의 구슬이 모두 다른 통에 들어갈 확률) 16

11.1.4 Birthday Paradox (계속) 17

11.1.4 Birthday Paradox (계속) 18

11.1.5 해쉬함수 종류 전용 해쉬 함수 MD4, MD5, SHA, SHA-1, RIPEMD-128/160, HAS-160 블록 암호 기반 해쉬 함수-DES 기반 Single length MDCs ※ Matyas-Meyer-Oseas, Davies-Meyer, Miyaguchi-Preneel MDC-2 MDC-4 모듈러 연산에 기반 해쉬 함수 MASH-1, MASH-2 19

11.2 전용해쉬 알고리즘 11.2.1 MD5 11.2.2 SHA-1 11.2.3 RIPEMD-128/160 11.2.4 HAS-160 20

11.2.1 MD5 21

11.2.1 MD5 (계속) HMD5 처리 과정 CVq 128 Yq 512 A B C D fF , ABCD, Yq, T [1-16] 16회 A B C D fG , ABCD, Yq, T [17-32] 16회 A B C D fH , ABCD, Yq, T [33-48] 16회 A B C D fI , ABCD, Yq, T [49-64] 16회 mod 232 CVq+1 22

11.2.1 MD5 (계속) MD5 초기값 A = 0x 0 1 2 3 4 5 6 7 B = 0x 8 9 A B C D E F C = 0x F E D C B A 9 8 D = 0x 7 6 5 4 3 2 1 0 23

11.2.1 MD5 (계속) MD5의 HMD5 상수 T [i]의 값 T [i ] = 232 * ABS (sin (i )) 정수부분; i 는 라디안 T[1] = D76AA478 T[17] = F61E2562 T[33] = FFFA3942 T[49] = F4292244 T[2] = E8C7B756 T[18] = C040B340 T[34] = 8771F681 T[50] = 432AFF97 T[3] = 242070DB T[19] = 265E5A51 T[35] = 699D6122 T[51] = AB9423A7 T[4] = C1BDCEEE T[20] = E9B6C7AA T[36] = FDE5380C T[52] = FC93A039 T[5] = F57C0FAF T[21] = D62F105D T[37] = A4BEEA44 T[53] = 655B59C3 T[6] = 4787C62A T[22] = 02441453 T[38] = 4BDECFA9 T[54] = 8F0CCC92 T[7] = A8304613 T[23] = D8A1E681 T[39] = F6BB4B60 T[55] = FFEFF47D T[8] = FD469501 T[24] = E7D3FBC8 T[40] = BEBFBC70 T[56] = 85845DD1 T[9] = 698098D8 T[25] = 21E1CDE6 T[41] = 289B7EC6 T[57] = 6FA87E4F T[10] = 8B44F7AF T[26] = C33707D6 T[42] = EAA127FA T[58] = FE2CE6E0 T[11] = FFFF5BB1 T[27] = F4D50D87 T[43] = D4EF3085 T[59] = A3014314 T[12] = 895CD7BE T[28] = 455A14ED T[44] = 04881D039 T[60] = 4E0811A1 T[13] = 6B901122 T[29] = A9E3E905 T[45] = D9D4D039 T[61] = F7537E82 T[14] = FD987193 T[30] = FCEFA3F8 T[46] = E6DB99E5 T[62] = BD3AF235 T[15] = A679438E T[31] = 676F02D9 T[47] = 1FA27CF8 T[63] = 2AD7D2BB T[16] = 49B40821 T[32] = 8D2A4C8A T[48] = C4AC5665 T[64] = EB86D391 24

11.2.1 MD5 (계속) MD5의 HMD5 의 기본 동작 g X[K] T [i] CLSS CLSS A B C D A B C g : 기약 함수 F, G, H, I 중의 하나 CLSS=<<<s :32 비트 순환 좌측 쉬프트(로테이션) X[k] : 메시지의 q번째 512비트 블록 중에서 k번째 단어(32비트) T[i] : 행렬 T에서 i번째 단어(32비트) : 법 232 의 덧셈 A B C D g X[K] T [i] CLSS CLSS 라운드 기약함수 g 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) A B C D 25

11.2.1 MD5 (계속) 라운드 기약함수 g 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) BCD FGHI 000 001 010 011 100 101 110 111 0001 1010 0110 1001 0011 0101 1100 1110 26

11.2.2 SHA 알고리즘 Secure Hash Algorithm NIST(National Institute of Standards and Technology)에서 개발 1993년에 표준으로 발표 (FIPS 180) 1995년에 개선된 버전 발표 (FIPS 180-1) SHA-1 해쉬길이: 160 비트(5개의 32 비트 워드) 입력: 264 비트 보다 작은 임의의 크기의 입력 512비트 단위로 적용 전체 입력의 크기가 512 비트의 배수가 아니면 padding을 한다. 마지막 64 비트에는 실제 크기를 기록한다. 27

11.2.2 SHA 알고리즘 (계속) L512비트=N  32비트 서명문 M 100  0 64 서명문 형식 패딩 패턴 : 1000 64비트 : 서명문 길이 표시 상위 32비트와 하위 32비트 교환 L512비트=N  32비트 서명문 M 100  0 64 서명문 M 100  0 64 448 mod 512 28

11.2.2 SHA 알고리즘 (계속) 512 비트 입력은 80개의 32비트 블록으로 확장 4 라운드, 라운드 당 20 단계 5 개의 32 비트 초기 값을 사용 A = 0x67452301 B = 0xefcdab89 C = 0x98badcfe D = 0x10325476 E = 0xc3d2e1f0 29

11.2.2 SHA 알고리즘 (계속) 30

11.2.2 SHA 알고리즘 (계속) 31

11.2.3 RIPEMD–160 L512비트=N  32비트 서명문 M 100  0 64 서명문 M 100  0 64 서명문 형식 패딩 패턴 : 1000 64비트 : 서명문 길이 표시 상위 32비트와 하위 32비트 교환 L512비트=N  32비트 서명문 M 100  0 64 서명문 M 100  0 64 448 mod 512 32

11.2.3 RIPEMD–160 (계속) Y0 Y1  Yq  YL–1   CV0= IV CV1 CVq CVL–1 CVL 512비트 512비트 512비트 512비트 Y0 Y1  Yq  YL–1 512 512 512 512 160 160 160 160 160 HRIP-160 HRIP-160  HRIP-160  HRIP-160 ABCDE CV0= IV CV1 CVq CVL–1 CVL 33

11.2.3 RIPEMD–160 (계속) RIPEMD 초기값 A = 0 1 2 3 4 5 6 7 B = 8 9 A B C D E F C = F E D C B A 9 8 D = 7 6 5 4 3 2 1 0 E = 0 F E 1 D 2 C 3 34

11.2.3 RIPEMD–160 [계속] CVq+1 f1, K1, Xi 16 steps A B C D E  : mod 232 Yq 35

11.2.3 RIPEMD–160 (계속) RIPEMD의 HRIP–160 상수 j = 0 ~ 15 K1 = 00000000 K1´ = 50A28BE6 j = 16 ~ 31 K2 = 5A827999 K2´ = 5C4DD124 j = 32 ~ 47 K3 = 6ED9EBA1 K3´ = 6D703EF3 j = 48 ~ 63 K4 = 8F1BBCDC K4´ = 7A6D76E9 j = 64 ~ 79 K5 = A953FD4E K5´ = 00000000 36

11.2.3 RIPEMD–160 (계속) RIPEMD의 논리함수 37

11.2.3 RIPEMD–160(계속) HRIP–160 기본 동작 A, B, C, D, E = 32비트 버퍼 j = 스텝 수 (0≤j≤79) rols(j) = rotation(회전) Xj = 512비트 입력 값에서 선택된 32비트 Kj = 상수 38

11.2.4 HAS-160 HAS-160 한국 디지탈 서명 표준인 KCDSA에서 사용할 목적으로 개발 160비트의 해쉬 값 512비트 단위로 입력 값 패딩 규칙은 SHA-1과 동일하다. 39

11.2.4 HAS-160 (계속) 초 기 화 값 각 라운드 상수 값 40

11.2.4 HAS-160 (계속) A, B, C, D, E = 32비트 버퍼 t = 라운드 수 (0≤t≤79) Ft = 라운드 함수 CLS(1)S/CLS(2)s = 32비트에서 s비트 순환 좌측 쉬프트 X[t] =512비트 입력 값에서 선택된 32비트, Kt : 상수 값 기 본 동 작 41

11.3 기타 해쉬함수 11.3.1 Single-length MDCs 11.3.2 Double-length MDCs 42

개 요 K C Hi Hi – 1 중간 해쉬값 A D 블록암호 방식을 이용한 일반 해쉬함수 D = EK(A)  C Hi = EK(Hi  1)  C K C Hi Hi – 1 E 중간 해쉬값 A D 43

개 요 (계속) Hi = EHi – 1(Mi)  Mi Hi = EHi – 1(Mi  Hi  1)  Mi  Hi  1 블럭암호 방식을 이용한 안전한 해쉬함수 Hi = EHi – 1(Mi)  Mi Hi = EHi – 1(Mi  Hi  1)  Mi  Hi  1 Hi = EHi – 1(Mi)  Hi  1  Mi Hi = EHi – 1(Mi  Hi  1)  Mi Hi = EMi(Hi  1)  Hi  1 Hi = EMi(Mi  Hi  1)  Mi  Hi  1 Hi = EMi(Hi  1)  Mi  Hi  1 Hi = EMi(Mi  Hi  1)  Hi  1 Hi = EMi  Hi – 1(Mi)  Mi Hi = EMi  Hi – 1(Hi  1)  Hi  1 Hi = EMi  Hi – 1(Mi)  Hi  1 Hi = EMi  Hi – 1(Hi  1)  Mi 44

11.3.1 Single-length MDCs Hi–1 key Mi E Hi Meyer – Matyas 해쉬함수 H0 : 초기벡터 Hi = EH i –1 (Mi)  Mi Hi–1 key Mi E Hi 45

11.3.1 Single-length MDCs (계속) Miyaguchi – Ohta – Iwata 해쉬함수 H0 : 초기벡터 Hi = EH i–1 (Mi)  Hi–1  Mi Hi –1 key Mi E Hi 46

11.3.1 Single-length MDCs (계속) Davies – Meyer 해쉬함수 H0 : 초기벡터 Hi = EMi (Hi –1)  Hi–1 Mi key Hi –1 E Hi 47

11.3.2 Double-length MDCs MDC-2 48

Double-length MDCs (계속) 49

해쉬 함수 요약 n bit 블록 암호 알고리즘을 기반으로 한 해쉬 함수의 요약 ISO/IEC 10118-2 표준에서 1) 단일 길이 MDC로 Matyas-Meyer-Oseas 방식 2) 이중 길이 MDC로 MDC-2 방식 K = 키의 비트 길이, M = 해쉬 값의 비트 길이 50

해쉬 함수 요약 전용 해쉬 함수 요약 모듈러 연산을 이용한 해쉬 함수 51