RSA może mieć poprawną matematykę i przegrać przez format danych wokół niej
RSA nie jest bezpiecznym systemem szyfrowania tylko dlatego, że poprawnie wykonujemy potęgowanie modularne. Wiadomość musi zostać odpowiednio zakodowana przed zastosowaniem prymitywu RSA, a sposób obsługi błędów po odszyfrowaniu również ma znaczenie. W 1998 roku Daniel Bleichenbacher pokazał praktyczny atak na protokoły używające starego formatu PKCS #1 v1.5: wystarczał serwer zdradzający pojedynczą informację o tym, czy spreparowany szyfrogram miał po odszyfrowaniu prawidłowy format. Matematyczne RSA nie zostało przy tym „sfaktoryzowane”. Problem powstał z połączenia paddingu, reakcji implementacji i możliwości wielokrotnego zadawania pytań.
Prymityw RSA to jeszcze nie gotowy szyfr
W podręcznikowym zapisie RSA łatwo skupić się na równaniach z modułem i wykładnikami. Rzeczywiste standardy dodają jednak warstwę kodowania wiadomości. Powód jest fundamentalny: surowe RSA ma strukturę algebraiczną i samo w sobie nie zapewnia wszystkich własności oczekiwanych od bezpiecznego szyfrowania. PKCS #1 definiuje więc konkretne schematy, między innymi RSAES-OAEP oraz starsze RSAES-PKCS1-v1_5. RFC 8017 wyraźnie odradza używanie v1.5 do szyfrowania dowolnych wiadomości i opisuje specjalne środki ostrożności wynikające z ataków chosen-ciphertext.
Jedna odpowiedź „format poprawny / niepoprawny” okazała się wystarczająca
Bleichenbacher rozważył serwer, który dla wybranego szyfrogramu ujawnia tylko to, czy po odszyfrowaniu blok wygląda zgodnie z wymaganym formatem PKCS #1. Taka odpowiedź wydaje się niemal bezużyteczna: nie zawiera jawnego tekstu, klucza ani nawet części wiadomości. Jednak dzięki adaptacyjnemu dobieraniu kolejnych szyfrogramów można łączyć tysiące takich pojedynczych bitów informacji i stopniowo zawężać możliwą wartość tajnego tekstu. Oryginalna praca wskazywała SSL 3.0 jako przykład protokołu podatnego na ten rodzaj ataku.
To przykład oracle attack: program odpowiada na pytanie, którego nie powinien zadawać przeciwnik
„Oracle” w tym kontekście nie musi być specjalnym interfejsem. Może nim zostać różnica w komunikacie błędu, kodzie odpowiedzi albo czasie wykonywania. Jeśli zachowanie systemu zależy od tajnego wyniku pośredniego, napastnik może zamienić tę zależność w kanał informacyjny. Dlatego RFC 8017 zaleca między innymi ujednolicanie błędów przy obsłudze PKCS #1 v1.5. Paradoksalnie problemem może być zbyt dokładne informowanie klienta, co konkretnie było nie tak z odszyfrowanym blokiem.
Bezpieczna kryptografia to algorytm plus protokół plus implementacja
Ta historia jest ważniejsza niż sam stary format paddingu. Pokazuje, dlaczego ocena „używamy RSA, więc jest bezpiecznie” jest niewystarczająca. Trzeba wiedzieć, jaki schemat kodowania jest używany, w jakim protokole, jakie odpowiedzi zwraca aplikacja i czy zachowanie implementacji nie przecieka informacji. Ten sam matematyczny prymityw może być częścią bezpiecznej konstrukcji albo niebezpiecznego protokołu. Współczesne standardy starają się definiować całość, a nie tylko równanie kryptograficzne.
Najmniejszy wyciek może być użyteczny, jeśli da się go powtarzać
Wiele ataków kryptograficznych nie potrzebuje jednorazowego „wielkiego wycieku”. Potrzebują małej, ale zależnej od sekretu informacji, którą można obserwować wielokrotnie. W ataku Bleichenbachera tą informacją było rozróżnienie zgodności formatu. W atakach czasowych będzie to kilka nanosekund różnicy, a w kanałach cache — stan mikroarchitektury. Wspólny wzorzec jest ten sam: dobrze zaprojektowana matematyka może zostać podważona przez informację ujawnianą wokół niej.
Nowocześniejszy padding zmienia konstrukcję, ale nie zwalnia implementacji z ostrożności
RFC 8017 zachowuje RSAES-PKCS1-v1_5 głównie dla zgodności i opisuje zabezpieczenia potrzebne w implementacjach, natomiast dla nowych zastosowań wskazuje RSAES-OAEP jako schemat o mocniejszej podstawie projektowej. To nie znaczy, że wystarczy mechanicznie zamienić nazwę paddingu. Implementacja nadal musi pilnować długości, poprawnego kodowania i tego, jakie informacje ujawniają błędy. Historia Bleichenbachera jest ważna właśnie dlatego, że uczy patrzeć na cały interfejs kryptograficzny: jeśli zewnętrzny obserwator może odróżnić rodzaje niepowodzenia i wielokrotnie zadawać starannie dobrane pytania, nawet pozornie drobny sygnał staje się częścią protokołu. Bezpieczeństwo schematu zapisane w specyfikacji zakłada określone zachowanie implementacji, a nie tylko poprawne wykonanie modularnego potęgowania.
Oraklem może być nie tylko komunikat błędu, ale również czas i zachowanie połączenia
Specyfikacja PKCS #1 ostrzega, że implementacje zgodne ze starszym v1.5 muszą uważać na rozróżnialne stany błędów. Nawet jeśli aplikacja zamieni komunikaty „zły padding” i „zły klucz sesji” na ten sam tekst, różnica w czasie odpowiedzi, zamknięciu połączenia albo dalszym przetwarzaniu może nadal zdradzać, którą ścieżkę wykonał program. To czyni obronę bardziej subtelną niż ukrycie jednego komunikatu. Kryptograficzny oracle jest po prostu obserwowalną zależnością pomiędzy sekretem a odpowiedzią systemu. Historia RSA pokazuje, że cały stos musi redukować takie różnice konsekwentnie — od parsera formatu klucza po warstwę protokołu — ponieważ przeciwnik może wykorzystać dowolny sygnał, który daje powtarzalną klasyfikację zapytań.