Hashcash

Hashcash jest narzędziem ograniczającym przyjmowanie wysyłanych masowo niechcianych wiadomości.

Metody walki ze spamem

Wiadomość nazywana spamem charakteryzuje się:

• jest niechciana
• wysyłana automatycznie do wielu odbiorców

Dotychczasowe podejście koncentrowało się na badaniu treści, zasada hashcash opiera się na ograniczaniu ich masowej wysyłki. Jego głównym obecnym wykorzystaniem jest pomoc użytkownikom stosującym hashcash uniknąć utraty wiadomości e-mail ze względu na systemy antyspamowe bazujące na zawartości i czarnych listach. Z powodu technologii antyspamowych mogą nastąpić straty e-maili. Popularnym podejściem do redukowania spamu są narzędzia badające mail czy nie wygląda na spam. Jeśli e-mail osób które próbują go wysłać przypadkowo wyzwala filtrowanie według słów kluczowych, taki mail może nigdy nie dotrzeć lub zostać filtrowany do folderu gdzie nie będzie czytany. Podobnie gdy znajdziemy się na czarnej liście. Sprzedawcy i autorzy anty spamowych narzędzi są zachęcani do zwolnienia maili wysyłanych z hashcash ze swoich czarnych list i filtrowania po treści. Alternatywą jest hashcash. Jest podejściem technicznym do redukowania wpływu spamu. Powoduje że mail staje się bardziej wiarygodny. Jeśli nadawca spamu musiałby użyć hashcash, znacząco spadłaby jego wydajność wysyłania wiadomości ponieważ dla każdej wymagane jest trochę czasu procesora. Hashcash jest metodą dodawania tekstowej pieczęci do nagłówka maila w celu udowodnienia że nadawca wydatkował przyzwoitą ilość czasu procesora do obliczenia pieczęci przed wysłaniem wiadomości. Innymi słowy, jeśli nadawca podjął pewien czas generowania pieczęci i wysłał maila, nie jest prawdopodobne że jest spamerem. Odbiorca może w sposób o nieznacznym koszcie obliczeniowym upewnić się, że pieczęć jest ważna. Jednak po stronie nadawcy jedynym możliwym sposobem wygenerowania ważnej pieczęci jest brute force, gdzie próbuje losowe wartości aż znajdzie. Teoria jest taka że spamerzy których model biznesowy opiera się na wysyłaniu wielkiej ilości maili bardzo małym kosztem nie mogą sobie na to pozwolić.

Zasada działania

Pieczęć hashcash stanowi dowód pracy procesora jaka musiała zostać wykonana do jej wygenerowania. Ilość koniecznej pracy po stronie nadawcy może być parametryzowana, natomiast po stronie odbiorcy można zweryfikować pieczęć błyskawicznie. Opiera się to na funkcji której wykonanie odbywa się szybko a znalezienie danych wejściowych dla zadanego wyjścia może trwać bardzo długo. Takimi funkcjami są funkcje skrótu (nazywanymi funkcjami haszującymi) które przyporządkowują ciągowi danych o dowolnej długości liczbę o stałej długości. Dla tej liczby w zależności od wyboru funkcji haszującej może być bardzo trudne znalezienie jakiegokolwiek ciągu z przeciwobrazu, to znaczy takiego dla którego skrótem będzie żądana liczba. Jako funkcji skrótu używana jest SHA-1 dająca w wyniku 160-bitową liczbę. Udowodnienie pracy hashcash jest znalezieniem ciągu z przeciwobrazu dla częściowo danej liczby, to znaczy ciągu którego skrót miałby wyzerowaną zadaną ilość najstarszych bitów (należy zaznaczyć, że w SHA-1 stosowana jest konwencja big endian). Przez wybranie ilości bitów które są równe 0, praca wymagana do znalezienia ciągu może być dowolnie droga – od ułamków sekund do minut i godzin. Natomiast weryfikacja jest wydajna ponieważ polega na jednokrotnym wykonaniu funkcji skrótu niezależnie od wymaganej ilości wyzerowanych bitów. Narzędzie hashcash pozwala na utworzenie pieczęci która jest dołączana do wysłanych maili i do weryfikowania pieczęci w otrzymanych e-mailach. Zwykle jest w postaci pluginu do programu pocztowego, który wstawia nagłówek X-Hashcash w sekcji nagłówków maila, przykładowo:

From: Someone <test@test.invalid>
To: Adam Back <adam@example.org>
Subject: test hashcash
Date: Thu, 26 Jun 2003 11:59:59 +0000
X-Hashcash: 0:030626:adam@example.org:6470e06d773e05a8

Dear Friend, Hi and welcome,

Nadawca przegotowuje nagłówek i dodaje początkowy losowy ciąg. Następnie oblicza 160-bitowy SHA-1 nagłówka. Jeśli określona liczba pierwszych bitów jest zerami (domyślnie 20) nagłówek jest dopuszczalny. Jeśli nie, bierze inny losowy ciąg i próbuje ponownie. Czas znalezienia odpowiedniego nagłówka rośnie wykładniczo względem ilości początkowym bitów które muszą być wyzerowane. Dla zwykłego użytkownika koszt jest akceptowalny jednak nie dla nadawców spamu wysyłających masowo maile. Po stronie odbiorcy komputer oblicza 160- bitowy hash SHA-1 całego łańcucha. Jeśli określona ilość pierwszych bitów jest zerowa, jest to dopuszczalna wiadomość. Komputer sprawdza datę w nagłówku: 030626 oznacza 26 czerwca 2003 w formacie YYMMDD. Format znacznika czasu powinien być oparty na UTCTime: 6-12 cyfr z pominiętym znakiem 'Z' na końcu. Czytając od lewej do prawej mamy w parach cyfry daty i czasu: rok(modulo 100),miesiąc,dzień, godzinę(24 godziny), minuty,sekundy (zwykle ograniczamy się tylko do daty). Strefa czasowa jest GMT(UTC). Dwie cyfry roku powinny być konwertowane do 4 cyfr roku przez porównanie do bieżącego roku. Powinna zostać użyta interpretacja, która jest bliższa bieżącej dacie. Zostało zaproponowane przez jednego z autorów serwera poczty który to implementował, że dla celów przedawnienia i porównania z datą w hashcash powinno się wziąć datę odbioru stemplowaną przez serwer poczty zamiast daty "dzisiaj". Zdecydowaną zaletą tego jest uniknięcie problemów gdzie użytkownik ściąga pocztę dużo później niż odebrał, np. po wakacjach a także kiedy korzysta z POP z trzymaniem na serwerze a następnie ładuje te same maile dużo później na innej maszynie. Serwer trzyma ścieżkę czasu odbioru w nagłówku poczty. Innym pozytywnym efektem ubocznym jest to że przedawnienie opiera się tylko na zegarze serwera MX/POP a nie na zegarze na komputerze klienta poczty. Jeśli pieczęć się przedawniła lub wskazuje na datę przyszłą, jest ona odrzucana, przy czym mamy 2 dni tolerancji dla wyrównania zegara i czasu trasy. Jeśli napotka się drugi raz tę samą pieczęć jest ona odrzucana, mamy bazę pieczęci które dostajemy z listami Domyślnie pieczęć przedawnia się po 28 dniach, ponieważ w przeciwnym wypadku baza rosła by nieograniczenie. Z powodów wydajnościowych przed wyszukaniem w bazie danych najpierw następuje sprawdzenie pieczęci. W bazie pieczęci mogą teoretycznie mieć różne okresy ważności, co pozwoliło by zmienić okres ważności przyszłych pieczęci bez wpływu na stare. Komputer odbiorcy sprawdza czy adres e-mail w nagłówku hashcash jest adresem odbiorcy (lub listy mailowej do której odbiorca jest zapisany). Gdy wszystko jest ważne, ta pieczęć jest dodawana do bazy danych. Jeśli nie była już w bazie danych, jest ważna.

int valid_stamp( stamp, needbits/*np. 20 bitów*/ )
{
 if stamp.date > Received.time + 2days
   return futuristic
 if stamp.date < Received.time - 28days - 2days
   return expired
 if count_zero_bits( SHA1( stamp ) ) < needbits
   return insufficient
 if in_spent_database( stamp )
   return spent
 return true
}

valid_hashcash( myemail )
{
  while stamp = get_next_x_hashcash_header()
    if stamp.email == myemail
    {
    if valid_stamp( stamp )
    {
      add_to_spent_database( stamp )
      return true
    }
  }
  return false
}

• Nadawca spamu nie może wysłać raz obliczonej pieczęci do wielu różnych ludzi ponieważ pieczęć jest ważna tylko dla jednego odbiorcy. Dla każdego wymagane jest generowanie od nowa.
• Nie może do jednego odbiorcy wysyłać wielu wiadomości z jedną pieczęcią, ponieważ ważna jest ona jeden raz; każdy odbiorca ma bazę pieczęci.
• Przeterminowane pieczęcie wyrzucane są z bazy. Domyślnie okres przedawnienia wynosi 28 dni.
• Nie można użyć też pieczęci starszych których nie ma już w bazie, ponieważ sprawdzana jest data.
• Sama zmiana daty pociąga za sobą konieczność wygenerowania nowej pieczęci.
• Nadawca spamu który chciałby przepełnić czyjąś skrzynkę musiałby liczyć się z kosztami tworzenia nowych pieczęci.
• Odrzucane są pieczęcie z datą przyszłą.

Wiadomość która ma wielu odbiorców powinna mieć dla każdego nagłówek X-Hashcash:

Wersja 0

Pieczęć składa się z kilku pól oddzielonych znakiem dwukropkiem. Ma postać:

stamp = ver:time:resource:rand

Parametry ver i time są definiowane jako dwa pierwsze pola oddzielone dwukropkiem. Parametr rand jest definiowany jako ostatni; łańcuch resource jest pomiędzy dwukropkiem następującym po polu time a dwukropkiem poprzedzającym pole rand. Ta definicja pozwala aby łańcuch resource zawierał znaki dwukropka. Parametr rand jest łańcuchem Ascii zmiennej długości składający się z dowolnych znaków z wyjątkiem znaków białych,nowej linii oraz dwukropka. Można tu używać podzbioru np. cyfr heksadecymalnych lub znaków ze zbioru base64 jednak wszystkie implementacje muszą akceptować wszelkie dopuszczalne znaki i łańcuchy rand o długości do 128 znaków. W praktyce rand może być 64 bitową liczbą zakodowaną w hex lub Base64. Przykład:

0:030626:adam@example.org:6470e06d773e05a8

Wersja 1

Celem zmiany formatu na wersję 1 jest danie ludziom możliwości dodawania rozszerzeń, tak że różne systemy używające hashcash mogą używać rozszerzeń które rozumieją i ignorować pozostałe bez konieczności zmiany głównej wersji formatu. Format pieczęci:

 ver:bits:date:resource:[exts]:rand:counter

gdzie:

• ver = 1
• bits = informacja o tym jak wiele początkowych bitów ma być wyzerowanych w skrócie sha powstałego z pieczęci

jeśli nie podano ilości, domyślnie jest 20 bitów.

• date = w formacie YYMMDD[hhmm[ss]]
• resource = nazwą usługi lub adres dla którego jest tworzona pieczęć, łańcuch oznaczający zwykle adres email, w ogólności może być to np. adres IP; w przypadku e-mail nazwa zasobu jest adresem odbiorcy w postaci user@example.com

jest małe uproszczenie : plik resource nie może zawierać dwukropka

• exts = rozszerzenia – ignorowane w bieżącej wersji

 Format rozszerzeń: [name1[=val1[,val2...]];[name2[=val1[,val2...]]]]
 Uwaga że wartość może również zawierać =, przykład:
           name1=2,3;name2;name3=var1=2,var2=3,2,val
 name1 ma dwie wartości 2 i 3;
 rozszerzenie 2 nie przyjmuje żadnej wartości; rozszerzenie name3 ma 4 wartości "var1=2","var2=3", "2" i "val".
 exts = ext,';',ext,';',ext,';',ext,';'...
 ext = name,'=',rest
 rest = val,',',val,',',val,',',val,','...
 Uwaga: wartości mogą zawierać "=",
 Dodajmy, że wartość rozszerzenia powinna być ograniczona do drukowalnego 7-bitowego ASCII bez spacji

• rand = łańcuch losowych znaków z alfabetu a-zA-Z0-9+/= pozwalający uniknąć kolizji z inną pieczęcią nadawcy

może być przykładowo 16-cyfrowa 64 bitowa liczba heksadecymalna lub losowy ciąg inny mniej więcej tej długości counter = aby znaleźć pieczęć z żądaną ilością początkowych zerowych bitów skrótu potrzeba wypróbować wiele różnych łańcuchów, ten licznik jest zwiększany po każdej próbie. Licznik jest także złożony ze znaków z alfabetu a-zA-Z0-9+/= ale zalecana jest liczba heksadecymalna. (Uwaga: implementacja nie wymaga aby zliczać kolejno) W wersji 1 jest jawnie podana ilość wiodących zer, nazwijmy ją claimed_value, wtedy measured_value jest ilościa obliczoną zer. Rzeczywista wartość obliczona jest

  value = ( measured_value < claimed_value ) ? 0 : claimed_value;

to oznacza że pieczęć nigdy nie ma wartości wyższej niż żądana, jeśli losowo udało się uzyskać więcej zer nie odnosi się z tego korzyści, pieczęć jest warta tyle ile wynosi żądaną wartość, z drugiej strony, jeśli ma mniej bitów niż twierdzi, jest bezwartościowa.

Generowanie

        rand := random_start();
        repeat
           rand := rand + 1
        until wszystkie najstarsze bity w ilości bits SHA1( ver:bits:date:resource:exts:rand:counter ) są zerowe

Możliwa implementacja Na początku inicjujemy np. za pomocą Randomize, czasu (QueryPerformanceCounter,rdtsc) czy częścią Guid (CoCreateGuid). Otrzymujemy liczbę 64 bitową. Zwiększamy ją kolejno. Ewentualnie można wybierać liczbę niesekwencyjnie, np. rand := część ostatniego SHA. Wartość rand musi być wybrana losowo. Jeśli rand będzie nie wybrany losowo, kolizje mogą się zdarzać przypadkowo lub być złośliwie wywołane pomiędzy różnymi nadawcami do tego samego odbiorcy. Długość wartości rand powinna być wybrana tak, aby być duża na tyle że prawdopodobieństwo kolizji pomiędzy nadawcami do tego samego odbiorcy było pomijalnie małe. Zaleca się minimum użyć zakresu 2^64 wartości. Ponieważ generowanie trwa jakiś czas, lepszej jakości pluginy mogą już tworzyć pieczęć podczas gdy nadawca redaguje swojego maila.

Weryfikacja

Weryfikacja hashcash jest bardzo prosta, jedyna skomplikowana rzecz to obliczenie funkcji skrótu SHA-1 która jest powszechnie znana i dostępna w bibliotekach różnych języków Pieczęć jest weryfikowana przez zliczanie jak wiele najbardziej znaczących bitów jest wyzerowanych na wyjściu funkcji SHA-1 weźmy przykład

                1:20:110501:fake@example.com::4A353BA13C3394CD:85605

daje nam

                sha = 487cd6bd943ec919b14c889f971cdc28366e4e1c

SHA liczone jest z pieczęci potraktowanej jako ciąg znaków, kolejno z bajtów

'1',':','2','0',':','1' ….

Jak można zobaczyć, mamy 5 najbardziej znaczących (big endian) cyfr heksadecymalnych (20 najbardziej znaczących bitów) wyzerowanych (akurat w tym przypadku bitów zerowych jest więcej niż 20 ale wystarczy 20) Data 110501 to 1 maja 2011 roku (rok module 100), 85605 to 546309 wykonanych prób. Pieczęcie nie powinny być akceptowane więcej niż jeden raz, powinna zostać zaimplementowana baza danych użytych pieczęci. Do redukcji rozmiaru tej bazy powinien być zdefiniowany termin ich unieważnienia.

Uwagi

Hashcash jest obsługiwana w SpamAssassin w wersji 2.70. Na dzień dzisiejszy minusem jest to, że nie można blokować maili bez pieczęci hashcash, ponieważ odrzuca się w ten sposób zdecydowaną większość pożądanych maili. Powinny być tworzone białe listy jeśli chodzi o listy mailowe, czy rejestracje na forach.

Z powodu pojawiania się coraz szybszych komputerów można przyjąć więcej niż 20 bitów, które mają być wyzerowane, tak aby generowanie trwało średnio np. 30 sekund, które można spędzić na edycji maila. Jednak znalezienie podpisu może trwać zarówno krócej niż średnia jak i dużo dłużej, podczas gdy przy masowej wysyłce liczy się czas średni. Użytkownicy mogą znacznie różnić się prędkościami maszyny przy czym spamer może posiadać specjalistyczne oprogramowanie, które wykonuje obliczenia korzystając z możliwości przetwarzania rozproszonego na karcie graficznej.

Zobacz też

• Sender Policy Framework

Linki zewnętrzne

• http://www.hashcash.org/source/ – oryginalne źródła hashcash