Zabawy z padding oracle

16 lipca 2014, 17:07 | Teksty | komentarzy 11
: zin o bezpieczeństwie - pobierz w pdf/epub/mobi.
Tekst zdobył drugie miejsce w sekurakowym konkursie na najlepszy tekst o bezpieczeństwie (kolejna edycja konkursu jest w trakcie – czekamy na teksty jeszcze prawie 2 miesiące).

Jakiś czas temu, zainspirowany przez sekuraka, postanowiłem zabawić moich kolegów z zespołu w pracy i zorganizować CTF. Jednym z etapów było rozszyfrowanie tokena zaszyfrowanego przy pomocy AES w trybie CBC. Token można było wprowadzić na stronie podatnej na atak 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.

Przykład:
Jeśli długość bloku to 16 bajtów, a tekst jawny to „TekstJawny”, to po dodaniu paddingu PKCS#7 otrzymamy „TekstJawny\x06\x06\x06\x06\x06\x06”.

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:

A B A ^ B
1 1 0
1 0 1
0 1 1
0 0 0

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

A ^ B = B ^ A
A ^ 0 = A
A ^ A = 0

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:
Szyfrowanie w CBC

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:
Deszyfrowanie w CBC

 

Praktyka: atak padding oracle

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

P – tekst jawany wraz z paddingiem, np. „TekstJawny\x06\x06\x06\x06\x06\x06
Pn – n-ty blok tekstu jawnego, np. jeśli blok ma rozmiar 8 bajtów, to:
P1 – „TekstJaw
P2 – „ny\x06\x06\x06\x06\x06\x06
C – zaszyfrowany tekst jawny P (inaczej szyfrogram)
Cn – n-ty blok szyfrogramu
IV – wektor inicjalizujący
E() – funkcja szyfrująca pojedynczy blok, np DES, AES,…
D() – funkcja deszyfrująca pojedynczy blok

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

C1 = E(P1 ^ IV)
Cn = E(Pn ^ Cn-1), dla n > 1

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

P1 = D(C1) ^ IV
Pn = D(Cn) ^ Cn-1, dla n > 1

Atak polega na odszyfrowaniu C bez znajomości klucza, przy pomocy którego był zaszyfrowany.

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:

B – spreparowany blok przez atakującego
C’ – payload, który będziemy przesyłać do wyroczni. Tworzymy go poprzez konkatenację dwóch bloków: B oraz Cn
P’ – tekst jawny powstały po odszyfrowaniu przez wyrocznię C’.

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:

B[i] – i-ty bajt bloku B
P’2[i] – i-ty bajt drugiego bloku P’

Z poprzednich definicji wiemy, że:

P’1 = D(B) ^ IV
P’2 = D(Cn) ^ B

Przypomnijmy, że:

Cn = E(Pn ^ Cn-1)

czyli:

P’2 = D(E(Pn ^ Cn-1)) ^ B = Pn ^ Cn-1 ^ B

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

Zauważcie, że w tym równaniu nie jest używana funkcja szyfrująca. Dlatego właśnie atak jest skuteczny niezależnie od tego, jak silny algorytm został użyty do szyfrowania.

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:

P’2[i] = Pn[i] ^ Cn-1[i] ^ B[i]

Parę przekształceń i otrzymujemy:

Pn[i] = P’2[i] ^ Cn-1[i] ^ B[i]

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:

Pn[i] = \x01 ^ Cn-1[i] ^ B[i], gdzie i, to ostatni bajt bloku

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:

B[i] = Pn[i] ^ P’2[i] ^ Cn-1[i], gdzie i, to ostatni bajt bloku

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.

Na (nie)szczęście programiści często popełniają błąd i ustawiają IV = 0 lub dołączają go jako pierwszy blok szyfrogramu C.

 

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ąć.

Na koniec chciałbym Wam zaproponować nietypowy CTF. Pod tym linkiem znajdziecie podatną aplikację, a zadanie polega na napisaniu własnego narzędzia do wykonania wyżej opisanego ataku.
Powodzenia!

Piotr Chmyłkowski

Spodobał Ci się wpis? Podziel się nim ze znajomymi:



Komentarze

  1. Lorek

    świetnie że ten artykuł powstał w języku polskim, z kryptografią na razie czuję się słabo ale przy każdej możliwej okazji staram się nadrobić ;)

    Odpowiedz
  2. Marek

    „Na (nie)szczęście programiści często popełniają błąd i ustawiają IV = 0 lub dołączają go jako pierwszy blok szyfrogramu C.”

    Po kolei. IV nie musi być tajne. Musi być unikalne. Przyłączenie go jako pierwszego bloku do szyfrogramu nie jest błędem.

    Jak dużym błędem jest ustawienie IV=0? To zależy. W trybie CTR jest show stopper (IV nie jest unikalne). W trybie CBC jest to znaczne osłabienie szyfru, z którego zaczną wyciekać dane odnośnie pierwszego (pierwszych) bloków szyfrogramu.

    Jeżeli każdy tekst jawny będziemy szyfrować unikalnym hasłem, ustawienie IV=0 nie będzie błędem.

    Odpowiedz
  3. Marek

    Ach, najistotniejsze mi umknęło. Bardzo fajny artykuł. Dobra robota!

    Jeżeli ktoś chce poćwiczyć Padding Oracle (i inne ataki) w praktyce, na courserze jest fajny kurs kryptografii (prowadzony przez prof. Dana Boneh ze Stanfordu!): https://www.coursera.org/course/crypto

    Kurs jest świetny. Polecam.

    Odpowiedz
    • To jeszcze zostaje Ci tylko wziąć udział w mini sekurakowym konkurie – info na samym dole posta.

      Odpowiedz
      • Marek

        No jest aplikacja. Chyba nawet działa. :) Tyle tylko że atak padding oracle wymaga szyfrogramu który będziemy łamać, a tego jak do tej porty nie udało mi się odszukać. On w ogóle gdzieś jest?

        Odpowiedz
        • Piotr
          Odpowiedz
          • To panowie, z tym hintem – do dzieła! ;-)

          • Marcin

            Jakiś hint gdzie szukać znaczenia „cyferek”? ;)

  4. Damian Wąsik

    Fajny artykuł, gratulacje.

    Odpowiedz
  5. Tor

    Mętnie napisane. Mam wrażenie że ten CTF (napisanie programu) jest po to, aby ułatwić Komuś zrozumienie o co chodzi. Tylko po co jest ten link do strony, skoro nie ma czego łamać?

    PS
    Cały program to tylko dwie pętle z wywołanie funkcji oracle i pare przypisań do zmiennych ;)

    Odpowiedz
  6. Karol

    Ja nie rozumiem jednej rzeczy: jak ta cała wyrocznia odróżnia błędny padding od poprawnego?

    Np rozpatrujemy padding = 0x01. Czego oczekujemy?

    Odpowiedz

Odpowiedz