mbator.pl / Hashcash
Autor: Maciej Bator

Hashcash

Czy gdybym powiedział Ci, że rozwiązanie antyspamowe z 1997 roku aktualnie zużywa 47.7 TWh energii elektrycznej, to uwierzyłbyś mi? Nie? Zapraszam, więc do lektury.


Oczywiście jak się domyślasz hashcash nie jest bezpośrednio odpowiedzialny za tak monstrualne zużycie energii elektrycznej, za to odpowiada technologia bazująca w pewnym stopniu na założeniach i sposobie jego działania - kryptowaluty. Nawet dwa wyrazy, z których składa się nazwa tego rozwiązania przywodzą namyśl terminy często używane w świecie technologii blockchain-owych - Hash i cash.

Czym jest hashcash?

Można metaforycznie porównać go do znaczka pocztowego, doklejanego do emaila (dosłownie, ale o tym później). Trafne będzie tu przytoczenie przykładu: jeśli próbujemy wysłać do kogoś list bez znaczka, poczta nie dostarczy go do odbiorcy. Tak samo jeśli spróbujemy wysłać list na drugi kontynent ze znaczkiem krajowym, wiadomość znów nie dotrze do celu.

Znaczki pocztowe dzielą wiele wspólnych właściwości z gotówką, muszą być trudne w skopiowaniu, oraz muszą być rozpoznawalne (weryfikowalne).

Jak to działa?

Ustaliliśmy więc, za metaforę hashcasha, znaczki pocztowe. Czym, więc są znaczki pocztowe? Są one pewną formą opłaty, która w naszym przypadku ma uczynić proceder spamerów nie opłacalnym. W oryginalnej wiadomości autor hashcasha sugeruje nawet użycie wirtualnej waluty Digicash (swoją drogą z 1990 roku), ale ze względu na jej małą popularność oraz wymóg polegania na osobie trzeciej wybrał dużo bardziej uniwersalną walutę - obliczenia.

Niestety aby zrozumieć hashcasha musimy znać (abstrakcyjnie) sposób działania funkcji hash. funkcja sha1) Polska wikipedia dość liberalnie kwalifikuje ją jako funkcję skrótu i stosuje wymiennie tą nazwę. Nie jest do końca prawda, bo najważniejszą właściwością kryptograficznej funkcji hashującej jest bycie funkcją jednokierunkową, a dopiero następnie bycie funkcją skrótu (jedno łączy się z drugim ze względu na bezpieczeństwo).

Chciałbym poruszyć teraz twoją wyobraźnię. Wyobraź sobie, że funkcja jednokierunkowa to skomplikowana maszynka do mielenia mięsa.

Jeśli wrzucisz do niej świnię to z drugiej strony dostaniesz serdelki. :) Jednak przepchnięcie serdelek z powrotem w żywą świnię jest już nie możliwe. Innymi słowy…

To działa:

funkcja jednokierunkowa

A to nie:

!funkcja jednokierunkowa

Funkcja jednokierunkowa to taka na podstawie której wyjścia, nie jesteśmy wstanie wywnioskować co do niej włożyliśmy.

Kontynuując tą masakryczną alegorię, funkcję skrótu możemy porównać do maszyny pakującej. serdelki funkcja skrótu
paleta Nie ważne czy wrzucimy do niej dwie parówki czy całego słonia, zawsze dostaniemy z niej tak samo ładnie zapakowaną paletę z towarem. słoń funkcja skrótu
paleta

A więc funkcja hashująca, łączy w sobie właściwości obu powyższych co oznacza, że:

funkcja hash Oczywiste jest, że aby funkcja jednokierunkowa była bezpieczna musi ona być jednocześnie funkcją skrótu, gdyby tak nie było, jej długość zależałaby od tego co do niej włożyliśmy, a chcemy uniknąć wszelkich połączeń między wyjściem a wejściem. W przykładzie widać wyniki funkcji sha1 (w zapisie hexadecymalnym), wyglądają one z początku na całkowicie losowe, jednak tak jak napisałem wcześniej, przy takim samym wejściu, wyjście zawsze będzie takie samo. Jednak powinieneś zauważyć tu pewną sprzeczność… skoro możemy wsadzić do funkcji treść dowolnej długości (także dłuższą od wyjścia) to mamy więcej możliwości dla wejścia niż dla wyjścia. Funkcja sha1 zwraca wynik o długości dokładnie 160 bitów, więc wsadzając do niej dłuższą treść możliwe znalezienie dwóch (lub więcej) wejść, które zwrócą ten sam wynik. Taką sytuację nazywamy kolizją.

Kryptograficzna funkcja skrótu powinna spełniać kombinację następujących kryteriów, w zależności od zastosowania:

  • Odporność na kolizje (collision resistance) – brak praktycznej możliwości wygenerowanie dwóch dowolnych wiadomości o takim samym skrócie

[…]


Wikipedia - Kryptograficzne funkcje skrótu

Stworzenie takiej sytuacji jest w praktyce bardzo trudne. Funkcje są specjalnie projektowane w taki sposób aby to utrudnić. Wracając do tytułowego bohatera tego wpisu…

Hashcash korzysta właśnie z częściowych kolizji, aby przedstawić proof-of-work/dowód wykonanej pracy, odbiorcy. Częściowa kolizja to taka w której skrót funkcji zgadza się jedynie w pewnej części z innym. W im większej części się on zgadza tym trudniej jest taki znaleźć. zobaczmy więc wreszcie jak wyglądała pierwsza wersja hashcasha:

X-Hashcash: 0:180331:maciek@mbator.pl:4034822300751131

Jest to nagłówek (jak można poznać po X- nie standardowym RFC822 RFC6648 nagłówku) z polami rozdzielonymi : oznaczające kolejno

  1. 0 - wersję
  2. 180331 - datę, tutaj 2018-03-31
  3. maciek@mbator.pl - adres email odbiorcy
  4. 4034822300751131 - losowa liczba

Jak narazie nic poza 4 polem nie jest nie przewidziane, w końcu logicznym jest aby zapisać datę naszego znaczka pocztowego nie może być on ważny nieskończenie długo, wtedy wystarczyłoby raz wygenerować jeden i korzystać z niego dowolną ilość razy. Adres odbiorcy również ma sens, w końcu chcemy wysłać list do pewnej konkretnej osoby, nasz znaczek nie jest niestety uniwersalny, ale gdyby był moglibyśmy wysłać za pomocą jednego hashcasha wiele listów, a tego nie chcemy. ### Po co więc nam losowe liczby? Wszystko stanie się jasne gdy zobaczymy sha1 tego nagłówka.

00000000ed08ce18f2a649f4a8b5ec5c665d5a34

Nie trudno jest zauważyć schemat: 00000000ed... pierwsze 8 cyfr to zera! To jest właśnie częściowa kolizja z hipotetycznym hashem zaczynającym się na 8 zer. Zmiana chociażby 1 bitu na wejściu funkcji hashującej prowadzi (zakładając, że mamy porządną funkcję) do zmiany wielu bitów na wyjściu, dlatego podstawianie losowych liczb może w końcu doprowadzić do znalezienia takiej kolizji. Biorąc pod uwagę kolejną właściwość kryptograficznej funkcji skrótu

Kryptograficzna funkcja skrótu powinna spełniać kombinację następujących kryteriów, w zależności od zastosowania:

[…]

  • pseudolosowości (pseudorandomness),

[…]


Wikipedia - Kryptograficzne funkcje skrótu

wymaga to jednak wielu prób, a w najgorszym przypadku 2^k gdzie k jest ilością bitów które mają się równać zeru. Im większa liczba bitów równych zero, tym większą wartość ma nasza pieczęć/znaczek, wykonaliśmy więc więcej pracy (work) by go uzyskać i co najważniejsze mamy na to dowód (proof).

Jak wiadomo czas to pieniądz a w tym wypadku czas naszego procesora to pieniądz (albo znaczek pocztowy).


tu prawdopodobnie przydałoby się jakieś podsumowanie ale go tu nie ma