본문으로 건너뛰기

11장. 암호학적 해시 함수

학습 목표

  • 암호학적 해시 함수의 응용을 요약한다.
  • 메시지 인증에 사용되는 해시 함수가 왜 보호되어야 하는지 설명한다.
  • Preimage resistant, Second preimage resistant, Collision resistant 속성의 차이를 이해한다.
  • 암호학적 해시 함수의 기본 구조를 개관한다.
  • CBC를 이용한 해시 함수 구성을 설명한다.
  • SHA-512의 동작을 이해한다.
  • 생일 역설과 생일 공격의 개요를 이해한다.

11.1 암호학적 해시 함수의 응용​

해시 함수 HH는 가변 길이 데이터 블록 MM을 받아 고정 길이 해시값 h=H(M)h = H(M)을 생성한다. MM의 어떤 비트가 변경되면 높은 확률로 hh도 변경된다.

암호학적 해시 함수란, (a) 사전 지정된 해시 결과에 매핑되는 데이터를 찾거나 (b) 같은 해시 결과를 내는 두 데이터를 찾는 것이 계산적으로 불가능한 알고리즘이다.

메시지 인증​

메시지의 무결성을 검증하는 메커니즘. 송신자가 H(M)H(M)을 계산하여 메시지와 함께 전송, 수신자가 재계산하여 비교한다. 해시값은 반드시 보호되어야 한다 — 그렇지 않으면 공격자가 메시지와 해시값을 함께 변조할 수 있다.

해시코드로 인증을 제공하는 네 가지 방식:

방식설명
(a) 대칭 암호화 (전체)E(K,  [M∥H(M)])E(K,\;[M \| H(M)]) — 기밀성 + 인증
(b) 대칭 암호화 (해시만)M∥E(K,  H(M))M \| E(K,\;H(M)) — 인증만 (기밀성 불필요 시)
(c) 비밀값 결합M∥H(M∥S)M \| H(M \| S) — 암호화 없이 인증 (공유 비밀값 SS 사용)
(d) 비밀값 + 암호화E(K,  [M∥H(M∥S)])E(K,\;[M \| H(M \| S)]) — 인증 + 기밀성
MAC (Message Authentication Code)

키 기반 해시 함수로, 비밀키 KK와 메시지 MM을 입력으로 받아 고정 길이 인증자(태그)를 생성한다. E(K,H(M))E(K, H(M))은 사실상 MAC의 한 형태이다. 실제로는 전용 MAC 알고리즘이 암호화 알고리즘보다 더 효율적이다. MAC은 12장에서 다룬다.

전자서명​

메시지의 해시값을 송신자의 개인키로 암호화하여 서명한다.

  • (a) E(PRa,  H(M))E(PR_a,\; H(M)) — 인증 + 서명
  • (b) E(K,  [M∥E(PRa,  H(M))])E(K,\; [M \| E(PR_a,\; H(M))]) — 인증 + 서명 + 기밀성 (일반적 기법)

기타 응용​

  • 일방향 비밀번호 파일: 비밀번호의 해시만 저장 → 원문 비노출
  • 침입 탐지 / 바이러스 탐지: 파일의 H(F)H(F)를 안전하게 저장, 변조 시 감지
  • PRF/PRNG: 해시 기반 의사난수 함수 구성 (대칭키 생성 등)

11.2 두 가지 단순 해시 함수​

비트별 XOR (종단 중복 검사)​

Ci=bi1⊕bi2⊕⋯⊕bimC_i = b_{i1} \oplus b_{i2} \oplus \cdots \oplus b_{im}

nn비트 해시코드의 각 비트 위치에 대한 단순 패리티. 랜덤 데이터에는 효과적이나 (2−n2^{-n} 확률로 오류 미탐지), 규칙적 데이터(예: ASCII의 최상위 비트가 항상 0)에서는 효과가 감소한다.

회전 XOR (RXOR)​

각 블록 처리 후 해시값을 1비트 순환 시프트(rotate) 한 뒤 XOR. 입력을 더 잘 "랜덤화"하지만, 암호화된 해시코드가 평문 메시지와 함께 전송될 때 — 대체 메시지를 쉽게 생성 가능하므로 보안 용도로는 부적합하다.

CBC + XOR 방식의 취약점

메시지 블록 X1,X2,…,XNX_1, X_2, \dots, X_N의 XOR을 해시코드로 사용하고 CBC 모드로 전체를 암호화하면, CBC의 정의에 의해 해시코드는 다음과 같이 분해된다:

XN+1=[IV⊕D(K,Y1)]⊕[Y1⊕D(K,Y2)]⊕⋯⊕[YN−1⊕D(K,YN)]X_{N+1} = [IV \oplus D(K, Y_1)] \oplus [Y_1 \oplus D(K, Y_2)] \oplus \cdots \oplus [Y_{N-1} \oplus D(K, Y_N)]

각 항을 어떤 순서로든 XOR할 수 있으므로, 암호문 블록의 순서를 바꿔도 해시코드가 변하지 않는다.

11.3 보안 요구사항​

용어 정의​

  • 원상 (Preimage): h=H(x)h = H(x)일 때 xx는 hh의 원상. HH는 다대일 함수이므로 하나의 해시값에 여러 원상이 존재한다.
  • 충돌 (Collision): x≠yx \neq y이면서 H(x)=H(y)H(x) = H(y).

해시코드가 nn비트이고 입력이 bb비트(b>nb > n)이면, 각 해시값은 평균 2b−n2^{b-n}개의 원상을 가진다.

보안 요구사항​

요구사항설명
가변 입력 크기임의 크기 데이터에 적용 가능
고정 출력 크기고정 길이 출력 생성
효율성H(x)H(x) 계산이 쉬움 (하드웨어·소프트웨어 모두 실용적)
Preimage resistant (일방향성)해시값 hh가 주어졌을 때 H(y)=hH(y) = h인 yy를 찾기 불가능
Second preimage resistant블록 xx가 주어졌을 때 H(y)=H(x)H(y) = H(x)인 y≠xy \neq x를 찾기 불가능
Collision resistantH(x)=H(y)H(x) = H(y)인 임의의 쌍 (x,y)(x, y), x≠yx \neq y를 찾기 불가능
의사난수성출력이 표준 의사난수 테스트를 통과

처음 다섯 속성을 만족하면 약한 해시 함수(weak hash function), 여섯 번째까지 만족하면 **강한 해시 함수(strong hash function)**라 한다.

저항 속성 간의 관계

Collision resistant → Second preimage resistant (역은 불성립). Collision resistant와 Preimage resistant는 서로 독립적이다.

응용별 요구 속성​

응용PreimageSecond PreimageCollision
해시 + 전자서명YesYesYes*
침입 탐지 / 바이러스 탐지Yes
일방향 비밀번호 파일Yes
MACYesYesYes*

* 공격자가 선택 메시지 공격을 수행할 수 있는 경우

무차별 대입 공격​

mm비트 해시코드에 대한 무차별 공격 비용:

공격 유형비용
Preimage / Second preimage2m2^m
Collision2m/22^{m/2} (생일 역설)

생일 역설과 생일 공격​

00부터 N−1N-1까지의 균등 분포에서 랜덤으로 값을 뽑을 때, N\sqrt{N}개를 뽑으면 반복 원소(충돌)가 나타날 확률이 0.50.5를 초과한다. mm비트 해시의 경우 2m=2m/2\sqrt{2^m} = 2^{m/2} 시도.

Yuval의 생일 공격 전략:

  1. 송신자 A가 정당한 메시지 xx에 서명할 준비를 한다.
  2. 공격자가 xx의 2m/22^{m/2}개 변형을 생성하고 해시값을 저장한다.
  3. 공격자가 위조 메시지 yy를 준비하고, yy의 변형 y′y'를 생성하며 H(y′)=H(x′)H(y') = H(x')인 쌍을 찾을 때까지 반복한다.
  4. 합법적 변형 x′x'을 A에게 제시하여 서명을 받고, 그 서명을 위조 변형 y′y'에 부착한다.
128비트 해시의 취약성

128비트 해시에 대한 충돌 탐색 비용은 2642^{64}에 불과하다. 1천만 달러짜리 전용 머신으로 MD5(128비트) 충돌을 24일만에 발견할 수 있다는 설계가 제시되었다. 따라서 128비트는 불충분하고, 160비트도 현재 의심되며, 256비트 이상이 권장된다.

암호분석과 반복 해시 함수 구조​

대부분의 해시 함수는 반복(iterated) 해시 함수 구조를 사용한다 (Merkle-Damgård):

CV0=IV,CVi=f(CVi−1,  Yi−1),H(M)=CVLCV_0 = IV, \quad CV_i = f(CV_{i-1},\; Y_{i-1}), \quad H(M) = CV_L

메시지 MM을 LL개의 bb비트 블록 Y0,Y1,…,YL−1Y_0, Y_1, \dots, Y_{L-1}으로 분할하고, 압축 함수 ff를 반복 적용한다.

Merkle-Damgård 정리

길이 필드가 입력에 포함되고, 압축 함수 ff가 충돌 저항이면, 결과적인 반복 해시 함수도 충돌 저항이다. 따라서 안전한 해시 함수 설계 문제는 고정 크기 입력에 대한 충돌 저항 압축 함수 설계 문제로 환원된다.

11.4 CBC 기반 해시 함수​

비밀키 없이 CBC 기법을 사용하여 해시 함수를 구성하는 방법:

H0=IV,Hi=E(Mi,  Hi−1),G=HNH_0 = IV, \quad H_i = E(M_i,\; H_{i-1}), \quad G = H_N

DES를 사용하면 64비트 해시코드만 생성 → 생일 공격에 취약. 더구나 단일 메시지·서명 쌍만으로도 meet-in-the-middle 공격이 가능하다:

  1. 원하는 메시지 Q1,…,QN−2Q_1, \dots, Q_{N-2}를 구성하고 HN−2H_{N-2}까지 계산
  2. 2m/22^{m/2}개의 랜덤 블록 XX에 대해 E(X,HN−2)E(X, H_{N-2})를 계산
  3. 2m/22^{m/2}개의 랜덤 블록 YY에 대해 D(Y,G)D(Y, G)를 계산
  4. E(X,HN−2)=D(Y,G)E(X, H_{N-2}) = D(Y, G)인 쌍을 찾음 (생일 역설)
  5. Q1,…,QN−2,X,YQ_1, \dots, Q_{N-2}, X, Y가 원본과 동일한 해시코드 GG를 가짐

Davies-Price 변형 Hi=E(Mi,Hi−1)⊕Hi−1H_i = E(M_i, H_{i-1}) \oplus H_{i-1}이나 Meyer 변형 Hi=E(Hi−1,Mi)⊕MiH_i = E(H_{i-1}, M_i) \oplus M_i 등이 제안되었으나, 모두 다양한 공격에 취약한 것으로 밝혀졌다.

11.5 SHA (Secure Hash Algorithm)​

SHA 패밀리​

NIST가 개발. 거의 모든 다른 표준화된 해시 함수가 심각한 약점을 가진 것으로 밝혀지면서, SHA가 사실상 유일한 표준이 되었다.

알고리즘메시지 크기블록 크기워드 크기다이제스트 크기
SHA-1<264< 2^{64}51232160
SHA-224<264< 2^{64}51232224
SHA-256<264< 2^{64}51232256
SHA-384<2128< 2^{128}102464384
SHA-512<2128< 2^{128}102464512
SHA-512/224<2128< 2^{128}102464224
SHA-512/256<2128< 2^{128}102464256

(모든 크기: 비트 단위)

SHA-1은 2692^{69} 연산으로 충돌을 찾을 수 있음이 발표 (이론적 한계 2802^{80}보다 훨씬 적음) → 단계적 폐지, SHA-2 사용 권장.

SHA-512 처리 과정​

Step 1 — 패딩: 메시지 길이 ≡896(mod1024)\equiv 896 \pmod{1024}가 되도록 패딩. 항상 추가 (이미 원하는 길이여도). 1비트 + 필요한 수의 0비트로 구성.

Step 2 — 길이 추가: 128비트 블록으로 원본 메시지의 비트 길이를 추가.

Step 3 — 해시 버퍼 초기화: 8개의 64비트 레지스터 a∼ha \sim h를 처음 8개 소수의 제곱근의 소수 부분에서 추출한 상수로 초기화.

Step 4 — 80라운드 처리: 각 1024비트 블록 MiM_i에 대해:

H0=IV,Hi=SUM64(Hi−1,  abcdefghi),MD=HNH_0 = IV, \quad H_i = \text{SUM}_{64}(H_{i-1},\; abcdefgh_i), \quad MD = H_N

여기서 SUM64\text{SUM}_{64}는 8개 워드 각각에 대한  mod 264\bmod 2^{64} 덧셈.

SHA-512 라운드 함수​

각 라운드 tt (0≤t≤790 \le t \le 79)에서:

T1=h+Ch(e,f,g)+Σ1512(e)+Wt+KtT_1 = h + Ch(e, f, g) + \Sigma_1^{512}(e) + W_t + K_t

T2=Σ0512(a)+Maj(a,b,c)T_2 = \Sigma_0^{512}(a) + Maj(a, b, c)

그 후 레지스터를 이동: h←gh \leftarrow g, g←fg \leftarrow f, f←ef \leftarrow e, e←d+T1e \leftarrow d + T_1, d←cd \leftarrow c, c←bc \leftarrow b, b←ab \leftarrow a, a←T1+T2a \leftarrow T_1 + T_2.

여기서:

Ch(e,f,g)=(e∧f)⊕(¬e∧g)(조건부: if e then f else g)Ch(e, f, g) = (e \wedge f) \oplus (\neg e \wedge g) \quad\text{(조건부: if } e \text{ then } f \text{ else } g\text{)}

Maj(a,b,c)=(a∧b)⊕(a∧c)⊕(b∧c)(다수결)Maj(a, b, c) = (a \wedge b) \oplus (a \wedge c) \oplus (b \wedge c) \quad\text{(다수결)}

Σ0512(a)=ROTR28(a)⊕ROTR34(a)⊕ROTR39(a)\Sigma_0^{512}(a) = ROTR^{28}(a) \oplus ROTR^{34}(a) \oplus ROTR^{39}(a)

Σ1512(e)=ROTR14(e)⊕ROTR18(e)⊕ROTR41(e)\Sigma_1^{512}(e) = ROTR^{14}(e) \oplus ROTR^{18}(e) \oplus ROTR^{41}(e)

메시지 스케줄​

처음 16개 워드 W0∼W15W_0 \sim W_{15}는 현재 메시지 블록에서 직접 취한다. 나머지는:

Wt=σ1512(Wt−2)+Wt−7+σ0512(Wt−15)+Wt−16W_t = \sigma_1^{512}(W_{t-2}) + W_{t-7} + \sigma_0^{512}(W_{t-15}) + W_{t-16}

σ0512(x)=ROTR1(x)⊕ROTR8(x)⊕SHR7(x)\sigma_0^{512}(x) = ROTR^{1}(x) \oplus ROTR^{8}(x) \oplus SHR^{7}(x)

σ1512(x)=ROTR19(x)⊕ROTR61(x)⊕SHR6(x)\sigma_1^{512}(x) = ROTR^{19}(x) \oplus ROTR^{61}(x) \oplus SHR^{6}(x)

SHA-512의 특성

80라운드 처리 후, 해시코드의 모든 비트는 입력의 모든 비트의 함수이다. 충돌 발견 난이도는 22562^{256}, 원상 발견 난이도는 25122^{512}으로 추정된다.

예시: "abc"의 SHA-512 해시​

24비트 입력 01100001 01100010 01100011을 872비트 패딩 + 128비트 길이 필드로 1024비트 블록을 구성한 뒤 80라운드를 처리하면:

ddaf35a193617aba cc417349ae204131 12e6fa4e89a97ea2 0a9eeee64b55d39a
2192992a274fc1a8 36ba3c23a3feebbd 454d4423643ce80e 2a9ac94fa54ca49f

"abc"를 "cbc"로 1비트 변경하면 해시의 253비트가 달라진다 (전체 512비트의 약 절반) — 우수한 눈사태 효과(avalanche effect).

11.6 SHA-3​

배경​

SHA-1은 MD4/SHA-0과 구조가 유사하여 취약점이 우려되었고, SHA-2도 같은 구조·수학 연산을 공유한다. NIST는 2007년 SHA-3 공모를 시작하여 2012년 Keccak 알고리즘을 SHA-3로 선정했다 (FIPS 202, 2015).

스펀지 구조 (Sponge Construction)​

SHA-3의 핵심 구조. 세 가지 파라미터로 정의된다:

  • ff — 각 입력 블록을 처리하는 내부 함수
  • rr — 입력 블록 크기 (비트율, bitrate)
  • pad\text{pad} — 패딩 알고리즘

상태 변수 ss는 b=r+cb = r + c 비트로 구성되며 (cc: 용량, capacity), 0으로 초기화된다.

흡수 단계 (Absorbing phase):

각 반복에서 입력 블록 PiP_i를 bb비트로 확장 (Pi∥0cP_i \| 0^c), 상태 ss와 XOR한 뒤, 내부 함수 ff를 적용한다.

s←f(s⊕(Pi∥0c))s \leftarrow f\bigl(s \oplus (P_i \| 0^c)\bigr)

추출 단계 (Squeezing phase):

해시 길이 ℓ≤r\ell \le r이면 흡수 단계 완료 후 ss의 상위 ℓ\ell비트를 반환하고 종료. ℓ>r\ell > r이면 ff를 추가로 적용하며 rr비트씩 추출하여 연결한다.

보안 강도

스펀지 구조의 보안은 **용량 cc**에 의존한다. 충돌 저항은 2c/22^{c/2}, 원상 저항은 min⁡(2c/2,2ℓ)\min(2^{c/2}, 2^\ell)이다. 구현 시 비트율 rr을 늘려 속도를 높이거나 용량 cc를 늘려 보안을 강화할 수 있다.

SHA-3 파라미터​

다이제스트 크기비트율 rr용량 cc라운드 수충돌 저항원상 저항
22411524482421122^{112}22242^{224}
25610885122421282^{128}22562^{256}
3848327682421922^{192}23842^{384}
51257610242422562^{256}25122^{512}

기본값: r+c=1600r + c = 1600비트 (Keccak-f[1600]).

SHA-3 반복 함수 ff (Keccak-f)​

1600비트 상태를 5×5×645 \times 5 \times 64의 3차원 배열 a[x,y,z]a[x, y, z]로 취급한다. 64비트 단위를 레인(lane) L[x,y]L[x, y]라 한다.

s[64(5y+x)+z]=a[x,y,z]s[64(5y + x) + z] = a[x, y, z]

24라운드를 수행하며, 각 라운드는 다섯 단계의 합성으로 구성된다: R=ι∘χ∘π∘ρ∘θR = \iota \circ \chi \circ \pi \circ \rho \circ \theta

단계유형설명
θ\theta치환각 비트를 자신 + 인접 두 열의 XOR로 갱신 → 확산
ρ\rho순열각 레인 내에서 서로 다른 양만큼 순환 비트 시프트
π\pi순열5×55 \times 5 행렬 내에서 레인의 위치 이동
χ\chi치환각 비트를 같은 행의 다음 두 레인 비트의 함수로 갱신 → 유일한 비선형 단계
ι\iota치환L[0,0]L[0, 0]에 라운드 상수 RC[ir]RC[i_r]을 XOR → 대칭성 파괴

θ\theta 단계​

L[x,y]←L[x,y]⊕C[x−1]⊕ROT(C[x+1],  1)L[x, y] \leftarrow L[x, y] \oplus C[x-1] \oplus ROT(C[x+1],\; 1)

여기서 C[x]=L[x,0]⊕L[x,1]⊕L[x,2]⊕L[x,3]⊕L[x,4]C[x] = L[x, 0] \oplus L[x, 1] \oplus L[x, 2] \oplus L[x, 3] \oplus L[x, 4]. 각 비트의 갱신값은 11개 비트에 의존하여 우수한 확산을 제공한다.

ρ\rho 단계​

L[0,0]L[0, 0]은 변경 없이, 나머지 24개 레인은 각각 서로 다른 양만큼 순환 시프트된다. 시프트량은 (t+1)(t+2)2 mod 64\frac{(t+1)(t+2)}{2} \bmod 64로 결정된다.

π\pi 단계​

L[x,y]←L[y,  (2x+3y) mod 5]L[x, y] \leftarrow L[y,\; (2x + 3y) \bmod 5]

같은 대각선에 있던 레인들이 같은 행으로 모이는 순열이다.

χ\chi 단계​

a[x,y,z]←a[x,y,z]⊕(¬a[x+1,y,z]∧a[x+2,y,z])a[x, y, z] \leftarrow a[x, y, z] \oplus (\neg a[x+1, y, z] \wedge a[x+2, y, z])

이것이 유일한 비선형 매핑이다. 이 단계 없이는 라운드 함수가 선형이 된다.

ι\iota 단계​

L[0,0]←L[0,0]⊕RC[ir](0≤ir≤23)L[0, 0] \leftarrow L[0, 0] \oplus RC[i_r] \quad (0 \le i_r \le 23)

24개의 64비트 라운드 상수가 사용되며, 해밍 무게는 1~6이다. θ\theta와 χ\chi를 통해 L[0,0]L[0, 0]의 변화가 1라운드 만에 모든 레인으로 확산된다.

SHA-3의 설계 특징

모든 연산이 비트 단위 부울 연산(XOR, AND, NOT)과 순환 시프트에 한정된다. 테이블 참조, 산술 연산, 데이터 의존적 시프트가 없으므로 하드웨어·소프트웨어 양쪽에서 효율적으로 구현 가능하며, 트랩도어를 숨길 수 없다.

주요 용어​

한글영문
흡수 단계absorbing phase
생일 공격birthday attack
생일 역설birthday paradox
비트율bitrate
용량capacity
충돌 저항collision resistant
압축 함수compression function
암호학적 해시 함수cryptographic hash function
해시코드 / 해시값hash code / hash value
키 기반 해시 함수keyed hash function
레인lane
메시지 다이제스트message digest
원상 저항preimage resistant
제2원상 저항second preimage resistant
스펀지 구조sponge construction
추출 단계squeezing phase
SHA-1 / SHA-2 / SHA-3SHA-1 / SHA-2 / SHA-3