Kryptografia haseł maskowanych, czyli magia matematyki

dodał 22 maja 2017 o 22:41 w kategorii HowTo, Krypto  z tagami:
Kryptografia haseł maskowanych, czyli magia matematyki

Zastanawialiście się kiedyś, jak zapisywane w bazie jest hasło maskowane, którego być może używacie by logować się do swojego banku? Odpowiedź ma dla Was Łukasz. I uwaga, będzie trochę matematyki (na poziomie podstawówki).

Niektóre banki uznały, że przesyłanie całego hasła za każdym razem gdy logujemy się do serwisu może stwarzać pewnego ryzyko, którego nie są w stanie zaakceptować i zaimplementowały podejście zwane „hasłami maskowanymi”. Zamiast prosić o całe hasło proszą tylko o kilka konkretnych znaków z tego hasła, na przykład 5, 7 i 11. Abstrahując od plusów i minusów takiego podejścia, za implementacją haseł maskowanych stoi spory kawałek wiedzy kryptograficznej. Niekiedy spotkałem się z pytaniami czy takie hasła muszą być przechowywane w bazie w postaci odwracalnej, bo nie można po prostu policzyć skrótu kryptograficznego. Przyjrzyjmy się zatem jak teoria pozwala nam poradzić sobie z bezpieczną implementacją takich haseł. Zdradzając zakończenie: nie, hasła nie muszą być przechowywane w postaci, którą łatwo odzyskać.

Ostrzeżenie: *nigdy* nie implementuj algorytmów kryptograficznych sam w domu. Pamiętaj, aby zawsze to robić w towarzystwie kogoś kto się na tym zna, a nie na podstawie jakiegoś artykułu w internecie.

Kody nuklearne i dzielenie sekretów

Załóżmy na moment, że Polska stała się potęgą nuklearną i właśnie Ty musisz opracować sposób wydania rozkazu użycia broni atomowej. Jednym z wymagań jest, aby dwóch generałów jednocześnie potwierdziło taki rozkaz. Musisz wymyślić system, który na to pozwala. Najprostszym rozwiązaniem byłoby stworzenie losowego hasła i rozdanie każdemu z nich połowy. Wtedy pojawia się kolejny problem: jeśli obcy wywiad przechwyci jednego z generałów to zdobędzie połowę hasła i efektywnie zmniejszy to długość hasła do znalezienia o połowę. Czy istnieje lepszy system, który nawet po porwaniu jednego z generałów nie pozwoliłby zbliżyć się w żaden sposób do złamania hasła?

Z pomocą przyjdzie nam geometria, a konkretnie jedna z najbardziej podstawowych prawd w geometrii, z której korzystamy prawie codziennie. Wiemy, że dowolne dwa różne punkty na płaszczyźnie w sposób jednoznaczny wyznaczają prostą na tej płaszczyźnie. Korzystamy z tego prawie za każdym razem kiedy używamy linijki. Z lekcji matematyki wiemy, że w układzie współrzędnych każda prosta jest jednoznacznie wyznaczona przez równanie: y = ax + b. Teraz wystarczy postąpić według następującego, krótkiego, schematu.

  1. Losujemy dowolne wartości a oraz b. Inaczej mówiąc: wybieramy dowolną, losową prostą na płaszczyźnie. Wartość b będzie naszym hasłem, które „rozdzielimy”.
  2. Na wybranej prostej losujemy dwa punkty o współrzędnych oznaczonych (x1, y1) oraz (x2, y2). Każdemu z generałów dajemy po jednym punkcie.

Gotowe – teraz każdy z generałów ma jeden punkt na prostej. Gdy się razem spotkają mają dokładnie jedną prostą wyznaczoną przez te oba punkty, a hasłem jest wartość w punkcie przecięcia prostej z osią Y, czyli, inaczej mówiąc, wartość w x = 0. Załóżmy, że obcy wywiad porwał jednego z generałów. Zdobyli w ten sposób jeden punkt na prostej. Wciąż nie wiedzą nic o tej prostej, a na pewno nie gdzie przetnie oś Y, ponieważ wciąż istnieje nieskończenie wiele prostych, które przechodzą przez ten punkt. Dzięki temu, że losowo wybraliśmy wartość a, zapewniliśmy, że porwanie jednego generała nie wystarczy, aby poznać nasze kody nuklearne. Można też rozwinąć takie dzielenie w inną stronę: jeśli wymagamy, aby dowolnych dwóch z pięciu (dziesięciu, piętnastu…) generałów było w stanie wydać rozkaz użycia broni atomowej, wystarczy każdemu z nich dać inny punkt na prostej – łącznie 5 (10, 15…) różnych punktów. Wtedy dowolnych dwóch będzie mogło zrekonstruować całą prostą. Swoją drogą, skoro obcy wywiad  już drugi raz porwał generała, to może warto rozdzielić hasło pomiędzy więcej osób niż dwie? To, tradycyjnie, zostawię jako proste ćwiczenie dla czytelnika (podpowiedź brzmi: „wielomiany„).

No dobrze, ale co to ma wspólnego z hasłami maskowanymi?

Zamaskowane hasło

Załóżmy, że nasze hasło, które chcemy „zamaskować”, składa się z dowolnej, ale mniejszej niż z góry ustalona liczby znaków. Każdy z tych znaków ma, odpowiadający mu, kod ASCII, który jest zwykłą liczbą. Dodatkowo, załóżmy, że bank spyta nas o tylko dwa znaki hasła. System, przy ustalaniu hasła, tak jak w poprzednim przypadku, losuje dwie wartości – a oraz b. W bazie danych zostanie zapisana wartość b, która będzie spełniała niejako taką samą funkcję jak skrót kryptograficzny w przypadku standardowej metody przechowywania haseł. Wartość b na końcu będzie porównywać z tym co wytworzymy z podanych przez użytkownika znaków hasła. Wartość a znów zapewni nam losowość, która spowoduje, że wyciek bazy nie będzie oznaczał automatycznie wycieku haseł.

Teraz losujemy tyle różnych punktów na naszej prostej, ile użytkownik podał znaków w swoim haśle. Każdy z tych punktów ma dwie współrzędne – x oraz y. Następnie w bazie danych przechowujemy, dla każdego punktu, wartość x oraz wartość y pomniejszoną o wartość ASCII znaku, który użytkownik wprowadził w haśle. Zauważmy, że bardzo istotne jest, żeby punkty przechowywać w odpowiedniej kolejności – wszak będziemy pytać użytkownika o znak hasła na ustalonej pozycji i musimy znać punkt, który tej pozycji w haśle odpowiadał. Teraz w bazie znajduje się tyle punktów, ile użytkownik ma znaków w haśle oraz wartość b. Dodatkową informacją, która nie musi być przechowywana w bazie, ale wynika bezpośrednio z przechowanych danych jest długość hasła użytkownika. Niestety, nie da się uniknąć przechowywania tej informacji – w końcu musimy zapytać użytkownika o pozycję w haśle, która istnieje. Zauważmy też, że w przypadku niemaskowanych haseł wartość ta nie jest w żaden sposób przechowywana ani w łatwy sposób wydobywalna z bazy danych.

Po stworzeniu hasła użytkownik kiedyś będzie chciał z niego skorzystać. Wtedy losujemy dwie (jak ustaliliśmy na początku) dowolne pozycje w haśle i pytamy użytkownika o te dwa znaki. Nic nas nie ogranicza – możemy spytać o dwa naprawdę dowolne znaki. W celu weryfikacji czy podane znaki są poprawne wykonujemy następujące kroki.

  1. Do współrzędnej y punktów, które odpowiadają wylosowanym pozycjom znaków dodajemy wartości ASCII znaków podanych przez użytkownika. Musimy dodać te wartości do odpowiednich punktów, dlatego tak ważne było trzymanie ich w kolejności.
  2. Mając dwa punkty odzyskane za pomocą wejścia od użytkownika jesteśmy w stanie wyznaczyć dokładnie jedną prostą na płaszczyźnie. Teraz wystarczy policzyć gdzie ta prosta przecina oś Y (inaczej mówiąc, jaka jest jej wartość w punkcie 0).
  3. Jeśli wyliczona wartość odpowiada wartości przechowywanej w bazie danych, to użytkownik poprawie podał znaki i może korzystać z bankowości elektronicznej. Oczywiście po odpowiednim sprawdzeniu drugiego czynnika uwierzytelnienia, na przykład wartości tokena.

Zauważmy, że wartość b była wybrany w losowy, niezwiązany z hasłem, sposób. Wartości punktów są co prawda związane z hasłem (poprzez odjęcie wartości znaków), ale też są losowe.

Jeśli bank chciałby zapytać o więcej niż dwa znaki hasła to, jak poprzednio, umiejętna czytelniczka bądź światły czytelnik będą w stanie rozszerzyć podany przykład, znów za pomocą wielomianów. Dodatkowo, przedstawiony algorytm jest teorią, która nie uwzględnia elementów poprawnej implementacji i optymalizacji jak i paru innych obostrzeń. Na przykład, że są lepsze i gorsze losowe punkty na prostej oraz powinno się unikać przetwarzania wartości odpowiadających liczbom rzeczywistym, a nie całkowitym.

Warto też wspomnieć, że samo użycie haseł maskowanych jest dosyć kontrowersyjne. Jednak ich implementacja może być przeprowadzona w sposób bezpieczny, tak, że nawet wykradając bazę danych atakujący będzie miał twardy orzech do zgryzienia, jeśli będzie chciał poznać hasło. Chociaż, jak wspomnieliśmy, nawet najlepsza implementacja wycieknie odrobinę metainformacji na temat hasła, a przechwycenie chociaż jednego zapytania o znaki w haśle zmniejszy przestrzeń możliwych wartości hasła. Poza tym należy pamięć, że jeśli coś może być zaimplementowane bezpiecznie to nie oznacza, że tak jest zaimplementowane.