Cryptographic Hashing — 암호학적 해시 함수

전자 서명에서 SHA로 메시지를 압축해 서명 크기를 줄인다고 했다. 그런데 SHA는 어떻게 동작하는가? 왜 역산이 불가능한가? 그리고 MD5나 SHA-1은 왜 더 이상 믿을 수 없는가? 이 글은 그 질문들에 답한다.

해시 함수의 3대 보안 성질

암호학적 해시 함수(cryptographic hash function) $H$는 임의 길이의 메시지 $m$을 고정 크기의 해시값 $h$로 변환한다. 암호화라 부르지 않는 이유는 되돌리는 연산이 없기 때문이다. 복호가 있는 암호와 달리 해시는 한 방향으로만 간다.

$$h = H(m)$$

단순히 데이터를 압축하는 것만으로는 부족하다. 암호 목적으로 안전하려면 세 가지 성질이 필요하다.

일방향성(Pre-image Resistance): $h$가 주어져도 $H(m) = h$인 $m$을 찾을 수 없다. 평균 $2^n$번의 시도가 필요하다. 서명 위조를 위해 특정 해시값을 갖는 메시지를 조작하는 것이 불가능해야 한다.

2차 역상 저항(Second Pre-image Resistance): $m_1$이 주어졌을 때 $H(m_2) = H(m_1)$인 $m_2 \neq m_1$을 찾을 수 없다. 평균 $2^n$번이 필요하다. 기존 문서와 같은 해시를 갖는 위조 문서를 만들 수 없어야 한다.

충돌 저항성(Collision Resistance): $H(m_1) = H(m_2)$인 임의의 쌍 $(m_1, m_2)$를 찾을 수 없다. Birthday Paradox에 의해 $2^{n/2}$번이면 충분하다. 이것이 세 성질 중 가장 약하므로 해시 길이를 결정하는 기준이 된다.

이 세 성질을 Checksum(체크섬)과 비교하면 차이가 명확해진다. 체크섬은 $A+1, B-1$ 변조에도 값이 변하지 않아 의도적 변조를 막지 못한다. 반면 암호학적 해시는 1비트 변경에도 해시값이 완전히 달라진다 — 눈사태 효과(Avalanche Effect).

Merkle-Damgård 구조

SHA-256의 내부는 Merkle-Damgård(MD) 구조 를 따른다. 고정 크기 입력만 처리할 수 있는 압축 함수 $f$를 이용해 임의 길이 입력을 처리하는 방법이다.

① 패딩: 메시지 뒤에 1 비트를 붙이고, 512 비트 블록 경계에 맞게 0으로 채운 뒤 끝에 64 비트 원본 길이를 붙인다. 이로써 입력이 512 비트의 배수가 된다.

② 블록 분할 및 순차 압축: 512 비트 블록으로 나눈 뒤, 초기값(IV)부터 시작해 각 블록을 차례로 압축한다.

$$h_i = f(h_{i-1},\ m_i)$$

③ 압축 함수 내부: 압축 함수는 256비트 연쇄값 $h_{i-1}$과 512비트 블록 $m_i$를 함께 받아 256비트를 내놓는다. 먼저 $h_{i-1}$의 8개 32비트 워드를 작업 변수 $a, \ldots, h$에 옮기고, 64라운드를 돌린다. 각 라운드에서 Ch(선택 함수), Maj(다수결 함수), 두 종류의 회전 함수(Σ, σ), 메시지 스케줄 $W_i$, 라운드 상수 $K_i$가 쓰인다.

라운드가 끝나면 작업 변수를 원래 연쇄값에 워드 단위로 $2^{32}$ 모듈러 덧셈 해 되먹인다. XOR이 아니다.

$$h_i^{(j)} = \left(a^{(j)} + h_{i-1}^{(j)}\right) \bmod 2^{32}, \qquad j = 0, \ldots, 7$$

이 되먹임은 Davies-Meyer 구조의 변형이다. 되먹임이 없으면 64라운드가 가역 변환이라 거꾸로 돌릴 수 있는데, 되먹임이 그 가역성을 깬다.

다만 되먹임이 있다는 사실만으로 단방향성이 증명되지는 않는다. 단방향성은 라운드 함수 전체에 대한 가정이며, 이 구조가 주는 것은 「블록 암호가 안전하다면 압축 함수도 안전하다」는 조건부 결론이다.

Length Extension 취약점

MD 구조에는 한 가지 취약점이 있다. $H(m)$만 알면 $H(m \| \text{padding} \| m')$을 비밀 없이 계산할 수 있다. 마지막 블록의 출력 상태가 그대로 다음 입력 상태가 되기 때문이다.

이 때문에 MAC(메시지 인증 코드)을 만들 때 $H(\text{key} \| m)$ 형태로 직접 사용하면 안 된다. 대신 HMAC 을 사용한다.

$$\text{HMAC}(k, m) = H\bigl((k \oplus \text{opad}) \| H((k \oplus \text{ipad}) \| m)\bigr)$$

SHA-3(Keccak)는 스펀지 구조(Sponge Construction)를 사용해 이 취약점을 근본적으로 해소했다.

Birthday Paradox와 해시 길이

왜 충돌 저항성이 $2^n$이 아니라 $2^{n/2}$인가?

365일 중 생일이 같은 두 사람 을 찾는 50% 충돌 임계점은 23명이고, 이는 약 $1.18\sqrt{365}$에 해당한다. 반면 특정인 과 생일이 같은 사람을 찾으려면 253명이 필요하다.

해시에서도 마찬가지다. 특정 $h$와 충돌하는 $m$을 찾으려면 $2^n$번이 필요하지만, 임의의 충돌 쌍 $(m_1, m_2)$를 찾으려면 $\approx 2^{n/2}$번이면 된다.

확률 공식은 다음과 같다.

$$P(\text{충돌}) \approx 1 - e^{-k(k-1) / 2N}$$

이 근사가 서는 모형을 밝혀 두자. 해시 함수를 무작위 함수로 보아 서로 다른 $k$개의 입력이 $N$개의 출력 중 하나를 균등·독립으로 받는다고 둔다. 세는 것은 서로 다른 입력의 개수, 곧 질의 횟수 $k$다.

지수의 $k(k-1)/2$는 입력 쌍의 개수다. 흔히 $k^2/2N$으로 줄여 쓰는데, $k$가 클 때 두 값의 차이가 무시할 만해서다. $k$가 작을 때는 이 단순화가 확률을 부풀린다.

50% 확률로 충돌이 나는 시도 횟수는 $k \approx 1.18\sqrt{N}$이다. $n$비트 해시에서 $N = 2^n$이므로 $k \approx 2^{n/2}$이다.

따라서:

해시	크기	이론적 충돌 복잡도	실제 공격 복잡도	상태
MD5	128 bit	$2^{64}$	$2^{40}$ (Wang et al. 2004)	폐기 — 수 초 내 충돌 생성 가능
SHA-1	160 bit	$2^{80}$	$\approx 2^{63}$ (SHAttered 2017)	폐기 — 주요 CA·브라우저 거부
SHA-256	256 bit	$2^{128}$	알려진 실용적 공격 없음	현재 표준
SHA-512	512 bit	$2^{256}$	알려진 실용적 공격 없음	초장기 안전

양자 컴퓨터 환경에서는 두 성질을 따로 봐야 한다.

역상 저항성은 Grover 알고리즘으로 $2^n$에서 $2^{n/2}$로 줄어든다. 목표 안전성이 $b$비트라면 $n \ge 2b$가 필요하다. 128비트 목표에는 SHA-256이면 되고, 192비트 목표에는 SHA-384가 필요하다.

충돌 저항성은 사정이 다르다. 고전 생일 공격이 이미 $2^{n/2}$이고, 양자 알고리즘(BHT)이 내는 $2^{n/3}$은 그만큼의 저장 공간을 요구해 실제 이득이 크지 않다는 평가가 일반적이다. 그래서 충돌 쪽 권고는 고전 기준과 크게 다르지 않다.

「양자 때문에 SHA-384 이상」이라고 뭉뚱그리면 어느 성질을 몇 비트로 지키려는지가 사라진다. 목표 안전성 비트 수를 먼저 정하고 그에 맞춰 출력 길이를 고르는 것이 순서다.

MD5와 SHA-1이 폐기된 이유

이론적 취약점 발견으로 끝나지 않았다. 실제 공격이 현실화됐다.

MD5: 2004년 Wang 등이 $2^{40}$ 연산으로 충돌을 만들어냈다. 이후 가정용 PC로 수 초 내에 충돌 쌍을 생성할 수 있게 됐다. 2012년 Flame 악성코드는 MD5 충돌을 이용해 Microsoft 코드 서명 인증서를 위조했다.

SHA-1: 2005년 $2^{63}$ 이론 공격에 이어, 2017년 Google 연구팀이 동일한 SHA-1 해시값을 갖는 두 PDF 파일을 실제로 공개했다(SHAttered). 비용은 약 $45,000(2019년 GPU 기준). Chrome, Firefox, 모든 주요 CA는 2017년부터 SHA-1 인증서를 거부한다.

올바른 해시 함수 응용

해시 함수는 올바르게 사용해야 한다. 잘못된 사용이 취약점을 만든다.

패스워드 저장: SHA-256(password)를 그대로 저장하면 안 된다. 레인보우 테이블 공격과 사전 공격에 취약하다. 의도적으로 느리게 설계된 bcrypt, scrypt, Argon2 를 사용해야 한다. 이들은 연산 비용이 높아 대규모 병렬 공격을 어렵게 만든다.

메시지 인증(MAC): 위에서 언급했듯 $H(\text{key} \| m)$ 형태는 Length Extension 취약점이 있다. HMAC-SHA256 을 사용한다.

무결성 검사: 파일 다운로드 후 SHA-256 해시를 확인하는 것은 전송 오류나 우발적 변조를 감지하는 데 적합하다. 단, 해시값 자체가 변조되지 않았다는 전제가 필요하다 — 전자 서명이나 HTTPS로 해시값의 출처를 보증해야 한다.

전자 서명: 이전 글에서 다뤘듯, SHA-256(m)에 서명하면 서명 크기가 메시지 크기와 무관해진다. 여기서 필요한 성질은 이름을 나눠 불러야 한다.

• 충돌 저항성: $H(m_1) = H(m_2)$인 서로 다른 $m_1, m_2$를 찾기 어렵다. 서명이 문서에 묶이려면 이것이 필요하다. 둘을 찾을 수 있으면 $m_1$에 받은 서명이 $m_2$에도 그대로 통한다.
• 제2 역상 저항성: 주어진 $m_1$에 대해 같은 해시를 갖는 다른 $m_2$를 찾기 어렵다. 이미 서명된 문서를 바꿔치기하는 공격을 막는다.
• 역상 저항성: 해시값만 보고 원래 입력을 복원하기 어렵다. 서명의 문서 묶임과는 다른 성질이다.

세 성질은 서로 다르고, 서명이 기대는 것은 앞의 둘이다. 그리고 해시만으로는 부족하다. 해시값을 서명 함수에 넣는 인코딩도 안전해야 한다. 예컨대 RSA에서 해시를 그대로 거듭제곱하면 위조가 가능해, RSA-PSS 같은 표준 패딩을 쓴다.