홍라이프 계산기해시 충돌 확률 계산기 쉽게 이해하기 — 개념과 원리
많은 항목에 해시값이나 무작위 ID, 짧은 체크섬을 붙이다 보면 언젠가 두 항목이 같은 값을 갖게 될 수 있습니다. 이 계산기는 생일 문제의 근사식으로, 주어진 비트 수의 해시에서 항목 n개 중 한 번이라도 충돌이 일어날 확률과 확률이 50%가 되는 항목 수를 계산합니다. ID 길이, 해시 테이블, 중복 제거 키를 정하거나 잘라 쓴 해시를 평가할 때 쓰입니다.
계산 방법
- N = 2^비트 수, 가능한 해시값의 개수
- 충돌 확률 p ≈ 1 − e^(−n² / 2N)를 백분율로 표시합니다. 아주 작은 확률도 반올림으로 사라지지 않도록 expm1 함수를 씁니다.
- 50% 충돌 항목 수 ≈ 1.1774 × √N = 1.1774 × 2^(비트/2)이며, 1.1774 = √(2 ln 2)입니다.
원리
생일 문제와 같은 원리입니다. 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘는데, 중요한 것은 사람 수가 아니라 짝의 수 n(n − 1)/2이기 때문입니다. 짝 하나가 충돌할 확률은 1/N이므로 충돌하는 짝의 기대 개수는 약 n²/2N이고, 짝들을 거의 독립으로 보면 지수 함수 꼴의 식이 나옵니다. 결국 충돌은 가능한 값 개수의 제곱근 근처에서 흔해지며, b비트 해시의 충돌 저항성은 약 b/2비트에 그칩니다.
예제 풀이
- 입력값: 64비트 해시, 항목 n = 10^9개
- N = 2^64 = 1.8447 × 10^19
- 지수: n² / 2N = 10^18 ÷ (3.6893 × 10^19) = 0.027105
- 확률: 1 − e^(−0.027105) = 0.02674, 약 2.67%
- 50% 지점: 1.1774 × 2^32 = 5,056,894,494개
| 항목 수 | 충돌 확률 |
|---|---|
| 2.5e+08 | 0.17% |
| 5e+08 | 0.68% |
| 7.5e+08 | 1.51% |
| 1e+09 | 2.67% |
| 1.25e+09 | 4.15% |
| 1.5e+09 | 5.92% |
| 2e+09 | 10.27% |
결과 해석
10억 건에서 2.67%라면 고유해야 하는 기본 키로는 너무 높지만, 캐시 용도라면 괜찮을 수 있습니다. 참고로 50%에 이르는 항목 수는 32비트 해시가 약 7만 7천 개, 64비트가 약 50억 개, 무작위 비트가 122개인 UUID는 약 2.7 × 10^18개입니다.
흔한 실수
- 충돌이 2^비트 개 근처에서야 생긴다고 생각하는 경우. 실제로는 2^(비트/2) 근처입니다.
- 값이 고르게 퍼지지 않는 약한 해시에 이 식을 그대로 쓰는 경우
- 우연한 충돌과 의도적인 공격을 혼동하는 경우
자주 묻는 질문
고유한 무작위 ID에는 몇 비트가 필요한가요?
식을 거꾸로 쓰면 됩니다. 10억 개에서 충돌 확률을 100만분의 1 이하로 하려면 대략 80비트 이상이 필요합니다.
왜 '생일 한계'라고 부르나요?
생일 역설과 같은 수학이며, 365일 대신 2^비트 개의 해시값을 넣은 것이기 때문입니다.
SHA-256을 잘라 ID로 써도 되나요?
충돌 특성은 잘라 낸 길이를 따르므로, 64비트로 자르면 좋은 64비트 해시와 같습니다.
출처: D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching · A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press