Mimo, że termin zadanka M minął już całkiem dawno, to pomyślałem, że i tak warto coś naskrobać na temat hashy. Wiedza ta przyda się w przeróżnych problemach w przyszłości, nie tylko przy zadaniach z algo :). No to zaczynamy…
Hash jest to funkcja skrótu(mieszająca), która dowolnie długiemu ciągowi znaków przypisuje stosunkowo krótką, często o stałej wielkości liczbe. Zaletą funkcji jest fakt, iż jest nieodwracalna - znając hash nie jesteśmy w stanie odtworzyć początkowej wiadomości(chyba, że brute force-o tym pozniej).
Zastosowania można podzielić na dwie kategorie - w algorytmice lub kryptografii.
1.W algorytmice(na tym m.in. polegało zadanie M) sluzy do implementacji tablic asocjacyjnych, czyli także słowników. Zaletą tej struktury jest to, że posiadamy szybki dostęp do danych. Odwołuje się do nich poprzez klucz, którym może być wszystko- np. kluczem mogą być nazwiska osób a informacją ich miejsce zamieszkania. Uzywa sie zwyklych tablic indeksowanych liczba ponieważ nie ma znaczenia ich rozmiar, dane wyszukiwane są w czasie stałym(przy idealnej funkcji hashujacej). Jak to działa? Otóż tworzymy funkcję mieszającą, która klucz zamieni na unikatową liczbę. To właśnie pod tą liczbą wpisujemy dane do tablicy.
Przykład:
Jan Kowalski - Karniowice oś.XXXV-lecia 69 32-082 Bolechowice ( :D )
funkcja mieszająca(int magia()) zamienia string "Jan Kowalski" na liczbe 523578. Tak wiec w tab[523578]="Karniowice oś.XXXV-lecia 69 32-082 Bolechowice".
Wyszukujemy dokładnie taką samą metodą, pierw hashujemy klucz a następnie patrzymy co jest w tab[hash]. Wyszukiwanie i dodawanie do tablicy jest w czasie stałym O(1). Jednak wszystko zależy od odpowiedniego dobrania funkcji. Co może być taką funkcją haszującą?
Oto pare przykładów:
- -Suma wszystkich znaków(do dupy-nie używać)
- -Iloczyn wszystkich znaków modulo duża liczba pierwsza(już lepiej)
- -Suma iloczynow kolejnych znakow przez kolejne potegi malej liczby pierwszej modulo duza liczba pierwsza tzn. dla "mama" będzie to (m*1+a*31+m*31^2+a*31^3)mod 2000029 ( o lol, ale to juz calkiem niezle - mozna uzywac ;) )
Jednak wszystkie one podatne są na kolizje. W takim przypadku trzeba zastosować sprytny manewr wymijający. Jeżeli okaże się, że dane miejsce jest już zajęte, wpisujemy wartość na następne pole(jeśli wolne), jeżeli jednak znowu zajęte, przechodzimy na pole +2^2, potem na +3^2 (szukanie kwadratowe). Należy unikać sprawdznia zawsze o jedno pole dalej ponieważ mogą szybko powstać duże klastry danych bardzo psujące złożoność.
Wyszukiwanie w takim przypadku wygląda identycznie. Jeżeli pod tab[hash] coś jest, ale dane różnią się od szukanych to przechodzi kolejno na +1 +2^2 +3^2 az znajdziemy co chcemy. To by było tyle z teorii, tym ktorzy jeszcze nie zaklpali życzę powodzenia :P
2.Przechodzimy do ciekawszej częsći, czyli do kryptografii. Zracji tego, iż jest to funkcja jednostronna, bez możliwości odwrócenia, ma duże zastosowanie w systemach komputerowych. Nie trzeba martwić się o tajność zaszyfrowanej wiadomości, jedynym mankamentem jest dobór na tyle bezpiecznej funkcji aby czas łamania trwał więcej niż chociażby 100 lat ;) Zapewnia to bezpieczenstwo np. przy logowaniu ponieważ nigdzie nie trzeba trzymać hasła w plain tekscie tylko w postaci zahashowanej. Odbywa sie to tak:
Podaj login: lalala
Podaj haslo: alamakota
If(hash(haslo) == hash_hasla_z_pamieci) access guaranted
else access denied
Proste i genialne. Najczesciej uzywane i znane funkcje hashujace:
MD5 - stworzony w 1991 pierwszym roku algorytm skraca wiadomość do 128-bitowej liczby. Niestety w 2004 roku znaleziono sposob na generowanie kolizji, jednak dalej jest powszechnie uzywany i uznawany za calkiem bezpieczny. Szyfrowanie przebiega w następujący sposób(źródło wikipedia.pl):
- Doklejamy do wiadomości wejściowej bit o wartości 1
- Doklejamy tyle zer ile trzeba żeby ciąg składał się z 512-bitowych bloków, i ostatniego niepełnego - 448-bitowego
- Doklejamy 64-bitowy (zaczynając od najmniej znaczącego bitu) licznik oznaczający rozmiar wiadomości. W ten sposób otrzymujemy wiadomość złożoną z 512-bitowych fragmentów.
- Ustawiamy stan początkowy na 0123456789abcdeffedcba9876543210
- Uruchamiamy na każdym bloku (jest przynajmniej jeden blok nawet dla pustego wejścia) funkcję zmieniającą stan
- Po przetworzeniu ostatniego bloku zwracamy stan jako obliczony skrót wiadomości
Przykłady wiadomości zakodowanych MD5:
"Lech Duraj" = c7c54e14afe31107a236f722b1ce0a8f
"lech duraj" = 1ebe0b198e7c478c1708b4fdb2477f29
Jak widać nawet niewielka zmiana generuje zupełnie inną liczbę.
SHA-1 - Algorytm hashujacy stworzony przez NSA (National Security Agnecy) w Stanach. Tworzy ona nieco dłuższą (160-bitową) liczbę, przez co jest bezpieczniejsza od MD5. O sposobie tworzenia można przeczytąc tutaj: http://pl.wikipedia.org/wiki/SHA1
I przykłady:
"Lech Duraj" = 55bd1a9f56e8c7733ea2c96ff2f57f9aa09dcabf
"lech duraj" = 0d0f5aefe3ea954c0c0f904076787ce7bf48cde3
O poniższych funkcjach już pisać nie będę, tylko je wymienie i pokaże przykład(ofkors "Lech Duraj").
RIPEMD-160: 6cd77d32 c079cf38 efd0fc96 9ad6aa06 1430fa4e
SHA2-256: e3625910cd12a820af1430a96b12a0ce904b1ac7b8123354de085e7685956c2e
SHA2-512: 99d8a8efd6a01ba51f6d650d1f7cb398a20d4068fc8c72784289d9898f8733702f7bda8985463b60e2f59ad7df46f28af3755a1ab956c1a581dbf97b40195f78
(hardcore :) )
Tiger-128: 8657159748601fcbb89cf220e6c337e1
WHIRLPOOL: 46aac5aa336d9eb66b10e5a656e58479fbeee10f11369005f90507d93e8332609652020b8d6577d75df1317ee4d39c992da26b4708437e8e5f981d4233a9598b
And more…
Jak widac są one całkiem podobne do siebie…lecz tylko z pozoru ;) A teraz troche o ich łamaniu. Ponieważ jak wiemy, jest to funkcja nieodwracalna można ją złamać tylko za pomocą metody Brute force. Wystarczy sprawdzić wszystkie kombinacje o napewno trafimy na tę właściwą…wystarczy(haha!). Na przecietnym kompie wiadomość ponad 15 znaków na pełnym charsecie przeczytają dopiero twoje dzieci. Tak więc…Good Luck :)
Jakby ktoś chciał się pobawić to tutaj jest zhashowany ciąg MD5, rozwalcie go! - 28f2b95533afb47cbec1d823b0f1a941
Istnieje także inny sposób, tzw. tablice tęczowe(rainbow tables). Jest to baza skrótów pozwalająca w dość szybkim czasie znależć odpowiednią wiadomość. Zwykłe bazy danych skrótów zajmują setki gigabajtów, przez co są nieefektywne. Tęczowa tablica jest tworzona przez zapisywanie łańcuchów (ang. chains) ze skrótów z możliwych haseł. Dobre i potężne tablice tęczowe można nabyć w internecie.
Kolizje w przypadku tych hashy są już dużo większym problemem. Wtedy nieznając prawdziwego hasła, można by logować się na nie swoje konta, uzyskiwać dostęp do tajnych danych. Czy można zrobić tak, zby kolizje nie istniały? Nie. Wezmy taki MD5. Sklada sie on z 32 znaków a-f i 0-9 co daje łączenie 340282366920938463463374607431768211456 kombinacji :P Calkiem sporo, jednak możliwych do zakodowania informacja jest nieskonczenie wiele, i wlasnie istnieje nieskonczenie wiele kolizji - grunt to je znalezc.
Ciekawe linki:
http://paginas.terra.com.br/informatica/paulobarreto/hflounge.html - spis funkcji hashujących.
http://www.hashemall.com/ - multi hasher :P
http://www.stachliu.com/md5coll.c - program szukający kolizji w MD5
http://www.tdhack.com - strona z zadaniami z cryptografii(sporo związane z hashami), hackingu, kombinatorki itp. Niech ktos sprobuje mnie pobic :P
No! To by było na tyle.
Pozdrawiam
aTahualpa
