만약, 한 방에서 같은 생일을 가진 사람이 존재할 확률이 50% 이상이 되려면, 몇 명의 사람이 있어야 할까? 그 답은 놀랍게도 23명이면 충분하다. 윤년을 생각하지 않더라도 1년이 365일이므로, 23명이란 표본의 수는 일반적으로 생각되는 것보다 훨씬 적은 수이다. 이것을 생일 파라독스(Birthday Paradox)라고 한다.
먼저, 이 사람들이 모두 다른 생일을 가지고 있을 확률을 알아보면, 첫 번째 사람은 365일 중 어떤 날을 선택할 수 있다. 두 번째 사람은 첫 번째 사람과 다른 날을 선택해야 하며, 이 확률은 (1 - 1 / 365)이다. 세 번째 사람은, 365일에서 선택할 수 있는 날이 2개 줄었으며, 따라서 (1 - 2 / 365)이다. 이와 같이 23명까지 전개해보면,
1 * (1 - 1 / 365) * (1 - 2 / 365) * (1 - 3 / 365) * ... (1 - 22 /365) = 0.493
따라서, 23명이 모두 다른 생일이 가질 확률이 0.493이므로, 최소한 두 명이 같은 생일 가질 확률은 1 - 0.493 = 0.507로 50%를 조금 넘는다.
이것을 일반화하여 생각해보자. 충분히 큰 수의 N개의 물건이 있다고 하고, r명의 사람들이 존재하며, 이 사람들 각각 N개의 물건 중 하나를 선택한다고 하자. 그렇다면, 이 사람들이 중복되는 물건을 선택할 확률은 얼마인가? 대략 다음과 같다.
1 - e^((-r^2) / 2N)
이것은 N이 충분히 큰 수일 경우에 해당되는 근사값이다. 여기서, 이 확률이 1 / 2이 넘기 위해서는 (r^2 / 2N) = ln2가 되어야 하며, 이것을 r에 대해서 정리하면 r = root(2ln2) * root(N)이 된다.
이것을 정리해본다면, N의 가능성이 있을 때, 최소한 root(N) 길이의 리스트를 조사하면 중복을 발견할 확률이 50% 정도 된다는 것이다. 이러한 성질은, 해시 함수를 공격하는데 좋은 근거가 된다. 즉, 64비트 해시값이 있다고 했을 때, 2^32번의 계산을 해보면 중복되는 해시값을 찾을 확률은 50%가 넘는다. 이 비트수가 낮을 수록 계산량은 급감하며, 전수공격은 해볼만한 가치가 생긴다. 중복되는 해시값을 찾았다면, 이것을 어떻게 악용할 수 있는가? 생일공격을 처음으로 제안했던 유발(Gideon Yuval)은 다음과 같이 설명한다.
1. Alice는 계약서를 두 종류로 준비한다. 하나는 Bob에게 보여줄 것이고, 다른 하나는 Bob을 속이기 위한 것이다.
2. Alice는 정당한 계약서를 눈에 띄지 않게 다양하게 변조한다. 변조하는 방법은 여러 가지가 있는데 Space 키 대신 Space - Backspace - Space를 쓰거나, 줄 바꾸기(Return) 키를 치기 전에 한 두개 정도의 Space를 넣는 방법 등이 있다. 만약 문서가 모두 32줄일 때, 각 줄마다 이런 식의 변조 방법을 쓴다면 2^32 종류의 서로 다른 문서들을 만들어 놓을 수 있다.
3. 필요하다면 가능한 변조를 계속해서 2^32 종류의 문서가 서로 다른 해시 함수값을 갖도록 한다.
4. 이번에는 Bob을 속이기 위한 부정한 문서를 역시 다양하게 변조하여 2^32 종류의 서로 다른 해시값들을 가지는 문서들을 만들어 놓는다.
5. 그런 다음 Alice는 정당한 문서들 가운데 절반인 2^32개씩 두 묶음(A, A´)으로 나눈다. 부정한 문서로 같은 방법으로 두 묶음(B, B´)으로 나눈다.
6. 가능한 해시값의 종류가 2^64이므로 대략 2^32개의 문서들의 그룹에서는 1 / 2 확률로 충돌쌍이 존재한다. 즉 (A, B), (A, B´), (A´, B), (A´, B´) 가운데 충돌쌍이 있는 그룹은 거의 항상 존재할 것이다.
7. 충돌쌍을 찾은 Alice는 Bob에게 변조되기는 했지만 겉으로는 정당한 문서에 서명해 달라고 한다.
8. Alice는 Bob이 서명한 문서를 서명하지 않았던 사기 문서로 바꾸어 놓는다. 앞으로 언젠가 Alice는 판사 앞에서, Bob이 전혀 생각하지도 않았던 문서에 서명했음을 입증할 때가 있을 것이다.
Reference
Wade Trappe, Lawrence Washington, Introduction to Cryptography with Coding Theory, Second Edition, PEARSON Education
최병문, 이영환(2007), 암호의 세계, 경문사
Library/Cryptography