Kiedy złożoność staje się podatnością: HashDoS, ReDoS i inne ataki na algorytmy

W serii o algorytmach sortowania wracał jeden wątek: przypadek średni to nie to samo, co pesymistyczny. Quicksort ma O(n log n) średnio i O(n²) na złośliwie dobranych danych; tablica mieszająca daje dostęp w czasie stałym, dopóki klucze nie zderzą się w jednym kubełku. W podręczniku to jest przypis. W aplikacji wystawionej do internetu to jest powierzchnia ataku – bo o tym, jakie dane trafią do algorytmu, decyduje ktoś inny niż ty.

Ataki przez złożoność obliczeniową (algorithmic complexity attacks) mają jedną wspólną cechę, która czyni je groźnymi: skrajną asymetrię kosztów. Atakujący wysyła kilkadziesiąt kilobajtów, serwer liczy przez kilka sekund. Nie trzeba botnetu ani łącza – wystarczy zrozumieć, jaki algorytm siedzi pod spodem i podać mu jego najgorszy przypadek.

HashDoS: kilka tysięcy kluczy, które lądują w jednym kubełku

Tablica mieszająca zamienia klucz na indeks kubełka i dlatego znajduje wartość w czasie stałym. Gdy dwa klucze trafią w ten sam kubełek, implementacja odkłada je na liście i przy każdym kolejnym wstawieniu musi tę listę przejrzeć. Jeśli wszystkie klucze wpadną do jednego kubełka, wstawienie n elementów kosztuje nie O(n), tylko O(n²).

Do wywołania takiego stanu nie potrzeba szczęścia – wystarczy znać funkcję skrótu. Klasyczny przykład to skrót napisów z Javy, mnożący kolejne znaki przez 31: napisy "Aa" i "BB" mają identyczny skrót (2112). A skoro tak, to każde ich sklejenie też: "AaAa", "AaBB", "BBAa", "BBBB" – wszystkie cztery są nie do odróżnienia dla tablicy. Z ośmiu takich klocków dostajesz 256 różnych kluczy o jednym skrócie, z szesnastu – 65 536.

# Python
def java_string_hash(text):
    """Skrót napisu z Javy: h = 31*h + znak. Wystarczy do pokazania kolizji."""
    h = 0
    for ch in text:
        h = (31 * h + ord(ch)) & 0xFFFFFFFF
    return h - 0x100000000 if h > 0x7FFFFFFF else h

java_string_hash("Aa")      # 2112
java_string_hash("BB")      # 2112

import itertools
keys = ["".join(p) for p in itertools.product(["Aa", "BB"], repeat=8)]
len(keys)                                     # 256 różnych kluczy
len({java_string_hash(k) for k in keys})      # ...i dokładnie 1 skrót

Policzmy, ile to kosztuje. Poniżej naiwna tablica mieszająca z łańcuchami kolizji – dokładnie taka, jaką miały wszystkie popularne platformy przed 2012 rokiem – licząca porównania kluczy przy wstawianiu:

# Python
class NaiveTable:
    """Tablica mieszająca z łańcuchami; liczy porównania kluczy przy wstawianiu."""

    def __init__(self, size=1024):
        self.buckets = [[] for _ in range(size)]
        self.comparisons = 0

    def put(self, key, value):
        bucket = self.buckets[java_string_hash(key) % len(self.buckets)]
        for i, (existing, _) in enumerate(bucket):
            self.comparisons += 1          # cała praca dzieje się tutaj
            if existing == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

Wynik dla kluczy kolizyjnych i dla zwykłych (key0, key1, …):

Kolumna z kolizjami to dokładnie n(n−1)/2 – ta sama liczba, którą sortowanie bąbelkowe pokazało w pierwszej części cyklu o sortowaniu. Podwojenie liczby kluczy czterokrotnie zwiększa pracę.

A teraz najważniejsze: do tej tablicy trafiają parametry żądania HTTP. Formularz POST z kilkoma tysiącami pól to zwykłe, poprawne żądanie – serwer musi je sparsować, zanim jakikolwiek twój kod się uruchomi.

Jak się przed tym broni

Odpowiedzi na HashDoS są trzy i warto znać wszystkie, bo pokazują trzy różne szkoły myślenia:

1. Limit wejścia. PHP dorzuciło dyrektywę max_input_vars (domyślnie 1000), która ucina liczbę przyjmowanych zmiennych $_GET, $_POST i $_COOKIE. Dokumentacja mówi wprost, że służy to ograniczeniu ataków opartych na kolizjach. To obrona tania i skuteczna, ale tylko dla tego jednego wejścia.
2. Losowość, której atakujący nie zna. Skoro atak wymaga znajomości funkcji skrótu, wystarczy dodać do niej sekret losowany przy starcie procesu. Python poszedł tą drogą (PYTHONHASHSEED), ale pierwsza wersja – losowy prefiks i sufiks doklejony do funkcji FNV – okazała się za słaba: jak tłumaczy PEP 456, „ponieważ FNV nie jest kryptograficzną funkcją skrótu (…), sekrety randomizacji mogą zostać wyliczone przez zdalnego atakującego”. Dlatego od Pythona 3.4 skróty napisów liczy SipHash – funkcja zaprojektowana dokładnie do tego zastosowania, używana dziś także przez Rusta, Ruby’ego, Perla i Redisa.
3. Algorytm z gwarancją w pesymistycznym przypadku. Java 8 poszła najdalej: gdy w jednym kubełku zbierze się osiem wpisów (przy tablicy o co najmniej 64 kubełkach), HashMap zamienia listę na drzewo czerwono-czarne. Kolizje przestają kosztować O(n), a zaczynają O(log n) – atak nie znika, ale przestaje być opłacalny.

Trzecia droga jest najciekawsza, bo to dokładnie ten sam ruch, który biblioteki wykonały przy sortowaniu: skoro istnieje wejście, na którym algorytm się załamuje, wbudujmy w niego plan awaryjny. IntroSort robi to samo z quicksortem – o czym za chwilę.

ReDoS: wyrażenie regularne, które liczy wykładniczo

Silniki wyrażeń regularnych w większości języków (Python, JavaScript, PHP, Java, .NET) działają na zasadzie nawrotów: próbują dopasowania, a gdy się nie uda, cofają się i próbują inaczej. Przy zagnieżdżonych kwantyfikatorach liczba kombinacji do sprawdzenia rośnie wykładniczo.

Klasyczny przykład to ^(a+)+$ skonfrontowany z ciągiem samych a zakończonym znakiem, który psuje dopasowanie. Pomiary z mojej maszyny:

Każde cztery dodatkowe znaki mnożą czas przez ~16. Przy 40 znakach mówimy o godzinach – a wejście dalej mieści się w jednym polu formularza.

# Python
import re, time

pattern = re.compile(r"^(a+)+$")
text = "a" * 26 + "!"          # 27 znaków wystarczy, żeby zająć rdzeń na sekundy

start = time.perf_counter()
pattern.search(text)
print(time.perf_counter() - start)     # ~1,7 s

To nie jest problem teoretyczny ani niszowy. 2 lipca 2019 roku globalna awaria Cloudflare trwała 27 minut i była spowodowana jedną regułą WAF-u zawierającą fragment .*(?:.*=.*) – wzorzec z tak zwanym katastrofalnym nawrotem. Firma opisała to szczegółowo w publicznej analizie powypadkowej i zapowiedziała przejście na silniki z gwarancją czasu wykonania: RE2 albo regex z Rusta.

Obrona jest tu wyjątkowo konkretna:

• Silnik bez nawrotów. RE2 (Go, C++), silnik regex w Ruście czy re2 w Pythonie działają w czasie liniowym względem długości wejścia, kosztem rezygnacji z kilku egzotycznych konstrukcji (wsteczne referencje, lookbehind).
• Grupy atomowe i kwantyfikatory zachłanne bez oddawania. Od Pythona 3.11 możesz napisać (?>a+)+ albo a++ – silnik nie wraca do już dopasowanego fragmentu i wykładniczy wybuch znika. We wcześniejszych wersjach ta składnia po prostu nie istnieje (re.error: unknown extension ?>).
• Limit długości wejścia przed dotknięciem go wyrażeniem regularnym – zwykle najtańsza i najskuteczniejsza linia obrony.
• Timeout na dopasowanie, jeśli platforma go oferuje (.NET ma go od dawna w konstruktorze Regex).
• Nie kompiluj wzorców pochodzących od użytkownika. Regex jako parametr wyszukiwarki to zaproszenie do ataku.

Sortowanie jako broń

W części drugiej cyklu o sortowaniu pokazywałem quicksort, który na tablicy odwróconej wykonuje 1128 porównań zamiast około 300 – bo każdy podział jest maksymalnie nierówny. Jeśli sortowana tablica pochodzi od użytkownika (wyniki wyszukiwania, pozycje koszyka, dane z importowanego pliku), to ktoś może ją dobrać celowo.

Trzy algorytmy, ta sama tablica odwrócona: czysty quicksort – 1128 porównań, IntroSort – 682, TimSort – 47. Różnica nie bierze się z lepszej implementacji, tylko z tego, że dwa ostatnie mają plan na najgorszy przypadek: IntroSort przełącza się na kopcowanie, gdy rekurencja robi się za głęboka, a TimSort rozpoznaje, że dane są jedną malejącą serią. Obu przyglądam się dokładniej w czwartej części cyklu, razem z tym, który z nich siedzi w twoim języku.

Co gorsza, sam dobór „złego” wejścia nie wymaga znajomości implementacji. Douglas McIlroy pokazał w pracy A Killer Adversary for Quicksort (1999), że wystarczy podstawić własną funkcję porównującą, która odpowiada na pytania algorytmu w locie tak, by każdy podział był pesymistyczny – i dowolna implementacja quicksorta zwalnia do kwadratu, nawet jeśli losuje pivota. Jeśli twój kod przyjmuje komparator z zewnątrz (a przyjmuje, jeśli sortuje obiekty domenowe po polu wskazanym przez użytkownika), to jest realne ryzyko.

Bomby: małe wejście, ogromne wyjście

Ostatnia rodzina to ataki, w których kosztowna nie jest złożoność algorytmu, tylko współczynnik rozprężenia danych:

• Bomba dekompresyjna. Słynny plik 42.zip waży 42 kilobajty i rozpakowuje się (rekurencyjnie) do 4,5 petabajta. Każdy serwis przyjmujący archiwa – poczta, antywirus, import danych – musi mieć limit rozmiaru po dekompresji, a nie tylko przed.
• Billion laughs. Dokument XML definiujący dziesięć encji, z których każda odwołuje się dziesięć razy do poprzedniej, rozwija się do miliarda znaków z kilkuset bajtów. Obrona: wyłączyć rozwijanie encji zewnętrznych w parserze (to ta sama opcja, która chroni przed XXE).
• Głębokie zagnieżdżenie JSON. Parser rekurencyjny dostaje [[[[[...]]]]] i kończy się przepełnieniem stosu. Obrona: limit głębokości (w PHP json_decode ma go w parametrze, domyślnie 512).

Wspólny wzorzec

Wszystkie te ataki mają identyczną strukturę: istnieje wejście, dla którego koszt po stronie serwera jest o rzędy wielkości wyższy niż koszt po stronie atakującego. Nie ma tu przepełnienia bufora, wstrzyknięcia ani wycieku danych – z punktu widzenia aplikacji wszystko działa poprawnie, tylko wolno.

Lista obron, które faktycznie zamykają temat:

1. Projektuj według przypadku pesymistycznego, nie średniego. Pytanie brzmi nie „ile to zwykle kosztuje”, tylko „ile to kosztuje, gdy ktoś się postara”.
2. Limituj wszystko, co kontroluje użytkownik: liczbę pól formularza, długość napisów, głębokość zagnieżdżenia, rozmiar po dekompresji, liczbę elementów do posortowania.
3. Sekrety, których atakujący nie widzi – losowe ziarno skrótu na proces. Ale uwaga: to działa tylko wtedy, gdy wynik funkcji skrótu nie wycieka na zewnątrz.
4. Wybieraj algorytmy z gwarancją, nie tylko z dobrą średnią: IntroSort zamiast czystego quicksorta, RE2 zamiast silnika z nawrotami, drzewo zamiast listy w kubełku.
5. Timeout i budżet CPU na żądanie. Jeśli obsługa jednego żądania przekracza sekundę, coś jest nie tak – niech to będzie błąd, a nie zajęty rdzeń.
6. Testuj najgorszy przypadek, nie tylko szczęśliwą ścieżkę. Fuzzing i testy własnościowe znajdują dokładnie te wejścia, których nie wymyślisz przy biurku.

Notacja O nie jest więc tylko narzędziem do porównywania algorytmów w podręczniku. To także sposób, żeby zobaczyć, gdzie w twojej aplikacji ktoś obcy może wybrać wejście – i ile go to będzie kosztowało. Bezpieczeństwo to nie tylko wstrzyknięcia SQL i XSS; czasem podatnością jest po prostu pętla, która wykonuje się o jeden rząd wielkości za wolno.