충돌 저항성 (Collision Resistance)
1. 개요
충돌 저항성(Collision Resistance)이란 서로 다른 두 개의 입력값이 동일한 해시값(Hash Value)을 생성하는 사례, 즉 '충돌(Collision)'을 찾아내는 것이 계산적으로 불가능에 가까울 만큼 어려운(Computationally Infeasible) 성질을 의미한다.
암호학적 해시 함수(Cryptographic Hash Function)는 임의의 길이를 가진 데이터를 고정된 길이의 비트열로 변환하는 함수이다. 이때 출력값의 범위는 유한하지만 입력값의 범위는 무한하므로, 수학적으로는 반드시 서로 다른 입력에 대해 동일한 출력이 발생하는 지점이 존재한다. 이를 비둘기집 원리(Pigeonhole Principle)라고 한다.
비둘기집 원리 예시: 10개의 비둘기집에 11마리의 비둘기가 들어간다면, 적어도 하나의 집에는 두 마리 이상의 비둘기가 함께 들어가게 된다. 이처럼 해시 함수의 출력 공간(비둘기집)보다 입력 가능한 데이터의 가짓수(비둘기)가 훨씬 많기 때문에 충돌은 반드시 발생한다.
그러나 보안성이 높은 해시 함수는 이러한 충돌 쌍을 찾는 데 드는 시간과 자원이 현대의 컴퓨팅 능력으로 감당할 수 없을 만큼 방대해야 하며, 이를 '충돌 저항성이 있다'고 표현한다.
2. 작동 원리와 수학적 배경
해시 함수 $H$가 있을 때, 충돌 저항성은 다음 조건을 만족하는 두 입력값 $x$와 $y$를 찾는 것이 매우 어려워야 함을 의미한다.
$$x \neq y \text{ 이지만, } H(x) = H(y)$$
정상적인 해시 함수는 입력값이 단 1비트만 달라져도 출력값이 완전히 달라지는 쇄도 효과(Avalanche Effect)를 가져야 하며, 이를 통해 충돌 발생 가능성을 낮춘다.
[표 1] 해시 함수의 정상 작동과 충돌 발생 비교
| 구분 |
입력값 A |
입력값 B |
결과 (해시값) |
상태 |
비고 |
| 정상 작동 |
"Hello" |
"Hello!" |
$H(A) \neq H(B)$ |
정상 |
쇄도 효과(Avalanche Effect)가 정상적으로 작동함 |
| 충돌 발생 |
"Data_1" |
"Data_2" |
$H(A) = H(B)$ |
충돌 |
서로 다른 입력이 동일한 결과 생성 |
3. 생일 공격 (Birthday Attack)
생일 공격은 확률론의 '생일 문제(Birthday Problem)'를 응용한 공격 기법으로, 특정 해시값과 일치하는 값을 찾는 것이 아니라, 어떤 값이든 상관없이 동일한 해시값을 갖는 임의의 두 쌍을 찾는 공격이다.
원리와 시간 복잡도
생일 문제에 따르면, 23명만 모여도 그중 생일이 같은 사람이 있을 확률이 50%를 넘는다. 이는 365일이라는 전체 범위에 비해 훨씬 적은 표본만으로도 충돌을 찾을 수 있음을 시사한다.
해시 함수의 출력 공간의 크기가 $N$일 때, 무작위로 입력값을 선택하여 충돌을 찾을 확률은 $O(N)$이 아니라 $O(\sqrt{N})$의 시간 복잡도를 갖는다.
- 단순 역상 공격: 특정 값 $y$에 대해 $H(x) = y$인 $x$를 찾으려면 평균 $N/2$번의 시도가 필요하다.
- 생일 공격: 임의의 $x, y$에 대해 $H(x) = H(y)$인 쌍을 찾으려면 평균 $\sqrt{N}$번의 시도만으로도 높은 확률로 성공한다.
따라서 128비트 해시 함수는 이론적으로 $2^{128}$의 보안 강도를 가질 것 같지만, 생일 공격으로 인해 실제 충돌 저항성 보안 강도는 $2^{64}$ 수준으로 급격히 떨어진다.
4. 충돌 저항성과 다른 보안 특성의 비교
해시 함수의 보안성은 크게 세 가지 저항성으로 구분된다. 이들은 서로 밀접하게 연관되어 있으나 공격 목표와 난이도에서 차이가 있다.
[표 2] 해시 함수 보안 특성 비교
| 특성 |
정의 |
공격 목표 |
보안 강도 (출력 $n$비트 기준) |
| 제1 역상 저항성 |
해시값 $y$가 주어졌을 때, $H(x)=y$인 $x$를 찾기 어려움 |
특정 출력값의 원본 찾기 |
$2^n$ |
| 제2 역상 저항성 |
입력값 $x$가 주어졌을 때, $H(x)=H(x')$인 $x' \neq x$를 찾기 어려움 |
특정 입력값과 충돌하는 다른 값 찾기 |
$2^n$ |
| 충돌 저항성 |
$H(x)=H(x')$를 만족하는 임의의 $x, x'$ 쌍을 찾기 어려움 |
어떤 값이든 상관없이 충돌 쌍 찾기 |
$2^{n/2}$ |
참고: 충돌 저항성이 깨지면 제2 역상 저항성도 위협받을 수 있지만, 그 역은 성립하지 않는다.
5. 디지털 서명 적용 사례 및 피해 시나리오
충돌 저항성은 특히 디지털 서명(Digital Signature) 메커니즘에서 핵심적인 역할을 한다. 디지털 서명은 원본 데이터 전체를 암호화하는 대신, 데이터의 해시값에 개인키로 서명하는 방식을 취한다.
적용 프로세스
- 송신자가 메시지 $M$의 해시값 $H(M)$을 계산한다.
- $H(M)$에 개인키로 서명하여 서명값 $S$를 생성한다.
- 수신자는 메시지 $M$의 해시값 $H(M)$을 직접 계산하고, $S$를 공개키로 검증하여 일치 여부를 확인한다.
충돌 발생 시 피해 시나리오
만약 해시 함수의 충돌 저항성이 깨져 공격자가 $H(M_1) = H(M_2)$인 두 메시지를 생성할 수 있다면 다음과 같은 공격이 가능하다.
1. 계약서 위조: 공격자가 정상적인 계약서 $M_1$과 자신에게 유리한 위조 계약서 $M_2$를 준비한다. 두 문서의 해시값이 동일하도록 조작한다.
2. 서명 유도: 피해자에게 $M_1$을 보여주고 디지털 서명을 받는다. 이때 서명값 $S$는 $H(M_1)$에 대한 서명이다.
3. 치환 공격: 공격자는 서명값 $S$를 그대로 유지한 채, 메시지만 $M_2$로 바꾼다.
4. 검증 통과: 수신자(또는 법원)가 검증할 때, $H(M_2)$는 $H(M_1)$과 동일하므로 서명 $S$는 유효한 것으로 판명된다. 결과적으로 피해자는 서명한 적 없는 $M_2$에 대해 법적 책임을 지게 된다.
6. 실제 사례 및 취약점 분석
과거 표준으로 사용되었으나 충돌 저항성 결여로 폐기된 알고리즘들은 보안 생태계에 큰 경종을 울렸다.
- MD5 (Message-Digest algorithm 5): 1990년대 널리 쓰였으나, 2004년 이후 효율적인 충돌 생성 방법이 발견되었다. 특히 '선택된 접두사 충돌(Chosen-prefix collision)' 공격을 통해 서로 다른 두 파일이 동일한 해시값을 갖게 조작할 수 있게 되었으며, 현재는 일반 PC에서도 수 초 내에 충돌 쌍을 생성할 수 있어 보안 목적으로 사용이 금지되었다.
- SHA-1 (Secure Hash Algorithm 1): 구글(Google)과 CWI 연구소는 2017년 'SHAttered' 공격을 통해 서로 다른 두 PDF 파일이 동일한 SHA-1 해시값을 갖게 하는 실제 충돌 사례를 증명하였다. 이는 이론적 취약점이 실제 공격으로 구현될 수 있음을 보여주었으며, 이로 인해 웹 브라우저 및 인증서 기관들은 SHA-1 지원을 중단했다.
7. 현대적 대응 및 권장 사항
현대 암호학에서는 생일 공격과 최신 연산 능력을 고려하여 더 긴 출력 길이를 가진 알고리즘을 권장한다.
[표 3] 주요 해시 알고리즘별 보안 강도 비교
| 알고리즘 |
출력 길이 (비트) |
충돌 저항성 강도 (비트) |
현재 상태 |
권장 용도 |
| MD5 |
128 |
$\approx 0$ (파괴됨) |
사용 금지 |
단순 체크섬 (비보안) |
| SHA-1 |
160 |
$\approx 0$ (파괴됨) |
사용 금지 |
레거시 시스템 유지보수 |
| SHA-256 |
256 |
$2^{128}$ |
안전 |
일반적인 보안 표준 |
| SHA-512 |
512 |
$2^{256}$ |
매우 안전 |
고보안 요구 시스템 |
| SHA-3 |
가변 |
$2^{n/2}$ |
매우 안전 |
차세대 표준, SHA-2 보완 |
안전한 해시 함수 선택 기준
- 충분한 출력 길이: 생일 공격을 고려하여 최소 256비트 이상의 출력 길이를 가진 알고리즘(SHA-256 이상)을 선택해야 한다.
- 검증된 표준 사용: NIST(미국 국립표준기술연구소) 등 공신력 있는 기관에서 표준화하고 학계의 검증을 거친 알고리즘을 사용한다.
- 용도별 분리: 단순 무결성 검사(Checksum)와 암호학적 보안(Digital Signature, Password Hashing)을 구분하여, 후자의 경우 반드시 충돌 저항성이 보장된 함수를 사용해야 한다. 단, 패스워드 저장 시에는 단순 충돌 저항성 함수(SHA-256 등)가 아닌, 연산 비용을 의도적으로 높인 Key Stretching 함수(예: Argon2, bcrypt, scrypt)를 사용해야 브루트포스 공격으로부터 안전하다.
# 충돌 저항성 (Collision Resistance)
## 1. 개요
**충돌 저항성(Collision Resistance)**이란 서로 다른 두 개의 입력값이 동일한 해시값(Hash Value)을 생성하는 사례, 즉 '충돌(Collision)'을 찾아내는 것이 계산적으로 불가능에 가까울 만큼 어려운(Computationally Infeasible) 성질을 의미한다.
암호학적 해시 함수(Cryptographic Hash Function)는 임의의 길이를 가진 데이터를 고정된 길이의 비트열로 변환하는 함수이다. 이때 출력값의 범위는 유한하지만 입력값의 범위는 무한하므로, 수학적으로는 반드시 서로 다른 입력에 대해 동일한 출력이 발생하는 지점이 존재한다. 이를 **비둘기집 원리(Pigeonhole Principle)**라고 한다.
> **비둘기집 원리 예시:** 10개의 비둘기집에 11마리의 비둘기가 들어간다면, 적어도 하나의 집에는 두 마리 이상의 비둘기가 함께 들어가게 된다. 이처럼 해시 함수의 출력 공간(비둘기집)보다 입력 가능한 데이터의 가짓수(비둘기)가 훨씬 많기 때문에 충돌은 반드시 발생한다.
그러나 보안성이 높은 해시 함수는 이러한 충돌 쌍을 찾는 데 드는 시간과 자원이 현대의 컴퓨팅 능력으로 감당할 수 없을 만큼 방대해야 하며, 이를 '충돌 저항성이 있다'고 표현한다.
## 2. 작동 원리와 수학적 배경
해시 함수 $H$가 있을 때, 충돌 저항성은 다음 조건을 만족하는 두 입력값 $x$와 $y$를 찾는 것이 매우 어려워야 함을 의미한다.
$$x \neq y \text{ 이지만, } H(x) = H(y)$$
정상적인 해시 함수는 입력값이 단 1비트만 달라져도 출력값이 완전히 달라지는 **쇄도 효과(Avalanche Effect)**를 가져야 하며, 이를 통해 충돌 발생 가능성을 낮춘다.
### [표 1] 해시 함수의 정상 작동과 충돌 발생 비교
| 구분 | 입력값 A | 입력값 B | 결과 (해시값) | 상태 | 비고 |
| :--- | :--- | :--- | :--- | :--- | :--- |
| **정상 작동** | "Hello" | "Hello!" | $H(A) \neq H(B)$ | **정상** | 쇄도 효과(Avalanche Effect)가 정상적으로 작동함 |
| **충돌 발생** | "Data_1" | "Data_2" | $H(A) = H(B)$ | **충돌** | 서로 다른 입력이 동일한 결과 생성 |
## 3. 생일 공격 (Birthday Attack)
생일 공격은 확률론의 **'생일 문제(Birthday Problem)'**를 응용한 공격 기법으로, 특정 해시값과 일치하는 값을 찾는 것이 아니라, **어떤 값이든 상관없이 동일한 해시값을 갖는 임의의 두 쌍**을 찾는 공격이다.
### 원리와 시간 복잡도
생일 문제에 따르면, 23명만 모여도 그중 생일이 같은 사람이 있을 확률이 50%를 넘는다. 이는 365일이라는 전체 범위에 비해 훨씬 적은 표본만으로도 충돌을 찾을 수 있음을 시사한다.
해시 함수의 출력 공간의 크기가 $N$일 때, 무작위로 입력값을 선택하여 충돌을 찾을 확률은 $O(N)$이 아니라 $O(\sqrt{N})$의 시간 복잡도를 갖는다.
- **단순 역상 공격:** 특정 값 $y$에 대해 $H(x) = y$인 $x$를 찾으려면 평균 $N/2$번의 시도가 필요하다.
- **생일 공격:** 임의의 $x, y$에 대해 $H(x) = H(y)$인 쌍을 찾으려면 평균 $\sqrt{N}$번의 시도만으로도 높은 확률로 성공한다.
따라서 128비트 해시 함수는 이론적으로 $2^{128}$의 보안 강도를 가질 것 같지만, 생일 공격으로 인해 실제 충돌 저항성 보안 강도는 $2^{64}$ 수준으로 급격히 떨어진다.
## 4. 충돌 저항성과 다른 보안 특성의 비교
해시 함수의 보안성은 크게 세 가지 저항성으로 구분된다. 이들은 서로 밀접하게 연관되어 있으나 공격 목표와 난이도에서 차이가 있다.
### [표 2] 해시 함수 보안 특성 비교
| 특성 | 정의 | 공격 목표 | 보안 강도 (출력 $n$비트 기준) |
| :--- | :--- | :--- | :--- |
| **제1 역상 저항성** | 해시값 $y$가 주어졌을 때, $H(x)=y$인 $x$를 찾기 어려움 | 특정 출력값의 원본 찾기 | $2^n$ |
| **제2 역상 저항성** | 입력값 $x$가 주어졌을 때, $H(x)=H(x')$인 $x' \neq x$를 찾기 어려움 | 특정 입력값과 충돌하는 다른 값 찾기 | $2^n$ |
| **충돌 저항성** | $H(x)=H(x')$를 만족하는 임의의 $x, x'$ 쌍을 찾기 어려움 | 어떤 값이든 상관없이 충돌 쌍 찾기 | $2^{n/2}$ |
**참고:** 충돌 저항성이 깨지면 제2 역상 저항성도 위협받을 수 있지만, 그 역은 성립하지 않는다.
## 5. 디지털 서명 적용 사례 및 피해 시나리오
충돌 저항성은 특히 **디지털 서명(Digital Signature)** 메커니즘에서 핵심적인 역할을 한다. 디지털 서명은 원본 데이터 전체를 암호화하는 대신, 데이터의 해시값에 개인키로 서명하는 방식을 취한다.
### 적용 프로세스
1. 송신자가 메시지 $M$의 해시값 $H(M)$을 계산한다.
2. $H(M)$에 개인키로 서명하여 서명값 $S$를 생성한다.
3. 수신자는 메시지 $M$의 해시값 $H(M)$을 직접 계산하고, $S$를 공개키로 검증하여 일치 여부를 확인한다.
### 충돌 발생 시 피해 시나리오
만약 해시 함수의 충돌 저항성이 깨져 공격자가 $H(M_1) = H(M_2)$인 두 메시지를 생성할 수 있다면 다음과 같은 공격이 가능하다.
1. **계약서 위조:** 공격자가 정상적인 계약서 $M_1$과 자신에게 유리한 위조 계약서 $M_2$를 준비한다. 두 문서의 해시값이 동일하도록 조작한다.
2. **서명 유도:** 피해자에게 $M_1$을 보여주고 디지털 서명을 받는다. 이때 서명값 $S$는 $H(M_1)$에 대한 서명이다.
3. **치환 공격:** 공격자는 서명값 $S$를 그대로 유지한 채, 메시지만 $M_2$로 바꾼다.
4. **검증 통과:** 수신자(또는 법원)가 검증할 때, $H(M_2)$는 $H(M_1)$과 동일하므로 서명 $S$는 유효한 것으로 판명된다. 결과적으로 피해자는 서명한 적 없는 $M_2$에 대해 법적 책임을 지게 된다.
## 6. 실제 사례 및 취약점 분석
과거 표준으로 사용되었으나 충돌 저항성 결여로 폐기된 알고리즘들은 보안 생태계에 큰 경종을 울렸다.
- **MD5 (Message-Digest algorithm 5):** 1990년대 널리 쓰였으나, 2004년 이후 효율적인 충돌 생성 방법이 발견되었다. 특히 '선택된 접두사 충돌(Chosen-prefix collision)' 공격을 통해 서로 다른 두 파일이 동일한 해시값을 갖게 조작할 수 있게 되었으며, 현재는 일반 PC에서도 수 초 내에 충돌 쌍을 생성할 수 있어 보안 목적으로 사용이 금지되었다.
- **SHA-1 (Secure Hash Algorithm 1):** 구글(Google)과 CWI 연구소는 2017년 'SHAttered' 공격을 통해 서로 다른 두 PDF 파일이 동일한 SHA-1 해시값을 갖게 하는 실제 충돌 사례를 증명하였다. 이는 이론적 취약점이 실제 공격으로 구현될 수 있음을 보여주었으며, 이로 인해 웹 브라우저 및 인증서 기관들은 SHA-1 지원을 중단했다.
## 7. 현대적 대응 및 권장 사항
현대 암호학에서는 생일 공격과 최신 연산 능력을 고려하여 더 긴 출력 길이를 가진 알고리즘을 권장한다.
### [표 3] 주요 해시 알고리즘별 보안 강도 비교
| 알고리즘 | 출력 길이 (비트) | 충돌 저항성 강도 (비트) | 현재 상태 | 권장 용도 |
| :--- | :---: | :---: | :---: | :--- |
| **MD5** | 128 | $\approx 0$ (파괴됨) | **사용 금지** | 단순 체크섬 (비보안) |
| **SHA-1** | 160 | $\approx 0$ (파괴됨) | **사용 금지** | 레거시 시스템 유지보수 |
| **SHA-256** | 256 | $2^{128}$ | **안전** | 일반적인 보안 표준 |
| **SHA-512** | 512 | $2^{256}$ | **매우 안전** | 고보안 요구 시스템 |
| **SHA-3** | 가변 | $2^{n/2}$ | **매우 안전** | 차세대 표준, SHA-2 보완 |
### 안전한 해시 함수 선택 기준
1. **충분한 출력 길이:** 생일 공격을 고려하여 최소 256비트 이상의 출력 길이를 가진 알고리즘(SHA-256 이상)을 선택해야 한다.
2. **검증된 표준 사용:** NIST(미국 국립표준기술연구소) 등 공신력 있는 기관에서 표준화하고 학계의 검증을 거친 알고리즘을 사용한다.
3. **용도별 분리:** 단순 무결성 검사(Checksum)와 암호학적 보안(Digital Signature, Password Hashing)을 구분하여, 후자의 경우 반드시 충돌 저항성이 보장된 함수를 사용해야 한다. 단, 패스워드 저장 시에는 단순 충돌 저항성 함수(SHA-256 등)가 아닌, 연산 비용을 의도적으로 높인 Key Stretching 함수(예: Argon2, bcrypt, scrypt)를 사용해야 브루트포스 공격으로부터 안전하다.