Kilka dni temu Blizzard ogłosił, że włamywacze, którzy dostali się do jego wewnętrznej sieci, ukradli dane związane z uwierzytelnieniem graczy z Ameryki Północnej. Blizzard poinformował przy okazji, że korzysta z protokołu SRP, który nie jest zbyt znany.
W sieci szybko pojawiły się różne spekulacje, czy hashe haseł wykradzione Blizzardowi można złamać czy nie. Postanowiliśmy zatem skorzystać z okazji i przybliżyć czytelnikom ten ciekawy protokół, a także opisać możliwe ataki i ich wydajność.
Jak działa protokół Secure Remote Password
Protokół SRP został opracowany pod koniec lat 90tych na Uniwersytecie Stanforda i jest od tego czasu ciągle rozwijany i ulepszany. Jego podstawową funkcjonalnością jest zapewnienie takiego procesu uwierzytelnienia klienta, który pozostanie bezpieczny, nawet gdy:
- atakujący posiada pełna wiedzę na temat protokołu
- atakujący ma dostęp do obszernego słownika możliwych haseł
- atakujący może podsłuchać pełną treść komunikacji między klientem a serwerem
- atakujący może przechwytywać i fałszować wiadomości przesyłane między klientem a serwerem
- brak jest zaufanej trzeciej strony.
Protokół ten ma następujące zalety:
- serwer ma pewność, że użytkownik zna prawidłowe hasło
- użytkownik ma pewność, że loguje się do serwera, na którym zakładał konto
- zarówno użytkownik jak i serwer nie muszą się obawiać podsłuchu komunikacji.
Przykładem uwierzytelnienia, które nie spełnia tych kryteriów, jest np. przesyłanie do serwera hasła otwartym tekstem czy nawet przesyłanie hasha MD5 czy SHA1. W protokole SRP, nawet, gdy atakujący może podsłuchać całą komunikację z serwerem, dalej nie będzie mógł wykorzystać posiadanych danych do złamania hasła. Jak zatem przebiega komunikacja i co zawiera?
Stałe serwera
Działanie protokołu opiszemy na przykładzie hipotetycznego gracza World of Warcraft. Serwer Blizzarda zna, ustalone wcześniej i takie same dla wszystkich dwie stałe:
- N, które jest liczbą pierwszą, spełniająca warunek N = 2q+1, gdzie q też jest liczbą pierwszą
- g, które nazywane jest generatorem grupy i stanowi istotny element dalszych obliczeń
W oparciu o inżynierię wsteczną ustalono, że Blizzard używa w protokole Battle.net v1 następujących wartości stałych:
N (256 bitów) = 112624315653284427036559548610503669920632123929604336254260115573677366691719
g = 47
Z góry przyjęta jest także funkcja H, będąca funkcją skrótu, służącą do obliczania hashy w procesie uwierzytelnienia. W protokole Battle.net Blizzard używa funkcji SHA-1.
Tworzenie konta
W momencie zakładania konta WoW użytkownik wybiera:
- nazwę użytkownika, dalej oznaczoną jako I
- hasło, dalej oznaczone jako P
Serwer dodatkowo losuje dla każdego użytkownika:
- sól, czyli losowy ciąg znaków używany w procesie hashowania hasła, dalej oznaczoną jako s
Następnie serwer oblicza wartość x wg wzoru x = H(sH(I:P), czyli na przykład:
- I = „Wojownik”
- P = „mojetajnehaslo”
- s = „v&H23s,28!ww”
Dodatkowo ważna jest informacja, że Blizzard do obliczenia wartości x używa nazwy użytkownika oraz hasła, w których wszystkie małe litery zostały zamienione na duże litery, tym samym zmniejszając poziom trudności przy późniejszym łamaniu hasła.
Zatem x = SHA-1(v&H23s,28!ww(SHA-1(WOJOWNIK:MOJETAJNEHASLO),a więc
x = SHA-1(v&H23s,28!ww68a8b3d1d73c1dab6497719add583a07312e7779), czyli
x = c2f16151cbf9901525bc4093d58679918fe8c88e
Wartości x będziemy używać w formie potęgi, zatem zamieńmy ją na postać dziesiętną.
x = 1112927166858406668446468662484822604222664602484
W kolejnym kroku następuje jedna z najważniejszych operacji – obliczenie wartości tzw. weryfikatora, czyli liczby, która pozwoli sprawdzić, czy użytkownik podał prawidłową parę nazwy użytkownika i hasła.
Weryfikator, czyli v, obliczany jest wg wzoru:
v = g do potęgi x, modulo N
co oznacza, ze stała g (czyli u Blizzarda 47), podnoszone jest do potęgi właśnie obliczonego x, a następnie dzielone jest przez stałą N i obliczana jest reszta z tego dzielenia – która stanowi wartość weryfikatora.
Co trafia do bazy
W bazie Blizzarda zatem zapisywane są następujące wartości:
- I, czyli nazwa użytkownika
- s, czyli sól
- v, czyli weryfikator
Oczywiście system pamięta również stałe N oraz g, lecz wystarczy, że zapisze je raz dla wszystkich użytkowników.
Czy to jest bezpieczne
Co zatem dzieje się, gdy, tak jak miało to miejsce kilka dni temu, włamywacze uzyskają dostęp do bazy danych użytkowników i poznają I, s oraz v? Czy na tej podstawie będą w stanie odkryć P, czyli hasło użytkownika?
Wszystko sprowadza się do obliczenia x ze wzoru v = g do potęgi x, modulo N. Jako że v, g oraz N są znane, należy teraz otrzymać x. W tym wzorze x zwany jest logarytmem dyskretnym, uważanym za trudny do obliczenia. O tę właśnie trudność obliczeniową oparte jest bezpieczeństwo algorytmu SRP.
Wariant 1, czyli sprawdźmy wszystkie mozliwości
Jednym z możliwych ataków jest obliczenie dużej ilości prawdopodobnych wartości x na podstawie znanej soli s, nazwy użytkownika I oraz możliwych haseł P uzyskanych ze słownika lub generatora ciągów spełniających określone założenia. Każdorazowe obliczenie x wymaga również jego podstawienia do wzoru na v, by sprawdzić, czy wybrane hasło daje w rezultacie prawidłową wartość weryfikatora.
Obliczenia te mogą wydawać się bardzo skomplikowane, jednak niektóre elementy są bardzo proste. Obliczenie podwójnej wartości SHA-1 można przeprowadzać w tempie ok. miliarda prób na sekundę przy wykorzystaniu sprzętu dostępnego dla przeciętnego użytkownika. Bardziej złożone jest podnoszenie do potęgi i obliczanie wartości modulo (reszty z dzielenia). Modulo N, dla wartości N o długości 1024 bitów, można obliczać w tempie ok. 1,8 tysiąca na sekundę na 1 rdzeniu procesora i7 -2600. Dla N o długości 256 bitów będzie to już ok. 100 tysięcy obliczeń na sekundę.
Jeśli zatem baza skradziona przez włamywaczy zawierała wartości v obliczane przez protokół Battle.net v1.0 (N=256 bitów), to na 1 procesorze z 4 rdzeniami można weryfikować prawie 35 miliardów par „nazwa użytkownika + hasło” na dobę. Jeśli zaś baza zawierała wartości weryfikatora obliczane przez protokół Battle.net v2 (N=1024 bity), to jeden procesor umożliwia weryfikację ok. 600 milionów haseł na dobę.
Pamiętajmy tez cały czas, że Blizzard używa do obliczeń hasła, w którym wszystkie małe litery zostały zamienione na duże – zatem ilość możliwych haseł do przetestowania znacząco maleje.
Wariant 2, czyli obliczamy logarytm dyskretny
Okazuje się, że istnieją metody, pozwalające na obliczanie algorytmu dyskretnego dla N = 256 bitów w dość krótkim czasie. Pierwsza faza obliczeń wymaga większego zaangażowania czasowego, jednak w oparciu o otrzymane dane można relatywnie szybko obliczać kolejne logarytmy. Przy wykorzystaniu narzędzia GDLOG jednemu z badaczy, Samuelowi Nevesowi udało się przeprowadzić fazę generowania małych liczb pierwszych w ciągu 2 godzin i w oparciu o nią był w stanie obliczać kolejne logarytmy dyskretne w czasie od 15 sekund do kilku minut każdy. Zakładając, że narzędzie posiada możliwości optymalizacji, można przyjąć, że operację obliczenia logarytmu dyskretnego atakujący będzie w stanie przeprowadzić w 15 sekund. Co mu to da?
Dzięki obliczeniu x, będzie mógł kontynuować atak w tempie miliarda zamiast 400 tysięcy prób na sekundę, ponieważ otrzymawszy x będzie musiał jedynie obliczyć podwójne SHA-1 dla kolejnych propozycji haseł. Biorąc pod uwagę duże litery w haśle Blizzarda, oznacza to możliwość sprawdzenia wszystkich możliwych kombinacji dziewięciu liter, cyfr i znaków specjalnych w czasie krótszym niż doba.
Oczywiście opisany powyżej drugi wariant ataku może mieć zastosowanie jedynie w przypadku gdy N = 256 bitów, ponieważ analogiczne ataki na logarytm dyskretny przy N = 1-24 bitów nie są wykonalne.
Podsumowanie
Jak więc widać na przedstawionych powyżej przykładach, twierdzenie Blizzarda iż Chronimy te hasła przez Bezpieczny Zdalny Protokół Haseł (SRP – Secure Remote Password Protocol), który został tak zaprojektowany, aby odkodowywanie prawdziwych haseł było jak najbardziej utrudnione nie jest do końca prawdą. Dość trywialnym krokiem, znacznie podnoszącym bezpieczeństwo protokołu SRP, było by na przykład zastosowanie funkcji skrótu bcrypt, scrypt lub PBKDF2 zamiast szybkiego SHA-1.
Co także ciekawe, pytania, jak łamać hasła przechowywane przez Blizzarda, pojawiły się w sieci już w sierpniu 2011, na przykład tutaj i tutaj. Oba pytania zawierały charakterystyczne wartości N i g, specyficzne tylko dla jednej implementacji SRP – Battle.net v1.0.
Do napisania artykułu zainspirowały nas (i dostarczyły mnóstwa informacji oraz linków) świetne wpisy na blogu Jeremiego Spilmana.
