Skip to content
Published on

생일 역설과 해시 충돌 — 왜 23명이면 절반이 겹치는가

🇰🇷KO🇺🇸EN🇯🇵JA
Split View필사 모드
Authors

들어가며 — 파티에서 시작하는 확률 이야기

방에 23명이 모여 있다고 합시다. 이 중 두 사람의 생일이 같을 확률은 얼마일까요? 대부분은 "365일 중 23명이면... 한 6% 정도?"라고 답합니다. 실제 답은 **50.7%**입니다. 절반이 넘습니다.

이 결과가 워낙 직관에 어긋나서 "생일 역설(birthday paradox)"이라는 이름이 붙었습니다. 사실 역설이라기보다는 우리 직관이 잘못된 질문에 답하고 있기 때문에 생기는 착시입니다. 그리고 이 착시를 제대로 이해하면, 겉보기엔 전혀 무관해 보이는 문제들이 하나로 꿰어집니다. UUID는 왜 충돌하지 않는가, 해시는 몇 비트여야 안전한가, 해시 테이블은 언제 커져야 하는가, git은 왜 SHA-1을 버렸는가.

이 글은 파티의 확률 문제에서 출발해 그 수학이 어디까지 뻗어 나가는지를 따라갑니다. 직접 해시를 만들어 보며 감을 잡고 싶다면 이 사이트의 해시 생성기를 함께 열어두면 좋습니다.

왜 23명이면 50%인가

핵심은 우리가 무엇을 세고 있는지에 있습니다. 직관이 떠올리는 질문은 이것입니다. "나와 생일이 같은 사람이 있는가?" 하지만 실제 질문은 다릅니다. "아무 두 사람의 생일이 같은가?"

23명 중에서 고를 수 있는 사람의 쌍은 몇 개일까요? 조합입니다.

쌍의 개수 = C(23, 2) = 23 × 22 / 2 = 253개

253쌍입니다. 각 쌍이 서로 생일이 같을 확률은 1/365이니, 253쌍이나 있으면 그중 하나가 겹칠 여지는 생각보다 큽니다. 사람이 늘어날 때 사람 수는 선형(23, 24, 25...)으로 늘지만, 쌍의 수는 제곱에 가깝게(약 n²/2로) 늘어납니다. 우리 직관은 사람 수만 보고, 진짜로 중요한 쌍의 수를 놓칩니다.

정확한 확률은 여사건으로 계산합니다. "겹치는 쌍이 하나도 없다"의 확률을 구한 뒤 1에서 빼는 것입니다.

P(모두 다름) = 365/365 × 364/365 × 363/365 × ... × 343/365
P(적어도 하나 겹침) = 1 − P(모두 다름)

n명일 때 이 값을 계산하면 다음과 같습니다.

인원 수적어도 한 쌍이 겹칠 확률
10약 11.7%
20약 41.1%
23약 50.7%
30약 70.6%
50약 97.0%
70약 99.9%

23명에서 이미 절반을 넘고, 70명이면 사실상 확실합니다. 파이썬으로 직접 확인할 수도 있습니다.

def birthday_prob(n, days=365):
    p_all_different = 1.0
    for i in range(n):
        p_all_different *= (days - i) / days
    return 1 - p_all_different

for n in (10, 20, 23, 30, 50, 70):
    print(n, round(birthday_prob(n) * 100, 1))

√N 직관 — 이 글의 진짜 주인공

생일 문제의 구체적인 숫자보다 훨씬 중요한 것은 그 뒤에 숨은 규칙입니다. N개의 가능한 값 중에서 무작위로 뽑을 때, 대략 √N개쯤 뽑으면 충돌(같은 값 두 개)이 나타나기 시작한다.

생일은 N = 365이고, √365 ≈ 19.1입니다. 실제로 50%를 넘는 지점인 23명이 이 √N 근처에 있습니다. 우연이 아닙니다.

왜 √N인가를 대략적으로 보면 이렇습니다. n개를 뽑으면 쌍은 약 n²/2개 생기고, 각 쌍이 충돌할 확률은 1/N입니다. 충돌 쌍의 기대 개수는 약 n²/(2N)이고, 이 값이 대략 1이 되는 지점, 즉 "이제 충돌 하나쯤은 나올 만하다"는 지점이 n ≈ √N입니다. 50% 확률을 기준으로 좀 더 정확히 쓰면 다음과 같습니다.

50% 충돌에 필요한 표본 수 n ≈ 1.1774 × √N

이 하나의 근사가 이 글 나머지 전부를 지배합니다. 기억해야 할 것은 딱 하나입니다. 충돌은 N이 아니라 √N에서 시작된다. 공간이 크다고 안심하면 안 되고, 그 제곱근이 얼마인지를 봐야 합니다.

UUID와 해시로 넘어가기

이제 파티를 떠나 컴퓨터로 갑니다. 소프트웨어에서 우리는 늘 "고유해야 하는 식별자"를 만듭니다. UUID, 해시값, 토큰. 이들은 사실상 아주 큰 상자에서 무작위로 값을 뽑는 것과 같습니다. 그래서 생일 문제의 수학이 그대로 적용됩니다.

UUID version 4는 122비트의 무작위 비트를 가집니다(128비트 중 버전과 변형 표시에 몇 비트를 쓰기 때문입니다). 가능한 값의 수 N은 2¹²²이고, 이는 대략 5.3 × 10³⁶입니다. 이렇게 큰 공간에서 충돌이 현실적으로 걱정되려면 √N개, 즉 약 2.3 × 10¹⁸개의 UUID를 생성해야 합니다.

이게 얼마나 큰 수인지 감을 잡아봅시다. 1초에 10억 개(10⁹)의 UUID를 쉬지 않고 생성한다고 해도, 50% 충돌 확률에 도달하려면 수백 년이 걸립니다. 그래서 실무에서는 UUIDv4를 "충돌하지 않는다"고 안심하고 씁니다. 엄밀히는 충돌이 가능하지만, 확률이 무시할 만큼 작습니다.

여기서 √N 직관의 위력이 드러납니다. 122비트 공간의 안전성은 122비트가 아니라 그 절반인 61비트만큼입니다. 충돌 저항성을 따질 때는 항상 비트 수를 절반으로 접어서 생각해야 합니다.

해시 충돌 확률을 어림하기

암호학적 해시 함수도 마찬가지입니다. 해시 함수는 임의 길이의 입력을 고정 길이 출력으로 보냅니다. 출력이 b비트이면 가능한 해시값은 2ᵇ개입니다. 서로 다른 입력이 같은 해시값을 갖는 것이 충돌입니다.

생일 근사를 그대로 적용하면, 약 2^(b/2)개의 서로 다른 입력을 해시했을 때 충돌 확률이 유의미해집니다. 정리하면 이렇습니다.

해시 출력 크기전수 공간 N충돌이 걱정되는 지점 (약 √N)
32비트2³² ≈ 43억약 2¹⁶ = 65,536개
64비트2⁶⁴약 2³² ≈ 43억 개
128비트2¹²⁸약 2⁶⁴ 개
256비트2²⁵⁶약 2¹²⁸ 개

32비트 해시는 겨우 6만 5천 개 정도의 값에서 충돌이 절반 확률로 나타납니다. 43억이라는 공간 크기에 속으면 안 되는 이유가 이것입니다. 실제 안전 마진은 그 제곱근인 6만 5천에 불과합니다.

아주 작은 충돌 확률을 어림하는 편리한 공식도 있습니다. N이 크고 표본 수 n이 √N보다 훨씬 작을 때, 충돌 확률은 대략 다음과 같습니다.

P(충돌) ≈ n² / (2N)

예를 들어 128비트 해시(N = 2¹²⁸)에 10억 개(n = 10⁹ ≈ 2³⁰)의 값을 넣으면, 충돌 확률은 약 (2³⁰)² / (2 × 2¹²⁸) = 2⁶⁰ / 2¹²⁹ = 2⁻⁶⁹입니다. 사실상 0입니다.

왜 128비트면 충분한가

이제 "왜 128비트냐"에 답할 수 있습니다. 128비트 해시나 식별자의 충돌 저항성은 √N, 즉 2⁶⁴번의 시도 수준입니다. 2⁶⁴는 약 1.8 × 10¹⁹입니다.

이 규모가 물리적으로 어떤 의미인지 보겠습니다. 지구상의 가장 빠른 슈퍼컴퓨터들을 총동원해 초당 수조 번(약 2⁴⁰) 해시를 계산한다고 해도, 2⁶⁴번에 도달하려면 수십만 년이 걸립니다. 무작위 충돌을 우연히 만날 확률은 실질적으로 0입니다.

여기서 두 종류의 "충돌 저항성"을 구분해야 합니다.

  • 충돌 저항성(collision resistance): 공격자가 "아무 두 입력"의 해시가 같아지도록 찾는 것. 생일 공격이 적용되어 난이도는 2^(b/2)입니다. 128비트면 2⁶⁴.
  • 역상 저항성(preimage resistance): "주어진 특정 해시값"에 대응하는 입력을 찾는 것. 여기는 생일 트릭이 안 통해서 난이도가 2ᵇ입니다. 128비트면 2¹²⁸.

즉 같은 128비트라도 "특정 값을 뚫는 것"은 2¹²⁸으로 훨씬 어렵고, "아무 충돌이나 찾는 것"은 2⁶⁴로 상대적으로 쉽습니다. 그래서 강한 충돌 저항성이 필요한 곳에서는 128비트로는 부족하다고 보고 256비트를 씁니다. SHA-256이 256비트를 쓰는 이유가 바로 이 여유(2¹²⁸의 충돌 저항성)를 확보하기 위해서입니다.

해시 테이블 — 충돌을 오히려 활용하는 곳

지금까지는 충돌이 나쁜 일이었습니다. 하지만 해시 테이블에서는 충돌이 피할 수 없는 일상이고, 오히려 이를 전제로 설계합니다. 여기서는 해시 공간이 일부러 작기 때문입니다.

해시 테이블은 키를 해시한 뒤 그 값을 버킷 개수 m으로 나눈 나머지를 인덱스로 씁니다.

index = hash(key) % num_buckets

버킷이 m개뿐이면 N = m으로 아주 작습니다. 생일 문제에 따라, 키를 √m개만 넣어도 충돌이 시작됩니다. 버킷이 100개면 겨우 10여 개 키에서 이미 충돌이 흔해집니다. 그래서 해시 테이블은 충돌을 없애려 하지 않고, 충돌이 났을 때 우아하게 처리하는 데 집중합니다. 대표적으로 같은 버킷에 연결 리스트로 매다는 체이닝(chaining), 또는 다음 빈 칸을 찾아가는 개방 주소법(open addressing)이 있습니다.

부하율과 리사이징

해시 테이블의 성능을 지배하는 값이 **부하율(load factor)**입니다.

부하율 α = 저장된 항목 수 n / 버킷 수 m

부하율이 낮으면 충돌이 드물어 조회가 평균 O(1)에 가깝습니다. 하지만 부하율이 높아질수록 버킷마다 항목이 쌓여 충돌이 잦아지고, 조회가 그 사슬을 훑느라 느려집니다. 그래서 대부분의 해시 테이블 구현은 부하율이 임계값을 넘으면 버킷 수를 늘리고 모든 항목을 다시 배치합니다. 이것이 리사이징(resizing) 또는 리해싱(rehashing)입니다.

  • Java의 HashMap은 기본 부하율 임계값이 0.75입니다. 항목 수가 버킷 수의 75%를 넘으면 버킷을 두 배로 늘립니다.
  • Python의 dict는 대략 2/3(약 0.66)을 넘으면 커집니다.
  • Go의 맵도 유사한 임계값에서 성장합니다.

리사이징은 모든 항목을 새 버킷에 다시 넣어야 하므로 O(n)의 비용이 듭니다. 비싸 보이지만, 버킷을 두 배씩 늘리는 전략(amortized doubling) 덕분에 항목 하나를 추가하는 평균 비용은 여전히 O(1)로 유지됩니다. 큐나 동적 배열이 커질 때 두 배씩 늘리는 것과 같은 원리입니다. 가끔 한 번 크게 비싸지만, 그 비용을 그 사이의 값싼 연산들에 나눠 담으면 평균은 상수 시간입니다.

여기서 흥미로운 대비가 있습니다. 암호학에서는 √N에서 충돌이 시작되는 것이 위협이라 공간을 크게 잡아 충돌을 피했습니다. 해시 테이블에서는 같은 √N 현상을 인정하고, 공간을 작게 유지하되 충돌 처리와 리사이징으로 성능을 관리합니다. 같은 수학, 정반대의 전략입니다.

충돌이 정말 중요해질 때 — git의 SHA-1에서 SHA-256으로

충돌 확률이 이론이 아니라 실제 사건이 된 대표적 사례가 git입니다.

git은 모든 객체(커밋, 트리, 블롭)를 그 내용의 해시로 식별합니다. 오랫동안 이 해시는 SHA-1이었고, SHA-1은 160비트를 출력합니다. 생일 규칙에 따르면 SHA-1의 충돌 저항성은 2^(160/2) = 2⁸⁰번의 시도입니다. 오랫동안 이 정도면 충분히 안전하다고 여겨졌습니다.

문제는 두 가지였습니다. 첫째, 2⁸⁰은 무한하지 않고, 계산 능력이 발전하면서 점점 손이 닿는 범위로 들어왔습니다. 둘째, 더 결정적으로 SHA-1은 순수한 무작위 함수가 아니었습니다. 내부 구조의 약점 때문에, 무작위 대입인 2⁸⁰보다 훨씬 적은 노력으로 충돌을 만드는 방법이 발견되었습니다.

2017년, 구글과 CWI가 실제로 서로 다른 두 PDF 파일이 같은 SHA-1 해시를 갖도록 만드는 데 성공했습니다. 이 "SHAttered" 공격은 약 2⁶³ 수준의 계산으로 충돌을 만들어냈습니다. 이론적 안전선인 2⁸⁰보다 한참 아래였습니다. 이는 콘텐츠 주소 저장소인 git에 직접적인 위협이었습니다. 악의적으로 만든 두 객체가 같은 해시를 가지면, 하나를 다른 하나로 몰래 바꿔치기할 여지가 생기기 때문입니다.

그래서 git은 두 방향으로 대응했습니다.

  • 단기 방어: SHAttered 유형의 충돌을 탐지하는 강화된 SHA-1(collision detection이 붙은 변형)을 도입해, 알려진 공격 패턴을 걸러냅니다.
  • 근본 해법: 해시 함수 자체를 SHA-256으로 전환하는 작업을 진행했습니다. SHA-256은 256비트를 출력하므로 충돌 저항성이 2¹²⁸로 뛰어, 예측 가능한 미래에 무작위 충돌은 물론 구조적 공격도 사실상 불가능합니다.

git의 교훈은 명확합니다. "지금 충분한 비트 수"가 영원히 충분하지는 않습니다. 계산 능력의 발전과 해시 함수 자체의 약점 발견이 겹치면, 어제의 안전선이 오늘의 취약점이 됩니다. 그래서 보안 시스템은 항상 넉넉한 여유(SHA-256의 2¹²⁸ 같은)를 두고 설계합니다.

정리 — 하나의 수학, 여러 얼굴

생일 역설은 파티의 흥미로운 트릭처럼 보이지만, 사실은 컴퓨팅 전반을 관통하는 근본 원리입니다.

  • 핵심 규칙: N개의 공간에서 충돌은 N이 아니라 √N에서 시작된다.
  • UUID·해시: 그래서 b비트의 충돌 저항성은 실질적으로 b/2비트다. 128비트가 안전한 이유는 2⁶⁴의 벽이 물리적으로 넘기 어렵기 때문이다.
  • 해시 테이블: 같은 √N 현상 때문에 충돌은 필연이다. 그래서 부하율을 관리하고, 임계값에서 두 배로 리사이징한다.
  • git: SHA-1의 2⁸⁰ 저항성이 SHAttered로 뚫리자 SHA-256의 2¹²⁸로 옮겨갔다. 어제의 충분함은 내일의 부족함이 될 수 있다.

이 모든 것이 "쌍의 수는 사람 수의 제곱으로 늘어난다"는 단순한 관찰에서 나옵니다. 다음에 UUID를 찍거나 해시 크기를 고를 때, 공간의 크기가 아니라 그 제곱근을 떠올려 보시기 바랍니다. 진짜 안전 마진은 늘 거기에 있습니다.

직접 여러 해시 알고리즘의 출력을 만들어 보고 크기를 비교해 보고 싶다면 해시 생성기에서 실험해 보세요.

참고 자료

Discuss on Twitter • View on GitHub