podwójne hashowanie haseł, ogólnie n-hashowanie Opcje

[nospor]

w związku z lekkim OT w pewnym temacie, który rozwinął się w ciekawą dyskusję, temat rozdzielam. Dotyczy on:
Czy podwójne (n-te) hashowanie hasła jest bezpieczniejsze, od pojedynczego hashowania

md5 sie nie odkoduje. mozna trafic na rozwiązanie metodą brute force. Dla tej metody jednak jest bez roznicy, czy ty dane haslo przepuścic przez md5 raz, dwa czy milion razy (IMG:style_emoticons/default/wink.gif)

Posty będące duplikacją postów już zawartych w temacie, będą bez ostrzeżenia usuwane. Ma to zapobiedz tworzeniu się zbędnego śmietnika

[Apocalyptiq]

Hm, ale ten mój pomysł miałby uniemożliwić dojście do hasła za pomocą dostępnych w necie baz danych z rozshashowanymi hashami. Wtedy musieliby sobie sami zrobić tablicę od nowa dla danego klucza :-) A że pozna klucz - możnaby własnie w bazie zapisywać te losowe klucze, wtedy nawet jakby je znał, musiałby dla każdego hasła utworzyć osobną tablicę tęczową, a takie coś to już byłby wyczyn (IMG:http://forum.php.pl/style_emoticons/default/biggrin.gif) Orientuje się ktoś ile czasu wymaga utworzenie takiej tablicy tęczowej lub takie bazy danych, jakie są dostępne w necie (wpisujemy hash i dostajemy hasło, z którego został wygenerowany)?

[sowiq]

A że pozna klucz - możnaby własnie w bazie zapisywać te losowe klucze, wtedy nawet jakby je znał, musiałby dla każdego hasła utworzyć osobną tablicę tęczową

Poczytaj o kolizjach.

Orientuje się ktoś ile czasu wymaga utworzenie takiej tablicy tęczowej lub takie bazy danych, jakie są dostępne w necie (wpisujemy hash i dostajemy hasło, z którego został wygenerowany)?

Ja mam taki projekt na Programowanie Równoległe i Rozproszone. Ściślej odpowiem jak go zrobię (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) Potrzeba na to i bardzo dużo czasu i bardzo dużo miejsca na dysku. Ogólnie rzecz biorąc im więcej tym lepiej, bo raczej trudne byłoby wygenerować każdą możliwą kombinację.

Ten post edytował sowiq 4.06.2009, 15:01:39

[Apocalyptiq]

Poczytaj o kolizjach.

Nie rozumiem, co do generowania hasha za pomocą hash_hmac mają kolizje? W chyba każdej metodzie hashowania istnieje jakieśtam prawdopodobieństwo powstania kolizji, ale hashowanie na podstawie losowego klucza, który jest później zapisywany, raczej zmniejsza to prawdopodobieństwo :-)

[sowiq]

W chyba każdej metodzie hashowania istnieje jakieśtam prawdopodobieństwo powstania kolizji, ale hashowanie na podstawie losowego klucza, który jest później zapisywany, raczej zmniejsza to prawdopodobieństwo :-)

Mylisz się. Prawdopodobieństwo powstania kolizji zależy od długości hasha, czyli od ilości możliwych kombinacji.
Jeśli takich kombinacji będzie N, to po wygenerowaniu 2 hashy masz 1/N prawdopodobieństwo, że nastąpiła kolizja. Im większe N, tym więcej trzeba się natrudzić, żeby trafić na ten sam wynik.
Skoro długość hasha jest określona, znaki w nim to 0-f, to ilość kombinacji jest skończona. Ilość ciągów wejściowych jest nieskończona, bo mozesz budować coraz dłuższe. Z tego jednoznacznie wynika, że kolizje są [wystarczyłoby (ilość_kombinacji_hasha + 1) ciągów wejściowych, żeby na 100% zdarzyła się jakaś kolizja]. Nieważne jak bardzo losowy ciąg będziesz kodował. Pytanie tylko jak trudno je znaleźć (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

Ten post edytował sowiq 4.06.2009, 15:46:48

[Apocalyptiq]

Mylisz się. Prawdopodobieństwo powstania kolizji zależy od długości hasha, czyli od ilości możliwych kombinacji.
Jeśli takich kombinacji będzie N, to po wygenerowaniu 2 hashy masz 1/N prawdopodobieństwo, że nastąpiła kolizja. Im większe N, tym więcej trzeba się natrudzić, żeby trafić na ten sam wynik.
Skoro długość hasha jest określona, znaki w nim to 0-f, to ilość kombinacji jest skończona. Ilość ciągów wejściowych jest nieskończona, bo mozesz budować coraz dłuższe. Z tego jednoznacznie wynika, że kolizje są [wystarczyłoby (ilość_kombinacji_hasha + 1) ciągów wejściowych, żeby na 100% zdarzyła się jakaś kolizja]. Nieważne jak bardzo losowy ciąg będziesz kodował. Pytanie tylko jak trudno je znaleźć (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

Hm, czyli jeżeli zmienię metodę hashowania z sha1 na powiedzmy sha512 (128 znaków), ten mój pomysł z hash_hmac powinien być ok? :-)

No i ja już mówie o tworzeniu hasha na podstawie jednego tylko klucza dla wszystkich kont, wtedy przecież prawdopodobieństwo kolizji jest takie samo jak przy surowym hashowaniu.

Ten post edytował Apocalyptiq 5.06.2009, 10:35:31

[sowiq]

Hm, czyli jeżeli zmienię metodę hashowania z sha1 na powiedzmy sha512 (128 znaków), ten mój pomysł z hash_hmac powinien być ok? :-)

Jeśli pracujesz dla Amerykańskiej armii i ochraniasz hasłem 'red button', to tak (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) Hash sha1 ma długość 40 znaków. Każdy z nich może być hexadecymalną wartością. Czyli ilość kombinacji sha1 to 16^40 = 1.46150164 * 10^48 (wg. Google). Przy sha512 ilość ta wzrasta do 16^128 = 1.34078079 * 10^154. Nie muszę Ci chyba mówić jak duże są to liczby (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

No i ja już mówie o tworzeniu hasha na podstawie jednego tylko klucza dla wszystkich kont, wtedy przecież prawdopodobieństwo kolizji jest takie samo jak przy surowym hashowaniu.

Dodawanie soli (klucza) ma za zadanie wykluczyć możliwość słownikowego ataku. Jeśli ktoś ma hasło password, to odnalezienie go nie jest trudne (porównywanie znalezionego hasha z generowanymi kolejno skrótami dla słów ze słownika). Ale jeśli dodasz sól, to hasło będzie wyglądało np. tak: password$%^HNJGCFksdfsdbj^*12. Wtedy słownikowy atak na nic się nie przyda (zakładając oczywiście, że hackerujący nie zna naszej soli).

Jeśli bardzo bredzę to proszę kogoś o poprawienie mnie. Ekspertem od kryptografii nie jestem (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

Ten post edytował sowiq 5.06.2009, 11:20:27