Generowanie łatwych do zapamiętania haseł z wykorzystaniem łańcuchów Markowa

Nie od dziś wiadomo, że tworzenie i zapamiętywanie haseł jest typowym problemem, z którym mierzy się praktycznie każdy użytkownik komputerów czy urządzeń mobilnych. Złe praktyki związane z hasłami często prowadzą też do incydentów bezpieczeństwa, np jeśli ustawimy je zbyt słabe i uda się złamać w ramach ataku bruteforce.

W odpowiedzi na ten problem coraz powszechniejsze staje się użycie menadżerów haseł, w którym wystarczy zapamiętać jedno hasło master, które to daje dostęp do wszystkich pozostałych haseł. Z różnych względów możemy jednak mieć takie hasła, których nie chcemy trzymać w tychże menadżerach, a i to główne hasło musimy przecież zapamiętać!

W ostatnich latach zaleca się podejście, w którym hasła są bardzo długie i składają się ze słów i zdań w języku ojczystym, zamiast losowych kombinacji liter, znaków specjalnych i cyfr. Innymi słowy – hasło okowa-blat-mikser-koniec-szczyt-rdza-szumny-ptak ma zbliżony poziom złożoności do 18 losowych znaków z zakresu [A-Za-z0-9], a jest bez porównania łatwiejsze do zapamiętania.

No właśnie! A może dałoby się wymyślić jeszcze lepszy sposób na tworzenie łatwych do zapamiętania haseł, ale inaczej niż poprzez wybieranie losowych słów ze słownika? O takim eksperymencie będzie ten tekst. Przykładowe hasło, które dostaniemy na końcu będzie wyglądać tak: włada czego dowodem jawnym jest lada jaką przeleciała drogą powitam zosienkę i jeśli nie jest piękności choć

Łańcuch Markowa

Inspiracją był dla mnie artykuł, na który dziś natrafiłem, dotyczący generowania tekstu z wykorzystaniem łańcucha Markowa. Czymże jest łańcuch Markowa? Wikipedia tłumaczy następująco:

Proces Markowa – ciąg zdarzeń, w którym prawdopodobieństwo każdego zdarzenia zależy jedynie od wyniku poprzedniego.

Łańcuchy Markowa to procesy Markowa z czasem dyskretnym.

Często przytaczanym przykładem zastosowania łańcuchów Markowa (także w tekście będącym inspiracją do eksperymentów) jest tworzenie modeli statystycznych pogody. Intuicyjnie chyba czujemy, że pogoda danego dnia jest w jakiś sposób zależna od pogody w dniu poprzednim. Moglibyśmy więc przygotować przykładowy model w następujący sposób:

• Jeśli pogoda dzisiaj jest słoneczna, to jest 90% szansy, że jutro też będzie słoneczna, a 10% – deszczowa.
• Jeśli pogoda dzisiaj jest deszczowa, to jest 50% szansy, że jutro pogoda będzie słoneczna, a 50% – deszczowa.

Przygotujmy prosty kod w JS, który wykorzysta ten model w celu wygenerowania pogody dla 10 kolejnych dni.

const model = {
  rainy: ["sunny", "rainy"],
  sunny: [
    "sunny",
    "sunny",
    "sunny",
    "sunny",
    "sunny",
    "sunny",
    "sunny",
    "sunny",
    "sunny",
    "rainy",
  ],
};

function randomElement(array) {
  return array[Math.floor(Math.random() * array.length)];
}

const start = randomElement(Object.keys(model));
const weather = [start];
for (let i = 0; i < 10; ++i) {
  weather.push(randomElement(model[weather[i]]));
}

console.log(weather.join(", "));

Przykładowy wynik wykonania kodu:

sunny, rainy, rainy, sunny, sunny, sunny, sunny, sunny, sunny, sunny, rainy

Tendencja powinna być taka, że gdy pojawi się dzień sunny, to będzie istniała większe prawdopodobieństwo, że kolejny dzień również taki. W większości wyników tak będzie właśnie to wyglądać.

Generowanie haseł

Jak się ma zatem łańcuch Markowa do generacji haseł? Spróbujemy język naturalny zmodelować w taki sposób, że prawdopodobieństwo kolejnego słowa, które wygenerujemy, będzie zależało od tego jakie było poprzednie.

To również powinno być intuicyjne. Na przykład jeśli wymyślę zdanie zaczynające się słowami: „Dzisiaj rano poszedłem do”, to na pewno istnieje większe prawdopodobieństwo, że kolejnym słowem będzie „sklepu”, niż „pomidor”.

Najpierw musimy jednak zbudować model danych. Zabawnym pomysłem wydało mi się nauczenie algorytmu polszczyzny na bazie Pana Tadeusza. Na stronach inicjatywy Wolne Lektury można znaleźć jego treść w postaci pliku txt, co jest doskonałym materiałem wejściowym. Sposób zbudowania modelu danych nie jest oczywisty; możemy zastosować kilka różnych podejść.

Ja spróbowałem następującego podejścia:

1. W modelu stanem jest jedno słowo,
2. Przejścia do kolejnego stanu zawierają dwa słowa.

Dzięki temu prawdopodobieństwo ułożenia sensownego zdania powinno być większe, niż gdyby przejście do kolejnego stanu składało się z jednego słowa.

Przykład: w całym Panu Tadeuszu słowo „początek” pojawia się cztery razy:

• „początek sporu o”
• „na początek dać małą wieś”
• „sędzia początek powieści posłyszał”
• „mają początek z Dobrzyna”

Jeśli więc algorytm wylosuje słowo „początek”, to później na pewno użyje dwóch kolejnych słów z jednej z tych czterech możliwości. Dzięki temu powinny wychodzić względnie sensownie zdania, a mają też pewną losowość.

Wynik eksperymentu zahostowałem na GitHub Pages:

Na stronie można użyć kilka gotowych tekstów lektur do generacji haseł. Oto przykłady haseł na podstawie Pana Tadeusza:

• łopot krepsztulowie z oficerów dobył się z przodu o koszta z drzewami naszemi czy aloes z długimi
• zdzieńciele słowem dawano huczne nad sklepem szalał już chciałem ten sprzęt rejencie proszę o głos żołnierski maćka
• wyzwanie w litwie jest zakazane pojedynkowanie jadę pożegnać stolnika po matce łowczynie która wpadnie trzy rany myślano

A dla porównania hasła na podstawie Chłopów, części czwartej:

• garnka nie ma wieś to zaraz zabierze a ma pojechał do budy ty do ojca bylicy gorąc
• nadszedł wypędził wszystkich że niech was łupią ze skóry z ludzi zdzierał jaki grosz kapnął niespodzianie pacierze
• obraziła się i chlipiąc rzewliwie na nic się nie bacząc nawet dzieci nie starczyło to chłopów o

Podsumowanie

Zastosowanie łańcuchów Markowa może być ciekawym podejściem do tworzenia trudnych do złamania, a łatwych do zapamiętania haseł. Docelowo rozwiązanie mogłoby być usprawnione – np. o celowe wprowadzenie „błędów” do haseł (np. błędów ortograficznych) czy wykrywaniu słów podobnie brzmiących. Ale to może eksperyment na inny raz!

— Michał Bentkowski, trener i haker w Securitum