생일 패러독스, 생일 공격

$n$명의 사람이 있다. 이 사람들의 생일이 모두 다를 확률은 얼마나 될까?

$$ \prod_{i=1}^{n-1} \left( 1 - \frac{i}{365} \right) $$

이다. 이 경우 $n = 23$만 되어도 이미 확률이 절반 이하가 된다.

 

생각보다 적은 수의 사람이 모여도 꽤 높은 확률로 생일이 같은 두 사람을 찾을 수 있다는 것이 생일 패러독스이다.

 

 

이를 이용하여 충돌쌍 하나를 효과적으로 구하는 암호론적 공격이 생일 공격이다.

해시함수의 충돌값을 찾거나, 블록암호를 공격할 때 사용된다.

Factoring 문제를 효과적으로 푸는 Pollard's rho 랜덤 알고리즘도 똑같은 원리를 기반으로 한다.

 

특히 블록암호에서 어떤 함수 $G$에 대해 $G(x) = G(y)$인 서로 다른 문자열 $x, y \in \{0, 1\}^*$을 찾으면 높은 확률로 공격이 성공하는 경우에 대한 예시를 아래 rkm0959님이 블로그에 정말 멋있게 정리해주셨다!

https://rkm0959.tistory.com/130

암호론 논문 리딩 #2: Even-Mansour Scheme

 

이와같이 충돌쌍을 구하는 문제에 효과적으로 사용되는 생일 공격에 대해 고찰해보았다.

 

 

 

전체 집합의 크기를 $H$라고 하자. (생일의 경우 $H = 365$이다.)

이 중 $n$개의 원소를 임의로 뽑았을 때, 모든 원소 값이 다를 확률은

$$ \prod_{i=1}^{n-1} \left( 1 - \frac{i}{H} \right) $$

이다. $i \ll H$라면 테일러 1차 근사를 사용하여 ($e^{-x} = 1 - x + \frac{x^2}{2} - \cdots \approx 1 - x$)

$$ \prod_{i=1}^{n-1} \left( 1 - \frac{i}{H} \right) \approx \prod_{i=1}^{n-1} e^{- \frac{i}{H}} = e^{-\frac{n(n-1)}{2H}} $$

로 근사할 수 있다.

 

여기서 추론할 수 있는 사실은, 유의미한 확률로 충돌쌍을 발견하려면 최소한 $n = \Theta (\sqrt{H})$ 정도는 되어야한다는 것이다.

$n \ll \sqrt H$라면, 충돌쌍이 존재할 확률은 negligible하다.

$n \gg \sqrt H$라면, 충돌쌍을 찾기 위해서 이미 너무 많은 쌍을 조사한 것이 된다.

실제로 충돌 확률이 50프로 이상이 되기위할 $n$의 최소값은 $ \sqrt{2 \log 2 H} \simeq 1.177 \sqrt{H}$ 정도가 된다.

즉 선택 평문/암호문 공격을 할 때 표본의 개수는 $\Theta (\sqrt{H})$ 정도가 되는 것이 가장 이상적이라는 결과가 나온다.

 

 

 

다음과 같은 문제를 생각해보자.

전체 집합의 크기가 $H$이다. 충돌쌍을 찾을 때까지 전체 집합에서 임의로(uniformly random) 원소 하나를 더 고른다. 충돌쌍을 찾은 순간까지 고르는 원소 개수의 기대값은 얼마일까?

 

기대값을 쓰면

$$ \sum_{n=1}^{H} e^{-\frac{(n-1)(n-2)}{2H}} \cdot \frac{n-1}{H} \cdot n $$

이다. 각 $n$에 대해서 이전 $n-1$번째 원소까지는 값이 모두 달라야하며, 마지막으로 고른 원소에서 충돌하고, 그 때의 고른 횟수는 $n$이기 때문이다.

 

적분을 이용해서 기대값을 근사하면 익숙한 형태가 나온다.

$$ \int_{0}^\infty e^{-\frac{n^2}{2H}} \cdot \frac{n^2}{H} dn $$

극좌표를 이용해서 가우스 적분을 하면

$$ \int_{-\infty}^\infty e^{-tx^2} dx = \sqrt{\frac{\pi}{t}} $$

임을 안다. 이를 $t$에 대해 미분하면

$$ \int_{-\infty}^\infty -x^2 e^{-tx^2} dx = - \frac{\sqrt \pi}{2} t^{-\frac{3}{2}} $$

이다. 그러므로 기대값의 근사값은 아래와 같이 정리된다.

$$ \int_0^\infty e^{-\frac{n^2}{2H}} \cdot \frac{n^2}{H} dn = \sqrt{ \frac{\pi}{2} H } $$

정리하면 충돌쌍을 찾을 때까지 생일공격하는 방법에서 공격 횟수의 기대값은 $\Theta (\sqrt{H})$라는 것이다.

 

 

여러모로 $\sqrt H$와 관련이 있는 방법인 것 같다.

감각적으로만 이해했던 것을 직접 증명을 하니 속이 편하다 ㅎㅎ