Hash Algorithm

원태연·2023년 1월 4일

CS algorithm

Hash

Hash는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다.

Input Data -> [Hash function] -> Hash key, Hash code

이때, 단순히 지정한 크기로 변환하는 것 뿐만 아니라 아래와 같은 특징을 가져야 한다.

Hash의 특징

어떤 입력 값에도 항상 고정된 길이의 해시 값을 출력한다.
입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력한다.
출력된 결과 값을 토대로 입력 값을 유추할 수 없다.
입력 값은 항상 동일한 해시 값을 출력한다.

Hash 활용

위와 같은 특징 가진 해시를 다양하게 활용하고 있다.

Hash Table

Key와 Value를 Mapping해둔 자료구조 이다. Key값의 해시코드를 주소로 하는 위치에 값을 저장하고, 접근할 때는 특정 Key를 해싱하여 값에 접근하도록 한다. 접근 성능은 해시 함수에 의존하지만, 대부분의 해시 함수는 상수 시간 복잡도를 가지기 때문에 다른 자료구조에 비해 빠른 접근 속도를 가진다는 장점이 있다.

Hash Collision

해시 함수의 성능에 따라 다른 입력값에 대해 동일한 해시코드가 생성될 수 있다.
$h(k) = h(13k)$ 처럼, $k$ 의 해싱결과 값과 $13k$ 의 해싱 결과가 동일할 수 있다.
해시 함수가 서로 다른 입력값에 대해 동일한 결과를 출력하는 경우를 해시 충돌(Hash Collision)이라고 한다.

이런 충돌을 해결하는 여러 방식이 존재한다.

분리 연결법(Separate Chaining)

해시테이블의 크기를 유연하게 만들어 해결한다. John Smith와 Sandra Dee의 해시값이 152로 동일하다. 이 경우, 버킷(bucket)의 데이터에 대해 연결 리스트, 트리 등의 자료구조를 활용해 동일한 해시값을 가지는 데이터에 대하여 다음 데이터의 주소를 저장하는 것이다.

데이터의 수가 많아지면 동일한 버킷에 chaining 되는 데이터가 많아지며 해시 테이블의 장점인 데이터 접근 효율성이 감소한다는 단점이 발생 할 수 있다고 한다.

개방주소법(Open Addressing)

개방주소법은 충돌이 일어난 해시를 비어있는 테이블에 저장하는 기법이다.

아까와 동일하게 John Smith와 Sandra Dee의 해시값이 충돌이 일어났다. 그래서 Chaining 방법과는 다르게 [index:152 버킷]에 모두 저장하는 것이 아닌, 그 아래 비어있는 [index:153 버킷]에 저장하였다.

또, Ted Baker의 해시값은 153으로 동일하게 충돌이 일어났지만, 위 전략과 동일하게 그 다음 해시에 저장했다.

Open Addressing는 비어있는 해시를 찾는 규칙에 따라 다음과 같이 구분할 수 있다.

선형 탐색(Linear Probing): 다음 해시(+1)나 n개(+n)를 건너뛰어 비어있는 해시에 데이터를 저장한다.
제곱 탐색(Quadratic Probing): 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장한다.
이중 해시(Double Hashing): 다른 해시함수를 한 번 더 적용한 해시에 데이터를 저장한다.

당연하게도, 한 해시테이블에 대해선 동일한 전략을 취해야 한다는 점이다.

Open Addressing는 다른 저장공간의 확장 없이 해시테이블 내에서 데이터 저장 및 처리가 가능하다는 장점이 있지만, 데이터 많아질수록(빈 테이블이 없을 수록) 성능이 Worst case에 가까워질 수 있다는 단점이 존재한다.

해시 버킷 동적 확장(Resize)

메모리 사용에 있어 여유가 있다면, 해시 버킷의 크기 자체를 확장하는 해결책도 존재한다. 이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다. Java의 HashMap에서도 Resize를 확인 할 수 있다. 저장된 데이터의 개수가 해시 버킷 크기의 75%를 넘어서면, 두 배로 확장한다.

임계점은 load factor

이러한 해싱 충돌 때문에, 해시 테이블의 탐색, 삭제, 삽입에 대해 항상 상수의 시간복잡도를 보장하지 않는다는 것을 주의하자. 최악의 경우, $O(n)$ 의 시간복잡도를 가질 수 있다.

Hashing 알고리즘과 보안

해싱 함수의 성능은 해시 테이블 뿐만 아니라 활용되는 모든 부분에 대해 영향을 끼친다. 좋은 함수, 알고리즘은 충돌이 일어날 확률이 매우 적으면서도 Key값과 해시값의 관계를 알아낼 수 없어야 한다. 이러한 성능이 고도화 되고, 안전성을 검증 받으면 암호학에서도 해싱이 활발하게 사용된다고 한다.

암호학에서 사용되는 해싱 함수는 다음과 같은 특징을 가짐을 인증 받아야 한다고 한다.

역상 저항성(preimage resistance): 해시 값을 생성해낸 입력값을 찾는 것이 어려움
제 2 역상 저항성(second preimage resistance): 어떤 입력값에 대한 해시 값을 유지 하며, 입력값을 수정하는 것이 어려움 (충돌)

충돌 저항성(collision resistance): 해시 충돌에 대해 안전해야 함.
단방향 암호화(one-way encryption): 복호화가 불가능하여야 하며 해시값을 가지고 원본값으로 역산할수 없어야 함.
눈사태 효과(avalanche effect): 입력값의 아주 작은 변화로도 해시값이 전혀 다른 값이 나와야 함.

이러한 특징을 가지는 해싱 알고리즘은 다양하게 존재한다.

MD5 (Message-Digest algorithm 5)

임의의 길이를 입력받아 128bit 길이의 해시값을 출력한다.
자주 활용되었지만, 현재는 심각한 보안 문제로 인하여 MD5를 보안 관련 용도로 사용하지 않는다.
추가적으로 2008년에는 MD5의 결함을 이용해 SSL 인증서를 변조하는 것이 발견되었다.

SHA (Secure Hash Algorithm)

1993년부터 미국 NSA가 제작하고 미국 국립표준기술연구소(NIST)에서 표준으로 채택한 암호학적 해시 함수이다.
SHA-0을 시작으로 SHA-1, SHA-2 등 다양한 차세대 버전이 등장하고 있다. 해시 충돌을 이용한 위험성이 발견되며 점점 개선한 버전들이 등장하고 있다.
현재는 SHA-2 버전을 많이 사용한다고 한다. 해시 길이에 따라 SHA-256, SHA-384, SHA-512 비트를 선택해서 사용할 수 있고, 당연히 해시 길이가 길수록 해시 충돌로부터 안전하다고 한다.