Vtipná historka: https://bugs.webkit.org/show_bug.cgi?id=168774#c27
no první co mě napadlo ty soubory strčit cvičně do GITu, ale zblbnout se mi ho nepodařilo. Dokonce ani v případě, že jsem prohodil obsahu mezi názvy souborů. Kromě obsahu souboru se do té hashe dává něco dalšího - nějaká metadata.
Například teď jsem zkusil znovu stahnout obě pdf, udělat na obě touch, aby měly oba shodný modify time a strčit do git napřed shattered-1.pdf, pak přejmenovat shattered-2.pdf na shattered-1.pdf a zas commitnout, ale kupodivu mají pořád různý hash :)
zito@bobek:/tmp$ mkdir pokus
zito@bobek:/tmp$ cd pokus
zito@bobek:/tmp/pokus$ git init
Initialized empty Git repository in /tmp/pokus/.git/
zito@bobek:/tmp/pokus$ wget https://shattered.it/static/shattered-{1,2}.pdf
--2017-02-27 12:20:05-- https://shattered.it/static/shattered-1.pdf
Resolving shattered.it (shattered.it)... 216.239.38.21, 216.239.36.21, 216.239.34.21, ...
Connecting to shattered.it (shattered.it)216.239.38.21:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 422435 (413K) [application/pdf]
Saving to: ‘shattered-1.pdf’
shattered-1.pdf 100%[==========================================================>] 412.53K 973KB/s in 0.4s
2017-02-27 12:20:06 (973 KB/s) - ‘shattered-1.pdf’ saved [422435/422435]
--2017-02-27 12:20:06-- https://shattered.it/static/shattered-2.pdf
Reusing existing connection to shattered.it:443.
HTTP request sent, awaiting response... 200 OK
Length: 422435 (413K) [application/pdf]
Saving to: ‘shattered-2.pdf’
shattered-2.pdf 100%[==========================================================>] 412.53K 2.22MB/s in 0.2s
2017-02-27 12:20:07 (2.22 MB/s) - ‘shattered-2.pdf’ saved [422435/422435]
FINISHED --2017-02-27 12:20:07--
Total wall clock time: 1.2s
Downloaded: 2 files, 825K in 0.6s (1.33 MB/s)
zito@bobek:/tmp/pokus$ touch *
zito@bobek:/tmp/pokus$ ll
total 832
-rw-r--r-- 1 zito zito 422435 Feb 27 12:20 shattered-1.pdf
-rw-r--r-- 1 zito zito 422435 Feb 27 12:20 shattered-2.pdf
zito@bobek:/tmp/pokus$ sha1sum *pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a shattered-2.pdf
zito@bobek:/tmp/pokus$ git add sh
shattered-1.pdf shattered-2.pdf
zito@bobek:/tmp/pokus$ git add shattered-1.pdf
zito@bobek:/tmp/pokus$ git commit -m 1
[master (root-commit) 11f8842] 1
1 file changed, 0 insertions(+), 0 deletions(-)
create mode 100644 shattered-1.pdf
zito@bobek:/tmp/pokus$ mv sh
shattered-1.pdf shattered-2.pdf
zito@bobek:/tmp/pokus$ mv shattered-2.pdf sh
shattered-1.pdf shattered-2.pdf
zito@bobek:/tmp/pokus$ mv shattered-2.pdf shattered-1.pdf
zito@bobek:/tmp/pokus$ git add shattered-1.pdf
zito@bobek:/tmp/pokus$ git commit -m 2
[master 0b0c0ad] 2
1 file changed, 0 insertions(+), 0 deletions(-)
zito@bobek:/tmp/pokus$ git log --oneline
0b0c0ad 2
11f8842 1
zito@bobek:/tmp/pokus$ cp shattered-1.pdf 1/shattered.pdf^C
zito@bobek:/tmp/pokus$ git ls-tree -l 0b0c0ad
100644 blob b621eeccd5c7edac9b7dcba35a8d5afd075e24f2 422435 shattered-1.pdf
zito@bobek:/tmp/pokus$ git ls-tree -l 11f8842
100644 blob ba9aaa145ccd24ef760cf31c74d8f7ca1a2e47b0 422435 shattered-1.pdf
Je to tak. Kouknul jsem na začátek toho jednoho objektu:
zito@bobek:/tmp/pokus$ printf "\x1f\x8b\x08\x00\x00\x00\x00\x00" cat - ./.git/objects/ba/9aaa145ccd24ef760cf31c74d8f7ca1a2e47b0 zcat head -c 32 xxd
00000000: 626c 6f62 2034 3232 3433 3500 2550 4446 blob 422435.%PDF
00000010: 2d31 2e33 0a25 e2e3 cfd3 0a0a 0a31 2030 -1.3.%.......1 0
Tak ano, je tam blob a velikost ukončené \0.
Nejsem žádný cryptoanalytik, ale nestěžuje to trochu tu úlohu, když součástí toho prefixu je délka výsledného souboru? Je to zřejmě další podmínka, kterou je nutné splnit, ale je otázka jestli tohle už umí - tedy dogenerovat za prefix takové smetí, aby klapla současně velikost souboru.
> Nejsem žádný cryptoanalytik, ale nestěžuje to trochu tu úlohu, když součástí toho prefixu je délka výsledného souboru?
Ne. SHA-1 je MD komprese bez velikosti/paddingu na začátku. Si to zkus s těmi zveřejněnými soubory - na jejich konec můžeš přidal libovolný (stejný) obsah a pořád jsou kolizní.
/tmp> head -c 1024 /dev/urandom >f
/tmp> cat shattered-1.pdf f sha1sum
05d1bd3012e77f504a0b14bb40e92acf913a4ef2 -
/tmp> cat shattered-2.pdf f sha1sum
05d1bd3012e77f504a0b14bb40e92acf913a4ef2 -
Tak to je vlastně nakonec logické, že přidáním shodného obsahuje jsou dva soubory pořád kolizní.
Mě šlo čistě o GIT, kde na začátku je velikost daná a já mám objekt dané velikosti a k němu potřebuju druhý kolizní objekt, který ma tím pádem velikost danou.
Je pravda že zpočátku stačí najít prostě pro srandu nějaký prefix, kde bude na začátku třeba
"blob 1000000\0cokoliv..."
"blob 1000000\0cokoliv s kolizi..."
soubory doplnit paddingem tu velikost 1000000. Do GITu pak commitnout objekty bez toho začátku "blob 100000000\0" a GIT nebude schopen přidat oba...
Tak to je vlastně nakonec logické, že přidáním shodného obsahuje jsou dva soubory pořád kolizní.
Zas tak logické to není, resp. je to právě ta slabina SHA-1, která teď byla zneužita. Ideální hashovací funkce by každý bit vstupu měla promítnout do náhodných bitů výstupu. I kdybyste hrubou silou získal dva různé vstupy, které dávají pro tu ideální hashovací funkci stejný hash, přidání jediného shodného bitu by muselo vygenerovat dva úplně odlišné hashe.
Konec konců si ty soubory můžeš diffnout a zjistit, že se liší jen ve dvou blocích skoro na začátku. Takže si ty jejich JPEGy klidně můžeš nahradit svými a vytvořit si tak kolizní dokumenty s vlastním obsahem. Už to někdo dal online - https://alf.nu/SHA1 (nezkoušel jsem to).