해시 충돌 확률 계산

해시 크기	128
항목 수	1,000,000

해시 크기

128

항목 수

1,000,000

최종 업데이트: 2026-06-23

해시 충돌 확률

해시 함수는 임의 길이의 입력을 고정 길이의 다이제스트(digest)로 변환합니다. 이상적으로는 서로 다른 두 입력이 동일한 다이제스트를 생성하지 않아야 하며, 이 속성을 충돌 저항성이라고 합니다. 그러나 출력 공간이 유한하므로 충돌은 반드시 존재합니다. 핵심 질문은 몇 개의 입력을 해시 처리해야 충돌이 발생할 가능성이 높아지는가입니다. 이 계산기는 생일 근사를 사용하여 해당 확률을 정량화합니다. 이 명칭은 생일 역설에서 유래합니다.

생일 역설

365일 중 균일하게 선택된 생일을 가진 23명이 모이면, 그 중 두 사람이 같은 생일을 공유할 확률이 이미 50%를 넘습니다. 이 확률이 직관보다 훨씬 높은 이유는 특정 날짜와의 일치가 아니라 집단 내 임의의 쌍을 세기 때문입니다. 동일한 비대칭성이 해시 충돌에도 적용됩니다. 두 입력이 같은 해시값을 가지는 충돌을 찾는 것은, 특정 목표 해시를 생성하는 입력을 찾는 원상 공격보다 훨씬 쉽습니다.

계산식

출력이 $b$ 비트인 해시 함수의 탐색 공간은 $2^b$ 개의 균등한 값으로 구성됩니다. $n$ 개의 항목을 무작위로 해시 처리했을 때의 정확한 충돌 확률은 모든 $n$ 개의 출력이 서로 다를 확률의 여사건입니다.

p = 1 - \prod_{k=0}^{n-1}\left(1 - \frac{k}{2^b}\right)

$2^b$ 가 충분히 크고 $n$ 이 적당한 경우, 생일 근사를 통해 더 간단한 폐형식을 얻을 수 있습니다.

p \approx 1 - e^{-n^2 / (2 \cdot 2^b)}

충돌 확률이 50%에 도달하는 항목 수를 구하면 다음과 같습니다.

n_{50\%} = \sqrt{2 \cdot 2^b \cdot \ln 2}

계산 예시

32비트 해시(체크섬에 사용되는 CRC32)의 경우를 살펴보겠습니다.

\begin{aligned} n_{50\%} &= \sqrt{2 \times 2^{32} \times \ln 2} \\ &= \sqrt{2 \times 4{,}294{,}967{,}296 \times 0.6931} \\ &\approx \sqrt{5{,}954{,}124{,}768} \\ &\approx 77{,}163 \end{aligned}

저장소에 파일이 77,163개만 있어도 두 파일이 동일한 32비트 CRC 값을 가질 확률이 약 50%에 달합니다. 근사 공식으로 확인하면 다음과 같습니다.

p = 1 - e^{-77163^2 / (2 \times 2^{32})} \approx 1 - e^{-0.693} \approx 0.50

이 결과는 CRC32가 소규모 데이터 스트림의 오류 감지 코드로는 우수하지만, 대규모 컬렉션에서 고유 식별자로 사용하기에는 부적합한 이유를 설명합니다.

보안 함의

생일 한계에 따르면 $b$ 비트 해시 함수는 $\lfloor b/2 \rfloor$ 비트의 충돌 저항성만 제공합니다. 공격자는 충돌을 찾는 데 약 $2^{b/2}$ 번의 해시 연산만 필요하며, $2^b$ 번이 아닙니다. 이 때문에 암호화 해시 함수는 목표 보안 수준보다 더 큰 출력을 갖도록 설계됩니다.

해시 함수	출력 길이	충돌 저항성
MD5	128비트	~ $2^{64}$ (실제로는 해독됨)
SHA-1	160비트	~ $2^{80}$ (실제로는 해독됨)
SHA-256	256비트	~ $2^{128}$ (현재 표준)
SHA-3-512	512비트	~ $2^{256}$ (고보안)

MD5와 SHA-1이 "해독됨"으로 분류된 이유는 생일 한계 때문만이 아닙니다. 연구자들이 생일 한계 예측보다 훨씬 빠르게 충돌을 생성하는 알고리즘적 취약점을 발견했기 때문입니다. MD5 충돌은 공개된 기법을 사용하면 범용 하드웨어에서 몇 분 안에 계산할 수 있습니다.

암호 탐색 공간에 대한 관련 분석은 비밀번호 엔트로피 계산기를 참조하십시오.

자주 묻는 질문 (FAQ)

암호학에서 생일 역설이란 무엇입니까?

생일 역설은 365일의 생일 경우의 수가 있음에도 23명만 모이면 두 사람이 같은 생일을 가질 확률이 50%를 넘는다는 반직관적인 결과입니다.

동일한 수학 원리가 해시 함수에도 적용됩니다. 공격자는 특정 출력값을 목표로 하는 원상 공격과 달리, 생일 공격에서는 임의의 두 입력이 충돌하는 것으로 충분합니다. 128비트 해시인 MD5의 경우 이 임계값은 약 2^64 ≈ 1.8 × 10¹⁹개로, 원상 공격에 필요한 2^128개보다 훨씬 적습니다.

생일 공격은 왜 비트 수의 절반으로도 충분합니까?

원상 공격은 특정 해시 출력을 찾아야 하므로 전체 2^b 공간을 탐색해야 합니다. 반면 생일 공격은 임의의 두 입력이 충돌하면 되므로, 생일 한계에 따라 약 2^(b/2)개의 샘플만으로 충돌 확률이 50%를 넘습니다. 이 때문에 암호화 해시 함수는 목표 보안 수준의 두 배에 해당하는 출력 비트를 갖도록 설계됩니다. 256비트 해시는 128비트의 충돌 저항성을 제공합니다.

MD5와 SHA-1은 왜 안전하지 않다고 간주됩니까?

MD5(128비트)와 SHA-1(160비트)은 생일 한계 확률 공격이 아닌, 실제 충돌을 생일 한계보다 훨씬 빠르게 찾아내는 알고리즘적 취약점이 발견되었습니다. 2004년 연구진은 MD5 충돌을 실증했으며, 2017년에는 Google의 SHAttered 프로젝트가 최초의 공개 SHA-1 충돌을 만들어냈습니다.

이 함수들은 체크섬이나 콘텐츠 주소 지정 같은 비암호화 용도로는 여전히 안전하지만, 디지털 서명이나 인증 기관처럼 충돌 저항성이 요구되는 용도에는 사용해서는 안 됩니다.

충돌과 원상(preimage)의 차이는 무엇입니까?

충돌은 hash(x) = hash(y)가 되는 서로 다른 두 입력 x와 y를 찾는 것입니다. 원상은 특정 목표값 h를 해시 결과로 갖는 입력 x를 찾는 것으로, 두 입력을 자유롭게 선택할 수 없기 때문에 더 어렵습니다. 두 번째 원상(second preimage)은 알려진 x와 동일한 해시값을 갖는 다른 입력 y를 찾는 것입니다.

이 세 가지는 난이도 순으로 나열됩니다. 충돌 저항성이 가장 약한 속성이고, 두 번째 원상 저항성이 가장 강한 속성입니다. 디지털 서명에 사용되는 해시 함수는 두 번째 원상 공격을 견뎌야 하며, 해시 테이블이나 블룸 필터에 사용되는 함수는 약한 수준의 충돌 저항성만으로도 충분합니다.

해시 충돌 확률 계산

입력

해시 충돌 확률 계산

해시 매개변수

충돌 확률

이 계산기 임베드

이 계산 공유

다음 추천 계산기

비밀번호 엔트로피 계산기

서브넷(CIDR) 계산기

이 계산기가 도움이 되셨나요?

개선이 필요해요