Jaros?aw Soko?owski <j...@l...waw.pl> wrote:
> Luke napisa?:
>
> > Wracaj?c do tematu z ga??zi o publikacjach naukowych, trzeba by chyba
> > jeszcze zwr?ci? uwag?, ?e si?a funkcji hashuj?cych maleje z czasem.
> >
> > To znaczy je?li podpisz? kwalifikowanym podpisem ze znacznikiem czasu
> > dokument poprzez podpisanie jego SHA1, mo?e si? okaza?, ?e za jakie?
> > 5-10 lat powstanie metoda generowania kolizji tego SHA1.
> >
> > I nagle b?dzie istnia?o 20 wersji wynalazku z tak? sam? sum? SHA1.
> >
> > I nikt nie udowodni, kt?ra istnia?a w momencie z?o?enia podpisu :)
>
> To jest w?a?nie *nieprawd?*, na kt?rej zasadza si? ca?e nieporozuminie.
>
> Da si? wygenerowa? kolizj? (dzisiaj dla MD5, za 5-10 lat mo?e dla SHA1),
> ale nie ma si? przy tym pe?ni swobody tw?rczej. W praktyce wygl?da to
> tak, ?e zamiast programu o znanym hashu mo?na komu? brzydko pod?o?y?
> inny, kt?ry robi zgo?a co innego, mo?e bardzo brzydkiego. Mog? stworzy?
> kr?tki plik tekstowy o tre?ci dajmy na to "Ala ma kota" i wygenerowa?
> jego skr?t MD5 (czy SHA). Tu te? kto? mo?e dopasowa? do mojego hasha
> sw?j plik.

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).

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.

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.


--
Waldek Hebisch