2014-03-26

1

Bezpieczeństwo

i ochrona danych

Algorytmy blokowe

tryby pracy

kryptoanaliza

Agenda

• Tryby pracy alg. blokowych
• Ataki na algorytmy blokowe

(na przykładzie algorytmu DES)

Tryby pracy algorytmów blokowych

Tryby pracy

• Elektroniczna książka kodowa ECB (ang. electronic

codebook)

• Każdy 64-bitowy blok tekstu jawnego jest kodowany

niezależnie z zastosowaniem tego samego klucza

• Zastosowania: bezpieczna transmisja pojedynczych

wartości

E

K

E

K

E

K

P

P1

P2

P3

C1

C2

C3

D

K

D

K

D

K

C

C1

C2

C3

P1

P2

P3

Tryb ECB

• C=E(P,K)
• Tekst jawny P

0

,P

1

,…,P

m

,…

• Najprostszy sposób wykorzystania

Szyfruj

Deszyfruj

C

0

= E(P

0

, K),

P

0

= D(C

0

, K),

C

1

= E(P

1

, K),

P

1

= D(C

1

, K),

C

2

= E(P

2

, K),…

P

2

= D(C

2

, K),…

• Dla ustalonego K – elektroniczna wersja książki

kodowej

• Nowa książka dla nowego klucza

Tryb ECB - Atak wytnij i wklej

• Tekst jawny

Alice digs Bob. Trudy digs Tom.

• Weźmy 64-bit bloki i znaki 8-bit ASCII:
P

0

= “Alice di”, P

1

= “gs Bob. ”,

P

2

= “Trudy di”, P

3

= “gs Tom. ”

• Kryptogram: C

0

,C

1

,C

2

,C

3

• Intruz ‘wycina i wkleja’ kryptogram: C

0

,C

3

,C

2

,C

1

• Otrzymujemy

Alice digs Tom. Trudy digs Bob.

2014-03-26

2

Tryby pracy

• Wiązania bloków zaszyfrowanych CBC (ang. cipher

block chaining)

• Dane wejściowe algorytmu szyfrującego stanowią XOR

następnych 64 bitów tekstu jawnego i poprzednich 64
bitów tekstu zaszyfrowanego

• Zastosowania: transmisja blokowa ogólnego

zastosowania, uwierzytelnienie

E

K

E

K

E

K

P

P1

P2

P3

C1

C2

C3







D

K

D

K

D

K

C

C1

C2

C3

P1

P2

P3







CBC

• Bloki tworzą łańcuch szyfrowania
• Losowa wartość IV jest konieczna do inicjacji

trybu CBC

• IV jest losowy, lecz nie musi być tajny

Szyfrowanie

Deszyfrowanie

C

0

= E(IV



P

0

, K),

P

0

= IV



D(C

0

, K),

C

1

= E(C

0



P

1

, K),

P

1

= C

0



D(C

1

, K),

C

2

= E(C

1



P

2

, K),…

P

2

= C

1



D(C

2

, K),…

CBC

• Identyczne bloki TJ dają różne postaci TT
• Atak ‘wytnij i wklej’ jest wciąż możliwy, ale

trudniejszy i pozostawia ślady

• Jeżeli C

1

jest zmienione na G wtedy

P

1



C

0



D(G, K), P

2



G



D(C

2

, K)

• Lecz P

3

= C

2



D(C

3

, K), P

4

= C

3



D(C

4

, K),…

• Automatyczny ‘powrót’ z błędów!

Tryby pracy - CFB

• Szyfrowanie ze

sprzężeniem

zwrotnym CFB

(ang. cipher

feedback)

• Dane wejściowe

przetwarzane są

po j bitów

• Zastosowania:

transmisja

strumieniowa

ogólnego

zastosowania,

uwierzytelnienie

Tryby pracy - OFB

• Sprzężenia

zwrotnego

wyjściowego OFB

(ang. output

feedback)

• Transmisja

strumieniowa przez

kanał narażony na

zakłócenia

Podwójny DES

• W związku z zagrożeniem załamania szyfrowanie DES z

kluczem 56 bitowym, pojawiły się propozycje

wielokrotnego użycia DES z wieloma kluczami

• Najprostsza wersja wielokrotnego DES to podwójny DES
• Przy danym tekście jawnym P i dwóch kluczach K1 i K2,

tekst zaszyfrowany C jest generowany jako C=E

K1

(E

K2

(P))

• Deszyfrowanie wymaga odwrócenia kolejności

zastosowania kluczy P=D

K2

(D

K1

(C))

E

K1

P

E

X

K2

C

D

K2

C

D

Y

K1

P

2014-03-26

3

Czy 2DES jest bezpieczny?

• Niech 2E( (k

1

,k

2

), m) = E(k

1

, E(k

2

, m) )

Atak: M = (m

1

,…, m

10

) , C = (c

1

,…,c

10

).

• Krok 1: zbuduj tablicę.
posortuj wg 2-giej kolumny
• Znajdź (k1,k2) takie, że

E(k

2

,m)=D(k

1

,c)

długość klucza= 112 bitów DES

m

E(k

2

,

⋅)

E(k

1

,

⋅)

c

k

0

= 00…00

k

1

= 00…01

k

2

= 00…10

⋮

k

N

= 11…11

E(k

0

, M)

E(k

1

, M)

E(k

2

, M)
⋮

E(k

N

, M)

2

56

pozycji

Atak typu Meet in the middle

Atak:M = (m

1

,…, m

10

) , C = (c

1

,…,c

10

)

• Krok 1: zbuduj tablicę.

• Krok 2: dla każdego k

∈{0,1}

56

sprawdź czy D(k, C) jest w 2-giej kolumnie

jeżeli tak, to E(k

i

,M) = D(k,C)

⇒ (k

i

,k) = (k

2

,k

1

)

m

E(k

2

,

⋅)

E(k

1

,

⋅)

c

k

0

= 00…00

k

1

= 00…01

k

2

= 00…10

⋮

k

N

= 11…11

E(k

0

, M)

E(k

1

, M)

E(k

2

, M)
⋮

E(k

N

, M)

Atak typu Meet in the middle

Czas = 2

56

log(2

56

) + 2

56

log(2

56

) < 2

63

<< 2

112

,

dla przestrzeni ≈ 2

56

Analogiczny atak na 3DES: Czas = 2

118

przestrzeń≈ 2

56

m

E(k

2

,

⋅)

E(k

1

,

⋅)

c

m

E(k

2

,

⋅)

E(k

1

,

⋅)

c

E(k

3

,

⋅)

Potrójny DES z dwoma kluczami

• Przy danym tekście jawnym P i dwóch kluczach K1 i K2,

tekst zaszyfrowany C jest generowany jako

C=E

K1

(D

K2

(E

K1

(P)))

• Deszyfrowanie wymaga odwrócenia kolejności

zastosowania kluczy P=D

K1

(E

K2

(D

K1

(C)))

E

K1

P

D

A

K2

C

E

K1

B

D

K1

C

E

B

K2

P

D

K1

A

Potrójny DES

• Przy danym tekście jawnym P i trzech kluczach K1, K2 i

K3 tekst zaszyfrowany C jest generowany jako

C=E

K1

(E

K2

(E

K3

(P)))

• Deszyfrowanie wymaga odwrócenia kolejności

zastosowania kluczy P=D

K1

(D

K2

(D

K3

(C)))

E

K1

P

E

A

K2

C

E

K3

B

D

K3

C

D

B

K2

P

D

K1

A

DESX

E : K × {0,1}

n

⟶ {0,1}

n

- algorytm blokowy

Niech EX

EX( (k

1

,k

2

,k

3

), m) = k

1

⨁ E(k

2

, m

⨁k

3

)

Dla DESX: długość klucza = 64+56+64 = 184 bit

… lecz istnieje „łatwy atak” rzędu 2

64+56

= 2

120

(jaki?)

Uwaga: k

1

⨁ E(k

2

, m) oraz E(k

2

, m

⨁k

1

) nic nie dają!!

2014-03-26

4

Ataki na algorytm DES

DES – atak brute force

msg = “The unknown messages is: XXXX … “

CT = c

1

c

2

c

3

c

4

Cel: znaleźć k

∈ {0,1}

56

takie, że DES(k, m

i

) = c

i

dla i=1,2,3

1997: Internet search -- 3 miesiące
1998: EFF (deep crack) -- 3 dni (250K $)
1999: combined search -- 22 godzin
2006: COPACOBANA (120 FPGAs) -- 7 dni (10K $)

⇒ 56-bitowe algorytmy nie powinny być używane!!

(128-bit key

⇒ 2

72

dni)

DES – atak brute force

• Dla danej pary (m,c) jest duże prawdopodobieństwo, iż tylko jeden

klucz k spełnia zależność

c = DES(m,k)

• Rozważmy DES jako kolekcję permutacji

π

(1)

… π

(2

56

)

.

• Jeżeli permutacje π

i

są niezależne, to



(m, k) :

Pr [



k

1

≠ k : DES(m, k

1

) = DES(m, k) ]

= 2

56

. 2

-64

= 2

-8

= 0.39%

• Dlatego dla określonej pary (m, c) klucz k jest określony

jednoznacznie.

• Aby odszyfrować wiadomość, trzeba znaleźć właściwy klucz.

DES – atak brute force

• Przegląd zupełny:

– Dla algorytmu blokowego n-bitowego z kluczem

o długości j-bitów, właściwy klucz może być
odnaleziony po około 2

j-1

próbach

– DES, j = 56 bit, n = 64 bit zatem przegląd zupełny

daje nam właściwy klucz po 2

55

operacjach

DES – atak brute force

• DES jest siecią Feistel dlatego:

DES(



m,



k) =



DES(m, k)

• Ta własność nazywa się własnością uzupełniania

(Complementation Property)

jeżeli c

1

= DES(m, k) oraz c

2

= DES(



m, k) wtedy gdy

DES(m, k

1

) ≠ c

1

ani



c

2

to k ≠ k

1

ani



k

1

• Przestrzeń poszukiwań jest zredukowana o połowę

Ataki czasowe (Timing Attacks)

• Wykorzystanie znanych zależności

czasowych pomiędzy wyjściem a wejściem
w kontekście zmiany tekstu jawnego i
klucza.

2014-03-26

5

Ataki analityczne

• Istnieje kilka analitycznych ataków na DES
• Wykorzystują wiedzę o strukturze algorytmu

– wykorzystują wiedzę z dostępnych kryptogramów
– umożliwiają odtworzenie części lub całych kluczy

poszczególnych rund

– pozostała część dostępna poprzez przegląd zupełny

• Ataki te wykorzystują pewne własności

statystyczne

• Przykłady

– Kryptoanaliza różnicowa
– Kryptoanaliza liniowa
– Atak na klucze zależne

Kryptoanaliza różnicowa

• Jedno z największych osiągnięć kryptoanalizy

współczesnej

• Znana od lat 70-tych

(powstała w kontekście projektu alg. DES)

• Murphy, Biham, Shamir – opublikowali jej

podstawy w 1990

• Mocna metoda analizy alg. blokowych
• Większość współczesnych algorytmów blokowych

poddana analizie

• DES jest względnie odporny

Kryptoanaliza różnicowa

• Statystyczny atak na algorytmy oparte na

sieci Feistel

• Funkcja F daje rezultaty zależne od

wejścia i od klucza

• Kryptografia różnicowa polega na

porównywaniu rezultatów dwóch
szyfrowań wykonanych z użyciem
określonej pary kluczy

Kryptoanaliza różnicowa

• Załóżmy, że mamy dwa bloki danych

wejściowych m oraz m'.

• Różnica dla tych danych wynosi m xor m'.
• Teksty mogą zostać wybrane losowo, ale różnice

pomiędzy nimi muszą spełniać określone
warunki.

• Stosując operację xor z bitami klucza (m xor k

oraz m' xor k ) otrzymujemy dane wejściowe do
S-boxów.

Kryptoanaliza różnicowa

• Funkcja rundy F(x,k

i

): {0,1}

32

x {0,1}

48

→ {0,1}

32

x (32 bits)

k

i

(48 bits)

48 bits

48 bits

32 bits

P

6 bits x 8

4 bits x 8

s

1

s

8

8 x S-boxes (4x16)
(podstawienie
– mieszanie)

P-box
(permutacja)
rozpraszanie

rozszerzenie

b

Kryptoanaliza różnicowa

• Rozważamy dowolną funkcję s-box F(x, k

i

) :

• Definiujemy miarę różnic na wejściu jako

Δ = b

1



b

2

= (x

1



k

i

)



(x

2



k

i

)

= x

1



x

2

• Wejście XOR (b

1



b

2

) nie zależy od klucza lecz

wyjście XOR (e

1



e

2

) już tak

S box

b

1

, b

2

(2x6 bits)

e

1

, e

2

(2x4 bits)

2014-03-26

6

Kryptoanaliza różnicowa

• Definiujemy zbiór Δ(b) złożony z uporządkowanych par (b

1

, b

2

) o

zadanej wartości XOR b:

Δ(b) = {(b

1

, b

2

) є {0,1}

6

| b

1



b

2

= b}

gdzie

| Δ(b) | = 2

6

= 64

• Na przykład dla b = 110100, jeżeli rozważamy pierwszy S-box pary

mogłyby być następujące

Δ(b) = {(000000,110100), (000001,110101), … (111111,001011)}







110100 110100 110100

Kryptoanaliza różnicowa

• Jeżeli wykonamy analizę dla wszystkich 64 par w Δ(b) wtedy

otrzymamy rozkład wyjściowych wartości XOR(e

1



e

2

) :

(e

1



e

2

)

0000 0001 0010 0011 … 1111

0

8 16 6 6

• Przypuśćmy, że (b

1



b

2

) = 110100 oraz (e

1



e

2

) = 0001, wtedy (b

1

,

b

2

) musi być jedną z ośmiu możliwych par, zatem b

1

jest jedną z 16

możliwych wartości.

• Skoro x

1

jest dane, 6 bitów klucza w funkcji XOR z x

1

daje b

1

czyli

jedną z 16 możliwych wartości.

• Proces jest powtarzany dla różnych Δ aby wywnioskować wartości

kolejnych bitów klucza.

Kryptoanaliza różnicowa

• (m xor k) xor (m' xor k) = m xor m'.
• Po przejściu przez S-boxy różnica (m xor k) xor

(m' xor k) ulega zmianie.

• Nowa różnica zależy nie tylko od m xor m', lecz

również od wartości klucza.

• Tylko niektóre wartości m xor k oraz m' xor k są

możliwe a co za tym idzie tylko niektóre
wartości samego k.

Kryptografia różnicowa

• Znając różnice wejścia poszukujemy

charakterystycznych różnic na wyjściu

Kryptoanaliza różnicowa

• Dla zadanego wejścia otrzymujemy

określone różnice na wyjściu z
prawdopodobieństwem p

• Jeżeli odnajdziemy przykłady dające

wyższe prawdopodobieństwo możemy
wnioskować o wartości klucza rundy

• Proces musimy powtarzać dla każdej rundy

Kryptoanaliza różnicowa

• Umożliwia atak na alg. DES rzędu 2

47

operacji z

użyciem 2

47

wybranych tekstów jawnych

• Atak przeszukania zupełnego rzędu 2

55

jest

bardziej ‘praktyczny’ gdyż nie wymaga

dodatkowej analizy, takiej jaka jest konieczna w

przypadku analizy różnicowej

2014-03-26

7

Kryptoanaliza liniowa

• Również metoda statystyczna
• Oparta na próbie określenia liniowego

przybliżenia przekształcenia szyfrującego DES

• Umożliwia skuteczny atak na DES z użyciem 2

47

znanych tekstów jawnych

• Praktycznie wciąż niewykonalne

Kryptoanaliza liniowa

• Rozważmy kryptogram otrzymany na podstawie klucza oraz

tekstu jawnego:

• Algorytm może być łatwo złamany, bo np.

c[1] = p[4]



p[17]



k[5]



k[3]

i.e. k[3]



k[5] = c[1]



p[4]



p[17]

• A to dlatego, iż algorytm posiada liniowe zależności

plaintext

key

cyphertext

Kryptografia liniowa

• Znajdź liniową aproksymację z

prawdopodobieństwem p != ½

Pr

[

m[i

1

]

⨁⋯⨁m[i

r

]

⨁

c[j

j

]

⨁⋯⨁c[j

v

]

=

k[l

1

]

⨁⋯⨁k[l

u

]

]

= ½ + ε

dla pewnego ε.

Dla DES, istnieje taka zależność dla ε = 1/2

21

≈ 0.0000000477

• Mamy liniową zależność dla bitów klucza
• Otrzymujemy pojedynczy bit klucza metodą

analizy największego prawdopodobieństwa

• Wymaga znacznej liczby szyfrogramów
• Efektywność metody wyznacza wartość: |p–½|

Kryptoanaliza liniowa

Pr

[

m[i

1

]

⨁⋯⨁m[i

r

]

⨁

c[j

j

]

⨁⋯⨁c[j

v

]

=

k[l

1

]

⨁⋯⨁k[l

u

]

]

=

½ + ε

dla danych 1/ε

2

losowych par (m, c=DES(k, m)) mamy

k[l

1

,…,l

u

] =

MAJ

[

m[i

1

,…,i

r

]

⨁

c[j

j

,…,j

v

]

]

z prawdopodobieństwem ≥ 97.7%

⇒ z 1/ε

2

parami we/wy można znaleźć

k[l

1

,…,l

u

]

w czasie ≈1/ε

2

.

Kryptoanaliza liniowa

Dla DES:
• ε = 1/2

21

⇒ z 2

42

we/wy parami możemy

znaleźć

k[l

1

,…,l

u

]

w czasie 2

42

• W przybliżeniu możemy znaleźć 14 bitów

klucza w czasie 2

42

• Pozostałe bity metodą „brute force”

56−14=42 w czasie 2

42

• Czas całego ataku ≈2

43

( << 2

56

) z 2

42

losowymi parami we/wy

Kryptoanaliza liniowa

Mała zależność liniowa w S

5

doprowadziła

do redukcji czasu ataku do poziomu 2

42

⇒ nie projektuj sam algorytmów
kryptograficznych!!
(zanim się tego dobrze nie nauczysz)

2014-03-26

8

Ataki „kwantowe”

Ogólny problem:

Niech f: X

⟶ {0,1} będzie funkcją.

Cel: znaleźć takie x

∈X że f(x)=1

Klasyczny komputer:

najlepszy ogólny algorytm poszukiwania = O( |X| )

Komputer kwantowy:

czas poszukiwania rozwiązania

= O( |X|

1/2

)

Przeszukiwanie zupełne (kwantowe)

Dane m, c=E(k,m)
Definiujemy:

Grover

⇒ komputer kwantowy może znaleźć k w czasie O( |K|

1/2

)

DES: ≈2

28

, AES-128: ≈2

64

Jak pozostać bezpiecznym?

komputer kwantowy

⇒ algorytm z kluczem 256-bit (np. AES-256)

1

if E(k,m) = c

0 if not

f(k) =

Kryptoanaliza algebraiczna

• Ataki te mogą być stosowane zarówno przeciwko

blokowym szyfrom symetrycznym jak i szyfrom
strumieniowym.

• Metodę tą zaproponowali polscy kryptolodzy

Courtois i Pieprzyk.

• Polega ona na przedstawieniu algorytmu w

postaci zbioru równań a następnie na ich
rozwiązaniu.

Kryptoanaliza algebraiczna

• Atak ten skuteczny jest między innymi dla najnowszego

standardu szyfrowania symetrycznego -- AES.

• Wykazano, że liczba operacji wymaganych do złamania

tego algorytmu nie rośnie wykładniczo jako funkcja
liczby rund.

• Proponowany atak może być lepszy niż atak

wyczerpujący i tak atak dla algorytmu AES-128 wyniósłby
2

100

, natomiast dla algorytmu Serpent 2

143

• W ataku tym należałoby użyć jednej pary blok z tekstem

jawnym -- blok z tekstem zaszyfrowanym.

• Metoda ta skuteczna jest również dla szyfrów

strumieniowych.

Ataki na implementację

1. Ataki typu side channel

– Pomiar czasu szyfrowania/deszyfrowania, pomiar poboru mocy

szyfrowania/deszyfrowania

2. Analiza błędów:

– Błędy obliczeniowe w trakcie ostatniej rundy ujawniają tajny klucz

⇒ nie implementuj nigdy algorytmów samodzielnie…

[Kocher, Jaffe, Jun,
1998]

smartcard

Dziękuję za uwagę