md5 - bezpieczny czy nie?

Swojego czasu dużo czytałem o tym algorytmie i wszędzie było wprost napisane, że zakodowane nim dane "są nie do złamania" i jedyną metodą by odkodować znak, jest skorzystanie ze stron gdzie znajduje się baza z zakodowanymi tym algorytmem stringami. Porównuje się tam zakodowane hasła czy inne dane i jeśli identyczne znajduje się w bazie, to pojawi się rozkodowana postać, jeśli natomiast w bazie nie ma identycznego wpisu, to złamanie kodowania jest niemal niemożliwe.
Był też wpis, że sami twórcy algorytmu nie stworzyli metody odkodowywania danych.

I tutaj pojawia się moje pytanie, ponieważ od jakiegoś czasu pojawia się coraz więcej informacji z których wynika, że np. złamanie 7 znakowego hasła, składającego się z samych cyfr, trwa około 20s, a 15 znakowego (cyfry,litery,znaki specjalne) około 36h.
Czyli jak to w końcu jest? Można złamać md5 posiadając odpowiednie umiejętności, czy to jest kwestia przypadku?

Można jak wszystko inne.
Po prostu metoda jest taka:
próbujemy wszystkie możliwe kombinacje hasła
Im lepszy komputer, hasło składające się z mniejszej ilości znaków tym znajdziemy je szybciej.

Lamiesz w stylu brute-force. Chodzi glownie o wygenerowanie kolizji md5(tekst) == hash, wiec im haslo mniej skomplikowane tym latwiej o taka kolizje. Oczywiscie sa sposoby przyspieszajace ten caly proces(teczowe tablice), ale w przypadku mocnych hasel do wygenerowania kolizji potrzeba duzej mocy obliczeniowej i duzo czasu.

Przede wszystkim MD5 nie jest funkcją szyfrującą tylko tworzącą skrót. Z dowolnych danych dowolnej długości możemy utworzyć stałej długości klucz. Dzięki temu, z jednej strony nie jest możliwe otrzymanie oryginalnych danych, a z drugiej, zawsze trzeba pamiętać o tym, że ten sam skrót będzie tworzyć wiele danych. I właśnie na tym polega metoda "łamania" MD5. Jeżeli znajdziemy taki sam (bądź inny) tekst, który ma identyczny skrót - dostaniemy dostęp do chronionych danych.

Szukanie kolizji przy funkcjach hashujących to w gruncie rzeczy brute force (czy od podstaw, czy to korzystając z tablic tęczowych), jest konieczność sprawdzenia wszystkich możliwości dopóki nie trafimy na właściwą. Są metody, które utrudniają to zadanie, np. dodanie soli (salt) do hasła czy użycie funkcji hashującej, która jest zaprojektowana w taki sposób, by na dzisiejszych procesorach wykonywała się po prostu wolno albo takiej, która tworzy dłuższy skrót (SHA).

36 godzin do złamania 15-znakowego hasła? Na jakim sprzęcie?

Kiedyś (kilka miesięcy temu) bez problemów sprawdzano pół miliarda hashy MD5 na sekundę na dwóch Radeonach HD4870 w SLI (via CUDA, znaczy ten odpowiednik od AMD). W takim tempie już hasła 9 znakowe są dość bezpieczne (kilka miesięcy pracy, także dlatego, że nie ma ogólnodostępnych "rainbow tables" dla haseł powyżej 8 znaków). Sprzęt tak bardzo poszedł do przodu, czy też ktoś wziął sklastrowaną Teslę od NVIDII zaprzągł do łamania MD5?

Z mojej strony przechodzę w nowych systemach na SHA-256 (z solą oczywiście) oraz - od strony użytkownika - na hasła powyżej 8 znaków.

@Ktos nie wiem na jakim sprzęcie. Napisała to osoba z jednego forum, gdzie jej osoba jest szanowana i na pewno nie jest to laik w tematach zabezpieczeń bo z tego co się dowiedziałem, na tym polega jego zawód. Sam się nie orientuję za bardzo, dlatego zapytałem, bo wydawało mi się, że jest to zbyt krótki czas.
Ale dzięki waszym odpowiedziom potwierdziło się tylko moje przypuszczenie. Co prawda ja nie użyłem fachowej definicji, ale w ostatecznym rozrachunku chodzi o to samo.
Dziękuję za odpowiedzi.

Pozdrawiam

Jak mi dobrze świta, to md5 zaczęło być uznawane za niebezpieczne kiedy pojawił sie artykuł o wykorzystaniu paradoksu urodzin do jego łamania. Statystyka, metoda opierająca się na prawdopodobieństwie pozwalająca znacznie skrócić czas poszukiwania kolizji.

swoją drogą, zawsze chciałem zobaczyć przykład dwóch danych tekstowych generujący taki sam hash md5

@dzek69:
http://eprint.iacr.org/2004/199.pdf
http://stackoverflow.com/questions/1224113/examples-of-hash-collisions

Nie są to dokładnie dane tekstowe, ale dane liczbowe już pokazujące kolizje w MD5.

// Właśnie nade mną przeleciał F-16 sądząc po odgłosach. CBŚ mnie namierza, bom haker?

[dopisane]
Zwłaszcza ze stackoverflow pierwszy link: http://www.mscs.dal.ca/~selinger/md5collision/ jest fajny - program, który robi co innego niż drugi, a mają taką samą sumę kontrolną...

Sprzęt tak bardzo poszedł do przodu, czy też ktoś wziął sklastrowaną Teslę od NVIDII zaprzągł do łamania MD5?
Do takich zastosowań częściej chyba klastrują Playstation 3 :-)
Największy zysk czasu się bierze chyba z tego, że algorytmy idą do przodu dzięki czemu nie trzeba sprawdzać WSZYSTKICH możliwych kombinacji.
Na tym właśnie polega łamanie: jeden wymyśli algorytm łamiący, zmniejszający złożoność obliczeniową tysiąc razy, drugi zbuduje klaster tysiąca komputerów i już z niewyobrażalnego teoretycznego miliona lat obliczeń robi nam się rok.

http://www.golubev.com/blog/?p=35

Radki są dużo lepsze w łamaniu haszy niż nVidiowe potworki.

Do takich zastosowań częściej chyba klastrują Playstation 3 :-)

Te kolizje w pierwszym linku jaki dawałem w poście wyżej były robione na klastrach PS3. Ale teraz jest gorzej - jak ktoś nie ma zapasów starych konsol to ma problem, na nowych już nie można Linuksa zainstalować i takich cudów robić :-)

Ale jak wynika z linka @donkey to chyba taniej będzie kupić kompa z Radeonem niż klastrować PS3 ;-)

Ktos [z pracy], tak, tą stronkę widziałem i te programiki, dlatego zwróciłem uwagę na to, żeby to były dane tekstowe :)

Cracking 14 Character Complex Passwords in 5 Seconds
http://www.ciozone.com/index.php/Security/Cracking-14-Character-Complex-Passwords-in-5-Seconds.html

Ja jak tworzyłem taką ministronkę, która nigdy już w starym frameworku nie wejdzie do produkcji to używałem mieszakni sha512(sha1(md5(hasło))). Teraz pewnie sięgnę po (b)crypt.

winerfresh napisał(a)

Ja jak tworzyłem taką ministronkę, która nigdy już w starym frameworku nie wejdzie do produkcji to używałem mieszakni sha512(sha1(md5(hasło))). Teraz pewnie sięgnę po (b)crypt.

Ok, prawdopodobnie pierwotnego hasła nikt nie pozna. Zwykle jednak chodzi Ci o to żeby wynik powyższego porównać do zapamiętanego hasha, stąd 'siła' tej mieszanki zależy tylko od tego jak trudno wywołać kolizję dla sha512, to co w środku nie ma znaczenia.

Dodatkowo, funkcje mieszające to na tyle zaawansowana matematyka, że łącząc je w ten sposób możesz wręcz sprawdzić, że o kolizję będzie łatwiej.

winerfresh napisał(a)

Ja jak tworzyłem taką ministronkę, która nigdy już w starym frameworku nie wejdzie do produkcji to używałem mieszakni sha512(sha1(md5(hasło))). Teraz pewnie sięgnę po (b)crypt.

To w takim razie łamanie brutem jest asymptotycznie tak szybkie jak łamanie najsłabszego algorytmu w ciągu. md5 jest 128-bitowy i entropia końcowego hasza nie może być większa (chyba że dodajesz sporo soli). Mówiąc prościej: łamanie brutem tego ciągu haszy będzie ~ 10x wolniejsze od łamania brutem zwykłego md5, w wariancie optymistycznym. W wariancie pesymistycznym, taki ciąg może zmniejszać entropię końcowego hasza i szybkość znajdowania kolizji może być większa niż nawet w przypadku samego md5.

Zwykły sha512(hasło) byłby dużo lepszym rozwiązaniem.