Sevity Blog

해시함수의 기본적인 내용에 대해서는 이전 글(http://sevity.tistory.com/21) 참조

자세한 설명에 들어가기전에 다음 예제를 살펴보자.

철수는 영희에게 중요한 문서를 전달할 예정이다.

그런데 누군가 중간에서 그 문서의 내용을 해킹으로 바꿀 수 있기 때문에, 문서내용에 대해서

(string to int) hash function을 적용해서 오프라인으로 해시값을 알려주기로 했다. 

이 해시값을 42라고 해보자.

영희는 문서를 전달받은다음, 철수와 동일한 hash function을 적용해서 42라는 값을 얻었고, 문서가 해킹당하지 않았음을 확신했다.

위와 같은 시나리오로 보안에서 해시가 사용되는 거시다.

그런데 만약 해시값인 42로 부터 원본 문서의 내용을 일부라도 유추할 수 있다면 어떻게 될까..

예를 들어 해시값이 4로 시작하면 원본 문서의 내용에 money라는 단어가 들어간다던가..

이런일이 있으면 안되기 때문에 해시값으로 부터 원본의 내용을 찾는게 계산상 어렵도록 hash function을 설계해야 한다.

이러한 공격을 제1역상 공격이라 하며, 이에 저항하기 위해 hash function이 가져야 하는 성질을 제1역상저항성(preimage resistance)이라 한다.

그런데, 또 다른 예를 살펴보자.

해커가 제1역상 공격을 통해 원본 내용을 찾는것은 불가능하더라도, 

여러가지 문서들을 hash function에 넣어보면서 42라는 같은 결과가 나오는 전혀다른 문서를 찾는다면 어떻게 될까?

이런게 가능하다면 영희는 해시값이 42로 동일하기 때문에 문서내용이 바뀌어도 모를 수 있을 것이다.

(단 이런 공격을 시도 하려면 hash function이 공개되어 철수/영희가 사용하는 것과 해커가 사용하는게 같아야 한다는 전재조건이 붙는다)

위와 같은 공격을 제2역상공격이라 하며, 이를 막기위해 입력의 해시 값을 바꾸지 않으면서 입력을 변경하는 것이 계산상 어렵도록 hash 함수를 설계해야 하며 이를 제2역상저항성(second preimage resistance)이라 한다.

위의 제2역상 공격은 사실 해시 함수의 충돌(collision)이라는 약점을 파고드는 것인데,

해시 함수는 더 큰 인풋(문서내용)을 더 작은 아웃풋(숫자하나)로 바꾸는 과정이기 때문에 충돌이 아예 없을수는 없다.

하지만 같은 해시 값을 생성하는 두 개의 입력값을 찾는 것이 계산상 어려워야 하며 이를 충돌 저항성(collision resistance)이라 부른다.

즉, 입력값과 해시 값에 대해서, 해시 값을 망가뜨리지 않으면서 입력값을 수정하는 공격에 대해 안전해야 한다. 이러한 성질을 가지는 해시 값은 원래 입력값을 의도적으로 손상시키지 않았는지에 대한 검증 장치로 사용할 수 있다.

좀더 알기쉽게 표현하자면 인풋의 일부만 바뀌어도 결과값이 크게 바뀔때 위의 속성들을 만족하는 좋은 해시라고 보통 표현을 하게된다.

또다른 예로는 패스워드를 암호화하는 것을 들 수 있다.

일방향이고 리버스 엔지니어링이 힘들다는 역상저항성을 활용해서, 주민번호나 패스워드를 직접 DB에 저장하는 대신 해시값을 저장하게 되면,

운영자에게 비밀번호나 주민번호를 노출하지는 않으면서도 로그인 보안은 구현할 수 있게 된다.

(물론 여기서도 전혀다른 비밀번호가 같은 해시값을 도출하게되는 제2역상공격이 성공하게 되면 큰일이다)

hash라고 했을때 헷갈리는 이유는 

자료구조로서 hash map (hash table) 과 

그 핵심함수인 hash function 이 헷갈려서 그런 이유가 크다.

비트코인에는 hash function이 내부적으로 사용된다.

자료구조로서 hash map은

key와 value가 있는데, key를 주면 value를 빠르게 토해내는 컨테이너..

기능으로 보자면 stl map이나 python dict 등과 비슷하다고 볼 수 있다.

단 map이나 dict는 보통 tree(그 중에서도 레드-블랙트리가 일반적)로 구현된다.

tree는 O(log N)의 복잡도를 가져서 hash의 O(1)보다 느리지만, 사용량에 따라 가변적으로 메모리를 할당하기 유리하기 때문.

거꾸로 말하면 hash는 미리 상당한 양의 메모리를 덩어리째 할당해야하는 구조라 trade-off가 있다고 볼 수 있다.

hash map은 O(1)의 속도를 위해서 쓰는것은 자명한데.. 어떤것이 빠른거냐.

Insert,Update,Delete,Search

위 네 가지 연산 모두 O(1)이다.

(물론 메모리공간을 처음에 충분히 할당한 경우이며, worst case 시나리오에서 collision이 발생하면 실제로는 이보다 느려질 수 있음)

c++에서는 stl map 을 쓰면 내부구현에 tree가 보통 사용되고, 내부적으로 tree가 아닌 hash가 사용되도록 하고 싶으면 unordered_map을 쓰면된다.

핵심함수인 hash function은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 

이게 무슨 뚱딴지 같은 소리인가 하겠지만.. 

일단 이해를 돕기위해 string to int hash function의 예를 들어보자.

임의의 string이 들어왔을때 1024이하의 숫자하나로 매핑이 된다고 해보자.

예를 들면 "Kim Wonil"이 들어왔을때 42로 매핑이 되고,

"Lee Hana"가 들어왔을때 27이 매핑되는 식이다.

이런걸 만들어서 어따가 쓸까..

1. hash map 자료구조를 hash function을 통해서 만들면 O(1)로 매우 빠른 자료구조를 만들수 있다.

2. 긴 길이의 데이터를 짧은 길이의 숫자로 바꿔주는 구조로 인해서 변경내용이 있는지 확인하는데 쓸 수 있다.

예를 들어서 겉보기에는 매우 비슷한 소스코드 두 개가 있다고 해보자.

그런데 둘의 내용이 일치하는지 아닌지 확실하지 않다고 해보자.

그러면 나이브한 방법으로는 두 파일을 바이트 단위로 비교하는 방법이 있을 것이다.

그런데 이렇게 나이브하게 하지 않고, 두 파일의 내용에 대해 각각 (string to int) hash function을 적용한다음 결과로 나온 숫자를 비교하는 방법도 있다.

예를 들어 첫번째 파일에서는 내용으로 해시한 결과값이 42인데 두번째 파일로 나온 값은 27이라면 두 파일의 내용은 확실히 다르다고 판정할 수 있다.

단, 해시값이 예를 들어 42로 동일하다고 해도 반드시 두 파일의 내용이 같다고 역으로 보장해주지 않는다.

이는, 큰 숫자를 작은숫자로 매핑하는 과정에서 반드시 충돌이 발생할 수 있다는 점을 상기해 보면 쉽게 이해가 된다.

이를 다시 적어보면 다음과 같다.

두 해시 값이 다르다면 그 해시값에 대한 원래 데이터도 달라야 한다. (역은 성립하지 않는다)

해시 함수의 가장 기본적인 성질은 두 해시 값이 다르다면 원래의 데이터도 다르다는 것이다. 이 특징은 해시 함수가 결정적이기 때문이다. 

위의 내용중 바이트 단위로 비교한다는 나이브 접근이 심각해보이지 않을 수도 있는데, 

단 두개의 문서를 비교할때는 심각성이 크지 않을 수 있지만,

예를 들어 특정폴더에 있는 파일중 내용이 같은파일이 있는지 검사하는 프로그램을 짠다고 해보자.

나이브한 방법으로는 파일의 갯수가 n개라면 모든 pair에 대해서 n(n-1)/2번 비교를 해야 중복파일 여부를 알 수 있다. 즉 $O(n^2)$

그런데 위의 해시함수를 사용한 방법으로는 해시함수값 끼리만 숫자비교를 하면 되기 때문에 $O(n)$ 으로 수행속도를 줄일 수 있다.

3. 함호학이나 비트코인에서 사용되는 해시 함수는 관련글(http://sevity.tistory.com/22) 참조

http://www.partow.net/programming/hashfunctions/index.html

위링크에 가보면 엄청 많은 종류의 해시펑션을 제공함..