생일 공격

생일 공격(birthday attack)은 암호학적 해시 함수의 해시 충돌을 찾아내는 암호해독 공격으로, 생일 문제의 확률적 결과를 기반으로 한다. 생일 문제에 따르면 해시 함수의 입력값을 다양하게 할수록 해시 값이 같은 두 입력값을 발견할 확률은 빠르게 증가한다. 따라서 모든 값을 대입하지 않고도 해시 충돌을 찾아낼 확률을 충분히 크게 만들 수 있다.

이론

$H$가지의 값을 가지는 암호학적 해시 함수 $f(x)$에 대해, $f(x_{1})=f(x_{2})$이고 $x_{1}$≠$x_{2}$인 두 입력값 $x_{1},x_{2}$를 찾는 것이 해시 충돌의 목표이다. 이를 찾기 위해서 $n$가지의 입력값을 임의로 선택한 후 해시 값을 비교한다고 할 때, 해시 충돌을 찾을 확률은 다음과 같다.

$p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}$

$n(p;H)$를 해시 충돌을 찾을 확률이 $p$ 이상이기 위한 입력값의 가짓수라고 하면 $p(n;H)$의 식에서부터 다음의 값이 유도된다.

$n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}}$

여기에서 $p=0.5$로 두면 $n(0.5;H)\approx 1.1774{\sqrt {H}}$를 얻는다.

해시 충돌을 찾을 때까지 여러 입력값을 대입하여 계산할 경우, 계산 횟수의 기댓값은 다음과 같다.

$Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}$

따라서, $k$비트 해시 함수의 충돌을 발견하기 위해서는 평균적으로 ${\sqrt {{\frac {\pi }{2}}2^{k}}}$가지의 입력값만 조사하면 되며, 이것은 모든 가능한 가짓수가 $2^{k}$인 것에 비교하여 차수를 크게 감소한 것이다.

외부 링크

• (영어) "What is a digital signature and what is authentication?" from RSA Security's crypto FAQ.
• (영어) "Birthday Attack" X5 Networks Crypto FAQs