zyxist.com

W bazach danych serwisów internetowych (i nie tylko) hasła użytkowników nie są trzymane w postaci jawnej. Przed ich zapisaniem przepuszcza się je przez jednokierunkową funkcję haszującą (zwaną też funkcją skrótu), która podany ciąg odwzorowuje jednoznacznie na pewien skrót o stałej długości (kilkaset bitów). Haszowanie jest procesem jednokierunkowym, w trakcie którego część informacji jest bezpowrotnie gubiona tak, że nie da się jednoznacznie odtworzyć oryginalnej wiadomości. Aby zweryfikować czy użytkownik wpisał poprawne hasło, po prostu haszujemy je i porównujemy wygenerowany skrót z tym, który jest w bazie. Choć idea jest prosta, w praktyce okazuje się, że jest niewystarczająca i aby obronić się przed częścią ataków, potrzeba czegoś więcej. Okazuje się jednak, że wielu - przede wszystkim początkujących programistów - dowiedziawszy się o tym, zaczyna podążać w niewłaściwym kierunku, proponując np. podwójne haszłowanie hasła: H(H(hasło)). Na czym polega problem? Na tym, że próbują oni uprawiać amatorską kryptografię na wyczucie, gdzie głównym kryterium oceny rozwiązania jest subiektywne, niepodparte żadnymi analizami przeświadczenie. Konsekwencje to nie tylko aplikacje z dziurami bezpieczeństwa, ale i chaos informacyjny wprowadzający w błąd innych.

Kryptograficzne funkcje haszujące

Funkcja haszująca to funkcja, która podanemu tekstowi przyporządkowuje pewien ściśle określony skrót będący ciągiem bitów o stałej długości. Skrót nie może zawierać elementów losowych; musi wynikać wprost z treści wiadomości. Zmieniając cokolwiek w treści, powinniśmy być w stanie to wykryć poprzez zauważenie, że zmienił się skrót. Poniżej podaję przykład działania jakieś wyimaginowanej funkcji haszującej h(x) dla dwóch tekstów:

• h(asia8) = 283
• h(asia7) = 918

Klasa funkcji haszujących jest bardzo rozległa - z powodu swoich właściwości znalazły one zastosowanie przy wykrywaniu i korekcie błędów w telekomunikacji, czy choćby w strukturach danych zwanych tablicami z haszowaniem. Skróty mają stałą długość, z czego wynika, że liczba możliwych do wygenerowania skrótów jest skończona. Możliwych tekstów wejściowych jest natomiast nieskończenie wiele, zatem istnieją dwa różne teksty mające ten sam skrót - zwiemy to kolizją. Zauważmy, że w przypadku naszej wyimaginowanej funkcji h(x) nie jesteśmy w stanie na podstawie skrótu ustalić, jak brzmiała oryginalna wiadomość, ale bez problemu znajdziemy dowolny pasujący do niego tekst. Taka właściwość jest bardzo niepożądana w sytuacji, gdybyśmy chcieli użyć tej funkcji do zabezpieczania haseł w naszej bazie. W tym miejscu do akcji wkraczają kryptograficzne funkcje haszujące, od których będziemy wymagać dodatkowych właściwości w zakresie odporności na kolizje:

1. praktycznie niewykonalne wygenerowanie wiadomości B o takim samym skrócie, jak zadana wiadomość A,
2. praktycznie niewykonalne wygenerowanie dwóch wiadomości A i B o takim samym skrócie,
3. brak praktycznej możliwości znalezienia jakiejkolwiek wiadomości A pasującej do podanego skrótu.

Przez brak praktycznej możliwości najczęściej rozumiemy porównywanie wszystkiego ze wszystkim, czyli atak siłowy. Przykładem kryptograficznej funkcji haszującej może być SHA3-256, która implementuje algorytm Keccak i generuje skróty o długości 256 bitów:

• sha3-256(asia8) = fc92df116f56ec6024cbed77b361752db87134136a10e4e0efc17913ef28fcdb
• sha3-256(asia7) = 6a55e542886a83c0774ef56dcb0d84afd6d919e24fff8d44f98f06f98fb2ee5d

Za wysoką zmienność generowanego skrótu odpowiada w takich funkcjach tzw. efekt lawiny. Polega on na tym, że jeśli zmienimy jeden bit w oryginalnej wiadomości, to znaczna część (np. połowa) bitów w skrócie powinna zmienić swoją wartość na przeciwną tak, aby uodpornić algorytm na próby analizy.

Problem oczywistych haseł

Na początku wpisu wspomniałem, że samo zahaszowanie haseł nie jest wystarczającym zabezpieczeniem. Problemem jest wykorzystywanie przez użytkowników oczywistych haseł. Choć liczba skrótów jest zbyt duża, aby stworzyć bazę obejmującą je wszystkie wraz z pasującymi tekstami, to stworzenie takiej bazy np. dla całego słownika języka polskiego jest jak najbardziej wykonalne. Przy jej pomocy możemy bardzo łatwo odkryć, że np. Adam jako hasła używa słowa cegłówka. Wystarczy, że sprawdzimy czy skrót jego hasła występuje w naszej bazie. W dodatku współczesne komputery są w stanie wygenerować nawet kilkaset tysięcy skrótów w ciągu sekundy, co czyni atak na bardzo proste kombinacje znaków bardzo banalnym bez względu na to, jakiej funkcji użyjemy. Stąd bierze się konieczność stosowania dodatkowych technik. I tak niestety powstają cuda, jeśli nie mamy podstawowej wiedzy z dziedziny kryptografii.

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ę zorientuje, co jest grane. Wspominałem już o amatorskiej kryptografii? Właśnie - jak programista czerpie swoją wiedzę z amerykańskich filmów akcji, 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.
Pomysł 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 skrót o długości n bitó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ż skrót w szczególności też może być kolejną wiadomością wejściową, może zajść jedna z dwóch sytuacji:

1. Dla danego algorytmu haszowania istnieją dwa takie skróty, które po ponownym zahaszowaniu wygenerują ten sam skrót. 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. Dla danego algorytmu haszowania pomiędzy dowolnymi dwoma skrótami 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 teoretyczne, ponieważ zgodnie z naszymi początkowymi założeniami, kolizje oraz funkcje odwrotne muszą być niemożliwie trudne do wyliczenia. Pokazuje to jednak, ż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ę. Warto też wspomnieć, że typowa kryptograficzna funkcja haszująca sama w sobie już zawiera pętlę wykonującą przez określoną liczbę rund zestaw tych samych operacji na bloku danych wejściowych. Podczas konkursów na standardy kryptograficzne parametry takie, jak liczba rund, podlegają ocenie i autorzy dokonują ich właściwej kalibracji, aby końcowy standard miał jak najlepsze właściwości. Wystarczy tylko przypomnieć kontrowersje wokół konkursu na algorytm SHA-3, jakie w środowiskach kryptograficznych wywołała próba opublikowania przez organizatora (NIST) jako standardu algorytmu o innych parametrach niż te nadesłane przez autorów. Dlatego poprawianie tych parametrów na oślep nie wydaje mi się najmądrzejszym podejściem.

Tęczowe tablice

W porządku, jak się zatem bronić? Aby zrozumieć ideę stojącą za konkretnymi rozwiązaniami, dobrze jest poznać same ataki. Wspomniałem wcześniej o tworzeniu katalogów skrótów. Gdyby stworzyć taki katalog dla skrótów SHA3-256 oraz słownika języka polskiego, zająłby on na oko 20-60 MB, zależnie od użytej funkcji skrótu, jednak zadziała on tylko dla haseł składających się z pojedynczych słów. Aby rozszerzyć atak przy pomocy takiego katalogu na większą liczbę możliwości, można zastosować tęczowe tablice (ang. rainbow tables), które są czymś więcej niż tylko zwykłą bazą danych. Pojedynczy rekord reprezentuje tutaj cały łańcuch powiązanych przekształceniami haseł, co pozwala na danej przestrzeni dyskowej zapamiętać informacje o znacznie większej liczbie skrótów.

Podstawą działania tęczowych tablic jest funkcja redukcyjna R(x), która z podanego skrótu generuje jakieś nowe hasło, np. o długości 8 znaków wg jakiejś przyjętej przez nas zasady. W połączeniu z funkcją haszującą H(x) 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 skrótu k. Polega to na tym, że wprowadzamy nasz skrót w ten sam cykl haszowania i redukcji. Otrzymywane hasła próbujemy dopasować do jednego z początkowych lub końcowych haseł w bazie. Jeśli nam się uda, oznacza to, że trafiliśmy na znany nam łańcuch. Teraz wystarczy już tylko 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 skrót k. Na wygenerowanie porządnych tablic tęczowych potrzeba dużo czasu i mocy obliczeniowej, jednak później otrzymujemy bardzo efektywne oraz znacznie bardziej optymalne objętościowo narzędzie do odkrywania haseł pasujących do skrótów.

Zauważmy, że tęczowe tablice nie atakują bezpośrednio funkcji haszującej, ale łatwe do zgadnięcia hasła, dla których skróty można skatalogować. Skutecznym zabezpieczeniem jest tutaj zastosowanie tzw. soli. Dla każdego użytkownika w naszej bazie generujemy losowy ciąg bitów, tzw. sól, który jawnie zapisujemy w bazie danych w rekordzie użytkownika. Sól doklejamy do jego hasła przed zahaszowaniem, innymi słowy - zawsze haszujemy hasło z doklejoną do niego solą. Aby złamać taki skrót, atakujący musiałby generować dla niego dedykowane tęczowe tablice, które uwzględniają doklejoną sól. Nadal jednak musimy uważać, by użytkownicy nie stosowali haseł będących prostymi słowami wziętymi do słownika. Dlaczego? Ponieważ - jak wspomnieliśmy wcześniej - typowy słownik zawiera tylko kilkaset tysięcy słów; przy założeniu, że typowy komputer osobisty jest w stanie wyliczyć np. 100 000 skrótów SHA3, czas na przebudowanie katalogu z użyciem innej soli to... 3 sekundy. Jeśli w naszej bazie jest 20000 użytkowników, moglibyśmy w mniej niż jeden dzień wygenerować indywidualny katalog dla każdego z nich.

Inne zabezpieczenia przed atakiem siłowym

Skuteczność soli polega na tym, że zmuszamy atakującego do wykonania ilości obliczeń związanej z przebudową tęczowych tablic, która jest niewspółmierna do zysku. To jest dla niektórych osób także argument za wielokrotnym haszowaniem - w ten sposób spowalniamy liczenie skrótu i sprawiamy, że ataki są kosztowniejsze. Owszem, jest to dobry argument, lecz szkopuł leży ponownie w tym, jak go zrealizujemy.

Przykładowa technika to tzw. key stretching, czyli po polsku rozciąganie skrótu, które jest połączeniem wielokrotnego haszowania razem z solą, a potwierdzeniem jej skuteczności jest to, że istnieją bazujące na niej algorytmy, które są standardami kryptograficznymi. Liczby powtórzeń idą w nich w tysiące, a wraz ze wzrostem mocy obliczeniowej komputerów można je jeszcze bardziej zwiększać. Oto kilka algorytmów tego typu:

• PBKDF2 opracowany przez RSA Laboratories - jako bazę wykorzystuje standardowe funkcje haszujące, np. z rodziny SHA. Znacząco może zwiększyć trudność ataków programowych, jednak algorytm jest bardzo prosty do zaimplementowania przy pomocy układów scalonych i wymaga mało dodatkowej pamięci, co otwiera furtkę do prób ataków przy pomocy dedykowanych układów sprzętowych lub GPU,
• bcrypt - bazuje na algorytmie szyfrującym blowfish, wykorzystując jego charakterystyczną cechę, tj. długą fazę inicjalizacji klucza. Wymaga większej ilości pamięci, ale wciąż nie da się jej ilością dokładnie sterować,
• scrypt - algorytm powstał w 2009 roku, a jednym z jego założeń jest dobra ochrona przed atakami sprzętowymi. W 2016 roku został opublikowany przez IEFT jako RFC 7914.

Przedstawione powyżej algorytmy to efekt długiej pracy wielu osób oraz dokładnego zrozumienia rodzajów ataków. Jaka jest szansa, że wymyślony na poczekaniu algorytm okaże się lepszy?

Aktualizacja funkcji haszujących

Dotychczasowa historia pokazuje, że zalecenia odnośnie wykorzystywanych funkcji haszujących zmieniają się z czasem. Gdy zaczynałem swoją przygodę z tworzeniem aplikacji internetowych gdzieś na początku ubiegłej dekady, z użycia powoli wychodził MD5, a krzykiem mody był SHA1. Obecnie istnieje wiele znanych technik ataku na MD5 i złamanie wygenerowanego przy jego pomocy skrótu nie jest niczym szczególnym, ani nie wymaga wielkiego wysiłku - zaledwie 10 dni temu świat obiegła informacja o kradzieży danych serwisu DaFont.com, gdzie hackerom udało się złamać zahaszowane MD5 hasła 98,5% z prawie 700 tys. użytkowników. Trzy miesiące temu Google ogłosił wygenerowanie kolizji SHA-1, publikując dwa dokumenty PDF o innym kolorze tła, lecz mające ten sam skrót, zaś rekomendowanymi rodzinami funkcji są SHA-2 oraz SHA-3. Bardzo prawdopodobne, że w przyszłości uda się przeprowadzić udane ataki również i na nie.

Oznacza to, że nasze aplikacje powinny być przygotowane na wymianę używanych funkcji haszujących, a my powinniśmy śledzić nowe rekomendacje w zakresie bezpieczeństwa i odpowiednio reagować. Problemem pozostają hasła wszystkich dotychczasowych użytkowników, można sobie z tym jednak poradzić:

1. w bazie, oprócz skrótu i soli zapisujemy także informacje o użytym algorytmie,
2. po zmianie algorytmu dokonujemy wymiany skrótów w momencie logowania użytkownika, kiedy przez chwilę mamy dostęp do hasła zapisanego czystym tekstem. Jeśli zauważymy, że w bazie jest hasło zaszyfrowane innym algorytmem, sprawdzamy je, ale przy okazji generujemy też nowy skrót i zapamiętujemy go do wszystkich późniejszych logowań.

Problem aktualizacji skrótów jest dość poważny, a widać go na przykładzie popularnej bazy avatarów Gravatar.com. Gdy pytamy się o avatar jakiegoś użytkownika, musimy w nim po prostu zahaszować jego adres e-mail funkcją... MD5 oraz wysłać go w zapytaniu, a w odpowiedzi dostaniemy avatar. Jeśli URL-e do Gravatara umieścimy w kodzie HTML naszego bloga, to równie dobrze moglibyśmy wypisywać e-maile użytkowników w sposób otwarty. Serwis ma też jeszcze jedną, ukrytą na pierwszy rzut oka wadę - adresy e-mail wielu ludzi zbudowane są w dość przewidywalny sposób, np. imię, nazwisko i jakiś znany dostawca poczty. Jeśli znamy czyjeś personalia oraz adres URL jego avatara, możemy próbować zgadnąć jego adres e-mail i po prostu porównywać skróty MD5, by sprawdzić czy nam się udało. Z tego powodu na tym blogu używam własnego proxy dla avatarów.

Podsumowanie

Na przykładzie wielokrotnego haszowania pokazałem, że nie powinniśmy uprawiać pseudo-kryptografii, bazującej na tym, co nam się wydaje. Kryptografia to dziedzina nauki, w dodatku dziedzina ścisła. Jeśli naszym celem jest po prostu stworzenie aplikacji internetowej, najlepsze co możemy zrobić, to wykorzystać gotowe, sprawdzone algorytmy i rozwiązania oraz przestrzegać rekomendacji specjalistów, zaś idąc w opracowywanie nowych rozwiązań - róbmy to porządnie.

Uwaga: oryginalny wpis o tym samym tytule opublikowałem na Zyxist.com w 2008 roku. Zdobył on wtedy bardzo dużą popularność i całkiem niedawno dostałem pytanie od dawnego czytelnika czy mógłbym go ponownie opublikować. Udało mi się odnaleźć starą wersję, lecz po lekturze uznałem, że wymaga ona odświeżenia i uzupełnienia o najnowsze informacje. Wynikiem jest właśnie ten wpis, napisany w dużej części od nowa tak, aby jak najlepiej służył współczesnemu czytelnikowi.