Pan Waldek Hebisch napisał:

> Nie. Chyba nikt nie zrozumial tego co napisalem. Kolizja
> to _dwa_ pliki z takim samym MD5. Nie masz wyboru jaki MD5
> dostaniesz. Zeby bylo jasniej przyjmijmy na chwile ze MD5
> dziala tak jak mieli nadzieje projektanci, tzn. ze najlepsza
> metoda jest losowy wybor. Wtedy trzeba by rzedu 2^64 haszy
> do znalezienia kolizji (jest to znany paradoks dnia urodzin).
> Do znalezienia zadanego hasza trzeba by 2^128 prob (czyli
> w zasadzie pelny przeglad). "Zalamanie" MD5 polaga na tym
> ze kolizje daje sie wyprodukowac duzo szybciej niz przy
> pomocy 2^64 prob. Podobny sposob pozwala troche szybciej
> znalesc duplikat zadanego hasha, ale to ciagle zupelnie
> niepraktyczne wartosci (cos rzedu 2^96 prob).

To "nikt nie zrozumiał" jest nieco krzywdzące. Ale nie gniewam
się. Na zgodę przyjmijmy, że zamiast komputera "informatycznego"
dysponujemy komputerem "matematycznym". Takim, co nie trochę
szybciej, nie dużo szybciej, a wszystkie problemy obliczalne
rozwiązuje w okamgnieniu. Jak się okazuje, niewiele to zmienia.

> Oczywiscie twoj argument tez sie liczy: jak wyprodukujesz
> kolizje to sa zupelnie bezsensowne ciagi bitow. Daje sie
> je opakowac w postscript (i chyba pdf) tak ze na ekranie
> to wyglada sensownie, tzn. mamy dwa sensownie wygladajace
> dokumenty z takim samym podpisem. Ale zagladniecie do
> srodka pokazuje ze jest to potencjalne oszustwo: w srodku
> jest troche binarnej sieczki i _oba_ teksty.

Z tym "opakowaniem" i "wyglądaniem na ekranie" to już brudna
sztuczka. Swoją trywialnością nijak nie przystająca do mocnych
metod matematycznych o których my tu. Pewnie z połowa ludzi
tutaj piszących jest w stanie z prędkościa karabinu maszynowego
generować wsady do atmelka, które mimo że każdy inny, będą tak
samo generowac napis "Hello world! na porcie RS-232. Takich, co
podobną sztuczkę zrobią z plikiem PDF, może też się paru znajdzie.
Żeby to zdemaskować nie potrzeba jasnowidza, nawet biegły nie
musi być do tego bardzo biegły ani przebiegły.

> Jak pisalem, nie jest znana praktyczna metoda wyprodukowania
> pliku z zadanym haszem. Gdyby byla znana to nie wiadomo
> na co by pozwalala. Majac komputer robiacy 2^128 instrukcji
> na sekunde w sensownym czasie dalo by sie znalezc
> naturalnie wygladajacy plik zawierajacy zadany tekst
> i majacy zadany hash (stosujac np. podprogowe kodowanie
> w szumie obrazka). Ale praktyczna metoda raczej bedzie
> bazowala na jakies (dzis hipotetycznej) dodatkowej
> slabosci MD5. Nie wiadomo czy jakas bedzie znaleziona
> i na co ona moze pozwolic.

Załóżmy na chwilę, że jest znana. Gros zastosowań skrótów MD5
to potwierdzenie autentyczności plików. Dane hulają sobie
gdzieś po torrentach, a na zaufanym serwerze jest suma MD5.
Jedno i drugie jest publicznie dostępne, każdy kto wszedł
w posidanie pliku może sprawdzić po sumie MD5, czy to jest
to, co powinno być. Opisy słabych punktów opierają się na
pokazaniu, że da się (choćby potencjalnie) zmodyfikować *znany*
plik i podłożyć tam coś innego. Wokół takich scenariuszy krążą
wszyscy PT Dyskutanci.

Tymczasem wykorzystanie hasha metodą "na notariusza" to całkiem
co innego. Publiczny jest *tylko* skrót. Jest moją słodką
tajemnicą, czy przehashowałem krótką inskrypcję "A kuku!",
czy zebrane dzieła Lenina zeskanowane do plików BMP w full
kolor z plamami krwi na egzemplarzu z autografem Dzierżyńskiego.
Suma MD5 zawsze przecież wygląda tak samo. A ja sam plik ujawnię
dopiero We Właściwym Momencie. Do tego momentu hakierstwo całego
świata może sobie dopasowywać co tam chce i zgadywać co miałem
na myśli.

Jarek

--
Każdy mógł więc przyjść do suma
I zapytać: jaka suma?
A sum jeden w całej Wiśle
Odpowiadał na to ściśle.