2014-04-29

1

Bezpieczeństwo

i ochrona danych

Ataki na jednokierunkowe

funkcje skrótu oraz

implementację algorytmu RSA

Agenda

• Ataki na funkcje skrótu

– paradoks urodzinowy
– atak Nostradamusa

• Ataki na implementacje RSA – podstawy

teoretyczne

– modularne potęgowanie ^2
– mnożenie i redukcja Mongomerego
– mnożenie Karatsuba

Problem przed-urodzinowy

• Przypuśćmy, że jest N osób w pokoju
• Jak duże musi być N aby

prawdopodobieństwo, że znajdziemy
kogoś, kto się urodził w tym samym dniu
co my sami będzie



½?

– Rozwiązanie: ½ = 1



(364/365)

N

dla N

– Czyli N = 253

Problem urodzinowy

• Jak wiele osób musi być w tym samym pokoju

aby prawdopodobieństwo znalezienia dwóch
osób obchodzących urodziny w tym samym
dniu było większe od ½ ?

– 1



365/365



364/365







(365



N+1)/365

– Przyrównujemy do ½ i rozwiązujemy:

N = 23

• Dziwne? Paradoksalne?
• Nie.

Powinno być około sqrt(365) ponieważ
poszukujemy par x i y

Urodziny i funkcje skrótu

• Jeżeli h(x) ma N bitów, ma 2

N

różnych wartości

• Zauważmy, że sqrt(2

N

) = 2

N/2

• Stąd przy 2

N/2

różnych wejściach możemy liczyć na

wystąpienie kolizji.

– “atak urodzinowy” — przeszukiwanie kompletne

• N-bitowy symetryczny algorytm wymaga około 2

N



1

sprawdzeń aby znaleźć klucz

• Dla N-bitowej funkcji skrótu: wystarczy 2

N/2

tylko

Atak urodzinowy na podpis

• Przypuśćmy, że mamy n-bitową funkcję skrótu
• Malkolm generuje dokument (M

Z

), w którym

Alicja przyznaje się do napadu na bank

– Chce dostać podpis Alicji pod wiadomością (M

Z

)

– Malkolm generuje petycję dotyczącą zwolnienia z

egzaminu wszystkich osób, których imię zaczyna się
na A (M

D

)

– Alicja chętnie podpisuje wiadomość (M

D

)

Jak Intruz może wykorzystać paradoks
urodzinowy aby uzyskać podpis pod
wiadomością (M

Z

)?

2014-04-29

2

Atak urodzinowy na podpis

• Intruz generuje 2

n/2

wariantów (M

D

)

– Wszystkie mają takie same znaczenie jak P
– Generuje wartości f-cji skrótu: h(M

D,0

),h(M

D,1

),…

• Intruz generuje 2

n/2

wariantów M

z

– Wszystkie mają takie same znaczenie jak M

Z

– Obliczamy wartości skrótów: h(M

Z,0

),h(M

Z,0

),…

• Paradoks urodzin mówi nam, że dla pewnego j

oraz k otrzymamy h(M

D,j

)= h(M

Z,k

)

Atak urodzinowy na podpis

• Alicja podpisała niewinną petycję M

D,j

• Intruz ma [h(M

D,j

)]

Alicja

• Ale

[h( M

D,j

)]

Alicja

= [h(M

Z,k

)]

Alicja

• Alicja ‘nieroztropnie’ podpisała

szkodliwy donos M

Z,0

• Atak wykorzystuje tylko paradoks

urodzin

Aukcje online

• Niech Ala, Bolek, Czarek uczestniczą w aukcji
• Ala obstawia A, Bolek B i Czarek C

– Chcą zachować tajność stawek

• Rozwiązanie

– Ala, Bolek i Czarek zgłaszają

skróty

h(A),h(B),h(C)

– Skróty są zgłaszane elektronicznie online
– Następnie można ujawnić wartości A, B, C

• Skróty nie ujawniają wartości
• Nie można zmienić stawki po wysłaniu (brak

kolizji)

Aukcje online

• Protokół nie jest bezpieczny!
• Jest możliwy atak poszukiwania

wstecznego

– Bolek oblicza h(A) dla domniemanego A

• Jak zapobiec?
• Ala oblicza h(A,R), R – jest losowe

– Alicja musi ujawnić A oraz R
– Intruz nie jest w stanie sprawdzić wszystkich

A i R

Aukcje online

• Niech B = $1000 oraz Bolek zgłasza

h(B,R)

• Ujawniamy: A = $1 oraz C = $2
• Bolek chce zmienić swoją propozycję

na: B



= $3

• Bolek oblicza h(B



,R



) dla różnych R



aż

znajdzie h(B



,R



) = h(B,R)

– Jak wiele możliwości musi sprawdzić?
– Około 2

n

skrótów

Aukcje online

• Słaba odporność na kolizje –

dla każdego danego bloku x, znalezienie
takiego y różnego od x, dla którego H(y)=H(x)
nie jest wykonywalne na drodze obliczeń

• Odporność na kolizje –

znalezienie pary (x,y), że H(y)=H(x) nie jest
wykonywalne na drodze obliczeń

2014-04-29

3

Atak słabych kolizji

• Atak na kolizje dla zadanego skrótu wymaga

nakładu około 2

n

operacji

• Atak na dowolną kolizję wymaga jedynie

około 2

n/2

• Atak Nostradamusa rozwiązuje problem

kolizji przy tylko 2

n/2

skrótach

– np. w przypadku naszej aukcji online
– można wykorzystać np. dla skrótu Merkle-

Damgard

Przewidywanie przyszłości

• Intruz twierdzi, że potrafi przewidzieć przyszłość
• 1 stycznia 2014, ogłasza y, twierdząc, że y = h(x)

– Gdzie x jest kursem PLN/EUR w dniu 30.05.2014

• 1 czerwca 2014, Intruz ujawnia x takie, że y = h(x)

– I wszystko się zgadza … (x – jest kursem PLN/EUR w dniu

30.05.2014)

• Czy to dowodzi nadprzyrodzonych zdolności Intruza?

Przewidywanie przyszłości

• Intruz podaje wartość y
• Niech P będzie kursem PLN/EUR w dniu

30.05.2014

• Jeżeli Intruz nie potrafi przewidywać

przyszłości, to musi znaleźć takie S, że
y = h(P,S)

• Intruz może próbować 2

n

różnych skrótów S

– Lecz jest to pracochłonne
– Może da się szybciej?

Atak Nostradamusa

• Nostradamus (1503-1566)

– Niektórzy twierdzą, że potrafił przewidzieć

przyszłość

– Lecz można to sprawdzić jedynie w formie

retrospektywy

• Atak Nostradamusa

– Intruz może przewidzieć przyszłość
– Zamienia rząd problemu przepowiedni z 2

n

na 2

n/2

– Ma zastosowanie dla dowolnej funkcji skrótu

Merkle-Damgard

Atak Nostradamusa

• Obliczanie kolizji: praca rzędu 2



2

n/2

– Porównanie jednego zbioru z drugim

• Przygotować kolizję w inteligentny sposób
• Tak aby zdeterminować y – wartość skrótu
• Jeżeli zdefiniujemy P, możemy wymóc

wartość skrótu y

– Potrzeba nam określonego S

Struktura diamentu

• Wybieramy

losowo M

0

• Obliczamy
d

00

= f(IV,M

0

)

• oraz M

1

,…,M

7



Znajdujemy M

00

,M

01

dające kolizję:

d

10

= f(d

00

,M

00

) = f(d

01

,M

01

)



Kontynuujemy: y = d

30

– jest poszukiwanym

skrótem

2014-04-29

4

Atak Nostradamusa

• Obliczenia wstępne

– Oblicz wartości struktury diamentowej o

wysokości 2

k

– Wybierz y = d

k0

jako przepowiadany skrót

• Kiedy skrót ‘przepowiedni’ jest znany,

Intruz:

– Niech P będzie przepowiednią
– Wybiera losowo S



, gdzie (P,S



) jeden blok

– Aż do znalezienia takiego f(IV,P,S



)=d

0j

dla

pewnego j

Atak Nostradamusa

• Skoro tylko znajdzie S



– Przechodzi ścieżką od d

0j

do d

k0

• W przypadku prezentowanej struktury diamentu,

jeżeli Intruz odkrył, że
f(IV,P,S



) = d

02

• Wtedy h(P,S



,M

02

,M

11

,M

20

) = d

30

= y

– Przypominamy, że y jest skrótem przepowiedni

• Niech x = (P,S



,M

02

,M

11

,M

20

)

• Oraz x jest wartością przepowiedni:

– P jest kursem PLN/EUR w dniu 30.05.2014,
– S



,M

02

,M

11

,M

20

wartością losową uniemożliwiającą atak

przeszukania wstecz na ‚przepowiednię’

Atak Nostradamusa

• Jak kosztowny?
• Zakładając, że struktura diamentu ma wysokość

2

k

i funkcja skrótu ma wyjście n bitowe

- Z jednej stron mamy: 2



2

n/2

(2

k



1) ≈ 2

n/2+k+1

– Można zredukować do 2

n/2+k/2+1

- Z drugiej chcemy osiągnąć zysk wymiaru: 2

n



k

Atak Nostradamusa

• W celu zminimalizowania kosztu

przyrównajmy dwie wartości z
poprzedniego slajdu w celu znalezienia k

• Mamy n/2 + k/2 + 1 = n



k co daje

k = (n



4)/3

• Dla MD4 lub MD5, n = 128, więc k = 41
• Struktura diamentu o wysokości 2

41

• Ostateczny koszt ataku to 2

87

Nostradamus

• Atak wymierzony przeciw algorytmom

opartym na idei Merkle-Damgard

• Nie jest praktyczny dla funkcji 128-bit
• Ostatecznie korzystanie ze skrótu w

celu przekonania kogoś o czymś nie jest
tak bezpieczne jak się wydawać może …

RSA

• RSA

– Klucz publiczny

: (e,N)

– Klucz prywatny

: d

• Szyfrowanie M

C = M

e

(mod N)

• Deszyfrowanie C

M = C

d

(mod N)

2014-04-29

5

Ataki na implementacje RSA

• Ataki na implementacje RSA

– Nie ma ataków w sensie ścisłym na algorytm RSA

• Zależności czasowe

– Potęgowanie jest kosztowe obliczeniowo
– Wykorzystanie różnic w czasie obliczeń pojawiających

się dla różnych wykładników (kluczy prywatnych)

• Ataki na błędy

– Wstrzykiwanie błędów może spowodować ujawnienie

informacji o kluczu prywatnym

Potęgowanie modularne

• Ataki związane ze specyfiką potęgowania

modulo

• Dla zwiększenia wydajności implementacja

potęgowania modulo korzysta z pewnej
kombinacji:

– Powtarzania operacji podnoszenia do potęgi 2
– Chińskiego twierdzenia o resztach (Chinese

Remainder Theorem - CRT)

– Mnożenia Montgomery
– Okna przesuwnego (Sliding window)
– Mnożenia Karatsuba

Powtarzanie ^2

• Przykład potęgi modulo

–

5

20

= 95367431640625 = 25 mod 35

• Lepiej:

powtarzanie ^2

o 20 = 10100 (binarnie)
o (1, 10, 101, 1010, 10100) = (1, 2, 5, 10, 20)
o Czyli 2 = 1



2, 5 = 2



2 + 1, 10 = 2



5, 20 = 2



10

o 5

1

= 5 mod 35

o 5

2

= (5

1

)

2

= 5

2

= 25 mod 35

o 5

5

= (5

2

)

2



5

1

= 25

2



5 = 3125 = 10 mod 35

o 5

10

= (5

5

)

2

= 10

2

= 100 = 30 mod 35

o 5

20

= (5

10

)

2

= 30

2

= 900 = 25 mod 35

• Brak wielkich liczb + wzrost wydajności

– W tym przypadku, 5 kroków vs 20

Powtarzanie ^2

• Algorytm

// oblicz y = x

d

(mod N)

// gdzie binarnie 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

Okno przesuwne

• Problem czas vs pamięć dla algorytmu ^2
• Zamiast przetwarzać bit po bicie…
• … przetwarzane jest n bitów w jednym

kroku

– Wykorzystanie wcześniej obliczonych wartości

przechowywanych w pamięci

– Zazwyczaj n = 5

Chińskie Twierdzenie o resztach

• Jedno z zasadniczych twierdzeń, wiążące

własności liczby całkowitej n z własnościami jej
czynników w rozkładzie na iloczyn potęg liczb
pierwszych, jest twierdzenie noszące nazwę
chińskiego twierdzenia o resztach.

2014-04-29

6

Chińskie Twierdzenie o resztach

• Jeśli liczby całkowite dodatnie:

n1, n2, n3, ... , nk
są parami względnie pierwsze, zaś
a1, a2, a3, ... , ak
są dowolnymi liczbami całkowitymi, to istnieje
taka liczba całkowita a, że:

a ≡ a1(mod n1),
a ≡ a2(mod n2),
...........................
a ≡ ak(mod nk),

Chińskie Twierdzenie o resztach

• Chinese Remainder Theorem (CRT)
• Chcemy obliczyć:

C

d

(mod N) gdzie N = pq

• Dzięki CRT, możemy obliczyć C

d

mod p oraz q, a

potem “skleić” wynik

• Dwa dzielenia modulo rozmiaru N

1/2

– Zamiast pojedynczego o rozmiarze N

• CRT – daje możliwość znacznego przyspieszenia

obliczeń

Algorytm CRT

• Dane:
• C, d, N, p,q
• Szukane:

C

d

(mod N) gdzie N = pq

• Oblicz

d

p

= d (mod (p



1)) oraz d

q

= d (mod (q



1))

• A następnie a oraz b takie, że

a = 1 (mod p) oraz a = 0 (mod q)

b = 0 (mod p) oraz b = 1 (mod q)

Algorytm CRT

• Korzystając z wcześniej obliczonych wartości
• Obliczamy:

• następnie:

• Wynik:

oraz

oraz

Przykład CRT

• Niech N = 33, p = 11, q = 3 oraz d = 7

– Wtedy e = 3 (lecz jest zbędne w tym przykładzie)

• Oblicz

d

p

= 7 (mod 10) = 7 oraz d

q

= 7 (mod 2) = 1

• Oraz , a = 12, b = 22 spełniają warunki
• Niech C = 5

– Chcemy obliczyć C

d

= 5

7

(mod 33)

– Znajdź C

p

= 5 (mod 11) = 5 oraz C

q

= 5 (mod 3) = 2

– Następnie x

p

= 5

7

= 3 (mod 11), x

q

= 2

1

= 2 (mod 3)

• Sprawdź: 5

7

= 3



12 + 22



2 = 14 (mod 33)

CRT

• Sprawia wrażenie dużej „pracochłonności”
• Lecz jest wręcz przeciwnie dużym

“zyskiem”

– Daje możliwość 4-krotnego przyspieszenia

obliczeń

• Problemy?

– Czynniki p oraz q liczby N muszą być znane
– Czynniki te powinny być znane jedynie

właścicielowi klucza prywatnego!

2014-04-29

7

Ciąg dalszy (zastosowania)

Na następnym wykładzie