Funkcja haszująca
Z Wikipedii
Funkcja haszująca (inaczej funkcja skrótu lub funkcja mieszająca) to funkcja, która przyporządkowuje dowolnie dużej liczbie będącej parametrem wejściowym (wiadomością) krótką, zwykle posiadającą stały rozmiar wartość określaną jako hash (skrót wiadomości; często używany jest też termin sygnatura danych). Pożądaną cechą dobrej funkcji haszującej jest to, że w przypadku wystąpienia nawet minimalnej różnicy w wiadomości, dla której obliczany jest skrót, z możliwie dużym prawdopodobieństwem dojdzie również do istotnej zmiany wartości skrótu.
Dzięki tej właściwości, w zastosowaniach informatycznych funkcje haszujące pozwalają na ustalenie krótkich i łatwych do weryfikacji sygnatur dla dowolnie dużych zbiorów danych. Takie sygnatury mogą chronić przed przypadkowymi lub celowo wprowadzonymi przekłamaniami transmisji, a także mają zastosowania przy optymalizacji dostępu do struktur danych w programach komputerowych.
Szczególną podgrupą funkcji haszujących są funkcje uznawane za bezpieczne do zastosowań kryptograficznych (jak np. SHA-1, SHA2, RIPEMD-160). W przypadku takich funkcji praktycznie niewykonalne musi być stworzenie dwóch wiadomości o tym samym skrócie (to umożliwiałoby celową podmianę danych, a mimo tego pomyślne przejście weryfikacji po stronie ich odbiorcy), oraz wywnioskowanie jakichkolwiek informacji o właściwościach wiadomości na podstawie jej skrótu (to ułatwiałoby np. kryptoanalizę zaszyfrowanych danych, do których dołączono sygnaturę tego typu).
Należy zauważyć, że uznanie funkcji za bezpieczną do zastosowań kryptograficznych w większości przypadków opiera się wyłącznie na domniemanej odporności na znane ataki kryptoanalityczne, nie zaś o matematyczne dowody gwarantujące niemożność ich złamania. Poważne słabości znaleziono w wielu funkcjach skrótu, które historycznie uchodziły za bezpieczne - m.in. w MD2, MD4, SHA, czy ostatnio MD5.
Spis treści |
[edytuj] Ataki na funkcje haszujące
Należy w nim poprawić: poniższe sekcje (a być może i cały artykuł) - vide dyskusja (--Lcamtuf 19:18, 24 lip 2006 (CEST)).
Więcej informacji co należy poprawić, być może znajdziesz w dyskusji tego artykułu lub na specjalnej stronie. W pracy nad artykułem należy korzystać z zaleceń edycyjnych. Po naprawieniu wszystkich błędów można usunąć tę wiadomość.
Możesz także przejrzeć pełną listę stron wymagających dopracowania.
[edytuj] Podstawy teoretyczne
Problemem znajdującym się pomiędzy efektywnymi strukturami danych a kryptografią są tzw. computational complexity attacks. Wiele struktur danych ma bardzo dobrą przeciętną złożoność obliczeniową i fatalną złożoność pesymistyczną – atakujący może za pomocą niewielkiej ilości specjalnie w tym celu przygotowanych danych przeciążyć system – choć radziłby sobie on ze znacznie większymi ilościami normalnych informacji.
Do najczęściej stosowanych typów computational complexity attacks należą właśnie ataki na niedoskonałe funkcje hashujące.
[edytuj] Przykład
Przykład ataku: 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 funkcja haszująca równomiernie rozprowadza dane po kubełkach, średnio musimy przeszukać 96 * 84 danych, przy czym jeśli ilość danych wzrośnie, możemy zwiększyć ilość kubełków, i wydajność dalej będzie świetna – 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źć taką serię danych, że wszystkie one mają taką samą wartość funkcji skrótu używanej przez serwer (czyli np. takie same ostatnie cyfry), potrafimy zmusić serwer do wrzucenia wszystkich danych do tego samego kubełka – przez co każde wyszukiwanie będzie wymagać przeszukania wszystkich danych. Już niezbyt duża ilość danych potrafi spowolnić serwer tak bardzo, że nie będzie on już potrafił wypełniać swojej funkcji. Jeśli serwer ten miał znaczenie dla bezpieczeństwa (IDS, firewall, serwer SSH), być może będziemy mogli przeprowadzić potem dalsze ataki innego typu.
[edytuj] Tęczowe tablice
Nowym sposobem ataku na funkcje hashujące są tęczowe tablice
-
Zobacz więcej w osobnym artykule: Tęczowe tablice.
[edytuj] Rozwiązania problemów
Możliwe rozwiązania to:
- używanie struktur danych o lepszej złożoności pesymistycznej, pomimo gorszych wyników przeciętnych (np. drzew czerwono-czarnych zamiast tablic hashujących),
- wykrywanie ataków tego typu, lub uniemożliwienie ich powstawania przez odrzucanie patologicznych danych,
- używanie kryptograficznie bezpiecznych funkcji skrótu dodatkowo wzmocnionych na ten rodzaj ataków (np. keyed MD5) – są one jednak bardzo powolne,
- używanie funkcji hashującej która, choć nie spełnia kryteriów bezpieczeństwa kryptograficznego, nie jest możliwa do zaatakowania w ten sposób. Istnieją bardzo szybkie funkcje tego typu z mocnymi dowodami bezpieczeństwa, jednak jest to relatywnie nowa dziedzina informatyki, więc w chwili obecnej (2004) nie jest to popularne rozwiązanie.
[edytuj] 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
