Wahr/Falsch
문제
독일어 원문
Der MD5-Hashing-Algorithmus produziert garantiert keine Kollisionen.
한국어 해석
MD5-Hashing-Algorithmus는 Kollisionen을 절대 만들지 않는다고 보장한다. Wahr/Falsch?
Wahr/Falsch 즉시 채점
선택 후 즉시 개념 함정을 확인하세요.
단계별 힌트
막혔을 때만 한 단계씩 여세요. 정답을 바로 읽는 것보다 기억을 꺼내는 시간이 중요합니다.
- 첫 힌트: Hash output은 fixed length이다. 입력 공간과 출력 공간 크기를 비교해 보라.
- 계산형 문항이 아니다.
- 판단 절차: fixed output length와 pigeonhole principle, MD5 약점을 연결한다.
- 함정: collision resistance를 collision-free와 동일시하기
- 함정: MD5를 현대 안전 hash로 취급하기
- 후속 점검: 왜 kollisionsfreie Hashfunktion은 수학적으로 존재하기 어려운가?
채점 기준으로 내 답안 점검하기
- Wahr/Falsch를 Falsch로 표시한다.
- 고정 길이 출력 때문에 collision 자체는 가능함을 설명한다.
- Kollisionsresistenz는 찾기 어렵다는 성질이지 존재하지 않는다는 보장이 아님을 적는다.
- MD5는 course material에서 약한 hash로 취급된다고 언급한다.
답안 슬롯 자가 점검 — 실제로 말하거나 쓴 항목만 체크하세요.
0/4 slots
정답과 핵심 해설 확인하기
Falsch
MD5는 collision absence를 보장하지 않으며, 안전한 collision resistance도 제공하지 못한다.
개념부터 다시 보는 상세 풀이
BEGINNER LESSON
1-(g) MD5는 collision을 절대 만들지 않는가?
ZERO-BASE START
정말 아무것도 모른다고 가정하고 시작합니다
전문 용어를 알고 있다고 가정하지 않습니다. 먼저 일상적인 장면을 보고, 그 장면의 사람과 행동에 실제 보안 용어를 하나씩 붙인 뒤, 시스템에서 일어나는 순서를 따라갑니다.
기초 개념 01
Hash는 암호화가 아니라 고정 길이 지문이다
1타 강사식 시작: 이름은 잠시 가리고 장면부터 봅시다
수많은 책을 짧은 서가 번호로 압축해 표시하면 언젠가 같은 번호가 겹친다. 좋은 hash는 공격자가 원하는 겹침을 일부러 찾기 매우 어렵게 만든다.
지금은 이 비유를 완벽히 외울 필요가 없습니다. 누가 무엇을 가지고 있고, 무엇을 하려 하며, 어느 지점에서 문제가 생기는지만 찾으면 됩니다.
이제 실제 용어를 하나씩 붙여 봅시다
Cryptographic hash function은 길이가 제각각인 입력을 정해진 길이의 digest로 바꾼다. 같은 입력은 같은 digest를 만들지만 digest에서 원문을 되찾기는 어려워야 한다. 서로 다른 두 입력이 같은 digest를 만드는 상황을 collision이라고 한다. 입력 가능성은 사실상 무한하고 출력 종류는 유한하므로 collision은 수학적으로 반드시 존재하며, 보안 목표는 collision이 전혀 없게 하는 것이 아니라 현실적인 시간에 찾기 어렵게 하는 것이다.
TERMS FROM ZERO
전문 용어를 한 단어씩 풀기
아래 단어는 이미 안다고 가정하지 않습니다. 먼저 쉬운 뜻을 읽고, 본문에서 같은 단어가 나오면 이 정의로 다시 바꾸어 읽으세요.
Hash function
임의 길이 입력을 고정 길이 digest로 바꾸는 단방향 함수입니다. 암호화처럼 복호화 key가 있는 기능이 아닙니다.
Digest
Hash function의 고정 길이 출력으로, 데이터의 짧은 지문처럼 사용됩니다.
Collision
서로 다른 두 입력이 같은 digest를 만드는 경우입니다. 출력 공간이 유한하므로 존재 자체는 피할 수 없습니다.
Preimage resistance
주어진 digest를 만드는 입력을 현실적인 시간에 찾기 어려워야 한다는 성질입니다.
프로그램이나 프로토콜 안에서는 다음 순서로 움직입니다.
- 출력 길이는 입력 문장 길이가 아니라 알고리즘이 정한 bit 수로 고정된다.
- Preimage resistance는 digest에서 원문을 찾기 어려운 성질이다.
- Collision resistance는 서로 다른 두 입력의 같은 digest를 찾기 어려운 성질이다.
- MD5처럼 실용적인 collision 공격이 알려진 알고리즘은 보안 용도로 사용하지 않는다.
왜 여기서 많이 틀릴까요?
collision-free라는 절대 표현과 collision-resistant라는 계산적으로 찾기 어렵다는 표현을 구분해야 한다.
조건을 생략하거나 서로 다른 기능을 같은 것으로 취급했는지 확인하세요. 정답 문장을 외우는 것보다 틀린 이유를 말할 수 있어야 변형 문제를 풀 수 있습니다.
핵심부터 말하면 정답은 Falsch(거짓). 고정 길이 해시는 수학적으로 collision이 반드시 존재하며, MD5는 그 충돌을 실제로 효율적으로 만들어 내는 공격까지 알려진 낡고 안전하지 않은 알고리즘이다.
이 글에서 익힐 것
collision의 정확한 정의를 말할 수 있다.
collision resistance와 collision-free를 구분한다.
비둘기집 원리와 birthday bound의 직관을 이해한다.
MD5를 단순 오류 검사용으로 쓰는 것과 보안 용도로 신뢰하는 것을 구분한다.
개념부터 차근차근
-
Collision이란
서로 다른 두 입력 m₁≠m₂가 같은 해시 H(m₁)=H(m₂)를 만들면 collision(충돌)이다. 입력이 완전히 같아 같은 해시가 나오는 것은 collision이 아니다. 공격자는 의미가 다른 두 문서가 같은 지문을 갖게 만들어 서명이나 무결성 검사를 속이려 할 수 있다.
-
해시는 왜 충돌을 피할 수 없는가
MD5 출력은 128비트라 가능한 digest가 2¹²⁸개다. 하지만 입력은 길이 제한 없이 훨씬 많다. 무한히 많은 물건을 2¹²⁸개의 상자에 넣으면 적어도 한 상자에는 서로 다른 물건 둘 이상이 들어간다. 따라서 어떤 고정 길이 해시도 충돌 없음(collision-free)을 보장할 수 없다.
-
보안 목표는 충돌 저항성
암호학은 충돌이 존재하지 않는다고 요구하지 않는다. 공격자가 현실적인 시간과 자원으로 서로 다른 두 입력의 충돌을 찾기 어려워야 한다는 collision resistance를 요구한다. 이상적인 n비트 해시는 birthday attack 때문에 대략 2^(n/2)번 시도에서 충돌을 기대한다.
-
MD5가 특별히 나쁜 이유
MD5는 128비트 출력이라는 크기 문제뿐 아니라 구조적 약점 때문에 일반적인 birthday brute force보다 훨씬 실용적인 collision 생성 공격이 알려져 있다. 그래서 디지털 서명, 인증서, 공격자가 파일을 선택할 수 있는 무결성 보장에 사용하면 안 된다.
예제로 확인하기
상황 설정
출력이 2비트뿐인 장난감 해시 H를 생각한다. 가능한 출력은 00, 01, 10, 11 네 개뿐이다.
풀이 순서
서로 다른 입력 5개를 해시하면 출력 상자는 4개뿐이다.
비둘기집 원리에 따라 적어도 두 입력은 반드시 같은 2비트 digest를 공유한다.
출력이 128비트인 MD5에서는 상자가 엄청 많지만 입력 가능성은 그보다 더 많으므로 원리는 같다.
안전성 질문은 '충돌이 존재하는가?'가 아니라 '공격자가 유용한 충돌을 얼마나 쉽게 찾을 수 있는가?'다.
MD5는 후자의 답도 나쁘기 때문에 cryptographically broken으로 취급한다.
Three security properties
-
주어진 digest h에 대해 H(m)=h인 입력 m을 찾기 어려운가?
Preimage resistance
collision resistance와 다른 목표다.
-
주어진 입력 m₁에 대해 같은 해시의 다른 m₂를 찾기 어려운가?
Second-preimage resistance
공격자가 첫 문서를 마음대로 고르지 못한다.
-
공격자가 둘 다 선택해 H(m₁)=H(m₂)인 서로 다른 쌍을 찾기 어려운가?
Collision resistance
MD5가 특히 명백히 실패한 속성이다.
Practical meaning
공식 사이트가 제공한 MD5 checksum과 다운로드 파일을 비교하면 우발적 전송 오류는 발견할 수 있다.
하지만 공격자가 파일과 공개된 checksum을 함께 바꿀 수 있다면 어떤 해시도 인증을 제공하지 않는다.
공격자가 서로 다른 두 파일을 설계할 수 있는 보안 상황에서는 MD5 collision 공격 때문에 신뢰해서는 안 된다.
현대적인 일반 선택은 SHA-256/SHA-512 계열이며, 비밀번호 저장에는 빠른 일반 해시 대신 salt를 포함한 Argon2id, scrypt, bcrypt 같은 password hashing/KDF가 필요하다.
문장을 하나씩 판별하기
produziert garantiert keine Kollisionen은 단 하나의 충돌도 없다는 절대 주장이다.
고정 128비트 출력이라는 사실만으로도 수학적으로 거짓이다.
게다가 MD5는 이론적 존재를 넘어 실제 collision 공격이 알려져 있으므로 더욱 명확히 Falsch다.
정답까지 사고 과정
1단계: collision을 m₁≠m₂이면서 H(m₁)=H(m₂)라고 정의한다.
2단계: 무한한 입력과 유한한 128비트 출력을 비교해 충돌 존재를 설명한다.
3단계: 안전한 해시도 충돌이 없는 것이 아니라 찾기 어려운 것이라고 구분한다.
4단계: MD5에는 실용적 collision 공격이 알려졌다고 덧붙인다.
5단계: 보장한다는 문장을 Falsch로 판정한다.
시험장에서는 이렇게 쓰기
최소 답안
Falsch.
안전한 두 문장 답안
Falsch. Wegen der Abbildung beliebig vieler Eingaben auf nur 2¹²⁸ MD5-Ausgaben müssen Kollisionen mathematisch existieren. Außerdem sind für MD5 praktische Kollisionsangriffe bekannt, weshalb MD5 nicht kollisionsresistent und für kryptographische Sicherheitszwecke ungeeignet ist.
Precision sentence
Auch eine moderne Hashfunktion ist nicht kollisionsfrei; Kollisionen sollen lediglich praktisch schwer zu finden sein.
자주 틀리는 지점
MD5가 오래되어서 그냥 거짓이라고만 쓰고 collision 정의를 설명하지 않는 것.
안전한 SHA-256은 collision이 절대 없다고 반대로 주장하는 것.
같은 입력을 두 번 해시해 같은 출력이 나온 것을 collision이라 부르는 것.
collision, preimage, second preimage 공격을 모두 같은 것으로 취급하는 것.
MD5 checksum이 우발적 오류 감지에도 전혀 쓸모없다고 과장하는 것. 보안 공격자가 있는 무결성·인증 용도에 부적합한 것이 핵심이다.
한 줄로 기억하기
해시는 무한한 사람에게 유한한 사물함 번호를 나눠 주는 것과 같다. 번호 중복은 반드시 생긴다. 좋은 해시는 같은 번호를 가진 두 사람을 찾기 어렵게 하고, MD5는 그 찾는 법까지 알려진 낡은 배정표다.
스스로 확인하기
-
collision의 수식 조건은?
m₁≠m₂이고 H(m₁)=H(m₂).
-
256비트 이상적 해시의 generic collision 탐색 규모는 대략?
birthday bound에 따라 약 2¹²⁸번이다.
-
현대 해시에서 collision이 수학적으로 전혀 없는가?
아니다. 존재하지만 현실적으로 찾기 어려워야 한다.
설명의 근거
Gedächtnisprotokoll Computersystemsicherheit WS2025_26.md — Krypto / Multiple Choice.
Übung 2 Lösung, p.3-4 — 충돌이 수학적으로 존재하는 이유와 안전/비안전 해시.
Vorlesung 02 Grundlagen Krypto, p.47-48 — MD5를 약하거나 안전하지 않은 hash function의 예로 제시.
이 문제가 어려운 이유
짧은 문제 문장 ‘MD5-Hashing-Algorithmus는 Kollisionen을 절대 만들지 않는다고 보장한다. Wahr/Falsch?’ 안에 정의, 조건, 처리 순서가 압축되어 있습니다. 아래 예시에서는 이를 한 단계씩 펼쳐 확인합니다.
AI 구두시험용 프롬프트
한 문항만 풀어라. 먼저 정답을 열지 말고 90초 안에 답안을 말한 뒤, css-ws2025-26-crypto-mc-007의 채점 프레임으로 스스로 채점하라. 문제: MD5-Hashing-Algorithmus는 Kollisionen을 절대 만들지 않는다고 보장한다. Wahr/Falsch?
학습 기록