haszysz

Hashcash to system proof-of-work używany do ograniczania spamu e-mailowego i ataków typu „odmowa usługi” . Hashcash został zaproponowany w 1997 roku przez Adama Backa i opisany bardziej formalnie w artykule Backa z 2002 roku „Hashcash - A Denial of Service Counter-Measure”.

Tło

Pomysł „… aby wymagać od użytkownika obliczenia umiarkowanie trudnej, ale nie trudnej funkcji…” został zaproponowany przez Cynthię Dwork i Moni Naor w ich artykule z 1992 r. „Pricing via Processing or Combatting Junk Mail”.

Jak to działa

Hashcash to kryptograficzny algorytm dowodu pracy oparty na haszu, który wymaga określonej ilości pracy do obliczenia, ale dowód można skutecznie zweryfikować. W przypadku wiadomości e-mail do nagłówka wiadomości e-mail dodaje się tekstowe kodowanie znaczka hashcash, aby udowodnić, że nadawca poświęcił niewielką ilość czasu procesora na obliczenie stempla przed wysłaniem wiadomości e-mail. Innymi słowy, ponieważ nadawca poświęcił trochę czasu na wygenerowanie znaczka i wysłanie wiadomości e-mail, jest mało prawdopodobne, aby był spamerem. Odbiorca może przy znikomym koszcie obliczeniowym zweryfikować ważność stempla. Jednak jedynym znanym sposobem na znalezienie nagłówka z niezbędnymi właściwościami jest brutalna siła , próbowanie losowych wartości, aż do znalezienia odpowiedzi; chociaż testowanie pojedynczego ciągu jest łatwe, satysfakcjonujące odpowiedzi są na tyle rzadkie, że znalezienie odpowiedzi będzie wymagało znacznej liczby prób.

Hipoteza jest taka, że spamerzy, których model biznesowy opiera się na możliwości wysyłania dużej liczby e-maili przy bardzo niskim koszcie na wiadomość, przestaną być rentowni, jeśli za każdy wysyłany przez nich spam poniosą nawet niewielki koszt. Odbiorcy mogą zweryfikować, czy nadawca dokonał takiej inwestycji i wykorzystać wyniki do filtrowania poczty.

Szczegóły techniczne

Linia nagłówka wygląda mniej więcej tak:

X-Hashcash: 1:20:1303030600:[email protected]::McMybZIhxKXu57jd:ckvi

Nagłówek zawiera:

ver : wersja formatu Hashcash, 1 (która zastępuje wersję 0).
bits : Liczba bitów „częściowego obrazu wstępnego” (zero) w zaszyfrowanym kodzie.
data : godzina wysłania wiadomości w formacie RRMMDD[ggmm[ss]] .
zasób : przesyłany ciąg danych zasobu, np. adres IP lub adres e-mail.
ext : Rozszerzenie (opcjonalne; ignorowane w wersji 1).
rand : Ciąg losowych znaków zakodowanych w formacie base-64 .
counter : Licznik binarny, zakodowany w formacie base-64.

Nagłówek zawiera adres e-mail odbiorcy, datę wysłania wiadomości oraz informacje potwierdzające wykonanie wymaganych obliczeń. Obecność adresu e-mail odbiorcy wymaga obliczenia innego nagłówka dla każdego odbiorcy. Data umożliwia odbiorcy zarejestrowanie ostatnio otrzymanych nagłówków i upewnienie się, że nagłówek jest unikalny dla wiadomości e-mail.

Strona nadawcy

Nadawca przygotowuje nagłówek i dołącza wartość licznika zainicjowaną do losowej liczby. Następnie oblicza 160-bitowy skrót SHA-1 nagłówka . Jeśli pierwsze 20 bitów (tj. 5 najbardziej znaczących cyfr szesnastkowych) skrótu to same zera, to jest to akceptowalny nagłówek. Jeśli nie, nadawca zwiększa licznik i ponownie próbuje hashować. Spośród 2 ¹⁶⁰ możliwych wartości skrótu, 2 ¹⁴⁰ wartości skrótu spełnia to kryterium. Zatem szansa na losowe wybranie nagłówka, który będzie miał 20 zer na początku skrótu, wynosi 1 do 2 ²⁰ (ok. 10 ⁶ lub mniej więcej jeden na milion). Liczba prób, które nadawca musi podjąć, aby uzyskać prawidłową wartość skrótu, jest modelowana za pomocą rozkładu geometrycznego . Dlatego nadawca będzie musiał wypróbować średnio 2 ²⁰ wartości, aby znaleźć prawidłowy nagłówek. Biorąc pod uwagę rozsądne szacunki czasu potrzebnego do obliczenia skrótu, znalezienie tego zajęłoby około jednej sekundy. Nie ma bardziej wydajnej metody niż to podejście brutalnej siły, aby znaleźć prawidłowy nagłówek.

Zwykły użytkownik komputera stacjonarnego nie odczuwałby znacznych niedogodności z powodu czasu przetwarzania wymaganego do wygenerowania ciągu Hashcash. Jednak spamerzy znacznie ucierpieliby z powodu dużej liczby wysyłanych przez nich wiadomości spamowych.

Strona odbiorcy

Technicznie system jest wdrażany w następujących krokach:

Komputer odbiorcy oblicza 160-bitowy skrót SHA-1 całego ciągu (np. "1:20:060408:[email protected]::1QTjaYd7niiQA/sc:ePa" ). Zajmuje to około dwóch mikrosekund na maszynie 1 GHz, czyli znacznie mniej niż czas potrzebny na odebranie reszty wiadomości e-mail. Jeśli pierwsze 20 bitów nie ma wartości zero, hash jest nieprawidłowy. (Późniejsze wersje mogą wymagać większej liczby bitów do zera w miarę wzrostu prędkości przetwarzania maszyny).
Komputer odbiorcy sprawdza datę w nagłówku (np. „060408” , co odpowiada dacie 8 kwietnia 2006 r.). Jeżeli nie przypada w ciągu dwóch dni od aktualnej daty, jest nieważny. (Dwudniowe okno kompensuje przesunięcie zegara i czas routingu sieciowego między różnymi systemami).
Komputer odbiorcy sprawdza, czy adres e-mail w ciągu skrótu pasuje do któregokolwiek z prawidłowych adresów e-mail zarejestrowanych przez odbiorcę lub pasuje do którejkolwiek z list mailingowych, do których subskrybuje odbiorca. Jeśli dopasowanie nie zostanie znalezione, ciąg skrótu jest nieprawidłowy.
Komputer odbiorcy wstawia ciąg skrótu do bazy danych. Jeśli ciąg znajduje się już w bazie danych (co wskazuje, że podjęto próbę ponownego użycia ciągu skrótu), jest nieprawidłowy.

Jeśli ciąg skrótu przejdzie wszystkie te testy, jest uważany za prawidłowy ciąg skrótu. Wszystkie te testy zajmują znacznie mniej czasu i miejsca na dysku niż otrzymanie treści wiadomości e-mail.

Wymagany wysiłek

Czas potrzebny do obliczenia takiej kolizji mieszania jest wykładniczy z liczbą bitów zerowych. Można więc dodać dodatkowe bity zerowe (podwajając czas potrzebny do obliczenia skrótu z każdym dodatkowym bitem zerowym), dopóki spamerzy nie będą mogli wygenerować prawidłowych wierszy nagłówka.

Potwierdzenie, że nagłówek jest prawidłowy, jest znacznie szybsze i zawsze zajmuje tyle samo czasu, bez względu na to, ile bitów zerowych jest wymaganych dla prawidłowego nagłówka, ponieważ wymaga to tylko jednej operacji mieszania.

Zalety i wady

System Hashcash ma tę przewagę nad propozycjami mikropłatności dotyczącymi legalnych wiadomości e-mail, że nie ma w nich żadnych prawdziwych pieniędzy. Ani nadawca, ani odbiorca nie muszą płacić, dzięki czemu można całkowicie uniknąć problemów administracyjnych związanych z jakimkolwiek systemem mikropłatności oraz kwestii moralnych związanych z pobieraniem opłat za e-mail.

Z drugiej strony, ponieważ Hashcash wymaga wydatkowania potencjalnie znacznych zasobów obliczeniowych na każdą wysyłaną wiadomość e-mail, nieco trudno jest dostroić idealną ilość średniego czasu, jaki klienci chcieliby poświęcić na obliczenie prawidłowego nagłówka. Może to oznaczać rezygnację z dostępności z niskobudżetowych systemów wbudowanych lub ryzyko, że wrogie hosty nie zostaną wystarczająco zakwestionowane, aby zapewnić skuteczny filtr przed spamem.

Hashcash jest również dość prosty do zaimplementowania w programach użytkownika poczty i filtrach spamu. Nie jest potrzebny centralny serwer. Hashcash można wdrażać stopniowo — dodatkowy nagłówek Hashcash jest ignorowany, gdy jest odbierany przez klientów pocztowych, którzy go nie rozumieją.

Pewna wiarygodna analiza wykazała, że prawdopodobny jest tylko jeden z następujących przypadków: albo wiadomość e-mail niebędąca spamem utknie z powodu braku mocy obliczeniowej nadawcy, albo wiadomość e-mail będąca spamem nadal się przedostanie. Przykłady każdego z nich obejmują odpowiednio scentralizowaną topologię poczty e-mail (taką jak lista mailingowa ), w której jakiś serwer ma wysyłać ogromną liczbę legalnych wiadomości e-mail, oraz botnety lub farmy klastrów, za pomocą których spamerzy mogą ogromnie zwiększyć swoją moc obliczeniową .

Większość z tych problemów można rozwiązać. Np. botnety mogą wygasać szybciej, ponieważ użytkownicy zauważają duże obciążenie procesora i podejmują środki zaradcze, a serwery list mailingowych mogą być rejestrowane na białych listach na hostach subskrybentów, a tym samym zwalniane z wyzwań związanych z hashcashem.

Innym przewidywanym problemem jest to, że komputery stają się coraz szybsze zgodnie z prawem Moore'a . Tak więc trudność wymaganych obliczeń musi z czasem rosnąć. Można się jednak spodziewać, że kraje rozwijające się będą korzystać ze starszego sprzętu, co oznacza, że będzie im coraz trudniej uczestniczyć w systemie poczty elektronicznej. Dotyczy to również osób o niższych dochodach w krajach rozwiniętych, których nie stać na najnowszy sprzęt.

Podobnie jak hashcash, kryptowaluty używają funkcji skrótu jako systemu proof-of-work. Rozwój kryptowalut stworzył popyt na maszyny górnicze oparte na ASIC . Chociaż większość kryptowalut korzysta z funkcji skrótu SHA-256 , ta sama technologia ASIC może być wykorzystana do tworzenia programów do rozwiązywania problemów hashcash, które są o trzy rzędy wielkości szybsze niż procesor konsumencki, zmniejszając przeszkodę obliczeniową dla spamerów.

Aplikacje

kopalnia bitcoinów

W przeciwieństwie do hashcash w aplikacjach pocztowych, które polegają na odbiorcach, którzy ręcznie ustawiają ilość pracy mającą na celu odstraszenie złośliwych nadawców, sieć kryptowalut Bitcoin stosuje inne oparte na hashach wyzwanie proof-of-work, aby umożliwić konkurencyjne wydobywanie bitcoinów . Górnik bitcoinów uruchamia program komputerowy, który zbiera niepotwierdzone transakcje od użytkowników w sieci. Razem mogą one utworzyć „blok” i zarobić górnika, ale blok jest akceptowany przez sieć tylko wtedy, gdy jego hash spełnia docelowy poziom trudności sieci. Tak więc, podobnie jak w przypadku haszyszu, górnicy muszą brutalnie odkryć „nonce” , który zawarty w bloku daje akceptowalny hasz.

W przeciwieństwie do hashcash, cel trudności Bitcoina nie określa minimalnej liczby wiodących zer w haszu. Zamiast tego skrót jest interpretowany jako (bardzo duża) liczba całkowita, a ta liczba całkowita musi być mniejsza niż docelowa liczba całkowita. Jest to konieczne, ponieważ sieć Bitcoin musi okresowo dostosowywać swój poziom trudności, aby utrzymać średni czas 10 minut między kolejnymi blokami. Gdyby wziąć pod uwagę tylko wiodące zera, wówczas trudność mogłaby zostać podwojona lub zmniejszona o połowę, powodując znaczne przeregulowanie lub niedostosowanie w odpowiedzi na niewielkie zmiany średniego czasu bloku. Mimo to liczba wiodących zer w celu stanowi dobre przybliżenie aktualnego poziomu trudności. w styczniu 2020 r. blok #614525 miał 74 wiodące zera.

Filtry spamu

Hashcash jest używany jako potencjalne rozwiązanie dla fałszywych alarmów z automatycznymi systemami filtrowania spamu, ponieważ legalni użytkownicy rzadko będą odczuwać niedogodności z powodu dodatkowego czasu potrzebnego na wydobycie znaczka. SpamAssassin może sprawdzać znaczki Hashcash od wersji 2.70, przypisując negatywny wynik (tj. mniejsze prawdopodobieństwo spamu) dla ważnych, niewydanych znaczków Hashcash. Jednak chociaż wtyczka hashcash jest domyślnie włączona, nadal musi być skonfigurowana z listą wzorców adresów, które muszą być zgodne z polem zasobu Hashcash, zanim zostanie użyta.

Klienci poczty e-mail

Projekt oprogramowania Penny Post na SourceForge implementuje Hashcash w kliencie pocztowym Mozilla Thunderbird . Nazwa projektu pochodzi od historycznej dostępności konwencjonalnych usług pocztowych, które kosztowały nadawcę tylko jednego grosza; zobacz Penny Post , aby uzyskać informacje o takich usługach pocztowych w historii.

E-mail stempel pocztowy

Firma Microsoft zaprojektowała i wdrożyła również obecnie przestarzałą otwartą specyfikację, podobną do Hashcash, a jednak niekompatybilną z Hashcash, Email Postmark, w ramach swojej Coordinated Spam Reduction Initiative (CSRI). Wariant Hashcash ze stemplem pocztowym poczty e-mail firmy Microsoft jest zaimplementowany w składnikach infrastruktury poczty Microsoft Exchange, Outlook i Hotmail. Różnice w formatach między Hashcash a stemplem pocztowym poczty e-mail firmy Microsoft polegają na tym, że stempel pocztowy miesza treść oprócz odbiorcy i używa zmodyfikowanego SHA-1 jako funkcji skrótu oraz wykorzystuje wiele podrzędnych zagadek, aby zmniejszyć dowód wariancji pracy.

Blogi

Podobnie jak poczta elektroniczna, blogi często padają ofiarą spamu w komentarzach . Niektórzy właściciele blogów używali skryptów hashcash napisanych w JavaScript , aby spowolnić spamerów w komentarzach. Niektóre skrypty (takie jak wp-hashcash) twierdzą, że implementują hashcash, ale zamiast tego polegają na zaciemnianiu JavaScript, aby zmusić klienta do wygenerowania pasującego klucza; chociaż wymaga to pewnej mocy obliczeniowej, nie wykorzystuje algorytmu hashcash ani znaczków hashcash.

Reputacja

Na rynku cyfrowym usługodawcy mogą wykorzystywać haszysz do budowania reputacji i przyciągania klientów. Aby zbudować reputację, usługodawca najpierw wybiera klucz publiczny jako swój identyfikator, a następnie brutalnie odkrywa wartość jednorazową, która po połączeniu z identyfikatorem daje skrót skrótu z kilkoma zerami na początku. Im więcej zer, tym wyższa reputacja.

Własność intelektualna

Hashcash nie jest opatentowany, a implementacja referencyjna i większość innych implementacji to wolne oprogramowanie. Hashcash jest dołączony lub dostępny dla wielu dystrybucji Linuksa .

RSA złożyło oświadczenia dotyczące praw własności intelektualnej do IETF dotyczące zagadek klienckich w kontekście RFC opisującego zagadki klienckie (nie hashcash). Dokument RFC zawierał hashcash w tytule i odwoływał się do hashcash, ale opisany w nim mechanizm jest interaktywnym wyzwaniem o znanym rozwiązaniu, które jest bardziej podobne do zagadek klienckich; hashcash jest nieinteraktywny i dlatego nie ma znanego rozwiązania. W każdym razie oświadczenie RSA dotyczące praw własności intelektualnej nie może odnosić się do hashcash, ponieważ hashcash poprzedza (marzec 1997 r.) publikację zagadek dla klientów (luty 1999 r.)

Zobacz też

Penny Black (projekt badawczy)

Notatki

Adam Back, „Hashcash – przeciwdziałanie odmowie usługi”, raport techniczny, sierpień 2002 (PDF) .
Ben Laurie i Richard Clayton, „Dowód pracy” dowodzi, że nie działa ”, WEIS 04. (PDF) .
Dwork, C. i Naor, M. (1992) „Wycena poprzez przetwarzanie lub zwalczanie wiadomości-śmieci”, Crypto '92, s. 139–147. (PDF)

Linki zewnętrzne