Dla niecierpliwych: dzisiejszy wpis mówi o tym, czym jest i jak się używa funkcji haszującej w kryptografii, a także objaśnia, czym jest sól w przechowywaniu skrótów haseł. Jeżeli znasz obydwa zagadnienia, nie znajdziesz tu dziś niczego nowatorskiego - możesz więc śmiało przełączyć się na coś innego. Na przykład na Joe Monstera albo The Onion.
Dzisiejszy wpis będzie króciutki. To znaczy, z takim zamysłem go rozpoczynam, a co z tego wyjdzie - zobaczymy. W każdym razie nie planuję tu i teraz pisać "Wojny i pokoju", jeśli o to chodzi.
Dziś będzie o hasłach.
Jak powszechnie wiadomo [citation needed],najlepszą jak do tej pory znaną nam metodą na sprawdzenie, czy użytkownik wpisał poprawne hasło, jest porównanie skrótu hasła, jakie wpisał, ze skrótem przechowywanym w rekordzie tego użytkownika w bazie danych.
Zaraz, zaraz, ale że co?
Skrót hasła to nic innego jak wynik przepuszczenia tego hasła przez specjalną funkcję, która zamienia dowolnie długi tekst na "skrócony" tekst o stosunkowo niewielkiej długości. Ten "skrócony" tekst jest zwyczajowo zwany skrótem tekstu wejściowego i ma trzy ważne cechy:
- Dla tego samego tekstu na wejściu funkcji skrótu, funkcja zawsze zwróci ten sam skrót. A więc funkcja skrótu jest deterministyczna.
- Dowolnie mała zmiana w tekście na wejściu funkcji skrótu powoduje, że skrót nowego tekstu będzie się znacznie różnił od poprzedniego skrótu. W szczególności przyjmuje się, że dobrze napisana funkcja skrótu powinna zmieniać mniej więcej połowę bitów na wyjściu, w przypadku zmiany pojedynczego bitu na wejściu.
- Nie da się obliczeniowo odwrócić czynności generowania skrótu: nie da się odtworzyć tekstu, jaki był podany na wejście funkcji skrótu, znając jedynie wartość skrótu tego tekstu, w inny sposób niż próbując skrócić różne teksty licząc na to, że się trafi na ten właściwy. Innymi słowy funkcja skrótu jest jednokierunkowa.
W kwestii nomenklatury, funkcję skrótu nazywa się żargonowo funkcją haszującą, a generowane przez nią skróty - haszami.
Pokażę teraz kilka przykładów haszów MD5. Po lewej stronie jest tekst do zahaszowania a po prawej - hasz (skrót) MD5 tego tekstu.
kalarepa => c1d5b24f99ea1051afcbd9f0154a543b
blog => 126ac9f6149081eb0e97c2e939eaad52
To jest jakiś długi tekst napisany wyłącznie w celu pokazania, że funkcja skrótu faktycznie skraca dane wyjściowe. => a598e9d7edb1f8e3668c98e915fa95c9
No i teraz przechodzimy do samego gęstego, czyli do haseł.
Załóżmy, że budujemy system on-line, w którym użytkownicy mają własne konta zabezpieczone hasłem. Tzn. hasłami.
Skąd mamy wiedzieć, czy użytkownik wpisał poprawne hasło podczas logowania się do systemu?
Metoda naiwna polega na tym, że w momencie zakładania przez użytkownika konta zapisujemy jego hasło w bazie danych, a potem porównujemy to hasło z wpisanym podczas logowania.
Z tym, że to jest bardzo, bardzo kiepski pomysł. Po pierwsze ktoś się nam prędzej czy później włamie do systemu i ukradnie wszystkie hasła, a po drugie nawet jeżeli nikt się nam jeszcze nie włamał, mamy przecież pracowników z dostępem do bazy danych, mamy kopie zapasowe, które mogą wpaść w niepowołane ręce i tak dalej. Prędzej czy później jakiś "uczciwy inaczej" odczyta wszystkie hasła i zrobi z nich niewłaściwy użytek.
Zamiast więc stosować metodę naiwną i zapisywać hasła jawnie, wystarczy po prostu w momencie zakładania konta wygenerować skrót hasła podanego przez użytkownika i zapisać ten skrót w bazie danych. Ponieważ funkcja skrótu jest jednokierunkowa, nawet jeżeli ten skrót wpadnie w niepowołane ręce, będzie bardzo trudno odgadnąć hasło. Jedynym sposobem będzie próbowanie różnych haseł i wyliczanie ich skrótów licząc na to, że się "trafi".
Niestety, to, co napisałem w poprzednim zdaniu, nie do końca jest prawdą. Jeżeli włamywacz dostanie w swoje ręce wszystkie hasze ze wszystkich haseł użytkowników, może sobie nieco ułatwić zadanie. Na przykład może dysponować własną bazą danych haszów do popularnych haseł, lub do haseł krótkich. Lista wszystkich haszów haseł maksymalnie ośmioznakowych jest stosunkowo łatwa do pozyskania i pozwala na błyskawiczne znalezienie hasła.
Do tego dochodzą jeszcze kolizje: ponieważ funkcja skrótu jest asymetryczna, oczywistym jest, że prędzej czy później dwa różne hasła wygenerują ten sam skrót. Dlatego też włamywacz może "oszukać" system szukając haseł o skrótach identycznych z tymi, które przechowujemy w naszej bazie danych.
Do tego dochodzi jeszcze fakt, że jeżeli dwóch różnych użytkowników będzie miało to samo hasło (na przykład "dupa123"), skrót tego hasła będzie w obydwu przypadkach identyczny ("2c73bdccfcb396e58ede6691fb9ca773"). A to oznacza, że użytkownicy używający popularnych haseł będą łatwiejsi do wykrycia: szukamy w bazie powtórzeń haszy, a następnie atakujemy je słownikowo.
To wszystko sprawia, że samo przechowywanie haszy haseł, chociaż skuteczne w przypadku "głupiego" włamywacza, jest nadal kiepskim pomysłem w przypadku włamywacza sprytnego.
Cóż więc robić?
Idea jest trywialna: trzeba hasła posolić! Sól sprawi, że wszelkie metody oparte na wstępnie wyliczonych haszach okażą się bezużyteczne, podobnie jak metody oparte na duplikatach haszy.
Czym jest nasza tajemnicza sól?
Niczym innym jak dużą liczbą całkowitą, zapisaną (jawnie!) wraz z haszem hasła.
A więc tak: użytkownik zakłada sobie konto w naszym serwisie i podaje hasło, jakiego chciałby używać.
My w tym momencie generujemy losowo dużą liczbę całkowitą X i dopisujemy ją na koniec tego hasła, a następnie wyliczamy z tak powstałego "nowego hasła" hasz, który zapisujemy do bazy danych wraz z wartością X (w osobnej kolumnie). A więc każdy użytkownik będzie teraz miał zapisane dwa elementy: hasz "posolonego" hasła oraz wartość X.
W momencie logowania się do systemu pobieramy od użytkownika jego hasło, dopisujemy na koniec tego hasła wartość X (odczytaną z jego rekordu na serwerze), wyliczamy z całości skrót i porównujemy ten skrót ze skrótem zapisanym w bazie. Jeżeli się zgadza, hasło było poprawne.
Z punktu widzenia atakującego taki system jest praktycznie nie do przejścia. O ile na przykład da się wygenerować wszystkie hasze haseł ośmioznakowych (jest to liczba rzędu 10^15 czyli petabajty - sporo, ale nie niemożliwe), to już wygenerowanie wszystkich kombinacji haseł ośmioznakowych z 256-bitową solą jest fizycznie niemożliwe w czasie krótszym, niż ludzkie życie. A przechowanie tych kombinacji wymagałoby więcej miejsca, niż cały Internet.
To by było na tyle, jeśli chodzi o solenie haseł. Na koniec podam jeszcze jeden sposób ataku na system: bierzemy użytkownika i zaczynamy pomalutku obcinać mu palce. Istnieją szanse, że poda nam swoje hasło zanim dojdziemy do stóp...
Ewentualnie sadzamy go przed transmisją obrad Sejmu, chociaż ta ostatnia metoda powinna być zakazana ze względu na szczególne okrucieństwo.
“Po lewej stronie jest tekst do zahaszowania a po prawej – hasz (skrót) MD5 tego tekstu.
kalarepa => c1d5b24f99ea1051afcbd9f0154a543b”
Acha, te 6 znaków po lewej to hasło, a te chyba 31 po prawej to jego skrót. Myśłałem, że skrót powinien być krótszy od oryginału. Taki ze mnie oryginał.
MD5 zawsze generuje skrót 32-znakowy, niezależnie od długości “skracanego” tekstu.