Vlákno názorů k článku SHA-1 není bezpečná, Google ukázal kolizi od K> - "Na stovce grafických procesorů tak dokážete vytvořit kolizní...
-
K> (neregistrovaný)
"Na stovce grafických procesorů tak dokážete vytvořit kolizní dokumenty během jednoho roku"
Tedy chapu to dobre ze jeden rok je prumerna doba hledani kolize? A vi nekdo jak priblizne vypada pravdepodobnstni rozdelovaci funkce te doby (histogram)? Je to rovnomerne nebo normalni, rozptyl? -
K> (neregistrovaný)
ja mel spis na mysli dobu hledani kolize pro dany konkretni dokument (a ne dobu hledani jakekoliv kolize).
proste chci provest utok (podvrhnout dokument), podle clanku mam pocitat s jednim rokem hledani kolize. je ta doba jednoho roku prumer? jaka ma ta doba rozdeleni (neboli jakou mam sanci ze kolizi najdu uz po jednom mesici)? -
mxlbzn (neregistrovaný)
tady je druhá ;)
$ sha256sum helloworld*.pdf
2933526acbb85042d5b1df3c4d6aee9671a048562a0f0a4907d66b1134512311 helloworld1.pdf
51bdd1bf1a1418728f71586ad1411ea8eda56790e2f7f4b3f820c36a917fa72d helloworld2.pdf
$ sha1sum helloworld*.pdf
a0cad1957a3369ed5d624bacd291837924da1a58 helloworld1.pdf
a0cad1957a3369ed5d624bacd291837924da1a58 helloworld2.pdf
respektive n-tá.. on už to není problém vyrobit, akorát ty vzniklé soubory jsou v podstatě k ničemu. -
Ondřej CaletkaZlatý podporovatelTady je generátor, co umí vytvořit smysluplné kolizní PDF:
Právě jsem jím vytvořil dvě směnky, jednu na 1 Kč, druhou na 1 MKč :D
$ sha1sum smenka*.pdf d423ec3ec39781f9b81a27c94ed88327bf544996 smenka1.pdf d423ec3ec39781f9b81a27c94ed88327bf544996 smenka2.pdf
-
mxlbzn (neregistrovaný)
tak tady jsou (trochu jiné, optimalizoval jsem velikost o pár řádů)
/Td6WFoAAATm1rRGAgAhARYAAAB0L+Wj4Cf/BJhdADQZSe6OHIvlLjRrQut+GFRfRrV6BtQUxwHH wq/efF2SoDVGopo35pev/MFFDCa769tBMG/xbcfAgJtj4PBl4AgBF2MPCmoRwifT00sXvyZL1YeZ l9CNdyjpJzd7hrzSVr/xhP8lk801Qo5iWmn347V+wJn2UDfx8oV25FbE/eFHODvdAZfS2Tx7PCaV QaM5AirKpY32ZZ2VzhliaMt8atUANHc+4Xk8f0MfuUxoPr2sTZEe4KUwlr4BCn0SxaPUfnTDIR16 MJSWewHVSEftCFyMwDd6PSkP3pBmEiKINlkRKQ1Icylm4eelGCE9BkCKlizM8LbNjTgRw5sdrLFz VqsTCQYav7UOXROo235FPkpaN4I8KyMgUOX4zS52Sm/UpfOmwPTKhi8ZJd8dL8tW3RdknPXoZuy8 5wdcS1kAGT1+SUzSbzl5v3Ffu79RFZK0AQCLcXaKqLAH7RtQmbG9fgvU8oU0ToobhZNzkEiv5t2J 30FPHAXzhkNyIKtIpOMdFX4geJaOlxYHQyvDkygrzeckAaBmUThXO/cb2UOnQpMdBf39/I2rJN/m Mzo4SPpX4ta1Rv1uqgqyApF8V9Oz/w8Q/6JT6LrFdqMoxjwCxCdo6aoQauRTwnTKDiP0iNXHGQie VyGqILEM5j/DeA5KtyAf+k0nGR9Lgqm1LTIoViZuCBmJBnnfTmLeoj0fw+TrFlkUU1spVZfbK3O9 o36YFTx9/+3I/MR0gQa7UEfoedGzYFsv3vLbhJx5a4D+4ZAan5HORXJXQO1Vhxiv/s5Q32vrGue9 mDrVCTF61q/lo+gwC6f2dlNj8HYUPJQZGk6/zqUdWTosPtPUhdIpNYu+5nDq28OKDPfBi45bEBoZ Bj/6+2+kqZ4icma8sadfkmUIM/pIQF6P81ZMhgUxj6PIb/5GT97kwwcSLGAiAQUCX7Ys83JXHtiZ FOAQgG50bJ218wYtPFmO50wCMJ+FuqxCw7c2XspzFuS3Iw2+HDCpf6nCxCBKgVoVrTJvE/fHdrer oR3IZ2sQDc5dIPRuhtI6Nora4aRqfK0Ac2d1/KFu3P7ze3GI1XaiV/W8OlEOkgoMePDPF3929EZn cQfFkwjujSY0pJW7J841S/E/+hjmj6EmOtXgivxXPXvVbhGFQ6No6fWff1sNf1TzECwgQIbD424G Ix3kZ7/dln/qkS1LFB21MdOw6xFMpm7C1eeQAMfFB/B8p0s2w3JEhp65awGd83JL+hdgIs/rZG6v fG9Pg2WERlk2Jfsq+MJqNXeRyYHa5b6IyzwGlc0xPk0c0uEJgBICmpzHVuty/P36wonv45AMhkWL GSB5wYzhLOd2G9H4TS/PUWsA12dvQndts67t123dflTqOMjoCaSlHrJJ+BRpPiYqCV3Ds44GM/jJ 2M2HlfLa7wxmhNaj5VdEO6TGicUHyAd5zDQ0e/f5JDrxxvExFzhHUDLeQnteL7zPNqlHBHo/Suyk HtevTfbmsJotGWXiGdCygP8QpznmRwnvmxN5PEAWZhXU+y5AI35N2YGPsl0MUz09yhsGt152ck4g JgYzf41VLG5eAABvrK3+GMlOGwABtAmAUAAARH/7zrHEZ/sCAAAAAARZWg==
-
Vlastně ne tak docela – naivní přístup by díky narozeninovém paradoxu po nějakém čase kolizi jistě našel. To už není exponenciální rozložení. Pokud bychom ale vybírali vstup pro další pokus náhodně, k exponenciálnímu rozložení bychom se přinejmenším přiblížili. Ale každý další prvek by měl o něco větší šanci kolidovat s něčím jiným již známým.
Intuitivně ale exponenciální rozložení dá optimističtější odhad ohledně brzkého nalezení (tj. před očekávanou dobou hledání), takže by zde mohlo z pohledu potenciální oběti posloužit jako pesimistický odhad.
A co platí pro tento útok, to je otázka. Přijde mi zajímavé, že jsem zatím neviděl nic o prostorové složitosti, která by byla při uložení 9e38 preimages značná.
Kolizní část těch souborů má dva bloky, a už po prvním bloku se stav přiblížil. Kdyby tyto dvě fáze probíhaly odděleně, stále je potřeba prostor pro aspoň 4.5e38 preimages. To je sice čtvrtina (preimage zde má pouze 64B namísto 128B), ale pořád mi to přijde dost na to, aby to stálo za zmínku.
