해시
* 혹시 #을 찾아오셨다면 #을 복사하셔서 검색창에 넣고 Go하시면 됩니다.
Hash Function 또는 이것을 사용하여 생성한 값(Hash Value)
Hash function은 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 말한다. 이러한 Hash function 을 적용하여 나온 고정된 길이의 값을 Hash value 라고 한다. 이 값은 또한 Hash code, hash sum, checksum[* 의미는 살짝 다르지만 hash가 checksum과 동일한 목적으로 사용되는 경우도 많기는 하다.] 등으로도 불린다. ~~MD5 배틀을 할 때 사용한다.~~
Hash Function은 보통 그리 복잡한 알고리즘으로 구현되지 않기 때문에, 상대적으로 *****U, 메모리같은 시스템 자원을 덜 소모하는 특성이 있다. 그리고 같은 입력값에 대해서는 같은 출력값이 보장되며, 이 출력값은 가능한 고른 범위에 균일하게 분포하는 특성이 있다. 특수 목적 용으로 Hash Value를 생성하는 원본과 별도의 값을 입력받아서 같은 입력에 대해 다른 출력값을 가지게 하는 Hash function도 존재한다.
Hash function은 보통 입력값의 범위보다 출력값의 범위가 좁은 경우가 많기 때문에 입력이 다름에도 불구하고 드물게 동일한 값이 출력되는 경우도 존재한다. 이러한 경우를 충돌(Collision)한다고 한다.
이러한 특성에 힘입어 여러 다양한 목적에 맞게 설계된 Hash Function이 존재하며 이들은 다음과 같은 다양한 분야에서 매우 유용하게 사용된다.
* 자료구조 * Hash Table * Hash Set * Bloom Filter * 캐시 * 중복 레코드 검색 * 유사 레코드 검색 * 유사 부분 문자열 검색 * 기하학적 Hash * 변조 탐지/에러 검출[* 프로그램, 특히 오픈소스 프로그램을 다운받을 때 md5sum, sha1sum, sha256sum 등으로 bacc82b32fe8b8b45c9225f129196943 과 같은 요상한 문자열을 같이 표기해 놓은 것을 볼 수 있다. 이게 이 목적으로 사용되는 Hash Value 이다.]
근래에 나오는 언어들은 기본 라이브러리에 해쉬함수가 포함되어 있는 경우가 많아서 굳이 구현할 필요없이 바로바로 해쉬값을 추출해서 사용할 수 있다. 다만 좀 오래된 언어들은 확장 라이브러리를 설치하거나 직접 구현하는 식으로 해결해야된다. 파이썬의 경우에도 사전에 클래스를 넣기 위해서는 해쉬함수를 구현해야 하는데, 해쉬함수와 함께 비교함수(cmp)도 구현해야 한다. 만약 해쉬함수가 구현되어 있지 않다면 그 객체의 주소값을 해쉬값으로 대체한다.
유명한 해쉬 알고리즘으로 Message-Digest Algorithm(MD)과 Secure Hash Algorithm(SHA) 등이 있다. 각 알고리즘은 심각한 해시 충돌 문제 등으로 인해 해시 함수를 개선하며 발표된 순서대로 MDn, SHA-n 식으로 넘버링된다. date기준으로 최신 버전은 각각 MD6, SHA-3이나 보통은 자신이 사용하는 언어에서 제공하는 라이브러리에 포함된 기본 해쉬 함수[* MD5나 SHA-1을 기반으로 구현된 사례가 많다.]를 사용하는 편이다.
Hash 를 사용하는 자료구조
색인(Index)에 Hash Value를 사용하는, 빠른 검색, 빠른 삽입이 특징인 자료구조이다.
일반적으로 대량의 연속된 데이터를 저장하고 관리할 경우 wiki:"리스트(자료구조)"리스트를 사용하지만 이 경우 데이터를 정렬해서 관리해야 된다는 전제조건이 따라붙는다. 정렬되지 않은 데이터는 리스트의 처음부터 끝까지 다 뒤져봐야 되는 비효율적인 상황이 발생하기 때문이다. 하지만 정렬 알고리즘을 아무리 효율적으로 짠다고 하더라도 결과적으로 데이터량이 늘어나면 결국 효율성이 떨어지는 것은 마찬가지이다.
이로 인해서 정렬을 하지 않고도 빠른 검색과 삽입이 가능한 방법을 연구했고 이를 위해 사용한 것이 해쉬이다. 해쉬는 리스트를 사용하는 접근법은 동일하지만 여기에 색인 개념이 추가되어 있다. 일단 충분히 큰 공간을 할당받은 다음 해쉬함수를 이용하여 고유 색인을 생성한다. 그리고 이 고유 색인과 맞는 위치에 데이터를 저장한다.
예로 설명하면 0 ~ 10000까지 데이터를 담을 수 있는 리스트를 생성하고, 엔하위키란 단어에 해쉬함수를 적용하여 2642란 색인이 생성되면 리스트 2642번 index에 엔하위키를 저장하는 방식이다. 해쉬함수는 언제나 동일한 해쉬값을 리턴하기 때문에 엔하위키를 입력하면 항상 2642란 색인이 나오므로 굳이 정렬하지 않고도 바로 찾을 수 있게 되는 셈. 단, 이러한 목적으로 사용하는 Hash Function 은 Hash Value 를 계산하는 비용이 기존 검색 알고리즘에 비해 훨씬 적고 뛰어나야 한다는 전제조건이 붙는다. 안그러면 이러한 방법을 사용하는 의미가 없다.
물론 상술한 것처럼 Hash 값에 충돌이 발생하므로 같은 색인이 만들어지는 경우도 있다. 예를 들어 나중에 입력된 위키위키 단어를 해쉬함수에 넣었더니 2642란 색인으로 나온다면 엔하위키와 동일한 색인을 가지게 되는 문제가 발생한다. 이 경우에는 위키위키를 2643번 색인에 기록하거나, 혹은 2642번 색인을 연결 리스트 형식으로 구성하여 엔하위키 뒤에 위키위키를 연결하는 식으로 해결하기도 한다. 어느 쪽이든 해당 색인을 찾아갔는데 일치하지 않을 경우 다음에 위치한 데이터를 한 번 더 찾아가면 되므로 빠른 검색이란 특징을 훼손시키지 않는다. [* 충돌이 발생할 경우 빠른 검색이라는 특징은 훼손된다. 위의 2642 색인의 예를 들면, 충돌 발생시 2643에 기록할 경우, 이후 2643의 색인을 갖는 자료값도 충돌을 일으킨다. 또한 나중에 2642 색인을 가진 자료값이 삭제된다 하더라도, 이미 이로 인해 충돌이 발생한 자료값들은 자동으로 복구되지 않으므로, 충돌이 발생함에 따라, 자료구조의 성능은 점차 떨어지게 된다. 일반적으로 50%이상의 수용률, 위의 경우에는 5000개 이상의 데이터,이 예상되는 환경에서는 충돌확률에 따른 성능저하 때문에 해쉬를 사용하는 자료구조를 권장하지 않는다.]
보안과 Hash
해쉬 자체는 보안분야에서도 널리 사용되는데 해쉬함수의 특성이 원래의 문장을 복호화할 수 없게 뭉개버린다는 장점 때문이다. 그 때문에 해쉬값을 저장해놓으면 아무리 용을 써도 이미 뭉개진 원문을 복원하는 것은 불가능하다. 따라서 비밀번호와 같은 민감한 자료들을 암호화할 때 주로 사용한다. 하지만 복호화가 안된다는 것 뿐이지 상술한 해시 충돌을 이용한 공격방법을 통해 우회적으로 뚫어버릴 수가 있다. 간단히 내 비밀금고를 열 수 있는 열쇠가 내가 의도한 것은 아니지만 시스템 레벨의 문제로 하나 더 존재할 수도 있다는 의미이다.
보안 분야에서는 이것이 매우 민감한 문제에 해당하지만 해쉬값의 경우에는 길이가 정해져있으므로 결국 해쉬값의 전체 개수는 정해져 있다. 반면 사람이 조합해낼 수 있는 문장의 가지수는 무제한에 가깝기 때문에 어쩔 수 없이 해쉬 충돌이 발생하게 된다. 또한 표준안으로 지정된 해쉬 함수의 경우에는 해쉬 값을 생성하는 규칙이 공개되어 있으므로 누군가 작정하고 파고들어서 해쉬 충돌을 생성할 수 있는 정형화된 규칙까지 발견되기도 한다. 결국 이 충돌 문제로 인해 지속적이고 반복적으로 새로운 해쉬 함수가 개발되고 있는 실정이다.
현재(date 기준)까지 개발된 거의 모든 함수는 해시 충돌의 문제가 확인된 상태이며 아직까지 해시 충돌을 발견하지 못한 함수는 SHA-3가 유일한 상황이다..
