-15% na nową książkę sekuraka: Wprowadzenie do bezpieczeństwa IT. Przy zamówieniu podaj kod: 10000

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

05 lutego 2021, 15:12 | Teksty | komentarzy 26

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:

Wygląd strony do generacji haseł metodą łańcuchów Markowa

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

Spodobał Ci się wpis? Podziel się nim ze znajomymi:



Komentarze

  1. Marcin

    Coś nie teges w tym zdaniu jest: „Z różnych względów możemy jednak mieć pewne hasła, których nie chcemy trzymać w tychże menadżerach, a przecież też… musimy też jakoś wymyślić to główne hasło!”

    No i kod js ma encje, słabo to wygląda.

    Odpowiedz
    • Michał Bentkowski

      Dzięki. Zdanie zmieniłem; fragment kodu poprawiony.

      Odpowiedz
      • zero one

        To się nazywa zrozumieć „konstruktywną krytykę”. ;-)
        Zdrowia Panie Michale!

        Odpowiedz
  2. Tomek

    Ale czy to nie sprawia, że hasło jest „mniej losowe”? Jeżeli znamy pierwszy wyraz i sposób tworzenia, to liczba kombinacji znacznie się nie zmniejsza?

    Odpowiedz
    • „Mniej losowe” od czego? Od sytuacji, gdy używamy niezależnych od siebie symboli? W przeliczeniu na symbol na pewno. Dlatego również i wygenerowane frazy są dłuższe.

      Wada jest niestety taka, że pokazanie tutaj, oparte na poemacie Mickiewicza zdania nie są lepsze od fraz generowanych z niezależnych symboli wg. wzorca (np. przymiotnik rzeczownik czasownik przysłówek ‘i’ przymiotnik rzeczownik czasownik przysłówek). Może większy korpus pomógłbym w czymś?

      Odpowiedz
    • Michał Bentkowski

      To dobre pytanie. Zaktualizuję pewnie w poniedziałek artykuł (albo napiszę nowy) z rozważaniami na temat losowości.

      Odpowiedz
      • Damien

        Generalnie łańcuchów i procesów markowa (np. HMM) używa się do budowania grafów ataków, np. szacowania najbardziej prawdopodobnych kroków jakie podejmie atakujący (używając do budowania grafu danych o lukach i innych cech systemu).

        Dlaczego nie używać tego samego do bardziej łebskiego brute forca?

        Odpowiedz
  3. Won-Tzu

    Cosik się posypało w tym kodzie i zamiast niektórych znaków są HTMLowe encje. (`&#91` zamiast `[`)

    Odpowiedz
  4. MBu

    Można też użyć łańcuchów Markowa na poziomie liter, a nie wyrazów. Wtedy hasła są niesłownikowe, ale w większości wymawialne. Wystarczy tylko dodać cyferki i znaki specjalne.

    Ciekawostka, ale pierwszym tekstem, którym nakarmiłem mój generator, był…. „Pan Tadeusz”. Przypadek?

    Odpowiedz
    • Te też nie są słownikowe. „Słownikowość” w kontekście kryptografii dotyczy nie obecności fragmentów haseł w słowniku języka polskiego, ale braku odporności na konkretny rodzaj ataku, polegającego na testowaniu niewielkiego, wybranego podzbioru wszystkich możliwych haseł. Ten zbiór nazywa się właśnie „słownikiem”. Oto wybrane przykłady haseł słownikowych: 01091977, correcthorsebatterystaple1!, 86mets, 742617000027, gesundheitsindustrie, chambersbu-emh2 i thyroparathyroidectomize. Tak żeby dać poczucie, co oznacza „słownikowe hasło”. :)

      Odpowiedz
  5. Ondrej

    > Z różnych względów możemy jednak mieć pewne hasła, których nie chcemy trzymać w tychże menadżerach

    Jakie to „względy”? Jakich haseł nie powinno się trzymać w menedżerze, który zaszyfrowaną bazę haseł przechowuje tylko lokalnie?

    Odpowiedz
    • Michał Bentkowski

      W moim przypadku – gdyby ktoś uzyskał dostep do moich haseł w menadżerze, to nie chciałbym, żeby uzyskał też dostęp do bankowości. Więc tego hasła tam nie trzymam.

      Odpowiedz
      • Franek

        Sytuacja z życia
        Wchodzisz codzzieniw do pracy, na wejściu pin jak codzień wpisujesz ener jesteś w firmie.
        I nagle któregoś dnia idziesz jak codzień do pracy myślisz o niebieskich migdałach chcesz wpisać PIN a w głowie biała plama w szufladce z napisem PIN…
        Jest i na to rozwiązanie, niestety analogowe.

        Odpowiedz
    • White

      @Michał Bentkowski

      1) Jeśli nasz model ryzyka obejmuje dostanie się atakującego do bazy haseł (np. programu KeePass) w czasie gdy jest ona odszyfrowana, to czy nie oznacza to jego dostępu do całej pamięci komputera? Wówczas hasło do banku – wpisywane przecież na tym samym komputerze – tak samo jest dostępne dla włamywacza. Mam rację?

      2) Hasła do banku kopiowanego z bazy KeePass do formularza na stronie banku nie da się przechwycić przez sprzętowy keylogger przy klawiaturze. A hasło wpisywane ręcznie – owszem.

      Czy nie lepiej więc trzymać wszystkie hasła w bazie? Ewentualnie te które chcemy mocniej chronić trzymać w odrębnej bazie, rzadziej odszyfrowywanej? Albo może wdrożyć izolację jak w QubesOS?

      Odpowiedz
      • Michał Bentkowski

        Ad 1. Zgadza się. Jeśli napastnik ma możliwość uruchomienia złośliwego oprogramowania, to zawsze może przechwycić hasło w momencie jego wpisywania; sposób przechowywania nie ma więc znaczenia.

        Natomiast nie jest to jedyny sposób dostania się do bazy haseł. Menadżer, którego używam, jest też wystawiony przez aplikację webową i czasem z takiej opcji też korzystam. Więc np. XSS mógłby pozwolić na wydobycie bazy haseł, pomimo braku wykonywania malware’u na moim komputerze.

        Ostatecznie: przechowywania hasła do banku w menadżerze haseł nie ma w moim przypadku sensu, bo i tak muszę podawać hasło w postaci maskowanej.

        Ad 2. Słuszna uwaga. Natomiast w moim osobistym modelu ryzyka wydaje mi się bardziej prawdopodobne, że ktoś zrobi mi XSS-a na stronie z menadżerem niż podepnie sprzętowy keylogger.

        Ciężko znaleźć tutaj jeden złoty środek, jak najlepiej przechowywać hasła; czy dzielić je na kilka baz itp. Warto rozważyć przed jakimi typami ataków chcemy się bronić i wdrożyć zabezpieczenia odpowiednie do tych typów.

        Odpowiedz
        • Joker

          > nie jest to jedyny sposób dostania się do bazy haseł. Menadżer,
          > którego używam, jest też wystawiony przez aplikację webową
          > i czasem z takiej opcji też korzystam

          No tak, ale przy korzystaniu jedynie z lokalnych plików KeePass (albo analogicznego rozwiązania), to zagrożenie zdalnego dostępu odpada.

          Odpowiedz
  6. Michał

    Gorzej jak cracker też używa łańcuchów markowa :D
    Czy łatwość zapamiętania nie jest zwyczajnie funkcją entropii?

    Odpowiedz
    • Michał Bentkowski

      Jeśli metoda by się spopularyzowała, to na pewno włamywacze zaczęliby tej metody też używać.

      Temat przeliczenia entropii dla tej metody jest u mnie otwarty – nie jestem do końca pewien, czy moje podejście jest właściwe, więc daję sobie trochę czasu na przemyślenie ;)

      Odpowiedz
  7. zero one

    Będę w pełni szczery. Pamiętać każde „silne” hasło to istny koszmar. Liczyć na menadżery to ryzyko. Jak postąpić? ;-) To trochę jak z kobietami – „żyć z nimi trudno a bez nich nie sposób”. (wybaczcie ja akurat hetero).

    Odpowiedz
    • Synhelmuta

      Jak postąpić? Zwyczajnie przeanalizować ryzyko i wybrać to, co ma większe szanse uniknięcia klapy w twojej sytuacji :) (ja wybaczam, inni pewnie też ;))

      Odpowiedz
  8. KrisK

    Widze że w wielu wypowiedziach płynie nieświadomości życia i/lub brak planów awaryjnych.
    Baza danych zapisane hasła wypadek i utrata pamięci częściowa lub trwała.
    I co? Jak macie plan awaryjny to ktoś ma hasło rodzina ma dostęp. Albo w pracy mają dostęp. Zależnie co to za baza. Ale…. w tej bazie nie zapiszecie sobie hasła do np pamiętnika…
    To hasło nie powinno się tam znaleźć.

    Scenariuszy można pisać wiele. Ten jest prosty i łatwy do wyśmiana ale życiowy.
    Mamy hasła pod hasłem i kto ma oprócz nas hasło? Znam już kilka przypadków ludzi którzy z dni a na dzień zostali wyłączenia i jest kolosalny problem.
    Warto stworzyć plik z danymi poufnymi i dać komuś zaufanemu dostęp do niego w razie naszej choroby czy śmierci. Ale są zeczy które są nasze i nasz śmierć czu choroba nie powinny tego zmieniać. Tu już takie hasło będzie jak znalazł

    Odpowiedz
  9. Gads4x4

    Taka metoda ma jak najbardziej sens. Co więcej, wystarczy użyć zlepku 3-4 wyrazów porozdzielanych znakami specjalnymi z zastosowaniem wersalików i sekwencji cyfr i jest to nie do złamania brutforcem czy słownikiem.

    Odpowiedz
  10. Zdzich

    Michale, pokojarzyło mi się przy tej okazji że Fortinet FortiWeb używa (do ochrony web-aplikacji przed potencjalnymi atakami) uczenia maszynowego opartego właśnie o Hidden Markov Model (HMM) :-)

    Odpowiedz
  11. Wiks

    To trochę taka kwadratura koła… Mieć trudne, unikalne hasło (dostępne w każdej chwili) i równocześnie 'niezgadywalne’.
    Tak jak my, tak i 'badacze-naszego-hasła’ mogą użyć wspomnianych w art. metod. Więc nie wiem, czy to coś poprawia.
    Podobnie jak Autor nie mam (bezgranicznego zaufania) do przechowywania swojego hasła w managerach. Więcej -nie mam zaufania do przechowywania go elektronicznie na OS (którego sam nie stworzyłem i nie updatuję). Trochę to paranoiczne, ale chyba tak jak zdrapki są bezpieczniejsze od SMS, tak kartka ołówek i naprawdę losowe hasła też…
    Mieć ciastko i zjeść ciastko, wykluczają się.

    Odpowiedz
  12. bbkr

    Okropnie przekombinowane. Dla kogo ma byc ta metoda? Dla ludzi, ktorzy nie potrafia wymyslec samodzielnie losowego zdania typu „Niebieski odkurzacz wciagnal podluzny klocek Lego”? Jest to uposledzneie umyslowe ponizej rozwoju 5-latka i na pewno taka osoba rowniez nie zapamieta zdania z generatora.

    Natomiast osobom z gorsza pamiecia prosciej miec haslo z istniejacej literatury, bo sama ilosc ksiazek i mozliwych do wyciecia fragmentow daje wystarczajaca entropie. Dla utrudnienia mozna wybrac cos z zapomnianej PRLowskiej makulatury (tresc nieindeksowana w wyszukiwarkach, na przyklad jako ebooki czy cytaty), zeby nikt nie odkryl latwo pochodzenia konkretnego zdania. Co wiecej wowczas maja metode ratunkowa jezeli hasla zapomna. Wystarczy wziac ksiazke z polki.

    Odpowiedz
  13. CoperNick

    Czy da się policzyć entropię takiego hasła? Polecam pracę programisty Bitcoin Core, Pietra Wuille o generowaniu wymawianych haseł. Przy okazji algorytm gwarantuje dana złożoność/entropię podawaną jako liczba bitów. Jeżeli algorytm tego nie gwarantuje, rozsądny człowiek będzie się obawiał i będzie starał się wygenerować hasło dłuższe niż jest to potrzebne.

    https://github.com/sipa/gramtropy

    Odpowiedz

Odpowiedz na mpan