Podczas ostatniej dyskusji na temat haseł maskowanych pojawiła się sugestia, że jeśli atakujący "nie widzi", które znaki są wpisywane, wówczas odgadnięcie pełnego hasła jedynie na podstawie przechwyconych fragmentów haseł, jest trudne. No, w każdym razie trudniejsze. Temat już wówczas mnie zaintrygował, ale Q4 zbliżał się nieubłaganie i temat zarzuciłem. Pora wrócić do tego tematu.
Hasła maskowane inaczej
O co chodzi
Przede wszystkim oderwijmy się od haseł maskowanych. Zamiast tego pomyślmy o pewnej metodzie generowania hasła jednorazowego na podstawie współdzielonego sekretu. Metoda ta polega na podaniu wybranych znaków występujących w sekrecie. Co ważne, znaki są wybierane w kolejności wystąpienia, czyli np. jeśli sekret wygląda tak:
1234567890
to dopuszczalnymi wartościami hasła jednorazowego są:
1570 1239 3468
Przykładowe nieprawidłowe wartości to, przykładowo:
2185 1191
Wartości te są nieprawidłowe, bo po 2 nie występuje 1, a po 8 nie występuje 5 (pierwszy przykład), oraz 1 występuje tylko raz (drugi przykład). Czy na początku lepiej jest wybrać dłuższe, czy krótsze hasło (jeśli generowane hasła nie mają równej długości, tak jest np. dla części przypadków haseł maskowanych)? Czy kolejne hasło powinno być "odległe", czy raczej bliskie tym wcześniej rozważanym?
Hasła maskowane są jednym z przykładów wykorzystania tej metody generowania hasła jednorazowego, ale nie jedyną. Zdarzają się na przykład metody uwierzytelnienia polegające na podaniu wskazanych cyfr z numeru PESEL, czy innego tajnego kodu. Spotkałem się nawet z metodą autoryzacji transakcji, która działała właśnie w ten sposób. Na początku klient uzgadniał z bankiem pewien dzielony sekret, a następnie przy wysyłaniu operacji musiał podać znaki występujące w nim na określonych pozycjach.
Zwracam jeszcze raz uwagę na założenie odnośnie tego, że podawane znaki muszą występować w kolejności. Nie w każdym schemacie tak jest.
Co ma atakujący
Jaki scenariusz rozważamy? Co dla atakującego jest znane? Załóżmy, że atakujący ma możliwość podsłuchiwania wielu haseł generowanych przez użytkownika. Nie wie natomiast, o które znaki z całego hasła użytkownik jest proszony. Taki przypadek może zaistnieć na przykład wówczas, gdy "ofiara" w obecności atakującego uwierzytelnia się w call center.
Atakujący może robić pewne założenia co do długości sekretu. Ta długość może być albo znana (bo wiadomo, że w określonym przypadku należy wybrać sekret o długości np. 8 znaków), albo jego długość mieści się w określonym zakresie (minimalna i maksymalna długość hasła). Dodatkowe wnioski odnośnie długości sekretu atakujący może wyciągnąć na podstawie zebranych haseł jednorazowych. Jeśli występuje w nich 10 unikalnych znaków, to długość sekretu musi wynosić co najmniej 10, nawet jeśli system pozwala na użycie sekretu długości 8 znaków.
Co robi atakujący
Dla uproszczenia przyjmijmy, że atakujący zna długość sekretu, którego szuka. Jeśli w rzeczywistości ta wartość pozostaje nieznana, atakujący może przyjąć pewne założenia i trzymać się ich tak długo, jak długo nie znajdzie dowodu na to, że założenie jest błędne.
W ramach przykładu załóżmy, że szukana przez nas wartość to 2435 i dysponujemy następującymi fragmentami:
25 35 43
W pierwszym kroku atakujący wybiera jedno z haseł jednorazowych i generuje wszystkie sekrety, które mogły posłużyć do wygenerowania takiego hasła. Wygląda to mniej więcej tak:
25xx 2x5x 2xx5 x25x x2x5 xx25
Ten zestaw "możliwych sekretów" jest punktem wyjścia. W drugim kroku operację powtarza dla kolejnego wybranego hasła i otrzymuje następujący zbiór wartości:
35xx 3x5x 3xx5 x35x x3x5 xx35
W tej chwili pozostaje sprawdzenie "części wspólnej", czyli znalezienie takich wartości, które mogły posłużyć do wygenerowania zarówno hasła jednorazowego o wartości 25 jak i 35. Dla każdej z wartości ze zbioru wyjściowego porównywane są wszystkie wartości z bieżącego kroku. Czyli:
25xx 35xx (sprzeczne) 25xx 3x5x (sprzeczne) 25xx 3xx5 (sprzeczne) 25xx x35x (sprzeczne) 25xx x3x5 (sprzeczne) 25xx xx35 2535
W tej chwili mamy pierwszego kandydata na sekret. Trzeba go jednak odrzucić, bo nie ma tu już żadnego "wolnego" miejsca, a z zebranych danych wiemy, że są co najmniej 4 unikalne znaki.
Druga próba:
2x5x 35xx (sprzeczne) 2x5x 3x5x (sprzeczne) 2x5x 3xx5 (sprzeczne) 2x5x x35x 235x 2x5x x3x5 2355 2x5x xx35 (sprzeczne)
W tym przypadku znajdujemy dwie wartości, z czego jedna spełnia warunki potrzebne do przejścia do następnego kroku rozważań, 235_. Idźmy dalej:
2xx5 35xx (sprzeczne) 2xx5 3x5x (sprzeczne) 2xx5 3xx5 (sprzeczne) 2xx5 x35x 2355 2xx5 x3x5 23x5 2xx5 xx35 2x35 x25x 35xx (sprzeczne) x25x 3x5x 325x x25x 3xx5 3255 x25x x35x (sprzeczne) x25x x3x5 (sprzeczne) x25x xx35 (sprzeczne) xx25 35xx 3525 xx25 3x5x (sprzeczne) xx25 3xx5 3x25 xx25 x35x (sprzeczne) xx25 x3x5 x325 xx25 xx35 (sprzeczne)
Nowy "punkt wyjścia" wygląda następująco:
235x 23x5 2x35 325x 3x25 x325
Nie pozostaje nic innego, jak powtórzyć zabawę dla kolejnej przechwyconej wartości, czyli 43:
43xx 4x3x 4xx3 x43x x4x3 xx43
Na wyjściu w tej chwili otrzymamy tylko jeden możliwy ciąg znaków, w oparciu o który można uzyskać podane hasła jednorazowe. Jest to 2435, czyli oryginalny sekret (jak zauważył Koziołek, nie jest to jedyne rozwiązanie, może też być 4325).
Czy to działa
Jak pokazałem na bardzo prostym przykładzie - tak, działa. W praktyce jest jednak trochę gorzej, ten algorytm jest dość naiwny. Ilość przypadków "pośrednich", które są generowane i które trzeba sprawdzić, jest olbrzymia. Nieoptymalne jest również porównanie każdego z elementów "punktu wyjścia" z każdym elementem dla aktualnie rozważanego hasła jednorazowego.
Trzeba pamiętać, że na wyjściu nie zawsze osiągnie się dokładnie jedno rozwiązanie. Może okazać się, że na podstawie zebranych haseł jednorazowych można stworzyć więcej niż jeden sekret, który pozwoli na wygenerowanie wszystkich zebranych przypadków. W takiej sytuacji nie pozostaje nic więcej, jak próbować przechwycić kolejne hasło jednorazowe i eliminować ze zbioru te sekrety, w oparciu o które tego nowego hasła jednorazowego nie można wygenerować.
Jednym z założeń w tym przykładzie było posiadanie na początku "ataku" kilku(nastu) zebranych haseł jednorazowych. Ciekawym zagadnieniem jest to, jaki wpływ na efektywność odzyskiwania sekretu, ma wybór (kolejność) haseł jednorazowych, które wykorzystywane są w obliczeniach.
A wniosek płynie z tego taki, że...
Jeśli w jakimś zastosowaniu wykorzystane ma być hasło jednorazowe generowane w oparciu o pewien współdzielony sekret, ilość informacji, które atakujący może uzyskać o sekrecie wyłącznie na podstawie przechwyconych haseł jednorazowych, powinna być jak najmniejsza. Na przykład kolejność znaków występujących w haśle jednorazowym nie powinna sugerować kolejności znaków w sekrecie, a to oznacza, że lepsze są te schematy, w których mamy podać losowe znaki z sekretu, a nie kolejne (kolejne, czyli pozycja znaku n+1 musi być większa, niż znaku n, choć nie koniecznie o 1).
I tak na koniec, nieco w temacie: Improving the Security of Four-Digit PINs on Cell Phones. Temat do przemyśleń - jak zmienia się złożoność zadania odgadnięcia sekretu w opisywanym tutaj przykładzie, jeśli:
- na różnych pozycjach powtarzają się te same znaki (np. 1424),
- znak występuje co najwyżej raz (np. 1234),
Ale ogólny sposób postępowania chyba w rozumiały sposób został opisany?