TL;DR получение MD5-коллизии этих двух изображений теперь(*) тривиально и мгновенно.

Не играйте с огнём, не полагайтесь на MD5.

(*) Создание коллизии для любой пары файлов возможно уже много лет, но каждый раз это занимает несколько часов, без возможности ускорить процесс. На этой странице приведены приёмы, специфичные для форматов файлов, и предвычисленные префиксы коллизий, чтобы сделать коллизию мгновенной. git clone. Запустите скрипт. Готово.

Хэш-коллизии и их эксплуатация

Авторы: Ange Albertini и Marc Stevens.

Введение
Статус
Атаки
Эксплуатация
Ссылки
Благодарности
Заключение

Введение

Цель — всесторонне исследовать существующие атаки и заодно показать, насколько слаб MD5 (мгновенные коллизии для любых JPG, PNG, PDF, MP4, PE...) — а также детально изучить распространённые форматы файлов, чтобы определить, как их можно эксплуатировать с помощью текущих или будущих атак.

Действительно, один и тот же приём с форматом файла можно применить к нескольким хэшам (те же приёмы с JPG использовались для MD5, malicious SHA-1 и SHA1), если коллизии следуют одним и тем же байтовым шаблонам.

Этот документ не о новых атаках (самая свежая была задокументирована в 2012 году), а о новых формах эксплуатации существующих атак.

Статус

Текущий статус известных атак — по состоянию на декабрь 2018 года:

получить файл, соответствующий хэшу другого файла или заданному хэшу: невозможно
- это даже непрактично с MD2.
- работает для более простых хэшей(*)
получить два разных файла с одинаковым MD5: мгновенно
- примеры: 1 ⟷ 2
сделать так, чтобы два произвольных файла имели одинаковый MD5: несколько часов (72 hours.core)
- примеры: 1 ⟷ 2
сделать так, чтобы два произвольных файла определённых форматов (PNG, JPG, PE...) имели одинаковый MD5: мгновенно
- читайте ниже
получить два разных файла с одинаковым SHA1: 6500 years.core
- получить два разных PDF с одинаковым SHA-1, показывающих разные изображения: мгновенно (префиксы уже вычислены)

(*) пример с crypt — спасибо Sven!```

import crypt crypt.crypt("5dUD&66", "br") 'brokenOz4KxMc' crypt.crypt("O!>',%$", "br") 'brokenOz4KxMc'

# Атаки

MD5 и SHA1 работают с блоками по 64 байта.

Если два содержимых A и B имеют одинаковый хэш, то добавление одного и того же содержимого C к обоим сохранит одинаковый хэш.``` text
hash(A) = hash(B) -> hash(A + C) = hash(B + C)

Коллизии работают путём вставки на границе блока нескольких вычисленных блоков коллизий, количество которых зависит от того, что было в файле ранее. Эти блоки коллизий выглядят очень случайными, но с незначительными различиями (которые следуют определённому шаблону для каждой атаки) и они вносят крошечные различия, в конечном итоге приводя к одинаковому значению хеша после этих блоков.

Эти различия используются для создания корректных файлов с определёнными свойствами.

Форматы файлов также работают сверху вниз, и большинство из них работает с чанками на уровне байтов.

Некоторые «комментарные» чанки можно вставлять, чтобы выровнять чанки файла по границам блоков, выровнять конкретные структуры по различиям блоков коллизий, скрыть остальную случайность блоков коллизий от парсеров файлов, и скрыть иное корректное содержимое от парсера (чтобы он видел другое содержимое).

Эти «комментарные» чанки часто не являются официально настоящими комментариями: они просто используются как контейнеры данных, которые игнорируются парсером (например, PNG-чанки с ID, начинающимся со строчной буквы, являются вспомогательными, а не критическими).

В большинстве случаев различие в блоках коллизий используется для изменения длины комментарного чанка, которая обычно объявляется непосредственно перед данными этого чанка: в промежутке между меньшей и большей версиями этого чанка объявляется ещё один комментарный чанк, чтобы перепрыгнуть через содержимое одного файла A. После этого содержимого файла A просто добавьте другое содержимое файла B.

Поскольку форматы файлов обычно определяют терминатор, после которого парсеры останавливаются, A завершит разбор, из-за чего добавленное содержимое B будет проигнорировано.

Поэтому обычно требуется как минимум два комментария — часто три:

выравнивание
скрытие блоков коллизий
скрытие содержимого одного файла (для повторно используемых коллизий)

Эти общие свойства форматов файлов делают это возможным — они обычно не рассматриваются как уязвимости, но их можно обнаружить или нормализовать:

фиктивные чанки — используются как комментарии
более одного комментария
огромные комментарии (длины: 64 бит для MP4, 32 бит для PNG -> тривиальные коллизии; 16 бит для JPG, 8 бит для GIF -> нет универсальной коллизии для GIF, ограниченная для JPG)
хранить любые данные в комментарии (может быть принудительно ASCII или UTF8)
хранить что угодно после терминатора (обычно используется только во вредоносных целях) - этого можно избежать, используя два комментария, заканчивающихся на одних и тех же смещениях.
отсутствие проверки целостности. CRC32 в PNG обычно игнорируются. Однако они могут быть все корректными, поскольку блоки коллизий объявляют чанки разной длины - так что даже если данные чанка начинаются по-разному, длины чанков различаются
плоская структура: ASN.1 определяет родительскую структуру с длиной всех вложенных подструктур, что предотвращает такие конструкции: нужно было бы злоупотребить длиной, но также и длиной родительской структуры.
поместить комментарий перед заголовком — это делает возможными универсальные повторно используемые коллизии.

Идентичный префикс

Определите произвольный префикс — его содержимое и длина не важны.
Префикс дополняется до следующего 64-байтового блока.
Блок(и) коллизий вычисляются в зависимости от префикса и добавляются. Обе стороны очень случайны. Различия предопределены атакой.
После этого(их) блока(ов) значение хеша одинаково, несмотря на различия в файлах.
Можно добавить любой произвольный идентичный суффикс.

Префикс	=	Префикс
Коллизия A	≠	Коллизия B
Суффикс	=	Суффикс

Оба файла почти идентичны (их содержимое отличается лишь на несколько битов).

Эксплуатация:

Свяжите два содержимых, затем либо:

Эксплуатация данных: запустить код, который проверяет различия и отображает одно или другое (обычно тривиально, поскольку различия известны заранее).
Эксплуатация структуры: использовать структуру файла (обычно длину комментария), чтобы скрыть одно содержимое или показать другое (зависит от формата файла и его парсеров).

Два файла с такой структурой:

будут показывать либо A, либо B.

FastColl (MD5)

Финальная версия в 2009 году.

время: несколько секунд вычислений
пространство: два блока

различия: нет контроля до, нет контроля после. Маска различий FastColl:

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

эксплуатация: сложная

Различия находятся не у начала/конца блоков, поэтому их очень трудно эксплуатировать, поскольку вы не контролируете ни один соседний байт. Потенциальное решение — перебор окружающих байт — см. PoCGTFO 14:10.

Примеры:

С пустым префиксом:``` MD5: fe6c446ee3a831ee010f33ac9c1b602c SHA256: c5dd2ef7c74cd2e80a0fd16f1dd6955c626b59def888be734219d48da6b9dbdd

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

MD5: fe6c446ee3a831ee010f33ac9c1b602c SHA256: e27cf3073c704d0665da42d597d4d20131013204eecb6372a5bd60aeddd5d670

Другие примеры с одинаковым префиксом: [1](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll1.bin) ⟷ [2](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll2.bin)

**Вариант**: существует [одноблочная коллизия MD5](https://marc-stevens.nl/research/md5-1block-collision/), но для её вычисления требуется пять недель.

Вот [запись](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll.svg) вычисления FastColl без префикса
и [ещё одна](https://github.com/decalage2/collisions/blob/HEAD/examples/fastcoll-prefix.svg) с префиксом.


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

Описано в [2012](https://www.cwi.nl/system/files/PhD-Thesis-Marc-Stevens-Attacks-on-Hash-Functions-and-Applications.pdf#page=199), реализовано в [2017](https://github.com/cr-marcstevens/hashclash/blob/95c2619a8078990056beb7aaa59104021714ee3c/scripts/poc_no.sh)

[UniColl](https://github.com/cr-marcstevens/hashclash#create-you-own-identical-prefix-collision) позволяет управлять несколькими байтами в блоках коллизии,
до и после первого различия, что делает её коллизией с идентичным префиксом, обладающей некоторыми управляемыми различиями, почти как коллизия с выбранным префиксом.
Это очень удобно, и, что ещё лучше, различие может быть очень предсказуемым:
в случае `m2+= 2^8` (также известного как `N=1` / `m2 9` в скрипте HashClash [poc_no.sh](https://github.com/cr-marcstevens/hashclash/blob/master/scripts/poc_no.sh#L30)),
различие составляет +1 в 9-м байте, что делает её очень легко эксплуатируемой,
так как вы можете даже продумать коллизию в голове:
9-й символ этого предложения будет заменён следующим: `0` заменяется на `1`, `a` на `b`..

- время: несколько минут (зависит от количества байт, которыми вы хотите управлять )
- пространство: два блока
- различия:   ```
   .. .. .. .. DD .. .. .. ..
   .. .. .. .. +1 .. .. .. ..

эксплуатация: очень простая - контролируемые байты до и после различия, и различие предсказуемо. Единственные ограничения - выравнивание и то, что вы контролируете 'только' 10 байт после различия.

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

UniColl даёт меньше контроля, чем истинная коллизия с выбранным префиксом,
но он гораздо быстрее, особенно потому что требует всего два блока.

Вот [запись](https://github.com/decalage2/collisions/blob/HEAD/examples/unicoll.svg) вычисления UniColl.


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

Описано в [2013](https://marc-stevens.nl/research/papers/EC13-S.pdf), вычислено в [2017](http://shattered.io).

- время: 6500 years.CPU и 110 year.GPU
- память: два блока
- различия:  ```
  .. .. .. DD ?? ?? ?? ??
  or
  ?? ?? ?? DD .. .. .. ..

эксплуатация: средняя. Различия находятся в самом начале и в самом конце блоков коллизий. Таким образом, нет контроля перед и после длины в префиксе/суффиксе: PNG хранит свою длину перед типом чанка, поэтому это не сработает. Однако это сработает с файлами JP2, когда они используют форму JFIF (так же, как JPG), и, вероятно, с MP4 и другими форматами на основе атомов/боксов, если использовать длинные (64-битные) значения длины (в этом случае они размещаются после типа атома).

Разница между блоками коллизий каждой стороны заключается в следующей 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)),
а также проверяет значения префиксов с помощью JavaScript на HTML-странице (файл является полиглотом: ZIP, HTML и PDF).


## Коллизии с выбранным префиксом

Они позволяют столкнуть любое содержимое.

| 𝓐            | ≠ | 𝔅             |
| :----:        |:-:| :----:        |
| Коллизия *A* | ≠ | Коллизия *B* |

1. возьмите два произвольных префикса
2. дополните более короткий до длины более длинного. оба дополняются до следующего блока - минус 12 байт
  - эти 12 байт случайных данных будут добавлены с обеих сторон для рандомизации поиска по методу дня рождения
3. X блоков почти-коллизии будут вычислены и добавлены.

   Чем меньше блоков, тем дольше вычисления.

   Напр.: [400 kHours для одного блока](https://www.win.tue.nl/hashclash/SingleBlock/). 72 ядро-часа для девяти блоков с помощью [HashClash](https://github.com/cr-marcstevens/hashclash).



Коллизии с выбранным префиксом всемогущи, но их построение может занять много времени даже для пары файлов.


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

Финальная версия вышла в [2009](https://www.win.tue.nl/hashclash/ChosenPrefixCollisions/) году.

Примеры: создадим коллизию для `yes` и `no`. Это заняло три часа на 24 ядрах.```
'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

Here is a log of the whole operation.

Shambles (SHA-1)

Shambles — это очень дорогая коллизия с выбранным префиксом, использующая 9 блоков.

Каждый блок имеет тот же xor-шаблон, что и Shattered:``` 0C 00 00 02 C0 00 00 10 B4 00 00 1C 3C 00 00 04 BC 00 00 1A 20 00 00 10 24 00 00 1C EC 00 00 14 0C 00 00 02 C0 00 00 10 B4 00 00 1C 2C 00 00 04 BC 00 00 18 B0 00 00 10 00 00 00 0C B8 00 00 10

## Сводка атак

Хэш | Имя | Дата | Длительность | Тип префикса | Контроль вблизи различий
---- | --------- | ---- | -------- | ----------- | -----------------
MD5 | FastColl | 2009 | 2 сек | Идентичный | нет
     | UniColl | 2012 | 7-40 мин | Идентичный | 4-10 байт
     | HashClash | 2009 | 72 ч | Выбранный | н/д
     |           |      |          |             |
SHA1 | Shattered | 2013 | 6500 лет | Идентичный | префикс и суффикс
     | Shambles | 2020 | ? | Выбранный | н/д

# Эксплуатация

Коллизии с идентичным префиксом обычно считаются (весьма) ограниченными, но метод выбранного префикса отнимает много времени.

Другой подход — создавать многоразовые префиксы с помощью атаки с идентичным префиксом, такой как UniColl, или с выбранным префиксом, чтобы преодолеть некоторые ограничения, — но затем использовать эту пару префиксов в сочетании с двумя полезными нагрузками, как в классической атаке с идентичным префиксом.

Как только пара префиксов вычислена, коллизия двух содержимых становится мгновенной:
остаётся лишь подогнать данные файла (согласно конкретным форматам), чтобы они соответствовали спецификациям форматов и требованиям предварительно вычисленного префикса.

## Стандартная стратегия

Классические коллизии двух корректных файлов одного и того же типа.

### JPG



Теоретические ограничения и обходные пути:
- сегмент *Application* теоретически должен находиться сразу после маркера *Start of Image*.
  На практике это не обязательно, поэтому наша коллизия может быть универсальной: единственное ограничение — размер наименьшего изображения.
- длина комментария хранится в двух байтах, поэтому объём, который он может хранить, ограничен 65536 байтами (примерно размер фото 400x400)
- вместо перепрыгивания через весь JPG-файл можно разбить этот файл на сегменты и добавить прыжковые трамплины между сегментами

  

  *комментарии над каждым сегментом изображения*

  

  *как работают трамплины из комментариев*

- в то время как большая часть структуры JPG состоит из сегментов, размер которых ограничен 65536 байтами,
фактические сжатые данные хранятся в *Entropy Coded Segment*, который не соблюдает эти ограничения:
его размер заранее неизвестен и может превышать этот предел.
Он растёт вместе с размером изображения, составляя бо́льшую часть размера файла в базовом (не прогрессивном) изображении.
Чтобы уместить всё изображение в фрагменты по 64 КБ, простой способ — сначала попробовать сохранить изображение как прогрессивное (это умеет любое ПО, и оно обычно разбивает ECS на шесть скан-проходов). Более продвинутый способ — использовать *JPEGTran* с его параметром командной строки 'wizard' `--scans` и задать собственные скан-проходы.
- Помимо сегментов скан-проходов других ограничений нет,
поэтому MD5-коллизия двух произвольных JPG-файлов является *мгновенной* и не требует коллизии с выбранным префиксом — достаточно UniColl.

С помощью [скрипта](https://github.com/decalage2/collisions/blob/HEAD/scripts/jpg.py):```
21:07:35.65>jpg.py Ange.jpg Marc.jpg

21:07:35.75>

Примеры:

⟷

пользовательские сканы

2 JPG с коллизией MD5

Вот пример определения сканов JPEGTran, чтобы превратить изображение RGB 1944x2508 в 100% JPG с 20 сканами, и все они умещаются в 64 кб.``` // : -, , ;

// 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;

Результат:



*изображение 1944x2508 RGB в виде 100% JPG с 20 сканами*


### PNG



Теоретические ограничения и обходные пути:
- PNG использует CRC32 в конце своих чанков, но на практике они игнорируются. Они могут быть корректными, но это не требуется.
- метаданные изображения (размеры, цветовое пространство...) хранятся в чанке `IHDR`,
  который в теории должен находиться сразу после сигнатуры (т.е. до любого потенциального комментария),
  поэтому это означало бы, что мы можем предвычислять коллизии только для изображений с одинаковыми метаданными.
  Однако этот чанк может на самом деле находиться после блока комментариев (в подавляющем большинстве программ просмотра, кроме Apple),
  поэтому мы можем поместить данные коллизии перед заголовком,
  что позволяет создать коллизию для любой пары PNG за одно предвычисление.

Поскольку чанк PNG имеет длину в четыре байта, нет необходимости изменять структуру любого из файлов: мы можем перепрыгнуть через целое изображение за один раз.

Мы можем вставить столько отбрасываемых чанков, сколько захотим, поэтому мы можем добавить один для выравнивания, а затем один, длина которого будет изменена с помощью UniColl. так что длина будет `00` `75` и `01` `75`.

Таким образом, MD5-коллизия двух произвольных PNG-изображений является *мгновенной*, без каких-либо предварительных условий (никаких вычислений, только небольшие изменения файлов), и не требует коллизии с выбранным префиксом — только UniColl.

С помощью [скрипта](https://github.com/decalage2/collisions/blob/HEAD/scripts/png.py):```
19:27:04.79>png.py nintendo.png sega.png

19:27:04.87>

Примеры:

⟷

2 PNG-файла с MD5-коллизией и разными свойствами

Вот запись всей операции.

запись универсальной (нарушающей спецификацию) PNG-коллизии

несовместимость

Большинство программ чтения без проблем принимают PNG-файлы, начинающиеся с чанка, отличного от IHDR.

Однако некоторые (например, Safari и Preview — есть ещё кто-то?) этого не терпят. В этом случае заголовок изображения и его свойства (размеры, цветовое пространство) должны быть первыми, до любых коллизионных блоков.

В этом случае оба конфликтующих файла должны иметь одинаковые свойства. Опять же, UniColl достаточно, и, конечно, вычисленную пару префиксов можно повторно использовать для любой другой пары файлов с теми же свойствами.

Вот скрипт для создания коллизии любой пары таких файлов, который при необходимости запускает UniColl для вычисления пары префиксов.

Примеры:

⟷

2 пары PNG-файлов с MD5-коллизией и одинаковыми свойствами для максимальной совместимости

Вот запись всей операции при вызове UniColl,

запись PNG-коллизии UniColl

и ещё одна, когда префикс уже был вычислен.

запись предвычисленной PNG-коллизии

GIF

С GIF всё непросто:

он хранит метаданные в заголовке до того, как становится возможным комментарий, поэтому не может быть универсального префикса для всех GIF-файлов.
если файл имеет глобальную палитру, она также сохраняется до того, как возможен комментарий.
длина его чанков комментариев ограничена одним байтом, то есть максимум 256 байт!

Однако чанки комментариев имеют своеобразную структуру: это цепочка <length:1> <data:length> до тех пор, пока не встретится нулевая длина. Поэтому любой ненулевой байт становится корректным «переходом вперёд». Это делает их пригодными для использования с FastColl, как показано в PoC||GTFO 14:11.

По крайней мере, даже если мы не можем получить универсальный префикс, мы можем создать коллизию для любой пары GIF-файлов с одинаковыми метаданными (размерами, палитрой), и нам нужна лишь секунда работы FastColl, чтобы вычислить её префикс.

Проблема в том, что мы не можем перепрыгнуть через целое изображение, как в PNG, или через большую структуру, как в JPG.

Возможный обходной путь — видоизменить сжатые данные или разбить изображение на крошечные области, как в случае с GIF hashquine, но это не оптимально.

Другая универсально работающая идея состоит в том, что данные изображения также хранятся с использованием этой структуры последовательности length data: поэтому, если мы возьмём два GIF-файла без анимации, нам нужно лишь:

нормализовать палитру
установить максимальную длительность первого кадра
создать комментарий, который перепрыгнет к началу данных первого кадра, так что комментарий проскользит по данным изображения как комментарий, и закончится так же: до тех пор, пока не встретится нулевая длина. Затем парсер встретит следующий кадр и отобразит его.

С небольшой подготовкой (всего несколько сотен байт накладных расходов) мы можем проскользить по любому GIF-изображению и обойти ограничение в 256 байт. Эту идею предложил Marc, и она блестящая!

Итак, текущие ограничения GIF для мгновенных MD5-коллизий таковы:

без анимации
изображения должны быть нормализованы к единой палитре — см. gifsicle --use-colormap web
изображения должны иметь одинаковые размеры
через 11 минут оба файла покажут одно и то же изображение

Простой способ нормализовать статичные GIF-изображения — сделать их кадрами анимации одного изображения, затем мы можем использовать скрипт, чтобы переиспользовать или вычислить блоки FastColl и создать пару файлов, показывающую каждый из них.

Примеры:

⟷

2 GIF-файла с MD5-коллизией — изображения KidMoGraph

Вот запись всей операции.

запись GIF-коллизии FastColl

GZIP

Спецификация GZIP v4.3: RFC 1952 (1996).

Gzip-файл состоит из одного или нескольких объединённых «элементов» (gzip-потоков). Все они будут распакованы, а их несжатое содержимое будет добавлено друг к другу — даже если несжатое содержимое элемента пусто.
эти элементы могут разделяться нулями. Нули будут просто пропускаться, кроме начала файла. Любой ненулевой байт будет проверяться на сигнатуру 1F 8B. Если сигнатура не совпадает, разбор остановится; это можно использовать для принудительной остановки разбора между двумя полезными нагрузками, но это вызовет предупреждения, которые могут привести к проблемам. Другая стратегия — добавить один дополнительный пустой элемент в конец файла и сделать так, чтобы разбор обеих полезных нагрузок завершался там — на самом элементе или на его теле.
Необязательные filename и file comment завершаются нулевым байтом, тогда как Extra field определяется 16-битным размером и потому допускает злоупотребление. Он состоит из одного или нескольких подполей с ID и собственной длиной, но подполя не проверяются — официально определено очень немногие.

Таким образом, пустой gzip-элемент с дополнительным полем — идеальный носитель для паразитной нагрузки.

Если сам файл слишком велик, чтобы поместиться в дополнительное поле, то его несжатый поток можно разбить на меньшие файлы, пока все они не поместятся в дополнительные поля.

После заголовка элемента идут его сжатое тело, его CRC32 и его несжатый размер (не проверяется). Поэтому пустое тело данных с нулевыми CRC32 и размером образует универсальную постобёртку, которую можно даже разделять между разными заголовками элементов.

Различные реализации полагаются на несжатый размер последнего элемента, а не на сумму всех элементов. Поэтому наши конфликтующие файлы будут показывать нулевой размер, так как эти файлы заканчиваются пустым элементом, используемым как трамплин.

Вот скрипт для генерации мгновенных MD5-коллизий двух GZip-файлов. Большую часть времени он тратит на распаковку и повторное сжатие данных, если входные файлы большие — префиксы коллизий предвычислены. Разделять элементы без распаковки невозможно, так как необходимо вычислить несжатый CRC32.

.tar.gz — это просто gzip-архив tar-архива. С gzip-архивом tar это будет работать нормально, в отличие от самого tar.

Примеры: collision1.tar.gz (Pacome) ⟷ collision2.tar.gz (Reg)

Portable Executable

Portable Executable имеет своеобразную структуру:

старый DOS-заголовок почти бесполезен и указывает на следующую структуру — PE-заголовок. Других ролей у DOS-заголовка нет. DOS-заголовки можно обменивать между исполняемыми файлами.
DOS-заголовок должен находиться по смещению 0 и иметь фиксированную длину в целый блок, а указатель находится в конце структуры, вне досягаемости UniColl: поэтому для коллизии PE-файлов таким образом пригодна только chosen-prefix коллизия.
PE-заголовок и всё, что за ним следует, определяют весь файл.

Итак, стратегия такова:

PE-заголовок можно сдвинуть вниз, чтобы оставить место для коллизионных блоков после DOS-заголовка.
DOS-заголовок можно эксплуатировать (с помощью chosen-prefix коллизий), чтобы он указывал на два разных смещения, куда будут перемещены два разных PE-заголовка.
Секции можно разместить рядом друг с другом, после структуры DOS/Collisions/Header1/Header2. Нужно лишь применить дельту к смещениям двух таблиц секций.

Это означает, что можно мгновенно создать коллизию для любой пары PE-исполняемых файлов. Даже если они используют разные подсистемы или архитектуры.

Хотя коллизии исполняемых файлов обычно тривиальны через любой загрузчик, такая эксплуатация здесь прозрачна: код идентичен и загружается по одному и тому же адресу.

Примеры: tweakPNG.exe (GUI) ⟷ fastcoll.exe (CLI)

Вот скрипт для генерации мгновенных MD5-коллизий Windows-исполняемых файлов.

MP4 и другие

Контейнер этого формата представляет собой последовательность чанков Length Type Value, называемых атомами. Длина — это 32-битное big-endian значение, которое включает само себя, тип и значение, поэтому минимальная нормальная длина равна 8 (тип — строка из 4 ASCII-символов).

Если длина равна нулю, то атом занимает остальную часть файла — например, атомы jp2c в файлах JP2. Если она равна 1, то за типом следует 64-битная длина, превращающая атом в Type Length Value, что делает его совместимым с другими коллизиями, такими как Shattered.

Некоторые атомы содержат другие атомы: в таких случаях они называются боксами. Поэтому эта иначе безымянная структура называется "atom/box".

Этот формат "atom/box", используемый в MP4, на самом деле является производным от Apple Quicktime и используется многими другими форматами (JP2, HEIF, F4V).

Первый тип атома обычно — ftyp, что позволяет различать конкретный файловый формат.

Формат довольно снисходителен: просто соедините в цепочку атомы free, исказите длину одного из них с помощью UniColl, а затем перепрыгните через первую полезную нагрузку.

Для MP4-файлов единственное, что нужно добавить, — это скорректировать таблицы stco (Sample Table - Chunk Offsets) или co64 (64-битный эквивалент), поскольку они содержат абсолютные(!) смещения, указывающие на видеоданные mdat, — и они действительно проверяются!

Это даёт скрипт, который мгновенно создаёт коллизию для любого произвольного видео — и, как уже упоминалось, он может работать и с другими форматами, не только MP4.

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

Примеры (видео KidMoGraph):

32-битные длины (стандарт) collision1.mp4 ⟷ collision2.mp4

⟷
64-битные длины collisionl1.mp4 ⟷ collisionl2.mp4

⟷

Обратите внимание: некоторые просмотрщики (OS X, Safari, FireFox) не допускают файл, начинающийся с атома, отличного от ftyp. В этом случае префикс должен это учитывать, и он уже не так универсален, но в остальном это та же стратегия — просто ограничена одним типом файлов.

JPEG2000

Файлы JPEG2000 обычно начинаются со структуры Atom/Box, как MP4, затем последний атом jp2c обычно идёт до конца файла (нулевая длина), а далее следует структура JFIF, как в JPEG (начиная с FF 4F в качестве маркера сегмента).

Чистая форма JFIF также допускается; в этом случае коллизия аналогична JPEG: совместима с Shattered, но с комментариями, ограниченными 64 КБ.

С другой стороны, если вы работаете с файлами JPEG2000 через Atom/Box, у вас нет этого ограничения.

Как упоминалось ранее, если вы пытаетесь создать коллизию этой структуры и есть дополнительные ограничения — например, начало с атома free не допускается некоторыми форматами, — то можно вычислить другую пару UniColl-префиксов, специфичную для этого формата: JPEG2000, похоже, требует атом 'jP ' перед обычным ftyp, но в остальном это единственное ограничение: ничего перемещать не нужно.

Поэтому итоговый скрипт ещё проще!

Oded Goldreich / Neal Koblitz

Примеры: collision1.jp2 ⟷ collision2.jp2

PDF

о Shattered

Эксплуатация Shattered была не трюком с PDF, а трюком с JPG внутри PDF.

Она лишь позволяла PDF-файлу содержать JPG-сжатый объект, который мог иметь два разных содержимых. В остальном оба PDF-файла должны были быть полностью идентичны.

Обратите внимание, что документы могут быть совершенно обычными и могут просто обрезать коллизионный JPG и отображать его в разных местах, например в многостраничных документах.

Примеры: статья о Shattered, изменённая ⟷ статья о Shattered, оригинальная

статья о Shattered с использованием коллизионного JPG в двух местах

PDF-коллизии с MD5

С помощью MD5 (и других схем коллизий) мы можем создавать PDF-коллизии на уровне документа, без каких-либо ограничений на любой из файлов!

PDF имеет структуру, сильно отличающуюся от других файловых форматов. Он использует номера объектов и ссылки для определения дерева. Весь документ зависит от корневого элемента.

Этот (корректный) 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.

Таким образом, хранение двух деревьев документов в одном файле допустимо. Нам просто нужно, чтобы корневой объект ссылался на корневой объект любого из двух документов.

Итак, нам нужно взять два документа, перенумеровать объекты и ссылки так, чтобы не было пересечений, создать коллизию так, чтобы номер элемента, на который ссылается корневой объект, можно было изменить, сохранив то же значение хэша, что идеально подходит для UniColl с N=1, и соответствующим образом скорректировать таблицу XREF.

Таким образом, мы можем безопасно создавать коллизии для любой пары PDF-файлов, независимо от количества страниц, размеров, изображений...

комментарии

PDF может хранить посторонние данные двумя способами:

как построчный комментарий, в котором единственными запрещёнными символами являются перевод строки (\r и \n). Это можно использовать внутри объекта-словаря, например, для изменения ссылки на объект через UniColl. Так что это корректный PDF-объект, даже если он содержит бинарные блоки коллизий — просто повторяйте попытку, пока не получите без символов перевода строки: ``` 1 0 obj << /Type /Catalog /MD5_is /REALLY_dead_now__ /Pages 2 0 R %¥┬•σe╕█╙X₧_~π▌╒εX∟■φe♦%τ8╞■[...]p╛╬ûFZ»‼v◘Åp↑╝%▓% ▼σφj╔◄dZ▀c²aU≤╨╩[├└─yNΓ5╔+▀╪yδ☻ß⌐░¼à(☺z₧

endobj
как объект потока, в этом случае возможны любые данные, но поскольку мы находимся внутри объекта, мы не можем изменить всю структуру PDF, поэтому требуется коллизия с выбранным префиксом, чтобы изменить структуру за пределами содержащего объекта потока.

коллизионный текст

Первый случай позволяет продемонстрировать красоту UniColl — коллизии, в которой различия предсказуемы, так что вы можете писать стихи поверх коллизирующих данных - спасибо Jurph!

Вместо изменения структуры документа и обмана парсеров мы просто будем использовать блоки коллизий напрямую, чтобы получить непосредственно текст, с альтернативным прочтением!``` V V Now he hash MD5, Now he hath MD5, No enemy cares! No enemy dares! Only he gave Only he have the shards. the shares. Can’t be owned & Can’t be pwned & his true gold, his true hold, like One Frail, like One Grail, sound as fold. sound as gold. ^ ^

Примеры: [poeMD5 A](https://github.com/decalage2/collisions/blob/HEAD/examples/poeMD5_A.pdf) ⟷ [poeMD5 B](https://github.com/decalage2/collisions/blob/HEAD/examples/poeMD5_B.pdf)



*Настоящее криптографическое художественное творение :)*

(Примечание: я напортачил с совместимостью Adobe, но это моя вина, а не UniColl)

**коллизии структуры документа**

Независимо от того, используете ли вы UniColl как встроенный комментарий или как выбранный префикс в фиктивном объекте потока, стратегия одинакова:
перетасуйте номера объектов, а затем заставьте объект Root указывать на разные объекты, так что, в отличие от Shattered, это означает мгновенную коллизию для любой произвольной пары PDF на уровне документа.

Полезный трюк в том, что вывод [`mutool clean`](https://mupdf.com/docs/manual-mutool-clean.html) надёжно предсказуем,
поэтому его можно использовать для нормализации PDF-файлов на входе и для исправления объединённого PDF, сохраняя важные части файла без изменений.
MuTool не отбрасывает фиктивные ключи/значения — если только не попросить, и сохраняет их в том же порядке,
поэтому использование фальшивых записей словаря, таких как `/MD5_is /REALLY_dead_now__`, идеально подходит для предсказуемого выравнивания без необходимости в комментариях другого рода.
Однако он не сохраняет комментарии в словарях (так что трюк со встроенными комментариями не сработает).

Простой способ выполнить перетасовку объектов без лишних хлопот — просто объединить оба PDF-файла
через `mutool merge`, а затем разделить объект `/Pages` на две части.

Чтобы освободить место для этого объекта, достаточно подмешать перед двумя документами фиктивный PDF.

При желании можно создать фиктивную ссылку на «висячий» массив,
чтобы сборщик мусора не удалил второй набор страниц.

**Пример**:
с помощью этого [скрипта](https://github.com/decalage2/collisions/blob/HEAD/scripts/pdf.py)
[меньше чем за секунду](https://github.com/decalage2/collisions/blob/HEAD/examples/pdf.log) можно создать коллизию для двух публичных PDF-статей, таких как Spectre и Meltdown:

Примеры: [spectre.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/collision1.pdf) ⟷ [meltdown.pdf](https://github.com/decalage2/collisions/blob/HEAD/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

Не забудьте нормализовать вывод PDFLaTeX — например, с помощью mutool, если это необходимо: PDFLaTeX сложно сделать воспроизводимым в разных дистрибутивах — возможно, вам даже захочется зафиксировать время выполнения, чтобы получить точный хеш, если это требуется.

JPG в PDF

Можно ожидать, что JPG — это только изображения, но в PDF и в некоторых программах просмотра PDF (не в браузерах, таких как Evince и Adobe Reader), он может использоваться как содержимое страницы точно так же, как и любой другой встроенный объект, внедрённый в изображение JPEG.

Для хранения данных JPEG без потерь сохраните их в градациях серого 100%, затем либо используйте изображение из одной строки/колонки, либо повторите строку данных 8 раз (так как блоки JPEG имеют размер 8x8), и тогда ваши данные будут сохранены без потерь и будут использоваться страницами PDF.

Примеры коллизий SHA-1 двух PDF-файлов через данные страницы JPEG (изображение в градациях серого, отображающее цвета) в качестве векторного содержимого страницы:

If ⟷ Shattered - the movie

2 PDF-файла с коллизией SHA-1, содержащие данные изображений в формате JPG

Можно ссылаться на коллизирующий JPG дважды: как на содержимое страницы, без потерь, при этом он также сам на себя ссылается как на изображение с потерями, предназначенное для отображения. Опять же, отображаемое изображение — в градациях серого, но содержимое страницы может отображать некоторые цвета с помощью операторов PDF.

В верхней части изображения показано содержимое страницы, повторённое 8 раз.

Примеры коллизий SHA-1 двух PDF-файлов через JPEG, используемый и как данные страницы, и как отображаемое изображение:

Skulls & Crossbones ⟷ Golden Axe

2 PDF-файла с коллизией SHA-1, где JPG используется и как изображение, и как содержимое страницы

ZIP

TL;DR Универсальной повторно используемой коллизии для ZIP не существует, но она существует для формата на основе ZIP. Должна быть возможность получить коллизию двух файлов за 2h.core (в 36 раз быстрее, чем выбранный префикс).

ZIP-архивы представляют собой «сэндвич» как минимум из 3 слоёв. Сначала идёт содержимое файлов (последовательность структур Local File Header, по одной на каждый архивируемый файл или каталог), затем — некоторый индекс (опять же последовательность Central Directory), и затем — единственная структура, которая указывает на этот индекс (End Of Central Directory).

Порядок этих слоёв нельзя менять. Некоторым парсерам достаточна только структура содержимого файла, но это неправильный способ разбора, и им можно злоупотребить.

Из-за этого обязательного порядка не существует универсального префикса, который мог бы помочь для любой коллизии.

Неуниверсальный подход

Другой подход может заключаться в простом объединении обоих архивов, вместе с их объединёнными слоями, и использовании UniColl — но с N=2, что вносит различие в 4-й байт, — чтобы уничтожить магическую сигнатуру End of Central Directory.

Это означает, что можно получить коллизию двух произвольных ZIP-архивов с помощью одного вызова UniColl и 24 байтов заданного префикса.

Типичный End of Central Directory, который составляет 22 байта, если комментарий пуст:``` 00: 504b 0506 0000 0000 0000 0000 0000 0000 PK.............. 10: 0000 0000 0000 ......

Если мы используем это в качестве префикса (дополнив префикс до 16 бит) для UniColl и `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..(

The input for this chunk is empty. Please provide the Markdown content to translate.``` 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..(

Это совсем не универсально, но гораздо быстрее, чем коллизия с выбранным префиксом:```
real 12m23.993s
user 112m24.072s
sys 2m0.194s

Проблема в том, что некоторые парсеры всё ещё разбирают ZIP-файлы «сверху вниз», даже если должны разбирать снизу вверх: способ гарантировать корректный разбор обоих файлов — связать два блока UniColl, чтобы включать/отключать каждый End of Central Directory.

Чтобы ZIP-парсеры не жаловались на неиспользуемое пространство, можно злоупотребить Extra Fields, комментариями к файлам в Central Directory и комментариями архива в End of Central Directory.

diagram of ZIP collision

Пример: вот исходный код на ассемблере, описывающий структуру двойного ZIP-архива, который может содержать два разных архивных файла.

После двух вычислений Unicoll получаются два конфликтующих файла: collision1.zip ⟷ collision2.zip

Форматы на основе Zip

Даже если сам формат Zip нельзя универсально эксплуатировать как Gzip, некоторые форматы, основанные на Zip, можно универсально эксплуатировать внутри ZIP-архивов с предопределённой структурой. Чтобы сделать коллизию Zip универсальной, необходимо принять некоторые меры предосторожности.

Некоторые форматы представляют собой несколько файлов, хранящихся в ZIP-архиве, и опираются на корневой файл с фиксированным именем, который указывает на другие файлы в архиве. Многие из них используют для корневого файла XML или текст, а остальные файлы хранят как есть.

Идея : заставить 2 набора файлов сосуществовать в одном архиве и указывать на любой из наборов. Универсальный корневой файл может быть сохранён первым в начале файла, но блоки коллизий хранятся вне содержимого файла, в архиве (поскольку коллизии имеют очень высокую энтропию, невозможно эксплуатировать XML или файлы только из ASCII с коллизиями).

Шаги:

Поместите 2 набора файлов из 2 источников в один архив — т.е. в разные подкаталоги.
Измените корневой файл так, чтобы он попеременно указывал на каждый набор.
Поскольку временная метка, длина и CRC корневого файла хранятся и в Local File Header — до содержимого файла, — и в Central Directory — после содержимого файла, — эти значения не должны меняться между двумя версиями файлов.
- Если длина меняется, все последующие указатели тоже изменятся, поэтому идентичный суффикс будет невозможен.
- Если CRC32 в Central Directory некорректен, эта копия значения может быть проигнорирована парсером, но подделка CRC32 до постоянного значения помогает полностью избежать проблемы. Подделки CRC путём добавления 4 случайных байтов, скорее всего, будет недостаточно, поскольку эти корневые файлы обычно представлены в XML или тексте со строгим синтаксисом, и они станут недействительными. CrcHack значительно помогает подделывать CRC с произвольными битами без перебора, гарантируя, что выходной файл остаётся ASCII и что изменённые биты всё ещё находятся в комментарии.
Использование extra field дополнительного фиктивного файла — даже пустого — в архиве после корневого файла является элегантным способом хранения блоков коллизий Hashclash: так ZIP-архив сохраняет стандартную структуру и может быть легко изменён впоследствии даже стандартными инструментами.

Extra Fields не имеют CRC32, а их 16-битная длина объявляется в заголовках заранее. У них есть собственный внутренний формат ID:2 Size:2 Data, но он обычно игнорируется, и они присутствуют и в Local File Header, и в Central Directory, но могут отсутствовать в Central Directory, чтобы сохранить идентичный суффикс после блоков коллизий.

Наличие дополнительного файла, который покрывает блоки коллизий в своём extra field, возможно, придётся объявить в структуре формата, например, в файле [Content_Types].xml в документе OOXML. Другие 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, можно вычислить универсальную переиспользуемую коллизию Hashclash для конкретного формата на основе zip.


### Сводка требований

- два или более префикса
- один или несколько типов файлов (полиглоты работают без проблем)
- корневой XML-файл с фиксированным именем файла, длиной файла и CRC: эта информация присутствует дважды — до и после блоков коллизий
 - содержимое — произвольный XML
 - допускается дополнение (padding), даже с помощью XML-комментария, для достижения одинаковой длины.
 - CRC можно задать (через CrcHack) для каждого содержимого.
- оба набора файлов сосуществуют в суффиксе, скорее всего, в разных каталогах. Некоторые инструменты жёстко прописывают путь, что может снизить совместимость.
- возможно, потребуется объединить XML-файл *Content type*, чтобы охватить все файлы — поддерживаемые и неподдерживаемые (блоки коллизий и альтернативный документ).


### Примеры

#### CRC32

Минимальный XML-комментарий (только ASCII) с подделанным CRC32 (мгновенное вычисление) с помощью CrcHack.``` bash
echo "<!--ABCDEF-->" | crchack -b 4.0:+.8*6:1 -b 4.1:+.8*6:1 -b 4.2:+.8*6:1 -b 4.3:+.8*6:1 -b 4.4:+.8*6:1 -b 4.5:+.8*5:1 - 0xdeadf00d
<!--X{]EZF-->

Ещё один пример, где вы корректируете CRC с учётом регистра буквенного сообщения.```bash echo "" | crchack.exe -b 4:+.8*32:.8 - 0xcafebabe

#### Коллизии

[zInsider](https://github.com/decalage2/collisions/blob/HEAD/scripts/zinsider.py) — это скрипт для мгновенной генерации MD5-коллизий пар произвольных документов с использованием следующих форматов ZIP+XML:
- 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/decalage2/collisions/blob/HEAD/scripts/makezip.py) для создания корневой ZIP-пары.
После вычисления коллизий используйте [этот другой скрипт](https://github.com/decalage2/collisions/blob/HEAD/scripts/extendzip.py), чтобы объединить эту корневую пару с общим суффиксом.

Несколько PoC-коллизий:
- Office Open XML: Excel ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-1.xls) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-2.xls)), Powerpoint ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-1.pptx) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-2.pptx)), Word ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-1.docx) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/free/md5-2.docx)).
- Open Container Format: Epub ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-1.epub) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-2.epub)).
- Open Packaging Conventions: 3MF ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-1.3mf) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-2.3mf)), XPS ([1](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-1.xps) - [2](https://github.com/decalage2/collisions/blob/HEAD/examples/collision-2.xps)).


Некоторые форматы с несколькими файлами на основе Zip не могут быть универсально использованы:
- Quake PK3: ZIP-архив файлов без конкретного корня.
- Open Document Format: файл `META-INF/manifest.xml` должен упоминать все остальные файлы, поэтому универсальным он быть не может.
- APK, JAR, XPI: файл `META-INF/MANIFEST.mf` также должен упоминать все остальные файлы с их хешами.


Спасибо [Philippe Lagadec](https://twitter.com/decalage2) за помощь с форматами файлов Office!


## Нестандартные стратегии

Обычно коллизии касаются двух валидных файлов одного типа.


### MultiColls: цепочка множественных коллизий

Ничто не мешает соединить в цепочку несколько блоков коллизий
и получить более двух содержимых с одинаковым значением хеша.
Примером этого являются *hashquine* — файлы, показывающие собственное значение MD5.
Файл [PoCGTFO 14](https://github.com/angea/pocorgtfo#0x14) содержит 609 коллизий FastColl,
чтобы сделать это через два типа файлов в одном файле.


### Validity

Другая стратегия — убить тип файла, чтобы обойти сканирование как повреждённый файл.
Достаточно просто перезаписать магическую сигнатуру.
Если дописать к обоим файлам (валидным или невалидным) формат,
которому не обязательно находиться по смещению 0 (архив, например ZIP/RAR/...), это выявит другой тип файла.

Это позволяет создавать полиглот-коллизии без использования chosen-prefix коллизии:
1. используйте UniColl, чтобы включить или отключить магическую сигнатуру, например PNG:
2. добавьте ZIP-архив

Хотя технически оба файла являются валидными ZIP, поскольку большинство парсеров возвращают первый найденный тип файла и начинают сканирование со смещения 0, они увидят разный тип файла.

Примеры:

 ⟷ [невалидное](https://github.com/decalage2/collisions/blob/HEAD/examples/png-invalid.png)



### PolyColls: коллизии разных типов файлов

Также можно сделать обе стороны коллизии разных типов, чтобы снизить подозрения:

Сценарий атаки:
1. отправьте `holiday.jpg`
2. добейтесь, чтобы он попал в белый список
3. отправьте `evil.exe`, у которого тот же MD5.

В таких случаях требуется chosen-prefix коллизия,
если оба формата файлов должны начинаться со смещения 0.

Некоторые примеры компоновок polycoll:

![полиглот-коллизия PDF-JPG](https://assets.kitploit.com/production/public/readmes/47472/3dcd55e877a4ce9c933bf1478d0a71ede85e129b9e746414d754ffabceabe463.png)

*PDF/JPG polycoll*


![полиглот-коллизия PE-PNG](https://assets.kitploit.com/production/public/readmes/47472/63df55a15e7ca33153f352f13ba273604df6b1ae3e1e8838b601fea39de801e0.png)

*PE/PNG polycoll*


#### PE - JPG

Поскольку заголовок PE обычно меньше 0x500 байт, он отлично помещается в комментарий JPG:
1. начните с заголовков DOS/JPG
2. комментарий JPEG перепрыгивает через PE-заголовок
3. поместите полное изображение JPG
4. поместите все спецификации PE

И снова коллизия [мгновенная](https://github.com/decalage2/collisions/blob/HEAD/scripts/jpgpe.py)

Примеры: [fastcoll.exe](https://github.com/decalage2/collisions/blob/HEAD/examples/jpg-pe.exe) ⟷ [Marc.jpg](https://github.com/decalage2/collisions/blob/HEAD/examples/jpg-pe.jpg)


#### PDF - PE

Объединение PDF с фиктивным файлом с помощью `mutool` — хороший универсальный способ переупорядочить объекты
и затем сделать первые два объекта отбрасываемыми (фиктивная страница и содержимое),
что идеально подходит для размещения объекта `stream` неизвестной длины как `1 0`,
а его длина ссылается дальше (после блоков коллизий) во втором объекте.

Единственная проблема в том, что `mutool` всегда встраивает длину и удаляет ссылку на неё,
поэтому в PDF вместо значения нужно заново вставить ссылку на длину,
но большинство ссылок `2 0 R` будут меньше, чем жёстко заданные длины.
К счастью, это можно исправить без изменения смещений объектов,
так что патчить XREF не нужно.

Вот [скрипт](https://github.com/decalage2/collisions/blob/HEAD/scripts/pdfpe.py), позволяющий, например, мгновенно столкнуть программу для просмотра PDF ([Sumatra](https://www.sumatrapdfreader.org/free-pdf-reader.html) — лёгкая и автономная) и PDF-документ:

Примеры: [Poster.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/pepdf.pdf) ⟷ [Sumatra.exe](https://github.com/decalage2/collisions/blob/HEAD/examples/pepdf.exe)

![программа просмотра PDF, показывающая PDF (сам показывающий PDF) с одинаковым MD5](https://assets.kitploit.com/production/public/readmes/47472/4356d710fc4b60297ee05999be64f596198e9d4a02c826666818eb8ae117310f.png)

*программа просмотра PDF, показывающая PDF (сам показывающий PDF) с одинаковым MD5*


#### PDF - PNG

Аналогично можно столкнуть, например, произвольные PDF и PNG-файлы без каких-либо ограничений с обеих сторон. Это мгновенно, переиспользуемо и универсально.

Примеры: [Hello.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/png-pdf.pdf) ⟷ [1x1.png](https://github.com/decalage2/collisions/blob/HEAD/examples/png-pdf.png)


### PileUps (multi-collision)

Криптографические коллизии не ограничиваются двумя файлами!

Как было продемонстрировано в эксперименте [Nostradamus](https://www.win.tue.nl/hashclash/Nostradamus/) в 2008 году,
соединение коллизий в цепочку позволяет столкнуть более двух файлов.

Первые коллизии могут быть одинаковыми или chosen-prefix, последующие должны быть chosen-prefix.

Их можно называть мультиколлизиями, но я предпочитаю *pileups* — так короче :)


#### PE - PNG - MP4 - PDF

Объединив все ранее полученные знания,
я использовал 3 chosen-prefix коллизии, чтобы создать 4 разных префикса для разных типов файлов:
документ (PDF), видео (MP4), исполняемый файл (PE) и изображение (PNG).

![диаграмма pileup PE/PNG/MP4/PDF](https://assets.kitploit.com/production/public/readmes/47472/f7c45f284bad51f431a2993cf4797f679c85671c028cf1862f1c07604740360a.png)

*диаграмма pileup PE/PNG/MP4/PDF*

Этот скрипт универсален и мгновенен:

![диаграмма pileup PE/PNG/MP4/PDF](https://assets.kitploit.com/production/public/readmes/47472/3ec7caeb459eab294c6b9876a8a82e136502c3d11c599804fd7925fc2d819276.png)

Примеры: [commodore.pdf](https://github.com/decalage2/collisions/blob/HEAD/examples/pileup.pdf) ⟷ [diagram.png](https://github.com/decalage2/collisions/blob/HEAD/examples/pileup.png) ⟷ [kidmo.mp4](https://github.com/decalage2/collisions/blob/HEAD/examples/pileup.mp4) ⟷ [sumatra18.exe](https://github.com/decalage2/collisions/blob/HEAD/examples/pileup.exe)


Поскольку вы можете распространять только один файл,
и невозможно угадать остальные значения префиксов из него,
решение — встроить все префиксы коллизии в JavaScript-код
и вставить его в ваши PoC,
превратив ваши файлы в [HTML-полиглоты](https://github.com/decalage2/collisions/blob/HEAD/examples/polyglot.html), чтобы легко делиться связанными коллизионными файлами.



[Выпуск 19](https://github.com/angea/pocorgtfo#0x19) журнала 'PoC or GTFO' — это такой pileup **и** полиглот,
сочетающий 80-страничный документ, сгенерированный с помощью PDFLaTeX, программу просмотра PDF для Windows,
PNG-диаграмму и короткое 'коллизионное' MP4-видео от [KidMoGraph](https://www.kidmograph.com/)
с HTML-пейлоадом для генерации остальных файлов из PDF-выпуска
(а также ZIP-архива):



Спасибо Rafał Hirsz за постоянную помощь с JavaScript.


## Use cases

Лучше вообще отказаться от MD5, потому что интроспекция файлов слишком трудоёмка и слишком рискованна!


### Gotta collide 'em all!

Ещё одно применение мгновенных, переиспользуемых и универсальных коллизий — спрятать любой файл заданного типа, скажем PNG, за фиктивными файлами (или каждый раз одним и тем же файлом) — что, по сути, достигается простой конкатенацией с тем же префиксом после удаления сигнатуры — это можно делать даже на уровне библиотеки!

С точки зрения строгого разбора
все ваши файлы будут показывать одно и то же содержимое,
а вредоносные изображения будут раскрыты как файл с тем же MD5, что и ранее собранные.

Возьмём два файла:

 ⟷


и столкнём их с одним и тем же PNG.

Теперь они показывают одно и то же фиктивное изображение и абсолютно идентичны вплоть до 2-го изображения на уровне файла!

 ⟷


Их вредоносная нагрузка скрыта за файлом с тем же MD5 соответственно.


### Incriminating files

Ещё один вариант использования коллизий — спрятать что-то компрометирующее внутри чего-то невинного,
но желаемого: если единственный способ сбора улик — сравнение слабых хешей,
то вы не сможете отрицать, что у вас есть другой файл (показывающий компрометирующее содержимое, но скрывающий невинное).

Программное обеспечение обычно ориентируется на (быстрый) разбор, а не на детальный анализ файлов.



*изображение, показывающее разные предпросмотры на разных вкладках EnCase Forensic*


## Failures

Не все форматы могут иметь универсальные префиксы, которые можно переиспользовать:
если между магической сигнатурой и стандартными заголовками, критичными и специфичными для каждого файла,
нельзя вставить некий контейнер данных,
то универсальные коллизии невозможны.

Конечно, можно превратить старые файлы в новый
и даже использовать код для ветвления на две разные нагрузки,
но это скорее перенос нагрузок, чем коллизия файловых структур.


### ELF



Заголовок ELF должен находиться по смещению 0 и содержит критическую информацию, такую как 32b/64b,
порядок байтов и ABI прямо с начала,
поэтому невозможно иметь универсальный префикс с последующими блоками коллизий
до критических параметров, специфичных для исходного файла.


### Mach-O



Файлы Mach-O даже не начинаются с одной и той же магии для 32b (`feedface`) и 64b (`feedfacf`).
Сразу после неё идут количество и размер команд (таких как определение сегмента, symtab, версия,...).

Как и для ELF, переиспользуемые коллизии невозможны.


### Java Class



Сразу после магии расположены версии (что может быть проблематично),
но также счётчик пула констант, который довольно специфичен для каждого файла,
поэтому универсальных коллизий для всех файлов нет.

Однако у многих файлов всё же общая версия, и мы можем дополнить самый короткий пул констант до наибольшего значения.
Сначала вставьте *UTF8-литерал* для выравнивания информации,
затем объявите ещё один, злоупотребив его длиной с помощью UniColl (длина хранится в 16 байтах в порядке big endian).

Однако это потребует манипуляций с кодом, поскольку все индексы пула будут сдвинуты.

Мгновенные переиспользуемые MD5-коллизии для Java Class должны быть возможны, но требуют анализа и модификации кода.


### TAR

**TL;DR** Никаких переиспользуемых коллизий для TAR-файлов, никакой другой стратегии, кроме chosen-prefix.



Tape Archives — это последовательность объединённых заголовков и содержимого файлов, всё выровнено по 512 байт.

Во всём файле нет центральной структуры. Значит, нет никакого глобального заголовка или комментария, которым можно было бы злоупотребить.

Хитрость заключалась бы в том, чтобы начать фиктивный файл переменной длины, но длина всегда находится по одному и тому же смещению, что несовместимо с UniColl, а значит, здесь полезны только chosen-prefix коллизии.


## Exploitations summary

Формат        | Универс.? | 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 с JPG — это [исходная реализация](http://shattered.io) атаки Shattered, но это просто чистый трюк с JPG внутри PDF-документа.
3. PNG: Safari/Preview требует, чтобы чанк `IHDR` в PNG находился на первом месте, перед любым блоком коллизий. Это препятствует универсальному префиксу, и в таком случае коллизия ограничена конкретными размерами, цветовым пространством, BPP и чересстрочностью.
4. Форматы Atom/Box, такие как MP4, могут работать с одним и тем же префиксом для разных подформатов. Некоторые подформаты, например JPEG2000 или HEIF, требуют дополнительной доводки, но стратегия эксплуатации та же — просто коллизия невозможна между подформатами, только с парой префиксов для конкретного подформата.
5. Atom/Box совместим с Shattered при использовании 64-битных длин.
6. Некоторые форматы на основе Zip могут быть универсально эксплуатируемы.
7. Для лучшей совместимости ZIP требует два UniColl для полного архива, и эти коллизии зависят от содержимого обоих файлов.

## Test files

[Здесь](https://github.com/decalage2/collisions/blob/HEAD/examples/free/README.md) находятся свободные (без авторских прав, без персональных данных) тестовые коллизионные пары.


# Ссылки

Статьи:

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

- 2019 KILL MD5 at Pass the Salt:
  - [слайды](https://speakerdeck.com/ange/kill-md5)

    [](https://speakerdeck.com/ange/kill-md5)
  - [видео](https://passthesalt.ubicast.tv/videos/kill-md5-demystifying-hash-collisions/)

    [![Видео Kill MD5](https://assets.kitploit.com/production/public/readmes/47472/4d7d0e2935f37e9ae363ad7bebe2abb3697978e7b3c1aa57851c54727b7ac49f.jpg)](https://passthesalt.ubicast.tv/videos/kill-md5-demystifying-hash-collisions/)


Воркшоп (CollTris):
  - [слайды](https://speakerdeck.com/ange/colltris)

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

  - [видео](https://www.youtube.com/watch?v=BcwrMnGVyBI)

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

  - [материалы](https://github.com/decalage2/collisions/blob/HEAD/workshop/README.md)

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


CTF-задания:
- [Prudentialv2](https://ctftime.org/task/3453), из *Boston Key Party CTF 2017*.
- [HREFIN](https://ctftime.org/task/6965), из *Google CTF 2018*.
- [Looking glass](https://ctftime.org/task/9271) из *Dragon Sector Teaser CTF 2019*.

<!-- - [Not my digest](https://ctftime.org/task/4784) из *Hack.lu CTF 2017*: не связано с коллизиями, но решено самим Марком :p -->
Общая сложность таких CTF-заданий — не давать слишком большого преимущества или помех в зависимости от объёма вычислительной мощности, доступной каждому игроку.


# Благодарности

Всё это стало возможным благодаря [Marc Stevens](https://marc-stevens.nl/research/),
не только за его криптографический вклад, но и за постоянную помощь и предложения!

Также спасибо Philippe Teuwen за его обширную обратную связь по файловым форматам в целом.


# Заключение

**Убейте MD5!**

Если вы активно не проверяете файлы на наличие аномалий или блоков коллизий, не используйте MD5!

Это не криптографический хеш, это игрушечная функция!

collisions

Популярное

Хэш-коллизии и их эксплуатация

Введение

Статус

Идентичный префикс

FastColl (MD5)

Shambles (SHA-1)

пользовательские сканы

несовместимость

GIF

GZIP

Portable Executable

MP4 и другие

JPEG2000

PDF

JPG в PDF

ZIP

Форматы на основе Zip