Mam duzy zestaw plikow.
Jak ksztaltuje sie prawdopodobienstwo wystapienia kolizji md5-ek tych
plikow w funkcji ich ilosci?

Podchodząc do sprawy liniowo wiem ze skoro md5 jest 128 bitowe to
2^128 plikow+1 wygeneruje kolizje.
Ale nie wiem jak md5 sie zachowuje dla plikow ktore sa do siebie
troche podobne (np formularze wypelnione podobnymi danymi).

Czy ktos sie o temat otarl? Potrzebuje oszacowac spod grubego palca
przy jakiej ilosci plikow prawdopodobienstwo powtorzenia md5-ki dla
roznych plikow bedzie na poziomie powiedzmy 50%.

--
Lukasz Sczygiel

do góry

Użytkownik "ptoki" <s...@g...com> napisał w wiadomości
news:83e2f2c7-23ae-43e6-be44-8269bc46acdc@d8g2000yqf
.googlegroups.com...
> Ale nie wiem jak md5 sie zachowuje dla plikow ktore sa do siebie
> troche podobne (np formularze wypelnione podobnymi danymi).

Wystarczy że rożnią się tylko jednym bajtem a md5 będzie zupełnie
niepodobne.

do góry

prorok wrote:

> Użytkownik "ptoki" <s...@g...com> napisał w wiadomości
> news:83e2f2c7-23ae-43e6-be44-8269bc46acdc@d8g2000yqf
.googlegroups.com...
>> Ale nie wiem jak md5 sie zachowuje dla plikow ktore sa do siebie
>> troche podobne (np formularze wypelnione podobnymi danymi).
>
> Wystarczy że rożnią się tylko jednym bajtem a md5 będzie zupełnie
> niepodobne.

Ale i odwrotnie, jesli roznia sie znacznie to md5 moze byc taki sam.

Jeśli chodzi o zabezpieczenie najprościej dać dwie sumy + długość.
lub samą długość danych. md5+sha1 powinno być trudno kolizyjne.

do góry

Użytkownik "Bronek (bryx) Tatukl" <b...@k...com> napisał w wiadomości
news:4c6e2dba$0$20997$65785112@news.neostrada.pl...
> Ale i odwrotnie, jesli roznia sie znacznie to md5 moze byc taki sam.

Jeżeli plików byłoby rzędu 2^128

> Jeśli chodzi o zabezpieczenie najprościej dać dwie sumy + długość.
> lub samą długość danych. md5+sha1 powinno być trudno kolizyjne.

wystarczyłoby sha1

do góry

prorok wrote:

> Użytkownik "Bronek (bryx) Tatukl" <b...@k...com> napisał w wiadomości
> news:4c6e2dba$0$20997$65785112@news.neostrada.pl...
>> Ale i odwrotnie, jesli roznia sie znacznie to md5 moze byc taki sam.
>
> Jeżeli plików byłoby rzędu 2^128
>
>> Jeśli chodzi o zabezpieczenie najprościej dać dwie sumy + długość.
>> lub samą długość danych. md5+sha1 powinno być trudno kolizyjne.
>
> wystarczyłoby sha1

Dlugość jest zazwyczaj mniejsza niż sha1. Co więcej długość zabezpiecza
przed znanymi algorytmami kolizji md5. md5 nie zostało złamane a jedynie
można znaleźc kolizje dla dłuższych plików. Długość ma znaczenie ;)

do góry

On Aug 20, 8:15 am, ptoki <s...@g...com> wrote:

> Czy ktos sie o temat otarl? Potrzebuje oszacowac spod grubego palca
> przy jakiej ilosci plikow prawdopodobienstwo powtorzenia md5-ki dla
> roznych plikow bedzie na poziomie powiedzmy 50%.

Około 2^64 (bardzo z grubsza).

do góry

On 2010-08-20, ptoki <s...@g...com> wrote:
> Mam duzy zestaw plikow.
> Jak ksztaltuje sie prawdopodobienstwo wystapienia kolizji md5-ek tych
> plikow w funkcji ich ilosci?
>
> Podchodząc do sprawy liniowo wiem ze skoro md5 jest 128 bitowe to
> 2^128 plikow+1 wygeneruje kolizje.
> Ale nie wiem jak md5 sie zachowuje dla plikow ktore sa do siebie
> troche podobne (np formularze wypelnione podobnymi danymi).
>
> Czy ktos sie o temat otarl? Potrzebuje oszacowac spod grubego palca
> przy jakiej ilosci plikow prawdopodobienstwo powtorzenia md5-ki dla
> roznych plikow bedzie na poziomie powiedzmy 50%.

nie za bardzo chce mi się liczyć dla 50%, ale 40% prawdopodobieństwo
jest przy 2^64 plików.

depesz

--
Linkedin: http://www.linkedin.com/in/depesz / blog: http://www.depesz.com/
jid/gtalk: d...@d...com / aim:depeszhdl / skype:depesz_hdl / gg:6749007

do góry

On 20.08.2010 14:35, hubert depesz lubaczewski wrote:
> On 2010-08-20, ptoki <s...@g...com> wrote:
>> Mam duzy zestaw plikow.
>> Jak ksztaltuje sie prawdopodobienstwo wystapienia kolizji md5-ek tych
>> plikow w funkcji ich ilosci?
>>
>> Podchodząc do sprawy liniowo wiem ze skoro md5 jest 128 bitowe to
>> 2^128 plikow+1 wygeneruje kolizje.
>> Ale nie wiem jak md5 sie zachowuje dla plikow ktore sa do siebie
>> troche podobne (np formularze wypelnione podobnymi danymi).
>>
>> Czy ktos sie o temat otarl? Potrzebuje oszacowac spod grubego palca
>> przy jakiej ilosci plikow prawdopodobienstwo powtorzenia md5-ki dla
>> roznych plikow bedzie na poziomie powiedzmy 50%.
>
> nie za bardzo chce mi się liczyć dla 50%, ale 40% prawdopodobieństwo
> jest przy 2^64 plików.

Z tym, że trzeba mieć niezłe zasoby, żeby przechować 2^40 plików.

--
wer <",,)~~
http://szumofob.eu

do góry

Użytkownik "hubert depesz lubaczewski" <d...@d...com> napisał w
wiadomości news:7e92k7-ffc.ln1@depesz.com...
> nie za bardzo chce mi się liczyć dla 50%, ale 40% prawdopodobieństwo
> jest przy 2^64 plików.

Skąd taka mała ilość? Przypuszczałbym że skoro dla dwóch plików jest rzędu
1/2^128 to prawdopodobieństwo 50% byłoby jeśli nie dla ilości 2^128, to
przynajmniej 2^127, skąd nagle wychodzi spierwiastkowana liczba?

do góry

Użytkownik "prorok" <p...@t...nie.adres> napisał w wiadomości
news:i4m46q$s42$1@news.onet.pl...
> Skąd taka mała ilość? Przypuszczałbym że skoro dla dwóch plików jest
> rzędu 1/2^128 to prawdopodobieństwo 50% byłoby jeśli nie dla ilości
> 2^128, to przynajmniej 2^127, skąd nagle wychodzi spierwiastkowana
> liczba?

Chyba że chodzi o to że przy ilości 2^64 ilość możliwych par każdy z każdym
będzie rzędu 2^127

do góry