Funkcje mieszające

Funkcje mieszające

Spośród wszystkich elementarnych procedur kryptograficznych najbardziej uniwersalne są funkcje mieszające. Funkcji takich można użyć do szyfrowania, do potwierdzania tożsamości, a nawet w pro­stym schemacie podpisu cyfrowego.

Funkcja mieszająca pobiera jako dane wejściowe dowolnej długości ciąg bitów
i zwraca wynik o stałym rozmiarze. Typowym zastosowaniem funkcji mieszającej są podpisy cyfrowe. Jeśli dana jest wiadomość
m, można ją podpisać bezpośrednio. Jednak operacje związane z kluczem publicz­nym w większości schematów podpisu elektronicznego są zwykle kosztowne obliczeniowo, wobec czego zamiast podpisywać m, stosujemy funkcję mieszającą h i skrót wiadomości h(m). Rozmiar wyniku funkcji h zwykle mieści się w przedziale od 128 do 512 bitów, podczas gdy sama wiado­mość m może zawierać tysiące lub nawet miliony bitów. Podpisanie h(m) jest zatem znacznie szybsze od podpisywania całej wiadomości m. Aby taka konstrukcja była bezpieczna, niedopusz­czalna jest możliwość skonstruowania dwóch wiadomości m1 i m2, dla których funkcja mieszająca zwróci tę samą wartość.

MD5

128-bitowa funkcja mieszająca MD5 została stworzona przez Rona Rivesta.
Jest ona rozwinięciem funkcji MD4, dodatkowo zabezpieczonym przed atakami.

Podczas obliczania wartości MD5 pierwszy kroki polega na podzieleniu wiadomości na bloki liczące po 512 bitów. Ostatni blok jest dopełniany, przy czym dołącza się do niego również długość wiadomości. MD5 posiada 128-bitową zmienną stanu, podzieloną na cztery słowa po 32 bity każde Funkcja kompresująca h’ składa się z czterech tur, podczas których następuje mieszanie bloków wiadomości ze zmienną stanu. Mieszanie to polega na zastosowaniu pewnej kombinacji działań dodawania, XOR, AND, OR i przesunięć słów 32-bitowych.W każdej turze cały blok wiadomości podlega przemieszaniu ze zmienną stanu, więc każde słowo wiadomości jest uży­wane czterokrotnie. Po czterech turach funkcji h’ stan wejściowy i wynik są dodawane do siebie, dając wynik h’.1

Taka konstrukcję działań na słowach 32-bitowych da się bardzo wydajnie zaimplementować dla 32-bitowych procesorów. Pierwszym przykładem takiego rozwiązania była funkcja MD4, obec­nie jest ono wspólną cechą wielu realizacji elementarnych operacji kryptograficznych.

Jedna z podstawowych właściwości iteracyjnych funkcji mieszających orzeka,
że jeżeli funkcja
h’ jest odporna na kolizje, to funkcja mieszająca h zbudowana na podstawie h’ jest także odporna na kolizje. Ostatecznie przecież wszelkie kolizje h mogą mieć miejsce tylko jako kolizje h’. Funkcja MD5 jest problematyczna o tyle, że znane są kolizje jej funkcji h’. Obecnie nie są znane żadne ataki na samą funkcję MD5,
ale istnienie kolizji funkcji kompresującej oznacza, że korzystając z MD5, trzeba zachować ostrożność.

W większości zastosowań 128-bitowy rozmiar obszaru mieszania MD5 już
nie wystarcza. Wy­korzystując paradoks urodzinowy
2, można znaleźć kolizję MD5
po obliczeniu około 2
64 wartości funkcji mieszającej, co we współcześnie powstających systemach jest wartością zbyt niską.

SHA-1

SHA (ang. Secure Hash Algorithm, bezpieczny algorytm mieszania) został zaprojektowany w NSA i przyjęty jako standard przez NIST. Jego pierwszą wersję nazywano po prostu SHA (obecnie często odwołuje się do niej jako do SHA-0),
ale miała ona pewne słabości. NSA
je odkryła i popra­wiła, zaś udoskonalona wersja została opublikowana przez NIST pod nazwą SHA-1. Jednak natura tych słabości nigdy nie została publicznie ujawniona. Trzy lata później Chabaud i Joux opubliko­wali informacje o słabościach SHA-0. Te właśnie niedoróbki zostały usunięte w SHA-1.

SHA-l jest 160-bitową funkcją mieszającą opartą na MD4. Z uwagi na podobny rodowód, ma i wiele cech wspólnych z MD5, ale jej konstrukcja jest znacznie bardziej konserwatywna. Jest i też dwu lub trzykrotnie wolniejsza od MD5. Tym niemniej jak dotąd nie są znane żadne problemy z bezpieczeństwem SHA-1, więc jest ona powszechnie używana.

SHA-l ma 160-bitową zmienną stanu składającą się z pięciu słów 32-bitowych. Tak jak MD5, obliczanie SHA-l przebiega w czterech turach, z których każda składa się z mieszanki elementarnych operacji 32-bitowych. Zamiast przetwarzać czterokrotnie każdy blok wiadomości, SHA-l za pomocą rekurencji liniowej „rozciąga” 16 słów
z bloku wiadomości do potrzebnych 80 słów. Jest to uogólnienie techniki zastosowanej w MD4. W MD5 każdy bit wiadomości jest w funkcji mieszającej używany czterokrotnie.

W SHA-l rekurencja liniowa zapewnia, że każdy bit wiadomości wpłynie
na funkcję mieszającą przynajmniej dwanaście razy. Jedyna różnica między SHA-0,
a SHA-l polega na uzupełnieniu kroku rekurencji jednobitowym przesunięciem.

SHA-256, SHA-384 i SHA-512

Ostatnio NIST3 opublikował projekt standardu, w którym opisuje trzy nowe funkcje mieszające. Funkcje te mają wyniki odpowiednio 256, 384 i 512 bitowe. Zaprojektowano je z myślą o współpracy ze 128-, 192- i 256-bitowymi kluczami AES. Budowa tych funkcji jest bardzo podobna do SHA-l.4

W sytuacji, kiedy SHA-l nie jest w stanie zapewnić wymaganego poziomu bezpieczeństwa, trzeba użyć funkcji mieszającej z dłuższymi danymi wynikowymi. Żadna z opublikowanych dotąd funkcji mieszających z odpowiednio długim wynikiem nie doczekała się szerszej publicznej analizy.

Obliczenie SHA-256 trwa znacznie dłużej, niż SHA-l. W przypadku długich wiadomości mieszanie za pomocą SHA-256 zajmuje mniej więcej tyle czasu,
co szyfrowanie za pomocą AES lub Twofish, a być może nawet nieco więcej.

Funkcja SHA-384 wydaje się bezużyteczna. Jej użycie wymaga tyle pracy co użycie SHA-512, a potem po prostu część bitów się odrzuca. Do tego nie potrzeba odrębnej funkcji, więc można pozostać przy SHA-256 i SHA-512.

1 N. Ferguson, B. Schneider: Kryptografia w praktyce, Wydawnictwo Helion, Gliwice 2004, s. 78

2 Paradoks urodzinowy „Ile osób należy wybrać, żeby prawdopodobieństwo, że co najmniej dwie z nich mają urodziny tego samego dnia było większe od jednej drugiej”. Jeśli losowo przyporządkujemy każdemu obiektowi jedną z n etykietek, to żeby prawdopodobieństwo że dwa obiekty będą oznaczone taką samą etykietką było większe od jednej drugiej trzeba zbioru obiektów o liczności rzędu √n.

3 National Institute of Standards and Technology (ang. Narodowy Instytut Standaryzacji i Technologii)
amerykańska agencja federalna spełniająca rolę analogiczną do Polskiego Komitetu Normalizacji.

4 N. Ferguson, B. Schneider: Kryptografia w praktyce, Wydawnictwo Helion, Gliwice 2004, s. 79