corkami/collisionsHash collisions and exploitations
By Ange Albertini and Marc Stevens.
P: É possível fazer um arquivo obter um MD2/MD4/MD5/MD6/SHA1/SHA2/SHA3 arbitrário, ou o mesmo hash de outro arquivo?
R: Não.
P: É possível criar 2 arquivos diferentes com o mesmo hash?
R: Com MD5, em alguns segundos em um computador comum. Com SHA1, é possível mas não prático para usuários finais (Complexidade: 2^61.2 Preço: $11k).
P: É possível fazer 2 arquivos diferentes obterem o mesmo hash anexando dados?
R: Com MD5, em algumas horas em um computador comum. Com SHA1, é possível mas não prático para usuários finais (Complexidade: 2^63.4 Preço: $45K)
P: Os 2 arquivos permanecerão válidos?
R: Em geral, sim, pois a maioria dos formatos de arquivo tolera dados anexados. Por outro lado, as assinaturas dos arquivos provavelmente serão quebradas.
P: É possível fazer 2 arquivos diferentes com conteúdos arbitrários e o mesmo hash?
R: Sim, pode ser instantâneo contando com estruturas especiais de arquivo:
P: Para quais formatos posso obter um par de arquivos com colisão MD5 instantânea?
R: JPG, PNG, GIF, GZIP, Portable Executable, MP4, JPEG2000, PDF, DOCX/PPTX/XSLX, EPUB, 3MF, XPS. Basta executar o script específico.
P: E para SHA1?
R: Para SHA1, JPG em um PDF é calculado e implementado.
P: E quanto aos formatos já suportados para MD5 (JPG, PNG...), mas para SHA1?
R: Eles provavelmente também são suportados com SHA1, mas suas colisões ainda não foram calculadas.
P: Os cálculos são mais rápidos para conteúdos semelhantes (mas diferentes)?
R: Não. Qualquer diferença mínima exige um cálculo completo.
P: Quais formatos não têm esse atalho?
R: ELF, Mach-O, Java Class, TAR, ZIP (entre outros...)
P: Colisões clássicas (em algumas horas) ainda são possíveis com esses formatos?
R: Sim, desde que qualquer quantidade de dados anexados seja tolerada (ou seja, provavelmente não ZIP ou Class).
P: Você fornece exemplos de colisões?
R: Sim.
O objetivo é explorar extensivamente ataques existentes - e mostrar no caminho o quão fraco é o MD5 (colisões instantâneas de qualquer JPG, PNG, PDF, MP4, PE...) - e também explorar em detalhes formatos de arquivo comuns para determinar como eles podem ser explorados com ataques atuais ou futuros.
De fato, o mesmo truque de formato de arquivo pode ser usado em vários hashes (os mesmos truques de JPG foram usados para MD5, SHA-1 malicioso e SHA1), desde que as colisões sigam os mesmos padrões de bytes.
Este documento não trata de novos ataques (o mais recente foi documentado em 2012), mas de novas formas de exploração de ataques existentes.
Status atual dos ataques conhecidos:
fazer um arquivo obter o hash de outro arquivo ou um hash específico: impossível
obter dois arquivos diferentes com o mesmo MD5: instantâneo
fazer dois arquivos arbitrários obterem o mesmo MD5: algumas horas (72 horas.core)
fazer dois arquivos arbitrários de formatos específicos (PNG, JPG, PE...) obterem o mesmo MD5: instantâneo
obter dois arquivos diferentes com o mesmo SHA1: 6500 anos.core
(*) exemplo com crypt - obrigado Sven!```
import crypt crypt.crypt("5dUD&66", "br") 'brokenOz4KxMc' crypt.crypt("O!>',%$", "br") 'brokenOz4KxMc'
# Ataques
MD5 e SHA1 trabalham com blocos de 64 bytes.
Se dois conteúdos A & B tiverem o mesmo hash, então anexar o mesmo conteúdo C a ambos manterá o mesmo hash.``` text
hash(A) = hash(B) -> hash(A + C) = hash(B + C)
Colisões funcionam inserindo, em um limite de bloco, um número de blocos de colisão calculados que depende do que veio antes no arquivo. Esses blocos de colisão têm aparência muito aleatória, com algumas diferenças menores (que seguem um padrão específico para cada ataque) e introduzem pequenas diferenças enquanto, eventualmente, fazem os hashes terem o mesmo valor depois desses blocos.
Essas diferenças são exploradas para criar arquivos válidos com propriedades específicas.
Formatos de arquivo também funcionam de cima para baixo, e a maioria deles funciona por chunks de nível de byte.
Alguns chunks de 'comentário' podem ser inseridos para alinhar os chunks do arquivo aos limites de bloco, para alinhar estruturas específicas às diferenças dos blocos de colisão, para esconder o restante da aleatoriedade dos blocos de colisão dos parsers de arquivo, e para esconder conteúdo de outra forma válido do parser (para que ele veja outro conteúdo).
Esses chunks de 'comentário' muitas vezes não são comentários oficiais reais: são usados apenas como contêineres de dados que são ignorados pelo parser (por exemplo, chunks PNG com ID começando em minúscula são auxiliares, não críticos).
Na maioria das vezes, uma diferença nos blocos de colisão é usada para modificar o comprimento de um chunk de comentário,
que normalmente é declarado logo antes dos dados desse chunk:
no espaço entre a versão menor e a versão mais longa desse chunk,
outro chunk de comentário é declarado para saltar sobre o conteúdo A de um arquivo.
Após esse conteúdo de arquivo A, basta anexar outro conteúdo de arquivo B.
Como os formatos de arquivo geralmente definem um terminador que faz os parsers pararem depois dele,
A encerrará o parsing, o que fará o conteúdo anexado B ser ignorado.
Então normalmente são necessários pelo menos dois comentários - frequentemente três:
Essas propriedades comuns dos formatos de arquivo tornam isso possível - elas não são normalmente vistas como fraquezas, mas podem ser detectadas ou normalizadas:
| Prefixo | = | Prefixo |
|---|---|---|
| Colisão A | ≠ | Colisão B |
| Sufixo | = | Sufixo |
Ambos os arquivos são quase idênticos (seus conteúdos têm apenas alguns bits de diferença)
Exploração:
Empacote dois conteúdos e, então, escolha uma das opções:
Dois arquivos com esta estrutura:
exibirão A ou B.
Versão final em 2009.
.. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. X. .. .. .. .. .. .. .. .. .. .. .. ..
.. .. .. .. .. .. .. .. .. .. .. .. .. X. .X ..
.. .. .. .. .. .. .. .. .. .. .. X. .. .. .. ..
As diferenças não estão perto do início/fim dos blocos, então é muito difícil explorar, já que você não controla nenhum byte próximo. Uma solução potencial é usar força bruta nos bytes ao redor - cf PoCGTFO 14:10.
Exemplos:
Com um prefixo vazio:``` 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)
**Variante**: existe uma [colisão MD5 de bloco único](https://marc-stevens.nl/research/md5-1block-collision/) mas leva cinco semanas de computação.
Aqui está uma [gravação](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll.svg) de uma computação FastColl sem prefixo
e [outra](https://github.com/corkami/collisions/blob/HEAD/examples/fastcoll-prefix.svg) com um prefixo.
### [UniColl](https://github.com/corkami/collisions/blob/HEAD/unicoll.md) (MD5)
Documentado em [2012](https://www.cwi.nl/system/files/PhD-Thesis-Marc-Stevens-Attacks-on-Hash-Functions-and-Applications.pdf#page=199), implementado em [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) permite controlar alguns bytes nos blocos de colisão,
antes e depois da primeira diferença, o que o torna uma colisão de prefixo idêntico com algumas diferenças controláveis, quase como uma colisão de prefixo escolhido.
Isso é muito útil e, melhor ainda, a diferença pode ser muito previsível:
no caso de `m2+= 2^8` (também conhecido como `N=1` / `m2 9` no script [poc_no.sh](https://github.com/cr-marcstevens/hashclash/blob/master/scripts/poc_no.sh#L30) do HashClash),
a diferença é +1 no 9º byte, o que a torna muito explorável,
pois você pode até pensar na colisão mentalmente:
o 9º caractere dessa frase será substituído pelo próximo: `0` substituído por `1`, `a` substituído por `b`..
- tempo: alguns minutos (depende da quantidade de bytes que você quer controlar )
- espaço: dois blocos
- diferenças: ```
.. .. .. .. DD .. .. .. ..
.. .. .. .. +1 .. .. .. ..
Exemplos com N=1 e 20 bytes de texto definido nos blocos de colisão:```
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 tem menos controle do que uma colisão de prefixo escolhido verdadeira,
mas é muito mais rápida, especialmente porque usa apenas dois blocos.
Aqui está uma [gravação](https://github.com/corkami/collisions/blob/HEAD/examples/unicoll.svg) de um cálculo de UniColl.
### [Shattered](http://shattered.io) (SHA1)
Documentado em [2013](https://marc-stevens.nl/research/papers/EC13-S.pdf), calculado em [2017](http://shattered.io).
- tempo: 6500 anos.CPU e 110 anos.GPU
- espaço: dois blocos
- diferenças: ```
.. .. .. DD ?? ?? ?? ??
or
?? ?? ?? DD .. .. .. ..
A diferença entre os blocos de colisão de cada lado é esta máscara 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
Exemplos: [PoC||GTFO 0x18](https://github.com/angea/pocorgtfo#0x18) usa os prefixos SHA1 calculados,
reutilizando a imagem diretamente da fonte PDFLaTeX (veja [artigo 18:10](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up)),
mas também verifica o valor dos prefixos via JavaScript na página HTML (o arquivo é poliglota, ZIP HTML e PDF).
## Colisões de prefixo escolhido
Elas permitem colidir qualquer conteúdo.
| 𝓐 | ≠ | 𝔅 |
| :----: |:-:| :----: |
| Colisão *A* | ≠ | Colisão *B* |
1. pegue dois prefixos arbitrários
2. preencha o mais curto para ficar tão longo quanto o mais longo. ambos são preenchidos até o próximo bloco - menos 12 bytes
- esses 12 bytes de dados aleatórios serão adicionados em ambos os lados para aleatorizar a busca de aniversário
3. X blocos de quase-colisão serão calculados e anexados.
Quanto menos blocos, mais longa a computação.
Ex: [400 kHours para um bloco](https://www.win.tue.nl/hashclash/SingleBlock/). 72 horas.núcleos para nove blocos com [HashClash](https://github.com/cr-marcstevens/hashclash).
Colisões de prefixo escolhido são poderosas, mas podem levar muito tempo apenas para um par de arquivos.
### [HashClash](https://github.com/cr-marcstevens/hashclash) (MD5)
Versão final em [2009](https://www.win.tue.nl/hashclash/ChosenPrefixCollisions/).
Exemplos: vamos colidir `yes` e `no`. Levou três horas em 24 núcleos.```
'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 is a very expensive chosen-prefix collision that uses 9 blocks.
Each block has the same xor pattern as 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
Mas mesmo que Shattered seja muito mais fácil de explorar do que FastColl,
as restrições das diferenças nos blocos de colisão são irrelevantes
já que Shambles é uma Colisão de Prefixo Escolhido.
## Resumo de ataques
Hash | Nome | Data | Duração | Tipo de prefixo | Controle próximo à diferença
---- | --------- | ---- | -------- | ----------- | -----------------
MD5 | FastColl | 2009 | 2s | Idêntico | nenhum
| UniColl | 2012 | 7-40min | Idêntico | 4-10 bytes
| HashClash | 2009 | 72h | Escolhido | n/a
| | | | |
SHA1 | Shattered | 2013 | 6500yr | Idêntico | prefixo e sufixo
| Shambles | 2020 | ? | Escolhido | n/a
# Explorações
Colisões de prefixo idêntico costumam ser vistas como (muito) limitadas, mas o prefixo escolhido exige tempo.
Outra abordagem é criar prefixos reutilizáveis por meio de um ataque de prefixo idêntico, como o UniColl - ou de prefixo escolhido para superar algumas limitações - mas reutilizar esse par de prefixos em combinações com dois payloads, como em um ataque clássico de prefixo idêntico.
Uma vez calculado o par de prefixos, colidir dois conteúdos torna-se instantâneo:
é apenas uma questão de ajustar os dados do arquivo (de acordo com formatos de arquivo específicos) para que se encaixem nas especificações dos formatos e nos requisitos do prefixo pré-computado.
## Estratégia padrão
Colisões clássicas de dois arquivos válidos com o mesmo tipo de arquivo.
### JPG
Limitações teóricas e soluções alternativas:
- o segmento *Application* deveria, em teoria, vir logo após o marcador *Start of Image*.
Na prática, isso não é necessário, portanto nossa colisão pode ser genérica: a única limitação é o tamanho da menor imagem.
- o comprimento de um comentário é armazenado em dois bytes, portanto a quantidade que ele pode armazenar é limitada a 65536 bytes (aproximadamente o tamanho de uma foto 400x400)
- em vez de saltar sobre um arquivo JPG completo, pode-se dividir esse arquivo em seus segmentos e adicionar trampolins de salto entre os segmentos
*comentários sobre cada segmento da imagem*
*como os trampolins de comentários funcionam*
- enquanto a maior parte da estrutura de um JPG é composta por segmentos que têm todos o tamanho limitado a 65536 bytes,
os dados comprimidos reais são armazenados no *Entropy Coded Segment*, que não respeita essas limitações:
seu tamanho é desconhecido antecipadamente e cresce além desse limite.
Ele cresce com o tamanho da imagem, tornando a maior parte do tamanho do arquivo em uma imagem baseline (não progressiva).
Para fazer a imagem inteira caber em blocos de 64kb, a maneira fácil é primeiro tentar salvar a imagem como progressiva (o que qualquer software consegue fazer, e divide o ECS normalmente em até seis varreduras). A maneira mais avançada é usar o *JPEGTran* com o parâmetro de linha de comando 'wizard' `--scans` e definir varreduras personalizadas.
Não há outra restrição além dos segmentos de varredura,
portanto uma colisão MD5 de dois JPGs arbitrários é *instantânea* e não precisa de colisão de prefixo escolhido, apenas UniColl.
Com o [script](https://github.com/corkami/collisions/blob/HEAD/scripts/jpg.py):```
21:07:35.65>jpg.py Ange.jpg Marc.jpg
21:07:35.75>
Exemplos:
⟷
2 JPGs com colisão MD5
Aqui está um exemplo da definição de scans do JPEGTran para transformar uma imagem RGB 1944x2508 em um JPG 100% com 20 scans, todos cabendo em 64kb.``` // : -, , ;
// 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;
Resultado:
*uma imagem RGB de 1944x2508 como um JPG de 100% com 20 passes*
### PNG
Limitações teóricas e soluções alternativas:
- O PNG usa CRC32 no final de seus chunks, mas na prática eles são ignorados. Podem estar corretos, mas não é obrigatório.
- os metadados da imagem (dimensões, espaço de cores...) são armazenados no chunk `IHDR`,
que em teoria deveria vir logo após a assinatura (ou seja, antes de qualquer comentário potencial),
o que significaria que só podemos pré-calcular colisões de imagens com os mesmos metadados.
No entanto, esse chunk pode, na verdade, ficar após um bloco de comentários (na vasta maioria dos leitores, exceto os da Apple), então podemos colocar os dados de colisão antes do cabeçalho,
o que possibilita colidir qualquer par de PNGs com uma única pré-computação.
Como um chunk PNG tem um comprimento de quatro bytes, não há necessidade de modificar a estrutura de nenhum dos arquivos: podemos pular uma imagem inteira de uma vez.
Podemos inserir quantos chunks descartados quisermos, então podemos adicionar um para alinhamento, depois um cujo comprimento será alterado por um UniColl. Assim, o comprimento será `00` `75` e `01` `75`.
Assim, uma colisão MD5 de duas imagens PNG arbitrárias é *instantânea*, sem pré-requisitos (nenhum cálculo, apenas pequenas alterações nos arquivos), e não precisa de colisão de prefixo escolhido, apenas UniColl.
Com o [script](https://github.com/corkami/collisions/blob/HEAD/scripts/png.py):```
19:27:04.79>png.py nintendo.png sega.png
19:27:04.87>
Exemplos:
⟷
2 PNGs com colisão MD5 e propriedades diferentes
Aqui está uma gravação de toda a operação.
A maioria dos leitores aceita sem problemas arquivos PNG que começam com um chunk que não é IHDR.
No entanto, alguns (como Safari e Preview - algum outro?) não toleram isso. Nesse caso, o cabeçalho da imagem e suas propriedades (dimensões, espaço de cores) devem vir primeiro, antes de qualquer bloco de colisão.
Nesse caso, ambos os arquivos em colisão devem ter as mesmas propriedades. Novamente, UniColl é suficiente e, claro, o par de prefixo calculado pode ser reutilizado para qualquer outro par de arquivos com as mesmas propriedades.
Aqui está um script para colidir qualquer par desses arquivos, que executa UniColl se necessário para calcular o par de prefixo.
Exemplos:
⟷
⟷
2 pares de PNGs com colisão MD5 e propriedades idênticas para máxima compatibilidade
Aqui está uma gravação de toda a operação quando UniColl é invocado,
e outra quando o prefixo já foi calculado.
GIF é complicado:
No entanto, os blocos de comentário seguem uma estrutura peculiar: é uma cadeia de <length:1> <data:length> até que um comprimento nulo seja definido.
Isso torna qualquer byte não nulo um 'salto para frente' válido. O que o torna adequado para uso com FastColl,
como mostrado em PoC||GTFO 14:11.
Então, pelo menos, mesmo que não possamos ter um prefixo genérico, podemos colidir qualquer par de GIFs com os mesmos metadados (dimensões, paleta) e só precisamos de um segundo de FastColl para calcular seu prefixo.
Agora o problema é que não podemos saltar sobre uma imagem inteira como PNG ou sobre uma estrutura grande como JPG.
Uma possível solução alternativa é massagear os dados compactados ou dividir a imagem em áreas minúsculas, como no caso do hashquine de GIF, mas isso não é o ideal.
Outra ideia que funciona genericamente é que os dados da imagem também são armazenados usando essa estrutura de sequência length data:
então, se pegarmos dois GIFs sem animação, só precisamos:
Com uma configuração mínima (apenas algumas centenas de bytes de overhead), podemos deslizar sobre qualquer imagem GIF e contornar a limitação de 256 bytes. Essa ideia foi sugerida pelo Marc, e é brilhante!
Então, no final, as limitações atuais do GIF para colisões MD5 instantâneas são:
gifsicle --use-colormap webUm atalho fácil para normalizar imagens GIF estáticas é transformá-las em quadros de animação da mesma imagem, então podemos usar um script para reutilizar ou calcular blocos FastColl e criar um par de arquivos que mostre cada uma delas.
Exemplos:
⟷
2 GIFs com colisão MD5 - imagens por KidMoGraph
Aqui está uma gravação de toda a operação.
Especificações GZIP v4.3: RFC 1952 (1996).
1F 8B. Se não corresponder à assinatura, a análise será interrompida, o que pode ser usado para forçar a interrupção da análise entre dois payloads, mas isso acionará alguns avisos que podem causar problemas. Outra estratégia é adicionar um membro vazio extra no final do arquivo e fazer com que a análise de ambos os payloads termine ali - no membro ou em seu corpo.filename opcional e o file comment são terminados em nulo, enquanto o Extra field é definido por tamanho de 16 bits, portanto abusável. Ele é composto de um ou mais subcampos, com um ID e seu próprio subcomprimento, mas os subcampos não são obrigatórios - pouquíssimos são oficialmente definidos.Portanto, um membro gzip vazio com um campo extra é um hospedeiro parasita perfeito.
Se o arquivo superior for grande demais para caber em um campo extra, seu fluxo descompactado pode ser dividido em arquivos menores até que todos caibam em campos extras.
Após o cabeçalho de um membro, vêm seu corpo compactado, seu CRC32 e seu tamanho descompactado (não obrigatório). Portanto, um corpo de dados vazio com CRC32 e tamanho nulos forma um postwrap genérico, que pode até ser compartilhado por diferentes cabeçalhos de membros.
Várias implementações dependem do tamanho descompactado do último membro em vez da soma de todos os membros. Portanto, nossos arquivos em colisão mostrarão que têm tamanho nulo, porque esses arquivos terminam com um membro vazio usado como trampolim.
Aqui está um script para gerar colisões MD5 instantâneas de dois arquivos GZip. Ele passa a maior parte do tempo descompactando e recomprimindo dados se os arquivos de entrada forem grandes - os prefixos de colisão são pré-computados. Dividir membros sem descompactar não é possível, pois o CRC32 descompactado precisa ser calculado.
Um .tar.gz é apenas o arquivo gzip de um arquivo tar. Funcionará bem com tar compactado com gzip, ao contrário do próprio tar.
Exemplos: collision1.tar.gz (Pacome) ⟷ collision2.tar.gz (Reg)
LZ4 e Zstandard são 2 formatos de compactação diferentes, com uma estrutura geral semelhante:
eles são feitos de frames, cada um começando com um magic específico: 0xFD2FB528 para frames Zstandard, 0x184D2204 para frames Lz4.
Eles também compartilham os mesmos frames TLV 'skippable', começando com 4 bytes de mágicos no intervalo 0x184D2A50 - 0x184D2A5F, depois o Comprimento dos dados do usuário (4 bytes, little-endian), e então os próprios Dados do Usuário.
Esses frames são totalmente opcionais, de qualquer comprimento e repetíveis. Os arquivos podem começar com esses frames. Portanto, esses frames podem ser encadeados para criar um prefixo de colisão genérico perfeito, entre 2 formatos.
Aqui está um script para gerar colisões MD5 instantâneas de dois arquivos Zstd/Lz4. Como no Gzip, 2 arquivos diferentes serão visíveis do exterior, independentemente do conteúdo: por exemplo, um .cpio.zst.
Exemplos:
O Portable Executable tem uma estrutura peculiar:
Então a estratégia é:
DOS/Collisions/Header1/Header2. Você só precisa aplicar um delta aos offsets das duas tabelas de seções.Isso significa que é possível colidir instantaneamente qualquer par de executáveis PE. Mesmo que eles usem subsistemas ou arquiteturas diferentes.
Embora colisões de executáveis sejam geralmente triviais via qualquer loader, esse tipo de exploração aqui é transparente: o código é idêntico e carregado no mesmo endereço.
Exemplos: tweakPNG.exe (GUI) ⟷ fastcoll.exe (CLI)
Aqui está um script para gerar colisões MD5 instantâneas de Executáveis Windows.
O contêiner desse formato é uma sequência de chunks Length Type Value chamados Atoms.
O comprimento é um big-endian de 32 bits e cobre a si mesmo, o tipo e o valor, portanto o comprimento normal mínimo é 8
(o tipo é uma string de 4 caracteres ASCII).
Se o comprimento for nulo, o atom ocupa o restante do arquivo - como atoms jp2c em arquivos JP2.
Se for 1, então o Tipo é seguido por um comprimento de 64 bits, transformando o atom em Type Length Value, tornando-o compatível com outras colisões como Shattered.
Alguns atoms contêm outros atoms: nesses casos, eles são chamados de boxes. É por isso que essa estrutura, sem nome de outra forma, é chamada de "atom/box".
Esse formato "atom/box" usado em MP4 é, na verdade, um derivado do Apple Quicktime, e é usado por muitos outros formatos (JP2, HEIF, F4V).
O primeiro tipo de atom é geralmente ftyp, o que permite diferenciar o formato de arquivo real.
O formato é bastante permissivo:
basta encadear atoms free, abusar do comprimento de um deles com UniColl e então saltar sobre o primeiro payload.
Para arquivos MP4, a única coisa a adicionar é ajustar as tabelas stco (Sample Table - Chunk Offsets) ou co64 (o equivalente de 64 bits), pois são offsets absolutos(!) que apontam para os dados de vídeo mdat - e elas são de fato aplicadas!
Isso resulta em um script que colide instantaneamente qualquer vídeo arbitrário - e, como mencionado, pode funcionar em outros formatos além do MP4.
Exemplos (vídeos por KidMoGraph):
comprimentos de 32b (padrão) collision1.mp4 ⟷ collision2.mp4
⟷
comprimentos de 64b collisionl1.mp4 ⟷ collisionl2.mp4
⟷
Observe que alguns visualizadores (OS X, Safari, FireFox) não permitem um arquivo que comece com um Atom que não seja ftyp.
Nesse caso, o prefixo precisa cobrir isso, e não é tão genérico, mas além disso é a mesma estratégia - apenas limitada a um único tipo de arquivo.
Arquivos JPEG2000 geralmente começam com a estrutura Atom/Box como no MP4,
então o último atom jp2c normalmente vai até o final do arquivo (comprimento nulo),
e a partir desse ponto segue a estrutura JFIF, como JPEG (começando com FF 4F como marcador de segmento).
A forma puramente JFIF também é tolerada; nesse caso, a colisão é como JPEG: compatível com Shattered, mas com comentários limitados a 64Kb.
Por outro lado, se você manipular arquivos JPEG2000 com Atom/Box, você não tem essa limitação.
Como mencionado antes, se você estiver tentando colidir essa estrutura e
se houver mais restrições - por exemplo, começar com um atom free não é tolerado por alguns formatos -
então você pode calcular outros pares de prefixo UniColl específicos para esse formato:
JPEG2000 parece exigir um atom 'jP ' primeiro antes do ftyp usual,
mas, além disso, essa é a única restrição: não há necessidade de realocar nada.
Portanto, o script resultante é ainda mais simples!
Exemplos: collision1.jp2 ⟷ collision2.jp2
sobre Shattered
A exploração do Shattered não era um truque de PDF, mas um truque de JPG dentro de um PDF.
Ela apenas permitia que um PDF contivesse um objeto compactado em JPG que pudesse ter dois conteúdos diferentes. Ambos os PDFs precisavam ser totalmente idênticos no restante.
Observe que os documentos podem ser totalmente normais e podem simplesmente recortar o JPG em colisão e exibi-lo em lugares diferentes, como documentos de várias páginas.
Exemplos: o artigo Shattered, modificado ⟷ o artigo Shattered, original
o artigo Shattered usando um JPG em colisão em dois lugares
Colisões de PDF com MD5
Com MD5 (e outros padrões de colisão), podemos fazer colisões de PDF no nível do documento, sem nenhuma restrição em nenhum dos arquivos!
O PDF tem uma estrutura muito diferente de outros formatos de arquivo. Ele usa números de objetos e referências para definir uma árvore. O documento inteiro depende do elemento Root.
Este PDF (válido)``` 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>>
é equivalente a:``` 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>>
Truques:
XREF.Então, armazenar duas árvores de documentos no mesmo arquivo é aceitável. Só precisamos fazer o objeto raiz referenciar o objeto raiz de um dos dois documentos.
Então, só precisamos pegar dois documentos,
renumerar objetos e referências para que não haja sobreposição,
criar uma colisão de modo que o número do elemento referenciado como objeto raiz possa ser alterado mantendo o mesmo valor de hash,
o que se encaixa perfeitamente no UniColl com N=1, e ajustar a tabela XREF de acordo.
Desta forma, podemos colidir com segurança qualquer par de PDFs, independentemente dos números de página, dimensões, imagens...
comentários
Um PDF pode armazenar dados externos de duas maneiras:
\r e \n).
Isso pode ser usado dentro de um objeto de dicionário, para modificar, por exemplo, uma referência a objeto, via UniColl.
Portanto, este é um objeto PDF válido mesmo que contenha blocos de colisão binários - basta tentar novamente até que não haja caracteres de nova linha: ```
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
texto em colisão
O primeiro caso possibilita destacar a beleza do UniColl, uma colisão em que as diferenças são previsíveis, para que você possa escrever poesia sobre dados em colisão - graças a Jurph!
Em vez de modificar a estrutura do documento e enganar parsers, vamos apenas usar blocos de colisão diretamente para produzir texto diretamente, com leitura alternativa!``` 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. ^ ^
Exemplos: [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)
*Uma verdadeira criação artística criptográfica :)*
(Nota: eu errei com a compatibilidade com a Adobe, mas a culpa é minha, não da UniColl)
**estrutura de documento em colisão**
Quer você use o UniColl como comentário inline ou prefixo escolhido em um objeto de stream fictício, a estratégia é semelhante:
embaralhe os números dos objetos, depois faça o objeto Root apontar para objetos diferentes. Assim, ao contrário do Shattered, isso significa colisão instantânea de qualquer par arbitrário de PDFs, no nível do documento.
Um truque útil é que a saída do [`mutool clean`](https://mupdf.com/docs/manual-mutool-clean.html) é previsível de forma confiável,
portanto, pode ser usada para normalizar PDFs como entrada e corrigir seu PDF mesclado, mantendo as partes importantes do arquivo inalteradas.
O MuTool não descarta chaves/valores falsos - a menos que solicitado, e os mantém na mesma ordem,
portanto, usar entradas de dicionário falsas, como `/MD5_is /REALLY_dead_now__`, é perfeito para alinhar as coisas de forma previsível sem precisar de outro tipo de comentário.
No entanto, ele não mantém comentários em dicionários (portanto, sem truque de comentário inline)
Uma maneira fácil de fazer a operação de embaralhamento de objetos sem complicação é apenas mesclar os dois arquivos PDF
via `mutool merge` e dividir o objeto `/Pages` em dois.
Para abrir espaço para esse objeto, basta mesclar um PDF fictício na frente dos dois documentos.
Opcionalmente, crie uma referência falsa para o array pendente
para evitar que a coleta de lixo exclua o segundo conjunto de páginas.
**Exemplo**:
com este [script](https://github.com/corkami/collisions/blob/HEAD/scripts/pdf.py),
leva [menos de um segundo](https://github.com/corkami/collisions/blob/HEAD/examples/pdf.log) para colidir os dois artigos PDF públicos, como Spectre e Meltdown:
Exemplos: [spectre.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/collision1.pdf) ⟷ [meltdown.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/collision2.pdf)
Extensão possível: encadear blocos UniColl para também manter pares dos vários [objetos não críticos](https://www.adobe.com/content/dam/acom/en/devnet/pdf/pdfs/PDF32000_2008.pdf#page=81)
que podem ser referenciados no objeto Root - como `Outlines`, `Names`, `AcroForm` e Ações Adicionais (`AA`) - nos arquivos de origem originais.
**no PDFLaTeX**
As técnicas anteriores funcionam com apenas um par de arquivos PDF,
mas também é possível fazê-lo diretamente do código-fonte TeX
via [operadores PDFTeX específicos](http://texdoc.net/texmf-dist/doc/pdftex/manual/pdftex-a.pdf).
Você pode definir objetos diretamente - incluindo chave e valores fictícios para alinhamentos - e definir objetos vazios para reservar alguns slots de objetos, incluindo isso bem no início do seu código-fonte 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
Não se esqueça de normalizar a saída do PDFLaTeX - com mutool, por exemplo - se necessário:
É difícil obter builds reproduzíveis de PDFLaTeX entre distribuições - você pode até querer fixar o horário de execução para obter o hash exato, se necessário.
Você pode esperar que JPG seja apenas imagens, mas em um PDF e em alguns leitores de PDF (não navegadores, como Evince e Adobe Reader), ele pode ser usado como conteúdo de página, assim como qualquer outro objeto incorporado, que é incorporado em uma imagem JPEG.
Para armazenar os dados JPEG sem perdas, armazene-os em escala de cinza 100%; em seguida, use uma imagem de uma única linha/coluna, ou repita a linha de dados 8 vezes (já que os blocos JPEG são 8x8), e seus dados serão armazenados sem perdas e referenciados pelas páginas do PDF.
Exemplos de dois PDFs em colisão SHA-1 via dados de página JPEG (uma imagem em escala de cinza renderizando cores) como conteúdo de página vetorial:
2 PDFs em colisão SHA-1 com dados de imagem armazenados como JPG
É possível referenciar o JPG em colisão duas vezes: como conteúdo de página, sem perdas, o que também se refere a si mesmo como uma imagem com perdas a ser exibida. Novamente, a imagem a ser exibida está em escala de cinza, mas o conteúdo da página pode renderizar algumas cores por meio de operadores de PDF.
O topo da imagem mostra o conteúdo da página repetido 8 vezes.
Exemplos de dois PDFs em colisão SHA-1 via JPEG usado como dados de página e imagem a ser exibida:
Skulls & Crossbones ⟷ Golden Axe
2 PDFs em colisão SHA-1 com JPG usado como imagem e conteúdo de página
TL;DR Não existe uma colisão genérica reutilizável para ZIP, mas existe para formatos baseados em ZIP. Deve ser possível fazer dois arquivos colidirem em 2h.core (36 vezes mais rápido que prefixo escolhido)
Arquivos ZIP são um sanduíche de 3 camadas (no mínimo).
Primeiro vem o conteúdo dos arquivos (sequência de estruturas Local File Header, uma para cada arquivo ou diretório arquivado),
depois um índice (novamente, uma sequência de Central Directory),
e então uma única estrutura que aponta para esse índice (End Of Central Directory).
A ordem dessas camadas não pode ser alterada. Alguns parsers só precisam da estrutura do conteúdo do arquivo, mas essa não é uma forma correta de fazer parsing e pode ser abusada.
Devido a essa ordem obrigatória, não há um prefixo genérico que possa ajudar em qualquer colisão.
abordagem não genérica
Outra abordagem poderia ser simplesmente mesclar os dois arquivos, com suas camadas mescladas, e usar o UniColl - mas com N=2, o que introduz uma diferença no 4º byte - para eliminar a assinatura mágica do End of Central Directory.
Isso significa que seria possível fazer dois ZIPs arbitrários colidirem com um único UniColl e 24 bytes de prefixo definido.
Um End of Central Directory típico, que tem 22 bytes se o comentário estiver vazio:```
00: 504b 0506 0000 0000 0000 0000 0000 0000 PK..............
10: 0000 0000 0000 ......
Se usarmos isto como prefixo (preencher o prefixo para 16 bits) para o UniColl e `N=2`, a diferença está no 4.º byte, matando a magia `.P .K 05 06` ao alterá-la previsivelmente para `.P .K 05 86`.```
00: 504b 0506 0000 0000 0000 0000 0000 0000 PK..............
10: 0000 0000 0000 2121 eb66 cf9d db01 83bb ......!!.f......
20: 2888 4c41 e345 7d07 1634 5d4a 3b61 89a0 (.LA.E}..4]J;a..
30: 0029 94af 4168 2517 0bbc b841 cbf2 9587 .)..Ah%....A....
40: e438 0043 6390 279d 7c9e a01e e476 4c36 .8.Cc.'.|....vL6
50: 527f b1f4 653e d866 f98d 7278 5324 0bd5 R...e>.f..rxS$..
60: b31d ef6d d5d6 1163 5a2e a8a5 21bf eab4 ...m...cZ...!...
70: c59c 028e a913 f6b7 0036 c93f 5092 a628 .........6.?P..(
I don't see any content to translate—the input after "INPUT:" is empty. Please provide the chunk text and I'll translate it.``` 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..(
Isto não é de todo genérico, mas muito mais rápido do que colisão de prefixo escolhido:```
real 12m23.993s
user 112m24.072s
sys 2m0.194s
Um problema é que alguns parsers ainda analisam arquivos ZIP de cabeça para baixo, mesmo que devessem ser analisados de baixo para cima:
uma maneira de garantir que ambos os arquivos sejam analisados corretamente é encadear dois blocos UniColl,
para ativar/desativar cada End of Central Directory.
Para evitar que parsers de ZIP reclamem de espaço não utilizado,
pode-se abusar de Extra Fields,
comentários de arquivo no Central Directory e comentários do arquivo no End of Central Directory.
Exemplo: aqui está um código-fonte de montagem que descreve a estrutura de um ZIP duplo, que pode hospedar dois arquivos compactados diferentes.
Após duas computações UniColl, ele fornece os dois arquivos em colisão: collision1.zip ⟷ collision2.zip
Mesmo que o formato Zip em si não possa ser explorado genericamente como o Gzip, alguns formatos que dependem do Zip podem ser explorados genericamente dentro de arquivos Zip com uma estrutura predefinida. Algumas precauções precisam ser tomadas para tornar a colisão Zip genérica.
Alguns formatos são arquivos múltiplos armazenados em um arquivo Zip e dependem de um arquivo raiz com um nome de arquivo fixo que aponta para outros arquivos no arquivo. Muitos deles usam XML ou texto para o arquivo raiz e armazenam os outros arquivos como estão.
Ideia : fazer 2 conjuntos de arquivos coexistirem no mesmo arquivo e apontar para qualquer um dos conjuntos de arquivos. Uma raiz genérica pode ser armazenada primeiro no início do arquivo, mas os blocos de colisão são armazenados fora do conteúdo do arquivo, no arquivo (já que colisões têm entropia muito alta, é impossível explorar arquivos XML ou somente ASCII com colisões).
Passos:
Colocar 2 conjuntos de arquivos de 2 origens no mesmo arquivo - ou seja, em subdiretórios diferentes.
Modificar o arquivo raiz para apontar alternadamente para cada conjunto.
Como o timestamp, o tamanho e o CRC do arquivo raiz são armazenados tanto no Local File Header - antes do conteúdo do arquivo - quanto no Central Directory - depois do conteúdo do arquivo - esses valores não devem mudar entre as duas versões dos arquivos.
Central Directory, essa cópia do valor pode ser ignorada pelo parser, mas forjar um CRC32 para um valor constante é útil para evitar totalmente o problema.
Forjar o CRC anexando 4 bytes aleatórios provavelmente não será suficiente, pois esses arquivos raiz são tipicamente XML ou texto com sintaxes estritas, então eles se tornariam inválidos.
O CrcHack ajuda muito a forjar CRCs com bits arbitrários e sem força bruta, garantindo que o arquivo de saída seja ASCII e que os bits modificados ainda estejam em um comentário.Usar o extra field de um arquivo dummy extra -- até mesmo vazio -- no arquivo, após o arquivo raiz, é uma maneira elegante de armazenar blocos de colisão Hashclash: dessa forma, o arquivo Zip mantém uma estrutura padrão e pode ser facilmente manipulado depois, até mesmo com ferramentas padrão.
Extra Fields não possuem CRC32, e seu comprimento de 16 bits é declarado nos cabeçalhos anteriores. Eles têm seu próprio formato interno ID:2 Size:2 Data, mas ele geralmente é ignorado, e estão presentes tanto no Local File Header quanto no Central Directory, mas podem estar ausentes do Central Directory para manter o sufixo idêntico após os blocos de colisão.
A presença do arquivo extra que cobre os blocos de colisão em seu extra field pode precisar ser declarada na estrutura do formato, como no arquivo [Content_Types].xml em um documento OOXML. Outros arquivos XML no sufixo podem precisar ser modificados, pois alguns formatos exigiam o uso de caminhos absolutos.
Aqui está a estrutura geral do exploit genérico para um formato específico baseado em Zip:``` [Root file] (with constant CRC32)
[Dummy file] (with collision blocks in the extra field)
[...] <- rest of the archive, with 2 documents merged
Assim, ao predefinir o conteúdo do arquivo raiz e forjar CRC32s ASCII, é possível calcular uma colisão Hashclash genérica e reutilizável para um formato específico baseado em zip.
### Resumo dos requisitos
- dois ou mais prefixos
- um ou mais tipos de arquivo (poliglotas funcionam sem problemas)
- um arquivo raiz XML com nome de arquivo, tamanho de arquivo e CRC fixos: essas informações estão presentes duas vezes, antes e depois dos blocos de colisão
- os conteúdos são XML arbitrário
- o preenchimento (padding) é possível, inclusive via comentário XML, para atingir o mesmo tamanho.
- o CRC pode ser definido (via CrcHack) em cada conteúdo.
- ambos os conjuntos de arquivos coexistem no sufixo, provavelmente em diretórios diferentes. Algumas ferramentas codificam o caminho de forma fixa (hardcode), o que pode reduzir a compatibilidade.
- um arquivo XML de *tipo de conteúdo* pode precisar ser mesclado para cobrir todos os arquivos, suportados e não suportados (blocos de colisão e documento alternativo)
### Exemplos
#### CRC32
Um comentário XML mínimo (somente ASCII) com um CRC32 forjado (cálculo instantâneo) com 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-->
Outro exemplo onde você ajusta o CRC com a caixa de uma mensagem alfabética.```bash echo "" | crchack.exe -b 4:+.8*32:.8 - 0xcafebabe
#### Colisões
[zInsider](https://github.com/corkami/collisions/blob/HEAD/scripts/zinsider.py) é um script para gerar instantaneamente colisões MD5 de pares de documentos arbitrários usando estes formatos ZIP+XML:
- Office Open XML: docx / pptx / xlsx
- Open Container Format: epub
- Open Packaging Conventions:
- 3D manufacturing format: 3mf
- XML Paper Specification: xps / oxps
Para gerar seus próprios prefixos de colisão, [aqui está um script](https://github.com/corkami/collisions/blob/HEAD/scripts/makezip.py) para gerar um par de zips raiz.
Depois de calcular as colisões, use [este outro script](https://github.com/corkami/collisions/blob/HEAD/scripts/extendzip.py) para combinar esses pares de raízes com um sufixo comum.
Alguns PoCs de colisão:
- 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)).
Alguns formatos com múltiplos arquivos baseados em Zip não podem ser explorados genericamente:
- Quake PK3: um zip de arquivos sem raiz específica.
- Open Document Format: o arquivo `META-INF/manifest.xml` tem que mencionar todos os outros arquivos, então não pode ser genérico.
- APK, JAR, XPI: o arquivo `META-INF/MANIFEST.mf` também tem que mencionar todos os outros arquivos, com seus hashes.
Agradecimentos a [Philippe Lagadec](https://twitter.com/decalage2) pela ajuda com formatos de arquivos do Office!
### Outros
- Wasm, por meio de uma seção personalizada: [script](https://github.com/corkami/collisions/blob/HEAD/scripts/wasm.py), exemplos: [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)
## Estratégias incomuns
Colisões normalmente envolvem dois arquivos válidos do mesmo tipo.
### MultiColls: encadeamento de múltiplas colisões
Nada impede encadear vários blocos de colisão e ter mais de dois conteúdos com o mesmo valor de hash.
Um exemplo disso são os *hashquines* - que mostram seu próprio valor MD5.
O arquivo [PoCGTFO 14](https://github.com/angea/pocorgtfo#0x14) contém 609 colisões FastColl, fazendo isso por meio de dois tipos de arquivo no mesmo arquivo.
#### Hashquines
Hashquines são arquivos que mostram seu próprio valor de hash. Eles são abordados [aqui](https://github.com/corkami/collisions/blob/HEAD/hashquines/).
### Validade
Uma estratégia diferente seria anular o tipo de arquivo para passar pela análise como um arquivo corrompido.
Basta sobrescrever a assinatura mágica.
Anexar a ambos os arquivos (válidos ou inválidos) um formato que não precisa estar no offset 0 (arquivo compactado, como ZIP/RAR/...) revelaria outro tipo de arquivo.
Isso permite colisões poliglotas sem usar uma colisão de prefixo escolhido:
1. use o UniColl para habilitar ou desabilitar uma assinatura mágica, por exemplo um PNG:
2. anexe um arquivo ZIP
Embora tecnicamente ambos os arquivos sejam um ZIP válido, como a maioria dos parsers retorna o primeiro tipo de arquivo encontrado e eles começam a análise no offset 0, eles verão um tipo de arquivo diferente.
Exemplos:
⟷ [inválido](https://github.com/corkami/collisions/blob/HEAD/examples/png-invalid.png)
### PolyColls: colisões de tipos de arquivo diferentes
Também é possível ter os dois lados de uma colisão com tipos diferentes para reduzir a suspeita:
Cenário de ataque:
1. enviar `holiday.jpg`
2. fazê-lo entrar na lista de permissões
3. enviar `evil.exe`, que tem o mesmo MD5.
Nesses casos, uma colisão de prefixo escolhido é necessária se ambos os formatos de arquivo precisarem começar no offset 0.
Alguns exemplos de layouts de polycoll:
*Polycoll PDF/JPG*
*Polycoll PE/PNG*
#### PE - JPG
Como um cabeçalho PE geralmente é menor que 0x500 bytes, ele cabe perfeitamente em um comentário JPG:
1. comece com cabeçalhos DOS/JPG
2. o comentário JPEG pula sobre o cabeçalho PE
3. Coloque a imagem JPG completa
4. Coloque todas as especificações PE
Mais uma vez, a colisão é [instantânea](https://github.com/corkami/collisions/blob/HEAD/scripts/jpgpe.py)
Exemplos: [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
Mesclar um PDF com um arquivo fictício com `mutool` é uma boa maneira genérica de reordenar objetos e então tornar os dois primeiros objetos descartáveis (página fictícia e conteúdo), o que é perfeito para hospedar um objeto `stream` de comprimento desconhecido como `1 0`, e seu comprimento referenciado mais adiante (após os blocos de colisão) no segundo objeto.
O único problema é que o `mutool` sempre embutirá o comprimento - e removerá a referência de comprimento, então ele precisa ser reinserido no PDF em vez do valor, mas a maioria das referências `2 0 R` será menor que os comprimentos fixos.
Felizmente, isso pode ser corrigido sem alterar nenhum offset de objeto, então não há necessidade de corrigir o XREF.
Aqui está um [script](https://github.com/corkami/collisions/blob/HEAD/scripts/pdfpe.py) para, por exemplo, colidir instantaneamente um visualizador de PDF ([Sumatra](https://www.sumatrapdfreader.org/free-pdf-reader.html) é leve e autônomo) e um documento PDF:
Exemplos: [Poster.pdf](https://github.com/corkami/collisions/blob/HEAD/examples/pepdf.pdf) ⟷ [Sumatra.exe](https://github.com/corkami/collisions/blob/HEAD/examples/pepdf.exe)
*um visualizador de PDF mostrando um PDF (que por sua vez mostra um PDF) com o mesmo MD5*
#### PDF - PNG
Da mesma forma, é possível colidir, por exemplo, arquivos PDF e PNG arbitrários sem restrição em nenhum dos lados. Isso é instantâneo, reutilizável e genérico.
Exemplos: [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 (multi-colisão)
Colisões criptográficas não se limitam a dois arquivos!
Como demonstrado no experimento [Nostradamus](https://www.win.tue.nl/hashclash/Nostradamus/) em 2008, o encadeamento de colisões torna possível colidir mais de dois arquivos.
As primeiras colisões podem ser idênticas ou de prefixo escolhido; as seguintes precisam ser de prefixo escolhido.
Você pode chamá-las de multi-colisões, eu prefiro *pileups* - é mais curto :)
#### PE - PNG - MP4 - PDF
Combinando todo o conhecimento adquirido anteriormente, usei 3 colisões de prefixo escolhido para criar 4 prefixos diferentes para tipos de arquivo diferentes: documento (PDF), vídeo (MP4), executável (PE) e imagem (PNG).
*diagrama de um pileup PE/PNG/MP4/PDF*
Este script é genérico e instantâneo:
Exemplos: [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)
Como você pode distribuir apenas um único arquivo e é impossível adivinhar os outros valores de prefixo a partir dele, uma solução é embutir todos os prefixos da colisão em código JavaScript e inseri-lo em seus PoCs, transformando seus arquivos em [poliglotas HTML](https://github.com/corkami/collisions/blob/HEAD/examples/polyglot.html) para compartilhar facilmente os arquivos colididos relacionados.
A [edição 19](https://github.com/angea/pocorgtfo#0x19) de 'PoC or GTFO' é um desses pileups **e** poliglotas, combinando um documento de 80 páginas gerado com PDFLaTeX, um visualizador de PDF para Windows, um diagrama PNG e um curto vídeo MP4 de 'colisão' de [KidMoGraph](https://www.kidmograph.com/) com um payload HTML para gerar os outros arquivos a partir do lançamento em PDF (e também um arquivo ZIP):
Agradecimentos a Rafał Hirsz por sua ajuda permanente com JavaScript.
## Casos de uso
Melhor descartar o MD5 de vez, porque a inspeção de arquivos é demorada demais e arriscada demais!
### Tem que colidir todos!
Outro uso de colisões instantâneas, reutilizáveis e genéricas seria esconder qualquer arquivo de um determinado tipo - por exemplo, PNG - atrás de arquivos fictícios (ou o mesmo arquivo toda vez) - o que na verdade é apenas concatená-lo ao mesmo prefixo após remover a assinatura - você poderia até fazer isso em nível de biblioteca!
De uma perspectiva estrita de análise, todos os seus arquivos mostrarão o mesmo conteúdo, e as imagens maliciosas seriam reveladas como um arquivo com o mesmo MD5 coletado anteriormente.
Vamos pegar dois arquivos:
⟷
e vamos colidi-los com o mesmo PNG.
Agora eles mostram a mesma imagem fictícia, e são absolutamente idênticos até a 2ª imagem no nível de arquivo!
⟷
Seus payloads maliciosos estão escondidos atrás de um arquivo com o mesmo MD5, respectivamente.
### Arquivos incriminadores
Outro caso de uso para colisões é esconder algo incriminador dentro de algo inocente, mas desejável: se a única maneira de coletar evidências é comparar hashes fracos, então você não pode negar que não tem o outro arquivo (que mostra conteúdo incriminador, mas esconde conteúdo inocente).
Os softwares normalmente focam em análise (rápida), não em análise detalhada de arquivos.
*uma imagem mostrando prévias diferentes em diferentes abas do EnCase Forensic*
## Falhas
Nem todos os formatos podem ter prefixos genéricos reutilizáveis: se algum tipo de recipiente de dados não puder ser inserido entre a assinatura mágica e os cabeçalhos padrão que são críticos e específicos para cada arquivo, então colisões genéricas não são possíveis.
Claro, ainda é possível transformar os arquivos antigos em um novo, e até usar código para ramificar em dois payloads diferentes, mas isso é mais como portar payloads do que colidir a estrutura de arquivos.
### ELF
O cabeçalho ELF é obrigatório no offset 0 e contém informações críticas como 32b/64b, endianness e ABI logo no início, então é impossível ter um prefixo universal e depois blocos de colisão antes de parâmetros críticos que são específicos do arquivo original.
### Mach-O
O Mach-O nem começa com a mesma assinatura mágica para 32b (`feedface`) e 64b (`feedfacf`).
Logo em seguida, há o número e o tamanho dos comandos (como definição de segmento, symtab, versão,...).
Como no ELF, colisões reutilizáveis não são possíveis.
### Java Class
Logo no início, após a assinatura mágica, estão localizadas as versões (que podem ser problemáticas), mas a contagem do pool de constantes é bastante específica para cada arquivo, então não há colisões universais para todos os arquivos.
No entanto, muitos arquivos ainda têm uma versão comum e podemos preencher o pool de constantes mais curto até a contagem mais longa.
Primeiro, insira um *literal UTF8* para alinhar as informações, depois declare outro com seu comprimento manipulado por um UniColl (o comprimento é armazenado em 16 bytes como big endian).
No entanto, isso exigirá manipulação de código, pois todos os índices do pool serão deslocados.
Colisões MD5 instantâneas e reutilizáveis para Java Class devem ser possíveis, mas exigem análise e modificação de código.
### TAR
**TL;DR** Não há colisão reutilizável para arquivos TAR, nenhuma outra estratégia além de prefixo escolhido.
Arquivos TAR são uma sequência de cabeçalhos e conteúdos de arquivo concatenados, todos alinhados a 512 bytes.
Não há uma estrutura central para o arquivo inteiro. Portanto, não há cabeçalho global ou comentário de qualquer tipo para explorar.
Um truque seria iniciar um arquivo fictício de comprimento variável, mas o comprimento está sempre no mesmo offset, o que não é compatível com o UniColl, o que significa que apenas colisões de prefixo escolhido são úteis aqui.
## Resumo das explorações
Formato | Genérico? | FastColl | UniColl | Shattered | HashClash / Shambles
-------- | -------- | :------: | :-----: | --------- | :-------:
PDF | Sim | | x | | x
JPG | Sim (1) | | x | x (2) | x
GZ | Sim | | x | | x
PNG | Sim/Não (3) | | x | | x
MP4 | Sim (4) | | x | x (5) | x
PE | Sim | | | | x
Baseado em ZIP (6) | Sim | | | | x
| | | | |
GIF | Não | x | | | x
ZIP | Não | | x (7) | | x
| | | | |
ELF | Não | | | | x
TAR | Não | | | | x
Mach-O | Não | | | | x
Class | Não | | | | x
1. O JPG tem algumas limitações nos dados que podem ser melhoradas até certo ponto manipulando a codificação dos scans.
2. PDF com JPG é a [implementação inicial](http://shattered.io) do ataque Shattered, mas é apenas um truque puro de JPG em um documento PDF.
3. PNG: Safari/Preview exige que o PNG tenha seu chunk `IHDR` no primeiro slot, antes de qualquer bloco de colisão. Isso impede um prefixo genérico, caso em que a colisão é limitada a dimensões específicas, espaço de cores, BPP e entrelaçamento.
4. Formatos Atom/Box como MP4 podem funcionar com o mesmo prefixo para diferentes subformatos. Alguns subformatos como JPEG2000 ou HEIF exigem preparação extra, mas a estratégia de exploração é a mesma - só que a colisão não é possível entre subformatos, apenas com um par de prefixos para um subformato específico.
5. Atom/Box é compatível com Shattered ao usar comprimentos de 64 bits.
6. Alguns formatos baseados em Zip podem ser explorados genericamente.
7. Para melhor compatibilidade, o ZIP precisa de dois UniColl para um arquivo completo, e essas colisões dependem do conteúdo de ambos os arquivos.
## Arquivos de teste
[Aqui](https://github.com/corkami/collisions/blob/HEAD/examples/free/README.md) estão pares de teste de colisão gratuitos (livres de direitos autorais, sem PII).
# Detecção
Existem diferentes maneiras de detectar colisões de hash em arquivos.
1. Dois arquivos: se você tiver dois ou mais arquivos com conteúdos diferentes e o mesmo hash, basta fazer diff deles!
No entanto, se você tiver apenas um único arquivo, pode ser difícil saber se o arquivo contém uma colisão de hash.
2. Estrutura do arquivo: analise o arquivo nos limites de bloco e, se você notar blocos de alta entropia e talvez prefixo/sufixo idênticos, talvez seja possível identificar qual colisão está sendo usada, mas é muito sujeito a erros. No caso de uma colisão de prefixo escolhido, pode ser impossível detectar, pois ambos os arquivos podem ser majoritariamente diferentes, exceto pela maior parte dos blocos de colisão.
3. Cálculo de hash: use uma implementação (em [C](https://github.com/cr-marcstevens/hashclash/tree/collisiondetection/src/collisiondetection) ou [Go](https://github.com/therealmik/detectcoll)) do DetectColl de Marc Stevens (cf. seu artigo [Counter-cryptanalysis](https://marc-stevens.nl/research/papers/C13-S.pdf)). Ela requer apenas um arquivo, mas exige que a colisão esteja em um estado funcional (o prefixo exato e seus blocos de colisão correspondentes) e é lenta.
O DetectColl fornece informações técnicas sobre a própria colisão e mostra `*coll*` ao lado do hash colidido.
## Exemplo
Com o certificado do malware 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
Como o Detectcoll consegue identificar blocos usados para uma colisão de hash, ele pode mitigar a colisão por meio de hashes seguros: se um bloco de colisão for detectado, ele o reprocessa novamente para quebrar a propriedade de colisão. Assim, o DetectColl é capaz de distinguir conteúdos diferentes por meio da mesma função de hash, apesar das colisões no arquivo.
Em resumo:
Exemplo com a colisão original de Wang de 2005:``` $ md5sum wang* 79054025255fb1a26e4bc422aef54eb4 *wang1.bin 79054025255fb1a26e4bc422aef54eb4 *wang2.bin
MD5 seguro nestes arquivos:```
$ detectcoll wang1.bin | grep coll
*coll* ff531291d102a41aa131e0e09f64ca60 wang1.bin
O conteúdo de entrada está vazio — não há texto para traduzir neste chunk.``` $ detectcoll wang2.bin | grep coll coll 6a8e7124724d5c819401afc202a4fbd0 wang2.bin
## Assinaturas
Para simplificar, você pode analisar a saída do Detectcoll com este [script](https://github.com/corkami/collisions/blob/HEAD/scripts/logparse.py) e compará-la com [assinaturas conhecidas](https://github.com/corkami/collisions/blob/7f7876c431614f33f765bfc1cb62506b476a2eb0/scripts/logparse.py#L15-L24) mais facilmente:``` 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
Uma pequena desvantagem dos hashes seguros é que eles impedem a detecção de múltiplas colisões no mesmo arquivo, mas o DetectColl ainda pode detectar colisões com hashes 'padrão'.
Exemplos com PoCorGTFO 0x14 (um hashquine NES+PDF com uma imagem de capa alternativa).``` $ 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
Hashes inseguros encontra todos eles:```
$ detectcoll_unsafe pocorgtfo14.pdf | grep Found | wc -l
609
Se você verificar as últimas colisões:``` $ 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:
Você pode notar que o último não está tão próximo dos anteriores:
isso porque os anteriores pertencem ao mesmo arquivo de imagem para os hashquines,
enquanto o último é para a capa alternativa.
# Referências
Artigos (sobre exploração de formatos de arquivo):
- 2004
- [MD5 To Be Considered Harmful Someday](https://eprint.iacr.org/2004/357.pdf) - Dan Kaminsky
- [Practical Attacks on Digital Signatures Using MD5 Message Digest](https://eprint.iacr.org/2004/356.pdf) - Ondredj Mikle
- 2005:
- [A Note on Practical Value of Single Hash Collisions for Special File Formats](https://github.com/corkami/collisions/blob/HEAD/papers/Illies_NIST_05.pdf) - Max Gebhardt, Georg Illies, Werner Schindler
- 2014:
- [Malicious Hashing: Eve’s Variant of SHA-1](https://malicioussha1.github.io/) - Ange Albertini, Jean-Philippe Aumasson, Maria Eichlseder, Florian Mendel, Martin Schläffer
- 2017:
- [The first collision for full SHA-1](http://shattered.io) - Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov
- [Postscript that shows its own MD5](https://archive.org/stream/pocorgtfo14#page/n45/mode/1up) por Gregor "Greg" Kopf
- [A PDF That Shows Its Own MD5](https://archive.org/stream/pocorgtfo14#page/n49/mode/1up) por Mako
- [This GIF shows its own MD5!](https://archive.org/stream/pocorgtfo14#page/n52/mode/1up) por Kristoffer "spq" Janke
- [This PDF is an NES ROM that prints its own MD5 hash!](https://archive.org/stream/pocorgtfo14#page/n55/mode/1up) por Evan Sultanik, Evan Teran
- 2018:
- [Easy SHA-1 Colliding PDFs with PDFLaTeX.](https://archive.org/stream/pocorgtfo18#page/n62/mode/1up) por Ange Albertini
- 2020:
- [SHA-1 is a Shambles](https://eprint.iacr.org/2020/014.pdf) por Gaëtan Leurent, Thomas Peyrin
Apresentações:
- 2017 Exploiting Hash Collisions at Black Alps:
- [slides](https://speakerdeck.com/ange/exploiting-hash-collisions)
[](https://speakerdeck.com/ange/exploiting-hash-collisions)
- [vídeo](https://www.youtube.com/watch?v=Y-oJWEYKVLA)
[](https://www.youtube.com/watch?v=Y-oJWEYKVLA)
- 2019 KILL MD5 at Pass the Salt:
- [slides](https://speakerdeck.com/ange/kill-md5)
[](https://speakerdeck.com/ange/kill-md5)
- [vídeo](https://passthesalt.ubicast.tv/videos/kill-md5-demystifying-hash-collisions/)
[](https://passthesalt.ubicast.tv/videos/kill-md5-demystifying-hash-collisions/)
Workshop (CollTris):
- [slides](https://speakerdeck.com/ange/colltris)
[](https://speakerdeck.com/ange/colltris)
- [vídeo](https://www.youtube.com/watch?v=BcwrMnGVyBI)
[](https://www.youtube.com/watch?v=BcwrMnGVyBI)
- [materiais](https://github.com/corkami/collisions/blob/HEAD/workshop/README.md)
- sessões
- 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
Tarefas de CTF:
- [Prudentialv2](https://ctftime.org/task/3453), do *Boston Key Party CTF 2017*.
- [HREFIN](https://ctftime.org/task/6965), do *Google CTF 2018*.
- [Looking glass](https://ctftime.org/task/9271) do *Dragon Sector Teaser CTF 2019*.
<!-- - [Not my digest](https://ctftime.org/task/4784) from *Hack.lu CTF 2017*: not related to collisions, but solved by Marc himself :p -->
Um desafio comum para tais tarefas de CTF é não dar uma vantagem ou desvantagem muito grande com base na quantidade de poder computacional a que cada jogador tem acesso.
# Créditos
Tudo isso foi possível graças a [Marc Stevens](https://marc-stevens.nl/research/),
não apenas por suas contribuições criptográficas, mas também por sua ajuda e sugestões constantes!
Agradecimentos também a Philippe Teuwen por seus extensos comentários sobre formatos de arquivo em geral.
# Conclusão
**Matem o MD5!**
A menos que você verifique ativamente se há malformações ou blocos de colisão nos arquivos, não use MD5!
Não é um hash criptográfico, é uma função de brinquedo!
<!-- pandoc -s -f gfm -t html README.md -o README.html -->
| Prefixo | = | Prefixo |
|---|
| Colisão A | ≠ | Colisão B |
| A | = | |
| = | B |