**해시 충돌(hash collision)**이란 해시 함수 $h:X\to Y$($h$는 $X$에서 $Y$로 가는 함수, $X$는 입력 전체 집합, $Y$는 해시값 전체 집합이고 $|Y|=m$)에서 서로 다른 두 입력 $x_1 \neq x_2$가 같은 해시값 $h(x_1)=h(x_2)$를 가지는 현상을 말한다. $|X|>m$이면 이런 충돌이 반드시 존재한다.
**생일 문제(birthday problem)**는 각 사람의 생일이 $m$개의 값(윤년을 제외하면 $m=365$) 중 하나를 서로 독립적으로, 균등한 확률로 갖는다고 할 때, $n$명 중 생일이 같은 두 사람이 적어도 한 쌍 존재할 확률 $P(n)$을 구하는 문제다. 이는 해시 충돌이 일어날 확률을 어림잡는 대표적인 확률 모형이다.
해시 충돌을 "생일이 겹치는 사람"에 비유하면, 해시값은 '생일'이고 입력값은 '사람'이다. 얼핏 보면 $n$명이 365개의 생일 중 하나씩 가지므로 겹칠 확률이 작을 것 같지만, 실제로 비교되는 것은 한 사람 대 특정한 한 사람이 아니라 $n$명 중 아무 두 사람의 짝이다. $n$명 중 만들 수 있는 짝의 개수는 조합으로 $_{n}C_{2}=\dfrac{n(n-1)}{2}$(엔 씨 투)이므로 $n$이 조금만 커져도 짝의 수는 제곱에 가깝게 늘어난다. 그래서 사람 수가 365에 비해 훨씬 적어도 충돌 확률은 빠르게 커진다. 해시 함수도 마찬가지로, 해시값의 가짓수 $m$이 아무리 커도 저장하는 데이터 개수 $n$이 늘면 생각보다 훨씬 빨리 충돌이 발생한다.
$n$명 모두 생일이 서로 다른 사건(여사건)의 확률은
$$P(\text{모두 다름}) = \frac{m(m-1)(m-2)\cdots(m-n+1)}{m^n} = \frac{{}_{m}P_{n}}{m^n}$$
($_{m}P_{n}$은 "엠 피 엔"이라 읽으며 서로 다른 $m$개에서 $n$개를 뽑아 순서를 정하는 순열의 수다.) 따라서 구하는 확률은
$$P(n) = 1 - \frac{{}_{m}P_{n}}{m^n}$$
$n$이 $m$에 비해 작을 때는 $1-\frac{i}{m}\approx e^{-i/m}$($e$는 자연로그의 밑, 약 $2.718$)을 이용해
$$P(n) \approx 1 - e^{-\,n(n-1)/(2m)}$$
로 근사할 수 있고, 이 확률이 $\dfrac12$을 넘는 지점은 $n \approx 1.1774\sqrt{m}$이다.
$m=365$, $n=4$일 때 여사건의 확률은 $$P(\text{모두 다름}) = \frac{365\cdot364\cdot363\cdot362}{365^4} = \frac{17{,}458{,}601{,}160}{17{,}748{,}900{,}625} \approx 0.9836$$ 이므로 $P(4) \approx 1-0.9836 = 0.0164$, 즉 약 $1.6\%$다. 반면 $n=23$이면 계산 결과 $P(23)\approx 0.507$로 절반을 넘는다.
아래는 근사식 $P(n)\approx 1-e^{-n(n-1)/730}$을 사람 수 $n$에 대한 그래프로 나타낸 것이다.
암호학적 해시 함수(예: SHA-256)의 안전한 출력 길이를 정할 때 생일 문제가 그대로 쓰인다. SHA-256의 해시값은 $2^{256}$가지이지만, 생일 문제의 근사식에 따르면 실제로 충돌을 찾는 데 필요한 시도 횟수는 $2^{256}$이 아니라 대략 $\sqrt{2^{256}}=2^{128}$번이면 충분하다(이를 생일 공격이라 한다). 그래서 암호학자들은 해시 함수를 설계할 때 목표로 하는 충돌 저항성의 두 배에 해당하는 출력 비트 수를 확보한다.