# 攻撃

MD5 と SHA1 は 64 バイトのブロックで動作します。

2 つのコンテンツ A と B が同じハッシュを持つ場合、両方に同じコンテンツ C を追加しても、ハッシュは同じままになります。``` text
hash(A) = hash(B) -> hash(A + C) = hash(B + C)

同一プレフィックスを持つ他の例: [1](https://github.com/corkami/collisions/blob/master/examples/fastcoll1.bin) ⟷ [2](https://github.com/corkami/collisions/blob/master/examples/fastcoll2.bin)

**バリアント**: [単一ブロックMD5衝突](https://marc-stevens.nl/research/md5-1block-collision/) もありますが、計算に5週間かかります。

プレフィックスなしの FastColl 計算の[記録](https://github.com/corkami/collisions/blob/master/examples/fastcoll.svg)はこちら、
プレフィックス付きの[別の記録](https://github.com/corkami/collisions/blob/master/examples/fastcoll-prefix.svg)はこちらです。


### [UniColl](https://github.com/corkami/collisions/blob/master/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) では、衝突ブロック内の数バイトを制御できます。
最初の差分の前後で制御できるため、一部を制御可能な差分を持つ同一プレフィックス衝突となり、ほぼ選択プレフィックス衝突に近いものになります。
これは非常に便利で、さらに良いことに差分は非常に予測可能です:
`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` に置き換わります..

- 時間: 数分（制御したいバイト数に依存します ）
- スペース: 2ブロック
- 差分:   ```
   .. .. .. .. DD .. .. .. ..
   .. .. .. .. +1 .. .. .. ..

UniColl は真の選択プレフィックス衝突よりも制御は劣りますが、特に2ブロックのみで済むため、はるかに高速です。

こちらが UniColl 計算の[録画](https://github.com/corkami/collisions/blob/master/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
- スペース: 2ブロック
- 差分:  ```
  .. .. .. DD ?? ?? ?? ??
  or
  ?? ?? ?? DD .. .. .. ..

例: [PoC||GTFO 0x18](https://github.com/angea/pocorgtfo#0x18) は、計算された SHA1 プレフィックスを使用し、
PDFLaTeX ソースから画像を直接再利用しています（[article 18:10](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up) 参照）。
また、HTML ページ内の JavaScript を介してプレフィックスの値をチェックしています（このファイルはポリグロットであり、ZIP、HTML、PDF です）。


## 選択プレフィックス衝突

これにより、任意のコンテンツを衝突させることができます。

| 𝓐            | ≠ | 𝔅             |
| :----:        |:-:| :----:        |
| 衝突 *A* | ≠ | 衝突 *B* |

1. 任意のプレフィックスを2つ取ります。
2. 短い方を最長のものと同じ長さまでパディングします。両方とも次のブロック - 12バイトまでパディングされます。
  - この12バイトのランダムデータは、誕生日探索をランダム化するために両側に追加されます。
3. X個の近衝突ブロックが計算され、追加されます。

   ブロック数が少ないほど、計算時間は長くなります。

   例: [1ブロックに400 kHours](https://www.win.tue.nl/hashclash/SingleBlock/)。[HashClash](https://github.com/cr-marcstevens/hashclash) では9ブロックに72コア時間。



選択プレフィックス衝突は非常に強力ですが、1組のファイルだけでも長い時間がかかることがあります。


### [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

しかし、Shattered が FastColl よりもはるかに悪用しやすいとしても、
衝突ブロックの差分に関する制約は無関係です。
Shambles は Chosen Prefix Collision であるためです。

## 攻撃の概要

ハッシュ | 名前      | 日付 | 所要時間 | プレフィックス種別 | 差分付近の制御
---- | --------- | ---- | -------- | ----------- | -----------------
MD5  | FastColl  | 2009 | 2s       | 同一   | なし
     | UniColl   | 2012 | 7-40分  | 同一   | 4-10バイト
     | HashClash | 2009 | 72h      | 選択      | n/a
     |           |      |          |             |                   
SHA1 | Shattered | 2013 | 6500年   | 同一   | プレフィックス & サフィックス
     | Shambles  | 2020 | ?        | 選択      | n/a

# 悪用

同一プレフィックス衝突は通常、（非常に）限定的と見なされますが、選択プレフィックスは時間がかかります。

別のアプローチは、UniColl のような同一プレフィックス攻撃、またはいくつかの制限を克服するための選択プレフィックス攻撃を介して再利用可能なプレフィックスを作成し、そのプレフィックスのペアを古典的な同一プレフィックス攻撃のように2つのペイロードと組み合わせて再利用することです。

プレフィックスペアが計算されると、2つのコンテンツの衝突は即座に行えます。
後は、特定のファイル形式に従ってファイルデータを調整し、ファイル形式の仕様と事前計算されたプレフィックスの要件に適合させるだけです。

## 標準的な戦略

同じファイルタイプを持つ2つの有効なファイルの古典的な衝突。

### JPG



理論上の制限と回避策：
- *Application* セグメントは理論上、*Start of Image* マーカーの直後にあるべきです。
  実際にはこれは必須ではないため、衝突を汎用的にできます。唯一の制限は、最も小さい画像のサイズです。
- コメントの長さは2バイトに格納されるため、保存できる量は65536バイト（およそ400x400の写真のサイズ）に制限されます。
- 完全なJPGファイルをスキップするのではなく、そのファイルをセグメントに分割し、セグメント間にジャンプ用トランポリンを追加することができます。

  

  *各画像セグメント上のコメント*

  

  *コメントのトランポリンがどのように機能するか*

- JPG構造のほとんどは、サイズがすべて65536バイトに制限されたセグメントで構成されていますが、
  実際の圧縮データは *Entropy Coded Segment* に格納されており、この制限に従いません。
  そのサイズは事前に不明で、その制限を超えて増加します。
  画像のサイズとともに増加し、ベースライン（非プログレッシブ）画像ではファイルサイズの大部分を占めます。
  画像全体を64kbチャンクに収める簡単な方法は、まず画像をプログレッシブとして保存することです（これはどのソフトウェアでもでき、通常最大6つのスキャンにECSを分割します）。
  より高度な方法は、*JPEGTran* を 'wizard' `--scans` コマンドラインパラメータとともに使用し、カスタムスキャンを定義することです。

スキャンセグメント以外に制約はないため、
任意の2つのJPGのMD5衝突は *即時* であり、選択プレフィックス衝突は不要で、UniCollだけで十分です。

[スクリプト](https://github.com/corkami/collisions/blob/master/scripts/jpg.py) を使うと:```
21:07:35.65>jpg.py Ange.jpg Marc.jpg

21:07:35.75>

結果:



*1944x2508のRGB画像（100% JPG、20回スキャン）*


### PNG



理論上の制限と回避策:
- PNGはチャンクの末尾にCRC32を使用しますが、実際には無視されます。正しい値を入れることもできますが、必須ではありません。
- 画像のメタデータ（寸法、色空間など）は`IHDR`チャンクに格納されます。
  このチャンクは理論的にはシグネチャの直後（つまり、潜在的なコメントの前）にあるべきですが、
  そのため、同じメタデータを持つ画像の衝突のみを事前計算できることになります。
  しかし、実際にはそのチャンクはコメントブロックの後ろに置くことができます（Apple製を除く大多数のリーダーで）。したがって、衝突データをヘッダの前に置くことができ、
  単一の事前計算で任意のPNGペアを衝突させることができます。

PNGチャンクの長さは4バイトで表されるため、どちらかのファイルの構造を変更する必要はありません。一気に画像全体を飛び越えることができます。

破棄チャンクは必要なだけ挿入できるため、アライメント用に1つ追加し、次にUniCollによって長さが変更されるチャンクを1つ追加できます。そのため、長さは`00` `75`と`01` `75`になります。

つまり、任意の2つのPNG画像のMD5衝突は*即時*であり、前提条件はありません（計算は不要で、わずかなファイル変更のみです）。また、選択プレフィックス衝突は必要なく、UniCollだけで済みます。

この[スクリプト](https://github.com/corkami/collisions/blob/master/scripts/png.py)を使うと:```
19:27:04.79>png.py nintendo.png sega.png

19:27:04.87>

は次と同等です：``` 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>>

例: [poeMD5 A](https://github.com/corkami/collisions/blob/master/examples/poeMD5_A.pdf) ⟷ [poeMD5 B](https://github.com/corkami/collisions/blob/master/examples/poeMD5_B.pdf)



*真の暗号学的芸術作品 :)*

(注: Adobe互換性のところでやらかしましたが、それは私のミスであり、UniCollのせいではありません)


**ドキュメント構造を衝突させる**

UniCollをインラインコメントとして使うか、ダミーストリームオブジェクト内の選択プレフィックスとして使うかにかかわらず、戦略は同様です:
オブジェクト番号をシャッフルし、Rootオブジェクトが異なるオブジェクトを指すようにします。このため、Shatteredとは異なり、任意のPDFペアをドキュメントレベルで即座に衝突させることができます。

便利なトリックとして、[`mutool clean`](https://mupdf.com/docs/manual-mutool-clean.html) の出力は確実に予測可能です。
そのため、入力を正規化するために使用したり、ファイルの重要な部分を変更せずにマージ済みPDFを修正したりできます。
MuToolは、要求しない限り偽のキー/値を破棄せず、同じ順序で保持します。
したがって、`/MD5_is /REALLY_dead_now__` のような偽の辞書エントリを使うことは、他の種類のコメントを必要とせずに物事を予測可能に整列させるのに最適です。
ただし、辞書内のコメントは保持されないため、インラインコメントのトリックは使えません。

オブジェクトのシャッフル操作を手間なく行う簡単な方法は、両方のPDFファイルをマージすることです
`mutool merge` を使用してから、`/Pages` オブジェクトを2つに分割します。

このオブジェクトのためのスペースを確保するには、2つのドキュメントの前にダミーPDFをマージするだけです。

必要に応じて、ダングリング配列への偽の参照を作成し、
ガベージコレクションが2番目のページセットを削除しないようにします。


**例**:
この [スクリプト](https://github.com/corkami/collisions/blob/master/scripts/pdf.py) を使えば、
Spectre や Meltdown のような公開PDF論文2件を衝突させるのに [1秒未満](https://github.com/corkami/collisions/blob/master/examples/pdf.log) しかかかりません:

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



可能な拡張: UniCollブロックを連鎖させて、[非クリティカルオブジェクト](https://www.adobe.com/content/dam/acom/en/devnet/pdf/pdfs/PDF32000_2008.pdf#page=81) のペアも保持します。
これらはRootオブジェクトで参照できます - 元のソースファイル内の `Outlines`、`Names`、`AcroForm`、および追加アクション (`AA`) などです。

**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

これを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..(

これはまったく汎用的ではありませんが、chosen-prefix collision よりはるかに高速です：```
real 12m23.993s
user 112m24.072s
sys 2m0.194s

したがって、ルートファイルの内容を事前定義し、ASCII CRC32を偽造することで、特定のzipベース形式に対して、再利用可能な汎用Hashclash衝突を計算できます。


### 要件の概要

- 2つ以上のプレフィックス
- 1つ以上のファイルタイプ（ポリグロットは問題なく動作します）
- 固定のファイル名、ファイル長、CRCを持つXMLルートファイル：この情報は衝突ブロックの前後に2回存在します
 - 内容は任意のXMLです
 - 同じ長さにするために、XMLコメントを使ったパディングも可能です。
 - CRCは各コンテンツに（CrcHack経由で）設定できます。
- 両方のファイルセットはサフィックス内に共存し、おそらく異なるディレクトリにあります。一部のツールはパスをハードコードするため、互換性が低下する可能性があります。
- サポート対象および非対象のすべてのファイル（衝突ブロックと代替ドキュメント）をカバーするには、*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-->

#### 衝突

[zInsider](https://github.com/corkami/collisions/blob/master/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/corkami/collisions/blob/master/scripts/makezip.py)。
衝突を計算した後、[この別のスクリプト](https://github.com/corkami/collisions/blob/master/scripts/extendzip.py)を使用して、これらのルートペアを共通のサフィックスと組み合わせます。

衝突 PoC の例:
- Office Open XML: Excel ([1](https://github.com/corkami/collisions/blob/master/examples/free/md5-1.xls) - [2](https://github.com/corkami/collisions/blob/master/examples/free/md5-2.xls)), Powerpoint ([1](https://github.com/corkami/collisions/blob/master/examples/free/md5-1.pptx) - [2](https://github.com/corkami/collisions/blob/master/examples/free/md5-2.pptx)), Word ([1](https://github.com/corkami/collisions/blob/master/examples/free/md5-1.docx) - [2](https://github.com/corkami/collisions/blob/master/examples/free/md5-2.docx))。
- Open Container Format: Epub ([1](https://github.com/corkami/collisions/blob/master/examples/collision-1.epub) - [2](https://github.com/corkami/collisions/blob/master/examples/collision-2.epub))。
- Open Packaging Conventions: 3MF ([1](https://github.com/corkami/collisions/blob/master/examples/collision-1.3mf) - [2](https://github.com/corkami/collisions/blob/master/examples/collision-2.3mf)), XPS ([1](https://github.com/corkami/collisions/blob/master/examples/collision-1.xps) - [2](https://github.com/corkami/collisions/blob/master/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/master/scripts/wasm.py)、例: [md5-1.wasm](https://github.com/corkami/collisions/blob/master/examples/free/md5-1.wasm) ⟷ [md5-2.wasm](https://github.com/corkami/collisions/blob/master/examples/free/md5-2.wasm)


## 特殊な戦略

衝突は通常、同じタイプの2つの有効なファイルに関するものです。


### MultiColls: 多重衝突チェーン

複数の衝突ブロックをチェーンすることを妨げるものは何もなく、
同じハッシュ値を持つ2つ以上のコンテンツを持つことができます。
その例が *hashquines* です。これは自分自身の MD5 値を示します。
[PoCGTFO 14](https://github.com/angea/pocorgtfo#0x14) ファイルには 609 個の FastColl 衝突が含まれており、
同じファイル内の2つのファイルタイプを通じてそれを実現しています。


#### Hashquines

Hashquines は、自分自身のハッシュ値を表示するファイルです。それらは[ここ](https://github.com/corkami/collisions/blob/master/hashquines)で説明されています。


### 有効性

別の戦略として、破損したファイルとしてスキャンされるのを回避するために、ファイルタイプを無効化する方法があります。
マジックシグネチャを上書きするだけで十分です。
オフセット 0 にある必要のない形式（ZIP/RAR/... などのアーカイブ）を両方のファイル（有効または無効として）に追加すると、
別のファイルタイプが明らかになります。

これにより、選択プレフィックス衝突を使用せずにポリグロット衝突が可能になります:
1. UniColl を使用してマジックシグネチャを有効または無効にします。たとえば PNG:
2. ZIP アーカイブを追加します

技術的には両方のファイルが有効な ZIP ですが、ほとんどのパーサーは最初に見つかったファイルタイプを返し、オフセット 0 からスキャンを開始するため、異なるファイルタイプとして認識されます。

例:

 ⟷ [無効](https://github.com/corkami/collisions/blob/master/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/master/scripts/jpgpe.py)です。

例: [fastcoll.exe](https://github.com/corkami/collisions/blob/master/examples/jpg-pe.exe) ⟷ [Marc.jpg](https://github.com/corkami/collisions/blob/master/examples/jpg-pe.jpg)


#### PDF - PE

`mutool` を使用して PDF をダミーファイルとマージすることは、オブジェクトを並べ替え、
最初の2つのオブジェクトを破棄可能にする（ダミーページとコンテンツ）ための優れた汎用的な方法です。
これは、未知の長さの `stream` オブジェクトを `1 0` としてホストし、
その長さを2番目のオブジェクト内で（衝突ブロックの後に）参照するのに最適です。

唯一の問題は、`mutool` が常に長さをインライン化し、長さ参照を削除することです。
そのため、値の代わりに PDF に再挿入する必要がありますが、
ほとんどの参照 `2 0 R` はハードコードされた長さよりも小さくなります。
ありがたいことに、これはオブジェクトオフセットを変更せずに修正できるため、
XREF をパッチする必要はありません。

たとえば、PDF ビューア（[Sumatra](https://www.sumatrapdfreader.org/free-pdf-reader.html) は軽量でスタンドアロン）と PDF ドキュメントを即座に衝突させる[スクリプト](https://github.com/corkami/collisions/blob/master/scripts/pdfpe.py)があります:

例: [Poster.pdf](https://github.com/corkami/collisions/blob/master/examples/pepdf.pdf) ⟷ [Sumatra.exe](https://github.com/corkami/collisions/blob/master/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/master/examples/png-pdf.pdf) ⟷ [1x1.png](https://github.com/corkami/collisions/blob/master/examples/png-pdf.png)


### PileUps (多重衝突)

暗号学的衝突は2つのファイルに限定されません!

2008 年の [Nostradamus](https://www.win.tue.nl/hashclash/Nostradamus/) 実験で実証されたように、
衝突を連鎖させることで、2つ以上のファイルを衝突させることが可能になります。

最初の衝突は同一または選択プレフィックスにすることができますが、次の衝突は選択プレフィックスでなければなりません。

マルチコリジョンと呼んでも構いませんが、私は *pileups* の方が好きです。より短いので :)


#### PE - PNG - MP4 - PDF

これまでに得たすべての知識を組み合わせて、
3 つの選択プレフィックス衝突を使用して、異なるファイルタイプ用の 4 つの異なるプレフィックスを作成しました:
ドキュメント (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/master/examples/pileup.pdf) ⟷ [diagram.png](https://github.com/corkami/collisions/blob/master/examples/pileup.png) ⟷ [kidmo.mp4](https://github.com/corkami/collisions/blob/master/examples/pileup.mp4) ⟷ [sumatra18.exe](https://github.com/corkami/collisions/blob/master/examples/pileup.exe)


単一のファイルのみを配布する場合、
そこから他のプレフィックス値を推測することは不可能なため、
解決策として、衝突のすべてのプレフィックスを JavaScript コードに埋め込み、
それを PoC に挿入して、
ファイルを [HTML ポリグロット](https://github.com/corkami/collisions/blob/master/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 を持つファイルとして明らかになります。

2つのファイルを例に取りましょう:

 ⟷


そして、それらを同じ PNG と衝突させます。

これで、それらは同じダミー画像を表示し、ファイルレベルで2番目の画像まで完全に同一です!

 ⟷


それぞれの悪意のあるペイロードは、同じ MD5 を持つファイルの背後に隠れています。


### 有罪を示すファイル

衝突の別のユースケースは、無実だが望ましい何かの内部に有罪を示す何かを隠すことです。
証拠を収集する唯一の方法が弱いハッシュの比較である場合、
もう一方のファイル（有罪を示すコンテンツを表示し、無実のコンテンツを隠している）を持っていないと否定することはできません。

ソフトウェアは通常、（迅速な）パーシングに重点を置いており、詳細なファイル分析には重点を置いていません。



*EnCase Forensic の異なるタブの下での異なるプレビューを示す画像*


## 失敗

すべての形式が再利用可能な汎用プレフィックスを持てるわけではありません。
マジックシグネチャと、各ファイルに固有で重要な標準ヘッダーの間に
何らかのデータホルダーを挿入できない場合、
汎用衝突は不可能です。

もちろん、古いファイルを新しいファイルに変換したり、
コードを使用して2つの異なるペイロードに分岐させたりすることは可能ですが、
それはファイル構造の衝突というよりは、ペイロードの移植に近いものです。


### 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 は完全なアーカイブに 2 つの UniColl を必要とし、この衝突は両方のファイルのコンテンツに依存します。


## テストファイル

[ここ](https://github.com/corkami/collisions/blob/master/examples/free/README.md)に、フリー（著作権フリー、PII フリー）のテスト用衝突ペアがあります。


# 検出

ファイル内のハッシュ衝突を検出するには、さまざまな方法があります。

1. 2つのファイル: 異なるコンテンツと同じハッシュを持つ2つ以上のファイルがある場合は、差分を取るだけです!

ただし、単一のファイルしかない場合、そのファイルにハッシュ衝突が含まれているかどうかを判断するのは難しい場合があります。

2. ファイル構造: ブロック境界でファイルを分析し、高エントロピーのブロックや、場合によっては同一のプレフィックス/サフィックスに気付いた場合、使用されている衝突を特定できるかもしれませんが、非常にエラーが発生しやすいです。選択プレフィックス衝突の場合、衝突ブロックのほとんどを除いて両方のファイルがほとんど異なる可能性があるため、発見することは不可能かもしれません。

3. ハッシュ計算: Marc Stevens の DetectColl の実装（[C](https://github.com/cr-marcstevens/hashclash/tree/collisiondetection/src/collisiondetection) または [Go](https://github.com/therealmik/detectcoll)）を使用します（彼の [Counter-cryptanalysis](https://marc-stevens.nl/research/papers/C13-S.pdf) 論文を参照）。これには1つのファイルしか必要ありませんが、衝突が機能している状態（正確なプレフィックスとそれに対応する衝突ブロック）である必要があり、低速です。

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

これらのファイルの安全なMD5:```
$ detectcoll wang1.bin | grep coll
*coll* ff531291d102a41aa131e0e09f64ca60 wang1.bin

$ detectcoll wang2.bin | grep coll
*coll* 6a8e7124724d5c819401afc202a4fbd0 wang2.bin
```
## シグネチャ

簡単のため、Detectcoll の出力をこの[スクリプト](https://github.com/corkami/collisions/blob/master/scripts/logparse.py)で解析し、[既知のシグネチャ](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
```
### 複数の衝突

セーフハッシュの小さな欠点は、同じファイル内で複数の衝突を検出できないことですが、DetectCollは「standard」ハッシュを使用した衝突を依然として検出できます。

PoCorGTFO 0x14（代替カバー画像付きのNES+PDFハッシュクワイン）の例。

セーフハッシュは1つの衝突しか見つけることができません：```
$ 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はいつか有害と見なされるであろう](https://eprint.iacr.org/2004/357.pdf) - Dan Kaminsky
  - [MD5メッセージダイジェストを用いたデジタル署名への実用的攻撃](https://eprint.iacr.org/2004/356.pdf) - Ondredj Mikle 
- 2005：
  - [特殊なファイル形式に対する単一ハッシュ衝突の実用的価値に関するノート](https://github.com/corkami/collisions/blob/master/papers/Illies_NIST_05.pdf) - Max Gebhardt, Georg Illies, Werner Schindler
- 2014：
  - [悪意あるハッシュ：Eve版SHA-1](https://malicioussha1.github.io/) - Ange Albertini, Jean-Philippe Aumasson, Maria Eichlseder, Florian Mendel, Martin Schläffer
- 2017：
  - [完全なSHA-1に対する最初の衝突](http://shattered.io) - Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov
  - [自身のMD5を表示するPostscript](https://archive.org/stream/pocorgtfo14#page/n45/mode/1up) 著：Gregor "Greg" Kopf
  - [自身のMD5を表示するPDF](https://archive.org/stream/pocorgtfo14#page/n49/mode/1up) 著：Mako
  - [このGIFは自身のMD5を表示します！](https://archive.org/stream/pocorgtfo14#page/n52/mode/1up) 著：Kristoffer "spq" Janke
  - [このPDFは自身のMD5ハッシュを出力するNES ROMです！](https://archive.org/stream/pocorgtfo14#page/n55/mode/1up) 著：Evan Sultanik, Evan Teran
- 2018：
  - [PDFLaTeXで簡単にSHA-1衝突PDFを作成する。](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up) 著：Ange Albertini
- 2020：
  - [SHA-1はShambles](https://eprint.iacr.org/2020/014.pdf) 著：Gaëtan Leurent, Thomas Peyrin

発表：
- 2017 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 Pass the SaltでのKILL MD5：
  - [スライド](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/master/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にも感謝します。


# 結論

**MD5を殺せ！**

ファイル内の異常や衝突ブロックを積極的にチェックしない限り、MD5を使うな！

それは暗号学的ハッシュではなく、おもちゃの関数だ！

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