Step 234. 해시 공격: 길이 확장, 충돌 개념 — 해시를 "서명"으로 쓰면 생기는 일

Level 3 — CTF 실전과 공격 스킬 심화 | 난이도 ★★★☆☆ | 예상 소요 시간 4시간

전제: Step 227(암호 수학 기초)의 mod 감각, Step 233(AES)까지의 대칭키 흐름. 오늘은 파이썬 표준 라이브러리 hashlib만 씁니다.

⚠️ 이 챕터의 실습은 내 랩·합법 플랫폼 전용입니다. 허가 없는 시스템에 적용하면 범죄입니다.

준비물: 파이썬 3(실측: 3.12.14). 외부 도구 설치 없이 표준 라이브러리만으로 진행합니다.
주의: 오늘 만드는 "토이 해시"는 구조 이해용 장난감입니다. 실제 해시를 흉내 낼 뿐 실제 해시가 아닙니다.

해시는 지문입니다 — 입력이 1비트만 달라도 출력이 통째로 바뀌고, 되돌릴 수 없습니다. 그런데 이 안전한 도구를 잘못 조립하면 공격이 됩니다. 대표적인 것이 길이 확장 공격(length extension attack): H(secret + message)를 "서명"처럼 쓰는 서버에서, 비밀키를 모른 채 메시지를 이어 붙인 새 서명을 만들어 내는 공격입니다. 오늘은 이 공격을 축소 모형으로 직접 성공시키고, MD5·SHA1이 왜 폐기됐는지(충돌), 왜 HMAC은 안전한지까지 정리합니다.

1. 학습 목표

이 챕터를 끝내면 다음을 할 수 있습니다:

머클-담고르(Merkle-Damgård) 구조의 해시가 "상태를 이어받는다"는 것을 설명한다
길이 확장 공격의 조건과 절차를 축소 모형으로 재현한다
hashlib으로 눈사태 효과(1비트 차이 → 출력 전면 변화)를 실측한다
충돌 저항성이 깨진 MD5·SHA1의 운명과 SHA-256의 위치를 정리한다
HMAC이 길이 확장에 안전한 구조적 이유를 설명한다

2. 배경 지식 — 오늘의 도구와 개념

오늘의 도구 한눈에 보기

구분	내용
언어·환경	파이썬 3 (실측: 3.12.14) — 표준 라이브러리 `hashlib`만, 설치 없음
오늘의 명령어	`hashlib.sha256()`, `.md5()`, `.sha1()`, `.hexdigest()` + 직접 짜는 토이 해시
필요한 개념	머클-담고르 구조, 패딩, 길이 확장 공격, 충돌 저항성, HMAC
오늘의 산출물	눈사태 효과 출력 + 길이 확장 위조 성공 출력(토이 해시) + 방어 정리 노트

2-1. 해시가 약속하는 것 — 세 가지 성질

암호학적 해시 함수는 세 가지를 약속합니다. ① 역상 저항성: 해시값에서 입력을 복원할 수 없다. ② 제2 역상 저항성: 입력 하나가 주어졌을 때 같은 해시를 가진 다른 입력을 찾기 어렵다. ③ 충돌 저항성: 같은 해시를 가진 두 입력을 찾는 것 자체가 어렵다.

눈사태 효과(avalanche effect)는 이 약속들의 증상입니다 — 입력이 1비트만 달라도 출력의 절반 정도의 비트가 무작위로 뒤집힙니다. 오늘 실측으로 확인합니다.

2-2. 머클-담고르 구조 — 상태를 이어받는 해시

MD5, SHA-1, SHA-2 계열(SHA-256 포함)은 전부 머클-담고르 구조입니다. 입력을 고정 크기 블록으로 쪼개고, 각 블록을 "내부 상태"에 차례로 압축합니다. 마지막 블록까지 처리한 내부 상태가 곧 해시 출력입니다.

여기가 핵심입니다 — 해시 출력은 내부 상태의 그대로 공개입니다. 즉 H(X)를 아는 사람은 "X를 다 처리한 직후의 내부 상태"를 손에 쥔 셈이고, 그 상태에서 계산을 이어갈 수 있습니다. 이것이 길이 확장 공격의 전부입니다.

2-3. 길이 확장 공격 — 서명이 아닌데 서명인 척

어떤 서버가 서명 = H(secret + 메시지)로 요청을 인증한다고 합시다. 공격자는 secret을 모릅니다. 하지만 원본 메시지와 서명을 알고, secret의 길이만 맞히면(보통 브루트포스로 추측) 이렇게 위조합니다:

원본: H(secret || msg) = sig
공격: sig를 "내부 상태"로 이어받아, 패딩 뒤에 || suffix 를 추가로 압축
결과: H(secret || msg || padding || suffix) 를 secret 없이 계산 성공

서버는 msg + padding + suffix를 받아 자기 방식대로 H(secret + 그것)을 계산하면 — 공격자의 위조값과 정확히 일치합니다. 메시지에 &role=admin을 붙이는 데 비밀키가 필요 없는 것입니다. 오늘 이걸 실제로 돌립니다.

2-4. 충돌과 HMAC — 왜 MD5는 폐기됐나

충돌(collision)은 서로 다른 두 입력이 같은 해시를 가지는 사건입니다. 이상적으로는 256비트 해시에서 2¹²⁸ 번 시도해야 찾을 수 있는데, MD5는 구조적 약점이 발견되어 사실상 실용적인 시간에 충돌 쌍을 만들 수 있게 됐고(2004년 이후), SHA-1도 2017년 Google이 실제 충돌 파일 쌍(SHAttered)을 공개하며 사망 선고를 받았습니다.

길이 확장에 대한 답은 HMAC입니다 — H(k⊕opad || H(k⊕ipad || m)). 내부 해시의 결과를 다시 한 번 해시로 감싸므로, 출력이 "이어갈 수 있는 내부 상태"가 아닙니다. SHA-3(Keccak)도 구조가 달라(스펀지 구조) 길이 확장이 통하지 않습니다.

3. 따라 하기

이 챕터의 모든 출력은 2026-09-09 파이썬 3.12.14 실측입니다.

3-1. 눈사태 효과 — 1비트 차이의 결과

import hashlib

a, b = "hello", "hellp"   # 마지막 바이트 'o' -> 'p' (1비트 차이)
ha = hashlib.sha256(a.encode()).hexdigest()
hb = hashlib.sha256(b.encode()).hexdigest()
print("SHA256(hello) =", ha)
print("SHA256(hellp) =", hb)
diff = sum(1 for x, y in zip(ha, hb) if x != y)
print("16진수 자리 중 다른 자리:", diff, "/ 64")

SHA256(hello) = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
SHA256(hellp) = fdd7585e08c4e2afd71dcabdb4636c89d557a3f42db9e2040c8bbd1708aa4ce7
16진수 자리 중 다른 자리: 63 / 64

출력 읽는 법: 1비트 차이로 64자리 중 63자리가 바뀌었습니다. 두 해시 사이에 어떤 상관도 없습니다 — "입력이 비슷하면 출력도 비슷하다"가 성립하지 않는다는 것이 해시의 생명입니다.

길이와 무관하게 출력 길이는 항상 같습니다:

print("SHA256(빈 문자열) =", hashlib.sha256(b"").hexdigest())
print("SHA256(1MB)      =", hashlib.sha256(b"A" * 1000000).hexdigest())

SHA256(빈 문자열) = e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
SHA256(1MB)      = e23c0cda5bcdecddec446b54439995c7260c8cdcf2953eec9f5cdb6948e5898d

3-2. 토이 머클-담고르 해시 만들기

SHA-256의 내부는 복잡하니, 구조만 축소한 8비트 장난감을 만듭니다. 상태 h를 이어받아 바이트마다 h = (h*31 + b) % 256으로 압축하고, 끝에 패딩(0x80, 0x00들, 길이 1바이트)을 붙입니다.

class ToyMD:
    def __init__(self, h=0):
        self.h = h
    def compress(self, block_byte):
        self.h = (self.h * 31 + block_byte) % 256
    @staticmethod
    def padding_for(length):
        pad = bytearray([0x80])
        while (length + len(pad) + 1) % 4 != 0:
            pad.append(0x00)
        pad.append(length % 256)
        return bytes(pad)
    @classmethod
    def pad(cls, msg):
        return msg + cls.padding_for(len(msg))
    def digest(self, msg):
        for b in self.pad(msg):
            self.compress(b)
        return self.h

secret = b"s3cr3t!"
msg = b"id=guest"
server_sig = ToyMD().digest(secret + msg)
print("서버가 계산한 H(secret + msg) =", server_sig)

서버가 계산한 H(secret + msg) = 168

읽는 법: compress 한 번이 실제 해시의 "압축 함수" 한 번에 해당합니다. 복잡도만 다를 뿐, "상태를 이어받아 블록 단위로 처리하고 최종 상태를 출력"하는 구조는 SHA-256과 같습니다.

3-3. 길이 확장 공격 실행

이제 공격자가 됩니다. secret은 모르지만 server_sig = 168과 secret의 길이(7바이트)를 압니다.

key_len = 7                      # secret 길이 (실전에선 브루트포스로 추측)
pad1 = ToyMD.padding_for(key_len + len(msg))
print("패딩 바이트:", pad1.hex())

suffix = b"&role=admin"
h2 = ToyMD(h=server_sig)         # 상태 이어받기 — 공격의 핵심 한 줄
total_len = (key_len + len(msg) + len(pad1)) + len(suffix)
for b in suffix + ToyMD.padding_for(total_len):
    h2.compress(b)
forged_sig = h2.h
print("위조한 해시 =", forged_sig)

# 서버가 실제로 계산하는 값과 비교
real_sig2 = ToyMD().digest(secret + msg + pad1 + suffix)
print("서버가 직접 계산한 값 =", real_sig2)
print("일치 여부:", forged_sig == real_sig2)
print("위조된 메시지 =", (msg + pad1 + suffix))

패딩 바이트: 800000000f
위조한 해시 = 57
서버가 직접 계산한 값 = 57
일치 여부: True
위조된 메시지 = b'id=guest\x80\x00\x00\x00\x0f&role=admin'

출력 읽는 법: secret을 모른 채 &role=admin이 붙은 메시지의 올바른 서명을 만들어 냈습니다. 위조 메시지 중간의 \x80\x00\x00\x00\x0f는 원본의 패딩 잔해입니다 — 서버가 메시지를 문자열로 해석해 패딩을 무시하거나 파라미터 구분자로 삼지 않는다면(실제 취약 사례들이 그랬습니다) 이 요청은 통과합니다.

3-4. HMAC은 왜 안전한가

inner = ToyMD().digest(b"\x36" * key_len + msg)      # H(k⊕ipad || m) 의 축소형
outer = ToyMD().digest(b"\x5c" * key_len + bytes([inner]))  # H(k⊕opad || inner)
print("토이 HMAC 값:", outer)

토이 HMAC 값: 47

읽는 법: HMAC의 출력 outer는 "m까지 처리한 내부 상태"가 아니라, inner라는 중간 결과를 다시 한 번 해시한 바깥쪽 상태입니다. 공격자가 outer를 이어받아 suffix를 붙여도, 그 결과는 H(k⊕opad || inner || ...)이지 H(k⊕opad || H(k⊕ipad || m || suffix))가 아닙니다 — 구조가 확장을 봉쇄합니다. 실무에서는 hmac 모듈을 쓰세요. 직접 조립하지 않습니다.

3-5. MD5·SHA1의 현재

print("MD5(hello)  =", hashlib.md5(b"hello").hexdigest())
print("SHA1(hello) =", hashlib.sha1(b"hello").hexdigest())

MD5(hello)  = 5d41402abc4b2a76b9719d911017c592
SHA1(hello) = aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d

읽는 법: 둘 다 지금도 계산은 됩니다 — 문제는 "깨졌다"는 것이지 "사라졌다"가 아닙니다. 파일 무결성 확인처럼 공격자가 없는 용도에서는 여전히 만나지만, 서명·인증·비밀번호 등 적대적 환경에서는 금지입니다. CTF에서 MD5/SHA1이 등장하면 "충돌 또는 레인보우 테이블이 답일 가능성"을 후보에 올리세요.

4. 미션과 연습문제

미션 — 길이 확장 공격 재현과 방어

3-2의 ToyMD를 이용해, secret을 b"topsecret"(9바이트)로 바꾼 서버 시나리오를 만들고 길이 확장으로 &debug=1이 붙은 위조 서명을 성공시킵니다 — secret 길이를 모른다고 가정하고 1~16을 브루트포스로 추측하는 루프를 포함시킵니다
같은 시나리오를 H(msg + secret) 순서로 바꿔 보고, 길이 확장이 왜 실패하는지 한 줄로 설명합니다
위조 성공 출력과 서버 계산값의 일치를 출력으로 증명합니다

연습문제

문제 1. H(secret + msg) 방식의 인증이 길이 확장에 취약한 이유를 "내부 상태의 공개"라는 관점에서 설명해 보세요.

문제 2. 눈사태 효과 실험에서 64자리 중 63자리가 바뀌었습니다. 만약 8자리만 바뀌는 해시가 있다면, 그것은 어떤 성질의 파괴를 의심하게 하나요?

문제 3. MD5가 "서명 용도로 폐기"된 이유와, 그래도 파일 다운로드 무결성 확인에는 아직 쓰이는 이유를 각각 한 문장으로 답해 보세요.

문제 4. HMAC이 길이 확장에 안전한 이유를, H(k + m)과 구조를 비교하며 설명해 보세요. 그리고 SHA-3가 안전한 이유는 HMAC과 어떻게 다른가요?

5. 모범 답안과 완료 기준

미션 모범 답안

핵심은 "길이 추측 루프"입니다 (2026-09-09 실측으로 확인한 패턴):

secret = b"topsecret"          # 서버만 아는 값 (공격자 코드에는 등장 금지)
msg = b"id=guest"
server_sig = ToyMD().digest(secret + msg)

suffix = b"&debug=1"
for guess in range(1, 17):     # secret 길이 브루트포스
    pad1 = ToyMD.padding_for(guess + len(msg))
    h2 = ToyMD(h=server_sig)
    total = guess + len(msg) + len(pad1) + len(suffix)
    for b in suffix + ToyMD.padding_for(total):
        h2.compress(b)
    pad1_real = ToyMD.padding_for(len(secret) + len(msg))
    if h2.h == ToyMD().digest(secret + msg + pad1_real + suffix):
        print(f"길이 {guess}에서 위조 성공: {h2.h}")
        break

검증하는 법: ① 추측 루프가 길이 9에서 성공하는가. ② H(msg + secret) 순서에서는 — 해시가 msg부터 처리하므로 출력 상태가 secret을 포함한 "뒤쪽 상태"이지만, 공격자가 이어받아도 H(msg || secret || pad || suffix) 꼴이 되어 서버가 기대하는 H(msg+secret) 검증 구조와 어긋남을 설명했는가 (secret이 뒤에 있으면 이어붙인 데이터가 secret 뒤가 아니라 그 바깥에 붙습니다). ③ 위조값과 서버값의 일치 출력이 있는가.

연습문제 해답

문제 1 해답. 머클-담고르 해시의 출력은 "입력을 다 처리한 직후의 내부 상태" 그 자체입니다. H(secret + msg)를 알면 그 상태에서 압축을 이어갈 수 있으므로, 비밀을 모른 채 H(secret || msg || pad || 추가 데이터)를 계산할 수 있습니다. 출력이 곧 상태이기 때문에 생기는 공격입니다.

문제 2 해답. 눈사태 효과가 약한 것이며, 나아가 충돌 저항성의 파괴를 의심하게 합니다. 비슷한 입력이 비슷한 해시를 가진다면, 입력을 조금씩 바꾸며 원하는 해시에 "근접"해 가는 유도 공격이 가능해지기 때문입니다.

문제 3 해답. 폐기 이유: 2004년 이후 실용 시간 내 충돌 쌍 생성이 가능해져, 서명 대상 문서를 공격자가 바꿔치기할 수 있게 됐기 때문입니다. 무결성 확인에 남는 이유: 다운로드 대조처럼 적대적이지 않은 환경에서는 우발적 손상만 잡으면 되고, 그 용도에는 충돌 공격이 무의미하기 때문입니다 (그래도 새 시스템에는 SHA-256 이상을 권장합니다).

문제 4 해답. H(k + m)은 출력이 내부 상태라 이어붙이기가 됩니다. HMAC은 H(k⊕opad || H(k⊕ipad || m))로, 바깥 해시의 입력이 안쪽 해시의 "결과"이므로 출력을 이어받아도 안쪽을 확장할 방법이 없습니다. SHA-3는 머클-담고르가 아닌 스펀지 구조라 출력이 내부 상태 전부가 아니어서(상태의 일부만 노출), 구조 자체로 안전합니다 — HMAC 없이 SHA3(k + m)도 길이 확장이 안 됩니다.

완료 기준 체크리스트

[ ] 머클-담고르 구조를 "상태를 이어받는 압축 반복"으로 설명할 수 있다
[ ] 눈사태 효과를 hashlib 실측으로 확인했다
[ ] 토이 해시에서 길이 확장 위조를 성공시켰다 (일치 여부 True 출력)
[ ] secret 길이를 모를 때 브루트포스로 추측하는 절차를 안다
[ ] MD5/SHA1이 깨진 의미(충돌)와 여전히 계산 가능한 사실을 구분한다
[ ] HMAC과 SHA-3가 안전한 구조적 이유를 각각 설명할 수 있다
[ ] 미션: 길이 추측 루프 포함 위조 스크립트 완성

6. 흔한 실수와 해결

벽 1. 위조값이 서버 계산과 안 맞는다

증상: 3-3에서 일치 여부가 False.
원인: 패딩을 "원본 메시지 길이"가 아닌 "suffix 길이" 기준으로 계산한 경우가 가장 흔합니다. 최종 패딩은 항상 서버가 보게 될 전체 길이(secret + msg + pad1 + suffix) 기준입니다.
해결: padding_for()에 넣는 길이를 출력해 보세요 — 원본 패딩은 15, 최종 패딩은 31이 나와야 합니다(3-3 실측 기준).

벽 2. pow는 되는데 해시 상태 이어받기가 안 된다

증상: hashlib.sha256 객체에 임의 상태를 주입할 방법을 못 찾습니다.
원인: 표준 hashlib은 내부 상태 주입을 허용하지 않습니다 — 그래서 실제 SHA-256 대상 길이 확장은 hashpump/hashpumpy 같은 전용 도구(상태를 직접 조작)가 필요합니다.
해결: 이 챕터에서는 토이 해시로 구조를 이해하고, 실제 문제(CTF)에서는 해당 플랫폼 환경에서 hashpumpy를 씁니다. 원리는 오늘 실측한 것과 정확히 같습니다.

벽 3. 패딩 바이트 때문에 서버가 요청을 거부한다

증상: 위조 메시지 중간의 \x80\x00... 때문에 서버 파서가 깨집니다.
원인: 실제 시스템이 메시지를 정규화하거나 특수 바이트를 거부하는 경우입니다.
해결: 그 시스템은 길이 확장에 (우연히) 덜 취약한 것입니다 — 공격 성립 조건은 "서버가 패딩 잔해를 포함한 메시지를 그대로 해시한다"입니다. CTF 문제라면 대부분 그대로 해시하도록 설계되어 있습니다.

벽 4. "SHA-256도 뚫리는데 왜 쓰나요?"

증상: 길이 확장이 된다는 사실에 해시 전체를 불신하게 됩니다.
원인: 용도 혼동입니다. 길이 확장은 H(secret + msg)라는 잘못된 조립을 공격하는 것이지, 해시 자체의 약점이 아닙니다. 파일 지문·무결성·HMAC 안에서의 SHA-256은 건재합니다.
해결: "알고리즘의 약점"과 "조립의 약점"을 구분하는 표를 노트에 적어 두세요.

벽 5. MD5로 "hello"를 해시했는데 책과 다르다

증상: 5d41402a...가 아닌 다른 값이 나옵니다.
원인: 입력 인코딩 차이입니다 — "hello"와 b"hello", 줄바꿈 포함 여부에 따라 해시가 다릅니다.
해결: 입력을 바이트로 명시(b"hello")하고, 파일을 해시할 때는 rb 모드로 읽으세요.

7. 정리

오늘의 개념

개념	한 줄 설명
머클-담고르 구조	상태를 이어받아 블록 단위로 압축하는 해시 구조 — MD5, SHA-1, SHA-2
눈사태 효과	입력 1비트 차이 → 출력 절반이 뒤집히는 성질
길이 확장 공격	`H(secret+msg)`의 출력(=내부 상태)을 이어받아 데이터 추가 위조
충돌 저항성	같은 해시를 가진 두 입력을 찾기 어려운 성질 — MD5, SHA-1에서 파괴됨
패딩	메시지 끝에 붙는 길이 정보 — 길이 확장 계산의 필수 재료
HMAC	해시를 두 겹으로 감싸 길이 확장을 봉쇄하는 표준 메시지 인증
SHA-3	스펀지 구조 — 출력이 내부 상태 전부가 아니라 길이 확장 내성

오늘의 명령어·코드

명령	하는 일
`hashlib.sha256(b"...").hexdigest()`	SHA-256 해시 (16진수 문자열)
`hashlib.md5() / .sha1()`	폐기된 해시 — 식별·분석 용도로만
`ToyMD(h=값)` (직접 구현)	상태를 이어받는 토이 해시 — 길이 확장 시연용
`padding_for(길이)` (직접 구현)	주어진 길이의 메시지에 붙는 패딩 계산

명령어보다 중요한 감각

오늘의 교훈은 하나입니다 — 안전한 부품도 잘못 조립하면 취약점이 됩니다. SHA-256은 튼튼하지만 H(secret + msg)는 깨집니다. 반대로 HMAC은 같은 해시를 두 번 감쌌을 뿐인데 구조가 공격을 봉쇄합니다. 앞으로 어떤 시스템에서든 "해시를 서명처럼 쓴" 설계를 만나면, 오늘 실측한 그 한 줄 — 상태 이어받기 — 을 떠올리세요.

전부 체크되면 Step 234 완료입니다. 사이드바의 체크박스를 눌러 진도를 저장하세요.

Step 234. 해시 공격: 길이 확장, 충돌 개념 — 해시를 “서명”으로 쓰면 생기는 일