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 鈥渒olizj膮鈥.

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 鈥減rzywr贸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.