Hashcash

Hashcash är ett proof-of-work-system som används för att begränsa e-postspam och överbelastningsattacker . Hashcash föreslogs 1997 av Adam Back och beskrivs mer formellt i Backs uppsats från 2002 "Hashcash - A Denial of Service Counter-Measure".

Bakgrund

Idén "...att kräva att en användare beräknar en måttligt hård, men inte svåröverskådlig funktion..." föreslogs av Cynthia Dwork och Moni Naor i deras 1992 uppsats "Pricing via Processing or Combatting Junk Mail".

Hur det fungerar

Hashcash är en kryptografisk hash-baserad algoritm för bevis-på-arbete som kräver en valbar mängd arbete att beräkna, men beviset kan verifieras effektivt. För e-postanvändning läggs en textkodning av en hashcash-stämpel till i rubriken på ett e-postmeddelande för att bevisa att avsändaren har använt en blygsam mängd CPU-tid på att beräkna stämpeln innan e-postmeddelandet skickades. Med andra ord, eftersom avsändaren har tagit en viss tid på sig att generera stämpeln och skicka e-postmeddelandet, är det osannolikt att de är en spammare. Mottagaren kan till en försumbar beräkningskostnad verifiera att stämpeln är giltig. Det enda kända sättet att hitta en rubrik med de nödvändiga egenskaperna är dock brute force , att prova slumpmässiga värden tills svaret hittas; Även om det är enkelt att testa en enskild sträng, är tillfredsställande svar sällsynta nog att det kommer att kräva ett stort antal försök att hitta svaret.

Hypotesen är att spammare, vars affärsmodell förlitar sig på deras förmåga att skicka ett stort antal e-postmeddelanden med mycket låg kostnad per meddelande, kommer att sluta vara lönsamma om det ens är en liten kostnad för varje skräppost de skickar. Mottagarna kan verifiera om en avsändare gjort en sådan investering och använda resultaten för att filtrera e-post.

Tekniska detaljer

Rubrikraden ser ut ungefär så här:

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

Rubriken innehåller:

ver : Hashcash-format version, 1 (som ersätter version 0).
bits : Antalet "partiell pre-image" (noll) bitar i den hashade koden.
datum : Tiden då meddelandet skickades, i formatet ÅÅMMDD[ttmm[ss]] .
resurs : Resursdatasträng som överförs, t.ex. en IP-adress eller e-postadress.
ext : Tillägg (valfritt; ignoreras i version 1).
rand : Sträng av slumpmässiga tecken, kodad i bas-64- format.
räknare : Binär räknare, kodad i bas-64-format.

Rubriken innehåller mottagarens e-postadress, datum för meddelandet och information som bevisar att den nödvändiga beräkningen har utförts. Närvaron av mottagarens e-postadress kräver att en annan rubrik beräknas för varje mottagare. Datumet gör det möjligt för mottagaren att spela in rubriker som tagits emot nyligen och för att säkerställa att rubriken är unik för e-postmeddelandet.

Avsändarens sida

Avsändaren förbereder en rubrik och lägger till ett räknarvärde initierat till ett slumptal. Den beräknar sedan 160-bitars SHA-1- hash för huvudet. Om de första 20 bitarna (dvs de 5 mest signifikanta hexadecimala siffrorna) i hashen alla är nollor, är detta en acceptabel rubrik. Om inte, ökar avsändaren räknaren och försöker hashen igen. Av 2 ¹⁶⁰ möjliga hashvärden finns det 2 ¹⁴⁰ hashvärden som uppfyller detta kriterium. Således är chansen att slumpmässigt välja en rubrik som kommer att ha 20 nollor som början av hashen 1 på 2 ²⁰ (ungefär 10 ⁶ , eller ungefär en på en miljon). Antalet gånger som avsändaren behöver försöka få ett giltigt hashvärde modelleras av geometrisk fördelning . Därför måste avsändaren i genomsnitt prova 2 ²⁰ värden för att hitta en giltig rubrik. Givet rimliga uppskattningar av den tid som krävs för att beräkna hashen, skulle detta ta ungefär en sekund att hitta. Ingen effektivare metod än denna brute force-metod är känd för att hitta en giltig rubrik.

En normal användare på en stationär PC skulle inte bli nämnvärt besvärande av den processtid som krävs för att generera Hashcash-strängen. Spammare skulle dock drabbas avsevärt på grund av det stora antalet skräppostmeddelanden som skickas av dem.

Mottagarens sida

Tekniskt implementeras systemet med följande steg:

Mottagarens dator beräknar 160-bitars SHA-1 -hash för hela strängen (t.ex. "1:20:060408:[email protected]::1QTjaYd7niiQA/sc:ePa" ) . Detta tar ungefär två mikrosekunder på en 1 GHz-maskin, mycket kortare tid än den tid det tar för resten av e-postmeddelandet att tas emot. Om de första 20 bitarna inte alla är noll är hashen ogiltig. (Senare versioner kan kräva fler bitar för att vara noll när maskinbearbetningshastigheterna ökar.)
Mottagarens dator kontrollerar datumet i rubriken (t.ex. "060408" , som representerar datumet 8 april 2006). Om det inte är inom två dagar från det aktuella datumet är det ogiltigt. (Tvådagarsfönstret kompenserar för klockskevhet och nätverksdirigeringstid mellan olika system.)
Mottagarens dator kontrollerar om e-postadressen i hashsträngen matchar någon av de giltiga e-postadresserna som registrerats av mottagaren, eller matchar någon av e-postlistorna som mottagaren prenumererar på. Om en matchning inte hittas är hashsträngen ogiltig.
Mottagarens dator infogar hashsträngen i en databas. Om strängen redan finns i databasen (vilket indikerar att ett försök görs att återanvända hashsträngen) är den ogiltig.

Om hashsträngen klarar alla dessa tester anses den vara en giltig hashsträng. Alla dessa tester tar mycket mindre tid och diskutrymme än att ta emot huvudinnehållet i e-postmeddelandet.

Krävd ansträngning

Den tid som krävs för att beräkna en sådan hashkollision är exponentiell med antalet nollbitar. Så ytterligare nollbitar kan läggas till (fördubbling av den tid som behövs för att beräkna en hash med varje extra nollbit) tills det är för dyrt för spammare att generera giltiga rubrikrader.

Att bekräfta att rubriken är giltig går mycket snabbare och tar alltid lika lång tid, oavsett hur många nollbitar som krävs för en giltig rubrik, eftersom detta bara kräver en enda hashoperation.

Fördelar och nackdelar

Hashcash-systemet har fördelen framför mikrobetalningsförslag som gäller legitim e-post att inga riktiga pengar är inblandade. Varken avsändaren eller mottagaren behöver betala, därför undviks de administrativa problem som är involverade i något mikrobetalningssystem och moraliska frågor relaterade till debitering för e-post.

Å andra sidan, eftersom Hashcash kräver att potentiellt betydande beräkningsresurser förbrukas på varje e-postmeddelande som skickas, är det lite svårt att ställa in den idealiska mängden genomsnittlig tid man vill att klienter ska spendera på att beräkna en giltig rubrik. Detta kan innebära att man offra tillgängligheten från inbäddade system med låga slutenheter eller annars riskerar att fientliga värdar inte utmanas tillräckligt för att tillhandahålla ett effektivt filter från skräppost.

Hashcash är också ganska enkelt att implementera i e-postanvändaragenter och spamfilter. Ingen central server behövs. Hashcash kan distribueras stegvis – den extra Hashcash-huvudet ignoreras när det tas emot av e-postklienter som inte förstår det.

En rimlig analys drog slutsatsen att endast ett av följande fall är troligt: antingen kommer e-post som inte är skräppost att fastna på grund av avsändarens bristande bearbetningskraft, eller så kommer skräpposten fortfarande att komma igenom. Exempel på var och en inkluderar en centraliserad e-posttopologi (som en e- postlista ), där någon server ska skicka en enorm mängd legitima e-postmeddelanden, och botnät eller klusterfarmar med vilka spammare kan öka sin processorkraft enormt. .

De flesta av dessa frågor kan lösas. Till exempel kan botnät upphöra snabbare eftersom användare märker den höga CPU-belastningen och vidtar motåtgärder, och e-postlistservrar kan registreras i vita listor på prenumeranternas värdar och därmed befrias från hashcash-utmaningarna.

Ett annat förväntat problem är att datorer fortsätter att bli snabbare enligt Moores lag . Så svårigheten för de beräkningar som krävs måste ökas med tiden. Däremot kan utvecklingsländer förväntas använda äldre hårdvara, vilket gör att de får allt svårare att delta i e-postsystemet. Detta gäller även individer med lägre inkomster i utvecklade länder som inte har råd med den senaste hårdvaran.

Liksom hashcash använder kryptovalutor en hashfunktion som sitt proof-of-work-system. Uppkomsten av kryptovaluta har skapat en efterfrågan på ASIC -baserade gruvmaskiner. Även om de flesta kryptovalutor använder SHA-256 , kan samma ASIC-teknik användas för att skapa hashcash-lösare som är tre storleksordningar snabbare än en konsument-CPU, vilket minskar beräkningshinderet för spammare.

Ansökningar

Bitcoin gruvdrift

I motsats till hashcash i e-postapplikationer som förlitar sig på att mottagarna manuellt ställer in en mängd arbete som är avsett att avskräcka skadliga avsändare, använder Bitcoin kryptovalutanätverket en annan hashbaserad proof-of-work- utmaning för att möjliggöra konkurrenskraftig Bitcoin-brytning . En Bitcoin-gruvarbetare driver ett datorprogram som samlar in obekräftade transaktioner från användare på nätverket. Tillsammans kan dessa bilda ett "block" och tjäna en betalning till gruvarbetaren, men ett block accepteras bara av nätverket om dess hash uppfyller nätverkets svårighetsmål. Så, precis som i hashcash, måste gruvarbetare med brute force upptäcka den "nonce" som, när den ingår i blocket, resulterar i en acceptabel hash.

inte Bitcoins svårighetsmål ett minsta antal inledande nollor i hashen. Istället tolkas hashen som ett (mycket stort) heltal, och detta heltal måste vara mindre än målheltalet. Detta är nödvändigt eftersom Bitcoin-nätverket regelbundet måste justera sin svårighetsnivå för att upprätthålla en genomsnittlig tid på 10 minuter mellan på varandra följande block. Om endast inledande nollor beaktades, skulle svårigheten bara kunna fördubblas eller halveras, vilket gör att justeringen kraftigt över- eller underskrider som svar på små förändringar i den genomsnittliga blockeringstiden. Ändå fungerar antalet inledande nollor i målet som en bra approximation av den aktuella svårigheten. I januari 2020 block #614525 74 inledande nollor.

Spamfilter

Hashcash används som en potentiell lösning för falska positiva resultat med automatiserade system för skräppostfiltrering, eftersom legitima användare sällan kommer att besväras av den extra tid det tar att bryta ett frimärke. SpamAssassin har kunnat leta efter Hashcash-stämplar sedan version 2.70 och tilldela ett negativt betyg (dvs mindre sannolikt att det är spam) för giltiga, oanvända Hashcash-stämplar. Men även om hashcash-pluginet är på som standard, måste det fortfarande konfigureras med en lista över adressmönster som måste matcha mot hashcash-resursfältet innan det kommer att användas.

E-postklienter

Mjukvaruprojektet Penny Post på SourceForge implementerar Hashcash i e-postklienten Mozilla Thunderbird . Projektet är uppkallat efter den historiska tillgängligheten av konventionella posttjänster som kostar avsändaren bara en krona; se Penny Post för information om sådana e-posttjänster i historien.

Maila poststämpel

Microsoft designade och implementerade också en nu föråldrad öppen spec, liknande och ändå inkompatibel med Hashcash, Email Postmark, som en del av deras Coordinated Spam Reduction Initiative (CSRI). Microsofts e-poststämpelvariant av Hashcash är implementerad i Microsofts e-postinfrastrukturkomponenter Exchange, Outlook och Hotmail. Formatskillnaderna mellan Hashcash och Microsofts e-poststämpel är att poststämpeln hashar kroppen förutom mottagaren, och använder en modifierad SHA-1 som hashfunktion och använder flera delpussel för att minska bevis på arbetsvariationer.

Bloggar

Precis som e-post, blir bloggar ofta offer för att kommentera spam . Vissa bloggägare har använt hashcash-skript skrivna på JavaScript -språket för att sakta ner kommentarspammare. Vissa skript (som wp-hashcash) hävdar att de implementerar hashcash men är istället beroende av JavaScript-obfuskation för att tvinga klienten att generera en matchande nyckel; Även om detta kräver viss processorkraft, använder det inte hashcash-algoritmen eller hashcash-stämplar.

Rykte

På en digital marknadsplats kan tjänsteleverantörer använda hashcash för att bygga upp ett rykte för att locka kunder. För att bygga upp ett rykte väljer en tjänsteleverantör först en publik nyckel som sitt ID, och upptäcker sedan med brute force en nonce som, när den sammanfogas med ID:t, resulterar i en hashsammandragning med flera inledande nollor. Ju fler nollor, desto högre rykte.

Immateriella rättigheter

Hashcash är inte patenterat, och referensimplementeringen och de flesta andra implementeringar är fri programvara. Hashcash är inkluderat eller tillgängligt för många Linux-distributioner .

RSA har gjort IPR-uttalanden till IETF om klientpussel i samband med en RFC som beskrev klientpussel (inte hashcash). RFC inkluderade hashcash i titeln och refererade hashcash, men mekanismen som beskrivs i den är en interaktiv utmaning med känd lösning som är mer besläktad med klient-pussel; hashcash är icke-interaktivt och har därför ingen känd lösning. I vilket fall som helst kan RSA:s IPR-uttalande inte gälla hashcash eftersom hashcash är före (mars 1997) publiceringen av klientpussel (februari 1999) och klientpusselpatentansökan US7197639 (februari 2000).

Se även

Penny Black (forskningsprojekt)

Anteckningar

Adam Back, "Hashcash - A Denial of Service Counter-Measure", teknisk rapport, augusti 2002 (PDF) .
Ben Laurie och Richard Clayton, "'Proof-of-Work' bevisar inte att fungera", WEIS 04. (PDF) .
Dwork, C. och Naor, M. (1992) "Pricing via Processing or Combating Junk Mail", Crypto '92, s. 139–147. (PDF)

externa länkar