Funkcja skrótu

Funkcja skrótu, funkcja mieszająca lub funkcja haszująca – funkcja przyporządkowująca dowolnie dużej liczbie krótką wartość o stałym rozmiarze, tzw. skrót nieodwracalny.

W informatyce funkcje skrótu pozwalają na ustalenie krótkich i łatwych do weryfikacji sygnatur dla dowolnie dużych zbiorów danych. Sygnatury mogą chronić przed przypadkowymi lub celowo wprowadzonymi modyfikacjami danych (sumy kontrolne), a także mają zastosowania przy optymalizacji dostępu do struktur danych w programach komputerowych (tablice mieszające).

Algorytmy funkcji skrótu

Doskonała funkcja haszująca

Dla zbioru S, doskonała funkcja haszująca przyporządkowuje każdemu elementowi z tego zbioru liczbę całkowitą bez kolizji. Innymi słowy, funkcja ta jest iniekcją.

Minimalna doskonała funkcja haszująca

Minimalna doskonała funkcja haszująca jest doskonałą funkcją haszującą, która n argumentom przyporządkowuje wartości ze zbioru n kolejnych liczb całkowitych. Formalnie można to wyrazić w następujący sposób: Niech j i k będą elementami pewnego skończonego zbioru kluczy K. F jest minimalną doskonałą funkcją haszującą wtedy i tylko wtedy, gdy równość funkcji dla argumentów j i k implikuje równość tych argumentów oraz istnieje liczba całkowita a taka, że zbiór wartości F to $[a,a+|K|-1]$ .

Haszowanie danych o rozkładzie jednostajnym

Jeśli dane wejściowe to dane o określonej długości i jednostajnym rozkładzie prawdopodobieństwa, funkcja haszująca może wykorzystać haszowanie modularne lub haszowanie przez mnożenie. Przykładowo, na wejściu pojawiają się liczby z zakresu od 0 do N-1, a na wyjściu chcemy otrzymać wartości h ze zbioru od 0 do n-1, gdzie N jest istotnie większe od n. Każdemu argumentowi można przyporządkować zatem wartość x mod n lub $\left\lfloor {\frac {x\times n}{N}}\right\rfloor ,$ gdzie x jest argumentem funkcji.

Haszowanie danych o innych rozkładach prawdopodobieństwa

Jeśli dane nie są niezależne, bądź ich rozkład jest niejednostajny, powyższe algorytmy nie dadzą oczekiwanych rezultatów. Haszowanie przez mnożenie nie spełni swojego zadania w momencie, gdy mamy do czynienia z danymi takimi jak numery telefonów w pewnym obszarze, które zaczynają się tym samym prefiksem. Dla dużej ilości danych n, haszowanie przez mnożenie, które zależy głównie od cyfr wiodących, wygeneruje dużo kolizji. Haszowanie modularne, które z kolei zależy głównie od cyfr końcowych, może w wyniku dać całkiem pożądane rezultaty.

Kryptograficzne funkcje skrótu

Szczególną podgrupą funkcji skrótu są funkcje uznawane za bezpieczne do zastosowań kryptologicznych (jak np. SHA-3). Kryptograficzna funkcja skrótu powinna spełniać kombinację następujących kryteriów, w zależności od zastosowania:

Odporność na kolizje (collision resistance) – brak praktycznej możliwości wygenerowania dwóch dowolnych wiadomości o takim samym skrócie
Odporność na kolizje konkretnych wiadomości (target collision-resistance, preimage resistance) pierwszego i drugiego rzędu – brak praktycznej możliwości wygenerowania wiadomości o takim samym skrócie jak wskazana wiadomość
Jednokierunkowość (one-wayness) – brak możliwości wnioskowania o wiadomości wejściowej na podstawie wartości skrótu. Zmiana dowolnego pojedynczego bitu wiadomości powinna zmieniać średnio połowę bitów skrótu w sposób, który nie jest istotnie podatny na kryptoanalizę różnicową.

Poza wymienionymi w niektórych zastosowaniach od funkcji skrótu wymaga się także:

pseudolosowości (pseudorandomness),
uwierzytelnienia wiadomości (message authentication),
niemożności odróżnienia od losowej wyroczni (indifferentiability from random oracles)^[1] – uczynienie niemożliwym do znalezienia dla przeciwnika dwóch wiadomości, dla których wartości funkcji skrótu nieznacznie się różnią.

Ponadto nie powinno być możliwości wywnioskowania żadnych użytecznych informacji na temat wiadomości, mając do dyspozycji tylko jej skrót. Dlatego, funkcje haszujące powinny zachowywać się jak funkcje losowe, na ile to możliwe, będąc jednocześnie funkcjami deterministycznymi, łatwymi do obliczenia.

Uznanie funkcji za bezpieczną do zastosowań kryptograficznych opiera się zawsze wyłącznie na domniemanej odporności na znane ataki kryptoanalityczne, nie zaś na matematycznych dowodach gwarantujących niemożność złamania. W szczególności bezpieczna funkcja skrótu musiałaby być funkcją jednokierunkową, a istnienie takich funkcji nie zostało dotychczas dowiedzione. Poważne słabości znaleziono w wielu funkcjach skrótu, które historycznie uchodziły za bezpieczne – m.in. w MD2, MD4, SHA, MD5.

Niekiedy zamiast wyspecjalizowanych funkcji skrótu do realizacji podobnych funkcji bezpieczeństwa stosuje się algorytmy zbudowane na bazie szyfrów blokowych – zwłaszcza w kodach uwierzytelniania wiadomości (MAC).

Zastosowania bezpiecznych funkcji skrótu

Weryfikacja integralności plików bądź wiadomości

Istotnym zastosowaniem funkcji skrótu jest weryfikacja spójności danych. Porównanie skrótów dwóch plików umożliwia stwierdzenie, czy w pliku zostały dokonane jakiekolwiek zmiany.

Z tego powodu, większość algorytmów podpisu cyfrowego działa na zasadzie wygenerowania skrótu wiadomości, dzięki czemu można w dowolnym momencie sprawdzić, czy wiadomość jest autentyczna.

Funkcje skrótu używane są również do weryfikacji haseł. W celu zapewnienia bezpieczeństwa haseł przed ich wyciekiem, w bazie danych przechowuje się skrót hasła, zamiast tekstu jawnego. Hasło wprowadzone przez użytkownika jest haszowane i dopiero wtedy porównywane ze skrótem w bazie danych. Taki sposób przechowywania haseł utrudnia ich odzyskanie, ze względu na jednokierunkowość funkcji haszujących^[2].

Identyfikacja plików lub danych

Skrót może również służyć do identyfikacji plików; Systemy kontroli wersji, takie jak Git lub Mercurial używają funkcji skrótu SHA do identyfikacji różnego rodzaju zawartości (zawartość plików, drzewa katalogów).

Innym zastosowaniem jest używanie skrótów w tablicach z haszowaniem w celu szybkiego wyszukiwania danych.

Ataki na funkcje skrótu

Część powszechnie stosowanych funkcji skrótu jest podatna na ataki typu length-extension: dla danych $h(m)$ oraz $\mathrm {len} (m),$ ale nieznanego $m,$ można obliczyć $h(m||m'),$ gdzie || oznacza konkatenację poprzez wybranie odpowiedniego $m'.$ Ta własność może być wykorzystana do złamania prostych schematów uwierzytelniania bazujących na funkcjach haszujących. Odporność na te ataki była jednym z celów projektowych SHA-3.

Ataki typu denial-of-service

Nawet bezpieczne funkcje skrótu mogą być obiektem ataków kryptograficznych wykorzystujących miejsce, gdzie funkcje te są wykorzystywane w strukturach danych. Wiele struktur danych działa bardzo efektywnie w przeciętnym przypadku, ale słabo w przypadku pesymistycznym. Atakujący może za pomocą niewielkiej ilości specjalnie w tym celu przygotowanych danych przeciążyć system (atak DoS).

Załóżmy, że serwer trzyma pewne dane w tablicy mieszającej – ma k kubełków (buckets), i w każdym trzyma te dane, dla których ostatnie kilka cyfr wartości funkcji skrótu jest równe numerowi kubełka.

Wyszukiwanie wśród danych odbywa się bardzo szybko – jeśli liczba kubełków jest proporcjonalna do ilości danych, to przeciętnie wyszukiwanie odbywa się w czasie stałym.

Jeśli potrafimy jednak znaleźć serię danych, dla których ostatnie cyfry wartości funkcji skrótu używanej przez serwer są identyczne, możemy zmusić serwer do wrzucenia wszystkich danych do tego samego kubełka. Wtedy każde wyszukiwanie będzie wymagać przeszukania wszystkich danych. Już niezbyt duża ilość danych potrafi spowolnić serwer tak bardzo, że nie będzie w stanie wypełniać swojej funkcji. Jest to szczególnie groźne, jeśli serwer ten miał znaczenie dla bezpieczeństwa (IDS, firewall, serwer SSH).

Możliwe zabezpieczenia przed atakami tego typu to między innymi:

używanie struktur danych o lepszej złożoności pesymistycznej, pomimo gorszych wyników przeciętnych (np. drzew czerwono-czarnych zamiast tablic mieszających),
wykrywanie ataków tego typu lub uniemożliwienie ich powstawania przez odrzucanie patologicznych danych,
używanie kryptograficznie bezpiecznych funkcji skrótu dodatkowo wzmocnionych przeciwko takim atakom (np. funkcji skrótu z kluczem jak HMAC-MD5, HMAC-SHA1),
randomizacja skrótów^[3].

Zalecenia dotyczące stosowania funkcji skrótu

Amerykański instytut NIST publikuje zalecenia dotyczące stosowania poszczególnych funkcji skrótu w zależności od pożądanego czasu ochrony informacji. Zgodnie z tymi wytycznymi od 1999 roku nie powinna być stosowana funkcja MD5, zaś funkcja SHA-1 powinna być stosowana co najwyżej do 2010 roku^[4].

Do nowych aplikacji zalecane są funkcje skrótu z rodziny SHA-2, a w przyszłości funkcja SHA-3^[5].

Zobacz też

Przypisy

↑ Marc Fischlin, Anja Lehmann, Krzysztof Pietrzak: Robust Multi-Property Combiners for Hash Functions Revisited. Darmstadt University of Technology, 2008. [dostęp 2012-10-09]. [zarchiwizowane z tego adresu (2013-07-31)].
↑ How to break MD5 and other hash functions.. [dostęp 2014-07-24]. [zarchiwizowane z tego adresu (2009-05-21)].
↑ Recommendation for Applications Using Approved Hash Algorithms (NIST SP 800-107). NIST, 2012.
↑ Aktualny poziom bezpieczeństwa funkcji skrótu. Security Standard, 20 marca 2009. [dostęp 2009-04-14]. [zarchiwizowane z tego adresu (2013-05-28)].
↑ Trzydziestu kandydatów do SHA-3. IPSec.pl, 4 listopada 2009. [dostęp 2009-04-14]. [zarchiwizowane z tego adresu (11 lutego 2011)].

Bibliografia

Kutyłowski M., Strothmann W.B., Kryptografia, OW Read Me 1999 ISBN 83-7147-092-4.
Sklyarov D., Łamanie zabezpieczeń programów OW Read Me 2004 ISBN 83-7243-418-2.
Cormen T. H., Leiserson C. E., Rivest R. L., Wprowadzenie do algorytmów WNT 2001 ISBN 83-204-2556-5.

Linki zewnętrzne

The Hash Function Lounge. Paulo S. L. M. Barreto. [dostęp 2011-03-06]. [zarchiwizowane z tego adresu (2008-12-25)]. (ang.).

[1] Marc Fischlin, Anja Lehmann, Krzysztof Pietrzak: Robust Multi-Property Combiners for Hash Functions Revisited. Darmstadt University of Technology, 2008. [dostęp 2012-10-09]. [zarchiwizowane z tego adresu (2013-07-31)].

[2] How to break MD5 and other hash functions.. [dostęp 2014-07-24]. [zarchiwizowane z tego adresu (2009-05-21)].

[3] Recommendation for Applications Using Approved Hash Algorithms (NIST SP 800-107). NIST, 2012.

[4] Aktualny poziom bezpieczeństwa funkcji skrótu. Security Standard, 20 marca 2009. [dostęp 2009-04-14]. [zarchiwizowane z tego adresu (2013-05-28)].

[5] Trzydziestu kandydatów do SHA-3. IPSec.pl, 4 listopada 2009. [dostęp 2009-04-14]. [zarchiwizowane z tego adresu (11 lutego 2011)].

[1]

[2]

[3]

[4]

[5]