컴퓨터공학 300 주제 시리즈의 245번째 글이다. 전체 지도는 여기.

한 줄 요약

암호학적 해시는 누구나 계산할 수 있는 데이터의 지문이고, MAC 은 비밀 키가 있어야만 만들 수 있는 봉인이다. 무결성만 원하면 해시, 진정성까지 원하면 MAC(대개 HMAC)을 쓴다.

왜 필요한가

파일이 전송 중 깨졌는지, 다운로드한 이미지가 원본과 같은지, 이 API 요청이 정말 우리 서버가 발급한 토큰으로 서명됐는지. 모두 “데이터가 바뀌지 않았다” 를 확인하는 문제다. 그런데 해시와 MAC 을 구분하지 못해 생기는 사고가 많다. sha256(secret + message) 를 서명이라고 쓰거나, 해시 비교를 == 로 해서 타이밍 정보가 새는 식이다.

해시는 또 비밀번호 저장, 전자서명, 블록체인, git 의 객체 주소, 중복 제거 등 보안 밖에서도 기반 부품이다. 무엇을 보장하고 무엇을 보장하지 않는지 정확히 알아야 한다.

핵심 개념

암호학적 해시의 세 가지 성질

임의 길이 입력을 고정 길이 출력(다이제스트)으로 바꾸는 함수 H 가 다음을 만족해야 한다.

성질 의미 일반적 공격 비용(n비트 출력)
역상 저항성 h 만 보고 H(x)=h 인 x 를 못 찾는다 약 2^n
제2역상 저항성 x 가 주어졌을 때 H(x’)=H(x) 인 다른 x’ 를 못 찾는다 약 2^n
충돌 저항성 H(x)=H(x’) 인 아무 쌍이나 못 찾는다 약 2^(n/2) (생일 공격)

충돌 저항성의 비용이 절반 지수인 이유가 생일 역설이다. 23명만 모여도 생일이 겹칠 확률이 절반을 넘듯, 출력 공간의 제곱근 정도만 시도하면 아무 두 입력이 겹칠 가능성이 커진다. 그래서 256비트 해시의 충돌 안전성은 128비트 수준이다.

현재 쓰는 해시

알고리즘 규격 출력 상태
MD5 RFC 1321 128 충돌이 쉽게 만들어진다. 보안 용도 금지
SHA-1 FIPS 180-4 160 실제 충돌이 공개됐다. 새 용도에 금지
SHA-256/384/512 FIPS 180-4 256/384/512 표준 선택
SHA3-256 등 FIPS 202 224~512 다른 구조(스펀지)의 대안
BLAKE2/BLAKE3 RFC 7693 (BLAKE2) 가변 빠른 대안

해시만으로는 진정성이 없다

해시는 키가 없다. 공격자가 데이터를 바꾸면 해시도 다시 계산해 붙이면 그만이다. 해시가 보장하는 건 “믿을 수 있는 경로로 받은 해시값과 데이터가 일치한다” 뿐이다. 해시값 자체를 공격자가 바꿀 수 있는 상황이면 무결성도 못 지킨다.

MAC 과 HMAC

MAC(Message Authentication Code)은 비밀 키 K 와 메시지 m 으로 태그 t 를 만든다. 키를 모르면 유효한 태그를 위조할 수 없다. 그래서 무결성과 진정성(이 키를 가진 쪽이 만들었다)을 동시에 준다.

가장 흔한 구성이 RFC 2104 의 HMAC 이다.

HMAC(K, m) = H( (K ⊕ opad) || H( (K ⊕ ipad) || m ) )

왜 그냥 H(K || m) 이면 안 될까. SHA-256 같은 Merkle–Damgård 구조 해시는 길이 확장 공격에 약하다. H(K‖m) 값만 알면 K 를 몰라도 H(K‖m‖padding‖추가데이터) 를 계산할 수 있다. 공격자가 amount=100 뒤에 &amount=900 을 붙이고 유효한 태그를 만드는 셈이다. HMAC 의 이중 구조는 이를 막는다. (SHA-3 는 구조상 길이 확장에 강하지만, 그래도 표준 MAC 구성을 쓰는 게 원칙이다.)

MAC 은 부인 방지를 주지 않는다

MAC 키는 양쪽이 공유한다. 수신자도 같은 태그를 만들 수 있으므로 제3자에게 “송신자가 만들었다” 를 증명하지 못한다. 그게 필요하면 다음 글의 전자서명을 쓴다.

비교는 상수 시간으로

태그를 == 로 비교하면 첫 번째로 다른 바이트에서 바로 끝나므로, 응답 시간 차이로 맞는 바이트 수가 샐 수 있다. 파이썬은 hmac.compare_digest() 를 제공한다.

직접 해 보기

표준 라이브러리만으로 눈사태 효과, 생일 공격, HMAC 검증을 확인한다.

import hashlib, hmac, secrets

# 1) 눈사태 효과
a = hashlib.sha256(b"transfer 100").digest()
b = hashlib.sha256(b"transfer 900").digest()
diff = sum(bin(x ^ y).count("1") for x, y in zip(a, b))
print("SHA-256 출력 256비트 중 바뀐 비트:", diff)

# 2) 생일 역설: 24비트로 자르면 충돌이 2^12 근처 규모에서 나온다
seen, i = {}, 0
while True:
    h = hashlib.sha256(str(i).encode()).digest()[:3]
    if h in seen:
        print(f"24비트 충돌: 입력 {seen[h]} 와 {i} (시도 {i+1}회, 2^12={2**12})")
        break
    seen[h] = i; i += 1

# 3) HMAC
key = secrets.token_bytes(32)
msg = b'{"user":42,"role":"viewer"}'
tag = hmac.new(key, msg, hashlib.sha256).hexdigest()

def verify(m, t):
    expected = hmac.new(key, m, hashlib.sha256).hexdigest()
    return hmac.compare_digest(expected, t)   # 상수 시간 비교

print("원본 검증:", verify(msg, tag))
print("변조 검증:", verify(b'{"user":42,"role":"admin"}', tag))

실행 결과(Python 3.12):

SHA-256 출력 256비트 중 바뀐 비트: 130
24비트 충돌: 입력 4163 와 8864 (시도 8865회, 2^12=4096)
원본 검증: True
변조 검증: False

256비트 중 130비트, 거의 정확히 절반이 바뀌었다. 24비트(약 1,677만 가지) 공간에서 충돌은 9천 번도 안 돼 나왔다. 2^24 번이 아니라 2^12 규모다. 실제 256비트 해시라면 같은 논리로 2^128 규모가 필요해 현실적으로 불가능하다.

현업에서는

  • 웹훅 서명 검증: 결제·Git 호스팅 서비스는 웹훅 본문에 HMAC-SHA256 서명 헤더를 붙여 보내는 경우가 많다. 수신 측은 원본 바이트 그대로 HMAC 을 계산해야 한다. JSON 을 파싱했다가 다시 직렬화하면 공백·키 순서가 바뀌어 검증이 깨진다. 비교는 상수 시간으로 한다.
  • JWT 의 HS256: HMAC-SHA256 으로 서명한 토큰이다. 키가 짧거나 추측 가능하면 오프라인 무차별 대입으로 키가 깨진다. 충분히 긴 무작위 키를 쓴다.
  • 컨테이너 이미지 다이제스트: image@sha256:... 로 참조하면 태그가 바뀌어도 같은 내용이 보장된다. 다만 그 다이제스트를 누가 정했는지(진정성)는 별개 문제라 서명(cosign 등)과 함께 쓴다.
  • 비밀번호에 SHA-256 금지: 빠른 해시는 비밀번호 저장에 부적합하다. 빠를수록 공격자도 빠르다. 별도 글에서 다룬다.

확인 문제

  1. 충돌 저항성의 일반 공격 비용이 2^n 이 아니라 2^(n/2) 인 이유는?
  2. 다운로드 파일 옆에 같은 서버에서 제공한 SHA-256 값이 있다. 이것만으로 막을 수 없는 공격은?
  3. sha256(secret + message) 를 MAC 으로 쓰면 어떤 공격에 노출되는가?
  4. HMAC 으로 부인 방지가 안 되는 이유는?

풀이

  1. 생일 역설. 임의의 두 입력이 겹치기만 하면 되므로 출력 공간의 제곱근 정도 시도로 충돌 확률이 크게 오른다.
  2. 서버를 장악한 공격자가 파일과 해시를 함께 바꾸는 공격. 해시값이 신뢰 경로로 오지 않으면 무의미하다.
  3. 길이 확장 공격. 키를 몰라도 메시지 뒤에 데이터를 덧붙인 유효 태그를 만들 수 있다.
  4. 키를 송수신자가 공유하므로 수신자도 같은 태그를 만들 수 있다. 제3자에게 누가 만들었는지 증명하지 못한다.

더 읽을거리 (References)