# 공격

MD5와 SHA1은 64바이트 블록으로 작동합니다.

두 콘텐츠 A와 B가 동일한 해시를 가지면, 둘 다에 동일한 콘텐츠 C를 추가해도 동일한 해시가 유지됩니다.``` text
hash(A) = hash(B) -> hash(A + C) = hash(B + C)

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/corkami/collisions/blob/HEAD/examples/fastcoll1.bin) ⟷ [2](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll2.bin)

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

다음은 접두사 없이 FastColl 계산을 수행하는 [녹화](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll.svg)이고,
[다른 것](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll-prefix.svg)은 접두사가 있는 경우입니다.


### [UniColl](https://github.com/corkami/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 collision)로 만들어 주며, 거의 선택 접두사 충돌(chosen-prefix collision)에 가깝습니다.
이것은 매우 유용하며, 더 좋은 점은 차이가 매우 예측 가능하다는 것입니다:
`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 .. .. .. ..
   ```
- exploitation: 매우 쉬움 - 차이 전후의 바이트를 제어할 수 있고, 차이도 예측 가능합니다. 유일한 제약은 정렬(alignment)과 차이 이후 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/corkami/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년.CPU 및 110년.GPU
- 공간: 두 블록
- 차이점:  ```
  .. .. .. DD ?? ?? ?? ??
  or
  ?? ?? ?? DD .. .. .. ..
  ```
- 악용: 중간. 충돌 블록의 차이는 시작과 끝에서 바로 나타납니다. 따라서 접두사/접미사에서 길이 앞 **및** 뒤를 제어할 수 없습니다.
  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개의 근접 충돌 블록이 계산되어 추가됩니다.

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

   예: [단일 블록에 40만 시간](https://www.win.tue.nl/hashclash/SingleBlock/). [HashClash](https://github.com/cr-marcstevens/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
```
전체 작업의 [로그](https://github.com/corkami/collisions/blob/HEAD/examples/cpc.html)는 다음과 같습니다.

### [Shambles](https://sha-mbles.github.io/) (SHA-1)

Shambles는 9개의 블록을 사용하는 매우 고비용의 선택-접두사 충돌입니다.

각 블록은 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
```
하지만 Shattered가 FastColl보다 훨씬 악용하기 쉽다 하더라도,
충돌 블록 간 차이의 제약은 무관하다.
Shambles가 선택 접두사 충돌(Chosen Prefix Collision)이기 때문이다.


## 공격 요약

Hash | Name      | Date | Duration | Prefix type | Control near diff
---- | --------- | ---- | -------- | ----------- | -----------------
MD5  | FastColl  | 2009 | 2s       | 동일        | 없음
     | UniColl   | 2012 | 7-40min  | 동일        | 4-10 바이트
     | HashClash | 2009 | 72h      | 선택        | n/a
     |         |     |         |           |
SHA1 | Shattered | 2013 | 6500yr   | 동일        | 접두사 및 접미사
     | Shambles  | 2020 | ?        | 선택        | n/a


# 악용

동일 접두사 충돌(Identical prefix collision)은 일반적으로 (매우) 제한적인 것으로 간주되지만, 선택 접두사(Chosen-prefix)는 시간이 많이 소요된다.

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

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


## 표준 전략

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


### JPG



이론적 제한 사항 및 우회 방법:
- *Application* 세그먼트는 이론상 *Start of Image* 마커 바로 뒤에 위치해야 한다.
  실제로는 반드시 그럴 필요가 없으므로, 충돌은 일반적(generic)일 수 있다. 유일한 제한은 가장 작은 이미지의 크기이다.
- 주석의 길이는 2바이트로 저장되므로, 저장할 수 있는 양은 65536바이트로 제한된다 (대략 400x400 사진 크기).
- 완전한 JPG 파일을 건너뛰는 대신, 해당 파일을 세그먼트로 나누고 세그먼트 사이에 점프 트램펄린을 추가할 수 있다.

  

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

  

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

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

스캔 세그먼트 외에는 다른 제한이 없다.
따라서 임의의 두 JPG의 MD5 충돌은 *즉시* 이루어지며, 선택 접두사 충돌이 필요 없고 UniColl만 있으면 된다.

다음 [스크립트](https://github.com/corkami/collisions/blob/HEAD/scripts/jpg.py)로:```
21:07:35.65>jpg.py Ange.jpg Marc.jpg

21:07:35.75>
```
예시:

 ⟷ 


#### 사용자 지정 스캔

*MD5 충돌 JPG 2개*

다음은 [1944x2508 RGB 이미지](https://github.com/corkami/collisions/blob/HEAD/pics/pocorgtfo14.png)를 20개의 스캔이 모두 64kb에 들어맞는 100% JPG로 변환하는 *JPEGTran* 스캔 정의의 예시입니다.```
// <component>: <minbyte>-<maxbyte>, <minbit>, <maxbit>;

// 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회 스캔된 100% JPG인 1944x2508 RGB 이미지*


### PNG



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

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

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

따라서 임의의 두 PNG 이미지의 MD5 충돌은 *즉시* 이루어지며, 전제 조건이 없다(계산 없이 약간의 파일 변경만 필요). 선택 접두사 충돌도 필요 없고 UniColl만 있으면 된다.

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

19:27:04.87>
```
예시:

 ⟷


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

전체 작업의 [녹화 영상](https://github.com/corkami/collisions/blob/HEAD/examples/pngGen.svg)입니다.

![범용(악용) PNG 충돌의 녹화 영상](https://raw.githubusercontent.com/corkami/collisions/HEAD/examples/pngGen.svg)

#### 비호환성

대부분의 리더는 `IHDR`이 아닌 청크로 시작하는 PNG 파일을 문제없이 받아들입니다.

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

이 경우 두 충돌 파일은 동일한 속성을 가져야 합니다.
다시 말하지만 UniColl이면 충분하며, 계산된 프리픽스 쌍은 동일한 속성을 가진 다른 파일 쌍에도 당연히 재사용할 수 있습니다.

필요 시 프리픽스 쌍을 계산하기 위해 UniColl을 실행하는, 이러한 파일 쌍을 충돌시키는 [스크립트](https://github.com/corkami/collisions/blob/HEAD/scripts/pngStd.py)가 있습니다.

예시:

 ⟷


 ⟷


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

UniColl이 호출될 때 전체 작업의 [녹화 영상](https://github.com/corkami/collisions/blob/HEAD/examples/pngUniColl.svg)입니다,

![PNG UniColl 충돌의 녹화 영상](https://raw.githubusercontent.com/corkami/collisions/HEAD/examples/pngUniColl.svg)

그리고 프리픽스가 이미 계산된 경우의 [또 다른 영상](https://github.com/corkami/collisions/blob/HEAD/examples/pngSpec.svg)입니다.

![미리 계산된 PNG 충돌의 녹화 영상](https://raw.githubusercontent.com/corkami/collisions/HEAD/examples/pngSpec.svg)

### GIF



GIF는 까다롭습니다:
- 메타데이터를 주석이 가능해지기 전에 헤더에 저장하므로, 모든 GIF 파일에 대한 범용 프리픽스는 있을 수 없습니다.
- 파일에 전역 팔레트가 있으면 그것도 주석이 가능해지기 전에 저장됩니다.
- 주석 청크의 길이는 1바이트로 제한되어, 최대 256바이트입니다!

하지만 주석 청크는 독특한 구조를 따릅니다: null 길이가 정의될 때까지 `<length:1>` `<data:length>`의 체인입니다.
따라서 0이 아닌 모든 바이트를 유효한 '앞으로 점프'로 만듭니다. 그래서 FastColl과 함께 사용하기에 적합합니다,
[PoC||GTFO 14:11](https://github.com/angea/pocorgtfo#0x14)에서 볼 수 있듯이.

따라서 최소한 범용 프리픽스가 없더라도, 동일한 메타데이터(크기, 팔레트)를 가진 GIF 쌍은 충돌시킬 수 있으며 프리픽스를 계산하는 데 FastColl을 1초만 실행하면 됩니다.

문제는 PNG처럼 이미지 전체를 건너뛰거나 JPG처럼 큰 구조를 건너뛸 수 없다는 것입니다.

가능한 해결책은 압축된 데이터를 조작하거나 GIF hashquine의 경우처럼 이미지를 아주 작은 영역으로 나누는 것입니다,
하지만 이는 최적이 아닙니다.

일반적으로 동작하는 또 다른 아이디어는 이미지 데이터도 이 `length data` 시퀀스 구조를 사용해 저장된다는 점입니다:
따라서 애니메이션이 없는 두 GIF를 사용한다면 다음만 하면 됩니다:
- 팔레트를 정규화
- 첫 번째 프레임의 지속 시간을 최대로 설정
- 첫 번째 프레임 데이터의 시작 부분으로 점프하는 주석을 만들어, 주석이 이미지 데이터 위를 주석으로 미끄러지듯 지나가도록,
- 그리고 같은 방식으로 끝납니다: null 길이를 만날 때까지입니다. 그러면 파서는 다음 프레임을 만나서 표시합니다.

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

결국 현재 *즉시* MD5 충돌을 위한 GIF의 제한 사항은 다음과 같습니다:
- 애니메이션 없음
- 이미지가 동일한 팔레트로 정규화되어야 함 - [`gifsicle --use-colormap web`](https://www.lcdf.org/gifsicle/) 참조
- 이미지 크기가 같아야 함
- 11분 후에는 두 파일 모두 같은 이미지를 표시함

정적 GIF 이미지를 정규화하는 간단한 방법은 그것들을 같은 이미지의 애니메이션 프레임으로 만드는 것입니다,
그런 다음 [스크립트](https://github.com/corkami/collisions/blob/HEAD/scripts/gif.py)를 사용해 FastColl 블록을 재사용하거나 계산하여 각각을 표시하는 파일 쌍을 만들 수 있습니다.

예시:

 ⟷


*2개의 MD5 충돌 GIF - 사진: [KidMoGraph](https://www.kidmograph.com/)*

전체 작업의 [녹화 영상](https://github.com/corkami/collisions/blob/HEAD/examples/gifFastColl.svg)입니다.

![GIF FastColl 충돌의 녹화 영상](https://raw.githubusercontent.com/corkami/collisions/HEAD/examples/gifFastColl.svg)

### GZIP



GZIP 사양 v4.3: [RFC 1952](https://datatracker.ietf.org/doc/html/rfc1952) (1996).

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

따라서 extra field를 가진 빈 gzip 멤버는 완벽한 기생 호스트입니다.

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

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

다양한 구현체는 모든 멤버의 합 대신 마지막 멤버의 압축 해제된 크기에 의존합니다. 따라서 우리의 충돌 파일은 크기가 0인 것으로 표시되는데, 이는 이 파일들이 트램펄린으로 사용되는 빈 멤버로 끝나기 때문입니다.

두 GZip 파일의 즉시 MD5 충돌을 생성하는 [스크립트](https://github.com/corkami/collisions/blob/HEAD/scripts/gz.py)가 있습니다. 입력 파일이 크면 대부분의 시간을 데이터 압축 해제 및 재압축에 소비합니다 - 충돌 프리픽스는 미리 계산되어 있습니다. 압축 해제하지 않고 멤버를 분할하는 것은 불가능한데, 압축 해제된 CRC32를 계산해야 하기 때문입니다.

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

예시: [collision1.tar.gz](https://github.com/corkami/collisions/blob/HEAD/examples/collision1.tar.gz) (Pacome) ⟷ [collision2.tar.gz](https://github.com/corkami/collisions/blob/HEAD/examples/collision2.tar.gz) (Reg)

### LZ4 / Zstandard




LZ4와 Zstandard는 전체 구조가 유사한 2가지 서로 다른 압축 형식입니다:
이들은 프레임으로 구성되며, 각 프레임은 특정 매직으로 시작합니다: Zstandard 프레임은 `0xFD2FB528`, Lz4 프레임은 `0x184D2204`입니다.

또한 이들은 동일한 '건너뛸 수 있는(skippable)' TLV 프레임을 **공유**합니다. 이 프레임은 `0x184D2A50`~`0x184D2A5F` 범위의 4바이트 *매직*으로 시작하고, 그 다음 사용자 데이터의 *길이*(4바이트, 리틀엔디언), 그 다음 *사용자 데이터* 자체로 이어집니다.

이 프레임들은 전적으로 선택적이며, 어떤 길이든 가능하고, 반복할 수 있습니다. 파일은 이러한 프레임으로 시작할 수 있습니다. 따라서 이 프레임들을 연결하여 2가지 형식에 걸쳐 완벽한 범용 충돌 프리픽스를 만들 수 있습니다.

두 Zstd/Lz4 파일의 즉시 MD5 충돌을 생성하는 [스크립트](https://github.com/corkami/collisions/blob/HEAD/scripts/zstd-lz4.py)가 있습니다. Gzip과 마찬가지로 내용과 관계없이 외부에서는 2개의 서로 다른 아카이브가 보입니다: 예를 들어 `.cpio.zst`.

예시:
- [md5-1.lz4](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.lz4) ⟷ [md5-2.lz4](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.lz4)
- [md5-1.zstd](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.zstd) ⟷ [md5-2.zstd](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.zstd)
- [md5-c6a611ce.zstd](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-c6a611ce.zstd) ⟷ [md5-c6a611ce.lz4](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-c6a611ce.lz4)

### Portable Executable



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

따라서 전략은 다음과 같습니다:
1. PE 헤더를 아래로 이동하여 DOS 헤더 뒤에 충돌 블록을 위한 공간을 남길 수 있습니다.
2. DOS 헤더는 (chosen-prefix 충돌을 통해) 두 개의 서로 다른 오프셋을 가리키도록 악용할 수 있으며, 그곳으로 두 개의 서로 다른 PE 헤더가 이동됩니다.
3. 섹션들은 `DOS/Collisions/Header1/Header2` 구조 뒤에 서로 나란히 배치할 수 있습니다. 두 섹션 테이블의 오프셋에 델타만 적용하면 됩니다.

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

실행 파일 충돌은 보통 어떤 로더를 통해서든 사소하게 가능하지만, 여기서의 이러한 악용은 투명합니다: 코드가 동일하고 같은 주소에 로드됩니다.

예시: [tweakPNG.exe](https://github.com/corkami/collisions/blob/HEAD/examples/collision1.exe) (GUI) ⟷ [fastcoll.exe](https://github.com/corkami/collisions/blob/HEAD/examples/collision2.exe) (CLI)

Windows 실행 파일의 즉시 MD5 충돌을 생성하는 [스크립트](https://github.com/corkami/collisions/blob/HEAD/scripts/pe.py)가 있습니다.



### MP4 and others

이 형식의 컨테이너는 Atoms라고 불리는 `Length Type Value` 청크들의 시퀀스입니다.
길이는 32비트 빅엔디언이며 자신, 타입, 값을 포함하므로 정상적인 최소 길이는 8입니다.
(타입은 4자리의 ASCII 문자열입니다).

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

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

MP4에서 사용되는 이 "atom/box" 형식은 사실 Apple Quicktime의 파생물이며,
[다른 많은 형식](http://www.ftyps.com/) (JP2, HEIF, F4V)에서도 사용됩니다.

첫 번째 atom 타입은 *보통* `ftyp`이며, 이를 통해 실제 파일 형식을 구분할 수 있습니다.

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

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

이를 통해 임의의 비디오를 즉시 충돌시키는 [스크립트](https://github.com/corkami/collisions/blob/HEAD/scripts/mp4.py)가 만들어집니다 - 그리고
앞서 언급했듯이 MP4 이외의 형식에서도 작동할 수 있습니다.

![Nirvana - Smells like Teen Spirit / Weird Al Yankovik - Smells like Nirvana](https://assets.kitploit.com/production/public/readmes/47471/73d5834dc98db928b538ffbe68d647d2a97375a6161e9b41ce12864c57e7d16c.png)

예시 ([KidMoGraph](https://www.kidmograph.com/)의 비디오):
- 32b 길이(표준) [collision1.mp4](https://github.com/corkami/collisions/blob/HEAD/examples/collision1.mp4) ⟷ [collision2.mp4](https://github.com/corkami/collisions/blob/HEAD/examples/collision2.mp4)

  <video width=300 controls> <source src="https://raw.githubusercontent.com/corkami/collisions/HEAD/examples/collision1.mp4" type="video/mp4">🏭</video> ⟷ <video width=300 controls> <source src="https://raw.githubusercontent.com/corkami/collisions/HEAD/examples/collision2.mp4" type="video/mp4">🛣️</video>

- 64b 길이 [collisionl1.mp4](https://github.com/corkami/collisions/blob/HEAD/examples/collisionl1.mp4) ⟷ [collisionl2.mp4](https://github.com/corkami/collisions/blob/HEAD/examples/collisionl2.mp4)

  <video width=300 controls> <source src="https://raw.githubusercontent.com/corkami/collisions/HEAD/examples/collisionl1.mp4" type="video/mp4">☀️</video> ⟷ <video width=300 controls> <source src="https://raw.githubusercontent.com/corkami/collisions/HEAD/examples/collisionl2.mp4" type="video/mp4">🌙</video>

<video controls>![어떻게 보여야 하는지(하지만 당신의 마크다운은 video 태그를 렌더링하지 않습니다)](https://assets.kitploit.com/production/public/readmes/47471/b611e0bd1ae01c731e2cb6822d03a122801c6314c7f71257c921bd115bd7c115.png)</video>

일부 뷰어(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을 먼저 [강제](https://github.com/uclouvain/openjpeg/blob/d2205ba2ee78faeea659263383446c4472b1f9df/src/bin/wx/OPJViewer/source/imagjpeg2000.cpp#L100-L111)하는 것 같습니다,
하지만 그 외에는 이것이 유일한 제한입니다: 아무것도 재배치할 필요가 없습니다.

따라서 결과물인 [스크립트](https://github.com/corkami/collisions/blob/HEAD/scripts/jp2.py)는 훨씬 더 간단합니다!

![Oded Goldreich / Neal Koblitz](https://assets.kitploit.com/production/public/readmes/47471/6177679c51449f4dd72eda33a047240f279837375959d89f7b2e0b253eff6f7a.png)

예시: [collision1.jp2](https://github.com/corkami/collisions/blob/HEAD/examples/collision1.jp2) ⟷ [collision2.jp2](https://github.com/corkami/collisions/blob/HEAD/examples/collision2.jp2)

### PDF



**Shattered에 대하여**

Shattered 악용은 PDF 트릭이 아니라 PDF 안의 JPG 트릭이었습니다.
이는 PDF가 서로 다른 두 내용을 가질 수 있는 JPG 압축 객체를 포함하도록 해주었을 뿐입니다.
두 PDF는 그 외에는 완전히 동일해야 했습니다.

문서는 완전히 정상일 수 있으며, 충돌 JPG를 잘라내어 여러 페이지 문서처럼 다른 위치에 표시하기만 하면 됩니다.

예시: [수정된 Shattered 논문](https://github.com/corkami/collisions/blob/HEAD/examples/shattered1.pdf) ⟷ [원본 Shattered 논문](https://github.com/corkami/collisions/blob/HEAD/examples/shattered2.pdf)




*두 군데에서 충돌 JPG를 사용하는 Shattered 논문*

**MD5를 사용한 PDF 충돌**

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

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

<!--
digraph {
 rankdir=LR;
 root -> "catalog#1"
 "catalog#1" -> "pages#2"
 "pages#2" -> "page#3"
 "page#3" -> "pages#2"
 "page#3" -> "content#4"
 "content#4" -> "Hello World!"
}
-->

![](https://raw.githubusercontent.com/corkami/collisions/HEAD/pics/pdf.svg)

이 (유효한) 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>>
```
Tricks:
- 사용되지 않는 객체를 PDF에 저장하는 것은 허용된다.
- 객체 번호를 건너뛰는 것도 괜찮다. `XREF` 테이블에서 번호를 건너뛰는 공식적인 방법도 있다.

따라서 두 개의 문서 트리를 같은 파일에 저장하는 것도 괜찮다.
루트 객체가 두 문서 중 어느 루트 객체를 가리키게만 하면 된다.

그래서 두 문서를 가져와서,
객체와 참조가 겹치지 않도록 번호를 다시 매기고,
Root 객체로 참조되는 요소 번호가 해시 값을 유지하면서 바뀔 수 있도록 충돌을 만들면 된다.
이는 `N=1`인 UniColl에 완벽하게 맞으며, 이에 맞게 `XREF` 테이블을 조정하면 된다.


<!--
digraph {
 rankdir=LR;
 "trailer" -> "catalog#1" [color=green]
 "catalog#1" -> "pages#2"
 "pages#2" -> "page#3"
 "page#3" -> "pages#2"
 "page#3" -> "content#4"
 "content#4" -> "Hello World!"
 trailer -> "catalog#11" [<col>or=red, style=dashed]
 "catalog#11" -> "pages#12"
 "pages#12" -> "page#13"
 "page#13" -> "pages#12"
 "page#13" -> "content#14"
 "content#14" -> "Bye World!";
}
-->

![](https://raw.githubusercontent.com/corkami/collisions/HEAD/pics/pdfcollision.svg)

이렇게 하면 페이지 번호, 크기, 이미지 등에 관계없이 어떤 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](https://github.com/Jurph/word-decrementer)님께 감사!

문서 구조를 수정하고 파서를 속이는 대신,
충돌 블록을 직접 사용하여 텍스트를 직접 생성하고,
다른 읽기를 제공할 것이다!```
           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/corkami/collisions/blob/HEAD/examples/poeMD5_A.pdf) ⟷ [poeMD5 B](https://github.com/corkami/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를 병합하기만 하면 됩니다.

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


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

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



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

**PDFLaTeX에서**

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

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
```
필요한 경우 - 예를 들어 `mutool`을 사용하여 - PDFLaTeX 출력을 정규화하는 것을 잊지 마세요:
PDFLaTeX는 배포판 간에 재현 가능한 빌드를 얻기 어렵습니다. 필요한 경우 정확한 해시를 얻기 위해 실행 시간을 연결하고 싶을 수도 있습니다.

#### PDF의 JPG

JPG는 단지 이미지일 뿐이라고 생각할 수 있지만, PDF 및 일부 PDF 리더(브라우저가 아닌 Evince 및 Adobe Reader 같은)에서는
다른 임베디드 객체와 마찬가지로 페이지 콘텐츠로 사용될 수 있습니다. 즉, JPEG 이미지에 임베드되는 방식입니다.

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

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

[If](https://github.com/corkami/collisions/blob/HEAD/examples/jpgpage1.pdf) ⟷ [Shattered - the movie](https://github.com/corkami/collisions/blob/HEAD/examples/jpgpage2.pdf)



*JPG로 저장된 이미지 데이터를 가진 2개의 SHA-1 충돌 PDF*

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

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

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

[Skulls & Crossbones](https://github.com/corkami/collisions/blob/HEAD/examples/dualjpg1.pdf) ⟷ [Golden Axe](https://github.com/corkami/collisions/blob/HEAD/examples/dualjpg2.pdf)



*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`)가 옵니다.

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

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

**비일반적 접근법**

또 다른 접근법은 두 아카이브를 병합된 레이어와 함께 그냥 병합하고 UniColl을 사용하는 것입니다. 단, N=2를 사용하여 4번째 바이트에 차이를 도입하고, 이를 통해 `End of Central Directory`의 매직 시그니처를 무력화합니다.

즉, 단일 UniColl과 24바이트의 설정된 접두사를 사용해 두 개의 임의 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..(
```
No input content was provided for translation.```
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 충돌 다이어그램](https://assets.kitploit.com/production/public/readmes/47471/e0fafd1f4ac2f826f383ca9ed1a465279352900283a681f9cfe8a2499f00257a.png)

**예제**: 다음은 두 개의 서로 다른 아카이브 파일을 담을 수 있는 이중 ZIP 구조를 설명하는 [어셈블리 소스](https://github.com/corkami/collisions/blob/HEAD/scripts/zip.asm)이다.

UniColl 계산을 두 번 수행하면 다음의 두 충돌 파일이 생성된다:
[collision1.zip](https://github.com/corkami/collisions/blob/HEAD/examples/collision1.zip) ⟷ [collision2.zip](https://github.com/corkami/collisions/blob/HEAD/examples/collision2.zip)


#### Zip 기반 포맷

Zip 포맷 자체는 Gzip처럼 범용적으로 악용될 수는 없지만, Zip에 의존하는 일부 포맷은 사전 정의된 구조를 가진 Zip 아카이브 내에서 범용적으로 악용될 수 있다. Zip 충돌을 범용적으로 만들기 위해서는 몇 가지 주의사항을 지켜야 한다.

일부 포맷은 Zip 아카이브에 저장된 여러 파일로 구성되며, 아카이브 안의 다른 파일을 가리키는 고정 파일명을 가진 루트 파일에 의존한다. 대부분의 경우 루트 파일에는 XML이나 텍스트를 사용하고, 다른 파일들은 원본 그대로 저장한다.

아이디어
: 2개의 파일 세트를 동일한 아카이브에 공존시키고, 각 세트를 가리키도록 한다. 범용 루트 파일을 파일의 시작 부분에 먼저 저장할 수 있지만, 충돌 블록은 파일 콘텐츠 밖, 즉 아카이브에 저장된다(충돌은 엔트로피가 매우 높기 때문에 XML 또는 ASCII 전용 파일을 충돌로 악용하는 것은 불가능하다).

단계:
1. 2개의 출처에서 가져온 2개의 파일 세트를 동일한 아카이브에 배치한다. 즉, 서로 다른 하위 디렉터리에 넣는다.
1. 루트 파일을 수정하여 각 세트를 번갈아 가리키게 한다.
1. 루트 파일의 타임스탬프, 길이 및 CRC는 파일 내용 앞의 `Local File Header`와 파일 내용 뒤의 `Central Directory`에 모두 저장되므로, 이 값들은 두 파일 버전 간에 변경되지 않아야 한다.

   - 길이가 달라지면 이후의 모든 포인터가 달라지므로 동일한 접미사(suffix)를 만들 수 없다.
   - `Central Directory`의 CRC32가 올바르지 않으면 이 값은 파서가 무시할 수도 있지만, CRC32를 상수 값으로 위조하면 문제 자체를 완전히 피하는 데 도움이 된다.
4바이트의 임의 데이터를 추가하여 CRC를 위조하는 것만으로는 충분하지 않을 수 있다. 이러한 루트 파일은 일반적으로 엄격한 문법을 가진 XML이나 텍스트이기 때문에 그렇게 하면 파일이 유효하지 않게 되기 때문이다.
[CrcHack](https://github.com/resilar/crchack)은 무차별 대입 없이 임의의 비트로 CRC를 위조하는 데 큰 도움이 되며, 출력 파일이 ASCII이고 수정된 비트가 여전히 주석 안에 있도록 보장한다.

4. 루트 파일 다음의 아카이브에 있는 추가 더미 파일의 `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 충돌을 계산할 수 있다.


### 요구 사항 요약

- 두 개 이상의 접두사
- 하나 이상의 파일 유형(폴리글롯은 문제없이 작동한다)
- 고정된 파일 이름, 파일 길이 및 CRC를 가진 XML 루트 파일: 이 정보는 충돌 블록 앞과 뒤에 두 번 존재한다
 - 내용은 임의의 XML이다
 - 동일한 길이에 도달하기 위해 XML 주석을 통해서도 패딩이 가능하다.
 - 각 내용에 (CrcHack을 통해) CRC를 설정할 수 있다.
- 두 파일 세트 모두 접미사(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 "<!--THISKINDOFCRCISREALLYIMPRESSIVEA-->" | crchack.exe -b 4:+.8*32:.8 - 0xcafebabe
<!--THIskInDoFCRcIsrEALlyimpRESSIVea-->
```
#### 충돌

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

자신만의 충돌 프리픽스를 생성하려면, [이 스크립트](https://github.com/corkami/collisions/blob/HEAD/scripts/makezip.py)로 루트 zip 쌍을 생성하세요.
충돌 계산 후에는 [이 다른 스크립트](https://github.com/corkami/collisions/blob/HEAD/scripts/extendzip.py)를 사용하여 이 루트 쌍을 공통 접미사와 결합하세요.

몇 가지 충돌 PoC:
- Office Open XML: Excel ([1](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.xls) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.xls)), Powerpoint ([1](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.pptx) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.pptx)), Word ([1](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.docx) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.docx)).
- Open Container Format: Epub ([1](https://github.com/corkami/collisions/blob/HEAD/examples/collision-1.epub) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/collision-2.epub)).
- Open Packaging Conventions: 3MF ([1](https://github.com/corkami/collisions/blob/HEAD/examples/collision-1.3mf) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/collision-2.3mf)), XPS ([1](https://github.com/corkami/collisions/blob/HEAD/examples/collision-1.xps) - [2](https://github.com/corkami/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)님께 감사드립니다!

### 기타

- Wasm, 사용자 정의 섹션을 통한 경우: [스크립트](https://github.com/corkami/collisions/blob/HEAD/scripts/wasm.py), 예시: [md5-1.wasm](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.wasm) ⟷ [md5-2.wasm](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.wasm)


## 비일반적인 전략

충돌은 대개 동일한 유형의 두 유효한 파일에 관한 것입니다.

### MultiColls: 다중 충돌 체인

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

#### Hashquines

Hashquines는 자신의 해시 값을 보여주는 파일입니다. [여기](https://github.com/corkami/collisions/blob/HEAD/hashquines/)에서 다룹니다.

### 유효성

다른 전략은 파일 유형을 무력화시켜 손상된 파일로 스캔을 우회하는 것입니다.
매직 시그니처를 덮어쓰는 것만으로 충분합니다.
오프셋 0에 위치할 필요가 없는 형식(아카이브, 예: ZIP/RAR/...)으로 두 파일(유효하든 무효하든)을 추가하면 다른 파일 유형이 드러납니다.

이는 선택-프리픽스 충돌 없이 폴리글롯 충돌을 가능하게 합니다:
1. UniColl을 사용하여 매직 시그니처를 활성화 또는 비활성화합니다 (예: PNG).
2. ZIP 아카이브를 추가합니다.

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

예시:

 ⟷ [무효](https://github.com/corkami/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/47471/3dcd55e877a4ce9c933bf1478d0a71ede85e129b9e746414d754ffabceabe463.png)

*PDF/JPG 폴리콜*


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

*PE/PNG 폴리콜*


#### PE - JPG

PE 헤더는 보통 0x500바이트보다 작기 때문에 JPG 주석에 완벽하게 들어맞습니다:
1. DOS/JPG 헤더로 시작
2. JPEG 주석이 PE 헤더를 건너뜀
3. 전체 JPG 이미지를 배치
4. 전체 PE 사양을 배치

다시 한번, 충돌은 [즉시](https://github.com/corkami/collisions/blob/HEAD/scripts/jpgpe.py) 생성됩니다.

예시: [fastcoll.exe](https://github.com/corkami/collisions/blob/HEAD/examples/jpg-pe.exe) ⟷ [Marc.jpg](https://github.com/corkami/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/corkami/collisions/blob/HEAD/scripts/pdfpe.py)가 있습니다:

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

![동일한 MD5를 가진 PDF(자신도 PDF를 표시)를 표시하는 PDF 뷰어](https://assets.kitploit.com/production/public/readmes/47471/4356d710fc4b60297ee05999be64f596198e9d4a02c826666818eb8ae117310f.png)

*동일한 MD5를 가진 PDF(자신도 PDF를 표시)를 표시하는 PDF 뷰어*

#### PDF - PNG

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

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

### PileUps (다중 충돌)

암호화 충돌은 두 파일로 제한되지 않습니다!

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

첫 번째 충돌은 동일하거나 선택-프리픽스일 수 있고, 다음 충돌은 선택-프리픽스여야 합니다.

다중 충돌이라고 부를 수도 있지만, 저는 *pileup*이 더 짧아서 선호합니다 :)

#### PE - PNG - MP4 - PDF

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

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

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

이 스크립트는 일반적이며 즉시 사용 가능합니다:

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

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

단일 파일만 배포할 수 있고 그 파일로부터 다른 프리픽스 값을 추측하는 것은 불가능하므로,
충돌의 모든 프리픽스를 JavaScript 코드에 포함하고 PoC에 삽입하는 것이 해결책입니다.
이렇게 하면 파일이 [HTML 폴리글롯](https://github.com/corkami/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/)의 짧은 'collision' 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

**TL;DR** 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-based (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/corkami/collisions/blob/HEAD/examples/free/README.md)에 무료(저작권 없음, 개인정보 없음) 테스트 충돌 쌍이 있습니다.

# 탐지

파일에서 해시 충돌을 탐지하는 방법에는 여러 가지가 있습니다.

1. 두 파일: 서로 다른 내용과 동일한 해시를 가진 파일이 두 개 이상 있다면, 그냥 diff를 해보세요!

그러나 파일이 하나만 있는 경우 파일에 해시 충돌이 포함되어 있는지 알기 어려울 수 있습니다.

2. 파일 구조: 블록 경계에서 파일을 분석하고, 높은 엔트로피 블록이나 동일한 프리픽스/접미사가 발견되면 어떤 충돌을 사용하는지 알 수 있을 수도 있지만 매우 오류가 발생하기 쉽습니다. 선택-프리픽스 충돌의 경우, 두 파일이 대부분의 충돌 블록 외에는 서로 다를 수 있으므로 발견하는 것이 불가능할 수도 있습니다.

3. 해시 계산: Marc Stevens의 DetectColl(그의 [Counter-cryptanalysis](https://marc-stevens.nl/research/papers/C13-S.pdf) 논문 참조)의 ([C](https://github.com/cr-marcstevens/hashclash/tree/collisiondetection/src/collisiondetection) 또는 [Go](https://github.com/therealmik/detectcoll)) 구현을 사용하세요. 파일 하나만 필요하지만 충돌이 작동 상태(정확한 프리픽스와 해당 충돌 블록)여야 하며 느립니다.

DetectColl은 충돌 자체에 대한 기술적 정보를 제공하고 충돌된 해시 옆에 `*coll*`을 표시합니다.

## 예시

Flame 악성코드 인증서를 사용한 경우:```
$ detectcoll flame.der
Found collision in block 11:
   dm: dm4=80000000 dm11=ffff8000 dm14=80000000
   ihv1=1ba33aac3a7f9ed70aec349b40390e85
   ihv2=9ba33aac3c7f60ee8cebf69bc2391085
*coll* c38a66643af816f8438b375b5f42ccbb flame.der
ba2499ba3dda9ef818f854b75a2bd1cd9f2b7bed flame.der
```
## 안전한 해시

Detectcoll은 해시 충돌에 사용되는 블록을 식별할 수 있으므로 *안전한 해시(safe hashes)*를 통해 충돌을 완화할 수 있습니다. 즉, 충돌 블록이 감지되면 충돌 속성을 깨기 위해 해당 블록을 다시 처리합니다. 따라서 DetectColl은 파일 내 충돌이 있음에도 불구하고 동일한 해시 함수로 서로 다른 내용을 구분할 수 있습니다.

요약하면:
- 충돌이 없는 파일의 경우 안전한 해시 값은 표준 해시 값과 동일합니다.
- 충돌이 있는 파일의 경우 안전한 해시는 다르지만, 충돌에도 불구하고 서로 다른 파일 내용에 대해서도 달라집니다.

2005년 Wang의 원본 충돌을 사용한 예:```
$ md5sum wang*
79054025255fb1a26e4bc422aef54eb4 *wang1.bin
79054025255fb1a26e4bc422aef54eb4 *wang2.bin
```
이 파일들에 대한 안전한 MD5:```
$ detectcoll wang1.bin | grep coll
*coll* ff531291d102a41aa131e0e09f64ca60 wang1.bin
```
I'm unable to produce a translation because the source text for this chunk was not included in the message. Please provide the content to translate.```
$ detectcoll wang2.bin | grep coll
*coll* 6a8e7124724d5c819401afc202a4fbd0 wang2.bin
```
## 시그니처

편의상 이 [스크립트](https://github.com/corkami/collisions/blob/HEAD/scripts/logparse.py)로 Detectcoll 출력을 파싱하고 [알려진 시그니처](https://github.com/corkami/collisions/blob/7f7876c431614f33f765bfc1cb62506b476a2eb0/scripts/logparse.py#L15-L24)와 더 쉽게 매칭할 수 있습니다:``` shell
$ detectcoll_unsafe * | ./logparse.py
apop-1.bin
block: 2, collision: APop
cpc1.bin
block: 9, collision: HashClashCPC
fastcoll1.bin
block: 2, collision: FastColl
single-cpc1.bin
block: 1, collision: SingleCPC
single-ipc1.bin
block: 0, collision: SingleIPC
wang1.bin
block: 1, collision: FastColl
pileup.exe
block: 10, collision: HashClashCPC
block: 20, collision: HashClashCPC
04-unicoll-1.bin
block: 1, collision: Unicoll1
05-uc-n2-1.bin
block: 1, collision: Unicoll2
05-uc-n3-1.bin
block: 1, collision: Unicoll3
05-uc-n3-2.bin
block: 1, collision: Unicoll3
12-shattered1.bin
block: 3, collision: SHAttered/Shambles
block: 4, collision: SHAttered/Shambles
13-shambles1.bin
block: 9, collision: SHAttered/Shambles
13-shambles2.bin
block: 9, collision: SHAttered/Shambles
ca-rogue.der
block: 10, collision: HashClashCPC
flame.der
block: 11, collision: Flame
```
### Multiple collisions

안전한 해시의 사소한 단점은 동일한 파일에서 여러 충돌을 감지하지 못한다는 점이지만, DetectColl은 여전히 '표준' 해시로 충돌을 감지할 수 있습니다.

PoCorGTFO 0x14(대체 표지 그림이 있는 NES+PDF hashquine)를 사용한 예시.

안전한 해시는 하나의 충돌만 찾을 수 있습니다:```
$ detectcoll_safe pocorgtfo14.pdf
Found collision in block 135:
   dm: dm4=80000000 dm11=ffff8000 dm14=80000000
   ihv1=73b615bd01d5e48032d3d1a549d0f956
   ihv2=f3b615bd83d5e480b4d3d1a5cbd0f956
*coll* c4b085f9fa4b38669fa79d4c410538e9 pocorgtfo14.pdf
eb5d0fb7607c1262236a5a7f591bb510ee9afbbc pocorgtfo14.pdf   
```
안전하지 않은 해시들은 모두 찾습니다:```
$ detectcoll_unsafe pocorgtfo14.pdf | grep Found | wc -l
609
```
마지막 몇 개의 충돌을 확인해 보면:```
$ detectcoll_unsafe pocorgtfo14.pdf | tail | grep Found
Found collision in block 34169:
Found collision in block 34250:
Found collision in block 34324:
Found collision in block 34389:
Found collision in block 34456:
Found collision in block 34523:
Found collision in block 34585:
Found collision in block 34738:
```
마지막 것은 이전 것들과 그렇게 유사하지 않다는 것을 알 수 있습니다:
그 이유는 이전 것들은 hashquines용 동일한 이미지 파일에 속하지만,
마지막 것은 대체 표지용이기 때문입니다.


# 참고 자료

논문(파일 포맷 악용 관련):

- 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/corkami/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/47471/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/47471/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/corkami/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)는 *Hack.lu CTF 2017*의 과제입니다: 충돌과는 관련이 없지만 Marc 자신이 해결했습니다 :p -->
이러한 CTF 과제들의 공통적인 난제는 각 플레이어가 사용할 수 있는 컴퓨팅 성능의 양에 따라 너무 큰 이점이나 불리함을 주지 않도록 하는 것입니다.


# 크레딧

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

또한 일반적인 파일 포맷에 대한 폭넓은 피드백을 제공한 Philippe Teuwen에게도 감사드립니다.


# 결론

**Kill MD5!**

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

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

<!-- pandoc -s -f gfm -t html README.md -o README.html -->