Na czym polega Hashowanie?
Strona Główna
Artykuły
Na czym polega Hashowanie?

Na czym polega Hashowanie?

Zaawansowany
Opublikowane Jul 29, 2019Zaktualizowane Jan 31, 2023
7m
Hashowanie (haszowanie; tworzenie skrótu) najprościej wytłumaczyć jako proces generowania danych wyjściowych o stałym rozmiarze z danych wejściowych o zmiennym rozmiarze. Idąc dalej, cały proces jest możliwy dzięki zastosowaniu specjalnych wzorów matematycznych znanych pod nazwą tzw. funkcji mieszających (inaczej algorytmów haszujących). 
Chociaż nie wszystkie algorytmy haszujące opierają się na kryptografii , to tzw. kryptograficzne funkcje haszujące (inaczej funkcje skrótu) są jednym z podstawowych elementów kryptowalut. To właśnie dzięki funkcjom haszującym sieci blockchain wraz z innymi rozproszonymi systemami są w stanie osiągnąć odpowiednią do ich działania integralność zachowując przy tym bezpieczeństwo danych w nich zapisanych.

Przy tej okazji warto zauważyć, iż zarówno konwencjonalne, jak i kryptograficzne funkcje skrótu są algorytmami deterministycznymi. Oznacza to, iż dopóki dane wejściowe się nie zmienią, algorytm mieszający zawsze będzie generował to samo wyjście (znane również jako skrót; hasz; hash).

Algorytmy haszujące wykorzystywane przez kryptowaluty są zaprojektowane w sposób jednokierunkowy, co oznacza, że odwrócenie danych wyjściowych do ich pierwotnej formy (danych wejściowych) wymaga bardzo dużo mocy obliczeniowej i czasu, aby mogło zostać zrealizowane. Innymi słowy, w przypadku jednokierunkowych algorytmów haszujących stosunkowo łatwo jest otrzymać dane wyjściowe (ang. output) z danych wejściowych (input), ale bardzo trudno jest odwrócić ten proces (aby wygenerować dane wejściowe znając jedynie dane wyjściowe). Mówiąc ogólnie, im trudniej jest znaleźć (odgadnąć; wyliczyć; rozszyfrować) dane wejściowe, tym bezpieczniejszy jest dany algorytm mieszający.


Jak działa przykładowy algorytm haszujący?

Każda z istniejących funkcji skrótu na podstawie tych samych danych wejściowych generuje dane wyjściowe o innym od innych funkcji skrótu rozmiarów. To, co jednak łączy wszystkie algorytmy haszujące, to fakt iż, dana funkcja mieszająca na podstawie tego samego zestawu danych zawsze wygeneruje dane wyjściowe o tym samym rozmiarze. Dla przykładu algorytm hashujący SHA-256 po przepuszczeniu przez niego jakichkolwiek danych (czyt. danych wejściowych) wyprodukuje skrót o długości 256 bitów, podczas gdy inny algorytm, SHA-1 zawsze wygeneruje skrót o długości 160 bitów.

Aby lepiej zilustrować ten mechanizm posłużmy się przykładem. Przez algorytm hashujący SHA-256 (ciekawostka: wykorzystywany w Bitcoinie) przepuścimy dwa słowa: Binance oraz binance.

SHA-256

Dane wejściowe

Dane wyjściowe (256 bitów)

Binance

f1624fcc63b615ac0e95daf9ab78434ec2e8ffe402144dc631b055f711225191

binance

59bba357145ca539dcd1ac957abc1ec5833319ddcae7f5e8b5da0c36624784b2


Zapewne zwróciłeś(aś) już uwagę, iż - wydawać by się mogło niewielka - zmiana w wielkości pierwszej z liter użytego przez nas słowa, w efekcie skutkuje wygenerowaniem całkowicie innego hashu. Dodatkowo, biorąc pod uwagę fakt, iż do stworzenia skrótu z naszych danych wejściowych użyliśmy algorytmu SHA-256, dane wyjściowe zawsze będą miały rozmiar 256-bitów (lub inaczej 64 znaków) - niezależnie od rozmiaru danych wejściowych. Przy tej okazji warto podkreślić również fakt, iż niezależnie od tego ile razy przepuścimy te dwa słowa przez nasz algorytm, to dane wyjściowe zawsze będą wyglądały tak samo.

W drugim przykładzie przepuścimy nasze dane z poprzedniego przykładu przez algorytm mieszający SHA-1. W wyniku tej operacji uzyskamy następujące dane:

SHA-1

Dane wejściowe

Dane wyjściowe (160 bitów)

Binance

7f0dc9146570c608ac9d6e0d11f8d409a1ee6ed1

binance

e58605c14a76ff98679322cca0eae7b3c4e08936


Jako ciekawostka warto również zauważyć, iż SHA, to akronim od słów Secure Hash Algorithms, co w dosłownym tłumaczeniu na język polski oznacza Bezpieczne Algorytmy Mieszające. Rodzinę algorytmów SHA tworzą m.in SHA-0, SHA-1 wraz z grupą algorytmów SHA-2 i SHA-3. Algorytm SHA-256 jest częścią grupy SHA-2, wraz z SHA-512 i innymi wariantami tej funkcji haszującej. Obecnie za bezpieczne uważa się jedynie algorytmy znajdujące się w grupach SHA-2 i SHA-3.


Do czego potrzebne są algorytmy haszujące?

Konwencjonalne funkcje skrótu mają szeroki zakres zastosowań, wliczając w to chociażby znakowanie plików w bazach danych do ich prostszego (i szybszego) wyszukiwania, analizę dużych plików czy generalnie zarządzanie danymi. Z drugiej strony, kryptograficzne funkcje skrótu są również szeroko stosowane w aplikacjach związanych z bezpieczeństwem informacji w takich dziedzinach jak np. uwierzytelnianie wiadomości przesyłanych w formie cyfrowej czy cyfrowa tożsamość. Jeśli chodzi o Bitcoina, to algorytmy haszujące są istotną częścią procesu kopania (ang. miningu), a poza tym odgrywają dużą rolę w generowaniu nowych adresów i kluczy.

Prawdziwa moc drzemiąca w funkcjach haszujących objawia się w sytuacji w której przychodzi nam zmierzyć się z dużą ilością informacji. Dla przykładu wyobraź sobie, że musisz przenieść bardzo ważne dane z jednego komputera na drugi, a po drodze musisz również przekazać nośnik z tymi danymi komuś, kto również będzie brał udział w tym procesie. Przed migracją przepuszczasz więc ten zbiór danych przez funkcję haszującą na swoim komputerze, a przed przeniesieniem ich na drugi komputer weryfikujesz, czy w międzyczasie nie zostały one zmodyfikowane przepuszczając je ponownie przez tę samą funkcję. Jeżeli hash powstały z przepuszczenia tych zbiorów danych przed i po migracji będzie taki sam, to masz pewność, że nie uległy one modyfikacji. Dzieje się tak ze względu na deterministyczny charakter funkcji skrótu: te same dane wejściowe po przepuszczeniu ich przez funkcję haszującą zawsze dadzą taki sam hash. Taka konstrukcja eliminuje konieczność przechowywania i zapamiętywania informacji o dużej ilości danych.

Hashowanie okazuje się szczególnie przydatne w kontekście technologii blockchain. W blockchain Bitcoina znajduje się wiele komponentów i akcji w których hashe grają pierwsze skrzypce. Większość z nich tyczy się procesu miningu. W rzeczywistości prawie wszystkie protokoły odpowiedzialne za działanie kryptowalut i ich sieci polegają na funkcjach haszujących i łączeniu grup transakcji w bloki, a także w tworzeniu tzw. łączy kryptograficznych między każdym blokiem - czyli innymi słowy tworzeniu łańcucha bloków.


Kryptograficzne funkcje hashujące

Tak jak zostało to już wcześniej wspomniane, funkcję hashującą w której wykorzystywane są techniki kryptograficzne nazywa się "kryptograficzną funkcją hashującą". Ogólnie rzecz biorąc, złamanie kryptograficznej funkcji skrótu wymaga niezliczonych prób i użycia na prawdę dużych zasobów mocy obliczeniowej. Ktokolwiek by nie podjął się przywrócenia (wyliczenia; odgadnięcia) danych wejściowych z posiadanych przez niego danych wyjściowych, to aby rozszyfrować co kryje się pod danym hashem, musi poznać dane wejściowe. Prawdę powiedziawszy nie ma innej drogi. Tutaj warto wspomnieć, iż istnieje pewne prawdopodobieństwo, iż różne dane wejściowe po przepuszczeniu je przez funkcję haszującą, dadzą takie same dane wyjściowe. Taką sytuację nazywamy “kolizją”.

Z technicznego punktu widzenia funkcja skrótu kryptograficznego musi spełniać trzy właściwości, aby uznać ją za skuteczną i bezpieczną. Tymi właściwościami są odpowiednio: odporność na pojawienie się kolizji, preimage resistance oraz tzw. second preimage resistance.

Przed omówieniem każdej z tych właściwości spójrzmy jednak na ich krótki opis (aby lepiej zrozumieć te zagadnienia).

  • Odporność na kolizję: właściwość dzięki której niemożliwe jest znalezienie dwóch odrębnych danych wejściowych, które w wyniku przepuszczenia ich przez funkcję hashującą dadzą taki sam hash.

  • Preimage resistance: właściwość dzięki której niemożliwe jest “przywrócenie” danych przepuszczonych przez funkcję skrótu (odkrycie danych wejściowych z posiadanych danych wyjściowych).

  • Second-preimage resistance: właściwość dzięki której niemożliwe jest odnalezienie drugiego zestawu danych wejściowych, który koliduje z innym określonym zestawem danych wejściowych.


Odporność na kolizję

Tak jak już wspomnieliśmy, kolizja ma miejsce, gdy różne dane wejściowe wytworzą dokładnie ten sam skrót. Funkcja skrótu jest uważana za odporną na kolizję do momentu, gdy komuś uda się doprowadzić do kolizji danych przez nią przepuszczonych. Przy tej okazji warto zauważyć, iż prawdopodobieństwa wystąpienia kolizji nie da się uniknąć. Dzieje się tak ponieważ, istnieje nieograniczona liczba danych wejściowych, a z drugiej strony ograniczona liczba danych wyjściowych.

Innymi słowy, funkcja skrótu jest odporna na kolizje, gdy możliwość znalezienia jakiejkolwiek kolizji jest tak niska, że wymagałaby milionów lat obliczeń. Pomimo tego więc, iż nie ma bezkolizyjnych funkcji haszujących, to niektóre z nich są wystarczająco silne, aby uznać je za odporne na kolizje (np. SHA-256).

Wśród różnych algorytmów SHA, te przypisane do grup SHA-0 i SHA-1 nie są już bezpieczne, ponieważ komuś udało się znaleźć sposób na doprowadzenie do kolizji. Obecnie funkcje hashujące znajdujące się w grupach SHA-2 i & SHA-3 są uważane za odporne na kolizje.


Preimage resistance

Właściwość określana jako Preimage resistance związana jest z koncepcją funkcji jednokierunkowych. Funkcja skrótu jest uważana za odporną na tzw. preimage, gdy istnieje bardzo małe prawdopodobieństwo, że ktoś będzie w stanie odnaleźć taki zestaw danych wejściowych, który wygeneruje konkretny zestaw danych wyjściowych.

Co istotne: ta właściwość różni się od poprzedniej - zauważ i w przypadku preimage resistance chodzi konkretnie o odporność na odgadnięcie przez kogokolwiek danych wejściowych przy użyciu dostępnych danych wejściowych. Z kolizją mamy do czynienia, gdy komuś uda się znaleźć dwa różne zestawy danych wejściowych, które wygenerują ten sam wynik, bez znaczenia, które z danych wejściowych były użyte jako pierwsze.

Preimage resistance okazuje się bezcenną właściwością w przypadku wykorzystywania funkcji haszujących do ochrony danych, ponieważ prosty hash stworzony na bazie danej wiadomości, może udowodnić jej autentyczność, bez konieczności ujawniania informacji jakie zostały zapisane w tej wiadomości. W praktyce wielu usługodawców oraz aplikacji internetowych przechowuje hasła swoich użytkowników w postaci hashy, które zostały wygenerowane na bazie haseł, a nie rzeczywiste hasła - jakie do formularza wpisuje użytkownik.


Second-preimage resistance

Aby uprościć ten i tak trudny temat, możemy uznać, iż właściwość second-preimage resistance znajduje się gdzieś pomiędzy pozostałymi dwoma właściwościami. Second-preimage attack występuje, gdy ktoś jest w stanie znaleźć określone dane wejściowe, które generują takie same dane wyjściowe z innych danych wejściowych, do których ta osoba ma już dostęp.

Innymi słowy, second-preimage attack polega na znalezieniu kolizji, ale zamiast poszukiwania dwóch losowych danych wejściowych, które wygenerują ten sam hash, atakujący poszukuje danych wejściowych, które wygenerują ten sam skrót, który został wygenerowany przez inny określony zestaw danych wejściowych.

Tym samym każda funkcja skrótu, która jest odporna na kolizje, jest również odporna na ataki second-preimage, ponieważ poprawne wykonanie ataku second-preimage oznacza znalezienie kolizji. Nadal jednak można próbować wykonać atak preimage na funkcję odporną na pojawienie się kolizji, ponieważ atak ten polega na znalezieniu pojedynczej danej wejściowej z pojedynczej danej wyjściowej.


Mining (kopanie kryptowalut)

Na mining w sieci Bitcoin składa się wielu etapów, z których wiele z nich opiera się o wykorzystanie algorytmów haszujących. Takimi komponentami są m. in sprawdzanie sald, łączenie danych wejściowych i wyjściowych transakcji oraz haszowanie transakcji w bloku w celu utworzenia tzw.Merkle Tree . To, co jednak sprawia, że sieć blockchain Bitcoin jest rzeczywiście tak bezpieczna, jak się o tym mówi, to fakt, iż górnicy muszą wykonać niezliczoną liczbę operacji haszujących, aby ostatecznie znaleźć prawidłowe rozwiązanie zagadki matematycznej pozwalające im na propagację następnego bloku.
Każdy z górników zanim uda mu się wykopać prawidłowe rozwiązane pozwalające mu umieścić dany blok w sieci, musi najpierw sprawdzić niezliczoną ilość różnych danych wejściowych dla swojego candidate block. Zasadniczo rzecz ujmując, hash ten musi zaczynać się od określonej liczby zer. Tylko taki hash pozwala poprawnie wykonać walidację bloku i jego propagację do sieci. Liczba zer determinuje trudność procesu miningu i zmienia się w zależności od ilości dostępnej w sieci mocy obliczeniowej.

W przypadku Bitcoina trudność określana jest na podstawie skumulowanej mocy obliczeniowej wszystkich węzłów uczestniczących w procesie miningu. Jeśli skumulowana moc obliczeniowa sieci (ang. hashrate) wzrośnie w badanym okresie, to protokół Bitcoin automatycznie dostosuje trudność wydobycia, tak aby średni czas potrzebny do wydobycia bloku wynosił około 10 minut. Dostosowanie trudności kopania działa również w dwie strony. Tym samym jeśli kilku górników zdecyduje się więcej nie uczestniczyć w procesie miningu, czym przy okazji spowodują spadek hashrate, to trudność wydobycia zostanie odpowiednio zmniejszona (aby znów średni czas potwierdzania bloków wynosił około 10 minut).

To, co jednak warto mieć na uwadze przy okazji miningu, to fakt iż górnicy nie poszukują kolizji, ponieważ istnieje zbyt wiele zbiorów danych wejściowych, które po przepuszczeniu przez funkcję haszującą wygenerują wymaganą przez sieć wartość wyjściową (a która musi zaczynać się o odkreślonej liczby zer). Istnieje więc kilka możliwych rozwiązań dla określonego bloku, a górnicy muszą tylko znaleźć jedno z nich - zgodnie z poziomem trudności jaki obecnie panuje w sieci.

Biorąc pod uwagę fakt, iż mining Bitcoinów - przy założeniu obecnego poziomu trudności - jest bardzo kosztownym przedsięwzięciem, to górnicy nie mają obecnie żadnego powodu, który mógłby zachęcić ich do podjęcia się próby oszukania systemu. Blockchain Bitcoina staje się tym bezpieczniejszy, czym więcej górników bierze udział w procesie miningu.


Zakończenie

Obecnie nikt nie powinien mieć żadnych wątpliwości, że funkcje haszujące odgrywają ogromną rolę w dzisiejszym świecie i są niezbędnymi narzędziami po które sięga się szczególnie w dziedzinie informatyki, a już szczególnie w przypadku ogromnych ilości danych. W połączeniu z kryptografią algorytmy hashujące są w stanie spełniać wiele funkcji, oferując bezpieczeństwo i możliwości uwierzytelniania danych na wiele różnych sposobów. Algorytmy hasujące stoją u podstaw prawie wszystkich sieci istniejących w dzisiejszych czasach kryptowalut, tym samym zrozumienie ich właściwości i mechanizmów działania z pewnością powinno być w kręgu zainteresowania każdego z fanów technologii blockchain i kryptowalut.