2013-04-30
1
Bezpieczeństwo
i ochrona danych
Ataki na implementacje
algorytmu RSA
Agenda
• Atak Kocher’a
• Atak Schindler’a
• Atak Brumley-Boneh
Ataki
• Atak Kocher’a
– Systemy które korzystają z powtarzającego ^2,
a nie z CRT lub Montgomerego (smart cards)
• Atak Schindler’a
– ^2, CRT oraz Montgomery
(brak rzeczywistych systemów)
• Atak Brumley-Boneh
– CRT, Montgomery, sliding windows, Karatsuba
(openSSL)
Kocher
• Atak na powtarzające się potęgowanie
– Nie działa dla CRT oraz Montgomery
– W większości przypadków jest
wykorzystywane CRT lub mnożenie
Montgomerego
– Tylko w przypadkach znacznych ograniczeń
sprzętowych korzysta się z metody ^2
– np. smartcards
Algorytm
// Compute y = x
d
(mod N)
// where, in binary, d = (d
0
,d
1
,d
2
,…,d
n
) with d
0
= 1
s = x
for i = 1 to n
s = s
2
(mod N)
if d
i
== 1 then
s = s
x (mod N)
end if
next i
return s
Atak Kocher’a -założenia
• Korzystamy z algorytmu ^2
• Czas operacji
s
x (mod N)
zależy od s oraz x
• Intruz może oszacować czas potrzebny dla
obliczenia wyniku przy domniemanych
wartościach s oraz x
• Intruz może otrzymać wynik pomiaru czasu z
wykorzystaniem klucza prywatnego
C
d
(mod N)
2013-04-30
2
Atak Kocher
• Odtwórz bity klucza prywatnego
– Klucz prywatny: d = d
0
,d
1
,…,d
n
gdzie d
0
= 1
– Odtwarza bity w kolejności, d
1
,d
2
,d
3
,…
• Nie trzeba odtworzyć wszystkich bitów
– Można odtwarzać skutecznie mniej
znaczące bity, kiedy znamy wystarczająco
dużo bitów bardziej znaczących
Atak Kocher’a
• Przypuśćmy, że bity d
0
,d
1
,…,d
k
1
, są znane
• Chcemy znaleźć bit d
k
• Losowo wybieramy C
j
dla j=0,1,…,m-1,
otrzymując czasy T(C
j
) dla C
j
d
(mod N)
• Dla każdego C
j
powtarzamy kroki i=1,2,…,k-1
alg. powtarzanego ^2
• Dla kroku k, symulujemy d
k
= 0 oraz d
k
= 1
• Wariancja
różnic czasu kodowania będzie
mniejsza dla właściwej wartości d
k
Atak Kocher’a
• Na przykład
– Niech klucz prywatny składa się z 8 bitów
– d = (d
0
,d
1
,…,d
7
) gdzie d
0
= 1
• Intruz wie, że
d
0
d
1
d
2
d
3
{1010,1001}
• Intruz generuje losowo C
j
…
– Otrzymuje ciąg czasów T(C
j
) i
– Szacuje czasy dla d
0
d
1
d
2
d
3
= 1010 oraz d
0
d
1
d
2
d
3
=
1001
• Niech
i
będzie szacowanym czasem dla bitu i
– Zależy od wartości tego bitu
Atak Kocher’a
• Dla i > m niech
i
…m
będzie skrótem
i
+
i+1
+ … +
m
• Intruz konstruuje tabelę z T(C
j
) oraz
0…3
• Oblicza wariancję
– Mniejsze wariancje “wygrywają”
Atak Kocher’a
• Przypuśćmy następujące wyniki
Dla d
0
d
1
d
2
d
3
= 1010 Intruz otrzymuje
E(T(C
j
)
0…3
) = 6 oraz var(T(C
j
)
0…3
) = 1/2
Dla d
0
d
1
d
2
d
3
= 1001 Intruz otrzymuje
E(T(C
j
)
0…3
) = 6 oraz var(T(C
j
)
0…3
) = 1
Atak
Kocher’a implikuje, że d
0
d
1
d
2
d
3
= 1010
Atak Kocher’a
• Dlaczego preferować małe wariancje?
– Więcej bitów prawidłowych, dlatego mniejsze
będą różnice czasu kodowania
• Dokładniej
–
i
czas wynikający z symulacji obliczeń dla bitu i
– t
i
rzeczywisty czas obliczeń dla bitu i
• Niech var(t
i
) = var(t) dla wszystkich i
– u „błąd” pomiaru
• Z poprzedniego przykładu:
– Właściwa wartość: var(T(C
j
)
0…3
) = 4var(t) + var(u)
– Błędna wartość: var(T(C
j
)
0…3
) = 6var(t) + var(u)
2013-04-30
3
Atak Kocher’a
• Prosty i elegancki
– Działa tylko dla algorytmu ^2
• Dlaczego nie dla CRT, etc.?
• Różnice czasów dla metody CRT,
Montgomery, etc., zawierają się w błędzie
pomiaru u
Atak Schindler’a
• Założenie: korzystamy z metody ^2, algo.
Montgomerego oraz CRT
• Nie jest dedykowana rzeczywistym
systemom
• Ale jest to istotny element na drodze do
innego typu ataków (Brumley-Boneh)
Atak Schindler’a
• Postać Montgomerego
Atak Schindler’a
• Alg. dzielenia Mongomerego
Atak Schindler’a
• Korzystamy również z CRT
– Dla każdego dzielenia mod N,
gdzie N = pq
– Oblicz reszty mod p oraz mod q
– Skorzystaj z algorytmu powtarzanego ^2
• Intruz wybiera kryptogram C
j
– Dysponuje dokładnym czasem C
j
d
(mod N)
– Celem jest odtworzenie d
Atak Schindler’a
• Przypuśćmy, że
a
= aR (mod N) oraz
B losowe
– B rozkładem losowym na przedziale
{0,1,2
,…,N
1}
• Wtedy atak Schindler określa
2013-04-30
4
Atak Schindler’a
• Powtarzane operacje potęgowania i mnożenia
– Potęgowanie: s
= Montgomery(s
,s
)
– Mnożenie: s
= Montgomery(s
,t
)
• Prawdopodobieństwo „extra redukcji” w
operacji “mnożenia”:
• Prawdopodobieństwo „extra redukcji” w
operacji “potęgowania”:
Atak Schindler’a
• Niech korzystamy z CRT
• Pierwszy krok
• Gdzie
• Przypuśćmy, że w obliczeniach
występuje k
0
operacji mnożenia oraz k
1
potęgowań
• Oczekiwana liczba „ekstra redukcji” :
Atak Schindler’a
• Liczba „ekstra
redukcji”:
• Nieciągłość przy
każdej całkowitej
wielokrotności p
Atak Schindler’a
• Jaka korzyść?
• Jeżeli wybrany kryptogram C
0
jest zbliżony
do C
1
– Przez ciągłość, czas T(C
0
) bliski T(C
1
)
• Jednak, jeżeli C
0
< kp < C
1
, wtedy
T(C
0
)
T(C
1
)
jest “duże” – bo nieciągła funkcja
– nieciągłości dla wszystkich wielokrotności p i q
Algorytm ataku Schindler’a
• Wybierz wartość początkową x oraz offset
• Niech C
i
= x + i
dla i = 0,1,2,…
• Oblicz t
i
= T(C
i+1
)
T(C
i
) dla i
= 0,1,2,…
• W końcu, “przedział” wielokrotności p
– To jest , C
i
< kp < C
i+1
– Możliwe, gdyż t
i
jest duże
• Wtedy oblicz gcd(n,N) dla wszystkich
C
i
n
C
i+1
– gcd(kp,N) = p oraz gcd(n,N) = 1 w przeciwnym
przypadku
Atak Schindler’a
• Atak „inteligentny”: przeciw metodzie
potęgowania, Montgomery oraz CRT
– Spostrzeżenie: „ekstra redukcje” w algorytmie
Montgomery powodują zależności czasowe
• Jednakże, brak rzeczywistych zastosowań
– Wersje optymalizowane korzystają również metody
Karatsuba
– Karatsuba negatywnie wpływa na zależności
czasowe związane z występowaniem „ekstra
redukcji”
2013-04-30
5
Atak Brumley-Boneh
• Atak przeciw - CRT, mnożenie Montgomery, okno
przesuwne, Karatsuba
• Optymalizowane implementacje RSA korzystają
właśnie z tych przekształceń
• Atak jest skuteczny
– Działa np. na implementację OpenSSL
Atak Brumley-Boneh
• Zaprojektowany przeciw implementacji RSA
w OpenSSL
– Wysoce zoptymalizowana implementacja
– CRT, powtarzane ^2, mnożenie Montgomerego,
okno przesuwne (5 bitów)
– Mnożenie Karatsuba dla liczb o zbliżonym
rozmiarze;
• Atak Kocher’a nieskuteczny wobec CRT
• Atak Schindler’a nieskuteczny przez
mnożenie Karatsuba
• Brumley-Boneh rozszerza atak Schindler’a
Atak Brumley-Boneh
• RSA w OpenSSL posiada dwa elementy
wrażliwe na analizę czasu
– Redukcaja Montgomerego
– Karatsuba
• Oba elementy oddziałują na siebie
– Pojawia się więcej redukcji (wolniej) kiedy
stosowano mnożenie Karatsuba (szybciej)
– Mniej redukcji (szybciej) więcej długich
operacji mnożenia (wolniej)
Atak Brumley-Boneh
• Niech C
będzie postacią Montgomerego C
• Przypuśćmy, że C
jest bliskie p gdzie C
> p
– Liczba redukcji Montgomerego jest mała
– C
(mod p) jest małe, więc pojawiają się długie
mnożenia
• Przypuśćmy, że C
jest bliskie p gdzie C
< p
– Liczba redukcji Montgomerego jest duża
– C
(mod p) jest bliskie p, więc korzystamy z
mnożenia Karatsuba
Atak Brumley-Boneh : Krok1
• Oznaczmy bity p przez p = (p
0
,p
1
,p
2
,…,p
n
)
– gdzie p
0
= 1
• Przypuśćmy, że p
1
,p
2
,…,p
i
1
zostały ustalone
• C
0
= (p
0
,p
1
,…, p
i
1
,0,0,…,0)
• C
1
= (p
0
,p
1
,…, p
i
1
,1,0,…,0)
• Niech
– Jeżeli p
i
= 1, wtedy C
0
< C
1
p
– Jeżeli p
i
= 0, wtedy C
0
p < C
1
Atak Brumley-Boneh : Krok 2
• Oznaczmy czas deszyfrowania T(C
0
) oraz T(C
1
)
• Niech
=
T(C
0
)
T(C
1
)
• Jeżeli C
0
< p < C
1
wtedy
jest duże
p
i
= 0
• Jeżeli C
0
< C
1
< p wtedy
jest małe
p
i
= 1
– Poprzednio
było używane do ustalenia progu pomiędzy
dużym/małym
2013-04-30
6
Atak Brumley-Boneh: Krok 2
• Jeżeli p
i
= 1 wtedy C
0
< C
1
< p
– Liczba redukcji pozostaje niezmienna
– Pojawia się mnożenie Karatsuba ponieważ wymiar
mod p jest zbliżony
– Spodziewamy się, że
będzie „małe”
• Jeżeli p
i
= 0 wtedy C
0
< p < C
1
– Jeżeli redukcje dominują, to T(C
0
)
T(C
1
) > 0
– Jeżeli Karatsuba dominuje nad długimi
mnożeniami, to T(C
0
)
T(C
1
) < 0
– W obu przypadkach spodziewamy się, że
będzie
„duże”
Atak Brumley-Boneh: Krok 3
• Powtórz kroki 1 oraz 2
• Odtwórz bity p
i+1
,p
i+2
,p
i+3
,…
• Kiedy połowa bitów z p odtworzona, weź
algorytm Coppersmiths w celu faktoryzacji N
• Wtedy d może być otworzona łatwo
Atak Brumley-Boneh:
rzeczywistość
• OpenSSL korzysta z okna przesuwnego
– Redukuje liczbę operacji mnożenia
– Konieczność wykorzystania metod statystycznych
– powtórzonych pomiarów, testowania wartości
progowych, etc.
• OpenSSL atak przez sieć
– Konieczność zastosowania metod statystycznych
– Atak jest zadziwiająco skuteczny
• W rzeczywistej sieci, moduły 1024-bit są
faktoryzowane z wykorzystaniem 1.4M
wybranych kryptogramów
Brumley-Boneh: podsumowanie
• Główne osiągnięcie kryptoanalizy
• Zaskakuje skuteczność nawet przy
zmienności parametrów środowiska
sieciowego
• Przyczynił się do zmian w OpenSSL
– oraz innych implementacjach RSA
• Brumley-Boneh jes rzeczywistym
zagrożeniem!
Zapobieganie analizie czasowej
• Wiele możliwych rozwiązań
• Najlepsza metoda
RSA Blinding
• W celu odszyfrowania C generuj losowe r, potem
oblicz
Y = r
e
C (mod N)
• Deszyfruj Y potem pomnóż przez
r
1
(mod N):
r
1
Y
d
= r
1
(r
e
C)
d
= r
1
rC
d
= C
d
(mod N)
• Ponieważ r jest losowe, Intruz nie może uzyskać
zależności czasowych poprzez wybór C
– Wada – nieznaczne pogorszenie wydajności
Atak błędów (Glitching)
• Wprowadzone błędy ujawniają elementy klucza
prywatnego
• CRT może być wykorzystane do realizacji tego
typu ataku
• Pojedynczy błąd może spowodować, że Intruz
będzie w stanie rozłożyć na czynniki pierwsze
moduł!
• Realne zagrożenie dla systemów smartcards
– oraz innych systemów gdzie intruz ma fizyczny dostęp
do zasobów
2013-04-30
7
Atak błędów (Glitching)
• Rozważmy CRT dla podpisu M
• Niech M
p
= M (mod p) i M
q
= M (mod q)
• Niech
d
p
= d (mod (p
1)) i d
q
= d (mod (q
1))
• Podpisujemy
S = M
d
(mod N) = ax
p
+ bx
q
(mod N)
a = 1 (mod p) i a = 0 (mod q)
b = 0 (mod p) i b = 1 (mod q)
Atak błędów (Glitching)
• Intruz wymusza wystąpienie pojedynczego
błędu
• Niech x
q
zamiast x
q
– x
p
jest prawidłowe
– Błąd w obliczeniu M
q
lub x
q
• “Podpis” S
= ax
p
+ bx
q
(mod N)
• Intruz wie, że wystąpił błąd, gdyż
(S
)
e
(mod N)
M
Atak błędu (Glitching)
• Intruz wymusza błąd
• Intruz otrzymuje S
= ax
p
+ bx
q
(mod N)
– a = 1 (mod p) i a = 0 (mod q)
– b = 0 (mod p) i b = 1 (mod q)
• Wtedy
S
(mod p) = x
p
= (M (mod p))
d (mod (p
1))
– Z definicji x
p
oraz a
Atak błędu (Glitching)
• Intruz wymusił błąd, więc
S
(mod p) = x
p
= (M (mod p))
d (mod (p
1))
• Można pokazać, że (S
)
e
= M (mod p)
– To znaczy, że (S
)
e
M = kp dla pewnego k
• Również, (S
)
e
M (mod q)
– wtedy (S
)
e
M
nie jest wielokrotnością
q
• Z tego wynika, gcd(N, (S
)
e
M) ujawnia czynnik
N, czyli p lub q
Atak błędu: podsumowanie
• Pojedynczy błąd może skompromitować
kryptosystem
• Realne zagrożenie
• Nawet jeżeli prawdopodobieństwo jest
niewielkie, daje to przewagę atakującemu
• Błędy mogą również przyczynić się do
złamania niektórych implementacji
algorytmu RSA gdzie nie korzysta się z CRT
Podsumowanie
• Ataki na zależności czasowe są realnym
zagrożeniem
• Ataki błędów (Glitching attacks)również bywają
skuteczne w niektórych przypadkach
• Te typy ataków nie są „klasyczną” metodą
kryptoanalizy
• Bezpieczeństwo kryptografii – więcej niż
bezpieczeństwo algorytmów
– Konieczna „dobra” implementacja
– Atakujący wykorzysta dowolny, słaby element
systemu
2013-04-30
8
Inne ataki na RSA
Mała wartość wykładnika
szyfrującego RSA
• W celu zwiększenia prędkości szyfrowania RSA często stosuje się
małą wartość wykładnika (komponent klucza - e) np. jest często
stosowana wartość 2
16
+1
• W przypadku, kiedy grupa użytkowników korzysta z tego samego
wykładnika (e), oczywiste jest, że muszą korzystać z innych
modułów n. W przeciwnym razie, również byłoby łatwo obliczyć
klucz prywatny.
• Niech Alicja chce wysłać wiadomość m do trzech różnych
podmiotów, które posługują się tym samym wykładnikiem
(e = 3):
c
1
= m
3
(mod n
1
)
c
2
= m
3
(mod n
2
)
c
3
= m
3
(mod n
3
)
Mała wartość wykładnika
szyfrującego RSA
• Obserwując c
1
, c
2
, c
3
oraz znając n
1
, n
2
, n
3
można skorzystać z
twierdzenia CRT:
x = m
3
mod n
1
n
3
n
3
• Ponieważ m < n
i
dla
n (w przeciwnym razie szyfrowanie
generowałoby straty informacji)
x = m
3
m = x
1/3
• Z tego powodu małe wykładniki nie powinny być
wykorzystywane do szyfrowania takich samych wiadomości do
różnych podmiotów.
• Dodawanie soli do wiadomości (uzupełnianie losowymi bitami)
może zapobiec tego typu atakom.
Inne ataki na RSA
Mały wykładnik deszyfrowania:
• Podobnie jak we wcześniejszym przypadku.
Atak typu Forward search :
• Ponieważ klucz szyfrujący jest publiczny, jeżeli przestrzeń
możliwych wiadomości jest mała lub przewidywalna, to
atakujący może podjąć się próby siłowego przeglądu wszystkich
możliwości
– Można stosować sól jako element prewencji
• przykład: system giełdowy
– Format wiadomości: “{BUY, SELL} DDDD SPÓŁKA” gdzie jest 1000 spółek
– |M| = 2 x 10000 x 1000 = 20,000,000 możliwych wiadomoci
– 1M sprawdzeń/ sekundę
20 sekund aby odkryć właściwy komunikat
Inne ataki na RSA
• Niech
c
1
= m
1
e
mod n
c
2
= m
2
e
mod n
• Wtedy
c
1
c
2
= (m
1
m
2
)
e
mod n
• Korzystając z tej własności można zrealizować atak na RSA
• Chcemy ujawnić kryptogram Alicji
c = m
e
mod n
Inne ataki na RSA
• Bob wysyła do Alicji dla losowego x wiadomość
(c’) = cx
e
mod n
• Alicja oblicza
(c’)
d
= (cx
e
)
d
mod n
= c
d
x
ed
mod n
= mx
ed
mod n
= mx mod n
• Jeżeli Alicja ujawni tę informację, to Bob może odczytać
informację oryginalną
m = (mx)x
-1
mod n
2013-04-30
9
Rozmiar modułu RSA
• W roku 1999, zespół prowadzony przez de Riele dokonał udanej
faktoryzacji liczby 512 bitowej.
• W 2001, Dan Bernstein opublikował artykuł, w którym
przedstawił ideę maszyny, która mogłaby dokonać rozkładu w
podobnym czasie modułu 3 razy dłuższego (1536 bits nie
wystarczą??)
– Pomysł wykorzystuje ideę małych elementów przetwarzających dane w
sposób równoległy oraz istnienie odpowiednich algorytmów
• W 2007, liczba 1039 bitowa (2
1039
-1) (307 digits) była
rozłożona w czasie 11 miesiecy
• Obecnie rekomendowane jest korzystanie z kluczy 4096
bitowych oraz liczby p jak i q powinny być zbliżonego rozmiaru
(lecz nie zbyt bliskie siebie)
Dziękuję za uwagę