[Cryptography] 10. Hash Function

◉ Hash function 

hash function 출처 : 위키피디아

Hash function 은, 임의의 길이를 입력으로 받아서 항상 fixed length string으로 리턴해주는 함수이다. 

 

단순히 길이만 fixed length로 리턴해 주는것이 아니라, 모든 입력값이 서로 다른 hash value (hash function의 함수값)을 갖는다.  

 

예를 들어, 

 

1. Input : Justin Seo => gaf34r3

2. Input : Justin Suo => wefnf33

 

이렇게 Plain Text 에서 단순히 하나의 값만 바꿔도, 해시값이 통채로 바뀌게 되버린다. 

 

해시함수를 비유하자면, 엄청 큰 정보의 문서를 구겨버려서(Crush) 해버려서 작게 압축해버리는 것과 비슷한 맥락이라고 볼 수 있겠다.

 

◉ 이 Hash Function은 그러면 어디다가 쓸까?

 

Hash function은 주로 메시지의 무결성(Integrity) 를 확인할때 사용한다. 

 

내가 상대방에게 메시지와 해시값을 보내면, 

 

상대방은 메시지가 중간에 바뀌었는지 재 점검하기 위해서 해시함수에 넣어 돌려보고, 해당 해시값이 나오면 안심할 수 있을 것이다. 

 

◉ Hash Collision

해시 충돌

 해시함수의 입력이 대체로 출력보다 길기때문에, 이론상으로는 서로 다른 입력으로 같은 출력을 갖는 상황이 있을 것임을 짐작할 수 있다. 

이런 상황을 Hash Collision (해시 충돌)이라고 한다. 해시 충돌은 이론상으로 가능하나, 실용적으로 사용되는 해시함수의 해시충돌은 매우매우 적은 확률을 갖는다.

 하지만 이 해시 충돌은 암호학 관점에서 굉장히 위험하다. 예를들어 MD5 라는 해시 함수는, 2004년 경, 중국인들에 의해서 해시 충돌의 알고리즘이 밝혀져 이제는 못쓰는 해시 알고리즘이 되기도 하였다. 

 

 

◉ Hash Algorithm의 종류

 

유명한 종류만 언급하자면, MD5, SHA-1, SHA-2, SHA-3 등이 있다.

이중 MD5 는 2004년부로 사실상 퇴출되었다.

 

짧게 덧붙이자면, 

MD5는 항상 128비트의 고정 길이로 해시값을 출력하고,

SHA-1 은 160비트의 고정 길이로 해시값을 출력,

SHA-2 는 224, 256, 384, 512 등의 고정길이로 해시값을 출력할 수 있다.

 

 

SHA 

 

 

◉ MAC 과 HMAC

 

MAC 과 HMAC 은 Hash 의 종류가 아니라, 메시지의 진위판별, 즉 Integrity를 검증하기 위해 확인하는 것이다. 

 

 

☞ MAC : Message authentication code 

 

MAC 은 일반적인 암호화 알고리즘보다 훨씬 빠르다. 다른점은, 메세지가 외부에 노출된다는 것, 그리고 reversible 하지 않다는 것이다.

 

MAC 을 사용하는 입장에서, 굳이 출력값을 reverse 할 필요가 없다. 

 

메세지가 외부에 노출되도 상관 없고, 수신자가 메세지의 진위 여부를 판별하고 싶을때 사용할 수 있는 가장 효율적인 방법이다. 

 

시나리오를 예를 들면, 

 

 Justin 은 수신자 Sidney 에게 메세지 M을 보내려고 한다. 이 때 메시지 인증을 위해 자신의 메시지 M을 해시 한 C를 메세지 M에 덧붙여서 (M, C)를 Sidney 에게 보낸다. Sidney는 이를 받아서 M을 해시해서, 자신이 받은 C의 값과 비교해본다. 두 값이 같다면 Sidney는 메세지가 변경되지 않았다고 확신할 수 있다. 

 

☞ HMAC : Hashed Based message authentication code

 

아래와 같은 해시 연산으로, 메시지를 수신하는 상대방이 메시지의 진위여부를 판별 할 수 있는 방법이다.

 

HMAC

식이 복잡하지만, 위 방법으로 Confusion 과 Diffusion을 모두 만족하는 해시값을 출력할 수 있다.

 

예를들어, ipad 와 opad로 bitwise XOR 연산을 하는 이유는 diffusion 을 위해서이다.