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ą, a ponieważ bawię się z bazą hashy z HIBP i planuję wkrótce wpis na ten temat, to 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, a 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 i 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 jeszcze samego hasła, a jedynie – ze sporym prawdopodobieństwem – jego hash, ale 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ć o hashe haseł moich użytkowników, których 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, a 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 lokalna kopia bazy hashy i ilości ich wystąpień pobrana 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 haseł i tej konkretnej implementacji nie jest tak bezpieczna, jak jest to przedstawiane.

Warto też zauważyć, że mamy tu do czynienia z dość prostym/popularnym hasłem i 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.

711 wyrazów o optymalizacji

Tytuł jest przekorny – raczej nie będzie to 711 wyrazów, ale liczba na początku tytułu dobrze wpływa na klikalność, a 711 jak najbardziej jest na miejscu, za to będzie o optymalizacji.

Mianowicie pojawił się pod koniec zeszłego roku Sekurak Book Simple CTF, gdzie było pewne zadanie. Jeśli chcesz pobawić się w zrobienie tego CTF samodzielnie, choć jest już zakończony[1], to dobry moment na przerwanie lektury wpisu. Zadanie jest na tyle proste i znane, że publikacja rozwiązania nie spowoduje krzywdy, a przy tym podczas dyskusji z kolegą z pracy pojawiły się ciekawe zagadnienia natury optymalizacyjnej, więc postanowiłem opisać.

Zmodyfikowana treść zadania, z zachowaniem pierwotnego sensu, pojawiła się – z moją niewielką pomocą – jako wpis zagadka o siódmej jedenaście na zaprzyjaźnionym blogu. Jeśli ktoś nie chce się bawić w całą CTFową otoczkę, a ma ochotę wytężyć mózg, zapraszam tamże. Tym bardziej, że jest więcej zagadek.

Całość daje się sprowadzić do układu dwóch równań z czterema niewiadomymi:
a + b + c + d = 7,11
a * b * c * d = 7,11
WolframAlpha – być może niewprawnie użyty – protestował Standard computation time exceeded, ale przecież to się da policzyć… W końcu chodzi o wartości nieciągłe, bo ceny muszą być wielokrotnością jednego grosza. Wiemy zatem, że każda z wartości jest większa od zera, mniejsza od 711 i jest wielokrotnością 0,01. Tu pauza – komputery znacznie lepiej radzą sobie z wartościami całkowitymi[2], więc przemnóżmy wartości przez 100 i przejdźmy w tym momencie na resztę czasu równoważną formę:
a + b + c + d = 711
a * b * c * d = 711000000

Przy naiwnym brute force, korzystając jedynie z faktu, że wszystkie zmienne muszą być liczbami całkowitymi, bez żadnych optymalizacji, mamy do sprawdzenia maksymalnie 711^4 kombinacji, czyli 225 miliardów. Można to zapisać w Pythonie w postaci:

limit = 712
iterations = 0
for a in range(1, limit):
    print(a)
    for b in range(1, limit):
        for c in range(1, limit):
            for d in range(1, limit):
                iterations += 1
                if a + b + c + d == 711:
                    if a * b * c * d == 711000000:
                        print("Solved: ", a, b, c, d, iterations)
                        exit()

Jak widać zliczam też ilość iteracji, i dzięki temu wiem, że komputer musi – w różnych pętlach – policzyć w sumie prawie do 43 miliardów, zanim znajdzie rozwiązanie. Czas znalezienia rozwiązania litościwe pominę – spokojnie można wybrać się na spacer czy zakupy.

Mamy jednak dwie dodatkowe własności: iloczyn czterech liczb oraz ich sumę. Jeśli ktoś bawił się w sprawdzanie, czy dana liczba jest pierwsza, to pamięta zapewne, jeśli liczba jest złożona, to mniejszy dzielnik będzie co najwyżej równy pierwiastkowi danej liczby. W naszym przypadku iloczyn dwóch niewiadomych będzie co najwyżej równy pierwiastkowi z 711000000, czyli 26665. Z kolei któraś z niewiadomych będzie mniejsza od pierwiastka z 26665, czyli nieco ponad 163. Można więc ograniczyć jedną ze zmiennych – oczywiście tę najczęściej używaną – do 163.
Dodatkowo, niewiele myśląc, można skorzystać z własności sumowania i ograniczyć pozostałe zmienne do 711-163=548, czyli zmniejszyć przeszukiwaną przestrzeń do niecałych 27 miliardów. Oblekając to w skrypt:

limit = 549
iterations = 0
for a in range(1, limit):
    print(a)
    for b in range(1, limit):
        for c in range(1, limit):
            for d in range(1, 164):
                iterations += 1
                if a + b + c + d == 711:
                    if a * b * c * d == 711000000:
                        print("Solved: ", a, b, c, d, iterations)
                        exit()

Czas potrzebny na rozwiązanie nadal pomijam, ale jest to raczej tyle, ile potrzeba na zrobienie kawy czy herbaty, niż zakupów. Ilość iteracji potrzebnych do znalezienia rozwiązania to niecałe 6 mld.

Jeśli nie pamiętamy o ciekawej własności związanej z dzielnikami danej liczby, to nadal możemy zoptymalizować pętle tak, żeby automatycznie uwzględniać w nich warunek związany z sumą – daną zmienną zwiększamy do wartości zależnej od wartości pozostałych zmiennych, dzięki czemu można zaobserwować, że w miarę wzrostu wartości zmiennej a sprawdzenia pozostałych są coraz szybsze.

limit = 712
iterations = 0
for a in range(1, limit):
    print(a)
    for b in range(1, limit - a):
        for c in range(1, limit - a - b):
            for d in range(1, limit - a - b - c):
                iterations += 1
                if a + b + c + d == 711:
                    if a * b * c * d == 711000000:
                        print("Solved: ", a, b, c, d, iterations)
                        exit()

Rozwiązanie jest znajdowane nawet nieco szybciej, niż w poprzednim przypadku – ok. 5,5 mld iteracji.

Tu pojawił się pomysł – a co gdyby zapisać to w taki sposób, by program działał na początku bardzo szybko i zwalniał? Czyli nie zaczynamy od niskich wartości zmiennych i zwiększamy, tylko zaczynamy od wysokich i zmniejszamy? Można to zapisać następująco:

limit = 711
iterations = 0
for a in range(limit, 0, -1):
    print(a)
    for b in range(limit - a, 0, -1):
        for c in range(limit - a - b, 0, -1):
            for d in range(limit - a - b - c, 0, -1):
                iterations += 1
                if a + b + c + d == 711:
                    if a * b * c * d == 711000000:
                        print("Solved: ", a, b, c, d, iterations)
                        exit()

Przyznaję, że efekty tego podejścia mnie zaskoczyły. Tylko 1 mld operacji potrzebnych do znalezienia rozwiązania. Na moim sprzęcie skrypt wykonał się poniżej 3 minut na Pythonie 3.8.3. Co ciekawe dla Pythona 2.7.18 był to czas poniżej 2 minut, więc znacznie szybciej. Oba z paczek z repo Debiana unstable. Ale to raczej tylko ciekawostka, Python 2 jest martwy.

Dochodzimy jednak do sedna. Widać, że interpreter Pythona ma znaczenie. Jeśli zależy nam na szybkości, to warto zainteresować się alternatywną implementacją Pythona, czyli projektem PyPy. PyPy w wersji 7.3.1 (kompatybilna z Pythonem 3.6.9) wykonuje powyższy program w… nieco ponad 3 sekundy. Czyli jakieś pięćdziesiąt razy szybciej. Jeśli wrócimy do rozwiązania drugiego, to okaże się, że z użyciem PyPy można je znaleźć w 17 sekund. Natomiast wersja naiwna to… raptem 2 minuty.

Jak widać, szybkie narzędzia mogą prowadzić do lenistwa umysłowego – skoro działa szybko, to po co optymalizować? Optymalizacja algorytmu w powyższych przykładach nie jest skończona, da się lepiej. Znacznie lepiej. Na razie zostawię pole do popisu czytelnikom w komentarzach, za jakiś tydzień zaktualizuję wpis.

[1] Jest to naprawdę prosty CTF, jeśli ktoś nie miał okazji się bawić – polecam przymierzyć.
[2] Jak mawiają: real programmers use integers.

Oddzwanianie

Zauważyłem nieodebrane połączenie na jednym z numerów telefonów. Zwykle nie oddzwaniam na nieznane numery, bo albo pomyłka, albo telemarketer, ale teraz miałem powód by przypuszczać, że kontakt był zasadny.

Rzut oka na numer – polska komórka, żadna zagranica. Szybkie sprawdzenie w sieci na portalach zajmujących się zbieraniem informacji o numerach – nienotowany, czyli prawdopodobnie nie telemarketer.

Dzwonię. Odbiera automat i informuje, że rozmowa jest nagrywana i że dane są przetwarzane zgodnie z zasadami opisanymi na stronie – tu adres, zawierający słowo RODO w domenie jednego z banków. Czyli wszystko w porządku! Albo… właśnie nie w porządku. Nie ma informacji, kto jest administratorem danych osobowych, nie ma informacji przez kogo jest przetwarzane, nie ma jednoznacznej informacji do kogo się dodzwoniłem. Zresztą, w przypadku oszustwa informacja o nagrywaniu rozmowy, dane dotyczące zawartości strony itp. będą zgodne z prawdą i służyć będą tylko wzbudzeniu zaufania.

Owszem, korzystam z usług tego banku. I mają w nim podany ten numer telefonu. Ale to jeszcze o niczym nie świadczy… Tego typu dane oszust może zdobyć z różnych miejsc w sieci albo… po prostu zgadywać numery i podawać się za któryś z popularnych banków. Jeśli bank ma powiedzmy 5% udziału w rynku, to mniej więcej dla takiego odsetka numerów będzie to wyglądało OK. Zapewne przytłaczająca większość błędnych adresatów po prostu zignoruje próbę kontaktu, uzna za pomyłkę, albo nie będzie wiedziała komu zgłosić taką „dziwną sytuację”[1].

Rozłączam, się. Wiem już, o który bank chodzi, znam numer telefonu. Szukam numeru na stronie banku i w wyszukiwarkach. Nie występuje. Nie wygląda to dobrze, więc zakładam roboczo próbę oszustwa i z takim nastawieniem dzwonię ponownie.

Odbiera osoba, która przedstawia się jako pracownik banku. Ja się nie przedstawiam, informuję tylko, że dzwonię, bo miałem nieodebrane połączenie. Moje pierwsze pytanie: jak mogę potwierdzić, że faktycznie jest pracownikiem banku i że to numer należący do banku. Jest nieco zaskoczona, ale podaje informacje, gdzie po zalogowaniu do banku znajdę jej dane i numer.

Proszę o chwilę cierpliwości. Loguję się do banku i sprawdzam w podanym miejscu. Faktycznie, dane się zgadzają. Dziękuję, przedstawiam się i kontynuujemy rozmowę.

Oczywiście dałem znać, czemu uznałem telefon/proces za podejrzany, ale nie bardzo wierzę w jego zmianę. Warto pamiętać, że jeśli sami nie nawiązujemy połączenia pod wybrany przez nas numer, np. wpisany ze strony internetowej instytucji, to nie mamy żadnej gwarancji, z kim rozmawiamy, więc uważajmy z podawaniem danych.

[1] Szczerze mówiąc, sam miałbym z tym problem – można próbować na infolinii instytucji, pod którą ktoś próbuje się podszyć, ale… różnie bywa ze zrozumieniem w czym problem.

Darmowy upgrade z Windows 7 do Windows 10

Microsoft zakończył support dla Windows 7 w dniu 14 stycznia 2020. Oznacza to brak aktualizacji, w tym brak poprawek bezpieczeństwa. W idealnym świecie systemy z Windows 7 powinny zniknąć, jako przestarzałe.

W 2016 Microsoft przeprowadzał kampanię promującą darmową aktualizację do Windows 10. Oficjalnie kampania została zakończona, ale mechanizm nadal działa, co oznacza, że technicznie nadal można zaktualizować Windows 7 do Windows 10.

Aby dokonać aktualizacji, wymagany jest oryginalny Windows 7 lub 8 z aktywowaną licencją. Wystarczy pobrać narzędzie ze strony Microsoftu i uruchomić je. Istnieje możliwość stworzenia nośnika, albo aktualizacji bieżącej instalacji, i ta ostatnia możliwość jest najbardziej interesująca. Upgrade’u można dokonać dla dowolnego wariantu systemu (szczegóły w źródle).
Oczywiście przed tak poważną operacją warto zrobić kopię bezpieczeństwa. Na pewno danych, ale na wypadek, gdyby coś poszło źle, warto zrobić także backup systemu, na przykład obraz dysku.

Systemy bez aktualizacji bezpieczeństwa stanowią zagrożenie zarówno dla swoich użytkowników, gdyż może dojść do infekcji i wycieku danych, jak również innych komputerów w sieci, stając się po infekcji częścią botnetu i uczestnicząc w atakach. Z punktu widzenia bezpieczeństwa sprawa jest prosta – trzeba aktualizować.

Czy operacja jest legalna? Nie jestem prawnikiem. Za przemawia fakt, że sam producent udostępnia mechanizm i oferuje możliwość aktualizacji, była nawet specjalna kampania promująca taki upgrade, a system nie różni się od takiego aktualizowanego w roku 2016.

Źródło: https://www.zdnet.com/article/heres-how-you-can-still-get-a-free-windows-10-upgrade/

Instalacja podatnych wersji oprogramowania HOWTO

Niekiedy zachodzi potrzeba uruchomienia starej, podatnej wersji systemu lub usługi w celu przetestowania czegoś, np. exploita. W przypadku Debiana i podobnych dystrybucji opartych na pakietach deb, instalacja starej wersji systemu bywa nieco problematyczna, ponieważ po pierwsze system pakietów nie wspiera downgrade’u, po drugie, domyślnie instalator instaluje najnowsze wersje pakietów, jeśli tylko ma taką możliwość.

Sposobów na instalację starszych wersji pakietów jest wiele. Można kompilować określoną wersję, ale nie jest to wygodne, jest czasochłonne i niekoniecznie uzyskamy wersję dokładnie taką, jaka była w systemie, np. z powodu patchy nakładanych przez Debiana czy nieco innego środowiska w którym pakiet był budowany[1].

Skoro jednak korzystamy z dystrybucji opartej o pakiety binarne, można także próbować robić downgrade pakietów, albo usuwać pakiety i instalować przy pomocy dpkg zamiast apt[2]. Jeśli nie mamy pecha, wszystko zadziała czy to od razu, czy po małym force przy instalacji. Można też instalować ze starych obrazów instalacyjnych, bez dostępu do sieci. Czasem jednak nie mamy szczęścia. A wszystko można zrobić szybciej i prościej.

Przede wszystkim, i tak trzeba jakoś zdobyć podatne wersje pakietów. W przypadku Debiana istnieje snapshot.debian.org, czyli serwis z oficjalnymi, snapshotami mirrorami repozytoriów Debiana. Doskonałe miejsce pozwalające i na pobranie pakietów w takich wersjach, w jakich były w danym momencie w repo, i na postawienie całego systemu w stanie na dany dzień. Snapshoty wykonywane są częściej, niż raz dziennie, poza głównym repozytorium pakietów dostępne inne, w tym security i backports, więc trudno sobie wyobrazić coś lepszego. Pozostaje instalacja systemu z wykorzystaniem powyższych repozytoriów.

Naprościej można to zrobić z użyciem debootstrap, poprzez podanie mirrora., z którego mają być pobierane pakiety. Przykładowo, aby zainstalować Debiana Buster w wersji, w jakiej był on dostępny dzień po wydaniu:

debootstrap buster /chrooted/ https://snapshot.debian.org/archive/debian/20190707T150059Z/

Po instalacji należałoby jeszcze wejść do chroota i uzupełnić sources.list o wpisy dla repozytorium security, zaktulizować pakiety i… gotowe. W katalogu /chrooted będzie dostępny podatny system. Jeśli był tam podmontowany dysk zdalny, to można uruchomić podatną maszynę według podlinkowanej wyżej instrukcji.

Istnieje jeszcze szybszy i IMO wygodniejszy sposób uruchomienia podatnej wersji systemu – można wykorzystać kontenery LXC do instalacji, a następnie uruchomienia podatnego systemu. O tyle wygodne i bezpieczne, że kontener LXC może być dostępny – i jest to domyślna konfiguracja – wyłącznie z poziomu hypervisora, bez udostępniania go na świat. Kontener z Debianem Buster w wersji na dzień po wydaniu z użyciem LXC tworzymy:

lxc-create -n test -t debian -- -r buster -a amd64 --mirror=https://snapshot.debian.org/archive/debian/20190707T150059Z/ --security-mirror=https://snapshot.debian.org/archive/debian-security/20190707T153344Z/

I gotowe. Po zakończeniu powinniśmy mieć dostępny kontener LXC z podatną wersją systemu o nazwie test, którym możemy zarządzać w standardowy sposób. W sources.list będziemy mieli:

cat /etc/apt/sources.list
deb https://snapshot.debian.org/archive/debian/20190707T150059Z/          buster         main
deb https://snapshot.debian.org/archive/debian-security/20190707T153344Z/ buster/updates main

[1] W weryfikacji zgodności pakietów pomóc mogą reproducible builds.
[2] W tym miejscu nadal odsyłam do wpisu o wajig i zachęcam do zapoznania się z narzędziem. To stary wpis, nie wszystkie opisane okoliczności muszą być prawdziwe, ale nadal wajig działa i ma ciekawe opcje, więc warto go znać.