2014-04-15
Agenda
" Funkcje jednokierunkowe
Bezpieczeństwo
" Podpis elektroniczny
i ochrona danych
" Wybrane algorytmy skrótu
 MD5, SHA
" Ataki na funkcje skrótu i podpisy
Jednokierunkowe funkcje
elektroniczne
skrótu i ich zastosowania
" Algorytmy wymiany klucza
Funkcja jednokierunkowa z
Funkcja jednokierunkowa
bocznym wejściem
" Stworzenie praktycznego systemu szyfrowania asymetrycznego z
" Obliczenie funkcji jednokierunkowej z bocznym
kluczem jawnym wymaga zastosowania funkcji jednokierunkowej
wejściem jest łatwe w jednym kierunku, a niewykonalne
z bocznym wejściem (ang. trapdoor one-way function)
w drugim, chyba że są znane pewne dodatkowe
informacje, które umożliwiają obliczenie odwrotności w
" Funkcja jednokierunkowa to taka, która przekształca swoją
dziedzinę na przedział w taki sposób, że każda wartość funkcji ma czasie wielomianowym
tylko jedną odwrotność, z tym że obliczenie funkcji jest łatwe
" Y=fk(X) - łatwe przy znajomości k i X
(czas wielomianowy), a obliczenie odwrotności niewykonalne
(wysiłek obliczeniowy rośnie szybciej niż wielomianowo): " X=fk-1(Y) - łatwe przy znajomości k i Y
" X=fk-1(Y) - niewykonalne, gdy znamy Y, a nie znamy k
 Y=f(X) - łatwe
 X=f-1(Y) - niewykonalne
Wymagania dla kryptograficznej
Algorytmy skrótu
funkcji skrótu
" Funkcja skrótu z danych o zmiennym rozmiarze wylicza
" H(x) można zastosować do dowolnej wielkości
pewien wynik H(M) o stałym rozmiarze, zwany też
bloku danych
wyciągiem lub skrótem komunikatu
" H(x) tworzy dane wyjściowe o ustalonej
" Wynik skrótu jest funkcją wszystkich bitów komunikatu i
długości
zapewnia:
 wykrywanie błędów,
 uwierzytelnianie (w pewnych warunkach)
" H(x) jest łatwo obliczyć dla każdego x, co
ułatwia implementację sprzętową i
programową
1
2014-04-15
Wymagania dla kryptograficznej
Skrót niekryptograficzny (1)
funkcji skrótu
" Dla każdego kodu m znalezienie takiego x, że H(x)=m
" Dane: X = (X0,X1,X2,& ,Xn-1), Xi są bajtami
nie jest wykonywalne na drodze obliczeń 
jednokierunkowość
" Niech hash(X) = X0+X1+X2+& +Xn-1
" Czy jest to bezpieczne?
" Dla każdego danego bloku x, znalezienie takiego y
" Przykład: X = (10101010,00001111)
różnego od x, dla którego H(y)=H(x) nie jest
wykonywalne na drodze obliczeń  słaba odporność na
" Skrót:10111001
kolizje
" Ale również jest to skrót
Y = (00001111,10101010)
" Znalezienie pary (x,y), że H(y)=H(x) nie jest
wykonywalne na drodze obliczeń  (silna) odporność na " A
atwo znalez
ć kolizję, więc nie jest
kolizje
bezpieczne&
Skrót niekryptograficzny (3)
Skrót niekryptograficzny(2)
" Dane: X = (X0,X1,X2,& ,Xn-1)
" Cyclic Redundancy Check (CRC)
" Niech skrót będzie następujący:
" CRC jest resztą z dzielenia
h(X) = nX0+(n-1)X1+(n-2)X2+& +1��Xn-1
" Dobre dla wykrywania błędów
" Czy jest bezpieczny?
h(10101010,00001111)ą�h(00001111,10101010) " A
atwe znalezienie kolizji
" Lecz skrót (00000001,00001111) jest taki sam
" CRC czasami, przypadkowo pojawia się w
jak skrót (00000000,00010001)
kontekście bezpieczeństwa (WEP)
" Nie jest bezpieczny, lecz wykorzystywany w
niekrytycznych aplikacjach np. rsync
Notacja klucza publicznego
Popularne funkcje
" MD5 �� opracowane przez Rivest a " Podpis Alicji dla wiadomości M
 128 bit wyjście
prywatnym kluczem: [M]Alicja
 MD5  wykryto kolizje
" Szyfrowanie wiadomości M
" SHA-1 �� standard rządu US (podobne do
kluczem publicznym: {M}Alicja
MD5)
" Wtedy:
 160 bit wyjście
{[M]Alicja}Alicja = M
 również uważana za mało bezpieczne rozwiązanie
" Wiele innych, lecz MD5 oraz SHA-1 są
[{M}Alicja]Alicja = M
najpopularniejsze
2
2014-04-15
Zastosowania funkcji skrótu:
Podpisy elektroniczne
Podpis elektroniczny
" Przypuśćmy, że Alicja podpisała M
" MAC - Message Authentication Code,
 Alicja wysyła M oraz S = [M]Alicja do Boba
także MIC - Message Integrity Code
 Bob weryfikuje, że M = {S}Alicja
 to w kryptografii kod służący uwierzytelnieniu
" Jeżeli M jest duże, [M]Alicja jest kosztowne danych.
obliczeniowo  argumentami funkcji uwierzytelniającej są tajny
klucz oraz wiadomość.
" Przypuśćmy natomiast, że Alicja podpisuje
 wartością wyjściową funkcji jest kod MAC.
h(M), gdzie h(M) jest mniejsze niż M
 Alicja wysyła M oraz S = [h(M)]Alicja do Boba
 Bob sprawdza czy h(M) = {S}Alicja
Podpisy elektroniczne Podpisy elektroniczne
" HMAC " Podpis elektroniczny zapewnia ochronę
keyed-Hash Message Authentication Code integralności
 MAC z kluczem tajnym zapewniający zarówno  Podobnie jak MAC oraz HMAC
ochronę integralności jak i autentyczności
" Dlaczego?
danych.
" Alicja wysyła M oraz S = [h(M)]Alicja do Boba
 Standardowy kod MAC zapewnia ochronę
integralności ale może podlegać sfałszowaniu jeśli " Jeżeli M będzie zmienione an Mó� lub S
nie jest zabezpieczony dodatkowym
zmienione na Só� (przypadkowo lub celowo)
mechanizmem chroniącym jego autentyczność
Bob wykryje to :
(np. podpisem cyfrowym).
h(Mó�) ą� {S}Alicja, h(M) ą� {Só�}Alicja, h(Mó�) ą�
{Só�}Alicja
Niezaprzeczalność Niezaprzeczalność
" Alicja zamawia 100 laptopów u Boba
" Podpis elektroniczny zapewnia
" Alicja oblicza MAC korzystając z klucza
niezaprzeczalność
symetrycznego
" Alicja wysyła M oraz S = [h(M)]Alicja do Boba
" Znajduje tańszą ofertę, Alicja twierdzi, że nie
" Alicja nie może  wyprzeć się podpisu
składała zamówienia
 Alicja nie może obronić twierdzenia, że nie
" Czy Bob może udowodnić Alicji kłamstwo?
podpisała M
" Nie! Ponieważ Bob również zna klucz
" Jak to działa?
symetryczny, mógł zatem sfałszować zamówienie
" Czy tak samo jak dla MAC?
" Problem: Bob wie, że Alicja złożyła zamówienie
i nie może tego udowodnić
3
2014-04-15
Niezaprzeczalność
Skróty i podpisy
" Alicja podpisuje h(M), wysyła M oraz
" Alicja zamawia 100 laptopów u Boba
S = [h(M)]Alicja do Boba oraz Bob weryfikuje
" Alicja podpisuje zamówienie korzystając z
h(M) = {S}Alicja
klucza prywatnego
" Bezpieczeństwo zależy od bezpieczeństwa
" Znajduje tańszą ofertę, Alicja twierdzi, że
kryptosystemu klucza publicznego i od
nie składała zamówienia
bezpieczeństwa funkcji skrótu
" Czy Bob może udowodnić Alicji kłamstwo?
" Niech Intruz znajdzie kolizję: Mó�ą� M taką, że
" Tak! Tylko ktoś kto zna klucz prywatny Alicji
h(Mó�) = h(M)
mógł złożyć podpis
" Wtedy Intruz może zamienić M na Mó� i
" Jeżeli nikt go nie ukradł Alicji to jest jedną
schemat podpisu jest złamany
osobą, która mogła to zrobić
Projekt kryptograficznej funkcji
Projekt kryptograficznej funkcji
skrótu
skrótu
" Pożądana własność: efekt lawinowy
" Dane wejściowe rozbijane na bloki
 Zmiana dowolnego bitu powoduje zmianę około
" Kompresja stosowana względem bloków
dużej liczby bitów skrótu
" Kryptograficzne funkcje skrótu składają się z
" Wartość bloku zależna od obecnej
kilku rund (analogicznie jak algorytmy
wartości i od wyjścia poprzedniej rundy
blokowe w trybie CBC)
 Wyjście z ostatniej rundy jest wartością
" Potrzebujemy bezpieczeństwa i prędkości
skrótu
 Efekt lawinowy po kilku rundach
" Dla funkcji skrótu rozważamy:
 Lecz runda musi być prosta
 Rozmiar bloku 512 bit
 Kompresja bloku wyjściowego 128 bit
Funkcja skrótu
Funkcje skrótu: ciekawostki
" Wejście lub
" Jeżeli wiadomość jest długości pojedynczego
 wiadomości w bloku 512-bit : h(M) = f(IV,M) gdzie f oraz IV
znane Intruzowi
blokach
" Dla 2 bloków:
M0,M1,& ,MN-�1
h(M) = f(f(IV,M0),M1) = f(h(M0),M1)
" Dodatkowo mod 232
" Ogólnie
na 32-bit słowie
h(M) = f(h(M0,M1,& ,Mn-�2),Mn-�1)
" Schemat Merkle-
 Jeżeli h(M) = h(Mó�) wtedy h(M,X) = h(Mó�,X) dla
Damgard
dowolnego X
4
2014-04-15
HMAC
Jak obliczyć HMAC?
" MAC: algorytm blokowy dla integralności
" Czy mamy obliczać HMAC jako h(K,M) ?
 Czy możemy użyć funkcji skrótu?
" Skróty obliczane w blokach
"  hashed MAC , HMAC, wiadomości M z
" Przypominamy: h(M0,M1) = F(h(M0),M1)
kluczem K
" Niech Mó� = (M,X)
 Dlaczego potrzebujemy klucza?
 Wtedy h(K,Mó�) = F(h(K,M),X)
" Jak obliczyć HMAC?
 Intruz może obliczyć HMAC z Mó� bez
 Dwa oczywiste podejścia:
znajomości K
h(K,M) and h(M,K)
 Kompromituje to HMAC
" Które (czy w ogóle) jest lepsze?
Jak obliczyć HMAC? Właściwy sposób na HMAC
" Czy powinniśmy obliczać HMAC jako
" Opisany w RFC 2104
h(M,K) ?
" Niech B będzie długością w bajtach bloku
 Lepsze niż h(K,M) ? funkcji skrótu
" Dla popularnych funkcji B = 64
" Jeżeli h(Mó�) = h(M) wtedy
 SHA-1, MD5, Tiger, etc.
h(M,K) = F(h(M),K) = F(h(Mó�),K) = h(Mó�,K)
" Definiujemy
" W tym przypadku, Intruz nie może
ipad = 0x36 (00110110) powtarzany B razy
obliczyć HMAC bez znajomości K
opad = 0x5C (01011100) powtarzany B razy
 Lecz musi znać kolizje
" Wtedy
 Lepsze niż h(K,M), lecz wciąż może być
HMAC(M,K) = H(K��opad, H(K��ipad, M))
lepiej
Algorytm MD5 Dodawanie bitów dopełniających
" Algorytm MD5 (ang. Message Digest) został opracowany " Komunikat jest dopełniany tak, by jego długość w bitach
przez Rona Rivesta i opublikowany jako RFC1321 przystawała do 448 modulo 512
" Algorytm z wejściowego komunikatu o dowolnej długości " Czyli długość komunikatu musi być o 64 bity mniejsza niż
generuje 128-bitowy skrót całkowita wielokrotność 512 bitów
" Dane wejściowe przetwarzane są w 512 bitowych " Na przykład jeżeli komunikat ma 2345 bitów to
blokach najbliższa wielokrotność 512 bitów to 2560, więc
komunikat zostanie dopełniony do 2496 bitów
" Przykład działania
" Dopełnienie dodaje się zawsze, nawet gdy komunikat ma
" MD5("Ala ma kota") =
żądaną długość
91162629d258a876ee994e9233b2ad87
" Dopełnienie składa się z bitu 1, po którym następuje
" MD5("Ala ma koty") =
odpowiednia liczba bitów 0
6a645004f620c691731b5a292c25d37f
5
2014-04-15
Dodanie długości komunikatu Inicjalizacja bufora MD
" Do komunikatu uzupełnionego o dopełnienie dodaje się " Do przechowywania pośrednich i końcowych wartości
64-bitową reprezentację długości pierwotnego funkcji skrótu stosuje się bufor 128-bitowy
komunikatu w bitach (przed dopełnieniem)
" Bufor ten można zapisać jako cztery 32-bitowe rejestry
" Jeżeli komunikat jest dłuższy niż 264 to używa się tylko oznaczane jako A, B, C, D
młodszych 64 bitów długości
" Rejestry te są na początku inicjalizowane następującymi
" To oznacza, że pole długości zawiera długość wartościami szesnastkowymi (najpierw młodsze oktety):
początkowego komunikatu modulo 264
A=01234567
" Następnie cały komunikat wraz z dopełnieniem i
B=89ABCDEF
długością jest przetwarzany w blokach Y0, Y1,...,YL-1, o
C=FEDCBA98
długości 512 bitów
D=76543210
Przetwarzanie komunikatu w 512-
Generowanie wyciągu w MD5
bitowych blokach Yq MDq
512 128
Długość
Dopełnienie komunikatu " Wszystkie 4 etapy mają
64 32
(1-512) bitów
(K mod 2 )
podobną strukturę, lecz każdy
A B C D
L x 512 bitów=N x 32 bity
fF (ABCD,Yq,T[1,...,16])
korzysta z innej elementarnej
K bitów
funkcji logicznej oznaczanej w
A B C D
Komunikat 100...0
fG (ABCD,Yq,T[17,...,32])
specyfikacji jako F, G, H, I
A B C D
" W każdym etapie jest
fH (ABCD,Yq,T[33,...,48])
przetwarzany aktualny blok Yq
512 bitów 512 bitów 512 bitów 512 bitów
A B C D
oraz bufor ABCD (MDq)
fI (ABCD,Yq,T[49,...,64])
Y Y . . . Y . . . Y
0 1 q L-1
" Dodatkowo w każdym etapie
512 512 512 512
korzysta się z kolejnych części
tablicy T[1,...,64]
128 128 128 128
H H H H + + + +
ABCD MD5 MD5 MD5 MD5
skonstruowanej na podstawie mod 232 mod 232 mod 232 mod 232
funkcji sinus
128
128 bitowy wyciąg MDq+1
Elementarna operacja MD5 Elementarna operacja MD5
A B C D
" Indeksy k do tablicy X oraz wartość przesunięcia s jest
" Każdy z kroków wykonywanych 64
zdefiniowana w RFC1321
g
razy dla każdego bloku ma postać
" Elementarna operacja MD5 może być zapisana jako
AŹ�B+CLSs(A+g(B,C,D)+X[k]+T[i])
+ [ABCD k s i]
32
mod 2
" Przez g oznaczamy jedną z funkcji
" Dla etapów 1-16 A=B+CLSs(A+F(B,C,D)+X[k]+T[i])
elementarnych F, G, H, I
+
32 X[k]
" X[k] oznacza k-te 32 bitowe słowo mod 2
[ABCD k s i] [DABC k s i] [CDAB k s i] [BCDA k s i]
w przetwarzanym 512-bitowym
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
bloku
+
32 T[i]
mod 2
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
" T[i] oznacza i-te 32 bitowe słowo w
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
tablicy stałych
CLS [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]
s
" Wszystkie dodawania są
+
realizowane modulo 232 32
mod 2
6
2014-04-15
Funkcje elementarne Algorytm SHA
" Algorytm SHA (ang. Secure hash algorithm) został
stworzony przez Narodowy Instytut Standardów i
F(B, C,D) =� (B��C) �� (B�� D) G(B, C,D) =� (B�� D) �� (C �� D)
Technologii USA (NIST) i opublikowany jako FIPS PUB
H(B, C,D) =� B �� C �� D I(B, C,D) =� C �� (B�� D) 180 w 1993 roku
" Algorytm z wejściowego komunikatu o długości
bity Funkcje bity Funkcje
elementarne elementarne mniejszej niż 264 bity generuje 160-bitowy wyciąg
B C D F G H I B C D F G H I
" Dane przetwarzane są w 512 bitowych blokach
0 0 0 0 0 0 1 1 0 0 0 0 1 1
" Od 2001 powstały cztery warianty określane jako SHA-2
0 0 1 1 0 1 0 1 0 1 0 1 0 1
0 1 0 0 1 1 0 1 1 0 1 1 0 0 (SHA-224, SHA-256, SHA-384, SHA-512)
0 1 1 1 0 0 1 1 1 1 1 1 1 0
" Ponieważ w 2004 zgłoszono udane ataki na funkcje
skrótu mające strukturę podobną do SHA-1 NIST ogłosił,
że do 2010 zaprzestanie stosować SHA-1 na rzecz
różnych wariantów SHA-2
Generowanie skrótu w SHA Generowanie skrótu w SHA Długość
Dopełnienie komunikatu
(1-512) bitów (K)
L x 512 bitów=N x 32 bity
" Dodawanie bitów dopełniających
K bitów (<264 bitów)
" Dodanie długości komunikatu , długość musi być mniejsza
Komunikat 100...0
niż 264
" Inicjalizacja 160-bitowego bufora MD
512 bitów 512 bitów 512 bitów 512 bitów
A=67452301 B=EFCDAB89 C=98BADCFE
Y0 Y1 . . . Yq . . . YL-1
D=10325476 E=C3D2E1F0
512 512 512 512
" Przetwarzanie komunikatu w blokach 512-bitowych
" Otrzymanie wyniku
160 160 160 160
HSHA HSHA HSHA HSHA
ABCDE
160 bitowy wyciąg
Przetwarzanie komunikatu w 512-
Elementarna operacja SHA
Yq MDq
bitowych blokach
A B C D E
512 160
" Każdy z etapów wykonywanych
" Podstawowym elementem
32
80 razy dla każdego bloku ma
algorytmu jest przetwarzanie f
A B C D E t +
32
postać mod 2
ETAP0 (ABCDE,Yq,K0)
bloku 512 bitowego za pomocą
A, B, C, D, E Ź�
A B C D E
80 podobnych etapów
(CLS5(A)+ft(B,C,D)+E+Wt+Kt), A,
ETAP1 (ABCDE,Yq,K1) +
32
CLS5
mod 2
" W każdym etapie jest CLS30(B), C, D
przetwarzany aktualny blok Yq " Przez ft oznaczamy jedną z
+
CLS30 32 Wt
A B C D E funkcji elementarnych
mod 2
oraz bufor ABCDE (MDq)
ETAP79 (ABCDE,Yq,K79)
" Wt oznacza 32 bitowe słowo w
" Dodatkowo w każdym etapie
przetwarzanym 512-bitowym
+
32
Kt
korzysta się z zdefiniowanej mod 2
bloku
stałej addytywnej Kt: 0Ł�tŁ�19
" Kt to zdefiniowana stała
+ + + + +
A B C D E
mod 232 mod 232 mod 232 mod 232 mod 232
160
MDq+1
7
2014-04-15
Tworzenie sekwencji danych
Funkcje elementarne
wejściowych
0 Ł� t Ł�19 ft (B, C,D) =� (B��C) �� (B �� D) " Wt oznacza 32 bitowe słowo z przetwarzanego 512-
bitowym bloku
20 Ł� t Ł� 39 ft (B, C,D) =� B �� C �� D
" Pierwsze 16 wartości Wt otrzymuje się bezpośrednio z
aktualnego bloku 512-bitowego
40 Ł� t Ł� 59 ft (B, C,D) =� (B��C) �� (B�� D) �� (C �� D)
" Pozostałe wartości są definiowane według
Wt=Wt-16��Wt-14��Wt-8��Wt-3
60 Ł� t Ł� 79 ft (B, C,D) =� B �� C �� D
512 bitów
W0 W2 W8 W13 Wt-16 Wt-14 Wt-8 Wt-3 W63 W65 W71 W13
Yq
XOR XOR XOR
32 32 32
32 32 32
. . . . . . . . .
W0 W1 W15 W16 Wt W79
Porównanie MD5 i SHA
Porównanie MD5 i SHA
MD5 SHA
" Bezpieczeństwo  SHA daje dłuższy skrót, co zapewnia
większe bezpieczeństwo
Długość skrótu 128 bitów 160 bitów
" Szybkość  oba algorytmy działają podobnie. Jednak
ponieważ SHA ma dłuższy bufor działa około 25% wolniej
Podstawowa jednostka 512 bitów 512 bitów
niż MD5
przetwarzania
" Prostota i poręczność  SHA posiada prostszą strukturę
Liczba kroków 64 80
" Architektura  MD5 interpretuje komunikat jako
Maksymalny rozmiar �� 264
sekwencje 32-bitowych słów zapisanych w architekturze
komunikatu
 little-endian , SHA stosuje architekturę  big-endian
Elementarne funkcje logiczne 4 3
Zastosowanie stałych 64 4
addytywnych
Bezpieczeństwo SHA Najważniejsze cechy SHA-256
" Złożoność obliczeniowa ataku metodą brutalnej siły dla
" SHA-256 daje skrót w długości 256 bitów co podnosi
wykrycia kolizji (wykrycie dwóch wiadomości, których
znacznie bezpieczeństwo skrótu
wynikiem jest ta sama funkcja skrótu) wynosi dla SHA
" Dane wejściowe przetwarzane są w 512 bitowych
280
blokach
" Kryptologom udało się opracować atak, którego
złożoność obliczeniowa wynosi 269 " Generalna zasada działania SHA-256 jest bardzo podobna
do MD5 i SHA
" W związku z tym pojawiły się wątpliwości co do
bezpieczeństwa wielu systemów kryptograficznych
" Zastosowano inne funkcje na etapie przetwarzania
używających SHA (np. system podpisu elektronicznego)
pojedynczych 512-bitowych bloków
" Narodowy Instytut Standardów i Technologii (NIST)
zaproponował zastąpienia szeroko używanej funkcji
haszującej SHA-1 silniejszą i mocniejszą funkcją SHA-
256 lub SHA-512
8
2014-04-15
Najważniejsze cechy SHA-512 SHA-3 - Algorytm Keccak
" SHA-512 daje 512 bitowy skrót. Dane wejściowe
przetwarzane są w 1024 bitowych blokach
" Komunikat jest dopełniany tak, by jego długość w bitach
przystawała do 896 modulo 1024
" Odpowiednio jak dla SHA-256 wprowadzono nowe
funkcje przetwarzające dane
Architektura gąbki
SHA-3 - Algorytm Keccak SHA-3 - Algorytm Keccak
SHA-3 - Algorytm Keccak
Dziękuję za uwagę
9