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ę