Zabawy z padding oracle

Chciałbym zaznaczyć, że atak typu padding oracle nie ma nic wspólnego z bazą danych Oracle. W kryptografii wyrocznia (ang. oracle) to urządzenie (funkcja), która wykona proces deszyfrowania i zwróci pewne informacje.

W przypadku opisywanego ataku, padding oracle pobierze od atakującego szyfrogram, odszyfruje go i zwróci informację, czy padding był poprawny (choć na ogół zwraca informacje o błędzie, co oznacza, że padding był niepoprawny).

W tym artykule postaram się pokazać, jak przeprowadzić taki atak, ale najpierw…

Trochę teorii

1. PKCS#7 Padding

Szyfry blokowe, takie jak AES czy 3DES, wymagają na wejściu tekstu jawnego o długości, która jest wielokrotnością wielkości bloku. Najczęściej długość tekstu jawnego nie spełnia tego warunku, więc należy dopisać „coś” na końcu, aby warunek ten spełnić. To „coś”, to właśnie padding. Wszystkie znane mi szyfry blokowe do konstruowania paddingu używają PKCS#7. W PKCS7 wartość każdego bajtu dodanego na końcu tekstu jawnego ma wartość równą liczbie dodanych bajtów.

2. Alternatywa wykluczająca

Cytując Wikipedię: alternatywa wykluczająca to logiczny funktor zdaniotwórczy. W naszym rozumieniu alternatywa wykluczająca, czyli operacja xor, to operacja na bitach zdefiniowana następująco:

Warto również przypomnieć parę własności operacji xor wynikających bezpośrednio z definicji, które wykorzystamy w dalszej części:

Powyżej opisałem, jak działa xor na bitach. Działanie xor na bajtach, to wykonanie xor na poszczególnych bitach tych bajtów, a działanie xor na łańcuchach znaków, to po prostu wykonanie xor na poszczególnych bajtach tych łańcuchów (oczywiście długości tych łańcuchów muszą być równe).

3. Tryb wiązania bloków zaszyfrowanych (ang. Cipher Block Chaining – CBC)

Ponownie cytując Wikipedię: CBC to jeden z trybów pracy szyfrów blokowych wykorzystujący sprzężenie zwrotne, samosynchronizujący się. A po polsku: podczas szyfrowania w tym trybie pierwszy blok tekstu jawnego jest poddawany działaniu alternatywy wykluczającej (lub mniej po polsku xorowany) z wektorem inicjalizującym IV. IV możemy rozumieć jako blok zerowy, którego wartość powinna być losowa. Służy on do zaszyfrowania pierwszego bloku tekstu jawnego. Każdy kolejny blok tekstu jawnego jest xorowany z zaszyfrowanym blokiem z poprzedniej rundy działania algorytmu.

Dla jasności schemat z angielskiej Wikipedii:

Na koniec należy wyjaśnić, jak deszyfrować w trybie CBC.

Pierwszy blok szyfrogramu jest deszyfrowany, a następnie xorowany z wektorem inicjalizującym. Każdy kolejny blok szyfrogramu jest deszyfrowany i xorowany z zaszyfrowanym blokiem z poprzedniej rundy algorytmu.

I znów diagram z angielskiej Wikipedii:

Praktyka: atak padding oracle

Sama idea ataku nie jest szczególnie skomplikowana, niestety wymaga trochę matematyki.
Przyjmijmy następujące oznaczenia:

Z matematycznego punktu widzenia szyfrogram C definiujemy jako ciąg bloków C1…Cx, gdzie:

Analogicznie P definiujemy jako ciąg bloków P1…Px, gdzie:

Ważne, aby zrozumieć, że atak ten jest skuteczny przeciwko CBC, a nie algorytmowi, który został w nim użyty. Swoją drogą, atak jest bardzo „hollywoodzki”, ponieważ atakujący łamie szyfrogram bajt po bajcie; idealnie nadaje się do zekranizowania w kolejnej części matrixa. :-)

A zatem, jako atakujący, będziemy przesyłać do wyroczni spreparowany szyfrogram składający się z dwóch bloków: B oraz Cn, gdzie Cn, to kolejne bloki szyfrogramu C. Niestety musimy wprowadzić kilka kolejnych definicji.
Przyjmijmy dodatkowo, że:

Oczywiście P’ jest znany tylko wyroczni i składa się również z dwóch bloków: P’1 i P’2.

Wprowadźmy kolejne oznaczenia:

Z poprzednich definicji wiemy, że:

Przypomnijmy, że:

czyli:

W ten sposób doszliśmy do miejsca, w którym mamy równanie z dwoma niewiadomymi i jednym typem działania: xor!

Wróćmy jednak do matematyki.

Jak wiadomo, nie da się jednoznacznie rozwiązać równania z dwiema niewiadomymi, zatem musimy pozbyć się jednej niewiadomej. Jak już wspomniałem, xorowanie łańcuchów, to xorowanie poszczególnych bajtów na tych łańcuchach.

Zastosujmy to do poprzedniego równania:

Parę przekształceń i otrzymujemy:

A teraz najtrudniejszy do zrozumienia moment w całej koncepcji ataku – czas wykorzystać wyrocznię.

Jeśli przyjmiemy, że i to ostatni bajt w bloku, to wysyłając do wyroczni różne C’ dla wszystkich możliwych wartości B[i] w pewnym momencie wyrocznia zwróci nam komunikat o poprawnym paddingu (bardziej prawdopodobne, o braku błędu w paddingu). Wiemy więc, na jaką wartość należy ustawić ostatni bajt w B, aby poprawnie odszyfrować C’.

Ale co to oznacza?

Ni mniej ni więcej, że ostatni bajt P’2 jest równy \x01! (lub \x02, jeśli przedostatni bajt w P’2 też miał wartość \x02).

Wykorzystajmy tę wiedzę do poprzedniego równania:

Powyższe równanie, to równanie z jedną niewiadomą: właśnie „złamaliśmy” ostatni bajt n-tego bloku oryginalnego tekstu jawnego P.

Kolejnym etapem będzie „złamanie” przedostatniego bajtu tekstu jawnego. Jak to zrobić?

Ustawmy B[i] na taką wartość, aby P’2[i] = \x02, gdzie i to ostatni bajt bloku. Dlaczego \x02?

Bo chcemy, żeby odszyfrowany tekst jawny P’ kończył się ciągiem \x02\x02. Jak obliczyć nową wartość dla B[i]?

Wykonując kolejne przekształcenia poprzedniego równania, otrzymujemy:

Pn[i] już znamy, bo „złamaliśmy” w poprzednim kroku. P’2[i] = \x02 a Cn-1[i] też jest znane. Wysyłamy do wyroczni nowe C’, iterując po wszystkich możliwych wartościach B[i-1]. W momencie, w którym nie otrzymamy błędu w paddingu, „złamaliśmy” przedostatni bajt oryginalnego tekstu jawnego. Dalej jest już z górki.

Należy iterować po wszystkich bajtach w bloku B w sposób opisany powyżej, aż „złamiemy” cały blok Pn. Iterując po wszystkich blokach P, złamiemy cały szyfrogram C. No, prawie cały, bo bez znajomości IV, nie jesteśmy w stanie odszyfrować pierwszego bloku C 1.

Podsumowanie

Mam nadzieję, że nie zanudziłem was tą matematyką. Starałem się wytłumaczyć logikę stojącą za atakiem, ponieważ wydaje mi się, że przeciętny pentester jest w stanie to ogarnąć.

— Piotr Chmyłkowski