생일 공격 문서 원본 보기

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

== 이론 ==

<math>H</math>가지의 값을 가지는 [[암호학적 해시 함수]] <math>f(x)</math>에 대해, <math>f(x_1) = f(x_2)</math>이고 <math>x_1</math>≠<math>x_2</math>인 두 입력값 <math>x_1, x_2</math>를 찾는 것이 [[해시 충돌]]의 목표이다.
이를 찾기 위해서 <math>n</math>가지의 입력값을 임의로 선택한 후 해시 값을 비교한다고 할 때, 해시 충돌을 찾을 확률은 다음과 같다.
:<math>p(n;H) \approx 1 - e^{-n(n-1)/(2H)} \approx 1-e^{-n^2/(2H)}</math>
<math>n(p;H)</math>를 해시 충돌을 찾을 확률이 <math>p</math> 이상이기 위한 입력값의 가짓수라고 하면 <math>p(n;H)</math>의 식에서부터 다음의 값이 유도된다.
:<math>n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}</math>
여기에서 <math>p = 0.5</math>로 두면 <math>n(0.5;H) \approx 1.1774 \sqrt H</math>를 얻는다.

해시 충돌을 찾을 때까지 여러 입력값을 대입하여 계산할 경우, 계산 횟수의 [[기댓값]]은 다음과 같다.
:<math>Q(H)\approx \sqrt{\frac{\pi}{2}H}</math>
따라서, <math>k</math>[[비트 (단위)|비트]] 해시 함수의 충돌을 발견하기 위해서는 평균적으로 <math>\sqrt{\frac{\pi}{2} 2^{k}}</math>가지의 입력값만 조사하면 되며,
이것은 모든 가능한 가짓수가 <math>2^k</math>인 것에 비교하여 차수를 크게 감소한 것이다.

== 같이 보기 ==
* [[충돌 공격]]

== 외부 링크 ==
* {{언어링크|en}} [https://web.archive.org/web/20040913080209/http://www.rsasecurity.com/rsalabs/node.asp?id=2182 "What is a digital signature and what is authentication?"] from [[RSA (security firm)|RSA Security]]'s crypto [[FAQ]].
* {{언어링크|en}} [http://x5.net/faqs/crypto/q95.html "Birthday Attack"] X5 Networks Crypto FAQs

{{암호화 해시}}

{{전거 통제}}

[[분류:암호 공격]]