Konspekt:
Funkcje skrótu
Autorzy: Grzegorz Dębiec, Edyta Gąsior, A
ukasz Krzanik, Maciej Tokarczyk DUMF
1
STRESZCZENIE
Konspekt powstał na podstawie wykładu z przedmiotu  Bezpieczeństwo i ochrona informa-
cji , prowadzonego przez dr inż. Mirosława Hajdera.
Omówione zostały tutaj funkcje skrótu z kluczem, bez klucza oraz ataki na funkcje skrótu.
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
2
SPIS TREÅšCI
Streszczenie .................................................................................................................................. 1
1. Funkcje skrótu .......................................................................................................................... 3
2. Funkcje skrótu bez klucza ........................................................................................................ 4
3. Funkcje skrótu z kluczem ......................................................................................................... 6
4. Metody ataku na funkcje skrótu ............................................................................................... 7
4.1 Atak Yuvala.................................................................................................................. 7
4.2 Ataki łańcuchowe ......................................................................................................... 7
4.3 Ataki wykorzystujące właściwości szyfru.................................................................... 8
Literatura ...................................................................................................................................... 8
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
3
1. FUNKCJE SKRÓTU
Funkcję h nazywamy funkcją skrótu, jeśli ma co najmniej trzy właściwości:
" Właściwość kompresji  h przekształca wejście x o dowolnej długości liczonej w bitach na
wyjście h(x) o ustalonej długości n,
" Właściwość łatwości obliczeń  dla danej funkcji h i wejścia x wartość h(x) jest łatwo obli-
czalna (w czasie wielomianowym),
" Jednokierunkowość  dla prawie wszystkich wartości jest obliczeniowo trudne znalezienie
argumentu dającego jako skrót tę wartość.
Dla funkcji skrótu bez klucza określa się dwie potencjalne właściwości:
" Słaba odporność na kolizje  jest obliczeniowo trudne znalez
ć drugi argument, który daje
taki sam skrót jak dowolnie wyspecyfikowany argument,
" Odporność na kolizje  jest obliczeniowo trudne znalez
ć dwa różne argumenty m, m dające
ten sam skrót, czyli takie że h(m) = h(m ).
Jednokierunkowa funkcja skrótu albo słabo jednokierunkowa funkcja skrótu jest to funkcja
skrótu h mająca dodatkowo własność słabej odporności na kolizje.
Funkcja skrótu odporna na kolizje albo silnie jednokierunkowa funkcja skrótu to funkcja
skrótu h mająca dodatkowo dwie właściwości:
" Słaba odporność na kolizje,
" Odporność na kolizje
Ze względów funkcjonalnych wyróżnia się dwie klasy funkcji skrótu:
" MDC  podklasę funkcji skrótu bez klucza,
" MAC  podklasę funkcji skrótu z kluczem.
Rys.1 Funkcja skrótu
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
4
MAC jest to rodzina funkcji hk, sparametryzowana za pomocą klucza tajnego k o następujących
właściwościach:
" A
atwość obliczeń  dla znanej funkcji hk, dla danego k i danego m skrót hk(m) jest łatwo
obliczalny.
" Kompresja  hk odwzorowuje wejście m o dowolnej długości w bitach na wyjście hk(m) o
ustalonej długości n bitów.
2. FUNKCJE SKRÓTU BEZ KLUCZA
Ze strukturalnego punktu widzenia funkcje skrótu bez klucza można podzielić następująco:
" Takie, w których budowie wykorzystuje się szyfry blokowe,
" Zaprojektowane wyłącznie do wyznaczania skrótu.
" Takie, których działanie polega na wykorzystaniu operacji arytmetyki modularnej.
Typowe konstrukcje MDC zbudowanych za pomocą szyfrów blokowych pokazano na poniż-
szym rysunku:
Rys. 2 Schematy funckji skrótu wykorzystujących szyfry blokowe: a) Daviesa-
Meyera, b) Matyasa-Meyera-Oseasa, c) Miyaguchi_Preneela
Funkcja v rozszerza słowo wejściowe do rozmiaru klucza szyfru E.
W celu zwiększenia długości skrótu stosuje się schematy funkcji skrótu podwójnej długości.
MDC-2 jest funkcją MDC wymagającą dwóch operacji szyfru blokowego (schemat Matyasa-
Meyera-Oseasa) przypadajÄ…cych na blok.
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
5
Rys. 3 Funkcja skrótu MDC - 2
MD5.
Funkcja skrótu MD5 przekształca ciąg znaków o dowolnej długości w 128-bitowy skrót. Algo-
rytm MD5 jest wzmocnionÄ… wersjÄ… MD4. Dla MD5 nie znaleziono dotÄ…d kolizji, ale znaleziono
kolizje dla funkcji kompresji algorytmu MD5.
SHA-1.
Funkcja skrótu SHA-1 opracowana przez Krajowy Instytut Standardów i Technologii USA
(NIST), jest innym niż MD5 rozwinięciem algorytmu MD4. Główne cechy SHA-1 są następu-
jÄ…ce:
" Skrót ma 160 bitów i używa się pięciu zmiennych.
" Funkcja kompresji jest obliczana w czterech rundach, z użyciem funkcji f, g i h w następu-
jący sposób: f w pierwszej rundzie, g  w trzeciej, natomiast h  w drugiej i czwartej. W
każdej rundzie jest wykonywanych 20 kroków.
" Wewnątrz funkcji kompresji każdy 16-słowowy blok wiadomości jest rozszerzany do bloku
80-słowowego w procesie, w którym każdy z ostatnich 64 spośród 80 słów są dodawane
modulo 2 do 4 słów na poprzednich pozycjach w rozszerzonym bloku. Te 80 słów stanowi
wejście dla każdego z 80 kroków (jedno słowo na krok).
" W kroku zasadniczym jedynÄ… stosowanÄ… rotacjÄ… jest rotacja 5-bitowa; piÄ…ta zmienna robo-
cza jest dodawana do wyniku każdego kroku. Słowa wiadomości rozszerzonego bloku wia-
domości są wykorzystywane sekwencyjnie.
" W SHA-1 używa się czterech niezerowych dodatnich stałych.
160-bitowa funkcja SHA-1 zapewnia zwiększoną odporność na atak poprzez wyczerpujące
przeszukiwanie (atak brutalny). Redundancja wprowadzona w przetwarzaniu wstępnym zwięk-
szyła zdecydowanie odporność na atak.
RIPEMD-160.
Funkcja kompresji tego algorytmu RIPEMD-160 przekształca 21-słowowe wejście (5 zmien-
nych i 16-słowowy blok wiadomości, słowa 32-bitowe) na 5-słowowe wyjście. Każdy blok
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
6
wejściowy jest przekształcany równolegle przez różne wersje (sekwencja lewa i sekwencja
prawa) funkcji kompresji. 160-bitowe wyjścia każdej linii są przekształcane w celu uzyskania
160-bitowego wyjścia.
Sekwencje lewa i prawa różnią się wzajemnie:
" W dwu ostatnich przypadkach (porządek, liczba bitów rotacji),
" Stałymi,
" Porządkiem, w jakim używane są funkcje.
Wszystko po to aby poprawić odporność na znane typy ataków. Każda z równoległych linii
przetwarzania używa tę samą wartość początkową IV co SHA-1.
MASH.
Zasadniczym zadaniem przy projektowaniu funkcji skrótu korzystającej z możliwości arytme-
tyki modularnej jest skonstruowanie funkcji iteracyjnej stosujÄ…cej arytmetykÄ™ modulo n i wy-
korzystywanie jej jako funkcji kompresującej. Przykładem takiej funkcji jest MASH zaprojek-
towana w dwóch odmianach.
Rys. 4 Funkcja skrótu MASH
3. FUNKCJE SKRÓTU Z KLUCZEM
Funkcje skrótu z kluczem, których specyficznym zadaniem jest uwierzytelnianie wiadomości,
nazywa się kodem uwierzytelniania wiadomości (MAC). W porównaniu z dużą liczbą algoryt-
mów MDC, zaproponowano dotąd niewiele algorytmów MAC. Wiele z nich korzysta z szy-
frów blokowych, inne  np. HMAC z dedykowanych funkcji skrótu.
Na poniższym rysunku pokazano funkcję skrótu z kluczem k, w której użyto z przekształcenia
szyfrujÄ…cego E oferowanego przez szyfr blokowy. W ostatnim etapie stosuje siÄ™ dodatkowe
przekształcenie z kluczem k `"k.
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
7
Rys. 5 Funkcja skrótu z kluczem
4. METODY ATAKU NA FUNKCJE SKRÓTU
Atak niezależny od algorytmu jest takim atakiem, który może być zastosowany do dowolnej
funkcji skrótu, traktując ją jako czarną skrzynkę charakteryzującą się długością skrótu wyno-
szącą n bitów (i w przypadku MAC  długością klucza) oraz czasem wykonywania jednej ope-
racji. Istnieje kilka typów ataków na funkcje skrótu, wśród których atak urodzinowy zasługuje
na szczególną uwagę.
4.1 Atak Yuvala
Atak Yuvala był jednym z pierwszych kryptograficznych zastosowań paradoksu urodzinowego.
Gdy losujemy elementy losowo ze zwracaniem ze zbioru n elementów, to z dużym prawdopo-
dobieÅ„stwem element bÄ™dzie wybrany powtórnie po wykonaniu O("n) prób. Atak można sto-
sować do wszystkich funkcji skrótu bez klucza w czasie O(2r/2), gdzie r jest długością skrótu
wyrażoną w bitach.
Kolizje wytworzone wskutek ataku urodzinowego są rzeczywiste, a tym samym mogą mieć
bezpośrednie praktyczne konsekwencje, gdy wiadomości mają dużą wartość.
Aby usunąć wymagania pamięciowe algorytmu Yuvala, można zastosować ogólną technikę
znajdowania cykli. Służy do tego algorytm Floyda.
4.2 Ataki łańcuchowe
Ataki łańcuchowe to ataki wykorzystujące iteracyjny charakter funkcji skrótu. Powoduje on
skupienie się raczej na funkcji kompresji f niż na całej funkcji h.
Punktem stałym funkcji kompresji f jest para Hi-1, mi, taka że f(Hi-1, mj)=Hi-1. Dla takiej pary
bloków wiadomości i wartości łańcuchowej skrót wiadomości pozostaje niezmienny, gdy
wstawić dowolną liczbę identycznych bloków mi. Takie ataki należy brać pod uwagę, jeśli
można doprowadzić do sytuacji, by zmienna łańcuchowa miała wartość, dla której jest znany
punkt stały. Obejmuje to następujące przypadki:
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
8
" Jeśli można znalez
ć punkty stałe i można łatwo doprowadzić do tego, aby zmienna łańcu-
chowa przyjmowała specyficzną wartość,
" Jeśli dla dowolnej zmiennej łańcuchowej Hi-1 można znalez
ć bloki mi dające punkty stałe.
Punkty stałe umożliwiają znalezienie kolizji; ich efekt można porównywać z wstawieniem dłu-
gości bloku do algorytmu wyznaczania skrótu.
Kryptoanaliza różnicowa jest skuteczna także w przypadku funkcji skrótu, włączając w to
funkcje skrótu z kluczem kryptograficznym. Dla wielorundowych szyfrów blokowych bada się
różnice wejściowe funkcji i odpowiadające im różnice wyjściowe tej funkcji, poszukując staty-
stycznych anomalii. Dla funkcji skrótu bada się różnice argumentów funkcji kompresji i odpo-
wiadające im różnice wyjściowe: kolizje występują dla różnic wyjściowych równych zero.
4.3 Ataki wykorzystujące właściwości szyfru
Pewne własności szyfrów blokowych, nieistotne w praktyce przy szyfrowaniu, muszą być bra-
ne pod uwagę, gdy stosuje się te szyfry do konstrukcji iterowanych funkcji skrótu. Generalnym
zagrożeniem jest, że takie własności mogą ułatwić manipulowanie wejściami funkcji kompre-
sji, co może ułatwić predykcję albo większą kontrolę wyjść lub zależności pomiędzy wyjściami
i kolejnymi iteracjami. Szczególną uwagę należy zwrócić na następujące właściwości:
" WÅ‚asność komplementarnoÅ›ci: c = Ek(m) Ô! c = E k (m ). Pozwala ona znalez
ć pary klucz-
wiadomość szyfru, dla których wyjścia różnią się w określony sposób.
" Klucze słabe: klucz k jest słaby, jeśli Ek(Ek(m)) = m dla każdego m. Ta własność ułatwia
utworzenie punktów stałych funkcji kompresji f w przypadku, gdy bloki wiadomości mi
mają bezpośredni wpływ na wejście klucza.
" Klucze półsłabe: parę kluczy (k ,k) nazywa się parą kluczy półsłabych, jeśli Ek(Ek(m)) = m
dla k `" k.
" Punkty stałe: Ek(m) = m. Punkty stałe szyfru blokowego mogą ułatwić atak łańcuchowy z
punktem stałym, jeśli intruz może kontrolować wejście klucza szyfru. Przykładowo, dla
funkcji kompresji Daviesa-Meyera f(Hi-1, m) = Emi(Hi-1)+ Hi-1 jeśli Hi jest punktem stałym
szyfru blokowego dla klucza mi uzyskuje się wyjście funkcji kompresji f(Hi-1,mi) = 0.
" Kolizja kluczy, Ek(m)=Ek (m), może dawać w wyniku kolizję funkcji kompresji.
LITERATURA
[1] William Stallings  Ochrona danych w sieci i intersieci w teorii i praktyce WNT War-
szawa, 1997,
[2] Strona WWW autorów konspektu: http://city.net.pl/editha/
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002