역상 문제에서는 목표 해시값이 먼저 주어지고, 그 값에 대응하는 입력을 찾습니다. 충돌 문제에서는 목표 해시값이 미리 정해져 있지 않으며, 같은 해시값을 내는 서로 다른 입력 두 개를 공격자가 함께 찾습니다.
n비트 출력을 갖는 이상적 균등 함수에서 역상을 찾는 평균 시도량은 대략 2ⁿ이고 충돌을 찾는 평균 규모는 대략 2ⁿᐟ²입니다. 실제 표준 알고리즘의 보안 강도는 구조와 공격 결과를 따르므로 이 장난감 근사를 그대로 실제 공격 비용으로 옮기면 안 됩니다.
먼저 공격자가 고정해야 하는 값을 봅니다
암호학적 해시 함수는 길이가 다른 메시지를 고정 길이 digest로 바꿉니다. 해시값만 보고 원문을 복원하지 못하게 하는 성질과, 같은 해시를 만드는 두 입력을 찾기 어렵게 하는 성질은 서로 다른 공격 문제입니다. NIST는 승인된 해시 함수의 기대 성질로 역상 저항성, 제2역상 저항성, 충돌 저항성을 구분합니다. FIPS 180-4와 FIPS 202는 각각 SHA-2 계열과 SHA-3 계열 등 표준 함수의 명세를 정합니다. 두 표준은 출력 크기와 알고리즘을 정의하며, 아래의 8비트 예는 그 표준 알고리즘의 내부 동작을 흉내 내지 않습니다.
| 문제 | 먼저 주어진 조건 | 공격자가 찾는 것 |
|---|---|---|
| 역상(preimage) | 목표 해시값 y | H(x)=y인 입력 x |
| 제2역상(second preimage) | 기준 입력 x | x와 다른 x′로 H(x′)=H(x) |
| 충돌(collision) | 해시 함수만 정해짐 | 서로 다른 x와 x′로 H(x)=H(x′)인 쌍 |
역상과 제2역상은 기존 목표가 고정되어 있습니다. 충돌은 공격자가 양쪽 입력을 모두 고를 수 있으므로 후보 쌍이 늘어나는 속도가 다릅니다. 따라서 ‘같은 digest를 찾았다’라는 결과만으로는 어느 성질을 시험했는지 알 수 없습니다. 문제에서 기준 메시지가 먼저 주어졌는지, 목표 digest만 주어졌는지, 공격자가 두 메시지를 모두 선택했는지를 표시하면 유형을 정확히 정할 수 있습니다.
8비트 장난감 출력으로 탐색 규모를 비교합니다
다음 계산은 해시 출력이 0부터 255까지인 이상적 무작위 함수라고 가정합니다. 특정 출력 하나를 맞히는 역상 탐색은 한 번마다 성공 확률이 1/256이므로 평균적으로 256번을 시도합니다. 성공 확률이 50%를 넘는 시도 수는 178번입니다. 계산은 1−(255/256)^q≥0.5를 만족하는 가장 작은 정수 q를 찾은 결과입니다. 평균 시도 횟수와 50% 도달 시도 횟수는 서로 다른 통계량입니다.
반면 충돌은 표본을 추가할 때 기존 표본과 짝을 이룰 가능성이 함께 늘어납니다. 표본이 20개라면 비교할 쌍은 20×19/2=190개입니다. 각 쌍이 같을 확률을 1/256으로 둔 birthday 근사에서는 충돌 확률이 1−exp(−190/256)≈52.39%입니다. 정확식은 1−(256×255×…×237)/256²⁰이며 약 53.32%입니다. 이 예에서 근사와 정확식의 차이는 약 0.92퍼센트포인트입니다. 근사는 정확값과 크게 동떨어지지 않지만 정확식과 같지는 않으므로, 문제에서 요구하는 정밀도에 맞춰 선택합니다.
문제 문장에서 유형을 고르는 네 단계
- 목표 digest가 먼저 제시됐는지 확인합니다.
- 기준 입력 메시지가 주어졌는지 별도로 표시합니다.
- 입력을 하나 찾는지, 서로 다른 입력 두 개를 찾는지 씁니다.
- 출력 비트 수와 이상적·균등·독립 가정을 확인한 뒤에만 탐색 규모를 비교합니다.
흔한 실수는 역상과 충돌을 둘 다 ‘해시값이 같은 입력 찾기’라고 뭉뚱그리는 것입니다. 또 제2역상에서 주어진 첫 메시지를 바꿔도 되는 것처럼 말하면 충돌 문제와 구별되지 않습니다. 실제 보안 강도를 수치로 말할 때에도 출력 길이만 보고 일반화하지 말아야 합니다. NIST의 승인 해시 안내는 특정 계열의 표와 보안 강도 범위를 제시하지만, 이상적 무작위 함수의 장난감 계산과 표준 알고리즘 평가는 다른 질문입니다. FIPS 180-4에는 개정 계획이, FIPS 202에는 향후 업데이트와 비규범 부록 정오표가 공지되어 있으므로 이 글은 함수의 기본 구분만 다루고 최신 표준 상태를 인증하지 않습니다.
가려 두고 직접 분류합니다
교육용 회상 문제입니다. 감사자가 보고서 원문 x와 그 해시값 H(x)를 모두 제공하고, 조사자가 H(x)와 같은 digest를 만드는 x와 다른 메시지를 찾습니다. 이는 역상, 제2역상, 충돌 중 어떤 문제인가요? 기준 입력과 목표 digest 가운데 무엇이 주어졌는지도 답에 포함하세요.
정답은 제2역상 문제입니다. 보고서 원문 x와 H(x)가 모두 주어졌고, 조사자는 기준 입력과 다른 메시지가 같은 해시를 내도록 찾아야 합니다. 목표 digest만 고정하고 기준 입력을 주지 않았다면 역상 문제이며, 기준 입력 없이 두 메시지를 모두 고를 수 있다면 충돌 문제입니다. 표와 문항은 개념 설명을 위해 새로 구성한 교육 예시입니다.
정답을 가리고 확인해 보세요
이 글을 위해 만든 학습 예시이며 공식 기출문제나 판매 카드의 인용이 아닙니다.
기준 메시지 x가 주어진 뒤 x와 다른 x′를 골라 H(x′)=H(x)를 만드는 문제는 역상, 제2역상, 충돌 중 무엇인가?
정답과 해설 확인
제2역상 문제입니다.기준 입력 x가 먼저 고정되어 있고 그와 다른 입력을 찾아 같은 출력을 내야 합니다. 공격자가 두 입력을 모두 고르는 충돌 문제와 다릅니다.