Chapter 5 해쉬 함수.

Presentation on theme: "Chapter 5 해쉬 함수."— Presentation transcript:

1 Chapter 5 해쉬 함수

2 해쉬 함수(hash function)? 해쉬 함수는 데이터(입력)를 비교적 작은 크기의 스트링(출력)으로 만드는 방법이다.
해쉬 함수의 출력값은 입력된 데이터의 디지털 “지문”의 역할을 한다. 암호 해쉬 함수(Crypto Hash function) 특정한 추가적인 보안의 특성을 갖는 해쉬 함수 Chapter 5 Hash Function

3 왜 해쉬 함수를 사용하는가? Alice가 메시지 M에 서명을 한다고 하자.
Alice는 M과 S = [M]Alice를 Bob에게 보낸다. Bob은 M = {S}Alice을 증명한다. 단순히 S를 보내는 것은 괜찮은가? 만약 M이 크다면, [M]Alice 을 계산하는데 많은 시간이 필요하다. 대신에, Alice가 h(M)에 서명을 한다면 어떨까? h(M)은 M 보다 훨씬 길이가 작다. Alice는 M과 S = [h(M)]Alice 를 Bob에게 보낸다. Bob은 h(M) = {S}Alice을 증명한다. Chapter 5 Hash Function

4 암호 해쉬 함수(Crypto Hash Function)
암호 해쉬 함수 h(x)는 다음과 같은 성질을 가져야 한다. 압축(Compression) 출력 메시지의 길이는 입력 메시지의 길이보다 작다. 효율성(Efficiency) h(x)는 어떤 x에 대해서도 계산하기 쉬워야 한다. 단방향(One-way) y가 주어졌을 때 h(x) = y에 해당하는 x를 찾는 것은 실행 불가능(infeasible)해야 한다. Chapter 5 Hash Function

5 암호 해쉬 함수 약한 충돌 방지(Weak collision resistance)
x와 h(x)가 주어졌을 때 h(y) = h(x)인 y ( x)를 찾는 것은 실현 불가능하다. 강한 충돌 방지(Strong collision resistance) h(x) = h(y)인 x와 y (x  y)를 찾는 것은 실현 불가능하다. 많은 충돌이 존재하겠지만 이것을 찾는 것은 힘들어야 한다. Chapter 5 Hash Function

6 생일 문제에 들어가기 전에… N명이 한 방에 있다고 하자.
해법: 1/2 = 1  (364/365)N for N 해답: N = 253 Chapter 5 Hash Function

7 생일 문제(Birthday Problem)
한 방에 있는 사람들 중에 2명 또는 그 이상이 같은 생일일 확률이 ½보다 크기 위해서는 얼마나 많은 사람들이 있어야 하나? 1  365/365  364/365   (365N+1)/365 위의 값이 ½과 같기 위해서는 N = 23 (n=22일 때 P≈0.475, n=23일 때 Pn≈0.506) 놀라운가? 역설적인가(paradox)? 아니다: “그렇게 되어야만 한다” x와 y의 모든 쌍들을 비교해야 하기 때문에 365의 제곱근이 근사값이 된다. Chapter 5 Hash Function

8 생일 문제 Chapter 5 Hash Function

9 해쉬와 생일 h(x)가 N비트이면, 2N 개의 다른 해쉬 값들이 가능하다. sqrt(2N) = 2N/2
의미: 안전한 N비트의 대칭키를 “깨기”위해서는 2N1번의 작업이 필요하다. 반면에 안전한 N 비트의 해쉬를 “깨기”위해서는 2N/2번의 작업이 필요하다.

10 비암호 해쉬(Non-Crytpo Hash)
Chapter 5 Hash Function

11 비암호 해쉬 (1) 데이터: X = (X0,X1,X2,…,Xn-1), Xi는 바이트
hash(X) = X0+X1+X2+…+Xn-1 mod 256이라고 하자. 출력 결과는 항상 8 bits 이것은 안전한가? 예: X = ( , ) = = 185 = Hash of X = 하지만 Hash of Y = ( , ) 쉽게 충돌을 찾을 수 있다. 따라서 안전하지 않다. Chapter 5 Hash Function

12 비암호 해쉬(2) 데이터: X = (X0,X1,X2,…,Xn-1) hash는 다음과 같다고 하자. 이 해쉬는 안전한가?
h(X) = nX0+(n-1)X1+(n-2)X2+…+1Xn-1 mod 256 이 해쉬는 안전한가? 적어도, h( , )h( , ) 하지만 hash of ( , )는 hash of ( , )와 같다. 안전하지는 않지만 이 해쉬는 비암호 응용 분야인 resync에서 성공적으로 사용되고 있다. Chapter 5 Hash Function

13 RSYNC rsync is a free software computer program for Unix systems which synchronizes files and directories from one location to another while minimizing data transfer using delta encoding when appropriate. Chapter 5 Hash Function 13

14 비암호 해쉬 (3) 중복 검사(Redundancy check) 검사합(Checksum)
별도의 데이터가 에러 검출 혹은 정정을 위해서 메시지에 첨가된다. 어떤 해쉬 함수도 중복 검사에 사용될 수 있다. 간단한 예: 패러티 검사(parity check) 검사합(Checksum) 중복 검사의 한 형태 IP 프로토콜에서 사용 Chapter 5 Hash Function

15 비암호 해쉬 (4) 순환 중복 검사(Cyclic Redundancy Check: CRC)
의도적으로 데이터를 손상시키는 것을 발견하기 위한 것은 아니다. 하지만 CRC는 가끔 암호 응용 분야에 잘못 사용되는 경우가 있다. (예: WEP) Chapter 5 Hash Function

16 WEP WEP: Wired Equivalent Privacy IEEE 802.11 무선 네트워크의 보안 프로토콜
WEP은 기밀성을 위해서 스트림 암호 RC4을 사용하고 무결성을 위해서 CRC-32 checksum을 사용한다. Chapter 5 Hash Function 16

17 암호 해쉬(Crytpo Hash) Chapter 5 Hash Function

18 암호 해쉬 설계 (1) 충돌 방지 바람직한 특성: 눈사태 효과 충돌을 방지할 수 있으면 해쉬 함수는 안전하다고 한다.
입력값의 변화는 출력값과는 상관 관계가 없어야 한다. 바람직한 특성: 눈사태 효과 입력값 1비트를 바꾸면 출력값의 반이 변경되어야 한다. 눈사태 효과는 회전(round)이 거의 없더라도 발생해야 한다. Chapter 5 Hash Function

19 암호 해쉬 설계 (2) 효율성 암호 해쉬 함수는 여러 번의 회전(rounds)으로 구성된다.
효율적이지 않으면(시간이 많이 걸린다면) 암호를 목적으로 해쉬를 사용하는 의미가 없다. 암호 해쉬 함수는 여러 번의 회전(rounds)으로 구성된다. 블록 암호의 설계와 비슷하다. 블록 암호의 반복과 마찬가지로 상호 교환(tradeoff)이 존재한다. 계산 속도 vs. 안전도 Chapter 5 Hash Function

20 대표적인 암호 해쉬들 MD(Message Digest) 5 Rivest가 개발
입력 블록: 512bits, 출력: 128 bits MD2 → MD4 → MD5 MD2와 MD4는 충돌이 발견되어서 더 이상 안전하지 않다. 주목! MD5 조차도 최근에 충돌이 발견되었다. Chapter 5 Hash Function

21 대표적인 암호 해쉬들 (2) SHA(Secure Hash Algorithm)-1
미국 정부 표준 (MD5와 유사) “세상에서 가장 인기 있는 해쉬 함수” 입력 블록: 512bits, 출력: 180 bits SHA-0 → SHA-1 다른 많은 해쉬가 있지만, MD5와 SHA-1이 가장 널리 사용되고 있다. Chapter 5 Hash Function

22 대표적인 암호 해쉬들 (3) 여기서는 MD5 or SHA-1 대신에 Tiger hash 알고리즘을 살펴 본다.
왜냐하면 Tiger가 MD5 or SHA-1 보다 훨씬 구조적으로 설계되어 있다. Chapter 5 Hash Function

23 Tiger Hash Chapter 5 Hash Function

24 Tiger Hash Ross Anderson & Eli Biham이 개발
이름이 의미하는 것처럼 “Fast and strong” 설계 기준 안전 64-bit 프로세서에 최적화 MD5 혹은 SHA-1로 쉽게 대체 Chapter 5 Hash Function

25 Tiger Hash MD5/SHA-1과 같이, 입력값은 512 bit 블록으로 나누어진다. (마지막 블록은 패딩된다.)
MD5/SHA-1와 다르게 출력값은 192 bits (세 개의 64-bit words) 비교 MD5: 128 bit, SHA-1: 180 bit 만약 MD5 혹은 SHA-1로 대체한다면 출력값을 짜르면 된다. 중간의 회전(round)은 모두 192 bits 4 S-boxes, 각각은 8 bits를 64 bits로 “key schedule”이 사용된다. Chapter 5 Hash Function

26 Tiger 외부 회전 Input : X There are n iterations of diagram at left
a b c Xi F5 W Input : X X = (X0,X1,…,Xn-1) Xi : 512 bits There are n iterations of diagram at left One for each input block 초기 (a,b,c) : 상수 최종 (a,b,c) : hash 블록 암호와 비슷하다! key schedule c a b F7 W key schedule F9 W    a b c a b c Chapter 5 Hash Function

27 Tiger 내부 회전 각각의 Fm 은 정확히 8개 회전으로 구성된다. Fm에 512 bit 입력 W 모든 선은 64 bits
a b c 각각의 Fm 은 정확히 8개 회전으로 구성된다. Fm에 512 bit 입력 W W=(w0,w1,…,w7) wi : 64bits W is 입력 블록 Xi 중 하나 모든 선은 64 bits fm,i 은 다음 장의 S-boxes에 의해 달라진다. w0 fm,0 w1 fm.1 fm,2 w2 fm,7 w7 a b c Chapter 5 Hash Function

28 Tiger Hash: One Round fm,i 는 a, b, c, wi, m의 함수 fm,i의 출력
이전 회전(round)의 출력값 a,b,c는 이번 회전의 입력값이 된다. wi : 64-bit 블록, W=(w0,w1,…,w7) m : multiplier c = (c0,c1,…,c7): ci는 1 바이트 fm,i의 출력 c = c  wi a = a  (S0[c0]  S1[c2]  S2[c4]  S3[c6]) b = b + (S3[c1]  S2[c3]  S1[c5]  S0[c7]) b = b  m Si는 S-box: 8 bits가 64 bits로 매핑된다. Chapter 5 Hash Function

29 Tiger Hash Key Schedule
입력: X X=(x0,x1,…,x7) X의 값에 조그만 변화도 키 스케쥴 출력값은 크게 변한다. x0 = x0  (x7  0xA5A5A5A5A5A5A5A5) x1 = x1  x0 , x2 = x2  x1 x3 = x3  (x2  ((~x1) << 19)) x4 = x4  x3 , x5 = x5 +x4 x6 = x6  (x5  ((~x4) >> 23)) x7 = x7  x6 , x0 = x0 +x7 x1 = x1  (x0  ((~x7) << 19)) x2 = x2  x1 , x3 = x3 +x2 x4 = x4  (x3  ((~x2) >> 23)) x5 = x5  x4 , x6 = x6 +x5 x7 = x7 (x6  0x ABCDEF) Chapter 5 Hash Function

30 Tiger Hash 요약 (1) 해쉬값과 중간값은 192 bits 24 (3-outer X 8-inner) 회전(rounds)
S-boxes: 각 입력 비트는 3 회전 후에 a, b, c에 영향을 미치도록 설계되었다. Key schedule: 메시지에 조그만 차이가 생기면 중간 해쉬값의 많은 비트에 영향을 준다. Multiply: 하나의 회전에서의 S-box의 입력은 다음 회전의 많은 S-box에 섞이도록 한다. S-boxes, key schedule, multiply는 강력한 눈사태 효과가 발생하도록 설계되었다. Chapter 5 Hash Function

31 Tiger Hash 요약 (2) 블록 암호로부터 많은 아이디어를 빌려옴
S-boxes 반복 회전(Multiple rounds) Mixed mode arithmetic 전체적으로 Tiger는 다음의 암호의 기본 개념을 사용하고 있다. Confusion Diffusion Chapter 5 Hash Function

32 HMAC Chapter 5 Hash Function

33 HMAC (1) MAC은 메시지 무결성을 위해서 사용한다고 했다. 하지만 M과 h(M)을 같이 보낼 수는 없다.
블록 암호의 CBC 모드에서 마지막 블록의 암호문을 MAC으로 사용하다. 하지만 M과 h(M)을 같이 보낼 수는 없다. Trudy는 M을 M’ 으로 바꾸고 MAC도 다시 계산해서 h(M)을 h(M’)으로 바꿀 수 있다. 어떻게 이 문제를 해결할 수 있을까? 한가지 해법: 해쉬에 키를 사용하도록 한다. 즉, hashed MAC (HMAC) 키는 오직 송신자와 수신자 만이 알고 있다. Chapter 5 Hash Function

34 HMAC (2) 어떻게 HMAC을 계산하는가? 두가지 명백한 선택 하지만 두 경우 모두 잠재적인 문제점을 갖고 있다.
Case1: h(K,M) Case2: h(M,K) 하지만 두 경우 모두 잠재적인 문제점을 갖고 있다. Chapter 5 Hash Function

35 HMAC: Case 1: HMAC as h(K,M)
암호 해쉬 함수는 메시지를 블록으로 해쉬한다. 예: MD5, SHA-1, Tiger: 512 bits/block If M=(B1,B2), then h(M)=F(F(A, B1), B2)=F(h(B1), B2) − ① F: 임의의 함수, A : 고정 길이의 초기 상수 If M’ = (M,X) Trudy는 K를 모르더라도 ① 을 사용하여 h(K,M)으로부터 h(K,M’)을 알 수 있다. 왜냐하면 h(K,M’) = h(K,M,X) = F(h(K,M), X) 힘수 F는 알려진 함수 따라서 이것은 문제가 있다. Chapter 5 Hash Function

36 HMAC: Case 2: HMAC as h(M,K)
하지만, h(M’)=h(M)인 M’가 있으면(즉, 충돌이 있다면), ①에 의해서 h(M,K)=F(h(M), K)=F(h(M’), K)=h(M’,K) 이것은 그렇게 심각한 문제는 아니다. 왜냐하면 충돌이 있다면 이 해쉬는 안전하지 않은 것이므로 어차피 사용할 수 없을 것이다. 하지만 이것을 해결할 수 있다면 당연히 그렇게 해야 한다. Chapter 5 Hash Function

37 HMAC: 올바른 계산 약간의 수정을 통해서 앞의 문제를 회피한다. IETF 표준: RFC 2104
B : 해쉬의 블록 길이 (바이트) B = 64 byes(=512 bits) for MD5, SHA-1, Tiger ipad = 0x36을 B번 반복 and opad = 0x5C을 B번 반복 그러면 HMAC(M,K) = H(K  opad, H(K  ipad, M)) Chapter 5 Hash Function

38 HMAC MAC(text)t = HMAC(K, text)t = H((K0  opad )|| H((K0  ipad) || text))t HMAC uses the following parameters: B: Block size (in bytes) of the input to the Approved hash function. H: An Approved hash function. ipad: Inner pad; the byte x’36’ repeated B times. K: Secret key shared between the originator and the intended receiver(s). K0: The key K after any necessary pre-processing to form a B byte key. L: Block size (in bytes) of the output of the Approved hash function. opad: Outer pad; the byte x’5c’ repeated B times. t : The number of bytes of MAC. text: The data on which the HMAC is calculated; text does not include the padded key. The length of text is n bits, where 0 <= n < 2B - 8B. x’N’: Hexadecimal notation, where each symbol in the string ‘N’ represents 4 binary bits. || : Concatenation  : Exclusive-Or operation. Chapter 5 Hash Function

39 STEP-BY-STEP DESCRIPTION
HMAC MAC(text)t = HMAC(K, text)t = H((K0  opad )|| H((K0  ipad) || text))t STEPS STEP-BY-STEP DESCRIPTION Step 1 If the length of K = B: set K0 = K. Else adjust K ; Step 2 –Step 3 omit Step4 Exclusive-Or K0 with ipad to produce a B-byte string: K0  ipad. Step 5 Append the stream of data 'text' to the string resulting from step 4: (K0  ipad) || text. Step 6 Apply H to the stream generated in step 5: H((K0  ipad) || text). Step 7 Exclusive-Or K0 with opad: K0  opad. Step 8 Append the result from step 6 to step 7: (K0 opad) || H((K0  ipad) || text) Step 9 Apply H to the result from step 8: H((K0  opad )|| H((K0  ipad) || text)). Step 10 Select the leftmost t bytes of the result of step 9 as the MAC. Chapter 5 Hash Function

40 Chapter 5 Hash Function

41 Hash의 응용 Chapter 5 Hash Function

42 Hash의 응용 인증 (HMAC) 메시지 무결성 (HMAC) 메시지 지문(fingerprint)
데이터 훼손 (corruption) 발견 효율적인 전자 서명 Chapter 5 Hash Function

43 온라인 경매(Online Auction)
입찰자(bidder): Alice, Bob, Charlie Alice는 A, Bob은 B, Charlie는 C에 입찰을 했다. 하지만 그들은 자신들의 입찰가가 비밀로 지켜지는 것을 신뢰할 수 없었다. 해법? Alice, Bob, Charlie는 해쉬값 h(A), h(B), h(C)을 제출한다. 이들이 제출한 해쉬값은 모두 온라인으로 공고한다. 그리고 입찰가를 제출한다. 해쉬값으로 입찰가를 알 수 없다.(one way) 해쉬값을 제출한 후에 입찰가를 변경할 수 없다. (collision) Chapter 5 Hash Function

44 스팸 감소(Spam Reduction) 내가 너로부터 전자메일을 받기 전에, 네가 전자메일을 작성하기 위해 약간의 “노력”을 했다는 것을 증명해라. (예, CPU cycles) 보낼 수 있는 전자메일의 양을 줄일 수 있다. 스팸을 보내는데 상당한 노력이 필요하도록 한다. 이것은 해쉬값을 계산하는 방법으로 할 수 있다. Sender: 일의 양은 요구하는데 달려 있다. Receiver: 단지 간단한 일만을 수행한다. Chapter 5 Hash Function

45 스팸 감소(2) (M, R, T)로부터 해쉬를 계산한다. Sender는 반드시 다음과 같은 R을 찾는다.
M = 메시지 R = 결정해야 하는 값 T = 현재 시간 Sender는 반드시 다음과 같은 R을 찾는다. hash(M,R,T) = (00…0,X), 해쉬값의 처음 N 비트는 모두 zero이다. Sender는 (M,R,T)을 보낸다. 수신자는 다음의 조건을 만족하면 이메일을 받아 들인다. hash(M,R,T)의 값의 처음 N 비트가 zero로 시작한다. N Chapter 5 Hash Function

46 스팸 감소(3) 송신자가 R을 찾는데 필요한 일의 양 수신가가 검증하는데 필요한 일의 양 2N hashes
Sender’s work increases exponentially in N 수신가가 검증하는데 필요한 일의 양 1 hash – 단지 hash(M,R,T)의 처음 N 비트가 zero인지 아닌지 확인하면 된다. N에 상관없이 수신자는 같은 일을 하면 된다. Chapter 5 Hash Function

47 스팸 감소(4) 어는 정도 길이의 N을 선택하면 적당할까? 보통의 이메일 사용자가 받아드릴 수 있을 정도의 일의 양
스패머(spapper)들에게는 감당할 수 없을 정도의 일의 양! Chapter 5 Hash Function