Ataki padding oracle w szczegółach

W trybie CBC (Cipher Block Chaining) deszyfrowanie każdego bloku obejmuje odszyfrowanie bloku szyfrogramu za pomocą szyfru blokowego, a następnie wykonanie operacji XOR z poprzednim blokiem szyfrogramu. Ta operacja XOR ma krytyczną właściwość: modyfikując bity w bloku szyfrogramu, napastnik może w przewidywalny sposób wpłynąć na konkretne bity odszyfrowanego tekstu jawnego w następnym bloku. Właściwość ta umożliwia atak typu padding oracle.

Szyfry blokowe wymagają danych wejściowych podzielonych na bloki o stałym rozmiarze. Dopełnienie PKCS#7 wypełnia ostatni blok: jeśli potrzebne są 3 bajty dopełnienia, dodaje się trzy bajty, z których każdy ma wartość 0x03. Jeśli blok jest już pełny, dodaje się cały blok dopełnienia, w którym wszystkie 16 bajtów ma wartość 0x10. Podczas deszyfrowania sprawdza się, czy bajty dopełnienia są spójne (wszystkie N bajtów ma wartość N), a następnie się je usuwa. Jeśli dopełnienie jest nieprawidłowe, deszyfrowanie powinno zakończyć się błędem.

Wyrocznia dopełnienia (padding oracle) to dowolny system, który ujawnia, czy odszyfrowany szyfrogram zawiera prawidłowe dopełnienie PKCS#7. Wyrocznią może być: jawny komunikat o błędzie (Nieprawidłowe dopełnienie), inny kod statusu HTTP (500 zamiast 403), inna treść odpowiedzi z błędem, a nawet różnica w czasie wykonania (deszyfrowanie z prawidłowym dopełnieniem jest nieco szybsze). Napastnik nie musi znać klucza — potrzebuje jedynie tego sygnału binarnego: dopełnienie jest prawidłowe albo nie.

Napastnik wybiera konkretny blok szyfrogramu. Aby odzyskać ostatni bajt tekstu jawnego, zmienia ostatni bajt poprzedniego bloku szyfrogramu i wysyła zmodyfikowany szyfrogram do wyroczni. Następnie sprawdza kolejno 256 możliwych wartości, aż wyrocznia zgłosi prawidłowe dopełnienie. Dla wartości, która daje prawidłowe dopełnienie (0x01), znana jest pośrednia wartość deszyfrowania (po wykonaniu z nią operacji XOR ze zmodyfikowanym bajtem otrzymujemy 0x01). Wykonanie operacji XOR z pierwotnym bajtem szyfrogramu ujawnia bajt tekstu jawnego.

Po odzyskaniu ostatniego bajtu celem staje się przedostatni bajt. Pośrednia wartość ostatniego bajtu jest już znana, więc można wymusić wartość 0x02. Następnie sprawdza się 256 wartości dla przedostatniego bajtu, aż dopełnienie 0x02 0x02 zostanie uznane za prawidłowe. Proces ten powtarza się dla każdego bajtu, odzyskując kompletny blok 16-bajtowy przy średniej liczbie 256 * 16 = 4 096 zapytań do wyroczni na blok. Przy szybkiej wyroczni można zakończyć ten proces w kilka sekund.

Proces jest powtarzany dla każdego bloku szyfrogramu (z wyjątkiem IV, którego nie można odzyskać bez poprzedniego bloku). Szyfrogram o długości 128 bajtów (8 bloków AES) wymaga średnio około 32 000 zapytań do wyroczni, aby w pełni go odszyfrować. W przypadku serwera internetowego obsługującego setki żądań na sekundę zajmuje to kilka minut. Atakujący odzyskuje cały tekst jawny, nie poznając ani razu klucza szyfrującego.

POODLE (Padding Oracle On Downgraded Legacy Encryption) wykorzystywał walidację dopełnienia CBC w SSL 3.0. SSL 3.0 używał schematu dopełnienia innego niż PKCS#7, ale atak dostosowywał koncepcję wyroczni. Atakujący, który mógł wstrzykiwać treści do sesji SSL 3.0 i zmusić klientów do obniżenia wersji do SSL 3.0, mógł odzyskać pliki cookie sesji za pomocą techniki wyroczni dopełnienia. POODLE doprowadził do wycofania SSL 3.0.

Lucky Thirteen (2013) wykorzystywał kanał boczny oparty na czasie w schemacie MAC-then-encrypt CBC protokołu TLS. Czas weryfikacji MAC różnił się o kilka nanosekund w zależności od tego, czy dopełnienie było prawidłowe, tworząc wyrocznię czasową. BEAST (2011) wykorzystywał przewidywalny IV w trybie CBC TLS 1.0 do przeprowadzenia ataku z wybranym tekstem jawnym na pliki cookie sesji. Oba ataki pokazały, że prawidłowa implementacja trybu CBC w TLS jest zasadniczo trudna.

Ostateczną ochroną przed atakami z wyrocznią dopełnienia jest używanie trybów AEAD (Authenticated Encryption with Associated Data) zamiast CBC. Tryby AEAD, takie jak AES-256-GCM i ChaCha20-Poly1305, weryfikują uwierzytelnienie przed wykonaniem jakiegokolwiek odszyfrowywania lub sprawdzenia dopełnienia. Jeśli tag uwierzytelniający jest nieprawidłowy, odszyfrowywanie nie następuje i nie wycieka żadna informacja o dopełnieniu. TLS 1.3 wymaga AEAD i całkowicie usuwa CBC.

Jeśli AEAD nie jest dostępne, konstrukcja Encrypt-then-MAC dodaje MAC obliczany dla szyfrogramu, a nie dla tekstu jawnego. Przed odszyfrowaniem lub sprawdzeniem dopełnienia weryfikowany jest MAC. Jeśli MAC jest nieprawidłowy, operacja zostaje natychmiast przerwana bez ujawniania jakichkolwiek informacji o dopełnieniu. Należy wykonać to w czasie stałym, aby zapobiec wyroczniom czasowym. Niepowodzenie weryfikacji MAC nie ujawnia niczego na temat tego, czy dopełnienie byłoby prawidłowe.

Aby przetestować podatność na ataki z wyrocznią dopełnienia, należy zaszyfrować znaną wiadomość, a następnie przesłać do aplikacji zmodyfikowany szyfrogram i obserwować odpowiedź. Jeśli prawidłowe i nieprawidłowe dopełnienie powodują zauważalnie różne odpowiedzi (komunikat błędu, kod statusu lub czas odpowiedzi), istnieje wyrocznia dopełnienia. Narzędzia automatyczne, takie jak padbuster i PadBuster, służą właśnie do testowania wyroczni dopełnienia w aplikacjach internetowych. Systematycznie modyfikują szyfrogramy i analizują odpowiedzi.

Czego system docelowy musi dostarczać, aby atak z wyrocznią dopełnienia umożliwił odszyfrowanie szyfrogramu bez znajomości klucza?

Podsumowanie ataku z wyrocznią dopełnienia: właściwość XOR deszyfrowania CBC umożliwia kontrolowaną modyfikację tekstu jawnego, walidacja dopełnienia PKCS#7 ujawnia binarną wyrocznię, a atakujący iteruje po wartościach bajtów i obserwuje prawidłowe lub nieprawidłowe odpowiedzi, aby odzyskać tekst jawny bajt po bajcie. Do rzeczywistych exploitów należą POODLE, Lucky Thirteen i BEAST. Ochrona polega na przejściu na AEAD (GCM, ChaCha20-Poly1305), które weryfikuje uwierzytelnienie przed odszyfrowaniem.