Paweł Goleń, blog

Kryptografia dla mas

Bruce Schneier powinien być znany każdemu, kto interesuje się bezpieczeństwem. Nawet jeśli ktoś nie interesuje się tym tematem zbyt intensywnie, prawdopodobnie miał okazję w jakiś sposób z nim się zetknąć. Można o nim powiedzieć, że jest celebrytą, aczkolwiek na swoją pozycję sobie zapracował. Zapracował na nią między innymi książką Applied Cryptography, w której w stosunkowo przystępny sposób przybliża zagadnienia związane z kryptografią. Tą książką zrobił wiele dobrego, ale też trochę złego... Wiele osób uznało, że po przeczytaniu tej książki wiedzą na temat kryptografii już wystarczająco wiele, by projektować i implementować własne rozwiązania. Niestety, skutki takiego postępowania są zwykle tragiczne. By sytuację choć trochę poprawić, Schneier napisał inną książkę, Practical Cryptography.

Jedną z podstawowych zasad jest to, by nie wymyślać własnych algorytmów. Należy korzystać wyłącznie ze sprawdzonych, zweryfikowanych rozwiązań. Nie należy tych algorytmów implementować we własnym zakresie, lecz należy korzystać wyłącznie ze sprawdzonych bibliotek. Trzeba jednak pamiętać, że nawet takie podejście nie gwarantuje, że wynik naszej pracy spełnia nasze oczekiwania. Nie wystarczy używać sprawdzonych algorytmów i sprawdzonych bibliotek, trzeba jeszcze robić to w sposób prawidłowy, wiedzieć czego trzeba użyć by osiągnąć określony cel i jak to zrobić prawidłowo.

Dzisiaj chciałem opowiedzieć o jednym, katastrofalnym w skutkach błędzie, który powoduje, że zaszyfrowane dane wcale nie są bezpieczne. Atakujący może je odszyfrować bez znajomości klucza, bez znajomości klucza może też zaszyfrować dowolnie wybrane przez siebie dane. Mowa o padding oracle. Często pierwszym skojarzeniem ze słowem oracle jest baza danych. W tym wypadku chodzi jednak o wyrocznię. Wyrocznię, do której możemy przesłać pewne dane i na podstawie jej odpowiedzi wyciągać pewne wnioski. Atak ten dotyczy szyfrów blokowych w trybie CBC, więc najpierw trochę teorii na ten temat.

Szyfry blokowe

Szyfr blokowy, jak sama nazwa wskazuje, operuje na blokach danych. Wiadomość, która ma zostać zaszyfrowana dzielona jest na bloki o wielkości takiej, jak rozmiar bloku, na którym operuje dany szyfr. Na przykład w 3DES rozmiar bloku to 64 bity, dla AES jest to 128 bitów. Dalej tak przygotowane dane wpadają do czarnej skrzynki, którą jest nasz szyfr blokowy. Czarna skrzynka przyjmuje na wejściu również klucz, a wynikiem jej działania jest blok zaszyfrowanych danych. W przypadku dobrego szyfru blokowego rezultat szyfrowania jest nierozróżnialny od losowych danych.

Procedura rozszyfrowania działa dokładnie w ten sam sposób. Zaszyfrowany blok danych przekazywany jest wraz z kluczem do szyfru blokowego. Tym razem szyfr blokowy pracuje w trybie odszyfrowywania danych i rezultatem jego pracy jest blok odszyfrowanego tekstu.

Oczywiście wiadomości mają to do siebie, że wcale ich rozmiar nie musi być wielokrotnością rozmiaru bloku szyfru. By ten problem rozwiązać stosowany jest padding. Polega on na uzupełnieniu wiadomości do pożądanej długości pewnymi danymi. Jeśli przypadkiem tak się składa, że długość wiadomości jest wielokrotnością rozmiaru bloku szyfru, wówczas dodawany jest cały blok paddingu.

Struktura paddingu nie jest przypadkowa. Jednym z najczęściej stosowanych paddingów jest padding zgodny z PKCS#7. Zasada jego działania jest prosta - brakujące bajty uzupełniane są pewnymi wartościami, przy czym wartość paddingu zależy od jego długości. Czyli jeśli padding ma rozmiar jednego bajtu, to wstawiana jest wartość 01, jeśli brakuje dwóch bajtów, wówczas padding ma wartość 02 02, jeśli trzech - 03 03 03, i tak dalej aż do pełnego bloku. Warto zapamiętać te informacje o strukturze paddingu, bo są one bardzo pomocne w ataku, o którym mowa.

Tryby ECB i CBC

Niewiele wiadomości mieści się w jednym bloku. Zaszyfrowanie dłuższej wiadomości polega po prostu na zaszyfrowaniu jej wszystkich bloków. W najprostszym przypadku, trybie ECB, każdy blok wiadomości szyfrowany jest kompletnie niezależnie od pozostałych bloków. Ma to swoje zalety, na przykład wydajność - operacja szyfrowania wielu bloków może być wykonywana równolegle, ale i wady.

Trzeba pamiętać, że szyfr blokowy jest algorytmem deterministycznym. Oznacza to, że jeśli na wejściu otrzyma taki sam klucz i takie same dane do zaszyfrowania, to zaszyfrowane dane będą również takie same. W praktyce oznacza to, że jeśli w szyfrowanej wiadomości znajdują się jakieś regularności, powtarzające się ciągi danych, to ta sama struktura może uwidocznić się z zaszyfrowanych danych, nawet mimo tego, że każdy blok z osobna jest nierozróżnialny od losowych danych.

Dobrą wizualizacją jest demonstracja szyfrowania obrazka. Na przykład takiego:

Po zaszyfrowaniu algorytmem AES w trybie ECB i wstawieniu do rezultatu szyfrowania prawidłowego nagłówka BMP otrzymuje się następujący rezultat:

W obrazku będącym rezultatem szyfrowania nadal widać napis wyraźnie odcinający się od tła. Analogiczny efekt można uzyskać na przykład w przypadku plików chronionych prawem autorskim. W pliku można osadzić pewien znak wodny, który nadal będzie widoczny w zaszyfrowanych danych, o ile rozwiązanie do ich zaszyfrowania na taki atak jest podatny (patrz: watermarking attack). Na atak tego typu były podatne różne rozwiązania służące do szyfrowania dysków, teraz jest lepiej - wystarczy, że autorzy takich programów w odpowiedni sposób użyją trybu XTS-AES zaaprobowanego przez NIST właśnie do takich zastosowań.

Jest również inny tryb pracy szyfru blokowego, którego rezultat dla tego samego obrazu wygląda zupełnie inaczej:

Tym trybem pracy jest CBC. Dane zaszyfrowane z jego wykorzystaniem są praktycznie, jako całość, nierozróżnialne od losowego szumu. Jeśli atakujący przechwyci wiadomość zaszyfrowaną w trybie CBC to w zasadzie nie dowie się na jej temat niczego poza tym, jaki ma rozmiar. To też może być przydana informacja, wystarczy wspomnieć atak CRIME, ale to już trochę inny temat.

Na czym polega tryb CBC? Po pierwsze pojawia się losowy wektor IV o rozmiarze równym rozmiarowi bloku szyfru. Wartość IV powinna być unikalna dla każdej szyfrowanej wiadomości i powinna być losowa. W trakcie operacji szyfrowania przed przekazaniem pierwszego bloku tekstu jawnego do szyfru blokowego, jest on poddawany operacji XOR z wektorem IV. Dopiero tak przekształcony blok poddawany jest operacji szyfrowania. Operacja ta powtarzana jest w kolejnych blokach, przy czym zamiast wektora IV używany jest rezultat szyfrowania poprzedniego bloku.

Analogicznie sytuacja wygląda w trakcie operacji rozszyfrowania danych. Zaszyfrowane dane są najpierw przepuszczane przez szyfr blokowy, rezultat tej operacji jest poddawany operacji XOR i dopiero w jej wyniku otrzymywany jest tekst jawny. W przypadku pierwszego bloku do operacji XOR wykorzystywany jest wektor IV, w przypadku kolejnych bloków - poprzedni blok tekstu zaszyfrowanego.

Czym skutkuje takie podejście? Po pierwsze spadkiem wydajności. W tej chwili operacja szyfrowania i staje się operacją sekwencyjną. Nie można zaszyfrować drugiego bloku przed zaszyfrowaniem bloku pierwszego, ponieważ wówczas nie wiadomo jeszcze co użyć przy XOR jawnego tekstu. Ważniejsze jest jednak to, że w przypadku losowych i unikalnych IV dwie zaszyfrowane tym samym kluczem wiadomości są kompletnie do siebie niepodobne, nawet jeśli są takie same. Również ewentualne regularności w obrębie jednej wiadomości zostają efektywnie ukryte.

O CBC nieco dokładniej

Przyjrzyjmy się operacji szyfrowania i deszyfrowania danych na przykładzie algorytmu 3DES i tekstu TECHCAMP#6.

W przypadku algorytmu 3DES rozmiar bloku to 64 bity (a więc 8 bajtów/znaków). Tekst składa się z 10 znaków, więc zmieści się w dwóch blokach, przy czym konieczne jest 6 bajtów paddingu, każdy z nich zgodnie z PKCS#7 ma wartość 06.

Zawartość pierwszego bloku tekstu jawnego jest poddawana operacji XOR z wartością IV, oczywiście ta operacja działa bajt po bajcie. Otrzymana wartość jest poddawana operacji szyfrowania, w rezultacie otrzymywany jest pierwszy blok tekstu tajnego, który jest również używany w operacji szyfrowania drugiego bloku. Znów mamy operację XOR, której wynik jest szyfrowany.

Rezultatem tej operacji są dwa bloki tekstu zaszyfrowanego, w wielu rozwiązaniach do wiadomości dołączany jest również wektor IV jako pierwszy blok. Jest on niezbędny przy operacji odszyfrowania danych.

Przy rozszyfrowaniu najpierw blok tekstu tajnego jest przekazywany rozszyfrowywany, a następnie jego rezultat jest poddawany operacji XOR z wektorem IV. Rezultatem jest pierwszy blok tekstu jawnego. Przy okazji warto zwrócić uwagę, że atakujący modyfikując wektor IV może dowolnie zmodyfikować wartość pierwszego bloku otrzymywanego po rozszyfrowaniu, ale ponownie - to nieco inny temat.

Przy rozszyfrowaniu kolejnego, w tym przypadku również ostatniego, bloku zaszyfrowanej wiadomości rezultat rozszyfrowania jest poddawany operacji XOR z poprzednim blokiem tekstu tajnego. Jej wynikiem jest pozostała część tekstu jawnego, oraz padding. Przy przetwarzaniu ostatniego bloku następuje weryfikacja paddingu i jest on odrzucany. A co w przypadku, gdy z jakiegoś powodu padding jest nieprawidłowy?

Nieprawidłowy padding i co z tego wynika

Skutkiem nieprawidłowego paddingu może być na przykład taki obrazek:

Oczywiście nie zawsze błąd musi być tak bardzo widoczny. Równie dobrze może to być minimalnie inne zachowanie systemu, ważne, by było w jakiś sposób rozróżnialne. Jeśli jest - mamy padding oracle.

W jaki sposób atakujący może generować takie błędy i co mu to w zasadzie daje? Popatrzmy jeszcze raz na operację rozszyfrowyania danych. Wyobraźmy sobie, że pierwszy blok zaszyfrowanego tekstu zastępujemy kompletnie losową wartością. Rezultatem rozszyfrowania pierwszego bloku będą prawdopodobnie śmieci, ale nie jest to specjalnie istotne. Bardziej istotne jest to, że ostatni blok po rozszyfrowaniu i wykonaniu operacji XOR nie będzie zawierał prawidłowego paddingu, a więc powinien wystąpić oczekiwany błąd.

Kolejnym krokiem atakującego będzie modyfikacja ostatniego bajtu przedostatniego bloku tekstu zaszyfrowanego. Wartość ta będzie używana przy operacji XOR na rezultacie operacji deszyfrowania ostatniego bloku wiadomości. Jeśli atakujący przejdzie wszystkie możliwe wartości tego bajtu, od 00 do FF, to w jednym przypadku system powinien odpowiedzieć troszkę inaczej. Dlaczego? Dlatego, że na ostatnim bajcie ostatniego bloku pojawia się wartość 01. W tej chwili wystarczy popatrzeć jaka wartość jest na ostatnim bajcie przedostatniego bloku i wiemy już jaka wartość występuje na ostatnim bajcie ostatniego bloku po wyjściu z 3DES.

Atakujący mając taką wiedzę modyfikuje ostatni bajt przedostatniego bloku w taki sposób, by teraz po operacji XOR dawał wartość 02, a modyfikuje przedostatni bajt przedostatniego bloku, znów od 00 do FF. I znów w jednym przypadku aplikacja zachowuje się nieco inaczej. Atakujący zna już dwa bajty, które w ostatnim bloku wychodzą z naszej czarnej skrzynki. Powtarzając ten sposób postępowania ustala on wartość całego bloku. Pozostaje mu w tej chwili wykonać operację XOR na ustalonej wartości i oryginalnej wartości poprzedniego bloku, a w rezultacie otrzymuje on tekst jawny. Całą zabawę powtarza dla kolejnych bloków, średnio 128 prób na bajt i wcześniej lub później dowie się, co było zaszyfrowane.

Atak z wykorzystaniem padding oracle nie ogranicza się do odszyfrowywania danych. Atakujący postępując w analogiczny sposób może również zaszyfrować wybrane przez siebie dane.

Po co to wszystko - padding oracle w praktyce

Na koniec pytanie - po co to wszystko? Niestety, istnieje przeświadczenie, że dane zaszyfrowane są bezpieczne i atakujący nie może ich w żaden sposób zmodyfikować. Z tego powodu w wielu aplikacjach dane, które nie powinny być modyfikowane przez użytkownika, są szyfrowane. Mówię tu oczywiście o tych przypadkach, gdy te dane są przechowywane (na przykład w polu ukrytym) po stronie klienta. Takie rozwiązania są stosowane na przykład do przechowywania stanu jakiejś operacji składającej się z wielu kroków w przypadku, gdy z jakiegoś powodu ten stan nie może być przechowywany po stronie serwera. Zajrzenie i ewentualna modyfikacja tego stanu może przynieść atakującemu spore korzyści. I, wiem to z doświadczenia, często przynosi.

A tak wygląda w praktyce wykorzystanie podatności padding oracle, tu z użyciem narzędzia PadBuster:

Nie jest to może zbyt pasjonujący pokaz, ale w tym przykładzie jest wszystko, czego potrzeba. Przykładowa aplikacja przyjmowała parametr, którego wartość była zaszyfrowana z wykorzystaniem AES w trybie CBC, wektor IV był zamieszczony w pierwszym bloku wiadomości.

W pierwszym kroku PadBuster sprawdził, czy podatność istnieje. Wykonał 256 żądań i zidentyfikował jedną odpowiedź serwera, która wyglądała nieco inaczej. To jest już wystarczająca informacja. Dalej blok po bloku, bajt po bajcie odszyfrowywał wiadomość według opisanego wcześniej sposobu postępowania.

Jak się bronić

Jak się bronić przed takim atakiem? Przede wszystkim trzeba sobie uświadomić, że co do zasady szyfrowanie danych nie chroni przed ich modyfikacją. Co do zasady, bo istnieją już tryby pracy szyfrów blokowych, które poza poufnością zapewniają również integralność i autentyczność danych. Takie tryby to na przykład CCM, GCM, EAX czy OCB. Niestety, bardzo często okazuje się, że w powszechnie wykorzystywanych bibliotekach te tryby szyfrowania nie są dostępne.

Innym rozwiązaniem jest użycie algorytmu HMAC do zapewnienia integralności i autentyczności zaszyfrowanych danych, przy czym koniecznie należy stosować podejście encrypt-then-mac. Na czym ono polega? Po zaszyfrowaniu do danych należy dodać tag będący wynikiem wykonania algorytmu HMAC na zaszyfrowanych danych. Odbiorca przed rozszyfrowaniem danych najpierw weryfikuje poprawność wartości tag i odszyfrowuje dane wyłącznie w przypadku, gdy wartość jest prawidłowa. Atakujący nie jest w stanie generować wartości tag dla zmodyfikowanych przez siebie danych, nie zna używanego w HMAC klucza, a w związku z tym atak padding oracle staje się niemożliwy.

P.S. Po prezentacji padło pytanie dlaczego HMAC jest lepszy od "zwykłego" hasha. Pisałem już o tym kilka razy, ale polecam ten odcinek kursu z kursu Cryptography I, który zresztą też polecam.