(c) Byoungcheon Lee, Joongbu Univ. 해쉬함수 중부대학교 정보보호학과 이병천 교수 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 메시지 압축의 필요성 서명의 효율성 향상 서명문 M N 비트 M 압축 함수 n 비트, n<<N CF(M) n 비트 압축 서명문 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 메시지 압축의 예 C1 = Ek (M1) C2 = Ek (M2  C1) C3 = Ek (M3  C2)  Ck = Ek (Mk  Ck–1) CF(M) = Ek (M1  M2    Mk  Ck) E C1 K C2 C3 Ck CF(M) M1 M2 M3 Mk (c) Byoungcheon Lee, Joongbu Univ.

해쉬함수의 정의 정의 임의의 길이의 비트스트링을 고정된 길이의 출력값으로 압축하는 함수 H = h(M), M: pre-image. H: image, hash code n 비트 서명문 M h R 비트 해쉬코드 H h(M) = H n >> R 해쉬값 H 2R 서명문 M 2n 정의역 공변역 이론상 충돌가능 충돌을 찾기는 어려워야 함

(c) Byoungcheon Lee, Joongbu Univ. 해쉬함수의 요구사항 0. 해쉬함수 계산의 효율성 양호 1. 일방향성 (약) 해쉬값 H로부터 h(M) = H가 되는 서명문 M을 찾는 것은 계산상 불가능 2. 일방향성 (강) 서명문 M과 해쉬값 H가 주어졌을 때 h(M) = H가 되는 서명문 M  M 를 찾는 것이 계산상 불가능 3. 충돌 회피성 h(M) = h(M)가 되는 서명문 M  M 를 찾는 것이 계산상 불가능 인증을 위해서는 2까지, 서명을 위해서는 3까지 필요. (c) Byoungcheon Lee, Joongbu Univ.

해쉬함수의 종류 1. 블록 암호 알고리즘에 기초한 해쉬함수 (ISO/IEC 10118-2) 2. 모듈러 연산을 사용하는 해쉬함수 (ISO/IEC 10118-4) 3. 전용해쉬함수 (ISO/IEC 10118-3) 128 bit : MD4, MD5, RIPEMD, RIPEMD-128 160 bit : RIPEMD-160, SHA, SHA-1, Selectable length (128~256): Haval, PMD-N

전용해쉬함수의 구조 덧붙이기 - 임의의 길이의 입력 X를 입력블록 비트수의 배수가 되도록 최소한의 비트추가 분할 - 덧붙여진 입력을 정해진 비트수로 나눔. t 개의 입력블록 (X1, … , Xt)로 분할됨. 초기화 - 첫 연쇄변수(chaining variable) H0 = IV. 반복연산 - Hi = g(Hi-1, Xi), i = 1, .. , t. 해쉬코드출력 - H = h(X) = Ht

(c) Byoungcheon Lee, Joongbu Univ. 해쉬함수에 대한 공격 생일 공격 (Birthday paradox) h(M) = h(M) 생일이 같은 날일 확률이 ½이려면 몇 명의 사람이 있어야 하나? 답 : 23명 n: 365일, r:학생의 수 라고 할 때 적어도 한쌍 이상의 학생이 동일한 생일을 가질 확률은? 칠판에 365일을 써넣고 한 사람씩 자기 생일을 지워 나갈 때 충돌이 발생하지 않으면 자기생일을 지울 수 있음. brute–force attack (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 해쉬함수에 대한 공격 해쉬값의 길이가 k=128 비트인 경우 임의의 r개의 해쉬값, s개의 해쉬값을 준비 (r=s=64비트) 동일한 해쉬값이 있는지 조사 동일한 해쉬값이 하나이상 발견될 확률은 2128 번 시도하지 않고도 2x264비트번 시도하면 충돌값을 찾을 수 있음 (c) Byoungcheon Lee, Joongbu Univ.

SHA (Secure Hash Algorithm) NIST (national institute of standards and technology)에서 개발 1993년 FIPS PUB 180 (Federal Information Processing Standard)로 공표 SHA는 MD4를 기반으로 MD4와 유사하게 설계 160비트의 해쉬값을 출력 512비트 단위로 동작 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. SHA SHA 서명문 형식 패딩 패턴 : 1000 64비트 : 원래의 서명문을 264 으로 법연산한 값, 즉 서명문의 하위 64비트 값 L512비트=N  32비트 서명문 M 100  0 64 서명문 M 100  0 64 448 mod 512 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. SHA SHA의 HSHA 처리과정 Yq CVq 512 160 A B C D E 라운드 0 f1, ABCDE, Yq, K0, w0 A B C D E 라운드 1 f2, ABCDE, Yq, K1, w1   A B C D E 라운드 79 f80, ABCDE, Yq, K79, w79 160 CVq+1 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. SHA SHA의 HSHA 기본동작 A B C D E 입력 버퍼 ft 논리함수 CLS5 입력메시지에서 선택된 32비트 CLS30 Wt Kt 상수 A B C D E 출력 버퍼 CLSn : n회 순환좌측쉬프트 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. SHA SHA 초기값 A = 6 7 4 5 2 3 0 1 B = E F C D A B 8 9 C = 9 8 B A D C F E D = 1 0 3 2 5 4 7 6 E = C 3 D 2 E 1 F 0 SHA의 상수 Kt 값 t = 0 ~ 19 Kt = 5 A 8 2 7 9 9 9 t = 20 ~ 39 Kt = 6 E D 9 E B A 1 t = 40 ~ 59 Kt = 8 F 1 B B C D C t = 60 ~ 79 Kt = C A 6 2 C 1 D 6 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. SHA SHA의 논리함수 t = 0 ~ 19 ft (B, C, D) = B · C + B · D t = 20 ~ 39 ft (B, C, D) = B  C  D t = 40 ~ 59 ft (B, C, D) = B · C + B · D + C · D t = 60 ~ 79 ft (B, C, D) = B  C  D (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. SHA SHA의 상수 wt w2 w8 wt–14 wt–8 w65 w71 512비트 Yq w0 w13 wt–16 wt–3 w63 w76 32 32 32 CLS1 CLS1 CLS1  w0 w1 w15 w16  wt  w79 (c) Byoungcheon Lee, Joongbu Univ.