해시 함수와 공격 성질
역상·제2역상·충돌 저항성과 생일 공격, 대표 해시 구조를 비교합니다.
1. 해시는 메시지를 대표값으로 대응시킨다
일반 암호학적 해시 함수는 비밀키 없이 메시지 M을 고정 길이 다이제스트 H(M)으로 만든다. 같은 입력은 같은 값을 만든다. 복호화로 원문을 되찾는 기능은 없지만 짧고 흔한 입력은 후보를 해시해 비교하는 방식으로 추측될 수 있다.
n비트 출력은 최대 2^n가지다. 가능한 입력이 더 많으므로 서로 다른 입력의 해시가 같아지는 충돌은 존재한다. 보안 목표는 충돌의 존재를 없애는 것이 아니라 실용적으로 찾기 어렵게 하는 것이다.
2. 세 가지 저항성을 구별한다
| 성질 | 이미 주어진 것 | 공격자가 찾으려는 것 |
|---|---|---|
| 역상 저항성 | 목표 해시 y | H(M)=y인 입력 M |
| 제2역상 저항성 | 특정 메시지 M | M과 다르지만 해시가 같은 M′ |
| 충돌 저항성 | 고정된 목표 없음 | 서로 다르면서 해시가 같은 M1·M2 |
이미 정해진 계약서를 다른 계약서로 바꾸되 해시를 유지하려는 것은 제2역상 문제다. 공격자가 두 문서를 모두 골라 같은 해시를 만들려는 것은 충돌 문제다. 충돌을 찾았다고 임의의 목표 해시의 입력까지 쉽게 찾게 되는 것은 아니다.
3. 생일 공격과 계산 규모
이상적인 n비트 해시의 일반 공격 규모를 단순화하면 역상·제2역상은 약 2^n, 충돌은 약 2^(n/2)다. 여러 출력 사이에서 비교할 쌍이 빠르게 늘어나므로 충돌은 더 적은 시도로 찾을 수 있다.
이상적인 128비트 해시
역상 공격 규모: 약 2^128
충돌 공격 규모: 약 2^64
이는 일반적인 규모 비교이며 일정 횟수 안에 반드시 성공한다는 뜻은 아니다. 특수한 입력 길이·구조적 약점·다른 공격 모델에는 별도 분석이 필요하다. 시험에서는 생일 확률의 지수함수 유도보다 역상과 충돌의 지수가 다른 이유를 이해한다.
4. 대표 해시 알고리즘과 내부 구조
| 계열 | 대표 출력 길이 | 구조·특징 |
|---|---|---|
| MD5 | 128비트 | 충돌 취약, 새로운 무결성·서명 보호에 부적합 |
| SHA-1 | 160비트 | 충돌 취약, 새로운 서명 용도에 부적합 |
| SHA-2 | 224·256·384·512비트 등 | 메시지를 블록으로 나누어 압축 함수를 반복 |
| SHA-3 | 224·256·384·512비트 | Keccak의 스펀지 구조 |
SHA-256의 내부 블록은 512비트이고 출력은 256비트다. SHA-512의 내부 블록은 1,024비트이고 출력은 512비트다. 블록 크기와 출력 크기를 구분한다. SHA-3는 입력을 흡수(absorb)한 뒤 출력을 짜내는(squeeze) 구조로 이해한다.
일부 반복형 해시에서는 내부 구조를 이용한 길이 확장 공격이 가능하다. 따라서 H(비밀키 || 메시지)처럼 단순히 연결한 값을 임의의 MAC으로 사용하지 않고 HMAC 등 검증된 구성을 쓴다. SHA-3까지 모든 해시가 같은 구조라고 일반화하지 않는다.
5. 해시 비교의 한계
파일의 해시가 신뢰 가능한 기준과 다르면 파일이 달라진 것이다. 값이 같으면 동일성의 강한 근거가 될 수 있지만, 충돌 가능성 때문에 수학적 동일성 증명과 같지는 않다. 특히 공격자가 파일과 기준값을 모두 제공했다면 진짜 발신자를 확인한 것이 아니다.
입력의 작은 변화가 많은 출력 비트를 바꾸는 쇄도 효과는 바람직한 성질이지만 안전성의 충분조건은 아니다. 메시지 인증은 MAC·HMAC과 메시지 인증, 비밀번호 저장의 후보 추측 방어는 비밀번호 기반 인증과 보호에서 구분한다.
개념 확인 문제
문제를 누르면 바로 아래에서 정답과 해설을 확인할 수 있습니다.
01이미 주어진 계약서와 다른 문서를 만들되 해시를 같게 하는 공격 목표는?
제2역상 공격이다. 공격자가 처음부터 두 문서를 모두 선택하여 같은 해시를 만드는 충돌 공격과 구별한다.
02이상적인 128비트 해시의 일반적인 충돌 공격 규모는 약 2^128인가?
아니다. 생일 공격에 따른 일반 충돌 규모는 약 2^64다. 역상 공격의 약 2^128 규모와 구분한다. 일정 시도 안에 반드시 성공한다는 뜻은 아니다.