27.08.2020 | 20:06

Marcin Zajączkowski

Jak sprawdzić hasło bez jego ujawniania, czyli czym jest k-anonimity

Uwierzylibyście stronie sprawdzającej „czy twoje hasło nie wyciekło już do sieci”? Jako czytelnicy z3s pewnie nie. Tymczasem da się to sprawdzić, nie narażając jednocześnie swojego hasła na ujawnienie. Jak? O tym pisze Marcin Zajączkowski.

Bezpieczeństwo i prywatność, szczególnie na masową skalę, często postrzegane są jako nieidące z sobą w parze. Zobaczmy, jak teorie naukowe mogą pomóc w sprawdzeniu bezpieczeństwa i unikalności naszego hasła bez potrzeby jego ujawniania.

W związku z realizowanymi pracami zawodowymi trafiłem ostatnio na koncepcję k-anonimowości, która pozwala na bezpieczniejsze udostępnianie zbiorów danych w sposób utrudniający naruszenie prywatności osób, których dane są w nich zawarte. W tym artykule chciałbym przedstawić jej przykładowe produkcyjne zastosowanie w toczącej się codziennie walce o używanie silnych i unikalnych haseł. Wszystko z zachowaniem prywatności i poufności.

Have I been pwned?

O serwisie „Have I been pwned?” pisaliśmy już wielokrotnie. Umożliwia on m.in. sprawdzenie, czy dane dotyczące naszego e-maila wyciekły, zapisanie się na powiadomienia, jak już wyciekną (to tylko kwestia czasu :-/) oraz weryfikację, czy nasze hasło (to używane albo to, jakiego chcemy użyć) znajduje się obecnie w bazie „znanych wycieków”.

To ostatnie jest przydatne, jeżeli bardzo lubimy nasze super hasło i wszędzie go używamy (odradzamy) albo jesteśmy organizacją, która chce sprawdzić, czy jej użytkownicy nie używają haseł, które są bardzo popularne i nagminnie pojawiają się w wyciekach (jak P@ssw0rd – 50000+ wystąpień). To drugie, w przypadku niektórych firm i organizacji, może być wręcz wpisane w rekomendacje wystosowane przez krajowy organ standaryzacyjny (jak amerykański NIST).

Podać czy nie podać?

W internecie można znaleźć różne ciekawe strony, umożliwiające dla przykładu sprawdzenie, czy numer naszej karty nie wyciekł. Wpisujemy pierwsze 5 cyfr. Strona informuje, że ma w bazie taką kartę. Podajemy 5 kolejnych – nadal ma. Martwimy się, że to może być nasza karta. Niestety strona „w trosce o bezpieczeństwo poszkodowanych” nie pokazuje danych pasujących kart, aż do momentu, gdy wpiszemy cały numer. Jeżeli strona była nieuczciwa (np. dla każdego podanego ciągu cyfr pokazała, że karta może być w spisie), w ten sposób mogliśmy przekazać dane naszej karty przestępcom. Jeżeli jeszcze pod jakimś pozorem podaliśmy również datę ważności i kod CVV/CVC, to teraz już na pewno nasze dane można traktować jako „znane osobom trzecim” :-).

Podobna sytuacja może być z hasłem. Serwis „Have I been pwned?” daje możliwość sprawdzenia, czy (i jak często) podane hasło było zawarte w skatalogowanych wyciekach. Wystawione API mogło być użyte do stworzenia strony, gdzie po podaniu hasła (zamienianego przez JavaScript po stronie przeglądarki na hash SHA1) jest ono wysyłane do serwera, który daje odpowiedź. Wydaje się, że Troy Hunt – twórca wspomnianego serwisu – prawdopodobnie ma uczciwe zamiary. Jednak zawsze istnieje ryzyko, iż w wyniku włamania do strony zostanie dołączony złośliwy skrypt, wysyłający wszystkie sprawdzane hasła (wraz w adresem IP i innymi danymi kontekstowymi) do przestępców. Patrząc na trwający 2 miesiące (i oparty na podobnym mechanizmie) wyciek 380 tysięcy danych płatniczych klientów British Airways, nie jest to niemożliwe. Czy można to zrobić sprytniej?

Pwned Passwords V2 – bezpieczna weryfikacja

Problem konieczności ujawnienia swojego (zahaszowanego) hasła został rozwiązany wraz z uruchomieniem drugiej wersji usługi Pwned Passwords. Z pomocą przyszła tutaj koncepcja k-anonimowości (ang. k-anonymity), na bazie której Junade Ali stworzył protokół anonimowej weryfikacji wygaśnięcia hasła, zintegrowany następnie z serwisem.

Koncepcja działania jest prosta. Pytający oblicza lokalnie skrót SHA1 sprawdzanego hasła i przekazuje w zapytaniu do serwera pierwsze 5 jego znaków. Serwer zwraca listę posiadanych skrótów, które zaczynają się od tych znaków. Pytający może porównać trzymany lokalnie skrót sprawdzanego hasła z otrzymaną listą, aby dowiedzieć się, czy i ile razy sprawdzane hasło wystąpiło w wyciekach. Szybko, prosto i bezpiecznie.

Przykładowy scenariusz:

  1. Kasia zakłada konto w serwisie dla Miłośników Mechaniki Kwantowej (dalej MMK).
  2. Kasia nie ma „pamięci do haseł” i podaje swoje ulubione, uniwersalne „P@ssw0rd”.
  3. Hasło ma 8+ znaków z czterech kategorii (małe i duże litery, cyfra oraz znak specjalny) i przechodzi walidację na „złożoność hasła”.
  4. Serwis (zarządzający kontami w) MMK wylicza lokalnie skrót hasła Kasi – 21BD12DC183F740EE76F27B78EB39C8AD972A757.
  5. Serwis MMK wysyła pierwsze pięć znaków skrótu (21BD1) do serwisu Pwned Passwords.
  6. Serwis MMK dostaje w odpowiedzi listę (w chwili pisania artykułu 528 różnych pozycji) skrótów z pasującym początkiem (poniżej dla ułatwienia podanym z nawiasie) wraz z ogólną liczbą wystąpień danego skrótu:
...
(21BD1)2D6980B9098804E7A83DC5831BFBAF3927F:1
(21BD1)2D8D1B3FAACCA6A3C6A91617B2FA32E2F57:1
(21BD1)2DC183F740EE76F27B78EB39C8AD972A757:52579
(21BD1)2DE4C0087846D223DBBCCF071614590F300:2
...
(21BD1)6D22A591152B1CB368DDEBE38AEF895259B:5
(21BD1)6D358B829C770F763CEA21BF73F550C3E2F:4
(21BD1)6D44A7750F3BDFC90CB4F5836B8926AFC5F:11
(21BD1)6D4A08CB51C8B88FC8CE07742974D7D541D:485
(21BD1)6E17B1233F394C9AE095D73B4CB4025A3AC:2
...
  1. Serwis MMK lokalnie porównuje skrót hasła Kasi (bez pierwszych 5 znaków) z otrzymaną listą (która też nie ma tych 5 znaków), sprawdzając, czy on tam występuje i ile razy.
  2. Hasło Kasi wystąpiło ponad 50000 razy. Zdecydowanie za dużo.
  3. System MMK prezentuje Kasi informacje o problemie wraz z klarownym wyjaśnieniem, jakie negatywne skutki finansowe, społeczne i zdrowotne może spowodować takie działanie oraz z rekomendacją użycia menedżera haseł i unikalnych, generowanych haseł w każdym serwisie.
  4. Kasia po przeanalizowaniu argumentów – zgodnie z rekomendacją – instaluje menedżer haseł i zaczyna używać unikalnych, wygenerowanych haseł (wraz ze zmianą dla już istniejących kont).
  5. System MMK z przyjemnością przyjmuje nowe hasło (i przechowuje je lokalnie z wykorzystaniem silnej funkcji skrótu z solą).
  6. Kolejny użytkownik w sieci stał się odrobinę bezpieczniejszy :-).

Warto tutaj podkreślić, iż podane przez użytkowniczkę hasło (ani jego skrót) nie opuściły w ogóle serwera, do którego następowało logowanie (który i tak musiał je poznać). Zewnętrzny serwis dowiedział się o pierwszych 5 znakach skrótu, co jest uznawane za bezpieczne, uwzględniając, że (w momencie uruchomienia drugiej wersji tej usługi – ponad 500 milionów haseł):

  1. Liczba zwracanych rekordów dla dowolnych 5 znaków jest w przedziale 381 do 584.
  2. Skróty zaczynające się od 5 wybranych znaków mogą być generowane ze zbioru zupełnie niepodobnych do siebie haseł (co utrudnia ich „zgadywanie”).

Warto wspomnieć, że – oprócz serwisów korporacyjnych – integracja z usługą sprawdzania haseł wbudowana jest w niektóre powszechnie używane publiczne serwisy, a także menadżery haseł oraz przeglądarki (i/lub rozszerzenia do przeglądarek) mogące weryfikować bezpieczeństwo wszystkich (i/lub zapamiętanych) haseł używanych przy logowaniu się.

O szczegółach technicznych dotyczących implementacji samego algorytmu oraz zmian w drugiej wersji API można przeczytać w oddzielnych wpisach autorów tych rozwiązań.

Inne zastosowania k-anonimowości

Ogólnie, anonimizacja jest procesem polegającym na usunięciu informacji, które umożliwiają identyfikację konkretnej osoby, której dane dotyczą. Przykładem może być zaczernienie części pół na formularzu. Jest to proces nieodwracalny, który niestety często znacząco zmniejsza przydatność całego zbioru danych. K-anonimowość zaś jest metodą polegającą na modyfikacji posiadanego zbioru danych w taki sposób, aby każdy zestaw danych wrażliwych występował w zanonimizowanym zbiorze przynajmniej k razy (k – liczba powtórzeń ustalona dla konkretnego zbioru). Dzięki temu znacząco utrudnione jest stwierdzenie, której konkretnej osoby dotyczy dany rekord. Jednocześnie metoda ta pozwala na zachowanie wysokiej użyteczności zbioru na potrzeby przetwarzania.

Dane medyczne są chyba najczęściej stosowanym przykładem na pokazanie działania (i przydatności) stosowania tej metody. W uproszonym wariancie możemy mieć: PESEL, imię, nazwisko, wiek, płeć, adres, wykształcenie i zdiagnozowaną chorobę (choroby). Udostępnienie takiej listy podmiotom badawczym może generować ryzyko ujawnienia, iż konkretny Jan Kowalski cierpi na coś, czego ujawnić światu by nie chciał.

Przy k-anonimowości dane, które nie mają istotnej wartości badawczej, są usuwane (jak PESEL, imię czy nazwisko). Wartości pozostałych pól związanych z identyfikacją osoby (jak wiek, adres czy wykształcenie) są generalizowane do postaci, która zapewnia wystąpienie przynajmniej k przypadków takich samych rekordów w danym zbiorze. Na przykład, dane dotyczące wieku będą przedziałowe <20, 20-30, 40-50, >50, dane dotyczące adresu będą miały pozostawioną tylko część kodu pocztowego (do określenia obszaru/wielkości miasta/województwa), a zdiagnozowane problemy zdrowotne zamiast konkretnego kodu schorzenia, będą w postaci: choroba układu oddechowego, choroba układu krwionośnego itp.

W rezultacie nadal będzie możliwe przeprowadzenie na przykład badań statystycznych dotyczących występowania problemów z sercem, w zależności od wieku i czynników kulturowych, bez ryzyka, że sąsiedzi zaczną kogoś wytykać palcami w związku ze „wstydliwą chorobą”.

Podsumowanie

Temat zachowania prywatności przy masowym zbieraniu danych (np. lokalizacyjnych) w związku z pandemią koronawirusa zdecydowanie jest na czasie. Zaproponowane niedawno przez Google i Apple rozwiązanie do bezpiecznego zbierania danych o interakcjach między ludźmi działa na innej zasadzie, jednak przyświeca mu ten sam cel. Koncepcje z ośrodków naukowych w połączeniu z dostępnymi możliwościami technicznymi otwierają różne ciekawe możliwości. Na świecie istnieją wręcz firmy, które w dedykowany sposób zajmują się tematem zachowania prywatności w udostępnianych zbiorach danych i w chwili obecnej raczej na pewno nie narzekają na brak klientów.

Powrót

Komentarze

  • 2020.08.27 20:51 TheOne

    Jak w kawale
    „Ale wygarnąłem szefowi w tej anonimowej ankiecie”!
    „Jakiej anonimowej ankiecie”?
    jeśli zbiór zwracanych skrótów jest jednoelementowy, to cała idea bierze w łeb.

    Nawet jeśli cała idea polega na tym żeby każdy kubełek miał k-elementów, to jak użytkownik końcowy ma to zweryfikować?

    Musi uwierzyć i to jest trochę słaby punkt.

    Odpowiedz
    • 2020.08.27 22:29 rozie

      Akurat jest napisane, że „liczba zwracanych rekordów dla dowolnych 5 znaków jest w przedziale 381 do 584”.

      Więcej, ani użytkownik, ani nikt inny nie musi wierzyć, może to samodzielnie sprawdzić czy to odpytując o wszystkie pięcioznakowe kombinacje (powodzenia), czy też po prostu pobierając bazę hashy i ilości ich wystąpień z HIBP i analizując dane samodzielnie.

      cat baza_HIBP | cut -c -5 | sort | uniq -c | sort -n

      Lub odpowiednik, bo ww. będzie wolne, o ile w ogóle się wykona.

      Odpowiedz
  • 2020.08.27 20:59 rozie

    To ja pozwolę sobie na małą polemikę. Konkretnie z „zewnętrzny serwis dowiedział się o pierwszych 5 znakach skrótu, co jest uznawane za bezpieczne”. Czy naprawdę jest to bezpieczne?

    Wszystko opiera się o założenie, że serwer zewnętrzny ma szansę od 1 do 381 do 1 do 584 na poznanie hasła użytkownika. Ale skoro już bawimy się w statystykę, to zamiast zwykłego prawdopodobieństwa należałoby lekko podeprzeć się socjologią(?) i tym, że jeśli początek skrótu należy do jakiegoś popularnego hasła, to raczej chodzi właśnie o nie. Czyli użyć prawdopodobieństwa ważonego, z uwzględnieniem ilości wystąpień.

    Przy takim podejściu mamy: suma wystąpień haseł o danych 5 znakach 60808. Prawdopodobieństwo, że chodzi o hash (21BD1)2DC183F740EE76F27B78EB39C8AD972A757 –
    52579/60808 = 86%. Czy zewnętrzny serwis wie o które hasło było zapytanie? Oczywiście nie. Ma „jedynie” 86% pewności.

    Odpowiedz
    • 2020.08.27 22:37 zatroskany

      Co daje zewnętrznemu serwisowi poznanie pierwszych pięciu liter, a nawet 86% szansa poznania hasła użytkownika jeśli nie ma loginu użytkownika? Już nie mówiąc o tym, że cały zamysł ma na celu popchania użytkownika do zmiany tego słabego, pierwszego hasła na inne, więc istnieje duża szansa, że ten „leak” pierwszych pięciu liter hasła zaraz zamieni się w „leak” pierwszych pięciu liter nieaktualnego hasła…

      Teoretycznie jeśli serwer zewnętrzny byłby złośliwy mógłby zgadywać, że jakiś użytkownik MOŻE założył konto ze słabym hasłem i o ile atakujący posiadałby dodatkowo np. ostatnie loginy na jakie zostały założone konta mógłby przeprowadzić skuteczny atak.

      Naciągane to „jedynie” 86% skuteczności ;)

      Odpowiedz
      • 2020.08.28 06:50 rozie

        Co daje poznanie pięciu znaków hasha, jeśli nie zna loginu użytkownika? To zależy. W tym przypadku głównie od tego, kto poznał te pięć liter i jakie jeszcze dane może poznać. Jaka firma obsługuje sprawdzenia hashy w przypadku HIBP i czym jeszcze się ona zajmuje?

        Zamysł zamysłem, ludzie ludźmi. Zamysł jest po stronie serwisu, który sprawdza, czy jego użytkownicy mają „bezpieczne” hasła. O tym, że użytkownicy lubią mieć to samo hasło do wielu serwisów jest już w samym artykule. Czy użytkownik faktycznie zmieni hasło, nawet w tym jednym serwisie, po komunikacie? Oczywiście można w to wierzyć. Ale mając tak wielką wiarę w stosowanie się użytkowników do komunikatów można im po prostu napisać „używaj losowych haseł i managerów haseł. ;-)

        K-anonimowość nie jest odpowiedzią na wszystko, tylko tyle.

        Odpowiedz
    • 2020.08.28 09:44 zbrodel

      Bo tu chodzi o co innego – żeby nie zasilać bazy „wyciekniętych” haseł o hasła wcale nie „wyciekniętę”. W tej wersji to nie zachodzi, bo serwis dostaje tylko 5 znaków z hasha. Co więcej, nawet jeśli te 5 znaków pasuje do jednego z kilkuset hashy w bazie, to wcale nie znaczy, żę użytkownik podał jedno z tych kilkuset haseł. Mógł podać zupełnie inne, którego nie ma w bazie, a którego hash przypadkowo zaczyna się od tych samych znaków. A serwis tego NIE WIE, i NIE ZNA podanego hasła. Dopiero po stronie klienta zachodzi weryfikacja, czy hash pasuje czy nie.

      Przypominam, że z podobieństwa hashy (np. wspólny początek) nie można wyciągać żadnych wniosków na temat podobieństwa hashowanych wartości. Więc to nie jest nawet „o, on ma hasło podobne do któregoś z tych kilkuset w mojej bazie”. Nie ma.

      Odpowiedz
      • 2020.08.28 11:02 rozie

        Ja doskonale rozumiem jak to działa. Oczywiście jest wiele hashy o wspólnym początku i oczywiście hash naszego ciągu znaków nie musi być w ogóle w bazie – 86% jest wartością przybliżoną. I oczywiście serwis niczego z całą pewnością nie wie.

        Tylko nie mówimy tu od losowych ciągach znaków z których są liczone hashe. Mówimy o hasłach tworzonych przez ludzi. I tu wchodzą ludzkie nawyki i statystyka.

        Odpowiedz
  • 2020.08.27 23:11 JeZZoo

    Ale jakie znaczenie ma ta statystyka? Anonimowo pytasz o hasło wysyłając te 5 znaków z hasha. Nie ma powiązania z identyfikatorem. Serwis nadal wie, co wiedział, bo analizę częstości występowania danego hasha czy pierwszych 5 znakow zrobi na danych, które już ma i zapytania nie są mu do niczego potrzebne. Nawet jeśli zdarzy się tak, że trafi się na kombinacje 5 znaków, dla których zostanie zwrócony 1 hash, przyjmijmy nawet, że złamany i znane jest hasło plaintext to nadal serwer wie jedynie, że ktoś odpytał go o hash z unikalnym początkiem, ale nie wie kto (zna API key, ale co z tego?).

    Odpowiedz
    • 2020.09.01 22:08 Filip

      No właśnie widzisz serwer czy API wie więcej niż byś chciał. Może poznać cały zwiazany z Tobą kontekst np. adres ip który przeważnie leży w tabeli zaraz obok loginu i hasha hasła które sobie wyciekły. Możesz to bagatelizować oczywiście ale warto abyś się jednak zastanowił czy aby na pewno nie widzisz tu zagrożenia. K – anonimization jest fajne ale szumne hasło na stronie jakiegoś serwisu nie zwalnia od myślenia.

      Odpowiedz
  • 2020.08.28 07:46 Rithande

    :s/opóźniły/opuściły w pierwszym zdaniu po 12 punktowym przykładowym scenariuszu.

    Odpowiedz
  • 2020.08.28 08:27 dedesad267

    „Wydaje się, że Troy Hunt – twórca wspomnianego serwisu – prawdopodobnie ma uczciwe zamiary”

    Warto dodać, że przeszedł na Open Source: https://www.troyhunt.com/im-open-sourcing-the-have-i-been-pwned-code-base/

    Odpowiedz
  • 2020.08.28 08:45 stryku

    To mój pierwszy komentarz, więc cześć wszystkim (:

    Tematyka wiąże się mocno z moim pet projektem, więc pozwolę sobie go przedstawić.

    Biblioteka i CLI do szybkiego sprawdzania OFFLINE, czy hash SHA1 wystąpił w bazie HIBP. Sposób działania jest prosty:
    1. Ściągasz plik .txt z HIBP
    2. Wrzucasz go w okonia
    2.1 okon go mieli i wypluwa przygotowany pod okonia plik
    3. Używając biblioteki albo CLI, sprawdzasz, czy dany hash wystąpił w bazie. Okon wypluwa '1′ gdy hash występuje albo '0′ gdy nie.

    Punkty 2 (przygotowywanie) i 3 (sprawdzanie) są całkowicie offline.

    Punkt 2 (przygotowywanie) jest jednorazowy (dla danej bazy). Potem można już sprawdzać wielokrotnie.
    Przygotowywanie trwa (na moim kompie) 342.2 sekund (5.7 minut) na SSD.
    Sprawdzanie, czy hash występuje, trwa (znow, na moim kompie) 3.405 MILIsekund, na SSD (13ms na HDD).

    Projekt jest open source, licencja MIT. Kod źródłowy, więcej info i przykłady użycia na githubie: https://github.com/stryku/okon

    W razie pytań/uwag śmiało albo tu albo issue na githubie.

    Odpowiedz
    • 2020.09.03 16:06 l0l3k

      mam nadzieję, że nie padnie tutaj pytanie „dlaczego okoń” :>

      Odpowiedz

Zostaw odpowiedź

Jeśli chcesz zwrócić uwagę na literówkę lub inny błąd techniczny, zapraszamy do formularza kontaktowego. Reagujemy równie szybko.

Jak sprawdzić hasło bez jego ujawniania, czyli czym jest k-anonimity

Komentarze