23명이면 생일이 겹칠 확률이 반을 넘는다
방 안에 사람이 몇 명 모여야 생일이 같은 쌍이 하나라도 있을 확률이 50%를 넘을까. 직감적으로는 183명 정도를 떠올리기 쉽다. 365일의 절반이니까 그쯤이면 되지 않겠느냐는 생각이다. 실제 답은 23명이다. 50명만 모여도 이 확률은 97%까지 치솟는다. 처음 듣는 사람은 대부분 믿지 않는데, 계산을 직접 해보면 반박할 여지가 없다.
이걸 생일 문제(Birthday Problem)라고 부른다. Wolfram MathWorld의 생일 문제 항목에 수학적 전개가 잘 정리되어 있는데, 핵심은 “특정 두 사람”의 생일이 겹치는 확률이 아니라 “아무 두 사람이든” 겹치는 확률을 보는 것이다. 23명이면 가능한 쌍의 수는 23 × 22 / 2 = 253개다. 각 쌍이 서로 다른 생일을 가질 확률을 하나하나 곱해 나가면, 253번째 쌍까지 전부 겹치지 않을 확률이 이미 49.3%까지 내려간다. 한 쌍이라도 겹칠 확률은 그 여사건, 즉 50.7%가 된다. 계산은 단순하지만 결과는 직관과 정면으로 충돌한다.
해시 충돌이 생각보다 빨리 일어나는 이유
이 문제가 소프트웨어 엔지니어링에서 중요한 이유는 해시 함수 때문이다. 해시 함수는 임의의 입력을 고정 길이의 출력값으로 변환한다. 파일 무결성 검증, 데이터베이스 인덱싱, 암호화 서명 등 거의 모든 영역에서 쓰인다. 출력 공간이 유한하니까 서로 다른 입력이 같은 출력을 내는 경우, 즉 충돌은 원리적으로 반드시 발생한다.
사람의 직관은 이렇게 작동한다. “출력 공간이 2의 128승이면 충돌이 일어나려면 적어도 그 절반쯤의 입력이 필요하지 않을까.” 틀렸다. 생일 문제와 같은 구조가 적용되기 때문에, 약 2의 64승 정도의 입력만으로 충돌 확률이 50%에 도달한다. 보안 강도가 출력 공간의 절반이 아니라 제곱근 수준으로 떨어지는 것이다. MD5 해시가 사실상 퇴역한 이유도 여기에 있다. 이론적 출력 공간은 2의 128승이지만, 생일 공격을 적용하면 실질적 보안 강도는 2의 64승으로 줄고, 현대 하드웨어로 이 정도는 뚫을 수 있다. 2004년 왕샤오윈 연구팀이 MD5 충돌을 실증한 이후로 보안 업계에서 MD5는 신뢰할 수 없는 해시 함수로 분류된다.
조합의 폭발을 과소평가하는 뇌
생일 문제의 본질은 조합론적 폭발에 있다. 원소의 수가 선형으로 늘어날 때, 가능한 쌍의 수는 이차식으로 증가한다. n명이 있으면 쌍의 수는 n(n-1)/2로, n에 대해 거의 제곱에 비례한다. 사람의 뇌는 선형 증가에는 꽤 정확한 감각을 가지고 있지만, 이차 이상의 증가율은 체감하기 어렵다. 10명이 20명으로 늘면 사람 수는 두 배지만, 쌍의 수는 45개에서 190개로 네 배 이상 뛴다. 이 비선형성을 직관이 따라가지 못한다.
엔트로피 기반 난수 생성기의 물리적 한계를 다룬 글에서도 비슷한 맥락이 등장한다. 난수의 출력 공간이 크면 안전하다고 생각하기 쉽지만, 실제 보안 강도는 출력 공간의 절대 크기가 아니라 그 제곱근에 의해 결정된다. 직관이 “크기”만 바라보는 사이에 수학은 “가능한 쌍의 수”를 세고 있는 셈이다.
UUID 충돌이 이론 밖의 문제가 되는 순간
UUID v4의 출력 공간은 2의 122승이다. 생일 경계를 적용하면 대략 2의 61승, 약 2.3 × 10의 18승 개의 UUID를 생성해야 충돌 확률이 유의미해진다. 대부분의 시스템에서는 이 수준까지 도달할 일이 없다. 하지만 분산 시스템에서 초당 수백만 건의 이벤트를 처리하면서 수년간 데이터를 누적하면 사정이 다르다. 초당 500만 건이면 하루에 약 4,320억 건, 1년이면 157조 건이 쌓인다. 10년이면 1,570조 건으로, 생일 경계의 턱밑까지 올라간다.
“UUID는 고유하다”는 통념은 확률적으로만 참이지, 절대적으로 참은 아니다. 데이터베이스 샤딩 키를 설계하거나 분산 로그에 고유 식별자를 부여할 때, 출력 공간의 크기만 보고 안심하면 수년 뒤에 원인 파악이 힘든 데이터 오염을 마주할 수 있다. 생일 문제는 수학 교과서의 퍼즐이 아니라, 시스템 설계에서 반드시 계산에 넣어야 하는 실전 제약이다.
소프트웨어 설계에서 생일 경계를 적용하는 법
실무적 교훈은 간단하다. 고유 식별자의 출력 공간을 정할 때, 기대되는 데이터 총량의 제곱을 출력 공간 크기와 비교해야 한다. 예상 레코드 수가 N이면, 출력 공간은 최소 N의 제곱 이상이어야 충돌 확률이 무시할 수 있는 수준으로 내려간다. 이 계산 한 번이면 5년 뒤에 터질 수 있는 사고를 설계 단계에서 막을 수 있다.