Dlaczego k-anonimowość nie jest dobra przy hasłach?

Na z3s.pl pojawił się artykuł o tym, czym jest k-anonimowość. Jest to dobry artykuł i warto go przeczytać przed lekturą tego wpisu. Nie zgadzam się jedynie z tezą, że w przypadku haseł jest to bezpieczna metoda sprawdzania. Napisałem komentarz, ale pewnie nie wszyscy czytelnicy bloga tam trafią. Ponieważ bawię się z bazą hashy z HIBP i planuję wkrótce wpis na ten temat, uznałem, że jest dobra okazja do wstępu.

Moja teza jest taka, że w przypadku haseł k-anonimowość wcale nie jest taka bezpieczna, jak jest to przedstawiane. Zgodnie z artykułem obecnie dla hashy z bazy HIBP pierwsze 5 znaków występuje od 381 do 584. Czyli podczas sprawdzenia strona trzecia nie poznaje ani hasła, ani jego pełnego hasha. Przekazywane jest jedynie pierwszych 5 znaków hasha, czyli – tu moja interpretacja – ma jedynie 1/381 do 1/584 prawdopodobieństwo, że zna właściwy hash.

Gdyby przyjąć, że strona trzecia jest złośliwa, warto też przyjąć, że jest inteligentna. Czyli zamiast prawdopodobieństwa zwykłego użyje prawdopodobieństwa ważonego, uwzględniając ilość wystąpień danego hasha. Dla przykładu z artykułu na z3s.pl i hasła P@ssw0rd mamy zwracanych 543 różnych hashy:

curl -s https://api.pwnedpasswords.com/range/21BD1 | wc -l

Natomiast suma wystąpień wszystkich hashy w momencie pisania tego wpisu wynosi 60808.

curl -s https://api.pwnedpasswords.com/range/21BD1 | awk -F ":" '{sum += $2} END {print sum}'

Nasz hash wystąpił 52579 razy. Znając zwyczaje ludzi dotyczące haseł i stosując prawdopodobieństwo ważone uzyskujemy 86% szansę na to, że chodzi o hash należący do hasła P@ssw0rd. Pewności nie ma, ale z 1/543 czyli z ~0,18% robi się 86%, czyli jakieś 467 razy więcej. Ups!

Oczywiście nie znamy tu samego hasła. Znamy jedynie – a i to jedynie ze sporym prawdopodobieństwem – jego hash. O tym, że to niekoniecznie jest problem, może będzie w którymś kolejnym wpisie.

W każdym razie gdybym był serwisem, to bałbym się odpytywać serwis trzeci o hashe haseł moich użytkowników. Użytkowników podejrzewam o proste, słownikowe hasła, jakiś serwis trzeci. Zwłaszcza jeśli ten serwis ma/może mieć także inne informacje, które pozwalają mu ustalić kto pyta o hasło. Tak właśnie może być w przypadku Cloudflare, który może dostawać część ruchu od użytkownika w ramach CDN, DNS lub DoH. Prosta korelacja czasowa może w tym przypadku prowadzić do powiązania hasha hasła z IP użytkownika. Jeśli chcemy sprawdzać hasła, to lepszym rozwiązaniem jest stworzenie lokalnej kopii bazy którą pobierzemy z HIBP.

Co nie znaczy oczywiście, że k-anonimowość ogólnie nie spełnia swojego zadania. Po prostu mam wrażenie, że akurat w przypadku hashy hasła i tej konkretnej implementacji nie jest tak bezpieczna, jak jest to przedstawiane.

Warto też zauważyć, że hasło z którym mamy tu do czynienia jest proste/populare. Dla innych pięcioznakowych początków hashy wystąpienia mogą rozkładać się inaczej, bez tak silnego wskazania na konkretny hash.

UPDATE Tak naprawdę nie ma potrzeby używania całej bazy hashy i ilości ich wystąpień z HIBP (>20GB). Najczęściej występujące 100 tys. hashy to raptem 3,2 MB. Najczęstszy milion – 32 MB.