TL;DR 이제(*) 이 두 이미지의 MD5 충돌을 만드는 것은 사소한 일이 되어 즉각적으로 가능합니다.

불장난하지 마세요, MD5를 믿지 마세요.

(*) 임의의 두 파일 간의 충돌을 만드는 것은 수년 전부터 가능했지만, 매번 몇 시간이 걸렸고 지름길도 없었습니다. 이 페이지는 파일 형식별 트릭과 미리 계산된 충돌 접두사를 제공하여 충돌을 즉시 가능하게 합니다. git clone. 스크립트 실행. 끝.

해시 충돌과 악용

Ange Albertini와 Marc Stevens 지음.

소개
현황
공격
악용
참고 자료
크레딧
결론

소개

이 문서의 목표는 기존 공격들을 폭넓게 탐구하고, 그 과정에서 MD5가 얼마나 취약한지 보여 주는 것입니다(모든 JPG, PNG, PDF, MP4, PE...의 즉시 충돌). 또한 일반적인 파일 형식을 자세히 살펴보아 현재 또는 미래의 공격으로 어떻게 악용될 수 있는지 파악합니다.

실제로 동일한 파일 형식 트릭은 여러 해시에 사용될 수 있습니다. (동일한 JPG 트릭이 MD5, 악성 SHA-1 및 SHA1에 사용되었습니다), 충돌이 동일한 바이트 패턴을 따르는 한 말입니다.

이 문서는 새로운 공격에 관한 것이 아닙니다(가장 최근의 공격은 2012년에 문서화되었습니다). 오히려 기존 공격의 새로운 악용 형태에 관한 것입니다.

현황

2018년 12월 기준, 알려진 공격들의 현재 상황은 다음과 같습니다.

한 파일을 얻어 다른 파일의 해시 또는 주어진 해시를 얻기: 불가능
- MD2의 경우에도 여전히 현실적이지 않습니다.
- 더 단순한 해시에는 작동합니다(*)
동일한 MD5를 가진 서로 다른 두 파일 얻기: 즉시
- 예시: 1 ⟷ 2
임의의 두 파일이 같은 MD5를 갖도록 만들기: 몇 시간 (72시간.core)
- 예시: 1 ⟷ 2
특정 파일 형식(PNG, JPG, PE...)의 임의의 두 파일이 같은 MD5를 갖도록 만들기: 즉시
- 아래를 읽어 보세요.
동일한 SHA1을 가진 서로 다른 두 파일 얻기: 6500년.core
- 다른 그림을 보여 주는 동일한 SHA-1을 가진 서로 다른 두 PDF 얻기: 즉시 (접두사는 이미 계산되어 있습니다)

(*) 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는 무시됩니다.

따라서 일반적으로 최소 두 개의 주석이 필요하며, 종종 세 개가 필요합니다:

정렬
충돌 블록 숨기기
하나의 파일 콘텐츠 숨기기(재사용 가능한 충돌을 위해)

파일 형식의 이러한 일반적인 속성들이 이를 가능하게 합니다. 이들은 일반적으로 취약점으로 간주되지 않지만, 탐지하거나 정규화하여 제거할 수 있습니다:

더미 청크 - 주석으로 사용됨
두 개 이상의 주석
거대한 주석 (길이: MP4는 64b, PNG는 32b -> 쉬운 충돌. JPG는 16b, GIF는 8b -> GIF에는 일반적인 충돌 없음, JPG는 제한적)
주석에 임의의 데이터 저장 (ASCII 또는 UTF8이 강제될 수 있음)
종결자 뒤에 아무거나 저장 (보통 악의적인 목적으로만 사용됨) - 동일한 오프셋에서 끝나는 두 개의 주석을 사용하여 피할 수 있습니다.
무결성 검사 없음. PNG의 CRC32는 보통 무시됩니다. 그러나 충돌 블록이 서로 다른 길이의 청크를 선언하기 때문에 모두 정확할 수 있습니다 - 그래서 청크의 데이터가 다르게 시작하더라도, 청크 길이는 다릅니다.
평면 구조: ASN.1은 포함된 모든 하위 구조의 길이를 가진 부모 구조를 정의하며, 이는 이러한 기법을 방지합니다: 길이뿐만 아니라 부모의 길이도 악용해야 합니다.
헤더 앞에 주석을 넣기 - 이는 일반적인 재사용 가능한 충돌을 가능하게 합니다.

동일한 프리픽스

임의의 프리픽스를 정의합니다 - 내용과 길이는 중요하지 않습니다.
프리픽스는 다음 64바이트 블록으로 패딩됩니다.
충돌 블록(들)은 프리픽스에 따라 계산되어 추가됩니다. 양쪽 모두 매우 무작위적입니다. 차이점은 공격에 의해 미리 결정됩니다.
이[이들] 블록[들] 이후에는 파일 차이에도 불구하고 해시 값이 동일합니다.
임의의 동일한 접미사를 추가할 수 있습니다.

프리픽스	=	프리픽스
충돌 A	≠	충돌 B
접미사	=	접미사

두 파일은 거의 동일합니다 (콘텐츠에는 단지 몇 비트의 차이만 있습니다).

익스플로잇:

두 콘텐츠를 묶은 다음, 다음 중 하나를 수행합니다:

데이터 익스플로잇: 차이점을 확인하고 하나 또는 다른 것을 표시하는 코드를 실행합니다 (차이점은 사전에 알려져 있으므로 일반적으로 사소합니다).
구조 익스플로잇: 파일 구조(일반적으로 주석의 길이)를 활용하여 하나의 콘텐츠를 숨기거나 다른 콘텐츠를 표시합니다 (파일 형식과 파서에 따라 다름).

이 구조를 가진 두 파일:

A 또는 B 중 하나가 표시됩니다.

FastColl (MD5)

2009년의 최종 버전입니다.

시간: 몇 초의 계산 시간
공간: 두 개의 블록

차이점: 앞에서 제어 불가, 뒤에서 제어 불가. FastColl 차이 마스크:

.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. X. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. .. .. .. .. .. .. .. .. X. .X ..
.. .. .. .. .. .. .. .. .. .. .. X. .. .. .. ..

익스플로잇: 어려움

차이점들이 블록의 시작/끝 근처에 있지 않으므로, 주변 바이트를 제어할 수 없어 익스플로잇하기가 매우 어렵습니다. 잠재적인 해결책은 주변 바이트를 무차별 대입(brute-force)하는 것입니다 - cf PoCGTFO 14:10.

예시:

빈 프리픽스를 사용하는 경우:``` MD5: fe6c446ee3a831ee010f33ac9c1b602c SHA256: c5dd2ef7c74cd2e80a0fd16f1dd6955c626b59def888be734219d48da6b9dbdd

00: 37 75 C1 F1-C4 A7 5A E7-9C E0 DE 7A-5B 10 80 26 7u┴±─ºZτ£α▐z[►Ç& 10: 02 AB D9 39-C9 6C 5F 02-12 C2 7F DA-CD 0D A3 B0 ☻½┘9╔l_☻↕┬⌂┌═♪ú░ 20: 8C ED FA F3-E1 A3 FD B4-EF 09 E7 FB-B1 C3 99 1D îφ·≤ßú²┤∩○τ√▒├Ö↔ 30: CD 91 C8 45-E6 6E FD 3D-C7 BB 61 52-3E F4 E0 38 ═æ╚Eµn²=╟╗aR>⌠α8
40: 49 11 85 69-EB CC 17 9C-93 4F 40 EB-33 02 AD 20 I◄àiδ╠↨£ôO@δ3☻¡ 50: A4 09 2D FB-15 FA 20 1D-D1 DB 17 CD-DD 29 59 1E ñ○-√§· ↔╤█↨═▌)Y▲ ................ 60: 39 89 9E F6-79 46 9F E6-8B 85 C5 EF-DE 42 4F 46 9ë₧÷yFƒµïà┼∩▐BOF ...X............ 70: C2 78 75 9D-8B 65 F4 50-EA 21 C5 59-18 62 FF 7B ┬xu¥ïe⌠PΩ!┼Y↑b { .............XX. ...........X.... ................ 00: 37 75 C1 F1-C4 A7 5A E7-9C E0 DE 7A-5B 10 80 26 7u┴±─ºZτ£α▐z[►Ç& ...X............ 10: 02 AB D9 B9-C9 6C 5F 02-12 C2 7F DA-CD 0D A3 B0 ☻½┘╣╔l_☻↕┬⌂┌═♪ú░ .............XX. 20: 8C ED FA F3-E1 A3 FD B4-EF 09 E7 FB-B1 43 9A 1D îφ·≤ßú²┤∩○τ√▒CÜ↔ ...........X.... 30: CD 91 C8 45-E6 6E FD 3D-C7 BB 61 D2-3E F4 E0 38 ═æ╚Eµn²=╟╗a╥>⌠α8 40: 49 11 85 69-EB CC 17 9C-93 4F 40 EB-33 02 AD 20 I◄àiδ╠↨£ôO@δ3☻¡ / 50: A4 09 2D 7B-15 FA 20 1D-D1 DB 17 CD-DD 29 59 1E ñ○-{§· ↔╤█↨═▌)Y▲ 60: 39 89 9E F6-79 46 9F E6-8B 85 C5 EF-DE C2 4E 46 9ë₧÷yFƒµïà┼∩▐┬NF 70: C2 78 75 9D-8B 65 F4 50-EA 21 C5 D9-18 62 FF 7B ┬xu¥ïe⌠PΩ!┼┘↑b {

MD5: fe6c446ee3a831ee010f33ac9c1b602c SHA256: e27cf3073c704d0665da42d597d4d20131013204eecb6372a5bd60aeddd5d670

다른 예시(동일한 접두어 사용): [1](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll1.bin) ⟷ [2](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll2.bin)

**변형**: [단일 블록 MD5 충돌](https://marc-stevens.nl/research/md5-1block-collision/)도 있지만 계산에 5주가 걸립니다.

접두어 없이 수행한 FastColl 계산 [녹화](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll.svg)와
접두어를 사용한 [또 다른 녹화](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll-prefix.svg)가 있습니다.


### [UniColl](https://github.com/decalage2/collisions/blob/HEAD/unicoll.md) (MD5)

[2012년](https://www.cwi.nl/system/files/PhD-Thesis-Marc-Stevens-Attacks-on-Hash-Functions-and-Applications.pdf#page=199)에 문서화되었고, [2017년](https://github.com/cr-marcstevens/hashclash/blob/95c2619a8078990056beb7aaa59104021714ee3c/scripts/poc_no.sh)에 구현되었습니다.

[UniColl](https://github.com/cr-marcstevens/hashclash#create-you-own-identical-prefix-collision)을 사용하면 충돌 블록 내의 몇 바이트를 제어할 수 있습니다.
첫 번째 차이 이전과 이후 모두에서 말이죠. 따라서 일부 차이를 제어할 수 있는 identical-prefix 충돌로서, 거의 chosen-prefix 충돌에 가깝습니다.
이는 매우 유용하며, 더욱 좋은 점은 그 차이가 매우 예측 가능하다는 것입니다:
`m2+= 2^8`(일명 HashClash [poc_no.sh](https://github.com/cr-marcstevens/hashclash/blob/master/scripts/poc_no.sh#L30) 스크립트의 `N=1` / `m2 9`)의 경우,
차이는 9번째 바이트에서 +1이므로 매우 악용하기 쉽습니다.
심지어 머릿속으로 충돌을 생각해볼 수도 있습니다:
그 문장의 9번째 문자는 다음 문자로 대체됩니다: `0`은 `1`로, `a`는 `b`로..

- 시간: 몇 분 (제어하려는 바이트 수에 따라 다름)
- 공간: 두 블록
- 차이점:   ```
   .. .. .. .. DD .. .. .. ..
   .. .. .. .. +1 .. .. .. ..

익스플로잇: 매우 쉬움 - 차이 앞뒤의 바이트를 제어할 수 있고 차이는 예측 가능합니다. 유일한 제약은 정렬과 차이 이후 '오직' 10바이트만 제어할 수 있다는 점입니다.

충돌 블록에서 N=1과 20바이트의 고정 텍스트를 사용한 예시:``` 00: 55 6E 69 43-6F 6C 6C 20-31 20 70 72-65 66 69 78 UniColl 1 prefix 10: 20 32 30 62-F5 48 34 B9-3B 1C 01 9F-C8 6B E6 44 20b⌡H4╣;∟☺ƒ╚kµD 20: FE F6 31 3A-63 DB 99 3E-77 4D C7 5A-6E B0 A6 88 ■÷1:c█Ö>wM╟Zn░ªê 30: 04 05 FB 39-33 21 64 BF-0D A4 FE E2-A6 9D 83 36 ♦♣√93!d┐♪ñ■Γª¥â6
40: 4B 14 D7 F2-47 53 84 BA-12 2D 4F BB-83 78 6C 70 K¶╫≥GSä║↕-O╗âxlp 50: C6 EB 21 F2-F6 59 9A 85-14 73 04 DD-57 5F 40 3C ╞δ!≥÷YÜà¶s♦▌W_@< .........X...... 60: E1 3F B0 DB-E8 B4 AA B0-D5 56 22 AF-B9 04 26 FC ß?░█Φ┤¬░╒V"»╣♦&ⁿ ................ 70: 9F D2 0C 00-86 C8 ED DE-85 7F 03 7B-05 28 D7 0F ƒ╥♀ å╚φ▐à⌂♥{♣(╫☼ ................ ................ .........X...... 00: 55 6E 69 43-6F 6C 6C 20-31 21 70 72-65 66 69 78 UniColl 1!prefix ................ 10: 20 32 30 62-F5 48 34 B9-3B 1C 01 9F-C8 6B E6 44 20b⌡H4╣;∟☺ƒ╚kµD ................ 20: FE F6 31 3A-63 DB 99 3E-77 4D C7 5A-6E B0 A6 88 ■÷1:c█Ö>wM╟Zn░ªê ................ 30: 04 05 FB 39-33 21 64 BF-0D A4 FE E2-A6 9D 83 36 ♦♣√93!d┐♪ñ■Γª¥â6 40: 4B 14 D7 F2-47 53 84 BA-12 2C 4F BB-83 78 6C 70 K¶╫≥GSä║↕,O╗âxlp / 50: C6 EB 21 F2-F6 59 9A 85-14 73 04 DD-57 5F 40 3C ╞δ!≥÷YÜà¶s♦▌W_@< 60: E1 3F B0 DB-E8 B4 AA B0-D5 56 22 AF-B9 04 26 FC ß?░█Φ┤¬░╒V"»╣♦&ⁿ 70: 9F D2 0C 00-86 C8 ED DE-85 7F 03 7B-05 28 D7 0F ƒ╥♀ å╚φ▐à⌂♥{♣(╫☼

UniColl은 진정한 chosen-prefix 충돌보다 제어력은 떨어지지만, 특히 두 개의 블록만 사용하므로 훨씬 빠릅니다.

다음은 UniColl 계산의 [녹화](https://github.com/decalage2/collisions/blob/HEAD/examples/unicoll.svg)입니다.


### [Shattered](http://shattered.io) (SHA1)

[2013](https://marc-stevens.nl/research/papers/EC13-S.pdf)에 문서화되었고, [2017](http://shattered.io)에 계산되었습니다.

- 시간: 6500 years.CPU and 110 year.GPU
- 공간: 두 개의 블록
- 차이점:  ```
  .. .. .. DD ?? ?? ?? ??
  or
  ?? ?? ?? DD .. .. .. ..

exploitation: 중간. 차이는 충돌 블록의 시작과 끝에 있습니다. 따라서 접두사/접미사의 길이 앞과 뒤는 제어할 수 없습니다: PNG는 청크 타입 앞에 길이를 저장하므로 작동하지 않습니다. 그러나 JFIF 형식(JPG와 동일)을 사용하는 JP2 파일에서는 작동하며, 64비트에서 긴 길이를 사용하면 MP4 및 기타 atom/box 형식에서도 작동할 가능성이 높습니다 (이 경우, 길이는 atom 타입 뒤에 배치됩니다).

각 측의 충돌 블록 간 차이는 다음과 같은 Xor 마스크입니다:``` 0C 00 00 02 C0 00 00 10 B4 00 00 1C 3C 00 00 04 BC 00 00 1A 20 00 00 10 24 00 00 1C EC 00 00 14 0C 00 00 02 C0 00 00 10 B4 00 00 1C 2C 00 00 04 BC 00 00 18 B0 00 00 10 00 00 00 0C B8 00 00 10



예시: [PoC||GTFO 0x18](https://github.com/angea/pocorgtfo#0x18)은 계산된 SHA1 접두사들을 사용하며, PDFLaTeX 소스에서 이미지를 직접 재사용합니다( [기사 18:10](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up) 참조). 또한 HTML 페이지의 JavaScript를 통해 접두사 값을 확인합니다(이 파일은 ZIP, HTML, PDF의 폴리글롯입니다).


## 선택 접두사 충돌

이를 사용하면 임의의 콘텐츠를 충돌시킬 수 있습니다.

| 𝓐            | ≠ | 𝔅             |
| :----:        |:-:| :----:        |
| 충돌 *A*      | ≠ | 충돌 *B*      |

1. 두 개의 임의 접두사를 가져옵니다.
2. 가장 짧은 것을 가장 긴 것과 같은 길이가 되도록 패딩합니다. 둘 다 다음 블록에서 12바이트를 뺀 크기로 패딩됩니다.
  - 이 12바이트의 무작위 데이터는 생일 탐색을 무작위화하기 위해 양쪽에 추가됩니다.
3. X개의 근접 충돌 블록이 계산되어 추가됩니다.

   블록 수가 적을수록 계산 시간이 길어집니다.

   예: [단일 블록에 400k시간](https://www.win.tue.nl/hashclash/SingleBlock/). HashClash로 9개 블록에 72코어-시간.



선택 접두사 충돌은 매우 강력하지만, 단지 파일 한 쌍에 대해서조차 오랜 시간이 걸릴 수 있습니다.


### [HashClash](https://github.com/cr-marcstevens/hashclash) (MD5)

최종 버전은 [2009년](https://www.win.tue.nl/hashclash/ChosenPrefixCollisions/)입니다.

예: `yes`와 `no`를 충돌시켜 봅시다. 24코어에서 3시간이 걸렸습니다.```
'yes' prefix:
000:  79 65 73 0A-3D 62 84 11-01 75 D3 4D-EB 80 93 DE  yes◙=bä◄☺u╙MδÇô▐   - Prefix, padding
010:  31 C1 D9 30-45 FB BE 1E-71 F0 0A 63-75 A8 30 AA  1┴┘0E√╛▲q≡◙cu¿0¬
020:  98 17 CA E3-A2 6B 8E 3D-44 A9 8F F2-0E 67 96 48  ÿ↨╩πókÄ=D⌐Å≥♫gûH
030:  97 25 A6 FB-00 00 00 00-49 08 09 33-F0 62 C4 E8  ù%ª√    I◘○3≡b─Φ

040:  D5 F1 54 CD-CA A1 42 90-7F 9D 3D 9A-67 C4 1B 0F  ╒±T═╩íBÉ⌂¥=Üg─←☼  - Collision blocks start
050:  04 9F 19 E8-92 C3 AA 19-43 31 1A DB-DA 96 01 54  ♦ƒ↓ΦÆ├¬↓C1→█┌û☺T
060:  85 B5 9A 88-D8 A5 0E FB-CD 66 9A DA-4F 20 8A AA  à╡Üê╪Ñ♫√═fÜ┌O è¬
070:  BA E3 9C F0-78 31 8F D1-14 5F 3E B9-0F 9F 3E 19  ║π£≡x1Å╤¶_>╣☼ƒ>↓

080:  09 9C BB A9-45 89 BA A8-03 E6 C0 31-A0 54 D6 26  ○£╗⌐Eë║¿♥µ└1áT╓&
090:  3F 80 4C 06-0F C7 D9 19-09 D3 DA 14-FD CB 39 84  ?ÇL♠☼╟┘↓○╙┌¶²╦9ä
0A0:  1F 0D 77 5F-55 AA 7A 07-4C 24 8B 13-0A 54 A2 BC  ▼♪w_U¬z•L$ï‼◙Tó╝
0B0:  C5 12 7D 4F-E0 5E F2 23-C5 07 61 E4-80 91 B2 13  ┼↕}Oα^≥#┼•aΣÇæ▓‼

0C0:  E7 79 07 2A-CF 1B 66 39-8C F0 8E 7E-75 25 22 1D  τy•*╧←f9î≡Ä~u%"↔
0D0:  A7 3B 49 4A-32 A4 3A 07-61 26 64 EA-6B 83 A2 8D  º;IJ2ñ:•a&dΩkâóì
0E0:  BE A3 FF BE-4E 71 AE 18-E2 D0 86 4F-20 00 30 26  ╛ú ╛Nq«↑Γ╨åO  0&
0F0:  0A 71 DE 1F-40 B4 F4 8F-9C 50 5C 78-DD CD 72 89  ◙q▐▼@┤⌠Å£P\x▌═rë

100:  BA D1 BF F9-96 80 E3 06-96 F3 B9 7C-77 2D EB 25  ║╤┐∙ûÇπ♠û≤╣|w-δ%
110:  1E 56 70 D7-14 1F 55 4D-EC 11 58 59-92 45 E1 33  ▲Vp╫¶▼UM∞◄XYÆEß3
120:  3E 0E A1 6E-FF D9 90 AD-F6 A0 AD 0E-C6 D6 88 12  >♫ín ┘É¡÷á¡♫╞╓ê↕
130:  B8 74 F2 9E-DD 53 F7 88-19 73 85 39-AA 9B E0 8D  ╕t≥₧▌S≈ê↓sà9¬¢αì
                                                                          \
140:  82 BF 9C 5E-58 42 1E 3B-94 CF 5B 54-73 5F A8 4A  é┐£^XB▲;ö╧[Ts_¿J
150:  FD 5B 64 CF-59 D1 96 74-14 B3 0C AF-11 1C F9 47  ²[d╧Y╤ût¶│♀»◄∟∙G      ................
160:  C5 7A 2C F7-D5 24 F5 EB-BE 54 3E 12-B0 24 67 3F  ┼z,≈╒$⌡δ╛T>↕░$g?      ................
170:  01 DD 95 76-8D 0D 58 FB-50 23 70 3A-BD ED BE AC  ☺▌òvì♪X√P#p:╜φ╛¼      ...............X
                                                                             ................
180:  B8 32 DB AE-E8 DC 3A 83-7A C8 D5 0F-08 90 1D 99  ╕2█«Φ▄:âz╚╒☼◘É↔Ö
190:  2D 7D 17 34-4E A8 21 98-61 1A 65 DA-FC 9B A4 BA  -}↨4N¿!ÿa→e┌ⁿ¢ñ║      ................
1A0:  E1 42 2B 86-0C 94 2A F6-D6 A4 81 B5-2B 0B E9 37  ßB+å♀ö*÷╓ñü╡+♂Θ7      ................
1B0:  44 D2 E4 23-14 7C 16 B8-84 90 8B E0-A1 A7 BD 27  D╥Σ#¶|▬╕äÉïαíº╜'      ..............X.
                                                                             ................
1C0:  C7 7E E6 17-1A 93 C5 EE-59 70 91 26-4E 9D C7 7C  ╟~µ↨→ô┼εYpæ&N¥╟|
1D0:  1D 3D AB F1-B4 F4 F1 D9-86 48 75 77-6E FE 98 84  ↔=½±┤⌠±┘åHuwn■ÿä      ................
1E0:  EF 3C 1C C7-16 5A 1F 83-60 EC 5C FE-CA 17 0C 74  ∩<∟╟▬Z▼â`∞\■╩↨♀t      ................
1F0:  EB 8E 9D F6-90 A3 CD 08-65 D5 5A 4C-2E C6 BE 54  δÄ¥÷Éú═◘e╒ZL.╞╛T      ...............X
                                                                             ................

'no' prefix:                                                                 ................
000:  6E 6F 0A E5-5F D0 83 01-9B 4D 55 06-61 AB 88 11  no◙σ_╨â☺¢MU♠a½ê◄      ................
010:  8A FA 4D 34-B3 75 59 46-56 97 EF 6C-4A 07 90 CC  è·M4│uYFVù∩lJ•É╠      ............X...
020:  FE 19 D7 CF-6F 92 03 9C-91 AA A5 DA-56 92 C1 04  ■↓╫╧oÆ♥£æ¬Ñ┌VÆ┴♦      ................
030:  E6 4C 08 A3-00 00 00 00-8D B6 4E 47-FF AF 7A 3C  µL◘ú    ì╢NG »z<
                                                                             ................
040:  D5 F1 54 CD-CA A1 42 90-7F 9D 3D 9A-67 C4 1B 0F  ╒±T═╩íBÉ⌂¥=Üg─←☼      ................
050:  04 9F 19 E8-92 C3 AA 19-43 31 1A DB-DA 96 01 54  ♦ƒ↓ΦÆ├¬↓C1→█┌û☺T      ............X...
060:  85 B5 9A 88-D8 A5 0E FB-CD 66 9A DA-4F 20 8A A9  à╡Üê╪Ñ♫√═fÜ┌O è⌐      ................
070:  BA E3 9C F0-78 31 8F D1-14 5F 3E B9-0F 9F 3E 19  ║π£≡x1Å╤¶_>╣☼ƒ>↓
                                                                             ................
080:  09 9C BB A9-45 89 BA A8-03 E6 C0 31-A0 54 D6 26  ○£╗⌐Eë║¿♥µ└1áT╓&      ................
090:  3F 80 4C 06-0F C7 D9 19-09 D3 DA 14-FD CB 39 84  ?ÇL♠☼╟┘↓○╙┌¶²╦9ä      .............X..
0A0:  1F 0D 77 5F-55 AA 7A 07-4C 24 8B 13-0A 54 B2 BC  ▼♪w_U¬z•L$ï‼◙T▓╝      ................
0B0:  C5 12 7D 4F-E0 5E F2 23-C5 07 61 E4-80 91 B2 13  ┼↕}Oα^≥#┼•aΣÇæ▓‼
                                                                             ................
0C0:  E7 79 07 2A-CF 1B 66 39-8C F0 8E 7E-75 25 22 1D  τy•*╧←f9î≡Ä~u%"↔      ................
0D0:  A7 3B 49 4A-32 A4 3A 07-61 26 64 EA-6B 83 A2 8D  º;IJ2ñ:•a&dΩkâóì      ...............X
0E0:  BE A3 FF BE-4E 71 AE 18-E2 D0 86 4F-20 00 30 22  ╛ú ╛Nq«↑Γ╨åO  0"      ................
0F0:  0A 71 DE 1F-40 B4 F4 8F-9C 50 5C 78-DD CD 72 89  ◙q▐▼@┤⌠Å£P\x▌═rë
                                                                           /
100:  BA D1 BF F9-96 80 E3 06-96 F3 B9 7C-77 2D EB 25  ║╤┐∙ûÇπ♠û≤╣|w-δ%
110:  1E 56 70 D7-14 1F 55 4D-EC 11 58 59-92 45 E1 33  ▲Vp╫¶▼UM∞◄XYÆEß3
120:  3E 0E A1 6E-FF D9 90 AD-F6 A0 AD 0E-CA D6 88 12  >♫ín ┘É¡÷á¡♫╩╓ê↕
130:  B8 74 F2 9E-DD 53 F7 88-19 73 85 39-AA 9B E0 8D  ╕t≥₧▌S≈ê↓sà9¬¢αì

140:  82 BF 9C 5E-58 42 1E 3B-94 CF 5B 54-73 5F A8 4A  é┐£^XB▲;ö╧[Ts_¿J
150:  FD 5B 64 CF-59 D1 96 74-14 B3 0C AF-11 1C F9 47  ²[d╧Y╤ût¶│♀»◄∟∙G
160:  C5 7A 2C F7-D5 24 F5 EB-BE 54 3E 12-70 24 67 3F  ┼z,≈╒$⌡δ╛T>↕p$g?
170:  01 DD 95 76-8D 0D 58 FB-50 23 70 3A-BD ED BE AC  ☺▌òvì♪X√P#p:╜φ╛¼

180:  B8 32 DB AE-E8 DC 3A 83-7A C8 D5 0F-08 90 1D 99  ╕2█«Φ▄:âz╚╒☼◘É↔Ö
190:  2D 7D 17 34-4E A8 21 98-61 1A 65 DA-FC 9B A4 BA  -}↨4N¿!ÿa→e┌ⁿ¢ñ║
1A0:  E1 42 2B 86-0C 94 2A F6-D6 A4 81 B5-2B 2B E9 37  ßB+å♀ö*÷╓ñü╡++Θ7
1B0:  44 D2 E4 23-14 7C 16 B8-84 90 8B E0-A1 A7 BD 27  D╥Σ#¶|▬╕äÉïαíº╜'

1C0:  C7 7E E6 17-1A 93 C5 EE-59 70 91 26-4E 9D C7 7C  ╟~µ↨→ô┼εYpæ&N¥╟|
1D0:  1D 3D AB F1-B4 F4 F1 D9-86 48 75 77-6E FE 98 84  ↔=½±┤⌠±┘åHuwn■ÿä
1E0:  EF 3C 1C C7-16 5A 1F 83-60 EC 5C FE-CA 17 0C 54  ∩<∟╟▬Z▼â`∞\■╩↨♀T
1F0:  EB 8E 9D F6-90 A3 CD 08-65 D5 5A 4C-2E C6 BE 54  δÄ¥÷Éú═◘e╒ZL.╞╛T

전체 작업의 로그는 여기 있습니다.

Shambles (SHA-1)

Shambles는 9개의 블록을 사용하는 매우 비용이 많이 드는 chosen-prefix 충돌입니다.

각 블록은 Shattered와 동일한 xor 패턴을 가집니다.``` 0C 00 00 02 C0 00 00 10 B4 00 00 1C 3C 00 00 04 BC 00 00 1A 20 00 00 10 24 00 00 1C EC 00 00 14 0C 00 00 02 C0 00 00 10 B4 00 00 1C 2C 00 00 04 BC 00 00 18 B0 00 00 10 00 00 00 0C B8 00 00 10

## 공격 요약

해시 | 이름      | 날짜 | 기간 | 접두어 유형 | 근접 차이 제어
---- | --------- | ---- | -------- | ----------- | -----------------
MD5  | FastColl  | 2009 | 2초       | 동일   | 없음
     | UniColl   | 2012 | 7-40분  | 동일   | 4-10바이트
     | HashClash | 2009 | 72시간      | 선택      | n/a
     |           |      |          |             |
SHA1 | Shattered | 2013 | 6500년   | 동일   | 접두어 및 접미어
     | Shambles  | 2020 | ?        | 선택      | n/a

# 악용

동일 접두어 충돌은 일반적으로 (매우) 제한적인 것으로 간주되지만, 선택 접두어는 시간이 많이 소요됩니다.

또 다른 접근 방식은 UniColl과 같은 동일 접두어 공격이나 일부 제한을 극복하기 위한 선택 접두어 공격을 통해 재사용 가능한 접두어를 만든 다음, 고전적인 동일 접두어 공격처럼 두 페이로드와 함께 그 접두어 쌍을 재사용하는 것입니다.

접두어 쌍이 계산되면 두 콘텐츠를 충돌시키는 것은 즉각적입니다.
특정 파일 형식에 따라 파일 데이터를 조정하여 파일 형식 사양과 사전 계산된 접두어 요구 사항에 맞추기만 하면 됩니다.

## 표준 전략

동일한 파일 형식을 가진 두 개의 유효한 파일 간의 고전적인 충돌입니다.

### JPG



이론적 제한 및 해결 방법:
- *Application* 세그먼트는 이론적으로 *Start of Image* 마커 바로 뒤에 있어야 합니다.
  실제로는 그럴 필요가 없으므로 충돌을 일반적으로 만들 수 있습니다. 유일한 제한은 가장 작은 이미지의 크기입니다.
- 주석의 길이는 2바이트로 저장되므로 저장할 수 있는 양은 65536바이트로 제한됩니다(대략 400x400 사진 크기).
- 전체 JPG 파일을 건너뛰는 대신 파일을 세그먼트로 분할하고 세그먼트 사이에 점프 트램펄린을 추가할 수 있습니다.

  

  *각 이미지 세그먼트 위의 주석*

  

  *주석 트램펄린이 작동하는 방식*

- JPG 구조의 대부분은 모두 65536바이트로 제한된 세그먼트로 이루어져 있지만,
실제 압축 데이터는 그러한 제한을 따르지 않는 *Entropy Coded Segment*에 저장됩니다.
그 크기는 사전에 알 수 없으며 그 한도를 넘어 계속 커집니다.
이미지 크기에 따라 커지므로 베이스라인(비프로그레시브) 이미지에서 파일 크기의 대부분을 차지합니다.
전체 이미지를 64kb 청크에 맞추는 쉬운 방법은 먼저 이미지를 프로그레시브로 저장하는 것입니다(어떤 소프트웨어로도 가능하며 ECS를 일반적으로 최대 6개의 스캔으로 분할합니다). 더 고급 방법은 *JPEGTran*의 'wizard' `--scans` 명령줄 매개변수를 사용해 사용자 지정 스캔을 정의하는 것입니다.

스캔 세그먼트 외에는 다른 제한이 없으므로,
두 개의 임의 JPG에 대한 MD5 충돌은 *즉시* 가능하며 선택 접두어 충돌이 필요하지 않고 UniColl만 있으면 됩니다.

다음 [스크립트](https://github.com/decalage2/collisions/blob/HEAD/scripts/jpg.py)를 사용합니다:```
21:07:35.65>jpg.py Ange.jpg Marc.jpg

21:07:35.75>

Examples:

⟷

커스텀 스캔

MD5 충돌 JPG 2개

다음은 1944x2508 RGB 이미지를 20개의 스캔이 모두 64kb에 들어맞는 100% JPG로 변환하기 위한 JPEGTran 스캔 정의의 예입니다.``` // : -, , ;

// 0=luma 0: 0-0, 0, 0; 0: 1-1, 0, 0; 0: 2-6, 0, 0; 0: 7-10, 0, 0; 0: 11-13, 0, 0; 0: 14-20, 0, 0; 0: 21-26, 0, 0; 0: 27-32, 0, 0; 0: 33-40, 0, 0; 0: 41-48, 0, 0; 0: 49-54, 0, 0; 0: 55-63, 0, 0;

// 1=blueness 1: 0-0, 0, 0; 1: 1-16, 0, 0; 1: 17-32, 0, 0; 1: 33-63, 0, 0;

// 2=redness 2: 0-0, 0, 0; 2: 1-16, 0, 0; 2: 17-32, 0, 0; 2: 33-63, 0, 0;

결과:



*20회 스캔으로 저장된 1944x2508 RGB 이미지(100% JPG)*


### PNG



이론적 제한 사항 및 해결 방법:
- PNG는 청크 끝에 CRC32를 사용하지만 실제로는 무시된다. 정확하더라도 필수는 아니다.
- 이미지 메타데이터(크기, 색 공간 등)는 `IHDR` 청크에 저장되며,
  이 청크는 이론상 서명 바로 뒤(즉, 잠재적 주석이 있기 전)에 있어야 하므로,
  같은 메타데이터를 가진 이미지 간의 충돌만 미리 계산할 수 있음을 의미한다.
  그러나 실제로는 (Apple 제외 대부분의 리더에서) 해당 청크가 주석 블록 뒤에 올 수 있으므로, 헤더 앞에 충돌 데이터를 배치할 수 있다.
  이를 통해 단 한 번의 사전 계산으로 임의의 PNG 쌍을 충돌시킬 수 있다.

PNG 청크는 4바이트 길이를 가지므로, 두 파일 중 어느 하나의 구조도 수정할 필요가 없다. 한 번에 전체 이미지를 건너뛸 수 있다.

우리는 원하는 만큼 많은 무시되는 청크를 삽입할 수 있다. 따라서 정렬용으로 하나를 추가한 다음, UniColl에 의해 길이가 변경될 청크를 하나 더 추가할 수 있다. 그러면 길이는 `00` `75`와 `01` `75`가 된다.

따라서 임의의 두 PNG 이미지에 대한 MD5 충돌은 *즉시* 발생한다. 사전 조건이 전혀 없으며(계산이 필요 없고 단지 약간의 파일 변경만 있으면 된다), chosen-prefix collision도 필요 없고 UniColl만 있으면 된다.

[스크립트](https://github.com/decalage2/collisions/blob/HEAD/scripts/png.py)를 사용하면:```
19:27:04.79>png.py nintendo.png sega.png

19:27:04.87>

예시:

⟷

서로 다른 속성을 가진 MD5 충돌 PNG 2개

전체 작업 과정의 녹화 영상입니다.

보편적(악용적) PNG 충돌의 녹화 영상

비호환성

대부분의 리더는 IHDR이 아닌 청크로 시작하는 PNG 파일을 무리 없이 허용합니다.

하지만 일부(Safari나 Preview 등 - 또 있나요?)는 이를 허용하지 않습니다. 이 경우 이미지 헤더와 그 속성(크기, 색 공간)이 충돌 블록보다 먼저 와야 합니다.

이 경우 두 충돌 파일은 동일한 속성을 가져야 합니다. 역시 UniColl이면 충분하며, 물론 계산된 접두사 쌍은 동일한 속성을 가진 다른 어떤 파일 쌍에도 재사용할 수 있습니다.

필요하면 UniColl을 실행해 접두사 쌍을 계산하는, 그러한 파일 쌍을 충돌시키는 스크립트가 여기 있습니다.

예시:

⟷

최대 호환성을 위해 동일한 속성을 가진 MD5 충돌 PNG 2쌍

다음은 UniColl이 호출될 때 전체 작업의 녹화 영상이며,

PNG UniColl 충돌 녹화 영상

접두사가 이미 계산된 경우의 또 다른 영상입니다.

미리 계산된 PNG 충돌 녹화 영상

GIF

GIF는 까다로운 형식입니다:

주석(comment)이 가능하기 전에 헤더에 메타데이터를 저장하므로, 모든 GIF 파일에 대한 범용 접두사는 있을 수 없습니다.
파일에 전역 팔레트가 있으면 그것도 주석이 가능하기 전에 저장됩니다.
주석 청크의 길이가 1바이트로 제한되어 있어 최대 256바이트뿐입니다!

하지만 주석 청크는 독특한 구조를 따릅니다: null 길이가 정의될 때까지 <length:1> <data:length>의 체인입니다. 그래서 null이 아닌 모든 바이트가 유효한 '앞으로 점프'가 됩니다. 따라서 PoC||GTFO 14:11에서 보여주는 것처럼 FastColl과 함께 사용하기에 적합합니다.

그래서 최소한, 범용 접두사는 만들 수 없어도 동일한 메타데이터(크기, 팔레트)를 가진 GIF 쌍은 충돌시킬 수 있으며, 접두사 계산에는 FastColl이 1초면 충분합니다.

문제는 PNG처럼 이미지 전체를 뛰어넘거나 JPG처럼 큰 구조를 뛰어넘을 수 없다는 점입니다.

가능한 우회 방법으로는 압축 데이터를 가공하거나 GIF hashquine의 경우처럼 이미지를 아주 작은 영역들로 나누는 방법이 있지만, 최적의 방법은 아닙니다.

일반적으로 동작하는 또 다른 아이디어는 이미지 데이터도 이 length data 시퀀스 구조로 저장된다는 점을 이용하는 것입니다: 애니메이션이 없는 GIF 두 개를 선택했다면 다음만 하면 됩니다:

팔레트를 정규화합니다
첫 번째 프레임의 지속 시간을 최대로 설정합니다
첫 번째 프레임 데이터의 시작 위치로 점프하는 주석을 만들어, 주석이 이미지 데이터를 주석처럼 미끄러져 지나가고 같은 방식으로 끝나게 합니다: null 길이를 만날 때까지입니다. 그러면 파서가 다음 프레임을 만나 그것을 표시합니다.

약간의 준비(수백 바이트의 오버헤드만)만으로 어떤 GIF 이미지든 미끄러져 지나가 256바이트 제한을 우회할 수 있습니다. 이 아이디어는 Marc가 제안했는데, 정말 훌륭합니다!

결국 현재 GIF에서 즉시 MD5 충돌을 만들기 위한 제약은 다음과 같습니다:

애니메이션이 없을 것
이미지가 동일한 팔레트로 정규화되어야 함 - gifsicle --use-colormap web 참고
이미지의 크기가 동일해야 함
11분 후에는 두 파일 모두 같은 이미지를 표시합니다

정지 GIF 이미지를 정규화하는 간편한 지름길은 그것들을 하나의 같은 GIF의 애니메이션 프레임으로 만드는 것입니다. 그런 다음 스크립트를 사용해 FastColl 블록을 재사용하거나 계산하여 각각의 이미지를 표시하는 파일 쌍을 만들 수 있습니다.

예시:

⟷

MD5 충돌 GIF 2개 - 이미지 출처: KidMoGraph

전체 작업 과정의 녹화 영상입니다.

GIF FastColl 충돌 녹화 영상

GZIP

GZIP 사양 v4.3: RFC 1952 (1996).

Gzip 파일은 하나 이상의 '멤버'(gzip 스트림)가 연결된 것입니다. 모든 멤버는 압축 해제되며 그 압축 해제된 내용이 서로 이어붙여집니다 - 멤버의 압축 해제 내용이 비어 있어도 마찬가지입니다.
이 멤버들은 0으로 구분할 수 있습니다. 0은 파일 시작 부분을 제외하고는 그냥 건너뜁니다. null이 아닌 모든 바이트는 시그니처 1F 8B와 대조됩니다. 시그니처가 일치하지 않으면 파싱이 중지되는데, 이를 이용해 두 페이로드 사이에서 파싱을 강제로 멈출 수 있지만 문제를 일으킬 수 있는 경고가 발생합니다. 또 다른 전략은 파일 끝에 빈 멤버를 하나 더 추가해서 두 페이로드의 파싱이 그 멤버 또는 그 본문에서 끝나게 하는 것입니다.
선택적인 filename과 file comment는 null로 종료되는 반면, Extra field는 16비트 크기로 정의되어 있어 악용할 수 있습니다. Extra field는 ID와 자체 하위 길이를 가진 하나 이상의 하위 필드(subfield)로 구성되지만, 하위 필드는 강제되지 않습니다 - 공식적으로 정의된 것은 극히 일부뿐입니다.

따라서 extra field가 있는 빈 gzip 멤버는 완벽한 기생 숙주입니다.

상단 파일이 extra field에 들어가기 너무 크면, 압축 해제된 스트림을 더 작은 파일들로 나눠 모두 extra field에 들어갈 수 있게 할 수 있습니다.

멤버의 헤더 뒤에는 압축된 본문, CRC32, 압축 해제된 크기(강제되지 않음)가 옵니다. 따라서 CRC32와 크기가 null인 빈 데이터 본문은 범용 postwrap이 되며, 서로 다른 멤버 헤더끼리 공유할 수도 있습니다.

여러 구현체는 모든 멤버의 합 대신 마지막 멤버의 압축 해제 크기에 의존합니다. 그래서 우리의 충돌 파일들은 크기가 null인 것처럼 보이는데, 이는 이러한 파일들이 트램펄린 역할을 하는 빈 멤버로 끝나기 때문입니다.

두 GZip 파일의 즉시 MD5 충돌을 생성하는 스크립트가 여기 있습니다. 입력 파일이 크면 대부분의 시간을 데이터 압축 해제 및 재압축에 사용합니다 - 충돌 접두사는 미리 계산되어 있습니다. 압축 해제된 CRC32를 계산해야 하므로 압축을 풀지 않고 멤버를 나누는 것은 불가능합니다.

.tar.gz는 tar 아카이브를 gzip으로 압축한 것일 뿐입니다. tar 자체와 달리, gzip으로 압축된 tar에서는 잘 작동합니다.

예시: collision1.tar.gz (Pacome) ⟷ collision2.tar.gz (Reg)

Portable Executable

Portable Executable은 독특한 구조를 가지고 있습니다:

기존 DOS 헤더는 거의 쓸모가 없으며, 다음 구조인 PE 헤더를 가리킵니다. DOS 헤더에는 그 외 다른 역할이 없습니다. DOS 헤더는 실행 파일 간에 교환할 수 있습니다.
DOS 헤더는 오프셋 0에 있어야 하고 전체 블록의 고정 길이를 가지며, 포인터는 구조의 끝에 있어 UniColl의 도달 범위를 벗어납니다: 따라서 이런 방식으로 PE 파일을 충돌시키려면 chosen-prefix 충돌만 유용합니다.
PE 헤더와 그 뒤의 내용이 파일 전체를 정의합니다.

따라서 전략은 다음과 같습니다:

PE 헤더를 아래로 이동해서 DOS 헤더 뒤에 충돌 블록을 위한 공간을 확보합니다.
DOS 헤더를(chosen-prefix 충돌을 통해) 악용해서 서로 다른 두 오프셋을 가리키게 하고, 그 위치에 서로 다른 두 PE 헤더를 이동시켜 놓습니다.
섹션들은 DOS/Collisions/Header1/Header2 구조 뒤에 서로 이어서 배치할 수 있습니다. 두 섹션 테이블의 오프셋에 델타를 적용하기만 하면 됩니다.

즉, 어떤 PE 실행 파일 쌍이든 즉시 충돌시키는 것이 가능합니다. 서로 다른 서브시스템이나 아키텍처를 사용하더라도 말입니다.

실행 파일 충돌은 보통 어떤 로더를 통해서든 사소하게 만들 수 있지만, 여기서의 이런 공격 방식은 투명합니다: 코드가 동일하고 같은 주소에 로드되기 때문입니다.

예시: tweakPNG.exe (GUI) ⟷ fastcoll.exe (CLI)

Windows 실행 파일의 즉시 MD5 충돌을 생성하는 스크립트가 여기 있습니다.

MP4 및 기타

이 형식의 컨테이너는 Atoms라고 불리는 Length Type Value 청크의 연속입니다. length는 32비트 빅엔디안이며 자기 자신, type, value를 포함하므로 정상적인 최소 길이는 8입니다 (type은 4개의 ASCII 문자로 된 문자열입니다).

length가 null이면 그 atom은 파일의 나머지 부분을 차지합니다 - JP2 파일의 jp2c atom처럼요. length가 1이면 Type 뒤에 64비트 길이가 이어져 atom이 Type Length Value로 바뀌면서, Shattered 같은 다른 충돌과도 호환됩니다.

일부 atom은 다른 atom을 포함합니다: 이런 경우 box라고 부릅니다. 그래서 이렇게 달리 이름이 없는 구조를 "atom/box"라고 합니다.

MP4에서 사용되는 이 "atom/box" 형식은 사실 Apple Quicktime에서 파생된 것이며, 다른 많은 형식들 (JP2, HEIF, F4V)에서도 사용됩니다.

첫 번째 atom type은 대개 ftyp이며, 이를 통해 실제 파일 형식을 구분할 수 있습니다.

이 형식은 상당히 관대합니다: free atom들을 연결하고, UniColl로 그중 하나의 길이를 악용한 다음, 첫 번째 페이로드를 뛰어넘으면 됩니다.

MP4 파일의 경우, 추가로 해야 할 일은 stco(Sample Table - Chunk Offsets) 또는 co64(64비트 버전) 테이블을 조정하는 것뿐입니다. 이들은 mdat 동영상 데이터를 가리키는 절대(!) 오프셋이며, 실제로 강제되기 때문입니다!

이를 통해 임의의 비디오를 즉시 충돌시키는 스크립트가 만들어집니다. 그리고 언급했듯이 MP4 외의 다른 형식에서도 작동할 수 있습니다.

Nirvana - Smells like Teen Spirit / Weird Al Yankovik - Smells like Nirvana

예시 (동영상 출처: KidMoGraph):

32비트 길이(표준) collision1.mp4 ⟷ collision2.mp4

⟷
64비트 길이 collisionl1.mp4 ⟷ collisionl2.mp4

⟷

일부 뷰어(OS X, Safari, FireFox)는 ftyp이 아닌 Atom으로 시작하는 파일을 허용하지 않는다는 점에 유의하세요. 이 경우 접두사가 이를 처리해야 하므로 그렇게 범용적이지는 않지만, 그 외에는 동일한 전략입니다 - 단지 단일 파일 형식으로 제한될 뿐입니다.

JPEG2000

JPEG2000 파일은 보통 MP4처럼 Atom/Box 구조로 시작하고, 마지막 atom jp2c는 일반적으로 파일 끝까지(null 길이) 이어지며, 그 지점부터는 JPEG처럼 JFIF 구조를 따릅니다(세그먼트 마커로 FF 4F로 시작).

순수 JFIF 형식도 허용되는데, 이 경우 충돌은 JPEG과 같습니다: Shattered와 호환되지만 주석이 64Kb로 제한됩니다.

반면, Atom/Box 구조로 JPEG2000 파일을 조작하면 이런 제한이 없습니다.

앞서 언급했듯이, 이 구조를 충돌시키려 하는데 더 많은 제약이 있다면 - 예를 들어 일부 형식은 free atom으로 시작하는 것을 허용하지 않습니다 - 이 형식에 특화된 또 다른 UniColl 접두사 쌍을 계산하면 됩니다: JPEG2000은 일반적인 ftyp 앞에 'jP ' atom을 먼저 강제하는 것 같지만, 그 외에는 그것이 유일한 제약입니다: 아무것도 재배치할 필요가 없습니다.

그래서 결과물인 스크립트는 훨씬 더 단순합니다!

Oded Goldreich / Neal Koblitz

예시: collision1.jp2 ⟷ collision2.jp2

PDF

Shattered에 대하여

Shattered 공격은 PDF 트릭이 아니라, PDF 안에서의 JPG 트릭이었습니다.

이는 단지 PDF가 서로 다른 두 내용을 가질 수 있는 JPG 압축 객체를 포함할 수 있게 했을 뿐입니다. 두 PDF는 그 외에는 완전히 동일해야 했습니다.

문서 자체는 완전히 정상일 수 있고, 충돌 JPG를 잘라내어 다중 페이지 문서 같은 서로 다른 위치에 표시할 수 있다는 점에 유의하세요.

예시: The Shattered 논문, 수정본 ⟷ The Shattered 논문, 원본

두 위치에 충돌 JPG를 사용한 The Shattered 논문

MD5를 이용한 PDF 충돌

MD5(및 기타 충돌 패턴)를 사용하면 문서 수준에서 PDF 충돌을 만들 수 있으며, 어느 쪽 파일에도 전혀 제약이 없습니다!

PDF는 다른 파일 형식과는 매우 다른 구조를 가지고 있습니다. 객체 번호와 참조를 사용해 트리를 정의합니다. 전체 문서는 Root 요소에 의존합니다.

이 (유효한) PDF``` text %PDF-1. 1 0 obj<</Pages 2 0 R>>endobj 2 0 obj<</Kids[3 0 R]/Count 1>>endobj 3 0 obj<</Parent 2 0 R>>endobj trailer <</Root 1 0 R>>

다음과 동일합니다:``` text
%PDF-1.
11 0 obj<</Pages 12 0 R>>endobj
12 0 obj<</Kids[13 0 R]/Count 1>>endobj
13 0 obj<</Parent 12 0 R>>endobj
trailer <</Root 11 0 R>>

요령:

PDF에 사용하지 않는 객체를 저장하는 것은 허용됩니다.
객체 번호를 건너뛰는 것도 괜찮습니다. XREF 테이블에서 번호를 건너뛰는 공식적인 방법도 있습니다.

따라서 한 파일에 두 개의 문서 트리를 저장하는 것도 괜찮습니다. 루트 객체가 두 문서 중 하나의 루트 객체를 참조하게 만들기만 하면 됩니다.

그러므로 우리는 두 문서를 가져와, 겹치지 않도록 객체와 참조 번호를 다시 매기고, 해시 값을 유지하면서 Root 객체로 참조되는 객체 번호를 변경할 수 있는 충돌을 만들고, 이는 N=1인 UniColl에 완벽하게 들어맞으며, 그에 맞게 XREF 테이블을 조정하면 됩니다.

이런 방식으로 페이지 수, 크기, 이미지 등에 관계없이 어떤 PDF 쌍이든 안전하게 충돌시킬 수 있습니다.

주석

PDF는 외부 데이터를 두 가지 방식으로 저장할 수 있습니다:

줄 주석으로, 이때 금지되는 문자는 줄바꿈(\r 및 \n)뿐입니다. 예를 들어 사전 객체 내부에서 UniColl을 통해 객체 참조를 수정하는 데 사용할 수 있습니다. 따라서 이진 충돌 블록이 포함되어 있어도 유효한 PDF 객체입니다. 줄바꿈 문자가 없을 때까지 다시 시도하세요: ``` 1 0 obj << /Type /Catalog /MD5_is /REALLY_dead_now__ /Pages 2 0 R %¥┬•σe╕█╙X₧_~π▌╒εX∟■φe♦%τ8╞■[...]p╛╬ûFZ»‼v◘Åp↑╝%▓% ▼σφj╔◄dZ▀c²aU≤╨╩[├└─yNΓ5╔+▀╪yδ☻ß⌐░¼à(☺z₧

endobj
스트림 객체로서의 경우에는 어떤 데이터도 가능하지만, 객체 내부에 있기 때문에 전체 PDF 구조를 변경할 수 없으므로, 포함하는 스트림 객체 외부의 구조를 수정하려면 선택-접두사 충돌(chosen-prefix collision)이 필요합니다.

충돌 텍스트

첫 번째 경우는 차이를 예측할 수 있는 충돌인 UniColl의 장점을 부각할 수 있게 해줍니다. 충돌하는 데이터 위에 시를 쓸 수 있습니다 - Jurph님께 감사드립니다!

문서의 구조를 수정하고 파서를 속이는 대신, 충돌 블록을 직접 사용하여 대체 해석이 가능한 텍스트를 만들어냅니다!``` V V Now he hash MD5, Now he hath MD5, No enemy cares! No enemy dares! Only he gave Only he have the shards. the shares. Can’t be owned & Can’t be pwned & his true gold, his true hold, like One Frail, like One Grail, sound as fold. sound as gold. ^ ^

예제: [poeMD5 A](https://github.com/decalage2/collisions/blob/HEAD/examples/poeMD5_A.pdf) ⟷ [poeMD5 B](https://github.com/decalage2/collisions/blob/HEAD/examples/poeMD5_B.pdf)



*진정한 암호학적 예술 작품 :)*

(참고: Adobe 호환성을 망친 것은 내 실수이지 UniColl의 잘못이 아닙니다)


**충돌하는 문서 구조**

UniColl을 인라인 주석으로 사용하든 더미 스트림 객체의 chosen-prefix로 사용하든, 전략은 비슷합니다:
객체 번호를 뒤섞은 다음 Root 객체가 서로 다른 객체를 가리키게 만드는 것입니다. 따라서 Shattered와 달리, 이는 문서 수준에서 임의의 PDF 쌍의 즉각적인 충돌을 의미합니다.

유용한 요령 중 하나는 [`mutool clean`](https://mupdf.com/docs/manual-mutool-clean.html) 출력이 확실하게 예측 가능하다는 것입니다.
따라서 이를 사용해 입력 PDF를 정규화하고, 파일에서 중요한 부분은 수정하지 않은 채 병합된 PDF를 고칠 수 있습니다.
MuTool은 요청하지 않는 한 가짜 키/값을 버리지 않고 같은 순서로 유지하므로, `/MD5_is /REALLY_dead_now__` 같은 가짜 사전 항목을 사용하면 다른 종류의 주석 없이도 항목을 예측 가능하게 정렬하는 데 완벽합니다.
하지만 사전의 주석은 유지하지 않습니다(인라인 주석 트릭은 불가능합니다).

객체 셔플링 작업을 번거로움 없이 수행하는 쉬운 방법은 두 PDF 파일을
`mutool merge`로 병합한 다음 `/Pages` 객체를 둘로 나누는 것입니다.

이 객체를 위한 공간을 만들려면 두 문서 앞에 더미 PDF를 병합하기만 하면 됩니다.

선택적으로, 가비지 컬렉션이 두 번째 페이지 집합을 삭제하지 못하도록 매달린 배열에 대한 가짜 참조를 만들 수 있습니다.


**예제**:
이 [스크립트](https://github.com/decalage2/collisions/blob/HEAD/scripts/pdf.py)를 사용하면 Spectre와 Meltdown 같은 두 공개 PDF 논문을 충돌시키는 데 [1초 미만](https://github.com/decalage2/collisions/blob/HEAD/examples/pdf.log)이 걸립니다:

예제: [spectre.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/collision1.pdf) ⟷ [meltdown.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/collision2.pdf)



가능한 확장: Root 객체에서 참조할 수 있는 다양한 [비필수 객체](https://www.adobe.com/content/dam/acom/en/devnet/pdf/pdfs/PDF32000_2008.pdf#page=81)의 쌍 - 예: `Outlines`, `Names`, `AcroForm`, 추가 동작(`AA`) - 을 원본 소스 파일에서도 유지하도록 UniColl 블록을 연결할 수 있습니다.

**PDFLaTeX에서**

앞서 설명한 기법은 단지 한 쌍의 PDF 파일에서만 동작하지만,
TeX 소스에서 직접 [특정 PDFTeX 연산자](http://texdoc.net/texmf-dist/doc/pdftex/manual/pdftex-a.pdf)를 통해 수행하는 것도 가능합니다.

정렬을 위한 더미 키와 값을 포함해 객체를 직접 정의할 수 있으며, 일부 객체 슬롯을 예약하기 위해 빈 객체를 정의할 수도 있습니다. TeX 소스 맨 처음에 다음을 포함하면 됩니다:``` latex
% set PDF version low to prevent stream XREF
\pdfminorversion=3

\begingroup

  % disable compression to keep alignments
  \pdfcompresslevel=0\relax

  \immediate
  \pdfobj{<<
    /Type /Catalog

    % cool alignment padding
    /MD5_is /REALLY_dead_now__

    % the first reference number should be on offset 0x49,
    % so the '2' object number will be changed to '3' by UniColl
    /Pages 2 0 R

    % now padding so that the collision blocks (ends at 0xC0) are covered
    /0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF
    % with an extra character to be replaced by a return char
    /0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0
  >>}

  % the original catalog of the shifted doc
  \immediate\pdfobj{<</Type/Pages/Count 1/Kids[8 0 R]>>}

  % the original catalog of the host doc
  \immediate\pdfobj{<</Type/Pages/Count 1/Kids[33 0 R]>>}

  % now we need to reserve PDF Objects so that there is no overlap
  \newcount\objcount

  % the host size (+3 for spare object slots) - 1
  % putting a higher margin will just work, and XREF can have huge gaps
  \objcount=25
  \loop
    \message{\the\objcount}
    \advance \objcount -1

  \immediate\pdfobj{<<>>} % just an empty object

  \ifnum \objcount>0
  \repeat

\endgroup

필요한 경우 PDFLaTeX 출력을 예를 들어 mutool로 정규화하는 것을 잊지 마세요: PDFLaTeX는 배포판들 간에 재현 가능한 빌드를 얻기 어렵습니다 - 필요한 경우 정확한 해시를 얻기 위해 실행 시각을 후킹하고 싶을 수도 있습니다.

PDF에서의 JPG

JPG가 단지 이미지일 뿐이라고 기대할 수 있지만, PDF 및 일부 PDF 리더(브라우저가 아닌, 예: Evince 및 Adobe Reader)에서는 JPEG 이미지에 포함된 다른 포함 객체와 마찬가지로 페이지 콘텐츠로 사용될 수 있습니다.

JPEG 데이터를 무손실로 저장하려면 100% 회색조(grayscale)로 저장한 다음, 단일 행/열(row/column)의 그림을 사용하거나 데이터 라인을 8번 반복하세요(JPEG 블록은 8x8이므로). 그러면 데이터가 무손실로 저장되고 PDF 페이지에서 참조됩니다.

JPEG 페이지 데이터(색상을 렌더링하는 회색조 그림)를 벡터 페이지 콘텐츠로 사용하여 SHA-1 충돌하는 두 PDF의 예시:

If ⟷ Shattered - the movie

이미지 데이터를 JPG로 저장한 2개의 SHA-1 충돌 PDF

충돌하는 JPG를 두 번 참조할 수 있습니다: 페이지 콘텐츠로 무손실 참조하고, 동시에 표시될 손실 이미지로도 자신을 참조합니다. 다시 말해, 표시되는 이미지는 회색조이지만, 페이지 콘텐츠는 PDF 연산자를 통해 일부 색상을 렌더링할 수 있습니다.

이미지의 상단은 페이지 콘텐츠가 8번 반복된 것을 보여줍니다.

JPEG를 페이지 데이터 및 표시용 그림으로 사용하여 SHA-1 충돌하는 두 PDF의 예시:

Skulls & Crossbones ⟷ Golden Axe

JPG를 이미지 및 페이지 콘텐츠로 사용한 2개의 SHA-1 충돌 PDF

ZIP

TL;DR ZIP에는 일반적으로 재사용 가능한 충돌이 없지만, ZIP 기반 형식에는 있습니다. 2h.core에서 두 파일을 충돌시키는 것이 가능해야 합니다 (chosen-prefix보다 36배 빠릅니다)

ZIP 아카이브는 (최소한) 3개의 레이어로 이루어진 샌드위치입니다. 먼저 파일 콘텐츠가 옵니다(Local File Header 구조의 시퀀스, 아카이브된 각 파일 또는 디렉터리당 하나). 그 다음에는 일부 인덱스(다시 Central Directory의 시퀀스), 마지막으로 이 인덱스를 가리키는 단일 구조(End Of Central Directory)가 옵니다.

이 레이어들의 순서는 바꿀 수 없습니다. 일부 파서는 파일 콘텐츠의 구조만 필요로 하지만, 이는 올바른 파싱 방법이 아니며 악용될 수 있습니다.

이 필수 순서 때문에, 어떤 충돌에도 도움이 될 수 있는 일반적인 접두사는 없습니다.

비일반적 접근

또 다른 접근 방식은 두 아카이브를 병합된 레이어와 함께 병합하고 UniColl을 사용하되, N=2로 설정하여 4번째 바이트에 차이를 만들어 End of Central Directory의 매직 시그니처를 제거하는 것입니다.

즉, 단일 UniColl과 24바이트의 set prefix로 두 개의 임의의 ZIP을 충돌시킬 수 있습니다.

주석이 비어 있는 경우 일반적인 End of Central Directory는 22바이트입니다:``` 00: 504b 0506 0000 0000 0000 0000 0000 0000 PK.............. 10: 0000 0000 0000 ......

이것을 UniColl용 접두사로 사용하고 (접두사를 16비트로 패딩) `N=2`인 경우, 차이는 4번째 바이트에서 발생하여 매직 `.P .K 05 06`을 예측 가능하게 `.P .K 05 86`으로 변경하여 무력화시킵니다.```
00: 504b 0506 0000 0000 0000 0000 0000 0000  PK..............
10: 0000 0000 0000 2121 eb66 cf9d db01 83bb  ......!!.f......
20: 2888 4c41 e345 7d07 1634 5d4a 3b61 89a0  (.LA.E}..4]J;a..
30: 0029 94af 4168 2517 0bbc b841 cbf2 9587  .)..Ah%....A....
40: e438 0043 6390 279d 7c9e a01e e476 4c36  .8.Cc.'.|....vL6
50: 527f b1f4 653e d866 f98d 7278 5324 0bd5  R...e>.f..rxS$..
60: b31d ef6d d5d6 1163 5a2e a8a5 21bf eab4  ...m...cZ...!...
70: c59c 028e a913 f6b7 0036 c93f 5092 a628  .........6.?P..(

I don't see any content in the INPUT section to translate. Please provide the chunk text you'd like translated.``` 00: 504b 0586 0000 0000 0000 0000 0000 0000 PK.............. 10: 0000 0000 0000 2121 eb66 cf1d db01 83bb ......!!.f...... 20: 2888 4c41 e345 7d07 1634 5d4a 3b61 89a0 (.LA.E}..4]J;a.. 30: 0029 94af 4168 251f 0bbc b841 cbf2 9587 .)..Ah%....A.... 40: e438 00c3 6390 279d 7c9e a01e e476 4c36 .8..c.'.|....vL6 50: 527f b1f4 653e d866 f98d 72f8 5324 0bd5 R...e>.f..r.S$.. 60: b31d ef6d d5d6 1163 5a2e a8a5 21bf eab4 ...m...cZ...!... 70: c59c 028e a913 f6af 0036 c93f 5092 a628 .........6.?P..(

이것은 전혀 일반적이지 않지만, chosen-prefix collision보다 훨씬 빠릅니다:```
real 12m23.993s
user 112m24.072s
sys 2m0.194s

문제는 일부 파서가 ZIP 파일을 아래에서 위로 파싱해야 함에도 여전히 위에서 아래로 파싱한다는 것입니다. 두 파일이 모두 올바르게 파싱되도록 하는 방법은 두 개의 UniColl 블록을 연결하여 각각의 End of Central Directory를 활성화/비활성화하는 것입니다.

ZIP 파서가 사용되지 않는 공간에 대해 불평하지 않도록 하려면, Extra Fields, Central Directory의 파일 주석과 End of Central Directory의 아카이브 주석을 남용할 수 있습니다.

ZIP 충돌 다이어그램

예제: 다음은 두 개의 서로 다른 아카이브 파일을 담을 수 있는 이중 ZIP의 구조를 설명하는 어셈블리 소스입니다.

두 번의 Unicoll 계산 후, 두 개의 충돌 파일이 생성됩니다: collision1.zip ⟷ collision2.zip

Zip 기반 포맷

Zip 형식 자체는 Gzip처럼 일반적으로 악용할 수 없지만, Zip에 의존하는 일부 형식은 사전 정의된 구조를 가진 Zip 아카이브 내부에서 일반적으로 악용될 수 있습니다. Zip 충돌을 일반적으로 만들기 위해서는 몇 가지 주의가 필요합니다.

일부 형식은 Zip 아카이브에 저장된 여러 파일로 구성되며, 아카이브의 다른 파일을 가리키는 고정된 파일명을 가진 루트 파일에 의존합니다. 대부분 루트 파일에 XML 또는 텍스트를 사용하며, 다른 파일들은 있는 그대로 저장합니다.

아이디어 : 같은 아카이브에 2개의 파일 세트가 공존하도록 만들고, 두 파일 세트 중 하나를 가리키게 합니다. 일반적인 루트 파일은 파일의 시작 부분에 먼저 저장할 수 있지만, 충돌 블록은 파일 콘텐츠 외부, 즉 아카이브에 저장됩니다(충돌은 엔트로피가 매우 높기 때문에 XML 또는 ASCII로만 이루어진 파일을 충돌로 악용하는 것은 불가능합니다).

단계:

같은 아카이브에 서로 다른 출처의 파일 세트 2개를 넣습니다. 즉, 서로 다른 하위 디렉터리에 둡니다.
루트 파일을 수정하여 각 세트를 번갈아 가리키게 합니다.
루트 파일의 타임스탬프, 길이, CRC는 Local File Header - 파일 내용 앞 - 와 Central Directory - 파일 내용 뒤 - 양쪽에 저장되므로, 이 값들은 두 파일 버전 간에 변경되지 않아야 합니다.
- 길이가 달라지면 이후의 모든 포인터가 달라지므로 동일한 접미사는 불가능합니다.
- Central Directory의 CRC32가 올바르지 않으면 파서가 이 값의 사본을 무시할 수 있지만, CRC32를 상수 값으로 위조하면 문제를 완전히 피하는 데 도움이 됩니다. CRC를 위조하기 위해 임의의 바이트 4개를 추가하는 것만으로는 충분하지 않을 것입니다. 이러한 루트 파일은 일반적으로 문법이 엄격한 XML 또는 텍스트이므로 무효화되기 때문입니다. CrcHack은 무차별 대입 없이 임의의 비트로 CRC를 위조하는 데 큰 도움이 되며, 출력 파일이 ASCII이고 수정된 비트가 여전히 주석 안에 있도록 보장합니다.
루트 파일 뒤에 있는 추가 더미 파일의 extra field(비어 있더라도)를 사용하는 것은 Hashclash 충돌 블록을 저장하는 우아한 방법입니다. 이렇게 하면 Zip 아카이브는 표준 구조를 유지하며 이후에 표준 도구로도 쉽게 조작할 수 있습니다.

Extra Fields에는 CRC32가 없으며, 그 16비트 길이는 앞선 헤더에 선언됩니다. Extra Fields는 자체 내부 포맷 ID:2 Size:2 Data를 갖지만 대개 무시되며, Local File Header와 Central Directory 양쪽에 존재합니다. 그러나 충돌 블록 이후의 접미사를 동일하게 유지하려면 Central Directory에서는 이를 생략할 수 있습니다.

extra field에 충돌 블록을 포함하는 추가 파일의 존재는 형식 구조에 선언해야 할 수 있습니다(예: OOXML 문서의 [Content_Types].xml 파일). 일부 형식은 절대 경로를 사용해야 하므로 접미사의 다른 XML 파일도 수정해야 할 수 있습니다.

다음은 특정 zip 기반 형식에 대한 일반적인 악용의 전체 구조입니다:``` [Root file] (with constant CRC32)

[Dummy file] (with collision blocks in the extra field)

[...] <- rest of the archive, with 2 documents merged

따라서 루트 파일 내용을 미리 정의하고 ASCII CRC32를 위조함으로써, 특정 zip 기반 형식에 대해 일반적으로 재사용 가능한 Hashclash 충돌을 계산할 수 있습니다.


### 요구 사항 요약

- 두 개 이상의 prefix
- 하나 이상의 파일 형식 (polyglot은 문제없이 동작합니다)
- 파일명, 파일 길이 및 CRC가 고정된 XML 루트 파일: 이 정보는 충돌 블록 앞과 뒤에 두 번 존재합니다.
 - 내용은 임의의 XML입니다.
 - 패딩은 동일한 길이에 도달하기 위해 XML 주석을 통해서도 가능합니다.
 - 각 콘텐츠에 CRC를 (CrcHack을 통해) 설정할 수 있습니다.
- 두 파일 세트 모두 suffix에 공존하며, 아마도 서로 다른 디렉터리에 있을 것입니다. 일부 도구는 경로를 하드코딩하므로 호환성이 줄어들 수 있습니다.
- *Content type* XML 파일은 지원되거나 지원되지 않는 모든 파일(충돌 블록 및 대체 문서)을 포함하도록 병합해야 할 수 있습니다.


### 예제

#### CRC32

CrcHack을 사용하여 위조된 CRC32(즉시 계산)가 포함된 최소한의 XML 주석(ASCII 전용)입니다.``` bash
echo "<!--ABCDEF-->" | crchack -b 4.0:+.8*6:1 -b 4.1:+.8*6:1 -b 4.2:+.8*6:1 -b 4.3:+.8*6:1 -b 4.4:+.8*6:1 -b 4.5:+.8*5:1 - 0xdeadf00d
<!--X{]EZF-->

알파벳 메시지의 경우에 CRC를 조정하는 또 다른 예입니다.```bash echo "" | crchack.exe -b 4:+.8*32:.8 - 0xcafebabe

#### 충돌

[zInsider](https://github.com/decalage2/collisions/blob/HEAD/scripts/zinsider.py)는 다음 ZIP+XML 형식을 사용하여 임의 문서 쌍의 MD5 충돌을 즉시 생성하는 스크립트입니다:
- Office Open XML: docx / pptx / xlsx
- Open Container Format: epub
- Open Packaging Conventions:
  - 3D 제조 형식: 3mf
  - XML Paper Specification: xps / oxps

자체 충돌 접두어를 생성하려면 루트 zip 쌍을 생성하는 [스크립트](https://github.com/decalage2/collisions/blob/HEAD/scripts/makezip.py)가 여기 있습니다.
충돌을 계산한 후에는 [이 다른 스크립트](https://github.com/decalage2/collisions/blob/HEAD/scripts/extendzip.py)를 사용하여 이 루트 쌍을 공통 접미어와 결합하세요.

몇 가지 충돌 PoC:
- Office Open XML: Excel ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-1.xls) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-2.xls)), Powerpoint ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-1.pptx) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-2.pptx)), Word ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-1.docx) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-2.docx)).
- Open Container Format: Epub ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-1.epub) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-2.epub)).
- Open Packaging Conventions: 3MF ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-1.3mf) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-2.3mf)), XPS ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-1.xps) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-2.xps)).


일부 Zip 기반 다중 파일 형식은 일반적으로 악용될 수 없습니다:
- Quake PK3: 특정 루트가 없는 파일들의 zip입니다.
- Open Document Format: `META-INF/manifest.xml` 파일이 다른 모든 파일을 언급해야 하므로 일반적일 수 없습니다.
- APK, JAR, XPI: `META-INF/MANIFEST.mf` 파일도 해시와 함께 다른 모든 파일을 언급해야 합니다.


Office 파일 형식에 대한 도움을 주신 [Philippe Lagadec](https://twitter.com/decalage2)에게 감사드립니다!


## 일반적이지 않은 전략

충돌은 일반적으로 같은 유형의 두 유효한 파일에 관한 것입니다.


### MultiColls: 다중 충돌 체인

여러 충돌 블록을 연결하고 동일한 해시 값을 가진 콘텐츠를 둘 이상 갖는 것을 막을 수는 없습니다.
그 예로 *hashquines*가 있습니다. 자신의 MD5 값을 보여줍니다.
[PoCGTFO 14](https://github.com/angea/pocorgtfo#0x14) 파일에는 동일한 파일 내 두 파일 형식을 통해 이를 수행하는 609개의 FastColl 충돌이 포함되어 있습니다.


### 유효성

다른 전략은 파일 형식을 죽여 손상된 파일로 스캔을 우회하는 것입니다.
매직 시그니처를 덮어쓰기만 하면 충분합니다.
오프셋 0에 있을 필요가 없는 형식(ZIP/RAR/... 같은 아카이브)으로 두 파일(유효하거나 무효한)을 추가하면 다른 파일 형식이 드러날 수 있습니다.

이를 통해 선택 접두어 충돌을 사용하지 않고도 폴리글로트 충돌이 가능합니다:
1. UniColl을 사용하여 매직 시그니처를 활성화 또는 비활성화합니다(예: PNG):
2. ZIP 아카이브를 추가합니다

기술적으로 두 파일 모두 유효한 ZIP이지만, 대부분의 파서는 발견된 첫 번째 파일 형식을 반환하고 오프셋 0에서 스캔을 시작하므로 다른 파일 형식을 보게 됩니다.

예시:

 ⟷ [유효하지 않음](https://github.com/decalage2/collisions/blob/HEAD/examples/png-invalid.png)



### PolyColls: 서로 다른 파일 형식의 충돌

의심을 줄이기 위해 충돌의 양쪽을 서로 다른 형식으로 만드는 것도 가능합니다:

공격 시나리오:
1. `holiday.jpg` 전송
2. 화이트리스트에 등록
3. 동일한 MD5를 가진 `evil.exe`를 전송합니다.

이러한 경우 두 파일 형식이 모두 오프셋 0에서 시작해야 한다면 선택 접두어 충돌이 필요합니다.

폴리콜 레이아웃의 몇 가지 예:

![pdf-jpg 폴리글로트 충돌](https://assets.kitploit.com/production/public/readmes/47472/3dcd55e877a4ce9c933bf1478d0a71ede85e129b9e746414d754ffabceabe463.png)

*PDF/JPG 폴리콜*


![pe-png 폴리글로트 충돌](https://assets.kitploit.com/production/public/readmes/47472/63df55a15e7ca33153f352f13ba273604df6b1ae3e1e8838b601fea39de801e0.png)

*PE/PNG 폴리콜*


#### PE - JPG

PE 헤더는 일반적으로 0x500바이트보다 작으므로 JPG 주석에 완벽하게 맞습니다:
1. DOS/JPG 헤더로 시작합니다
2. JPEG 주석이 PE 헤더를 건너뜁니다
3. 전체 JPG 이미지를 넣습니다
4. 전체 PE 사양을 넣습니다

다시 말하지만, 충돌은 [즉시](https://github.com/decalage2/collisions/blob/HEAD/scripts/jpgpe.py) 발생합니다

예시: [fastcoll.exe](https://github.com/decalage2/collisions/blob/HEAD/examples/jpg-pe.exe) ⟷ [Marc.jpg](https://github.com/decalage2/collisions/blob/HEAD/examples/jpg-pe.jpg)


#### PDF - PE

`mutool`로 PDF와 더미 파일을 병합하는 것은 객체를 재정렬한 다음 처음 두 객체(더미 페이지와 콘텐츠)를 버릴 수 있게 만드는 좋은 일반적인 방법이며, 알 수 없는 길이의 `stream` 객체를 `1 0`으로 호스팅하고 그 길이는 두 번째 객체의 충돌 블록 이후에 참조되도록 하기에 완벽합니다.

유일한 문제는 `mutool`이 항상 길이를 인라인하고 길이 참조를 제거한다는 것입니다. 따라서 값을 대신해 PDF에 길이 참조를 다시 삽입해야 합니다. 대부분의 `2 0 R` 참조는 하드코딩된 길이보다 작을 것입니다.
다행히도 객체 오프셋을 변경하지 않고도 이 문제를 해결할 수 있으므로 XREF를 패치할 필요가 없습니다.

예를 들어 PDF 뷰어([Sumatra](https://www.sumatrapdfreader.org/free-pdf-reader.html)는 가볍고 독립 실행형입니다)와 PDF 문서를 즉시 충돌시키는 [스크립트](https://github.com/decalage2/collisions/blob/HEAD/scripts/pdfpe.py)가 여기 있습니다:

예시: [Poster.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/pepdf.pdf) ⟷ [Sumatra.exe](https://github.com/decalage2/collisions/blob/HEAD/examples/pepdf.exe)

![동일한 MD5를 가진 PDF(그 자체로 PDF를 표시하는)를 보여주는 PDF 뷰어](https://assets.kitploit.com/production/public/readmes/47472/4356d710fc4b60297ee05999be64f596198e9d4a02c826666818eb8ae117310f.png)

*동일한 MD5를 가진 PDF(그 자체로 PDF를 표시하는)를 보여주는 PDF 뷰어*


#### PDF - PNG

마찬가지로, 예를 들어 임의의 PDF와 PNG 파일을 양쪽에 제한 없이 충돌시키는 것이 가능합니다. 이는 즉각적이고 재사용 가능하며 일반적입니다.

예시: [Hello.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/png-pdf.pdf) ⟷ [1x1.png](https://github.com/decalage2/collisions/blob/HEAD/examples/png-pdf.png)


### PileUps (다중 충돌)


암호화 충돌은 두 개의 파일에만 국한되지 않습니다!

2008년 [Nostradamus](https://www.win.tue.nl/hashclash/Nostradamus/) 실험에서 입증되었듯이, 충돌을 연결하면 두 개 이상의 파일을 충돌시키는 것이 가능합니다.

첫 번째 충돌은 동일하거나 선택 접두어일 수 있지만, 이후의 충돌은 선택 접두어여야 합니다.

다중 충돌이라고 부를 수 있지만, 저는 *pileups*을 선호합니다. 더 짧거든요 :)


#### PE - PNG - MP4 - PDF

앞서 얻은 모든 지식을 결합하여, 서로 다른 파일 형식을 위한 4개의 서로 다른 접두어를 만들기 위해 3개의 선택 접두어 충돌을 사용했습니다: 문서(PDF), 비디오(MP4), 실행 파일(PE), 이미지(PNG).

![PE/PNG/MP4/PDF 파일업 다이어그램](https://assets.kitploit.com/production/public/readmes/47472/f7c45f284bad51f431a2993cf4797f679c85671c028cf1862f1c07604740360a.png)

*PE/PNG/MP4/PDF 파일업 다이어그램*

이 스크립트는 일반적이며 즉각적입니다:

![PE/PNG/MP4/PDF 파일업 다이어그램](https://assets.kitploit.com/production/public/readmes/47472/3ec7caeb459eab294c6b9876a8a82e136502c3d11c599804fd7925fc2d819276.png)

예시: [commodore.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/pileup.pdf) ⟷ [diagram.png](https://github.com/decalage2/collisions/blob/HEAD/examples/pileup.png) ⟷ [kidmo.mp4](https://github.com/decalage2/collisions/blob/HEAD/examples/pileup.mp4) ⟷ [sumatra18.exe](https://github.com/decalage2/collisions/blob/HEAD/examples/pileup.exe)


단일 파일만 배포할 수 있고 그 파일에서 다른 접두어 값을 추측하는 것이 불가능하기 때문에, 해결책은 충돌의 모든 접두어를 JavaScript 코드에 포함하여 PoC에 삽입하고, 파일을 [HTML 폴리글로트](https://github.com/decalage2/collisions/blob/HEAD/examples/polyglot.html)로 만들어 관련 충돌 파일을 쉽게 공유하는 것입니다.



'PoC or GTFO'의 [19호](https://github.com/angea/pocorgtfo#0x19)는 그러한 파일업 **이자** 폴리글로트로, PDFLaTeX로 생성된 80페이지 문서, Windows용 PDF 뷰어, PNG 다이어그램, [KidMoGraph](https://www.kidmograph.com/)의 짧은 '충돌' MP4 비디오를 결합하고, PDF 릴리스에서 다른 파일들을 생성하는 HTML 페이로드(그리고 ZIP 아카이브도)를 포함합니다:



JavaScript에 대한 지속적인 도움을 주신 Rafał Hirsz에게 감사드립니다.


## 사용 사례

MD5는 아예 버리는 것이 낫습니다. 파일 검사는 너무 시간이 많이 걸리고 위험하기 때문입니다!


### 모두 충돌시키자!

즉각적이고 재사용 가능하며 일반적인 충돌의 또 다른 용도는 주어진 형식(예: PNG)의 파일을 더미 파일(또는 매번 동일한 파일) 뒤에 숨기는 것입니다. 이는 실제로 시그니처를 제거한 후 동일한 접두어에 연결하기만 하면 되며, 라이브러리 수준에서도 할 수 있습니다!

엄격한 파싱 관점에서 모든 파일은 동일한 콘텐츠를 표시하며, 악성 이미지는 이전에 수집된 것과 동일한 MD5를 가진 파일로 드러날 것입니다.

두 개의 파일을 예로 들어 보겠습니다:

 ⟷


그리고 동일한 PNG와 충돌시킵니다.

이제 동일한 더미 이미지를 표시하며, 파일 수준에서 두 번째 이미지까지 완전히 동일합니다!

 ⟷


각각의 악성 페이로드는 동일한 MD5를 가진 파일 뒤에 숨겨져 있습니다.


### 유죄를 입증하는 파일

충돌의 또 다른 사용 사례는 무해하지만 바람직한 무언가 안에 유죄를 입증하는 무언가를 숨기는 것입니다. 증거를 수집하는 유일한 방법이 취약한 해시를 비교하는 것이라면, 다른 파일(유죄를 입증하는 콘텐츠를 표시하지만 무해한 콘텐츠를 숨기는 파일)을 가지고 있지 않다고 부인할 수 없습니다.

소프트웨어는 일반적으로 상세한 파일 분석보다는 (빠른) 파싱에 중점을 둡니다.



*EnCase Forensic의 다른 탭 아래 서로 다른 미리보기를 보여주는 이미지*


## 실패

모든 형식이 재사용 가능한 일반적인 접두어를 가질 수 있는 것은 아닙니다. 매직 시그니처와 각 파일에 중요하고 고유한 표준 헤더 사이에 어떤 종류의 데이터 보유자를 삽입할 수 없다면 일반적인 충돌은 불가능합니다.

물론 기존 파일을 새 파일로 변환하고 코드를 사용하여 두 개의 다른 페이로드로 분기할 수도 있지만, 이는 파일 구조를 충돌시키기보다는 페이로드를 포팅하는 것에 가깝습니다.


### ELF



ELF 헤더는 오프셋 0에 있어야 하며 32b/64b, 엔디언, ABI와 같은 중요한 정보를 처음부터 포함하므로, 원본 파일에 고유한 중요한 매개변수 앞에 범용 접두어와 충돌 블록을 둘 수 없습니다.


### Mach-O



Mach-O는 32b(`feedface`)와 64b(`feedfacf`)에서 같은 매직으로 시작하지조차 않습니다. 그 직후에는 명령의 수와 크기(세그먼트 정의, symtab, 버전 등)가 있습니다.

ELF와 마찬가지로 재사용 가능한 충돌은 불가능합니다.


### Java Class



시작 매직 바로 뒤에 버전(문제가 될 수 있음)이 위치하지만, 상수 풀 개수는 각 파일에 상당히 고유하므로 모든 파일에 대한 범용 충돌은 없습니다.

그러나 많은 파일은 여전히 공통 버전을 가지며, 가장 짧은 상수 풀을 가장 긴 개수로 패딩할 수 있습니다.
먼저 정보를 정렬하기 위해 *UTF8 리터럴*을 삽입한 다음, 길이가 UniColl에 의해 악용된 다른 하나를 선언합니다(길이는 빅 엔디언 16바이트로 저장됩니다).

그러나 모든 풀 인덱스가 이동되므로 코드 조작이 필요합니다.

Java Class의 즉각적이고 재사용 가능한 MD5 충돌은 가능해야 하지만 코드 분석과 수정이 필요합니다.


### TAR

**요약** TAR 파일에는 재사용 가능한 충돌이 없으며 선택 접두어 외의 전략도 없습니다.



Tape Archive는 연결된 헤더와 파일 콘텐츠의 시퀀스로, 모두 512바이트로 정렬됩니다.

전체 파일에 대한 중앙 구조가 없습니다. 따라서 악용할 수 있는 전역 헤더나 주석이 없습니다.

한 가지 트릭은 가변 길이의 더미 파일을 시작하는 것이지만, 길이는 항상 같은 오프셋에 있으므로 UniColl과 호환되지 않습니다. 즉, 여기서는 선택 접두어 충돌만 유용합니다.


## 익스플로잇 요약

형식            | 범용?    | FastColl | UniColl | Shattered | HashClash / Shambles
--------      | -------- | :------: | :-----: | --------- | :-------:
PDF           | Y        |          | x       |           | x
JPG           | Y (1)    |          | x       | x (2)     | x
GZ            | Y        |          | x       |           | x
PNG           | Y/N (3)  |          | x       |           | x
MP4           | Y (4)    |          | x       | x (5)     | x
PE            | Y        |          |         |           | x
ZIP 기반 (6)   | Y        |          |         |           | x
              |          |          |         |           |
GIF           | N        | x        |         |           | x
ZIP           | N        |          | x (7)   |           | x
              |          |          |         |           |
ELF           | N        |          |         |           | x
TAR           | N        |          |         |           | x
Mach-O        | N        |          |         |           | x
Class         | N        |          |         |           | x

1. JPG는 데이터에 몇 가지 제한이 있으며, 스캔 인코딩을 조작하여 어느 정도 개선할 수 있습니다.
2. PDF w/ JPG는 Shattered 공격의 [초기 구현](http://shattered.io)이지만, PDF 문서 안의 순수한 JPG 트릭일 뿐입니다.
3. PNG: Safari/Preview는 PNG가 충돌 블록 앞의 첫 번째 슬롯에 `IHDR` 청크를 가질 것을 요구합니다. 이렇게 하면 범용 접두어가 불가능해지며, 이 경우 충돌은 특정 크기, 색 공간, BPP 및 인터레이싱으로 제한됩니다.
4. MP4와 같은 Atom/Box 형식은 서로 다른 하위 형식에 대해 동일한 접두어로 작동할 수 있습니다. JPEG2000이나 HEIF 같은 일부 하위 형식은 추가적인 정리가 필요하지만, 익스플로잇 전략은 동일합니다. 단지 하위 형식 간에는 충돌이 불가능하고 특정 하위 형식에 대한 접두어 쌍에만 충돌이 가능할 뿐입니다.
5. Atom/Box는 64비트 길이를 사용할 때 Shattered와 호환됩니다.
6. 일부 Zip 기반 형식은 일반적으로 악용될 수 있습니다.
7. 더 나은 호환성을 위해 ZIP은 완전한 아카이브에 두 개의 UniColl이 필요하며, 이 충돌은 두 파일의 내용에 따라 달라집니다.

## 테스트 파일

무료(저작권 없음, 개인정보 없음) 테스트 충돌 쌍은 [여기](https://github.com/decalage2/collisions/blob/HEAD/examples/free/README.md)에 있습니다.


# 참고 자료

논문:

- 2004
  - [MD5 To Be Considered Harmful Someday](https://eprint.iacr.org/2004/357.pdf) - Dan Kaminsky
  - [Practical Attacks on Digital Signatures Using MD5 Message Digest](https://eprint.iacr.org/2004/356.pdf) - Ondredj Mikle 
- 2005:
  - [A Note on Practical Value of Single Hash Collisions for Special File Formats](https://github.com/decalage2/collisions/blob/HEAD/papers/Illies_NIST_05.pdf) - Max Gebhardt, Georg Illies, Werner Schindler
- 2014:
  - [Malicious Hashing: Eve’s Variant of SHA-1](https://malicioussha1.github.io/) - Ange Albertini, Jean-Philippe Aumasson, Maria Eichlseder, Florian Mendel, Martin Schläffer
- 2017:
  - [The first collision for full SHA-1](http://shattered.io) - Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov
  - [Postscript that shows its own MD5](https://archive.org/stream/pocorgtfo14#page/n45/mode/1up) by Gregor "Greg" Kopf
  - [A PDF That Shows Its Own MD5](https://archive.org/stream/pocorgtfo14#page/n49/mode/1up) by Mako
  - [This GIF shows its own MD5!](https://archive.org/stream/pocorgtfo14#page/n52/mode/1up) by Kristoffer "spq" Janke
  - [This PDF is an NES ROM that prints its own MD5 hash!](https://archive.org/stream/pocorgtfo14#page/n55/mode/1up) by Evan Sultanik, Evan Teran
- 2018:
  - [Easy SHA-1 Colliding PDFs with PDFLaTeX.](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up) by Ange Albertini
- 2020:
  - [SHA-1 is a Shambles](https://eprint.iacr.org/2020/014.pdf) by Gaëtan Leurent, Thomas Peyrin

프레젠테이션:
- 2017 Exploiting Hash Collisions at Black Alps:
  - [슬라이드](https://speakerdeck.com/ange/exploiting-hash-collisions)
  
    [](https://speakerdeck.com/ange/exploiting-hash-collisions)
  
  - [동영상](https://www.youtube.com/watch?v=Y-oJWEYKVLA)
  
    [![해시 충돌 익스플로잇 Youtube 동영상](https://assets.kitploit.com/production/public/readmes/47472/c995bb115228391b655125ee5806530149829d3a62b8754485071f5db9512e67.jpg)](https://www.youtube.com/watch?v=Y-oJWEYKVLA)

- 2019 KILL MD5 at Pass the Salt:
  - [슬라이드](https://speakerdeck.com/ange/kill-md5)

    [](https://speakerdeck.com/ange/kill-md5)
  - [동영상](https://passthesalt.ubicast.tv/videos/kill-md5-demystifying-hash-collisions/)

    [![Kill MD5 동영상](https://assets.kitploit.com/production/public/readmes/47472/4d7d0e2935f37e9ae363ad7bebe2abb3697978e7b3c1aa57851c54727b7ac49f.jpg)](https://passthesalt.ubicast.tv/videos/kill-md5-demystifying-hash-collisions/)


워크숍 (CollTris):
  - [슬라이드](https://speakerdeck.com/ange/colltris)

    [](https://speakerdeck.com/ange/colltris)

  - [동영상](https://www.youtube.com/watch?v=BcwrMnGVyBI)

    [](https://www.youtube.com/watch?v=BcwrMnGVyBI)

  - [자료](https://github.com/decalage2/collisions/blob/HEAD/workshop/README.md)

  - 세션
    - 2019/07/02 150p, Pass The Salt
    - 2019/07/24 199p, Google
    - 2019/08/19 208p, Google
    - 2019/10/23 222p, Hack.lu
    - 2019/11/07 225p, Black Alps
    - 2019/12/03 229p, Google


CTF 문제:
- [Prudentialv2](https://ctftime.org/task/3453), *Boston Key Party CTF 2017*에서.
- [HREFIN](https://ctftime.org/task/6965), *Google CTF 2018*에서.
- [Looking glass](https://ctftime.org/task/9271) *Dragon Sector Teaser CTF 2019*에서.

<!-- - [Not my digest](https://ctftime.org/task/4784) from *Hack.lu CTF 2017*: not related to collisions, but solved by Marc himself :p -->
이러한 CTF 문제의 공통적인 과제는 각 플레이어가 접근할 수 있는 컴퓨팅 파워의 양에 따라 너무 큰 이점이나 불리함을 주지 않는 것입니다.


# 크레딧

이 모든 것은 [Marc Stevens](https://marc-stevens.nl/research/) 덕분에 가능했습니다. 그의 암호학적 기여뿐만 아니라 지속적인 도움과 제안에도 감사드립니다!

또한 일반적인 파일 형식에 대한 폭넓은 피드백을 주신 Philippe Teuwen에게도 감사드립니다.


# 결론

**MD5를 죽여라!**

파일에서 변형이나 충돌 블록을 적극적으로 확인하지 않는 한, MD5를 사용하지 마세요!

MD5는 암호화 해시가 아니라 장난감 함수입니다!

collisions

인기