Hasła cząstkowe od kuchni

W niektórych systemach bankowych, podczas logowania, użytkownicy proszeni są o wpisanie tylko pewnych, wybranych pozycji w haśle. Takie rozwiązanie ma tę zaletę, że nawet gdy jakiś keylogger przechwyci moment wpisywani hasła, to i tak będzie miał tylko 3 albo 4 jego pozycje. Jeżeli dodatkowo trojan nie posiada opcji zapisywania zrzutów ekranowych, agresor nie będzie mógł stwierdzić, którym pozycjom przypisane są jakie litery.

Z takim rozwiązaniem, wiąże się oczywiście zupełnie inny mechanizm przechowywania hasła. W niniejszym artykule opiszę jak to rozwiązywano, jak nie powinno się tego rozwiązywać, oraz jak to zrobić dobrze.

Standardowo, hasła w bazie danych zapisywane są jako suma kontrolna np. MD5 (już rzadko, podatne na kolizje), czy SHA-256 (częściej). Takie rozwiązanie oczywiście częściowo uniemożliwia stosowanie haseł cząstkowych, no bo przecież jak porównać 3 znaki hasła z hashem, ale nie wyklucza całkowicie, co zaraz się wyjaśni.

Plaintext

Nie ma wątpliwości, że przechowywanie niezaszyfrowanych haseł w bazie, jest niczym innym jak głupotą. W prawdzie w takim przypadku zaimplementowanie algorytmu haseł cząstkowych byłoby bardzo proste, ale jest to takie samo zabezpieczenie jak kłódka na drzwiach z obluzowanymi zawiasami.

Hashe

Wcześniej wspomniałem, że wykorzystanie funkcji hashującej nie jest za bardzo możliwe, prawie nie jest. Często stosowaną techniką było tworzenie dla każdego hasła wszystkich możliwych kombinacji \(n\) znakowych, a następnie ich hashowanie. Czyli dla hasła 12 znakowego, w którym będziemy proszeni o podanie 4 znaków, baza musi zawierać tyle wpisów:

$$
C^{4}_{12} = {12 \choose 4}= 495
$$

Przy liczbie klientów liczonej w tysiącach, baza będzie miała naprawdę pokaźne rozmiary. Nie jest to rozwiązanie optymalne, ale jest akceptowalne.

Shamir’s Secret Sharing

Jest to algorytm szyfrowania współdzielonego, w którym klucz dzielony jest na części, a każdy uczestnik otrzymuje swoją część. Do odtworzenia klucza potrzeba wszystkich części albo tylko niektórych. Liczenie na to, że wszyscy uczestnicy podadzą swoją część, może okazać się niepraktyczne, dlatego często stosuje się schemat, w którym do odtworzenia klucza wystarczy kombinacja tylko \(k\) części.

Tego typu rozwiązanie stosowane jest właśnie w hasłach cząstkowych, co raz dokładnie Wam pokażę.

Szyfrowanie

Wybierzmy dowolne hasło \(P\) i zapiszmy je w systemie dziesiętnym. Ustalmy także zmienną \(N = 3\), która mówi o tym, ile znaków będzie musiał wprowadzić użytkownik.

\(P_{text{ASCII}} = text{rudy102}\)
\(P_{10} = {114, 117, 100, 121, 49, 48, 50}\)

Następnie, system generuje tajny klucz \(K\), który będzie unikalny dla każdego użytkownika. Klucz 32-bitowy powinien być wystarczający dla \(N=3\).

\(K_{10}=1732426912\)

 

W kolejnym kroku, generowane jest \(N-1\) 32-bitowych, losowych liczb \(R_1, R_2, \cdots, R(N-1)\).

\(R_1 = 1133272513\)
\(R_2 = 3880634564\)

Ostatni krok, to obliczenie \(k\) punktów (\(k\) jest długością hasła) na wielomianie.

\(y=K+R_1\cdot x+R_2\cdot x^2+\cdots+R_{(N-1)}\cdot x^{(N-1)}\), dla \(x=1,2,\cdots, k\)

Czyli w naszym przypadku będzie to:

\(y_1=1732426912+1133272513\cdot 1+3880634564\cdot 1^2=6746333989\)
\(y_2=1732426912+1133272513\cdot 2+3880634564\cdot 2^2=19521510194\)
\(y_3=40057955527\)
\(y_4= 68355669988\)
\(y_5=104414653577\)
\(y_6=148234906294\)
\(y_7=199816428139\)

Mając obliczone punkty, tworzymy wartości \(s\) wg schematu:
\(s_1=(y_1-P_1), s_2=(y_2-P_2),\cdots,s_k=(y_k-P_k)\)

\(s_1=6746333875\)
\(s_2= 19521510077\)
\(s_3=40057955427\)
\(s_4=68355669867\)
\(s_5=104414653528\)
\(s_6=148234906246\)
\(s_7=199816428089\)

W bazie przechowywane są właśnie te wartości \(s\) wraz z kluczem \(K\), albo jego hashem.

Autentykacja

Użytkownik wchodzi na stronę logowania i system losuje mu 3 pozycje w haśle, które ma uzupełnić. Niech w tym przypadku będą to pozycje: 2, 3 i 6.

System oblicza wartości \(y_i\) na podstawie liczb \(s\) zapisanych w bazie i 3 liter hasła wprowadzonych przez użytkownika w trakcie logowania \(P’\). Jest to zwykłe dodawanie, załóżmy, że użytkownik wprowadził poprawne wartości.

\(y_2 = s_2+P’_2 = 19521510194\)
\(y_3=s_3+P’_3 = 40057955527\)
\(y_6=s_6+P’_6 = 148234906294\)

Jako, że użytkownik wprowadził poprawne 3 znaki, wartości \(y\) są oczywiście takie same jak w poprzednim kroku.

Teraz chyba najtrudniejsza część całego algorytmu, musimy obliczyć wielomian \(K’\) na podstawie wzoru:

$$K’ = \sum_i y_i \cdot  \frac{\gamma (j) }{\gamma(i-j)}$$

Zmienna \(i\) przebiega po wszystkich wylosowanych przez system pozycjach, czyli w naszym przypadku będą to oczywiście: \(2, 3, 6\). Zmienna \(j\) zachowuje się podobnie, tylko omija aktualną wartość \(i\), np. gdy \(i=3\), to \(j={2, 6}\) (zachowuje się prawie jak zbiór). Funkcja \(\gamma\) to po prostu mnożenie, gdy podamy do niej \(j={3,6}\), czyli wtedy gdy \(i=2\), to \(\gamma(j)\) zwróci nam: \((3\cdot 6)\), natomiast \(\gamma(i-j)\) da wynik: \(((2-3)\cdot(2-6))\).

Zobaczmy to na naszym przykładzie:

$$K’ = 19521510194\cdot\frac{3\cdot 6}{(2-3)\cdot(2-6)}+40057955527\cdot\frac{2\cdot 6}{(3-2)\cdot(3-6)}+$$

$$+148234906294\cdot\frac{2\cdot 3}{(6-2)\cdot(6-3)} = 1732426912$$

Jeżeli \(K=K’\), oznacza to, że autentykacja się powiodła, czyli tak jak u nas.

Literatura

http://www.smartarchitects.co.uk/news/9/15/Partial-Passwords—How.html
http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

[guest@itachi.pl:~]$