Chociaż specjalistą od kryptografii nie jestem, poznałem już na tyle Google'a i matematykę, by to i owo móc we własnym zakresie jednoznacznie rozstrzygnąć oraz by zniechęcić do uprawiania amatorskiej kryptografii na wyczucie. W każdym razie zacznijmy od początku...

Własności funkcji haszującej

Funkcja haszująca dowolnej wiadomości musi przyporządkować pewien klucz, zazwyczaj stałej długości. Nawet najmniejsza zmiana w treści wiadomości powinna wygenerować zupełnie inny klucz. Dlatego też haszowanie jest bardzo często stosowane do weryfikowania poprawności danych, pozwalając na bardzo łatwe wykrycie przypadkowych lub celowych, ale niepożądanych zmian. Poniżej podaję przykład działania funkcji haszującej SHA1 dla dwóch bardzo podobnych ciągów:

• sha1(asia8) = 4669555f36df2142df9f828c4ac67cb6a6de602c
• sha1(asia7) = 8c5a87e3a225ec261d0ae279f16fcfe86bd10312

Istnieje tylko skończona ilość kluczy o zadanej długości, zaś ilość wiadomości jest nieskończona. Dlatego na pewno istnieją dwa teksty dające ten sam hasz - zwiemy to kolizją. W tym miejscu od kryptograficznych funkcji haszujących będziemy wymagać paru dodatkowych cech:

1. Praktycznie niewykonalne wygenerowanie wiadomości B o takim samym kluczu, jak zadana wiadomość A.
2. Praktycznie niewykonalne wygenerowanie dwóch wiadomości A i B o takim samym kluczu.
3. Brak praktycznej możliwości odtworzenia wiadomości A na podstawie jej klucza.

Przez brak praktycznej możliwości najczęściej rozumiemy porównywanie wszystkiego ze wszystkim, czyli atak siłowy.

Haszowanie w informatyce

Aby zapobiec przechwyceniu haseł użytkowników w wypadku kradzieży bazy danych, są one tam trzymane w postaci zahaszowanej, z której teoretycznie nie da się odtworzyć oryginału. Algorytm działania jest prosty. Gdy rejestrujemy się, system haszuje nasze hasło i zapisuje je w bazie. Podczas logowania, zawartość pola "Hasło" jest także haszowana i porównywana z zapisem w bazie. W ten sposób nie trzeba znać postaci jawnej, aby zalogować się do serwisu. Tyle mówi teoria. Jednak odnajdywanie prostych haseł w stylu asia8 jest banalne. Typowy słownik zawiera kilkaset tysięcy słów, mnożąc to przez 10, wychodzi nam parę milionów haseł do sprawdzenia - prawdę mówiąc możliwe jest nawet bezproblemowe skatalogowanie tego, przez co cały proces sprowadza się do znalezienia odpowiedniego rekordu w bazie. Mój komputer potrafi policzyć w ciągu sekundy kilkaset tysięcy haszów, więc przetworzenie całego słownika na bazę wykonałoby się w mgnieniu oka. Jest to powód, dla którego programiści próbują jakoś dodatkowo zabezpieczyć hasła użytkowników. I tak powstają cuda.

Wielokrotne haszowanie

Jest to najprostszy patent typowego, świeżo upieczonego programisty bez względu na kraj pochodzenia. Jeśli H(x) można prosto złamać dla banalnych haseł, to zrobię H(H(x)), hehehe. Gość będzie liczyć w nieskończoność, zanim się skapuje, co jest grane. Wspominałem już o amatorskiej kryptografii? Właśnie - jak programista się naoglądał za dużo filmów z Hollywood, wciąż żyje w świecie, w którym siła algorytmów szyfrujących tkwi w ich tajności. Ta era tymczasem zakończyła się około 1975 roku. Obecnie wszystkie wiodące algorytmy są jawne, a ich siła leży w matematyce skupionej wokół kilku działów takich, jak teoria liczb czy teoria złożoności obliczeniowej. Patent na podwójne zahaszowanie jest tak oklepany, że naprawdę ciężko oczekiwać, by atakujący nie sprawdzał również i tej kombinacji.

Co więcej, n-krotne haszowanie zwiększa lub w najlepszym wypadku pozostawia na niezmienionym poziomie podatność na kolizje. Niech A będzie wiadomością, której klucz o długości n znaków to H(A). Możemy to ponownie zahaszować, uzyskując H(H(A)). Teraz próbujemy skonstruować taką wiadomość B, że H(A) != H(B), ale H(H(A)) = H(H(B)). Ponieważ klucz w szczególności też może być kolejną wiadomością wejściową, może zajść jedna z dwóch sytuacji:

1. Istnieją dwie takie n-znakowe wiadomości będące poprawnym kluczem, które po zahaszowaniu dadzą ten sam klucz. Wtedy po podwójnym zahaszowaniu stworzymy kolizję między wiadomościami A i B, chociaż przy pojedynczym takiej kolizji nie ma. Oznacza to, że znajdując B i wprowadzając ją jako hasło, system z podwójnym haszowaniem by nas wpuścił; z pojedynczym - nie.
2. Pomiędzy n-znakowymi wiadomościami będącymi poprawnymi kluczami nie ma kolizji. Wtedy dla tego konkretnego zbioru funkcja haszująca jest bijekcją, co oznacza że istnieje też funkcja odwrotna potrafiąca analitycznie z H(H(A)) wyliczyć H(A) (ale już niekoniecznie samo A). Gdyby ktoś taką funkcję znalazł, udowadniając przy okazji bijekcję i dyskredytując H(), bez trudu odnalazłby sobie oryginalny hasz.

Nigdy natomiast nie zajdzie sytuacja odwrotna, tzn. H(A) = H(B) i H(H(A)) != H(H(B))

Są to rozważania dość teoretyczne, ponieważ kolizje tudzież funkcje odwrotne do H(H(x)) wcale nie muszą być specjalnie łatwiej wykrywalne, ale pokazuje to, że rzeczywistość jest nieco inna, niż podpowiada intuicja. Złożenie funkcji haszującej z samą sobą daje co najwyżej tak samo silną funkcję.

Tęczowe tablice

Tworzenie katalogów haszów dla wszystkich możliwych kombinacji haseł jest miejscożerne. Katalog zaledwie 25 miliardów haszów (bez samych haseł) zajmuje już ponad 1 TB. Znacznie bardziej optymalną pod względem zajętości wersją są tęczowe tablice, które są czymś więcej, niż zwykłą bazą danych. Pojedynczy rekord reprezentuje tutaj cały łańcuch powiązanych pewnymi przekształceniami haseł, co pozwala na tej samej powierzchni zapamiętać informacje o znacznie większej ilości kluczy.

Podstawą w tęczowych tablicach jest funkcja redukcyjna R(), która z podanego klucza generuje nowe hasło. W połączeniu z f. haszującą H() można w ten sposób z hasła startowego A zbudować całą sekwencję według następującego wzoru:

1. Ak = H(A)
2. B = R(Ak)
3. Bk = H(B)
4. C = R(Bk)
5. ...

Proces powtarzamy pewną skończoną liczbę razy, a w pojedynczym wierszu tęczowej tablicy zapisujemy wyłącznie początkowe A oraz końcowe X. Spróbujmy teraz odnaleźć hasło pasujące do klucza k. Polega to na tym, że wprowadzamy nasz klucz w ten sam cykl haszowania i redukcji. Otrzymywane hasła próbujemy dopasować do jednego z końcowych haseł w bazie. Jeśli nam się uda, odnajdujemy łańcuch, w którym znajduje się nasz klucz, a tym samym i hasło, które go generuje. Wystarczy odczytać z niego hasło początkowe, wpuścić je do maszynki hasz-redukcja i poczekać, aż dotrzemy do hasła, które w efekcie da nam zadany klucz k.

Na wygenerowanie porządnych tablic tęczowych potrzeba kupę czasu i mocy obliczeniowej, ale później otrzymujemy bardzo efektywne oraz znacznie bardziej optymalne objętościowo narzędzie do odkrywania haseł pasujących do kluczy.

Jak się bronić?

Wielokrotne haszowanie może dać nam słabszą funkcję haszującą, lecz często mówi się, że utrudniają one atak siłowy poprzez zwiększenie ilości niezbędnych operacji do wykonania. Z drugiej strony, nic nie stoi na przeszkodzie, aby wygenerować tęczowe tablice dla samych kluczy. Ponadto - wielokrotne haszowanie nie tylko obciąża komputery atakującego, ale też nasz własny serwer. W sieci widziałem już kody puszczające hasło przez pętlę mającą i 50000 powtórzeń. W przypadku sha1(), policzenie czegoś takiego na moim pececie w PHP zabiera 1/12 sekundy. Wyobraźmy sobie, co się stanie, gdy nasza strona stanie się popularna i serwer, zamiast obsługiwać ruch, będzie zajęty liczeniem kluczy :). Mi jakoś nie widzi się wysyłanie do wszystkich użytkowników maila z prośbą o wybranie nowego hasła, ponieważ z powodu zmniejszenia liczby iteracji trzeba na wszystkich kontach dokonać przehaszowania :).

Dodam, że ataki słownikowe lub siłowe mogą być robione na konkretnej aplikacji - wtedy problem wydajności będzie NASZYM problemem, a nie atakującego. On tylko będzie generować kolejne hasła, tymczasem klucze i tak będziemy liczyć my.

Istnieje bardzo prosta i powszechnie uznawana za skuteczną metoda radzenia sobie z tęczowymi tablicami. Z każdym kontem związujemy wygenerowaną losowo, ale jawną sól (kilkanaście znaków). Podczas haszowania, doklejamy ją do hasła. Powoduje to, że każde hasło wymaga innego zestawu tęczowych tablic.

Jednak ostatecznie bezpieczeństwo zależy od samych użytkowników. Ani sól, ani wielokrotne haszowanie, nie zabezpieczy debilnych haseł pokroju asia8 przed solidnym atakiem słownikowym. Pierwszy lepszy pecet poradzi sobie z czymś takim w mgnieniu oka.

Funkcje haszujące

Na zakończenie zebrałem parę informacji o popularnych funkcjach haszujących i ich bezpieczeństwie.

1. MD5 - generuje 128-bitowy skrót. Wciąż powszechnie stosowana, pomimo iż już od kilku lat znane są efektywne algorytmy generowania kolizji. Sprawdziłem jeden na własnym komputerze i uzyskałem kolizję już po 40 minutach. Inne cudeńka już wyczyniane: dwa podpisy cyfrowe z tym samym kluczem, dwa sensowne dokumenty PostScript, o plikach wykonywalnych nie wspominając.
2. SHA-1 - generuje 160-bitowy skrót. Udało się wygenerować pierwsze kolizje, lecz wciąż są to zadania dla najpotężniejszych superkomputerów.
3. SHA-2 - rodzina czterech funkcji różniących się głównie długością wyjściowego klucza. Jak dotąd nie wykryto jeszcze żadnych kolizji.

Zakończenie

Z tym wpisem miałem zaczekać do czasu skonsultowania się z jakimś kryptologiem, głównie pod kątem sprawdzenia, czy te wywody o wielokrotnym haszowaniu mają jedynie charakter akademicki, czy też faktycznie niosą jakieś implikacje, a jeśli tak, to jakie. Ponieważ jednak trochę się to odsuwa w czasie, najwyżej później uzupełnię i/lub sprostuję odpowiednie informacje, jeśli zajdzie potrzeba.

Powrót

Na Zyxist.com panuje swoboda wyrażania opinii oraz krytyki pod dowolnym adresem. Jedyny warunek: musi być ona kulturalna i rzeczowa. Na chamstwo, prostactwo lub jawne obrażanie kogokolwiek nie ma tu miejsca i takie komentarze są bardzo szybko usuwane. Jeśli zamierzasz polemizować z treścią wpisu, wpierw uważnie ją przeczytaj.