Chapter 5 해쉬 함수

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

왜 해쉬 함수를 사용하는가? 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

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

암호 해쉬 함수 약한 충돌 방지(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

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

생일 문제(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

생일 문제 Chapter 5 Hash Function

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Tiger Hash Chapter 5 Hash Function

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

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

Tiger 외부 회전 Input : X There are n iterations of diagram at left 64 64 64 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

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 : 입력 블록 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

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

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  0x0123456789ABCDEF) Chapter 5 Hash Function

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

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

HMAC Chapter 5 Hash Function

메시지 인증 MAC은 메시지 무결성을 위해서 사용한다고 했다. MAC으로 사용할 수 있는 한가지 예 블록 암호의 CBC 모드에서 마지막 블록의 암호문을 MAC으로 사용하다. 하지만 M과 h(M)을 같이 보낼 수는 없다. Trudy는 M을 M’ 으로 바꾸고 MAC도 다시 계산해서 h(M)을 h(M’)으로 바꿀 수 있다. 어떻게 이 문제를 해결할 수 있을까? Chapter 5 Hash Function

메시지 인증 코드(MAC) 메시지 무결성을 증명 암호화는 없음 ! 하지만 송신자 인증은 안된다. message H( ) compare 메시지 무결성을 증명 암호화는 없음 ! 하지만 송신자 인증은 안된다. 해쉬를 사용하여 메시지 다이제스트(Message Digest) Chapter 5 Hash Function

HMAC s = shared secret 송신자와 수신자 사이에 비밀값을 공유하고 있다. message H( ) s compare s = shared secret 송신자와 수신자 사이에 비밀값을 공유하고 있다. 송신자를 인증한다(authenticate) 메시지 무결성을 증명 암호화는 없음 ! “keyed hash”라고도 불리움 MDm = H(s||m) ; 전송 m||MDm

HMAC (RFC 2104) 널리 사용되고 있는 MAC 표준 MD5나 SHA-1 해쉬 함수와 함께 사용될 수 있다. 응용 예: OSPF 공격 메시지 삽입 메시지 제거 메시지 수정 어떻게 라우터는 전송받은 메시지가 진짜인지 알 수 있는가?

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

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

HMAC(참고) HMAC uses the following parameters: 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

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

Chapter 5 Hash Function

Hash의 응용 Chapter 5 Hash Function

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

온라인 경매(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

네트워크 상에서 홀짝 게임 하기 Alice와 Bob은 전화 통화를 하고 있다. 둘은 영화를 보러 갈지 야구를 보러 갈지 결정을 하려고 한다. 서로 의견의 일치를 보지 못해서 동전 던지기로 결정하기로 했다. 만약 동전의 앞이 나오면 영화를 보고 동전의 뒤가 나오면 야구를 보기로 했다. 어떻게 전화 상에서 이것을 결정할 수 있을까? Chapter 5 Hash Function

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

스팸 감소(2) (M, R, T)로부터 해쉬를 계산한다. Sender는 반드시 다음과 같은 R을 찾는다. M = email 메시지 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

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

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

메시지 다이제스트를 이용한 디지털 서명 + equal ? Alice는 디지털 서명의 진위를 증명한다. Bob은 디지털 서명한 메시지를 전송한다. Alice는 디지털 서명의 진위를 증명한다. large message m H: Hash function KB(H(m)) - encrypted msg digest H(m) digital signature (encrypt) Bob’s private key large message m K B - Bob’s public key digital signature (decrypt) K B + KB(H(m)) - encrypted msg digest H: Hash function + H(m) H(m) equal ?