Hash Function Design Principles (Sponge, Merkle-Damgård) TODO
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}")
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.
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/.