Treść mojego referatu oparta jest przede wszystkim na pracy:
"Chosen Ciphertext Attacks Against Protocols Based on RSA Encryption Standart PKCS #1"
napisanej przez:
Daniel'a Bleichenbacher'a.
Jest w niej opisana próba ataku na PKCS #1, polegająca na możliwości operacji z użyciem klucza prywatnego przy założeniu, że jest dostęp do wyroczni ("oracle"), która dla zadanego szyfrogramu zwraca bit, czy jest on poprawnie zaszyfrowany PKCS #1.
Zakładam znajomość algorytmu szyfrowania RSA (a zatem również podstawy teori liczb, arytmetyki modulo itd.).
Poniżej zamieszczam opis najważniejszych faktów użytych w moim referacie.

n, e -> RSA public key (PK) = klucz publiczny;

d, p, q-> RSA secret key (SK) = klucz prywatny;
p i q duże rożne liczby pierwsze;

Objaśnienia:
n = p * q -> obliczenia są wykonywane modulo n.
fi (n) = (p-1) * (q-1) -> funkcja Euler'a;
d = e ^ (-1) mod (fi(n))

Obecnie w PKCS #1 występują 3 rodzaje bloków: 0, 1 i 2. Nas interesuje 2 o postaci:

k -> długość w bajtach n; Zatem:
2 ^ (8 * (k - 1)) <= n < 2 ^ (8k)
Blok danych D złożony z |D| bajtów.
"Padding string" PS składa się z k - 3 - |D| niezerowych bajtów wygenerowanych pseudolosowo.
|D| <= k - 11, zatem |PS| >= 8. Szyfrowanie polega na:

1. Uzyskaniu wyżej opisanej postaci.
2. Skonwertowaniu bloku EB = 00||02||PS||D do liczby całkowitej x.
3. Szyfrowaniu RSA do c = x ^ (e) (mod n)

1. Uzyskaniu x' deszyfrując używając PK wiadomość c.
2. Skonwertowaniu bloku x' do postaci EB' (sprawdzane są pierwsze 2 bajty).
3. Po znalezieniu drugiego bloku 00 wiadomo, że po nim zaczynają się dane (a kończy PS).

Blok EB złożony z k bajtów:
EB = EB1||...||EBk jest nazywany PKCS #1 potwierdzonym jeśli ma postać wymaganą przez blok numer 2 PKCS #1. Czyli:

• EB1 = 00
• EB2 = 02
• EB3 do EB10 są niezerowe
• Przynajmnie jeden z bajtów od EB11 do EBk jest 00

• "Chosen-Ciphertext Attack" - atak, w którym atakujący wysyła wybrany przez siebie szyrogram do ofiary i otrzymuje tekst jawny (rozszyfrowany).
• "Adaptive Chosen-Ciphertext Attack" - atakujaćy wybiera kolejne szyfrogramy na podstawie poprzednich iteracji

Fakty:
1. "zwykłe RSA" jest podatne na "Chosen-Ciphertext Attack":
   1. Napastnik chce uzyskać: m = c ^ d (mod n).
   2. Znajduje losowe s i pyta o odszyfrowanie c' = ((s ^ e) * c) (mod n)
   3. Z odpowiedzi: m' = (c') ^ d -> m = m' * s ^ (-1) (mod n)
2. Istnieje algorytm potrafiący odczytac wiadomość RSA, jeśli mamy dostęp do jednego (dowolnego) odszyfrowanego bitu widomości.
   Praca:
   J. Hastad, M. Naslund The security of individual RSA bits. manuscript 1998.
   

Podany algorytm bedzie kożystał z wyroczni, odpowiadającej na pytanie: "CZy dana wiadomość jest PKCS potwierdzona?" (co jest słabszym założeniem niż w "Chosen-Ciphertext Attack").
Możnaby próbować wykożystać (fakt 2) do rozwiązania problemu, ale ten algorytm ma być praktyczny, i starać się minimalizować liczbę dostępów do wyroczni.
Analiza złożoności algorytmu jest "heurystyczna" (bardziej interesujące w tym przypadku są średnie wartości niż górne granice).

Atakujący chce dostać m = c ^ d (mod n), gdzie c to dowolna liczba naturalna.
Wybiera s takie, że c' = c * (s ^ e) (mod n) i wysyła c' do wyroczni.
Jeśli wyrocznia odpowie, że wiadomość jest PKCS potwierdzona to wiadomo, że pierwsze dwa bajty wiadomości (m * s) są 00 i 02.
Przyjmijmy dla wygody: B = 2 ^ (8 * (k - 2)) ; k to długość n w bajtach
Zatem: z tego, że (m * s) jest PKCS potwierdzona wynika:
2 * B <= (m * s) (mod n) < 3 * B (*)
Kożystając z takich kawałków informacji można obliczyć m (średnio 2 ^ 20 dostępów do wyroczni).

Atak można podzielić na trzy fazy:


1. Wiadomość c jest zasłaniana przez wiadmosc c0 (związana z wiadomoscią jawną m0), która jest PKCS potwierdzona.
   
   
2. Proba znalezienia takiego si by szyfrogram c0 * (si ^ e) był PKCS potwierdzony.
   Dla każdego si (takiego że wiadomość jest PKCS potwierdzona) -> liczone są przedziały takie, że m0 musi się nich zawierać.
   
   
3. Zaczyna się gdy pozostaje tylko jeden przedział. Wtedy atakujący posiada wystarczającąliczbę informacji by lepiej wybierać si (by c0 * (si ^ e) (mod n) bylo bardziej prawdopodobnie PKCS potwierdzone). Rozmiar si szybko się zwiększa -> zmniejsza wielkość przedziału. Gdy przedzial ma jeden element to następuje koniec działania.
   
   

Objaśnienia: niech Mi będzie zawsze liczbą zamkniętych przedziałów, w których znajduje sie m0.

1. Zaciemnianie:
   Dla liczby naturalnej c, znajdź losowe s0 takie, że c * (s0 ^ e) jest PKCS potwierdzone.
   Dla pierwszego s0: c0 <- c * (s0 ^ e) (mod n)
   M0 <- {[2B,3B - 1]}
   i <- 1
   
   
2. Szukanie PKCS potwierdzonych wiadomości.
   
   
   1. Początek szukania:
      Jeśli i = 1 to szukaj najmniejszego s1 (s1 >= n / (3B)) takiego, że
      c0 * (s1 ^ e) (mod n) jest PKCS potwierdzone.
      Uwaga: s1 >= (n / 3B) dlatego, że dla mniejszych wartosci na pewno wiadość nie jest PKCS potwierdzona (wynika to z równania (*)).
      
      
   2. Szukanie z więcej niż jednym przedziałem.
      Jeśli i > 1 i |M(i - 1)| >= 2 to szukaj najmniejszego si> s(i-1), takiego, że c0 * (si ^ e) (mod n) jest PKCS potwierdzone.
      
      
   3. Szukanie z jednym przedziałem.
      Jeśli Mi = 1 (np.: Mi = {[a,b]}) wtedy wybieraj takie małe wartości ri i si takie, że:
      
      i
      
      c0 * (s0 ^ e) (mod n) jest PKCS potwierdzone.
      
3. Zawężenie zbioru rozwiązań.
   Po tym jak si zostało znalezione policz Mi jako
   
   
   
4. Obliczenie rozwiązania.
   Jeśli Mi zawiera tylko jedenprzedział długości 1 (np.: Mi = {[a,a]}), to ustaw
   m <- a * (s0 ^ (-1)) (mod n) i zwróć m jako rozwiązanie równania:
   m = c ^ d (mod n).
   W przeciwnym przypadku:
   i <- i + 1
   oraz idż do kroku 2.
   

Uwagi:

• Krok 1 może być pominięty jeśli c jest PKCS potwierdzone.
• Warunek 1 jest używany by zminejszyć pozostały przedział przynajmniej o połowe (w każdej iteracji).
• Możnaby poprawić skuteczność ataku próbując wykorzystać informacje np.: o tyn, że wiadamość m0 * si zawiera przynajmniej jeden bajt zerowy.

Teraz zostanie podana krótka i heurystyczna anlaliza algorytmu (ilości dostępów do wyroczni).
Uwaga: Wszystkie szcowania złożoności są liczone mniej więcej!!!. Oczywiście dodwód poprawności jest "normalny".

Pr(P) - prawdopodobiństwo, że losowo wybrana liczba naturalna (0 <= m < n), jest PKCS potwierdzona.
Pr(A) - prawdopodobiństwo, że losowo wybrana liczba naturalna ma dwa pierwsze bajty: 00 i 02. Wynosi (z wcześniej podanej nierówności): (B / n).
Z
B * 2 ^ 16 > n > 2 ^ 8
wynika 2 ^ (-16) < Pr(A) < 2 ^ (-8)
Pr(A) zazwyczaj wynosi 2 ^ (-16), gdyż n jest zwykle zbliżone do wielokrotności 8.
Prawdopodobieństwo, że PS ("padding string")zawiera conajmniej 8 niezerowych bajtów, po których następuje zerowy:

Przyjmując n przynajmniej 512 bitów (k >= 64): 0.18 < Pr(P | A) < 0.97 (tu k dąży do nieskończoności), zatem
0.18 * 2 ^ (-16) < Pr(P) < 0.97 * 2 ^ (-8)

Dowód poprawności algorytmu:
Zostanie pokazane, że algorytm znajduje m0 i dlatego m.
Pokażemy, że m0 in M(i) iterując po i (indukcja).
Ponieważ m0 jest PKCS potwierdzone to 2B <= m0 <= 3B - 1
a zatem też m0 in M(0).

Załóżmy że m0 in M(i - 1).
Zatem istnieje [a, b] in M(i - 1) takie że a <= m0 <= b.
Ponieważ m0 * si jest PKCS potwierdzone, istnieje liczba naturalne r taka, że
2B <= m0 * si +- r * n <= 3B - 1 i a * si - (3B - 1) <= r * n <= b * si - 2B.
Zatem również:

Zatem z definicji M(i) m0 należy do jednego z przedziałów M(i).

Analiza złożoności ataku:
W kroku 1, s0 znajdowane jest losowo - zatem wymaga (około) 1 / PR(P) dostępów do wyroczni.
Podobnie jest dla i >= 1 w kroku 2.a i 2.b (czyli w kązdym z wymienionych kroków musi być wykonane około 1 / PR(P)).
Niech omega(i) - będzie liczba przedziałow w M(i). Używając heurystycznych argumentów należy oczekiwać, że:


Przedział w M(i) jest ograniiczony przez sufit (B / si).
Wiedza o tym, że m0 * si jest PKCS potwierdzone prowadzi do sufit ((si * B) / n) przedziałów postaci:

Jest tak ponieważ r przyjmuje co najwyżej sufit ((si * B) / n) wartości w równaniu (3).
W szczgólności M(1) zawiera sufit ((si * B) / n) przedziałów.
Jeśli i > 1 oraz I(r) przecina się z jakimś przedziałem z M(i - 1) to I(r) jest zawarte w M(i). Żaden z przedziałów I(r) nie zawiera się w dwuch przedziałach M(i - 1) (wynika to z równań określających przedziały).
Jeśli przedziały I(r) są losowa rozmieszczone to prawdopodobieństwo, że jeden przedział przecina się z M(i - 1) wynosi:
((1 / si) + (1 / s(i-1))) * omega (i - 1), czyli

Oczekujemy, że s2 będzie mniej więcej 2 / Pr(P). Zatem mamy (z wzoru na omega(i)):
Mi wychodzi 2 razy więcej - ale w pracy jest tak:
(2 * (B / n) ^ 2) / Pr(P)) = 2B / (n * Pr(P|A)) < 2B / (0.18 * n) < 1 / 20
Zatem omega(2) wynosi 1 z dużym prawdopodobieństwem. Czyli krok 2.b będzie wykonany tylko raz.

Analiza kroku 2.c:
Czyli M(i) = {[a, b]} i a <= m0 <= b. I dlatego:

Długość przedziału [(2B + ri * n) / b, (3B - 1 + ri * n) / a] wynosi:

Dlatego należy oczekiwać, że znalezienie pary ri, si, która odpowiada (2) odbędzie się dal co trzeciego ri. Zatem znalezienie pary, która odpowiada (1) i (2) to poprostu "przebieganie" po kolejnych wartościach ri.
Prawdopodobieństwo, że si in [(2B + ri * n) / m0, (3B - 1 + ri * n) / m0] wynosi okoła (1 / 2).
Uwaga: Wedug mnie nie jest to oczywiste - ale jeśli rozpisze się odpowiednie prawdopodobieństwa to wyszło mi, że chyba tak jest.
Dlatego znalezienie PKCS potwierdzonego si wymaga około 2 / Pr(P|A) dostępów.
Dlatego, że M(i) jest dzielone w każdym kroku (2.c) na pół (można to pokazać z warunków (1) i (2)) można oczekiwać , że m0 zostanie znalezine po
3 / Pr(P) + (16 * k) / Pr(P|A)
dostępach do wyroczni.

Dla Pr(P) = 0.18 * 2 ^ (-16) i k = 128 (1024-bitowy moduł) potrzeba mniej więcej 2 ^ 20 dostępów do wyroczni (bitowa długość modułu wynisi zazwyczaj wielokrotność 8 i dlatego Pr(P) jest bliskie 0.18 * 2 ^ 16).

Uwagi:

• Prawdopodobięństwa były liczone przy założeniu, że si są niezależne od siebie - a to nie musi być prawdą.
  Np.:niech m0 i si * m0 będą PKCS potwierdzone z "padding" napisami podobnej długości. Dlatego dla pewnego j: m0 = 2 * (2 ^ (8 * (k - 2))) + (2 ^ (8 * j)) * PS + D
  si * m0 = 2 * (2 ^ (8 * (k - 2))) + (2 ^ (8 * j)) * PS' + D'
  Dlatego (2 * si - 1) * m0 będzie PKCS potwierdzona z dużym prawdopodobieństwem, gdyż:
  (2 * si - 1) * m0 = 2 * (2 ^ (8 * (k - 2))) + (2 ^ (8 * j)) * (2PS' - 2PS) + 2D' - D
  jest często PKCS potwierdzone.
  To wydaje się pomagać atakowi, ale być może w pewnych sytuacjach może działać na niekorzyść.
• Podane szacowania są heurystyczne, zatem mogą zdażyć się sytuacje gdy będzie potrzebne więcej dostępów do wyroczni, niż opisane powyżej.
• Zazwyczaj rozmiar bitowy modułów RSA jest wielokrotnością 8. Wybór jest dobry gdyż dla takich modułów Pr(P) jest małe.
  Moduł o długości 8 * k - 7 mógłby powodować atak dużo prostszym (około 2 ^ 13 dostępów do wyroczni).

• Proste Szyfrowanie:
  
  1. Alicja -> m (wiadomość) -> szyforwanie PKCS #1 (bez żadnych sprawdzeń rzetelności) -> c.
     
  2. Alicja wysyła c do Boba.
     
  3. Bob odszyfrowywuje: jeśli c jest PKCS potwierdzona to postępuje zgodnie z protokołem, wpp.: zwraca błąd.
  Jeśli Ewa udaje Alicje to może uzyskać "informacje Wyroczni" (nawet jeśli dany protokół zawiera jakieś póżniejsze sprawdzenia integralności).
  
  Uwaga:
  Standart szyfrowania RSA PKCS #1 nie określa, gdzie powinny się znajdować sprawdzenia rzetelności (przed, czy po zastosowaniu PKCS #1 (a może w ogóle :))).
  
  
• Wiadmości diagnostyczne ("detailed error messages"):
  Umieścić sprawdzenie rzetelności przed PKCS #1 = Alicja szyfruje widomość swoim SK (a potem PK Bob'a).
  Wtedy Ewa nie jest w stanie losować poprawnej wiadomości.
  Atak jednak się i tak powiedzie jeśli wiadomość błędu informuje o miejscu wystąpienia błędu (np.:czy błąd wystąpił podczas sprawdzania czy wiadomość jest PKCS potwierdzona, czy podczas sprawdzania autentyczności).
  
  
• "Atak czasowy":
  Sytuacja podobna do powyższej.
  Załużmy, że zaszyforwana wiadomość c jest odszyfrowywana następująco:
  1. m = c ^ d (mod n)
     
  2. jeśli m nie jest PKCS potwierdzone to odrzuc;
     
  3. wpp.: sprawdz sygnaturę m;
     
  4. jeśli podpis jest właściwy to akceptuej, wpp.: odrzuć;
     
  Można probować wykorzystać mierzenie czasu odpowiedzi serwara do rostrzygnięcia czy wiadomość jest PKCS potwierdzona.
  

Opisany atak można przeprowadzić w SSL V.3.0 podczas protokołu "hand-shake".

1. Klient i server wymieniają wiadomości client.hello i server.hello.
   Następuje wymiana informacji (miedzy innymi jest określane postępowanie kryptograficzne).
   
   
2. Przesłanie kluczy publicznych i certyfikatów.
   
   
3. Klient generuje losowopremastersecret.
   Szyfruje ten string RSA (jeśli został wybrany odpowiedni tryb) i wysyła rezultat do serwera.
   
   
4. Server odszyfrowywuje szyfrogram.
   Jeśli wiadomość nie jest PKCS potwierdzona, to serwer wysyła wiadomość o błędzie i zamyka połączenie.
   Wpp.: kontynuuje protokół "hand-shake".
   
   
5. Klient wysyła wiadomość finished, która zawiera silną autentykacje (by ją obliczyć trzeba znac premastersecret).

Uwaga:
Problemem może być numer wersji umieszczony w formacie bloku. Jest on tam umieszczany by zapobiec atakowi "version rollback".
Jeśli następuje sprawdzenie od razu (razem z PKCS) numeru wersji, znalezienie poprawnej wiadomości może być dużo dłuższe.
Wymieniona przez autora implementacja sprawdzała numer wersji wtedy, gdy serwer był uruchomiony w trybie zgodności (czyli atak byłby możliwy do przprowadzenia).
Ale bardziej bezpieczna implementacja mogłaby sprawdzać numer wersji we wszystkich trybach i zwracać zawsze ten sam kod błędu odzszyfrowywania.
Wtedy prawdopodobieństwo, że losowa wiadomość jestakceptowana jest około 2 ^ (-40).
A to czyni atak nie praktycznym.

Autorzy pracy podają wyniki swoich testów (wszystko implementowali sami):

Podane są również wyniki innych badań nad serwerami SSL.
Tylko jeden z trzech serwerów był bezpieczny na opisany atak.