해시 충돌 생일 문제, 작은 표본에서 확률 계산하기

n비트 출력 공간의 크기를 N=2ⁿ이라 두면, k개의 독립·균등 출력에서 충돌이 없을 확률은 (N/N)×((N−1)/N)×…×((N−k+1)/N)입니다. 따라서 충돌 확률은 1에서 이 곱을 뺀 값입니다.

k가 N보다 훨씬 작을 때는 1−exp(−k(k−1)/(2N))으로 근사할 수 있습니다. 이 값은 이상적 함수의 표본 확률이지, 실제 해시 알고리즘 공격 비용이나 안전성 판정은 아닙니다.

출력 후보보다 비교 쌍을 셉니다

출력 후보 수를 256개로 정한 이상적 해시를 생각해 봅시다. 첫 번째 입력의 결과가 무엇이든 두 번째 결과가 그 값과 같을 확률은 1/256입니다. 세 번째 결과는 앞의 두 값 중 하나와 일치할 수 있으므로, 충돌이 아직 없다고 조건을 붙였을 때 새 출력이 피해야 할 값은 두 개입니다. 다음에는 세 개, 그 다음에는 네 개로 늘어납니다. 충돌은 ‘특정 값 하나를 맞히는’ 문제와 달리 후보 쌍이 증가하므로 예상보다 적은 표본에서도 가능성이 커집니다.

정확식과 근사식을 구분합니다

출력 공간이 N개이고 서로 독립으로 뽑은 해시 결과가 k개라면, 충돌이 없을 확률은 첫 결과에는 제한이 없고 다음 결과부터 이전에 나온 값을 피할 확률을 곱합니다. 따라서 P(충돌)=1−∏ᵢ₌₀ᵏ₋₁(1−i/N)입니다. k가 작아 각 i/N이 충분히 작으면 곱을 지수함수로 근사해 1−exp(−k(k−1)/(2N))을 얻습니다. 이 식의 핵심은 출력 길이 n이 아니라 비교하는 쌍의 수 k(k−1)/2가 지수의 분자를 이룬다는 점입니다.

두 확률의 차이는 약 0.19퍼센트포인트입니다. 이 표본에서는 근사가 방향과 규모를 잘 보여 주지만, 항상 정확한 값이라는 뜻은 아닙니다. 충돌 확률이 50%를 넘는 최소 표본은 정확 계산에서 20개입니다. 20개 결과의 충돌 없는 확률은 256×255×…×237을 256²⁰으로 나눈 값이므로, 이를 1에서 빼면 약 53%가 됩니다. 비교 쌍은 190개이고, 근사 계산은 약 52%입니다. 정확식과 근사식의 차이는 약 1퍼센트포인트입니다.

실제 해시 보안 수치와 혼동하지 않습니다

NIST의 해시 안내 페이지는 승인된 해시 함수의 충돌 저항성 강도를 출력 길이의 절반으로 표에 제시합니다. 이는 이상적인 birthday 현상과 연결되는 이론적 기준입니다. 하지만 실제 알고리즘에서 알려진 구조적 약점, 사용 방식, 출력 절단, 선택한 메시지 조건까지 자동으로 반영하는 숫자는 아닙니다. 예를 들어 SHA-256의 256비트 출력에 단순히 2¹²⁸을 대입했다고 해서 모든 시스템에서 충돌 공격 비용을 확정할 수는 없습니다. 표준 페이지는 FIPS 180-4를 개정할 계획이라고 표시하므로, 알고리즘 현황은 별도로 확인해야 합니다.

1. digest 비트 수 n을 확인하고 후보 공간 N=2ⁿ을 씁니다.
2. 표본 수 k에서 비교 쌍 k(k−1)/2를 계산합니다.
3. 빠른 추정에는 생일 근사를 적용하고, 작은 표본에서는 정확한 곱도 계산합니다.
4. 독립·균등 가정과 toy 계산의 한계를 답에 적습니다.

자주 하는 실수는 표본 10개를 출력 후보 256개와 직접 비교해 10/256만 계산하는 것입니다. 이는 특정 해시값 하나를 맞힐 확률에 가까운 사고방식이고, 충돌에서는 45개의 서로 다른 쌍이 생깁니다. 두 번째 실수는 근사식을 작은 k에서 정확식으로 취급하는 것입니다. 계산 대상이 충분히 작으면 곱을 직접 구하거나 코드로 검산하세요. 이 글의 숫자는 표준 알고리즘을 공격해 얻은 실험 결과가 아니라, 가정된 균등 난수 모형의 확률입니다.

정확식의 항을 직접 써 봅니다

교육용 회상 문제입니다. 8비트 균등 출력에서 서로 다른 입력 4개를 해시합니다. 충돌 없는 확률을 곱으로 쓰고, 충돌 확률을 대략 얼마로 근사할지 설명해 보세요.

충돌 없는 확률은 1×255/256×254/256×253/256입니다. 정확 충돌 확률은 약 2.327001%이고 근사식 1−exp(−6/256)은 약 2.316498%입니다. 소수점 둘째 자리까지 반올림하면 각각 2.33%와 2.32%이며 차이는 약 0.010504퍼센트포인트입니다. 이 작은 예에서는 근사값도 정확값에 가깝지만 두 계산은 동일하지 않습니다. 문제에서 요구하는 정밀도에 맞춰 선택합니다. 이 문항은 개념 학습용으로 새로 만든 예시입니다.