생일 문제와 해시 충돌이 무슨 관계인가요?

23명만 모여도 같은 생일인 사람이 있을 확률이 50%를 넘는 것이 생일 문제입니다. 해시 충돌도 같은 원리입니다. 해시 공간이 2^N이면 약 2^(N/2)개만 해싱해도 충돌 확률이 50%에 도달합니다.

SHA-256은 충돌에 안전한가요?

SHA-256은 2^128개의 해시가 필요하여 현재 기술로 충돌을 찾는 것이 사실상 불가능합니다. 우주의 원자 수(약 2^266)와 비교해도 매우 큰 수입니다. 현재 보안 표준으로 안전합니다.

UUID v4의 충돌 확률은 어느 정도인가요?

UUID v4는 122비트 랜덤이므로 충돌 50% 확률에 약 2^61(약 2.3×10^18)개가 필요합니다. 초당 10억 개를 생성해도 약 73년이 걸려, 실용적으로 충돌 걱정이 없습니다.

SHA-1은 왜 더 이상 안전하지 않나요?

SHA-1은 160비트로 이론적으로 2^80 연산이 필요하지만, 2017년 Google의 SHAttered 공격으로 실제 충돌이 생성되었습니다. 약 2^63 연산(GPU 클러스터로 수일)으로 가능해져 디지털 서명, 인증서 등에서 사용이 금지되었습니다.

해시 함수의 비트 수를 2배로 늘리면 보안도 2배가 되나요?

아닙니다. 생일 공격 기준으로 보안 강도는 비트 수의 절반입니다. 128비트 해시는 64비트 보안, 256비트 해시는 128비트 보안을 제공합니다. 비트 수를 2배로 늘리면 보안은 2^(비트수/2)배 강화되어 기하급수적으로 증가합니다.

블록체인에서 해시 충돌이 발견되면 어떻게 되나요?

비트코인은 SHA-256 이중 해시를 사용합니다. 만약 SHA-256 충돌이 발견되면 서로 다른 거래가 같은 해시를 가져 이중 지불 등의 공격이 가능해집니다. 이 때문에 블록체인은 가장 강력한 해시 함수를 사용하며, 양자 컴퓨터 대비 연구도 진행 중입니다.

해시 테이블에서의 충돌과 암호학적 충돌은 다른가요?

네. 해시 테이블 충돌은 제한된 버킷 수로 인한 자연스러운 현상이며, 체이닝이나 오픈 어드레싱으로 처리합니다. 암호학적 충돌은 의도적으로 같은 해시값을 가진 두 입력을 찾는 공격이며, 이를 방지하는 것이 해시 함수의 보안 요구사항입니다.

calculator bench🎓몇%

교육 / IT

해시 충돌 확률

생일 공격 원리로 해시 충돌 확률을 계산합니다.

해시 충돌 확률 계산기는 생일 문제(birthday problem)의 원리를 적용하여 해시 함수의 충돌 확률을 계산하는 도구입니다. N비트 해시에서 k개의 값을 해싱했을 때 최소 2개가 같은 해시값을 가질 확률을 산출합니다. 생일 공격에 의하면, N비트 해시의 충돌을 50% 확률로 찾으려면 약 2^(N/2)개의 해시만 필요합니다. MD5(128비트)는 약 2^64개, SHA-256(256비트)은 약 2^128개가 필요합니다. MD5의 경우 현대 컴퓨팅으로 수 초 만에 충돌을 생성할 수 있어 보안 용도로 사용이 금지됩니다. 이 계산기를 통해 해시 함수 선택과 시스템 설계 시 충돌 위험을 사전에 평가할 수 있습니다.

input / result surfaceLIVE

입력

해시 비트 수

해시 함수의 출력 비트 수

항목 수

해시할 고유 항목의 수

해시 공간: 2^256

충돌 확률

0.000000%

불가능

50% 충돌 필요 항목 수

4.01×10^38

충돌 확률이 50%가 되는 항목 수

충돌 확률0.0%

항목 수별 충돌 확률

차트 로딩중...

workflow

사용 방법

약 1분

총 소요 시간: 약 1분

해시 비트 수 선택

해시 함수의 출력 비트 수(128, 256 등)를 입력합니다.

해시 개수 입력

생성할 해시 값의 수를 입력합니다.

결과 확인

충돌 확률과 50% 도달에 필요한 해시 수를 확인합니다.

principle

계산 원리

## 해시 충돌 확률의 수학적 배경

### 생일 문제 공식 N개의 가능한 값 중에서 k개를 무작위로 선택할 때, 최소 2개가 같을 확률:

P(충돌) = 1 - ∏(i=0 to k-1) (N-i)/N

### 근사 공식 k가 N에 비해 충분히 작을 때:

P(충돌) ≈ 1 - e^(-k²/(2N))

N비트 해시에서 N = 2^n이므로:

P(충돌) ≈ 1 - e^(-k²/2^(n+1))

### 50% 충돌에 필요한 해시 수 P(충돌) = 0.5가 되는 k값:

k₅₀ ≈ √(2N × ln2) ≈ 1.177 × √N = 1.177 × 2^(n/2)

128비트: k₅₀ ≈ 2^64 ≈ 1.8 × 10^19 256비트: k₅₀ ≈ 2^128 ≈ 3.4 × 10^38

### 보안 강도(Security Strength) 해시 함수의 충돌 저항 보안 강도 = n/2 비트

MD5(128비트): 64비트 보안 → 현대 컴퓨팅으로 파괴 가능 SHA-256(256비트): 128비트 보안 → 현재 안전

faq

자주 묻는 질문

cases

실생활 예시

CASE 01

데이터베이스 100만 레코드의 UUID 충돌

100만 개의 UUID v4가 있을 때 충돌 확률은 약 p ≈ k²/(2×2^122) ≈ 10^12/(2×5.3×10^36) ≈ 10^-25입니다.

사실상 0%입니다. UUID v4는 수십억 개 수준에서도 충돌 걱정이 불필요합니다.

CASE 02

MD5 해시의 위험성

MD5(128비트)는 약 2^64(약 1.8×10^19)개의 해시로 충돌 확률 50%에 도달합니다. 현대 GPU로 수 초 내에 충돌을 생성할 수 있습니다.

MD5는 보안 용도(디지털 서명, 인증서 등)로 사용하면 안 됩니다. 파일 무결성 체크에만 제한적으로 사용됩니다.

CASE 03

Google의 SHA-1 충돌 공격 (SHAttered)

2017년 Google은 약 2^63 SHA-1 연산(110개 GPU로 1년)을 수행하여 서로 다른 두 PDF 파일이 같은 SHA-1 해시를 갖도록 만들었습니다.

이 공격으로 SHA-1 기반 디지털 서명의 위조가 가능해졌습니다. Git, SSL 인증서 등 SHA-1을 사용하던 시스템들이 SHA-256으로 전환하는 계기가 되었습니다.

CASE 04

Git의 해시 충돌 시나리오

Git은 SHA-1(160비트)으로 커밋을 식별합니다. 전 세계 모든 Git 저장소의 커밋이 약 10억(약 2^30)개라면, 충돌 확률은 약 2^60/(2×2^160) = 2^(-101)로 극히 낮습니다.

Git의 자연 충돌 확률은 무시할 수 있지만, 의도적 공격에는 취약합니다. Git은 SHA-256으로 전환을 진행 중입니다.

CASE 05

분산 시스템의 데이터 중복 제거(Deduplication)

클라우드 스토리지에서 SHA-256 해시로 파일 중복을 감지합니다. 10억 개 파일이 저장된 경우 충돌 확률은 약 10^18/(2×2^256) ≈ 10^(-59)입니다.

SHA-256 기반 중복 제거는 사실상 완벽합니다. 충돌보다 하드웨어 오류로 인한 데이터 손상 확률이 훨씬 높습니다.

glossary

용어 사전

해시 함수(Hash Function): 임의 길이의 입력을 고정 길이의 출력(해시값)으로 변환하는 함수입니다. 같은 입력은 항상 같은 출력을 생성합니다.
해시 충돌(Hash Collision): 서로 다른 두 입력이 같은 해시값을 생성하는 현상입니다. 해시 공간이 유한하므로 이론적으로 반드시 존재합니다.
생일 공격(Birthday Attack): 생일 문제의 원리를 이용하여 해시 충돌을 효율적으로 찾는 공격 방법입니다. 2^(n/2) 연산만으로 n비트 해시의 충돌을 찾을 수 있습니다.
SHA-256: 256비트 출력을 가진 보안 해시 알고리즘입니다. 현재 가장 널리 사용되는 암호학적 해시 함수 중 하나입니다.
MD5: 128비트 해시 함수로, 충돌 생성이 쉬워 보안 용도로 사용이 금지되었습니다. 파일 체크섬에만 제한적으로 사용됩니다.
UUID v4: 122비트 랜덤 값을 기반으로 생성하는 범용 고유 식별자입니다. 충돌 확률이 극히 낮아 분산 시스템에서 ID로 널리 사용됩니다.
충돌 저항(Collision Resistance): 같은 해시값을 가진 서로 다른 두 입력을 찾기 어려운 성질입니다. 암호학적 해시 함수의 핵심 보안 요구사항입니다.
프리이미지 저항(Preimage Resistance): 주어진 해시값에 대해 원래 입력을 찾기 어려운 성질입니다. 해시 충돌과 별개의 보안 속성으로, 비밀번호 해싱에 중요합니다.

next tools