Hash Function Design Principles (Sponge, Merkle-Damgård) TODO

Math · Day 50 / 52 · December — Cryptography & Information Theory (Day 44-52)

Concept

A cryptographic hash function maps an arbitrary-length input to a fixed-length output while aiming for preimage resistance, second-preimage resistance, and collision resistance. Because of the birthday problem, collision resistance for an n-bit output is capped at roughly 2^(n/2), so the choice of output length is what sets the security level. The Merkle-Damgård construction splits the input into blocks and repeatedly applies a compression function, appending length-encoding padding at the end; it's provable that if the compression function is collision resistant, so is the whole construction — but because the internal state is exactly the output, it's vulnerable to length-extension attacks. The sponge construction instead splits internal state into a rate portion that's exposed and a capacity portion that's never exposed; it absorbs input and then squeezes out as much output as needed, which supports arbitrary-length output and is not vulnerable to length-extension attacks. The security level is governed by the size of the capacity.

Using a hash for authentication without knowing whether it's vulnerable to length extension breaks the MAC construction, and choosing too short an output length opens the door to collision-based attacks.

Code & Formula

# 해시함수 설계 원리(스펀지·머클-담고르) — 고정 크기 압축함수를 체이닝해 임의 길이 입력을
# 고정 길이로 접는 머클-담고르 구성을 hashlib 없이 토이 버전으로 직접 만들어 본다.

def compress(state: int, block: int, mod: int = 2**32) -> int:
    # 진짜 해시가 아니라 예시용 압축함수 — 비선형 섞기 흉내만 낸다.
    return ((state ^ block) * 2654435761 + 0x9E3779B9) % mod


def merkle_damgard(message: bytes, block_size: int = 4) -> int:
    padded = message + b"\x80" + b"\x00" * ((-len(message) - 1) % block_size)
    state = 0
    for i in range(0, len(padded), block_size):
        block = int.from_bytes(padded[i:i + block_size], "big")
        state = compress(state, block)
    return state


h1 = merkle_damgard(b"hello world")
h2 = merkle_damgard(b"hello world!")   # 한 글자만 달라짐
h3 = merkle_damgard(b"hello world")    # 같은 입력 → 같은 해시

print(f"H('hello world')  = {h1:#010x}")
print(f"H('hello world!') = {h2:#010x}  (한 글자만 달라도 완전히 다른 출력 — 눈사태 효과)")
print(f"determinism check: H('hello world') 재계산 == 원래 값? {h1 == h3}")

docs/code/math/math-50.py

Exercise

Build a naive secret-prefix MAC using a Merkle-Damgård-family hash and actually succeed at a length-extension attack against it, then try the same attack against a sponge-family hash and against HMAC and confirm they're not vulnerable.

Practical Connection

Ethereum uses Keccak-family sponge hashes, and Merkle trees, address generation, and storage keys all depend on it — so how you construct hash input encoding for Verex's condition ID or position ID is directly a question of collision safety.

Where it lands in Jayverse

• Verex: document which hash construction backs condition ID and position ID generation. Confirm it's Keccak-family sponge (inherited from Solidity), and confirm the input encoding can't let two different conditions collide on the same ID — an encoding ambiguity, not the hash itself, is the usual source of that bug.
• Auditor: add a length-extension test to the checklist for any hash-based authentication scheme. If Verex or another service ever signs API tokens or session data on top of a raw hash, confirm it's HMAC or a sponge construction rather than naive secret-prefix Merkle-Damgård before trusting it as a MAC.

If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.

한국어

해시함수 설계 원리(스펀지·머클-담고르) TODO

Math · Day 50 / 52 · 12월 — 암호학·정보이론 (Day 44–52)

개념

암호학적 해시함수는 임의 길이 입력을 고정 길이 출력으로 보내면서 원상 저항성, 제2원상 저항성, 충돌 저항성을 목표로 한다. 생일 문제 때문에 n비트 출력의 충돌 저항성은 대략 2의 n/2제곱 수준이 상한이므로 출력 길이 선택이 곧 보안 수준이 된다. 머클-담고르 구조는 입력을 블록으로 나눠 압축함수를 반복 적용하고 마지막에 길이를 포함한 패딩을 붙이는 방식으로, 압축함수가 충돌 저항적이면 전체도 충돌 저항적임을 증명할 수 있지만 내부 상태가 곧 출력이라 길이 확장 공격에 취약하다. 스펀지 구조는 내부 상태를 외부에 드러나는 rate 부분과 절대 드러나지 않는 capacity 부분으로 나누고, 입력을 흡수(absorb)한 뒤 필요한 만큼 출력을 짜내는(squeeze) 방식이라 임의 길이 출력을 지원하고 길이 확장 공격이 성립하지 않는다. 보안 수준은 capacity 크기가 좌우한다.

길이 확장 공격 가능 여부를 모른 채 해시를 인증에 쓰면 MAC 구성이 깨지고, 출력 길이를 잘못 고르면 충돌 기반 공격에 문이 열린다.

코드 · 수식

# 해시함수 설계 원리(스펀지·머클-담고르) — 고정 크기 압축함수를 체이닝해 임의 길이 입력을
# 고정 길이로 접는 머클-담고르 구성을 hashlib 없이 토이 버전으로 직접 만들어 본다.

def compress(state: int, block: int, mod: int = 2**32) -> int:
    # 진짜 해시가 아니라 예시용 압축함수 — 비선형 섞기 흉내만 낸다.
    return ((state ^ block) * 2654435761 + 0x9E3779B9) % mod


def merkle_damgard(message: bytes, block_size: int = 4) -> int:
    padded = message + b"\x80" + b"\x00" * ((-len(message) - 1) % block_size)
    state = 0
    for i in range(0, len(padded), block_size):
        block = int.from_bytes(padded[i:i + block_size], "big")
        state = compress(state, block)
    return state


h1 = merkle_damgard(b"hello world")
h2 = merkle_damgard(b"hello world!")   # 한 글자만 달라짐
h3 = merkle_damgard(b"hello world")    # 같은 입력 → 같은 해시

print(f"H('hello world')  = {h1:#010x}")
print(f"H('hello world!') = {h2:#010x}  (한 글자만 달라도 완전히 다른 출력 — 눈사태 효과)")
print(f"determinism check: H('hello world') 재계산 == 원래 값? {h1 == h3}")

docs/code/math/math-50.py

연습

머클-담고르 계열 해시로 naive한 secret 접두 MAC을 만들어 길이 확장 공격을 실제로 성공시켜 보고, 같은 시도를 스펀지 계열 해시와 HMAC에 해봐서 막히는지 확인하라.

실무 · Verex 연결

이더리움은 Keccak 계열 스펀지 해시를 쓰고 머클 트리·주소 생성·스토리지 키가 모두 여기에 의존하므로, Verex의 컨디션 ID나 포지션 ID를 다루는 코드에서 해시 입력 인코딩을 어떻게 구성하느냐가 곧 충돌 안전성 문제가 된다.

Jayverse에서의 위치

• Verex: 컨디션 ID와 포지션 ID 생성을 뒷받침하는 해시 구성을 문서화한다. Solidity에서 물려받은 Keccak 계열 스펀지 구성인지 확인하고, 입력 인코딩이 서로 다른 두 컨디션을 같은 ID로 충돌시킬 수 없는지 확인한다. 보통 이 버그의 원인은 해시 자체가 아니라 인코딩의 모호함이다.
• Auditor: 해시 기반 인증 방식에는 길이 확장 공격 테스트를 체크리스트에 추가한다. Verex나 다른 서비스가 원시 해시 위에 API 토큰이나 세션 데이터를 서명한다면, 이를 MAC으로 신뢰하기 전에 순진한 secret-prefix 머클-담고르가 아니라 HMAC이거나 스펀지 구성인지 확인한다.

공부한 날 원본 커리큘럼(docs/knowledge/math-50-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.