Birthday Attack

암호문을 깨기 위해 사용하는 방법 중 가능한 모든 방법을 대입하여 공격하는 전수공격(brute force) 기법이 존재한다. 이는 가장 확실한 방법이기는 하지만 소요되는 시간이 너무나 길어 현실성이 없는 경우가 대부분이다. 그러나 수학적 논리는 종종 인간의 직관을 뛰어넘는 경우가 있다. 통계학적으로 그렇게 전수공격이 비현실적이지만은 안은가보다, 여기서 소개할 생일공격(birthday attack) 또는 생일역설(birthday paradox) 을 살펴보면 불가능하게만 보였던 전수공격이 한번 시도해볼 수 있는 여지를 가지고 있다고 생각하게 만들 것이다.

최소한 몇명이 모여있으면 그 중에 생일이 같은 두 사람이 있을 확률이 없을 확률보다 높을까?

한번 생각해보시길 바람니다. 100명 혹은 1000명 몇 명정도 일까요? 생일공격에 따르면 23명만 있으면 된다.

주머니에 1부터 N까지의 번호가 새겨진 공이 한 개씩 들어있다. 주머니에서 공을 q번 복원 추출할 때, 같은 번호의 공이 뽑히게 되면 "충돌이 발생했다"고 한다. 이 사건이 발생할 확률을 C(N,q) 라 하자. C(N,q) 는 다음과 같이 계산된다.

따라서, 축구장에서 뛰고 있는 23명 중 생일이 같은 사람이 있을 확률은 C(365, 23) = 0.507 이다.

생일공격은 종종 해쉬 함수의 충돌(collision)을 발견하는데 사용된다.

위의 정리에 의해 해쉬값의 길이가 n 비트이면 N = 2^n 가지의 출력이 생성될 수 있다. 그러므로 q = 2^(n/2) 정도되면 충돌쌍을 찾을 확률이 1/2 에 근접하기 때문에 해쉬 함수의 안전성을 2^(n/2) 로 본다.