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.

Aktualizacje macOS

Pierwszą aktualizacją macOS, którą robiłem, była ta między „dużymi” wersjami, do wersji Catalina. Wtedy byłem umiarkowanie zadowolony, bo to duża aktualizacja. I pierwsza. I się udała. Od tego czasu miałem parę razy okazję aktualizować system między „małymi” wersjami i… wyrobiłem sobie zdanie.

Źródło: http://www.highstreetcomputers.com/apple-logo-broken/

Aktualizacje systemu w macOS to porażka, generalnie. „Duże” może nie są najgorsze, ale „małe” są tragiczne. Spójrzmy na listę aktualizacji Cataliny na Wikipedii, linkującą do opisu aktualizacji na stronach Apple. Od końca października 2019 do lipca 2020 było sześć aktualizacji. Każda to przynajmniej 3 GB do pobrania i blisko godzina stracona na aktualizację.

No właśnie, jeśli ktoś zastanawia się, o co mi w ogóle chodzi i czy da się system aktualizować lepiej, to szybko nakreślę jak wygląda proces aktualizacji w Linuksie. Otóż sprowadza się do pobrania pakietów i wykonania restartu. Cały czas można pracować na komputerze. Restart i okoliczne czynności nie trwają pół godziny, to zwykły reboot, jak każdy inny, czyli pewnie minuta. Aktualizowany jest zarówno kernel, kluczowe pakiety, jak i pakiety opcjonalne. Nie trzeba pobierać 3 GB, ale to już detal. Chodzi głównie o brak przerwy w możliwości korzystania z komputera.

No właśnie, gdy pisałem o aktualizacji do Cataliny i porównywałem jej czas z aktualizacją Debiana, popełniłem błąd. Porównywałem jabłka z gruszkami – w przypadku macOS brałem pod uwagę czas aktualizacji samego systemu, czyli podstawki, a w przypadku Linuksa systemu i wszystkich dodatkowych aplikacji będących w repozytoriach, a trochę tego jest (LibreOffice, Firefox, Chromium). Nie jest to aż tak ważne, bo to, czy pobieranie trwa pół godziny, czy godzinę nie ma większego znaczenia, jeśli można korzystać z systemu. Kluczowy jest czas niedostępności komputera.

Tyle o aktualizacjach systemu w makach, dopóki coś się diametralnie nie zmieni albo nie wybuchnie przy upgrade, nie będę wracał do tego smutnego tematu.

LXDE, laptop, jasność i głośność – HOWTO

Jest taka rzecz w laptopach z Linuksem, która często nie działa zaraz po instalacji. Przynajmniej nie na środowiskach korzystających z Openbox, np. LXDE. Chodzi o sterowanie jasnością ekranu oraz głośnością dźwięku.

Nie pamiętam, czy coś się ostatnio zmieniło, czy zawsze tak było, tylko miałem skonfigurowane, ale ostatnio konfigurowałem laptopa z LXDE i jak wszystko działało, tak sterowanie głośnością i jasnością ekranu – nie. Wydaje mi się, że kiedyś obsługa dodatkowych klawiszy była robiona przez ACPI i skrypty (zob. linki na końcu wpisu), ale teraz można prościej.

W obu przypadkach wykorzystywany będzie plik ~/.config/openbox/lxde-rc.xml.

Jasność

Na początek kontrola jasności. W przypadku karty intela, bo taką miałem, kontrola jasności odbywa się z wykorzystaniem programu xbacklight, który musiałem doinstalować. Rozwiązanie powinno działać także dla innych kart. Dodatkowo musiałem utworzyć plik /etc/X11/xorg.conf.d/20-intel.conf o następującej zawartości:

Section "Device"
    Identifier "Intel Graphics"
    Driver "intel"
    Option "Backlight" "intel_backlight"
EndSection

W pliku XML zaś dodałem:

<keybind key="XF86MonBrightnessDown">
  <action name="Execute">
    <command>xbacklight -5</command>
    <startupnotify>
      <enabled>yes</enabled>
      <name>Decrease screen brightness</name>
    </startupnotify>
  </action>
</keybind>
<keybind key="XF86MonBrightnessUp">
  <action name="Execute">
    <command>xbacklight +5</command>
    <startupnotify>
       <enabled>yes</enabled>
       <name>Increase screen brightness</name>
    </startupnotify>
  </action>
</keybind>

Głośność

Trzeba oczywiście mieć zainstalowane programy, które będziemy wykorzystywać – w przypadku instalacji pełnego środowiska LXDE i Debiana 10 wszystko już było zainstalowane. Natomiast w pliku konfiguracyjnym XML wystarczy dodać:

  <keybind key="XF86AudioRaiseVolume">
    <action name="Execute">
      <execute>pactl set-sink-volume 0 +10%</execute>
    </action>
  </keybind>
  <keybind key="XF86AudioLowerVolume">
    <action name="Execute">
      <execute>pactl set-sink-volume 0 -10%</execute>
    </action>
  </keybind>
  <keybind key="XF86AudioMute">
    <action name="Execute">
      <execute>pactl set-sink-mute 0 toggle</execute>
    </action>
  </keybind>

Istnieją warianty wykorzystujące inne polecania pamixer czy amixer (zob. linki).

Oczywiście w ten sposób można zmieniać zachowanie dowolnych skrótów i wykorzystywać dowolne klawisze, nie tylko te wymienione. Pełna lista w źródłach (zob. linki)

Linki:

UPDATE: Skoro już konfigurujemy, warto też pod Print Screen dodać robienie screenshotów. Podobno jest domyślnie, nie potwierdzam, ale może „zasługa” unstable.

    <keybind key="Print">
      <action name="Execute">
        <command>gnome-screenshot -i</command>
      </action>
    </keybind>

711 wyrazów o optymalizacji – część 3

Była część pierwsza i część druga, pora na kolejną, niezupełnie planowaną. Jak pamiętamy w części drugiej udało się ograniczyć sprawdzane liczby do 49 sztuk. To, co chodziło mi od czasu do czasu po głowie to pytanie, czy da się rozwiązać tę zagadkę „na piechotę”, bez użycia komputera?

Rozejrzałem się za możliwymi uproszczeniami i zauważyłem kolejne potencjalne pole do zmniejszenia liczby obliczeń. Jak wiadomo, 711 jest liczbą nieparzystą. Aby suma dwóch liczb była nieparzysta, jedna z nich musi być parzysta, druga nieparzysta. Z kolei aby suma dwóch liczb była parzysta, albo obie muszą być parzyste, albo nieparzyste. Tu mamy do czynienia z sumą czterech liczb, więc są dwa przypadki: albo 1 liczba jest nieparzysta, a 3 parzyste, albo odwrotnie.

Z naszych 49 liczb, 37 jest parzystych, a 12 nieparzystych. Jak to wpływa na przestrzeń rozwiązań? Z 49^4, czyli ok. 5,8 mln przechodzimy na 12*37^3 + 37*12^3 czyli ok. 672 tys. Nadal trochę dużo jak na ręczne liczenie, ale jak to wpłynie na czas obliczeń? Nasz skrypt będzie miał postać:

number = 711
iterations = 0
divs_odd = list()
divs_even = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        if i % 2 == 0:
            divs_even.append(i)
        else:
            divs_odd.append(i)

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

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

Niezależnie od kolejności bloków (najpierw 1 liczba parzysta i 3 nieparzyste, co jest teoretycznie korzystniejszym wariantem, czy odwrotnie), potrzebować będziemy poniżej 95 tys. iteracji. Czas to 0,08 sekundy dla zwykłego interpretera Pythona lub 0,12 sekundy dla Pypy.

Możliwa jest też wersja „w dół”:

number = 711
iterations = 0
divs_odd = list()
divs_even = list()
for i in range(1, round(number/2) + 1):
    iterations += 1
    if 711000000 % i == 0:
        if i % 2 == 0:
            divs_even.append(i)
        else:
            divs_odd.append(i)

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

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

Ilość potrzebnych iteracji waha się od 18 do 28 tys. w zależności od kolejności bloków, a czas wykonania to 0,06 sekundy dla zwykłego interpretera Pythona i 0,1 sekundy dla Pypy.

Nadal nie jest to wersja do policzenia ręcznie, ale… coraz bliżej.