해쉬 알고리즘.

Presentation on theme: "해쉬 알고리즘."— Presentation transcript:

1 해쉬 알고리즘

2 해쉬 함수의 구성 원리 MD5 메시지 다이제스트 알고리즘 안전한 해쉬 알고리즘(SHA-1) RIPEMD-160 HMAC

3 해쉬함수의 구성원리 CV0 = IV = 초기 n 비트 값 CVi = f(CVi-1, Yi-1) 1 ≤ i ≤ L
H(M) = CVL 해쉬 함수의 입력값은 Y0, ..., YL-1 블록들로 구성된 메시지 M

4 1. MD5 메시지 다이제스트 알고리즘 MIT의 Ron Rivest에 의해 개발됨 RFC1321 MD5 로직
입력 : 임의의 길이의 메시지 출력 : 128비트 메시지 다이제스트 입력처리 : 512비트 블록단위로 처리 5단계로 구성

5 L*512 bits = N * 32 bits K bits Message 512 512 512 512 Y0 Y1 Yq YL-1
Mess. Length (K mod 2^64) Padding (1 to 512 bits) L*512 bits = N * 32 bits K bits Message 100…0 512 512 512 512 Y0 Y1 Yq YL-1 512 512 512 512 HMD5 HMD5 HMD5 HMD5 128 IV 128 128 128 CV1 CVq CVL-1 Digest

6 단계1 : 패딩 비트의 부가 단계2 : 메시지 길이의 부가 단계3 : MD 버퍼의 초기화
하나의 ‘1’비트 뒤에 필요한 개수의 ‘0’ 비트들을 붙여서 구성 단계2 : 메시지 길이의 부가 512비트의 정수배가 되도록 메시지 길이 구성 단계3 : MD 버퍼의 초기화 Little endian 형태로 4개의 레지스터에 1부터 값을 초기화 A= <= 워드 A : (낮은 주소 바이트 위치에 있는 워드의 LSB 형태로 저장) 단계4 : 512 비트(16단어) 블록의 메시지 처리 4개의 라운드로 구성된 압축함수 모듈 통과

7 Yq CVq 128 32 A B C D 512 F, T[1…16], X[i] 16steps A B C D G, T[17…32], X[p2i] 16steps A B C D H, T[33…48], X[p3i] 16steps A B C D I, T[49…64], X[p4i] 16steps + + + + Addition is mod 2^32 CVq+1

8 단계5 : 출력 입력 : 128비트 버퍼 값 ABCD 각 라운드 : 사인함수로 구성되는 T[1..64]의 ¼ 사용
T의 i번째 요소는 2^32 * abs(sin(i))의 정수부분과 일치하는 값 i는 라디안 Abs(sin(i)) : 0과 1사이의 값 T의 각 요소는 32비트 정수 테이블은 사인함수 이용 네번째 라운드의 출력은 첫번째 라운드의 입력이었던 CVq와 더해져서 CVq+1생성 단계5 : 출력

9 CV = IV CVq+1 = SUM32(CVq, RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]])
MD5의 과정요약 CV = IV CVq+1 = SUM32(CVq, RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]]) MD = CVL IV : 3단계에서 정의된 ABCD 초기 버퍼값 Yq : 메시지의 q번째 512비트 블록 L : 메시지의 블록수 CVq : 메시지의 q번째 블록과 함께 처리되는 체인변수 RFx : 기약 논리 함수 x를 사용하는 라운드 함수 MD : 최종 메시지 다이제스트 값 SUM32 : 입력 쌍의 각 단어에 제각기 수행되는 법 2^32 덧셈

10 MD5 압축 함수 각 단계의 형식은 다음과 같다 a <- b + ((a + g(b,c,d) + X[k] + T[i]) <<< s) a,b,c,d : 버퍼의 4단어, 단계에 따라 상이한 순서로 되어있음 g : 기약함수 F,G,H,I 중의 하나 <<< s : s 비트에 의한 32비트 매개변수의 순환좌측쉬프트 X[k] : 메시지의 q번째 512비트 블록 중에서 k번째 32비트단어 T[i] : 매트릭스 T에서 i번째 32비트 단어 + : 법 2^32 덧셈

11 A B C D + g X[k] + T[i] + + A B C D 라운드 기약함수 g g(b,c,d) 1 F(b,c,d)
(bc)(bc) 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 + g X[k] + T[i] + CLSs + A B C D

12 MD4 MD4는 MD5의 이전버전 MD4의 목적 Ron Rivest가 1990년 10월 개발 RFC 1320
안전성 : 해쉬코드에 대한 일반적인 요구사항 속도 : 빠른 시행에 적합 -> 32비트 구조로 연산 단순성과 간결성 : 프로그램과 표현이 단순 Little-endian구조의 선호

13 MD4 vs MD5 라운드 덧셈 논리함수 이전 단계와의 연결 MD4 : 16단계의 3라운드 MD5 : 16단계의 4라운드
MD5는 64단계의 각각에 다른 덧셈 상수 T[I]사용 논리함수 MD4 : 각라운드에 한번씩 3개의 기약 함수 사용 MD5 : 각 라운드에서 한번씩 4개의 기약 논리 함수 사용 이전 단계와의 연결 MD5 : 이전 단계의 결과의 데이터 이용 =>더 큰 쇄도효과

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

15 SHA-1 논리 최대 264비트 미만의 길이 메시지 입력 512비트의 블록 단위로 처리 160비트 메시지 다이제스트 출력
512비트 메시지 블록 단위, 160비트 해쉬코드, 체인변수를 갖고 MD5와 유사한 처리 과정을 수행 단계 1 : 패딩 비트의 부가 단계 2 : 메시지 길이의 부가 단계 3 : MD 버퍼의 초기화(big endian 형태 저장) A= <= 워드 A :

16 4개의 각 라운드는 f1, f2, f3, f4로 표현되는 4가지의 기약 논리함수 사용 80개의 덧셈 상수 사용(4가지의 숫자)
단계 4 : 1개의 블록(512비트-16워드) 처리 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을 생성

17

18 SHA-1 압축함수 단계 5 : 출력 SHA-1의 전체 처리과정 A<-(E+f(t,B,C,D)+S5(A)+Wt)
CV0 =IV CVq+1 = SUM32(CVq, ABCDEq) MD= CVL SHA-1 압축함수 A<-(E+f(t,B,C,D)+S5(A)+Wt) B<-A C<-S30(B) D<-C E<-D

19 SHA-1 처리 기본동작

20 80워드 입력 계열의 생성

21 SHA-1과 MD5의 차이점 특성 MD5 SHA-1 다이제스트 길이 처리의 기본단위 처리 단계수 최대 메시지 크기
기약 논리 함수 덧셈 상수 128비트 512비트 64(16*4) 무한대 4 64 160비트 80(20*4) 264

22 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비트

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

24 단계 3 : MD 버퍼의 초기화 단계 4 : 512비트 블록 메시지 처리
160비트 버퍼는 해쉬의 중간결과와 최종 결과를 저장 5개의 32비트 레지스터(A,B,C,D,E) 각 레지스터들은 고정된 값으로 초기화 A= (SHA-1에서 사용된 값과 동일) 단계 4 : 512비트 블록 메시지 처리 16단계로 되어 있는 10라운드의 처리 10라운드는 두개의 5라운드로 나뉘어 병렬처리 각 라운드는 각각의 f1,f2,f3,f4,f5 기약 논리함수 사용 각 라운드는 서로 다른 9가지(0의 값 포함)의 덧셈상수(K1)사용 좌,우 5번째 라운드에서 CVq+1을 생성하기 위해 모듈러 232덧셈수행 단계 5 : 출력 – 160비트 메시지 다이제스트 생성

25 단일 512비트 블록 처리

26 기본동작 메시지Xi (0<=i<=15) 상수 Ki rol10:10bit회전

27 MD5, SHA-1, RIPEMD-160비교

28 해쉬함수 성능비교 알고리즘 Mbps Md5 26 SHA-1 48 RIPEMD-160 31
850-MHz Celeron에서 C++ 코딩 경우 알고리즘 Mbps Md5 26 SHA-1 48 RIPEMD-160 31

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

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

31 HMAC 구조 을 b/8번 반복 을 b/8번 반복

32 처리과정 b비트 스트링 K+ 생성 : 비밀키 K의 왼쪽에 0을 첨가 b비트 블록 Si를 생성 : K+ 와 ipad를 XOR
M을 Si 에 추가 : Msg1=[Si||M] 3단계의 Msg1에 해쉬를 적용 b비트 블록 S0를 생성 : K+ 와 opad를 XOR 단계 4에서 만들어진 해쉬함수 적용결과에 S0를 추가 6단계의 결과에 해쉬함수를 다시 적용 HMACK(M)=H[(K+ XOR opad)||H(K+ XOR ipad)||M]]

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

34 디지털 서명 & 인증 프로토콜

35 목 차 1. 디지털 서명 개요 2. 직접적 디지털 서명 3. 중재된 디지털 서명

36 암호학적 점검값의 기본 사용 예 K1 EK2[M || CK1(M)] M M C || E D 비교 C K2 K2 CK1(M)

37 1. 디지털 서명 적용 예 전자식 자금 전달의 경우 주식 매매 요청의 경우 디지털 서명 해결책
수신자 : 1. 전달된 자금의 양을 증가 2. 송신자로부터 해당 금액이 왔다고 주장 주식 매매 요청의 경우 송신자 : 1. 단말기를 통해 주식 매매 요청 2. 주식 값이 하락 3. 자신이 요청을 한 적이 없다고 주장 송신자와 수신자의 완벽한 신뢰가 없는 상황에서 인증 이상의 어떤 것이 필요 디지털 서명 해결책

38 1. 디지털 서명 배경 정의 목적 1) 종이 문서 사회에서 정보화 사회로의 진전으로 다양한 서비스 요구
1) 종이 문서 사회에서 정보화 사회로의 진전으로 다양한 서비스 요구 2) 데이타 무결성 및 사용자 인증 서비스가 필수적 정의 공개키 암호화를 사용하여 구현하며, 보낸 사람과 메시지를 연결하는 방법을 제공하고, 구매 시 사이버 스페이스에서 서명하는 것이다. 목적 신뢰성 확보 ( 내용의 위·변조 및 신분 확인에 사용)

39 디지털 서명 특징 손으로 쓴 서명과 유사 해당 서명의 저자, 날짜와 시간의 확인 가능 서명할 당시의 내용을 인증 가능
분쟁시 제 3자가 확인 가능

40 디지털 서명 특징 위조불가(Unforgeable) : 서명자만이 서명문 생성 가능 서명자 인증(Authentic)
: 서명문의 서명자를 확인 가능 재사용 불가(Not reusable) : 서명문의 서명은 다른 문서의 서명으로 사용 불가능 변경 불가(Unalterable) : 서명된 문서의 내용 변경 불가능 부인 불가(Nonrepudiation) : 서명자는 후에 서명한 사실을 부인 불가능

41 디지털 서명 요구 조건 서명은 서명되는 메시지에 의존하는 비트 형태이어야 한다.
서명은 위조와 부인을 방지하기 위해서 송신자에 대한 유일한 어떤 정보를 이용해야만 한다. 디지털 서명을 만들기가 비교적 쉬워야 한다. 디지털 서명을 인식하고 확인하기가 쉬워야 한다. 기존의 디지털 서명에 대한 새로운 메시지를 구성하거나 또는 주어진 메시지에 대한 거짓 디지털 서명을 구성함으로써 디지털 서명을 위조하는 것이 계산적으로 실행 불가능해야 한다. 기억장소에 디지털 서명의 복사본을 유지하는 것이 실용적이어야 한다.

42 2. 직접적 디지털 서명 오직 통신하는 상대방(출신, 목적지)만을 포함 직접적 디지털 서명 방식 비밀성을 위해
송신자의 개인키를 가지고 전체 메시지를 암호화 송신자의 개인키를 가지고 메시지의 해쉬 코드를 암호화 비밀성을 위해 수신자의 공개키 또는 공유 비밀키를 가지고 서명된 메시지를 암호화

43 Authentication and signature
메시지 암호화의 기본 사용법 M E D KRa EKRa(M) Authentication and signature KUa

44 단점 구조의 정당성은 송신자의 개인키에 달려 있음 송신자가 개인키를 분실, 도난 당했다고 주장이 가능
실제로 개인키를 도난 당했을 경우의 대책 미흡 사례 공갈 협박에 의해 개인키를 노출하고 침묵 가능 => 신고 이전까지는 심각한 손상 초래 사고 발생시에 불리할 경우 도난 당했다고 거짓 주장 실제로 자신도 모르는 사이에 도난 당했을 경우 가능성 존재

45 3. 중재된 디지털 서명 기법 관용 암호 방식(1) 중재자에게 메시지 노출 Alice와 Carol 간에 비밀키 공유 : KCA
Carol과 Bob 간에 비밀키 공유 : KCB 2. Verification Carol 1. M || EKCA[IDA || H(M)] 3.EKCB[IDA || M || EKCA[IDA || H(M) || T] Alice Bob

46 관용 암호 방식(1) Bob은 Alice의 서명을 직접 검사할 수 없음 서명은 분쟁 해결을 위해 존재
Alice와 Bob은 Carol에게 높은 신뢰를 가지고 있어야 함 Carol이 KCA를 노출 시키지 않는다. EKCA [IDA || H(M)] 형태의 거짓 서명을 만들지 않는다. Bob은 서명이 A에 의해서 만들어졌을 때만, carol이 EKCB [IDA || M || EKCA[IDA || H(M) || T]를 보낸다는 것을 신뢰

47 관용 암호 방식(2) 메시지 비밀 유지 Alice와 Bob이 비밀키를 공유 : KAB Carol Bob Alice
1. IDA || EKAB[M] || EKAC[IDA || H(EKAB[M])] 2. Verification 3.EKCB[IDA || EKAB[M] || EKAC[IDA || H(EKAB[M]), T] Alice Bob Carol

48 관용 암호 방식(2) 장점 단점 Carol은 메시지 내용을 읽을 수 없다.
Carol은 Alice와 Bob의 부정을 막을 수 있다. 단점 Carol은 Alice와 함께 서명된 메시지를 부인할 수 있다. Carol은 Bob과 함께 Alice의 서명을 위조할 수 있다.

49 공개키 암호 방식 메시지 비밀 유지 관용 암호 방식에서 발생할 수 있는 문제점 해결 가능 Carol Bob Alice
1. IDA || EKRA[ IDA || EKUB(EKRA[M])] 2. Verification 3.EKRC[IDA || EKUB(EKRA[M])], T] Alice Bob Carol

50 공개키 암호 방식 장점 통신 전에 통신의 상대자간에 공유해야 할 정보가 없다.
KRa가 노출되었다고 할지라도 KRC가 노출되지 않았으면 부정확한 날짜가 매겨진 메시지가 보내질 수 없다. Alice로부터 Bob에게 온 메시지의 내용은 Carol과 다른 모든 사람들에게 있어서 비밀이다.