[Crypto] Hash Collision

Hash Collision에 대하여

Hash Collision, 우리 말로 하면 해시 충돌이다. 해시 충돌이란 어떤 해시 함수가 서로 다른 두 입력에 대해 동일한 출력 값을 나타내는 경우를 말한다. 보통 해시 함수는 다수의 데이터가 있을 때 이들을 구별하고 특정 데이터의 검색을 빠르게 하기 위해 사용되는데, 이 때문에 해시 충돌이 많이 일어나는 해시 함수일수록 그 질이 낮다고 평가된다(서로 다른 데이터를 구분하고 검색하는 비용이 증가하기 때문)

Hash Collision의 예를 들자면 다음과 같다. 입력으로 받은 데이터를 정수 0부터 15까지의 해시 값으로 매핑해주는 해시 함수가 있다고 가정하자. 재수없게 해시 충돌이 발생한다면 다음 그림과 같은 상황일 것이다.

해싱을 했을 때 하나의 데이터당 하나의 해시 값이 매핑되는 것이 이상적이지만 그림처럼 두 개 이상의 데이터가 같은 해시 값을 갖는 경우를 해시 충돌이라고 부르며 해시를 사용하는 입장에서 썩 좋은 컨디션은 아니다.

해시 충돌이 일어나는 근본적인 이유는 “비둘기집 원리” 때문이다. 이산 수학에서 기본 개념으로 등장하지만 심심하면 걸어놓은 링크에 증명법도 함께 있으니 읽어보는 것을 추천한다. 그러니까 해시 함수에 입력할 수 있는 데이터의 가짓수는 무한한데, 출력으로 나올 수 있는 해시 값이 유한하기 때문에 발생한다는 것이다.

여담으로, 이러한 해시 충돌 문제를 해결하기 위해 연결 리스트를 이용하는 체이닝(chaining) 과 오픈 어드레싱(open addressing) 이 등장했지만 이들은 해시 함수가 주는 이점인 상수 시간의 시간 복잡도 를 깨기 때문에 잘 쓰이는지는 모르겠다. 데이터베이스나 다른 알고리즘 등에서 성능 개선의 목적으로 사용하는 상황에서 해시 충돌은 성능 저하에 따른 비용 증가 때문에 귀찮아진다는(?) 것에서 끝나지만 암호학에서 해시 암호에 대한 해시 충돌은 여러모로 골치아픈 문제를 일으킨다.

해시 암호와 Hash Collision

해시 암호 는 말 그대로 해시를 암호화에 쓰는 것이다. 해시 값만 가지고는 해시 함수에 들어왔던 평문 텍스트와의 관계성을 찾기 매우 어렵다는 특징 때문에 사용한다. 해시 값과 평문의 연관성을 찾기가 얼마나 어려운지 알고싶다면 여기 에서 직접 해시 암호화를 해보면 좋을 것 같다.

해시 암호는 지켜야하는 세가지 성질이 있는데 그 중 하나가 바로 충돌 저항성(collision resistance)이다. 이름에서 알 수 있듯이 해당 해시 함수가 해시 충돌에 대해 안전해야 한다는 것. 물론 앞서 설명한 비둘기집 원리 에 의해 해시 충돌이 전혀 1도 없는 해시 함수를 만드는 것은 불가능하다. 때문에 보통 “해시 충돌에 대해 안전하다” 라는 말의 기준은 대충 “어떤 알고리즘을 써도 충돌 쌍을 찾는데 억만년이 걸림” 정도의 뉘양스이다. 여기서 ‘충돌 쌍’이란 같은 해시 값을 가지는 두 데이터 쌍을 의미한다 (아까 그림에서는 “ARGOS”와 “MINIBEEF”가 충돌 쌍일 것이다).

Hash Collision의 위험성

해시 암호는 기본적으로 단방향 암호이다. 간단하게 설명을 덧붙이자면, 암호화 해시 함수에 의해 한번 해싱이 되면 해당 해시 값에 대한 평문이 뭐였는지는 개발자도, 해커도, 며느리도 모르게 된다. 즉, 복호화가 안된다는 것(100% 안되는지는 장담 못하겠다. 더 공부해보고 추가할 예정).

그렇다면 만약 사용자의 비밀번호를 해시 암호화를 이용해 인증하는 서비스가 있을 때 복호화 방법이 없는데 이를 어떻게 확인하느냐? 놀랍게도 해시 값을 비교한다.

위 그림처럼 암호를 등록할 때 서버 DB에는 이를 평문이 아닌 해시 값으로 저장하고, 실제로 인증을 할 때에는 입력받은 값과 저장된 해시를 비교하여 참 거짓을 판단한다. 눈치를 챘을 지 모르겠지만 이러한 인증 방식을 채택하는 까닭에 보안에서 해시 충돌의 위험성이 설명된다. 잠시 아까 처음 봤었던 그림을 살펴보자.

해시 충돌을 설명하는 삽화에서 “ARGOS”와 “MINIBEEF”는 그 해시 값이 같은 충돌 쌍이었다. 만약 위 인증 과정에서 “ARGOS”가 아닌 “MINIBEEF”를 입력했을 때 결과는 어떨까?

서버에서는 입력 값의 평문이 뭐였는지에는 관심이 없고 해당 해시만 비교하기 때문에 너무 당연하다는 듯이 인증이 우회된다. 물론 해시 충돌 쌍을 찾는 방법에 대한 설명도 없었고, 계정이나 암호의 해시 값이 길바닥에 뒹굴어 다니는 것이 아니기 때문에 현실성이 전혀 없는 이야기처럼 들릴지도 모르겠다.

하지만 실제로 해커들이 DB를 크랙하고 얻어낸 관리자 계정의 해시를 깬다던가하는 사례가 충분히 많고, 이러한 공격 이론이 존재한다는 것 부터 시스템의 무결성에 금이 간다는 소리이기 때문에 이를 간과해서는 안된다.