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ę