b비트 해시 함수에는 2ᵇ개의 가능한 출력이 있습니다. 특정한 목표 해시값을 맞히려면 이상적인 모델에서 약 2ᵇ 규모의 시도가 필요하지만, 아무 두 입력이나 같은 해시를 갖는 충돌을 찾는 문제는 훨씬 빠르게 가능성이 커집니다. 비교할 입력 쌍의 수가 시도 횟수의 제곱에 비례해 늘기 때문입니다.
이 현상을 해시 생일 공격이라고 부릅니다. 365개의 생일 중 같은 생일인 두 사람을 찾는 생일 역설과 수학 구조가 같습니다. b비트 이상적 해시의 충돌 확률이 약 50%가 되는 표본 수는 정확히 2^(b/2)가 아니라 약 √(2ln2)×2^(b/2), 즉 약 1.1774×2^(b/2)입니다. 보안 강도를 말할 때는 상수배를 생략해 ‘약 2^(b/2) 작업’이라고 표현합니다.
50% 충돌 지점 n₀.₅≈√(2ln2)·2^(b/2)≈1.1774·2^(b/2)
해시 충돌이란 무엇인가
해시 함수 H는 길이가 다양한 입력을 고정 길이 출력으로 바꿉니다. 서로 다른 두 입력 x≠y가 H(x)=H(y)를 만족하면 충돌입니다. 입력의 가능한 수가 출력의 가능한 수보다 많으므로 비둘기집 원리에 따라 충돌 자체는 반드시 존재합니다. 암호학적 목표는 충돌이 없게 만드는 것이 아니라 계산으로 충돌을 찾기 어렵게 만드는 것입니다.
| 보안 성질 | 공격자가 찾는 것 | 이상적 b비트 해시의 일반적 규모 |
|---|---|---|
| 원상 저항성 | 주어진 h에 대해 H(x)=h인 x | 약 2ᵇ |
| 제2원상 저항성 | 주어진 x와 같은 해시인 다른 y | 약 2ᵇ |
| 충돌 저항성 | 아무 x≠y에 대해 H(x)=H(y) | 약 2^(b/2) |
세 문제를 섞으면 보안 비트 수를 잘못 판단합니다. 생일 공격은 공격자가 두 입력을 모두 자유롭게 고르는 충돌 문제입니다. 이미 정해진 문서 하나와 같은 해시를 갖는 새 문서를 찾는 제2원상 문제는 같은 계산이 아닙니다.
충돌이 없을 정확한 확률
해시 출력 공간의 크기를 M=2ᵇ라고 하겠습니다. 이상적인 해시는 각 입력의 출력이 M개 값에 독립적이고 균일하게 분포한다고 가정합니다. 첫 번째 해시는 무엇이 나와도 충돌이 없습니다. 두 번째가 첫 번째와 다를 확률은 (M−1)/M입니다. 세 번째가 앞의 둘과 다를 확률은 (M−2)/M입니다.
P(충돌 없음)=∏ₖ₌₀ⁿ⁻¹(1−k/M)=M(M−1)…(M−n+1)/Mⁿ
따라서 적어도 한 번 충돌할 확률은 1에서 이 값을 뺀 것입니다. n>M이면 비둘기집 원리에 따라 충돌 확률은 1입니다. 하지만 생일 경계는 M보다 훨씬 작은 √M 부근에서 이미 충돌 가능성이 커진다는 점을 보여 줍니다.
지수 근사로 50% 지점 구하기
n이 M에 비해 충분히 작을 때 ln(1−u)≈−u를 사용할 수 있습니다. 충돌 없음 확률의 로그는 각 k에 대해 ln(1−k/M)을 더한 값이고, 이는 대략 −(0+1+···+n−1)/M=−n(n−1)/(2M)입니다.
P(충돌)≈1−exp(−n(n−1)/(2M))
이 확률을 1/2로 놓으면 exp(−n(n−1)/(2M))≈1/2입니다. 큰 n에서는 n(n−1)≈n²이므로 n≈√(2Mln2)입니다. M=2ᵇ를 넣으면 n≈√(2ln2)·2^(b/2)이고 √(2ln2)≈1.177410입니다.
왜 제곱근에서 충돌이 커지는가
n개의 해시 중 비교 가능한 서로 다른 쌍은 n(n−1)/2개입니다. 특정한 한 쌍이 충돌할 확률은 이상적인 모델에서 1/M입니다. 기대되는 충돌 쌍 수는 n(n−1)/(2M)입니다. 이 값이 1 정도가 되는 지점이 n≈√(2M), 즉 출력 공간 크기의 제곱근 부근입니다.
쌍 사건들이 완전히 독립인 것은 아니므로 기대값만으로 정확한 충돌 확률을 얻지는 못합니다. 하지만 왜 규모가 √M인지 직관적으로 보여 줍니다. 정확한 곱셈식이나 지수 근사를 쓰면 원하는 확률에 해당하는 상수까지 계산할 수 있습니다.
b비트별 생일 경계
| 출력 길이 b | 출력 공간 2ᵇ | 50% 충돌 표본 수 근사 |
|---|---|---|
| 32비트 | 약 4.29×10⁹ | 약 77,163 |
| 64비트 | 약 1.84×10¹⁹ | 약 5.06×10⁹ |
| 128비트 | 약 3.40×10³⁸ | 약 2.17×10¹⁹ |
| 256비트 | 약 1.16×10⁷⁷ | 약 4.01×10³⁸ |
표의 50% 지점은 이상적인 균일 해시와 무작위에 가까운 독립 입력을 가정한 확률 계산입니다. 실제 공격 비용에는 해시 계산 속도, 저장과 검색, 병렬화, 입력 생성 비용이 포함됩니다. 알려진 구조적 약점이 있는 해시는 일반 생일 공격보다 훨씬 적은 작업으로 충돌이 발견될 수 있습니다.
128비트 출력은 왜 충돌 보안이 약 64비트인가
충돌 탐색의 일반적인 작업량이 2^(b/2) 규모이므로 b=128이면 약 2⁶⁴ 규모입니다. 출력 길이와 충돌 보안 강도를 같은 수로 말하면 안 됩니다. 256비트 이상적 해시는 일반 충돌 공격에 대해 약 128비트 보안 강도를 제공한다고 표현합니다.
여기서 ‘128비트 보안’은 정확히 2¹²⁸번 수행하면 성공한다는 보장이 아니라, 알려진 일반 공격의 작업 규모를 2¹²⁸ 수준으로 비교하는 표현입니다. 알고리즘의 실제 구조와 사용 방식이 안전해야 하며, 출력 일부만 잘라 쓰면 유효 b가 줄어듭니다.
저장 공간과 정렬 비용도 필요하다
가장 단순한 생일 공격은 많은 입력의 해시를 계산해 저장하고, 같은 출력이 나타나는지 표나 정렬로 확인합니다. 약 2^(b/2)개의 해시를 저장하면 메모리 요구량도 큽니다. 해시 테이블을 쓰면 평균적인 검색은 빠르지만 메모리와 충돌 처리 비용이 듭니다.
메모리를 덜 쓰는 충돌 탐색 기법도 있지만 시간·공간 절충이 생깁니다. 따라서 ‘2^(b/2)’는 핵심적인 해시 평가 횟수의 규모를 나타내는 이론적 기준이며 실제 장비의 총비용과 동일하지 않습니다.
무작위 충돌 위험과 악의적 공격은 다르다
데이터베이스에 n개의 임의 식별자를 저장할 때 우연한 충돌 위험을 계산하는 것과 공격자가 입력을 조절해 충돌을 찾는 것은 목적이 다릅니다. 전자는 시스템 규모에 맞춰 허용 가능한 확률을 정하는 신뢰성 문제이고, 후자는 공격자가 계산 자원을 집중하는 보안 문제입니다. 수학 공식은 비슷해도 위험 평가가 다릅니다.
무작위 식별자에는 충돌 시 재생성하는 절차를 둘 수 있습니다. 디지털 서명이나 인증에 쓰이는 해시 충돌은 서로 다른 문서를 같은 다이제스트로 만들 가능성과 연결될 수 있어 훨씬 엄격한 선택이 필요합니다. 용도에 맞는 표준과 충분한 출력 길이를 사용해야 합니다.
MD5와 SHA-1 사례에서 배울 점
이상적인 b비트 모델은 비교 기준입니다. 실제 해시 함수에 설계 약점이 있으면 더 빠른 특수 공격이 가능합니다. MD5에는 실용적인 충돌 생성법이 알려졌고, SHA-1도 2017년 공개된 SHAttered 연구에서 서로 다른 PDF 파일의 실제 충돌이 제시되었습니다. 이는 단순한 무작위 생일 탐색보다 함수 내부 구조를 이용한 결과입니다.
그러므로 출력 길이만 보고 안전성을 판단할 수 없습니다. 현재 용도에 승인된 표준인지, 충돌 공격 연구가 어떤 수준인지, 단순 해시가 아니라 MAC이나 디지털 서명 같은 상위 구성에서 어떻게 쓰이는지를 함께 확인해야 합니다.
생일 역설과 정확히 같은 수학
23명만 모여도 생일이 같은 쌍이 있을 확률이 50%를 넘는 계산에서는 출력 공간 M이 365입니다. 50% 근사식 √(2×365×ln2)은 약 22.49이므로 정수 표본 23명에서 절반을 넘습니다. 해시에서는 365일 대신 2ᵇ개의 다이제스트를 상자처럼 놓습니다.
실제 생일은 계절과 요일 등에 따라 완전히 균일하지 않고 2월 29일도 있지만, 이상적 해시 모델은 균일성을 보안 목표로 삼습니다. 이 비유가 유용한 이유는 특정 값을 맞히는 문제가 아니라 표본들끼리 이루는 모든 쌍을 비교한다는 공통점입니다.
체크디지트와 암호학적 해시는 다르다
EAN-13 바코드 체크디지트의 모듈로 10 계산과 룬 알고리즘의 번호 검증은 입력 실수를 검출하도록 설계되었습니다. 출력 공간이 작고 공격에 견디는 충돌 저항성을 목표로 하지 않습니다. 체크디지트를 암호학적 해시처럼 사용하면 안 됩니다.
자주 하는 계산 실수
- 50% 지점을 정확히 2^(b/2)라고 씁니다. 이는 규모 표기이며 상수까지 포함하면 약 1.1774배입니다.
- 충돌 저항성과 원상 저항성을 같은 2^(b/2)로 계산합니다.
- 해시 출력이 균일하고 독립적으로 행동한다는 이상적 모델을 밝히지 않습니다.
- b비트 출력을 일부만 사용하면서 원래 b비트의 충돌 강도를 유지한다고 생각합니다.
- 해시값 n개가 만들 수 있는 쌍을 n²개라고 정확히 적습니다. 정확히는 n(n−1)/2개입니다.
- 체크섬과 암호학적 해시의 목적을 혼동합니다.
해시 생일 공격 FAQ
2^(b/2)번이면 충돌이 반드시 생기나요?
아닙니다. 이상적 모델에서 그 부근부터 충돌 확률이 상당해진다는 규모입니다. 약 1.1774×2^(b/2)개의 무작위 표본에서 충돌 확률이 약 50%입니다. 보장은 2ᵇ+1개의 서로 다른 입력 해시를 모았을 때 비둘기집 원리로 얻습니다.
SHA-256 충돌을 찾는 데 2²⁵⁶번이 필요한가요?
일반 충돌 공격의 기준 규모는 약 2¹²⁸입니다. 특정한 주어진 해시의 원상을 찾는 일반 기준은 약 2²⁵⁶입니다. 서로 다른 보안 성질입니다.
우연한 충돌과 공격자가 만든 충돌의 공식은 같은가요?
이상적인 무작위 출력에서는 기본 확률 구조가 같습니다. 하지만 실제 보안 공격은 입력 선택, 계산·메모리 자원, 해시 함수의 구조적 약점을 활용하므로 위험 모델이 다릅니다.
핵심 정리
b비트 이상적 해시의 출력 공간은 M=2ᵇ입니다. n개 출력에 충돌이 없을 확률은 ∏(1−k/M)이고, 충돌 확률은 대략 1−exp(−n(n−1)/(2M))입니다. 이를 1/2로 놓으면 n≈√(2ln2)·2^(b/2)≈1.1774·2^(b/2)입니다.
2^(b/2)은 충돌 저항성의 규모를 간단히 나타내는 표기입니다. 특정 출력의 원상을 찾는 문제와 구별해야 하며, 실제 함수의 구조적 공격과 시스템의 사용 방식도 함께 검토해야 합니다. 해시 길이가 b비트라는 사실만으로 모든 용도에서 b비트 보안이 생기는 것은 아닙니다.