해시 충돌

해시 충돌이란 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다. 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다.

해시 충돌은 해시 함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리며, 따라서 해시 함수는 해시 충돌이 자주 발생하지 않도록 구성되어야 한다. 암호학적 해시 함수의 경우 해시 함수의 안전성을 깨뜨리는 충돌 공격이 가능할 수 있기 때문에 의도적인 해시 충돌을 만드는 것이 어렵도록 만들어야 한다.

검색

해시 함수를 사용하여 입력 키 값으로부터 해시 값을 얻어 그것을 인덱스로 사용하는 것은 효율적인 검색 방식 중 하나이다. 이와 같은 해시 값으로 이루어진 자료구조를 '해시 테이블'이라고 부른다. 서로 다른 입력 키 값이 서로 다른 해시 값(인덱스)으로 매핑될 경우 해시 테이블 조회에 걸리는 시간은 상수 시간이 된다. 그러나 여러개의 서로 다른 키 값이 동일한 인덱스로 매핑될 경우, 해시 충돌이 발생하여 해시 테이블의 성능을 떨어뜨리게 된다. 이와 같은 해시 충돌을 처리하는 방식 중 가장 많이 쓰이는 것이 '체이닝'(chaining, 각각의 해시 테이블 인덱스에 해당하는 자료구조를 연결 리스트로 만드는 방법)과 '개방 번지화'(open addressing, 해시 테이블 인덱스 중 비어있는 공간을 할당하는 방법)'이다. 그러나 둘다 최악의 경우 조회 복잡도가 원소 개수에 따라 선형 시간이 된다.

암호학에서의 쓰임

암호화 해시 함수의 중요한 요소 중 하나는 계산적으로 충돌을 찾아내는 것이 불가능해야 한다는 것이다. 해시 함수 출력 값의 충돌을 찾아낼 수 없다면 출판, 간행물의 원본이 변하지 않았음을 확인하는 값으로서 해시 함수의 출력값을 이용할 수 있다. 여기서 충돌을 찾아내는 것이 '불가능'하다고 하는 것은 해시 함수의 출력 값 범위 내에서 어떤 알고리즘을 사용하더라도 해시 충돌을 일으키는 값을 다항시간 내에 찾아낼 수 없다는 것을 의미하며, 여기서 가능하다는 것은 생일 공격(Birthday attack)의 알고리즘 보다 훨씬 빠르다는 것이다.

해시 충돌을 일으키는 임의의 두 값을 찾는 과정을 '충돌 공격(collision attack)'이라고 한다. 또한 주어진 값에 대해 그 값과 해시 충돌을 일으키는 값을 찾는 것은 역상 공격이라고 한다. 암호 공격라는 측면에서 보면 역상 공격은 충돌 공격 보다 더 심각한 공격이 될 것이다.

충돌 저항성

주어진 조건:해시 함수 $H$ , 패스워드 $x$ , $y$ .

약한 충돌 저항성: 주어진 $x$ 에 대해, $H(x)=H(y)$ 인 $y\neq x$ 를 찾는 것이 어려울 때 해시 함수가 약한 충돌 저항성을 가지고 있다고 한다. 주어진 패스워드를 입력 값으로 해시 함수에 넣고, 그것을 초기 값 ( $x$ )이라고 하자. 만약 $x$ 에 대한 출력 값과 같은 출력 값을 갖는 또다른 패스워드를 찾을 확률이 해시 함수의 출력 값 범위 내에서 무시 가능(negligible)할 때 이 함수는 약한 충돌 저항성을 가지고 있다고 한다.