decalage2/collisions해시 충돌과 그 악용
TL;DR 이제(*) 이 두 이미지의 MD5 충돌을 만드는 것은 사소한 일이 되어 즉각적으로 가능합니다.
⟷
<a href=http://gunshowcomic.com/648>
불장난하지 마세요, MD5를 믿지 마세요.
(*) 임의의 두 파일 간의 충돌을 만드는 것은 수년 전부터 가능했지만, 매번 몇 시간이 걸렸고 지름길도 없었습니다.
이 페이지는 파일 형식별 트릭과 미리 계산된 충돌 접두사를 제공하여 충돌을 즉시 가능하게 합니다.
git clone. 스크립트 실행. 끝.
Ange Albertini와 Marc Stevens 지음.
이 문서의 목표는 기존 공격들을 폭넓게 탐구하고, 그 과정에서 MD5가 얼마나 취약한지 보여 주는 것입니다(모든 JPG, PNG, PDF, MP4, PE...의 즉시 충돌). 또한 일반적인 파일 형식을 자세히 살펴보아 현재 또는 미래의 공격으로 어떻게 악용될 수 있는지 파악합니다.
실제로 동일한 파일 형식 트릭은 여러 해시에 사용될 수 있습니다. (동일한 JPG 트릭이 MD5, 악성 SHA-1 및 SHA1에 사용되었습니다), 충돌이 동일한 바이트 패턴을 따르는 한 말입니다.
이 문서는 새로운 공격에 관한 것이 아닙니다(가장 최근의 공격은 2012년에 문서화되었습니다). 오히려 기존 공격의 새로운 악용 형태에 관한 것입니다.
2018년 12월 기준, 알려진 공격들의 현재 상황은 다음과 같습니다.
한 파일을 얻어 다른 파일의 해시 또는 주어진 해시를 얻기: 불가능
동일한 MD5를 가진 서로 다른 두 파일 얻기: 즉시
임의의 두 파일이 같은 MD5를 갖도록 만들기: 몇 시간 (72시간.core)
특정 파일 형식(PNG, JPG, PE...)의 임의의 두 파일이 같은 MD5를 갖도록 만들기: 즉시
동일한 SHA1을 가진 서로 다른 두 파일 얻기: 6500년.core
(*) crypt를 사용한 예시 - Sven에게 감사합니다!```
import crypt crypt.crypt("5dUD&66", "br") 'brokenOz4KxMc' crypt.crypt("O!>',%$", "br") 'brokenOz4KxMc'
# 공격
MD5와 SHA1은 64바이트 블록으로 동작합니다.
두 콘텐츠 A와 B가 동일한 해시를 가진다면, 두 콘텐츠 모두에 동일한 콘텐츠 C를 추가해도 해시는 동일하게 유지됩니다.``` text
hash(A) = hash(B) -> hash(A + C) = hash(B + C)
충돌은 블록 경계에 계산된 충돌 블록들을 삽입하는 방식으로 작동하며, 그 블록들의 개수는 파일에서 그 앞에 있던 내용에 따라 달라집니다. 이 충돌 블록들은 아주 무작위로 보이지만 몇 가지 사소한 차이점이 있으며, (이 차이점들은 각 공격에 대해 특정 패턴을 따릅니다.) 그리고 이들은 사소한 차이를 만들어 내면서 결국 이 블록들 이후에는 해시를 동일한 값으로 만듭니다.
이러한 차이점들은 특정 속성을 가진 유효한 파일을 제작하는 데 악용됩니다.
파일 형식도 위에서 아래로(top-down) 동작하며, 대부분은 바이트 단위 청크(chunk)로 동작합니다.
일부 '주석' 청크는 파일 청크를 블록 경계에 정렬하고, 특정 구조를 충돌 블록 차이에 정렬하며, 충돌 블록의 나머지 무작위성을 파일 파서로부터 숨기고, 그리고 그렇지 않으면 유효한 콘텐츠를 파서로부터 숨기기 위해(그래서 파서가 다른 콘텐츠를 보게 됩니다) 삽입될 수 있습니다.
이러한 '주석' 청크는 공식적으로 실제 주석이 아닌 경우가 많습니다: 그것들은 단지 파서가 무시하는 데이터 컨테이너로 사용되며, (예를 들어, 소문자로 시작하는 ID를 가진 PNG 청크는 필수(critical)가 아닌 보조(ancillary)입니다.)
대부분의 경우, 충돌 블록의 차이는 주석 청크의 길이를 수정하는 데 사용됩니다.
이 주석 청크의 길이는 일반적으로 이 청크의 데이터 바로 앞에 선언됩니다:
이 청크의 더 짧은 버전과 더 긴 버전 사이의 간격에서,
다른 주석 청크가 파일 콘텐츠 A 하나를 건너뛰도록 선언됩니다.
이 파일 콘텐츠 A 뒤에, 또 다른 파일 콘텐츠 B를 그냥 추가하면 됩니다.
파일 형식은 일반적으로 파서가 그 이후에 중지하도록 만드는 종결자(terminator)를 정의하므로,
A는 파싱을 종료하게 되어, 추가된 콘텐츠 B는 무시됩니다.
따라서 일반적으로 최소 두 개의 주석이 필요하며, 종종 세 개가 필요합니다:
파일 형식의 이러한 일반적인 속성들이 이를 가능하게 합니다. 이들은 일반적으로 취약점으로 간주되지 않지만, 탐지하거나 정규화하여 제거할 수 있습니다:
| 프리픽스 | = | 프리픽스 |
|---|---|---|
| 충돌 A | ≠ | 충돌 B |
| 접미사 | = | 접미사 |
두 파일은 거의 동일합니다 (콘텐츠에는 단지 몇 비트의 차이만 있습니다).
익스플로잇:
두 콘텐츠를 묶은 다음, 다음 중 하나를 수행합니다:
이 구조를 가진 두 파일:
| 프리픽스 | = | 프리픽스 |
|---|---|---|
| 충돌 A | ≠ | 충돌 B |
| A | = | |
| = | B |
A 또는 B 중 하나가 표시됩니다.
2009년의 최종 버전입니다.
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. X. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. .. .. .. .. .. .. .. .. X. .X ..
.. .. .. .. .. .. .. .. .. .. .. X. .. .. .. ..
차이점들이 블록의 시작/끝 근처에 있지 않으므로, 주변 바이트를 제어할 수 없어 익스플로잇하기가 매우 어렵습니다. 잠재적인 해결책은 주변 바이트를 무차별 대입(brute-force)하는 것입니다 - cf PoCGTFO 14:10.
예시:
빈 프리픽스를 사용하는 경우:``` MD5: fe6c446ee3a831ee010f33ac9c1b602c SHA256: c5dd2ef7c74cd2e80a0fd16f1dd6955c626b59def888be734219d48da6b9dbdd