해시 충돌 문서 원본 보기

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

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

==검색==
{{본문|해시 테이블}}

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

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

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

=== 충돌 저항성 ===
'''주어진 조건''':해시 함수 <math>H</math>, 패스워드 <math>x</math>, <math>y</math>.

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

'''강한 충돌 저항성''': <math>H(x) = H(y)</math>와 같이 같은 해시 출력 값을 갖는 <math>x</math>와 <math>y</math>를 찾는 것이 함수의 출력 값 범위 내에서 [[무시 가능 함수|무시 가능(negligible)]]할 때 해시 함수 <math>H</math>는 강한 충돌 저항성을 가진다고 한다.

== 같이 보기 ==
* [[비둘기집 원리]]

==참조==
* http://www.cryptography.com/cnews/hash.html
* https://web.archive.org/web/20090206122657/http://eprint.iacr.org/2005/425.pdf - Improved Collision Attack on Hash Function [[MD5]], very technical.

== 외부 링크 ==
* [http://www.cryptography.com/cnews/hash.html Cryptography Research - Hash Collision Q&amp;A]
* [https://web.archive.org/web/20090201040933/http://www.networkdls.com/Software.Asp?Review=64 Free collision &amp; hash reversal tool]

{{전거 통제}}

[[분류:암호화 해시 함수]]
[[분류:암호화 공격]]
[[분류:해싱]]