corkami/collisionsHash collisions and exploitations
Авторы: Ange Albertini и Marc Stevens.
В: Можно ли заставить файл получить произвольный MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3 или такой же хэш, как у другого файла?
О: Нет.
В: Можно ли создать 2 разных файла с одинаковым хэшем?
О: С MD5 — за несколько секунд на обычном компьютере. С SHA1 — возможно, но непрактично для конечных пользователей (Сложность: 2^61.2 Цена: $11k).
В: Можно ли заставить 2 разных файла получить одинаковый хэш, добавив данные?
О: С MD5 — за несколько часов на обычном компьютере. С SHA1 — возможно, но непрактично для конечных пользователей (Сложность: 2^63.4 Цена: $45K)
В: Будут ли 2 файла оставаться корректными?
О: В целом да, так как большинство форматов файлов допускают добавленные данные. С другой стороны, подписи файлов, скорее всего, будут нарушены.
В: Можно ли создать 2 разных файла с произвольным содержимым и одинаковым хэшем?
О: Да, это может быть мгновенным, если опираться на особые структуры файлов:
В: Для каких форматов можно мгновенно получить пару файлов с коллизией MD5?
О: JPG, PNG, GIF, GZIP, Portable Executable, MP4, JPEG2000, PDF, DOCX/PPTX/XSLX, EPUB, 3MF, XPS. Просто запустите соответствующий скрипт.
В: А как насчёт SHA1?
О: Для SHA1 вычислена и реализована JPG в PDF.
В: А форматы, уже поддерживаемые для MD5 (JPG, PNG...), но для SHA1?
О: Скорее всего, они поддерживаются и для SHA1, но их коллизии ещё не вычислены.
В: Вычисления для похожих (но разных) содержимых выполняются быстрее?
О: Нет. Любое мельчайшее отличие требует полного вычисления.
В: Какие форматы не имеют такого обходного пути?
О: ELF, Mach-O, Java Class, TAR, ZIP (среди прочих...)
В: Возможны ли классические коллизии (за несколько часов) с этими форматами?
О: Да, если допускается любое количество добавляемых данных (то есть, скорее всего, не ZIP или Class).
В: Предоставляете ли вы примеры коллизий?
О: Да.
Цель — всесторонне исследовать существующие атаки — и заодно показать, насколько слаб MD5 (мгновенные коллизии для любых JPG, PNG, PDF, MP4, PE...) — а также детально изучить распространённые форматы файлов, чтобы определить, как их можно эксплуатировать с помощью текущих или будущих атак.
Действительно, один и тот же приём с форматом файла можно использовать для нескольких хэшей (те же приёмы с JPG использовались для MD5, malicious SHA-1 и SHA1), если коллизии следуют одним и тем же байтовым шаблонам.
Этот документ посвящён не новым атакам (самая недавняя была задокументирована в 2012 году), а новым формам эксплуатации существующих атак.
Текущий статус известных атак:
заставить файл получить хэш другого файла или заданный хэш: невозможно
получить два разных файла с одинаковым MD5: мгновенно
заставить два произвольных файла получить одинаковый MD5: несколько часов (72 ядро-часа)
заставить два произвольных файла определённых форматов (PNG, JPG, PE...) получить одинаковый MD5: мгновенно
получить два разных файла с одинаковым SHA1: 6500 ядро-лет
(*) пример с 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 будет проигнорировано.
Итак, обычно нужны как минимум два комментария - часто три:
Эти общие свойства форматов файлов делают это возможным - обычно они не считаются слабостями, но их можно обнаружить или нормализовать:
| Префикс | = | Префикс |
|---|---|---|
| Коллизия A | ≠ | Коллизия B |
| Суффикс | = | Суффикс |
Оба файла почти идентичны (их содержимое различается лишь несколькими битами)
Эксплуатация:
Объедините два содержимых, затем либо:
Два файла с такой структурой:
будут показывать либо A, либо B.
Окончательная версия 2009 года.
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. 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
Other examples, with an identical prefix: [1](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll1.bin) ⟷ [2](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll2.bin)
**Variant**: there is a [single-block MD5 collision](https://marc-stevens.nl/research/md5-1block-collision/) but it takes five weeks of computation.
Here is a [recording](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll.svg) of a FastColl computation without any prefix
and [another one](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll-prefix.svg) with a prefix.
### [UniColl](https://github.com/corkami/collisions/blob/HEAD/unicoll.md) (MD5)
Documented in [2012](https://www.cwi.nl/system/files/PhD-Thesis-Marc-Stevens-Attacks-on-Hash-Functions-and-Applications.pdf#page=199), implemented in [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) lets you control a few bytes in the collision blocks,
before and after the first difference, which makes it an identical-prefix collision with some controllable differences, almost like a chosen-prefix collision.
This is very handy, and even better the difference can be very predictable:
in the case of `m2+= 2^8` (a.k.a. `N=1` / `m2 9` in HashClash [poc_no.sh](https://github.com/cr-marcstevens/hashclash/blob/master/scripts/poc_no.sh#L30) script),
the difference is +1 on the 9th byte, which makes it very exploitable,
as you can even think about the collision in your head:
the 9th character of that sentence will be replaced with the next one: `0` replaced by `1`, `a` replaced by `b`..
- time: a few minutes (depends on the amount of byte you want to control )
- space: two blocks
- differences: ```
.. .. .. .. DD .. .. .. ..
.. .. .. .. +1 .. .. .. ..
Примеры с 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/corkami/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
Вот журнал всей операции.
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
Но даже если Shattered гораздо легче эксплуатировать, чем FastColl,
ограничения на различия в коллизионных блоках не имеют значения,
поскольку Shambles — это коллизия с выбранным префиксом (Chosen Prefix Collision).
## Сводка атак
Хэш | Имя | Дата | Длительность | Тип префикса | Контроль вблизи различий
---- | --------- | ---- | -------- | ----------- | -----------------
MD5 | FastColl | 2009 | 2 с | Идентичный | нет
| UniColl | 2012 | 7-40 мин | Идентичный | 4-10 байт
| HashClash | 2009 | 72 ч | Выбранный | n/a
| | | | |
SHA1 | Shattered | 2013 | 6500 лет | Идентичный | префикс и суффикс
| Shambles | 2020 | ? | Выбранный | n/a
# Эксплуатация
Коллизии с идентичным префиксом обычно считаются (очень) ограниченными, но выбор префикса занимает много времени.
Другой подход — создавать повторно используемые префиксы либо с помощью атаки с идентичным префиксом, такой как UniColl, либо с выбранным префиксом, чтобы преодолеть некоторые ограничения, — но затем повторно использовать эту пару префиксов в сочетании с двумя полезными нагрузками, как в классической атаке с идентичным префиксом.
Как только пара префиксов вычислена, коллизия двух содержимых становится мгновенной:
достаточно подогнать данные файла (в соответствии с конкретными форматами файлов) так, чтобы они соответствовали спецификациям форматов и требованиям предварительно вычисленного префикса.
## Стандартная стратегия
Классические коллизии двух валидных файлов одного типа.
### JPG
Теоретические ограничения и обходные пути:
- сегмент *Application* теоретически должен идти сразу после маркера *Start of Image*.
На практике это не обязательно, поэтому наша коллизия может быть универсальной: единственное ограничение — размер самого маленького изображения.
- длина комментария хранится в двух байтах, поэтому объём, который он может хранить, ограничен 65536 байтами (примерно размер фото 400x400)
- вместо того чтобы перепрыгивать через весь файл JPG, можно разбить этот файл на сегменты и добавить переходные трамплины между сегментами
*комментарии над каждым сегментом изображения*
*как работают трамплины комментариев*
- хотя большая часть структуры JPG состоит из сегментов, размер которых ограничен 65536 байтами,
фактические сжатые данные хранятся в *Entropy Coded Segment*, который не соблюдает эти ограничения:
его размер заранее неизвестен и может превышать этот предел.
Он растёт вместе с размером изображения, составляя большую часть размера файла в базовом (не прогрессивном) изображении.
Чтобы всё изображение уместилось в фрагменты по 64 КБ, простой способ — сначала попробовать сохранить изображение как прогрессивное (это умеет любое ПО, и это разбивает ECS, как правило, на шесть проходов). Более продвинутый способ — использовать *JPEGTran* с его 'мастером' — параметром командной строки `--scans` — и определять собственные проходы.
Нет других ограничений, кроме сегментов проходов,
поэтому коллизия MD5 двух произвольных JPG — *мгновенная*, и для неё не нужна коллизия с выбранным префиксом, достаточно UniColl.
С помощью [скрипта](https://github.com/corkami/collisions/blob/HEAD/scripts/jpg.py):```
21:07:35.65>jpg.py Ange.jpg Marc.jpg
21:07:35.75>
Examples:
⟷
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;
Результат:
*изображение RGB 1944x2508 в виде 100% JPG с 20 сканами*
### PNG
Теоретические ограничения и обходные пути:
- PNG использует CRC32 в конце своих чанков, но на практике они игнорируются. Они могут быть корректными, но это не требуется.
- метаданные изображения (размеры, цветовое пространство...) хранятся в чанке `IHDR`,
который в теории должен быть сразу после сигнатуры (т.е. до любого возможного комментария),
что означало бы возможность предвычисления коллизий только для изображений с одинаковыми метаданными.
Однако этот чанк на самом деле может находиться после блока комментариев (в подавляющем большинстве просмотрщиков, кроме Apple), поэтому мы можем поместить данные коллизии перед заголовком,
что позволяет получить коллизию для любой пары PNG с помощью одного предвычисления.
Поскольку длина чанка PNG занимает четыре байта, нет необходимости изменять структуру любого из файлов: мы можем перепрыгнуть через целое изображение за один раз.
Мы можем вставить сколько угодно отбрасываемых чанков, поэтому можем добавить один для выравнивания, затем тот, чья длина будет изменена с помощью UniColl, так что длина станет `00` `75` и `01` `75`.
Таким образом, MD5-коллизия двух произвольных PNG-изображений получается *мгновенно*, без каких-либо предварительных условий (никаких вычислений, лишь небольшие изменения файлов), и не требует коллизии с выбранным префиксом — достаточно UniColl.
С помощью [скрипта](https://github.com/corkami/collisions/blob/HEAD/scripts/png.py):```
19:27:04.79>png.py nintendo.png sega.png
19:27:04.87>
Примеры:
⟷
2 PNG-файла с MD5-коллизией и разными свойствами
Вот запись всей операции.
Большинство программ просмотра без проблем принимают PNG-файлы, начинающиеся с чанка, отличного от IHDR.
Однако некоторые (например, Safari и Preview — есть другие?) этого не допускают. В этом случае заголовок изображения и его свойства (размеры, цветовое пространство) должны быть первыми, до любых блоков коллизии.
В этом случае оба файла, образующие коллизию, должны иметь одинаковые свойства. Опять же, достаточно UniColl, и, конечно, вычисленную пару префиксов можно повторно использовать для любой другой пары файлов с теми же свойствами.
Вот скрипт для создания коллизии любой пары таких файлов, который при необходимости запускает UniColl для вычисления пары префиксов.
Примеры:
⟷
⟷
2 пары PNG-файлов с MD5-коллизией и одинаковыми свойствами для максимальной совместимости
Вот запись всей операции при вызове UniColl,
и ещё одна для случая, когда префикс уже вычислен.
GIF — коварный формат:
Однако чанки-комментарии имеют своеобразную структуру: это цепочка <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Простой способ нормализовать статичные GIF-изображения — сделать их кадрами анимации одного изображения, затем можно использовать скрипт, чтобы повторно использовать или вычислить блоки FastColl и создать пару файлов, показывающую каждый из них.
Примеры:
⟷
2 GIF-файла с MD5-коллизией — картинки от KidMoGraph
Вот запись всей операции.
Спецификация GZIP v4.3: RFC 1952 (1996).
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)
LZ4 и Zstandard — это два разных формата сжатия со схожей общей структурой:
они состоят из фреймов, каждый из которых начинается с определённой магической последовательности: 0xFD2FB528 для фреймов Zstandard, 0x184D2204 для фреймов Lz4.
Кроме того, они совместно используют одни и те же 'пропускаемые' TLV-фреймы, начинающиеся с 4 байт магических чисел в диапазоне 0x184D2A50 - 0x184D2A5F, затем длины пользовательских данных (4 байта, little-endian), затем самих пользовательских данных.
Эти фреймы полностью необязательны, могут быть любой длины и повторяться. Файлы могут начинаться с этих фреймов. Поэтому такие фреймы можно объединять в цепочку, чтобы получить идеальный универсальный префикс коллизии для двух форматов.
Вот скрипт для создания мгновенных MD5-коллизий двух файлов Zstd/Lz4. Как и в случае с Gzip, снаружи будут видны 2 разных архива независимо от содержимого: например, .cpio.zst.
Примеры:
Portable Executable имеет своеобразную структуру:
Итак, стратегия такова:
DOS/Collisions/Header1/Header2. Нужно лишь применить дельту к смещениям двух таблиц секций.Это означает, что можно мгновенно создать коллизию для любой пары PE-исполняемых файлов. Даже если они используют разные подсистемы или архитектуру.
Хотя коллизии исполняемых файлов обычно тривиальны через любой загрузчик, такая эксплуатация здесь прозрачна: код идентичен и загружается по одному и тому же адресу.
Примеры: tweakPNG.exe (GUI) ⟷ fastcoll.exe (CLI)
Вот скрипт для создания мгновенных MD5-коллизий исполняемых файлов Windows.
Контейнер этого формата представляет собой последовательность чанков Length Type Value, называемых атомами.
Длина — это 32-битное значение big-endian, которое охватывает сам себя, тип и значение, поэтому минимальная нормальная длина равна 8
(тип — строка из 4 ASCII-символов).
Если длина равна нулю, атом занимает остаток файла — как атомы jp2c в файлах JP2.
Если она равна 1, то после Type идёт 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.
Примеры (видео от KidMoGraph):
длины 32b (стандарт) collision1.mp4 ⟷ collision2.mp4
⟷
длины 64b collisionl1.mp4 ⟷ collisionl2.mp4
⟷
Обратите внимание, что некоторые программы просмотра (OS X, Safari, FireFox) не допускают файл, начинающийся с атома, отличного от ftyp.
В этом случае префикс должен это учитывать, и он уже не такой универсальный, но в остальном стратегия та же — только ограничена единственным типом файла.
Файлы JPEG2000 обычно начинаются со структуры Atom/Box, как MP4,
затем последний атом jp2c обычно идёт до конца файла (нулевая длина),
а далее следует структура JFIF, как в JPEG (начиная с FF 4F как маркера сегмента).
Чистая форма JFIF также допускается, и в этом случае коллизия подобна JPEG: совместима с Shattered, но с комментариями, ограниченными 64Kb.
С другой стороны, если работать с файлами JPEG2000 через Atom/Box, этого ограничения нет.
Как уже упоминалось, если вы пытаетесь создать коллизию для этой структуры и
есть дополнительные ограничения — например, некоторые форматы не допускают начало с атома free —
то можно вычислить другие пары префиксов UniColl, специфичные для этого формата:
JPEG2000, похоже, требует атом 'jP ' первым перед обычным ftyp,
но в остальном это единственное ограничение: ничего перемещать не нужно.
Так что итоговый скрипт даже проще!
Примеры: collision1.jp2 ⟷ collision2.jp2
о 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>>
Приёмы:
XREF.Таким образом, хранить два дерева документов в одном файле можно. Нам просто нужно, чтобы корневой объект ссылался на любой из корневых объектов обоих документов.
Итак, нам нужно взять два документа, перенумеровать объекты и ссылки так, чтобы не было пересечений, сконструировать коллизию, позволяющую изменить номер объекта, используемого в качестве корневого объекта Root, при сохранении того же хеш-значения, что идеально подходит для 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
Коллидирующий текст
Первый случай позволяет продемонстрировать красоту 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/corkami/collisions/blob/HEAD/examples/poeMD5_A.pdf) ⟷ [poeMD5 B](https://github.com/corkami/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/corkami/collisions/blob/HEAD/scripts/pdf.py) на столкновение двух публичных PDF-документов, таких как Spectre и Meltdown, уходит [меньше секунды](https://github.com/corkami/collisions/blob/HEAD/examples/pdf.log):
Примеры: [spectre.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/collision1.pdf) ⟷ [meltdown.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/collision2.pdf)
Возможное расширение: выстраивайте блоки UniColl в цепочку, чтобы также сохранять пары различных [некритичных объектов](https://www.adobe.com/content/dam/acom/en/devnet/pdf/pdfs/PDF32000_2008.pdf#page=81),
на которые можно ссылаться в объекте Root - такие как `Outlines`, `Names`, `AcroForm` и Additional Actions (`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 и в некоторых программах просмотра PDF (не в браузерах, например в Evince и Adobe Reader) его можно использовать как содержимое страницы, как и любой другой встроенный объект, встроенный в JPEG-изображение.
Чтобы хранить данные JPEG без потерь, сохраните их как grayscale 100%, затем либо используйте изображение из одной строки/столбца, либо повторите строку данных 8 раз (так как блоки JPEG имеют размер 8x8), и ваши данные сохранятся без потерь и будут использоваться страницами PDF.
Примеры коллизий SHA-1 между двумя PDF-файлами через данные JPEG-страницы (grayscale-изображение, отображающее цвета) в качестве векторного содержимого страницы:
2 SHA-1 коллизионных PDF, в которых изображение хранится как JPG
Возможно ссылаться на коллизионный JPG дважды: как на содержимое страницы, без потерь, и при этом он также ссылается на себя как на изображение с потерями для отображения. Опять же, отображаемое изображение - grayscale, но содержимое страницы может отображать некоторые цвета с помощью операторов PDF.
В верхней части изображения показано содержимое страницы, повторённое 8 раз.
Примеры коллизий SHA-1 между двумя PDF-файлами через JPEG, используемый и как данные страницы, и как отображаемая картинка:
Skulls & Crossbones ⟷ Golden Axe
2 SHA-1 коллизионных PDF, в которых JPG используется и как изображение, и как содержимое страницы
TL;DR Не существует универсальной повторно используемой коллизии для ZIP, но она существует для формата на основе ZIP. Должна быть возможна коллизия двух файлов в 2h.core (в 36 раз быстрее, чем chosen-prefix)
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-й байт, уничтожая magic `.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..(
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.
Пример: вот исходный код ассемблера, описывающий структуру двойного ZIP-архива, который может содержать два разных архивных файла.
После двух вычислений Unicoll получаются два коллизионных файла: collision1.zip ⟷ collision2.zip
Даже если сам формат Zip не может быть универсально эксплуатирован подобно Gzip, некоторые форматы, полагающиеся на Zip, могут быть универсально эксплуатированы внутри Zip-архивов с заранее заданной структурой. Некоторые меры предосторожности необходимо предпринять, чтобы сделать коллизию Zip универсальной.
Некоторые форматы представляют собой несколько файлов, хранящихся в Zip-архиве, и используют корневой файл с фиксированным именем, который указывает на другие файлы в архиве. Многие из них используют XML или текст для корневого файла, а остальные файлы хранят как есть.
Идея : сделать так, чтобы два набора файлов сосуществовали в одном архиве и указывали на любой из наборов. Универсальный корневой файл может храниться в начале файла, но блоки коллизий хранятся вне содержимого файла, в архиве (поскольку коллизии имеют очень высокую энтропию, невозможно использовать XML или файлы, содержащие только ASCII, с коллизиями).
Шаги:
Поместите 2 набора файлов из 2 источников в один архив - т.е. в разные подкаталоги.
Измените корневой файл, чтобы он поочерёдно указывал на каждый набор.
Поскольку метка времени, длина и CRC корневого файла хранятся как в Local File Header - до содержимого файла - так и в Central Directory - после содержимого файла - эти значения не должны меняться между двумя версиями файлов.
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
- дополнение возможно, даже через 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/corkami/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/corkami/collisions/blob/HEAD/scripts/makezip.py) для создания корневой пары zip.
После вычисления коллизий используйте [другой скрипт](https://github.com/corkami/collisions/blob/HEAD/scripts/extendzip.py), чтобы объединить эту пару корневых элементов с общим суффиксом.
Несколько PoC-примеров коллизий:
- Office Open XML: Excel ([1](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.xls) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.xls)), Powerpoint ([1](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.pptx) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.pptx)), Word ([1](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.docx) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.docx)).
- Open Container Format: Epub ([1](https://github.com/corkami/collisions/blob/HEAD/examples/collision-1.epub) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/collision-2.epub)).
- Open Packaging Conventions: 3MF ([1](https://github.com/corkami/collisions/blob/HEAD/examples/collision-1.3mf) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/collision-2.3mf)), XPS ([1](https://github.com/corkami/collisions/blob/HEAD/examples/collision-1.xps) - [2](https://github.com/corkami/collisions/blob/HEAD/examples/collision-2.xps)).
Некоторые форматы с несколькими файлами на основе Zip не могут быть использованы универсально:
- Quake PK3: zip-архив файлов без конкретного корневого элемента.
- Open Document Format: файл `META-INF/manifest.xml` должен упоминать все остальные файлы, поэтому универсальным он быть не может.
- APK, JAR, XPI: файл `META-INF/MANIFEST.mf` также должен упоминать все остальные файлы с их хэшами.
Спасибо [Филиппу Лагадеку](https://twitter.com/decalage2) за помощь с форматами файлов Office!
### Прочие
- Wasm, через пользовательскую секцию: [скрипт](https://github.com/corkami/collisions/blob/HEAD/scripts/wasm.py), примеры: [md5-1.wasm](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-1.wasm) ⟷ [md5-2.wasm](https://github.com/corkami/collisions/blob/HEAD/examples/free/md5-2.wasm)
## Нестандартные стратегии
Обычно коллизии касаются двух допустимых файлов одного типа.
### MultiColls: цепочка множественных коллизий
Ничто не мешает объединить в цепочку несколько блоков коллизий и получить более двух содержимых с одинаковым значением хэша. Примером этого являются *hashquines* — файлы, показывающие собственное значение MD5. Файл [PoCGTFO 14](https://github.com/angea/pocorgtfo#0x14) содержит 609 коллизий FastColl, чтобы добиться этого через два типа файлов в одном файле.
#### Hashquines
Hashquines — это файлы, показывающие собственное значение хэша. Они описаны [здесь](https://github.com/corkami/collisions/blob/HEAD/hashquines/).
### Валидность
Другая стратегия — убить тип файла, чтобы обойти сканирование как повреждённого файла. Достаточно просто перезаписать магическую сигнатуру. Добавление к обоим файлам (валидным или невалидным) формата, которому не нужно находиться по смещению 0 (архив, например ZIP/RAR/...), выявит другой тип файла.
Это позволяет создавать полиглот-коллизии без использования коллизии с выбранным префиксом:
1. используйте UniColl, чтобы включить или отключить магическую сигнатуру, например PNG:
2. добавьте ZIP-архив
Хотя технически оба файла являются валидным ZIP, поскольку большинство парсеров возвращают первый найденный тип файла и начинают сканирование со смещения 0, они увидят разный тип файла.
Примеры:
⟷ [невалидное](https://github.com/corkami/collisions/blob/HEAD/examples/png-invalid.png)
### PolyColls: коллизии разных типов файлов
Также можно сделать обе стороны коллизии разных типов, чтобы снизить подозрения:
Сценарий атаки:
1. отправьте `holiday.jpg`
2. добейтесь, чтобы он попал в белый список
3. отправьте `evil.exe` с тем же MD5.
В таких случаях требуется коллизия с выбранным префиксом, если оба формата файлов должны начинаться со смещения 0.
Некоторые примеры компоновок polycoll:
*поликоллизия PDF/JPG*
*поликоллизия PE/PNG*
#### PE - JPG
Поскольку заголовок PE обычно меньше 0x500 байт, он идеально подходит для комментария JPG:
1. начните с заголовков DOS/JPG
2. комментарий JPEG перепрыгивает через заголовок PE
3. поместите полное изображение JPG
4. поместите все спецификации PE
И снова коллизия [мгновенна](https://github.com/corkami/collisions/blob/HEAD/scripts/jpgpe.py)
Примеры: [fastcoll.exe](https://github.com/corkami/collisions/blob/HEAD/examples/jpg-pe.exe) ⟷ [Marc.jpg](https://github.com/corkami/collisions/blob/HEAD/examples/jpg-pe.jpg)
#### PDF - PE
Объединение PDF с фиктивным файлом с помощью `mutool` — хороший универсальный способ переупорядочить объекты и сделать первые два объекта отбрасываемыми (фиктивная страница и содержимое), что идеально подходит для размещения объекта `stream` неизвестной длины как `1 0`, и ссылка на его длину указывается дальше (после блоков коллизии) во втором объекте.
Единственная проблема в том, что `mutool` всегда встраивает длину напрямую и убирает ссылку на длину, поэтому в PDF нужно заново вставить ссылку вместо значения, но большинство ссылок вида `2 0 R` будут короче, чем жёстко заданные длины. К счастью, это можно исправить без изменения смещений объектов, поэтому патчить XREF не нужно.
Вот [скрипт](https://github.com/corkami/collisions/blob/HEAD/scripts/pdfpe.py), который позволяет, например, мгновенно создать коллизию PDF-просмотрщика ([Sumatra](https://www.sumatrapdfreader.org/free-pdf-reader.html) — лёгкий и автономный) и PDF-документа:
Примеры: [Poster.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/pepdf.pdf) ⟷ [Sumatra.exe](https://github.com/corkami/collisions/blob/HEAD/examples/pepdf.exe)
*PDF-просмотрщик, показывающий PDF (сам показывающий PDF) с одинаковым MD5*
#### PDF - PNG
Аналогично можно создать коллизию, например, произвольных PDF- и PNG-файлов без ограничений с какой-либо стороны. Это мгновенно, переиспользуемо и универсально.
Примеры: [Hello.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/png-pdf.pdf) ⟷ [1x1.png](https://github.com/corkami/collisions/blob/HEAD/examples/png-pdf.png)
### PileUps (множественная коллизия)
Криптографические коллизии не ограничиваются двумя файлами!
Как показал эксперимент [Nostradamus](https://www.win.tue.nl/hashclash/Nostradamus/) в 2008 году, объединение коллизий в цепочку позволяет создавать коллизии более чем для двух файлов.
Первые коллизии могут быть идентичными или с выбранным префиксом, последующие должны быть с выбранным префиксом.
Вы можете называть их мультиколлизиями, но я предпочитаю *pileups* — так короче :)
#### PE - PNG - MP4 - PDF
Объединив все ранее полученные знания, я использовал 3 коллизии с выбранным префиксом, чтобы создать 4 разных префикса для разных типов файлов: документ (PDF), видео (MP4), исполняемый файл (PE) и изображение (PNG).
*диаграмма pileup PE/PNG/MP4/PDF*
Этот скрипт универсален и мгновенен:
Примеры: [commodore.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/pileup.pdf) ⟷ [diagram.png](https://github.com/corkami/collisions/blob/HEAD/examples/pileup.png) ⟷ [kidmo.mp4](https://github.com/corkami/collisions/blob/HEAD/examples/pileup.mp4) ⟷ [sumatra18.exe](https://github.com/corkami/collisions/blob/HEAD/examples/pileup.exe)
Поскольку вы можете распространять только один файл и угадать остальные значения префиксов из него невозможно, решением будет встроить все префиксы коллизии в JavaScript-код и вставить его в ваши PoC, превратив файлы в [HTML-полиглоты](https://github.com/corkami/collisions/blob/HEAD/examples/polyglot.html), чтобы легко делиться соответствующими коллизирующими файлами.
В [выпуске 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-архива):
Спасибо Рафалу Хиршу за постоянную помощь с JavaScript.
## Варианты использования
Лучше вообще отказаться от MD5, потому что анализ файлов слишком трудоёмок и слишком рискован!
### Gotta collide 'em all!
Ещё одно применение мгновенных, переиспользуемых и универсальных коллизий — спрятать любой файл заданного типа, например PNG, за фиктивными файлами (или за одним и тем же файлом каждый раз), что на самом деле делается простой конкатенацией с одним и тем же префиксом после удаления сигнатуры — это можно делать даже на уровне библиотеки!
С точки зрения строгого разбора все ваши файлы будут показывать одно и то же содержимое, а вредоносные изображения будут раскрыты как файл с тем же MD5, что и ранее собранный.
Возьмём два файла:
⟷
и создадим их коллизию с одним и тем же PNG.
Теперь они показывают одно и то же фиктивное изображение и абсолютно идентичны вплоть до 2-го изображения на уровне файла!
⟷
Их вредоносная полезная нагрузка скрыта за файлом с таким же MD5 в каждом случае.
### Компрометирующие файлы
Ещё один вариант использования коллизий — спрятать нечто компрометирующее внутри чего-то невинного, но желаемого: если единственный способ собрать улики — сравнение слабых хэшей, то вы не сможете отрицать, что у вас нет другого файла (показывающего компрометирующее содержимое, но скрывающего невинное).
Программное обеспечение обычно сосредоточено на (быстром) разборе, а не на детальном анализе файлов.
*изображение, показывающее разные превью под разными вкладками EnCase Forensic*
## Неудачи
Не все форматы могут иметь универсальные переиспользуемые префиксы: если между магической сигнатурой и стандартными заголовками, которые критичны и специфичны для каждого файла, нельзя вставить какой-либо контейнер данных, то универсальные коллизии невозможны.
Конечно, можно по-прежнему превращать старые файлы в новые и даже использовать код для ветвления на две разные полезные нагрузки, но это скорее перенос полезных нагрузок, чем коллизия структуры файлов.
### ELF
Заголовок ELF обязателен по смещению 0 и с самого начала содержит критическую информацию, такую как 32b/64b, порядок байтов и ABI, поэтому невозможно иметь универсальный префикс, а затем блоки коллизии до критических параметров, специфичных для исходного файла.
### Mach-O
Mach-O даже не начинается с одной и той же магии для 32b (`feedface`) и 64b (`feedfacf`). Сразу после этого идут количество и размер команд (таких как определение сегмента, symtab, версия,...).
Как и в случае с ELF, переиспользуемые коллизии невозможны.
### Java Class
Сразу после стартовой магии расположены версии (что может быть проблематично), но также и количество элементов constant pool, которое довольно специфично для каждого файла, поэтому универсальных коллизий для всех файлов не существует.
Однако многие файлы всё же имеют общую версию, и мы можем дополнить самый короткий constant pool до наибольшего значения счётчика. Сначала вставьте *UTF8 literal*, чтобы выровнять информацию, затем объявите ещё один, злоупотребив его длиной через UniColl (длина хранится в 16 байтах в порядке big endian).
Однако это потребует манипуляций с кодом, поскольку все индексы пула будут смещены.
Мгновенные переиспользуемые MD5-коллизии для Java Class должны быть возможны, но требуют анализа и модификации кода.
### TAR
**TL;DR** Переиспользуемых коллизий для TAR-файлов нет, не существует другой стратегии, кроме коллизии с выбранным префиксом.
Tape Archives — это последовательность объединённых заголовков и содержимого файлов, всё выровнено по 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 с JPG — это [первоначальная реализация](http://shattered.io) атаки Shattered, но это просто чистый трюк с JPG внутри PDF-документа.
3. PNG: Safari/Preview требует, чтобы чанк `IHDR` находился на первом месте, до любого блока коллизии. Это препятствует созданию универсального префикса, и в таком случае коллизия ограничена конкретными размерами, цветовым пространством, BPP и чересстрочностью.
4. Форматы Atom/Box, такие как MP4, могут работать с одним и тем же префиксом для разных подформатов. Некоторые подформаты, такие как JPEG2000 или HEIF, требуют дополнительной настройки, но стратегия эксплуатации та же — просто коллизия невозможна между подформатами, только с парой префиксов для конкретного подформата.
5. Atom/Box совместим с Shattered при использовании 64-битных длин.
6. Некоторые форматы на основе Zip могут эксплуатироваться универсально.
7. Для лучшей совместимости ZIP требуется две UniColl для полного архива, и эти коллизии зависят от содержимого обоих файлов.
## Тестовые файлы
[Здесь](https://github.com/corkami/collisions/blob/HEAD/examples/free/README.md) находятся свободные (без авторских прав, без PII) тестовые коллизирующие пары.
# Обнаружение
Существуют разные способы обнаружения коллизий хэшей в файлах.
1. Два файла: если у вас есть два или более файлов с разным содержимым и одинаковым хэшем, просто сравните их!
Однако, если у вас только один файл, может быть трудно понять, содержит ли файл коллизию хэша.
2. Структура файла: анализируйте файл на границах блоков, и если вы заметите блоки с высокой энтропией и, возможно, одинаковый префикс/суффикс, вы, вероятно, сможете определить, какая коллизия используется, но это очень чревато ошибками. В случае коллизии с выбранным префиксом заметить её может быть невозможно, поскольку оба файла могут быть в основном разными, за исключением большинства блоков коллизии.
3. Вычисление хэша: используйте реализацию (на [C](https://github.com/cr-marcstevens/hashclash/tree/collisiondetection/src/collisiondetection) или [Go](https://github.com/therealmik/detectcoll)) DetectColl Марка Стивенса (см. его статью [Counter-cryptanalysis](https://marc-stevens.nl/research/papers/C13-S.pdf)). Для этого требуется только один файл, но необходимо, чтобы коллизия находилась в рабочем состоянии (точный префикс и соответствующие ему блоки коллизии), и это медленно.
DetectColl выдаёт техническую информацию о самой коллизии и показывает `*coll*` рядом с коллизионным хэшем.
## Пример
На примере сертификата вредоносного ПО Flame:```
$ detectcoll flame.der
Found collision in block 11:
dm: dm4=80000000 dm11=ffff8000 dm14=80000000
ihv1=1ba33aac3a7f9ed70aec349b40390e85
ihv2=9ba33aac3c7f60ee8cebf69bc2391085
*coll* c38a66643af816f8438b375b5f42ccbb flame.der
ba2499ba3dda9ef818f854b75a2bd1cd9f2b7bed flame.der
Поскольку DetectColl может определять блоки, используемые для коллизии хешей, он может смягчать коллизию с помощью безопасных хешей: если обнаружен блок коллизии, он обрабатывает его повторно, чтобы разрушить свойство коллизии. Таким образом, DetectColl способен различать разное содержимое с помощью одной и той же хеш-функции, несмотря на коллизии в файле.
Короче говоря:
Пример с оригинальной коллизией Ванга 2005 года:``` $ md5sum wang* 79054025255fb1a26e4bc422aef54eb4 *wang1.bin 79054025255fb1a26e4bc422aef54eb4 *wang2.bin
Безопасный MD5 для этих файлов:```
$ detectcoll wang1.bin | grep coll
*coll* ff531291d102a41aa131e0e09f64ca60 wang1.bin
The input chunk is empty — no content was provided to translate. Please supply the Markdown content for chunk 55 of 65, and I'll translate it into Russian according to the specified rules.``` $ detectcoll wang2.bin | grep coll coll 6a8e7124724d5c819401afc202a4fbd0 wang2.bin
## Сигнатуры
Для простоты вы можете разобрать вывод Detectcoll с помощью этого [скрипта](https://github.com/corkami/collisions/blob/HEAD/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 по-прежнему может обнаруживать коллизии с помощью «стандартных» хэшей.
Примеры с PoCorGTFO 0x14 (NES+PDF хэшквин с альтернативной обложкой).
Безопасные хэши могут найти только одну коллизию:``` $ 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/HEAD/papers/Illies_NIST_05.pdf) - Max Gebhardt, Georg Illies, Werner Schindler
- 2014:
- [Вредоносное хэширование: вариант 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
- [Postscript, показывающий свой собственный MD5](https://archive.org/stream/pocorgtfo14#page/n45/mode/1up) — Gregor "Greg" Kopf
- [PDF, который показывает свой собственный MD5](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 — NES ROM, который выводит свой собственный MD5-хэш!](https://archive.org/stream/pocorgtfo14#page/n55/mode/1up) — Evan Sultanik, Evan Teran
- 2018:
- [Создание SHA-1-коллизий в PDF с помощью PDFLaTeX.](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up) — Ange Albertini
- 2020:
---
[Read more](https://github.com/corkami/collisions)
| Префикс | = | Префикс |
|---|
| Коллизия A | ≠ | Коллизия B |
| A | = | |
| = | B |