Paweł Goleń, blog

Idąc dalej - dwie wiadomości powinny być po zaszyfrowaniu nierozróżnialne. Co to oznacza? Wyobraźmy sobie, że atakujący ma dwie wiadomości m1 i m2. Dysponuje również czarną skrzynką (encryption oracle), do której może "wrzucić" m1 oraz m2, a z której wyjdzie zaszyfrowana wiadomość c (tak, chodzi mi tutaj o chosen-plaintext attack), która powstaje z zaszyfrowania wiadomości m1 LUB m2. Zadaniem atakującego jest stwierdzenie w wyniku zaszyfrowania której wiadomości powstała wiadomość c. Jeśli jest to w stanie zrobić z prawdopodobieństwem wyraźnie większym niż 1/2 (bo takie ma szanse po prostu zgadując), łamie system.

Jak to wygląda w praktyce? Weźmy dowolny szyfr blokowy, na przykład AES. Użyjmy tego szyfru w trybie ECB. Tryb ten działa w ten sposób, że wiadomość wejściowa jest dzielona na bloki o określonej długości i każdy z tych bloków jest szyfrowany niezależnie od siebie. Czyli jeśli mamy wiadomość m składającą się z bloków m1, m2, m3, (...) i np. m1 == m3, to po zaszyfrowaniu otrzymujemy wiadomość c składającą się z bloków c1, c2, c3, (...) gdzie c1 == c3. Czy w takim wypadku atakujący może stwierdzić, jaka wiadomość została zaszyfrowana?

Odpowiedź jest chyba oczywista - tak. Po prostu atakujący przygotowuje wiadomość m1 i m2 w taki sposób, że obie wiadomości składają się z dwóch bloków, przy czym w przypadku wiadomości m1 te bloki są takie same, w przypadku m2 - różne. Wiadomość c będzie również składała się z dwóch bloków (właściwie trzech, bo należy uwzględnić padding). Jeśli dwa pierwsze bloki wiadomości c są identyczne, zaszyfrowana została wiadomość m1, jeśli różne - szyfrowana była wiadomość m2.

Zmieńmy teraz trochę warunki zadania. Zamiast trybu ECB użyjmy trybu CBC, ale dla utrudnienia (albo ułatwienia) załóżmy, że IV jest ustalony na pewną nieznaną, ale stałą wartość i nie ulega zmianie. Czy w tym wypadku atakujący ma szansę stwierdzić, która wiadomość została zaszyfrowana?

Tak, choć tym razem będzie musiał skorzystać z możliwości wcześniejszego odpytania "czarnej skrzynki". Może zrobić to w sposób następujący:

• m1 = A
• m2 = B

W odpowiedzi uzyska on wiadomości c1 i c2 będące zaszyfrowaną wersją wiadomości m1 i m2. Dodajmy jeszcze, że zarówno A i B mają długość dokładnie jednego bloku.

W kolejnym kroku atakujący może przygotować wiadomości (o długości dwóch bloków):

• m3 = A || C
• m4 = B || C

Może je przesłać do "czarnej skrzynki" ponieważ są one inne niż te, które sprawdzał wcześniej. Jak atakujący sprawdzi, czy otrzymana wiadomość c powstała z zaszyfrowania wiadomości m3 lub m4? Prosto - wystarczy, że porówna początek zaszyfrowanej wiadomości z wcześniej zapisanymi zaszyfrowanymi wiadomościami m1 i m2. Jeśli początek jest taki jak w c1 - zaszyfrowana została wiadomość m3. Jeśli nie (jest taki sam, jak w c2) - zaszyfrowana jest wiadomość m4. Dlaczego?

Ponieważ IV jest stały, zaszyfrowanie dwóch takich samych wiadomości da taką samą wartość zaszyfrowanego tekstu. Jeśli dwie różne wiadomości mają taki sam początek (w sensie - jeden lub więcej takich samych bloków), zaszyfrowane wiadomości będą różne, ale początek tekstu zaszyfrowanego w tym przypadku również będzie taki sam. Gdyby dla każdej szyfrowanej wiadomości był generowany nowy, unikalny IV, problemu w tym przypadku by nie było. Dokładnie taka sama sytuacja miałaby miejsce w przypadku trybu CTR w zależności od tego, czy nonce byłby wybierany losowo, czy też nie.

No to wykonajmy kolejny eksperyment myślowy. Załóżmy, że mamy sytuację, w której są dwie czarne skrzynki. Skrzynka A przesyła do skrzynki B zaszyfrowany komunikat. Komunikat ten składa się z dwóch części:

• tajnego identyfikatora uwierzytelniającego skrzynkę A wobec skrzynki B,
• dane wprowadzane przez użytkownika (atakującego) do skrzynki A,

Dodatkowo załóżmy, że szyfrowanie spełnia semantic security (niech to będzie AES w trybie CTR). Ale dodajmy do tego jeszcze jeden krok - komunikat przed zaszyfrowaniem jest poddawany kompresji. Zobaczmy co się dzieje, czy ta dodatkowa kompresja powoduje jakieś niepożądane skutki? Czy dwie wiadomości po zaszyfrowaniu nadal pozostają nierozróżnialne?

Niech wiadomość przed szyfrowaniem wygląda tak:

secret=fcde69af2ad69df45a5d09eb6c19f1bb;daneuzytkownika

W secret przesyłany jest wspomniany tajny klucz, zawartość komunikatu po średniku jest kontrolowana przez użytkownika.

Atakujący w pierwszym kroku może przygotować następujący komunikat:

secret=fcde69af2ad69df45a5d09eb6c19f1bb;secret=ABCDEFGHIJKLMNOPQRSTUVWXYZqrstuv

Jak będzie wyglądała wartość (wielkość) skompresowanych danych? Można to sprawdzić takim prostym skryptem:

[(len(zlib.compress('secret=fcde69af2ad69df45a5d09eb6c19f1bb;secret=%02xCDEFGHIJKLMNOPQRSTUVWXYZqrstuv' % i)), '%02x' %i) for i in range(256)]

Przeskoczmy do interesującego nas fragmentu wyjścia:

(...)
 (82, 'f9'),
 (82, 'fa'),
 (82, 'fb'),
 (81, 'fc'),
 (82, 'fd'),
 (82, 'fe'),
 (82, 'ff')]

Jak widać najmniejszy rozmiar dane po skompresowaniu miały w przypadku, gdy wstawiony został ciąg fc, wówczas wiadomość przed kompresją miała następującą postać:

secret=fcde69af2ad69df45a5d09eb6c19f1bb;secret=fcCDEFGHIJKLMNOPQRSTUVWXYZqrstuv

W kolejnym kroku atakujący modyfikuje kolejne dwa znaki i otrzymuje następujący rezultat:

(...)
 (81, 'dc'),
 (81, 'dd'),
 (80, 'de'),
 (81, 'df'),
 (82, 'e0'),

W ten sposób znajduje kolejne dwa znaki szukanego sekretu. I może tak robić dalej, aż do poznania pełnej wartości szukanego sekretu, a całość jest przykładem chosen-plaintext attack, a konkretnie adaptive chosen-plaintext attack.

Cały atak jest możliwy, ponieważ atakujący na podstawie rozmiaru danych po kompresji jest w stanie wnioskować o danych przed kompresją. W szczególności jest w stanie powiedzieć, w którym przypadku dane przed kompresją zawierały najdłuższe dwa powtarzające się ciągi danych. W tym przypadku kompresja jest najbardziej efektywna i rozmiar danych po kompresji najmniejszy. Informacja o wielkości szyfrowanych danych jest dostępna po zaszyfrowaniu - w przypadku trybu CTR długość szyfrogramu jest identyczna z długością zaszyfrowanych danych (z dokładnością do nonce).

Co w przypadku trybów szyfrowania, w których informacja o rozmiarze szyfrowanego tekstu nie jest tak dokładna? Chodzi mi tu o szyfry blokowe. Dla przypomnienia w szyfrach blokowych (CTR też jest szyfrem blokowym, ale specyficznym) wiadomość jest uzupełniana paddingiem w taki sposób, by mieć rozmiar dokładnie mieszczący się w (kolejnym) bloku, a jeśli wiadomość już mieści się dokładnie w bloku, dodawany jest cały blok paddingu.

Atakujący wciąż jest w stanie przeprowadzić swój atak, musi go jednak trochę zmodyfikować. Prawdopodobnie wygodniej będzie mu sprawdzać po jednym znaku. W pierwszym kroku powinien przygotować taki tekst "bazowy", który po kompresji mieści się dokładnie w bloku. Spowoduje to dodanie na wejściu całego bloku paddingu. Następnie atakujący może modyfikować szyfrowany tekst i patrzeć na rozmiar szyfrogramów. Prawdopodobnie jedna z przygotowanych przez atakującego wiadomości będzie skompresuje się lepiej, niż wiadomość bazowa. O jeden bajt. Ten jeden bajt jednak spowoduje, że przed zaszyfrowaniem zamiast dodania całego bloku paddingu, padding zostanie wstawiony w ten brakujący bajt, w związku z czym szyfrogram będzie wyraźnie różnił się rozmiarem. Atakujący będzie powtarzał te kroki aż do odzyskania wartości interesującego go sekretu.

Jak to się ma do wspominanego już CRIME? Za czarną skrzynkę robiła przeglądarka internetowa, za sekret - cookie (httpOnly). Skrypt demonstracyjny można zobaczyć tutaj: If it's a CRIME, then I'm guilty. Całość dobrze pokazuje, jak niewiele trzeba, by szyfrowanie przestało spełniać swoją rolę. Jeśli szyfrowanie ma zapewniać poufność, to jeśli istnieje jakikolwiek sposób, w który tą poufność można naruszyć, mamy problem. Tu można choćby przypomnieć też o tej sprawie: I can still see your actions on Google Maps over SSL.