Hashcash

Hashcash è un sistema proof-of-work usato per limitare email spam e attacchi di denial of service, e più recentemente è diventata famosa per il suo uso in bitcoin (e altre criptovalute) come parte dell'algoritmo di mining. L'hashcash è stato proposto nel marzo 1997 da Adam Back.

Come funziona

L’hashcash è un algoritmo proof-of-work (scoraggia attacchi DOS e altri abusi di servizio) che richiede una quantità selezionabile di lavoro da eseguire, dove tale dimostrazione di efficienza può essere mostrata senza alcun problema. Per un utilizzo di tale metodo tramite email, un codice testuale di un hashcash viene aggiunto all’intestazione dell’email per provare che il mittente ha occupato del tempo per utilizzare una piccola quantità di CPU, calcolando il timbro prima di inviare l’email. In altre parole, se il mittente ha utilizzato un certo lasso di tempo per generare il timbro e inviare l’email, è molto improbabile che sia uno spammer. Il destinatario può, ad un costo di calcolo trascurabile, verificare che il timbro sia valido. Comunque sia, l’unico modo conosciuto di trovare l’intestazione con le proprietà necessarie è tramite la brute force, provando dei valori casuali, fin quando la risposta non venga trovata. Tuttavia, nonostante analizzare una singola stringa sia facile, riuscire a trovare una risposta soddisfacente è altrettanto difficile, e questo implicherà un considerevole numero di tentativi per trovare la risposta.

L’ipotesi è quella che gli spammers, il cui modello di business si basa sull'abilità nel mandare un grande quantitativo di email ad un basso costo per messaggio, smettano di avere un profitto se c’è anche un piccolo costo in più per ogni spam inviata. Il destinatario può verificare se il mittente abbia fatto un tale investimento e usare i risultati per filtrare e rendere più sicure le email.

Dettagli Tecnici

La riga di intestazione assomiglia a questa:

X-Hashcash: 1:20:1303030600:adam@cypherspace.org::McMybZIhxKXu57jd:ckvi

L'intestazione contiene:

• ver: formato in versione hashcash, 1 (che sostituisce la versione 0).
• bits: numero di (zero) bit "pre-immagine" nel codice hash.
• date: l'orario in cui il messaggio è stato mandato, nel formato YYMMDD[hhmm[ss]].
• resource: stringa della risorsa dei dati che viene trasmessa, es. indirizzo IP o indirizzo email.
• ext: estensione (opzionale; ignorato nella versione 1).
• rand: stringa di caratteri casuali, codificato nel formato base-64.
• counter: contatore binario (fino a 2²⁰), codificato nel formato base-64.

L’intestazione contiene la data del messaggio, delle informazioni che provino che i calcoli richiesti siano avvenuti, e l’indirizzo email del destinatario, ed è per questo che ogni intestazione deve essere calcolata in modo diverso per ciascun ricevente. La data permette al destinatario di registrare le intestazioni ricevute recentemente e assicurarsi che quest’ultime siano uniche per il messaggio di posta elettronica.

Lato del mittente

Il mittente prepara un’intestazione e imposta un valore contatore inizializzato ad un numero casuale. Dopodiché viene calcolato l’hash dell’intestazione a 160-bit SHA-1.Se i primi 20 bits (es. le prime 5 cifre esadecimali) dell’hash sono tutte zero, allora l’intestazione è accettabile. In caso non sia così, allora il mittente incrementa il contatore e prova ancora una volta l’hash. Su 2¹⁶⁰ valori di hash, solamente 2¹⁴⁰ valori di hash soddisfano questo criterio. Quindi, la probabilità di ottenere in modo casuale un’intestazione che abbia 20 zeri all’inizio dell’hash è di 1 su 2²⁰. Il numero di tentativi che il mittente deve provare per ottenere un codice hash valido è modellato dalla distribuzione geometrica. Il mittente dovrà provare in media 2²⁰ valori per trovare un’intestazione valida. Date stime ragionevoli del tempo necessario per calcolare l’hash, questo impiegherà circa un secondo per trovare la corretta intestazione. Al giorno d’oggi, non ci sono metodi più efficaci conosciuti per trovare un’intestazione valida.

Un normale utente che utilizza un PC desktop non viene significativamente disturbato dal tempo di processo utilizzato per generare una stringa hashcash. Tuttavia, gli spammer ne risentiranno molto, considerando il grande quantitativo di messaggi spam che inviano.

Lato del destinatario

Tecnicamente il sistema è implementato con le seguenti fasi:

• Il computer del destinatario calcola l'hash di 160 bit SHA-1 dell'intera stringa. Il tempo di calcolo impiegato da una macchina di 1 GHz è di circa due microsecondi, molto meno tempo di quanto ne viene impiegato per ricevere il resto dell’email. Se i primi 20 bit non sono tutti zero, l’hash è invalido.
• Il computer del destinatario controlla la data all’interno dell’intestazione (e.g., "060409", che rappresenta il 9 Apr 2006). Se tale data non rientra nei due giorni precedenti la data corrente, allora la stringa di hash è invalida.
• Il computer del destinatario controlla se l’indirizzo email nel codice hash combacia con qualsiasi indirizzo email valido registrato del mittente, o combacia con qualsiasi mailing list a cui il mittente è iscritto.
• Il computer del destinatario aggiunge la stringa di hash all’interno di un database. Se tale stringa è già presente, allora la stringa di hash è invalida.

Se la stringa di hash passa tutti questi test, è considerata valida. Tutti questi test impiegano molto meno tempo e spazio su disco rispetto a ricevere il corpo intero dell’email.

Vantaggi e svantaggi

Il sistema degli hashcash, rispetto alle proposte di micropagamento, ha il vantaggio che nessuna somma di denaro è coinvolta. Né il mittente né il destinatario devono pagare, e quindi i problemi amministrativi coinvolti con tutti i sistemi di micropagamento sono completamente evitati.

D’altro canto, visto che gli hashcash richiedono risorse di calcolo potenzialmente significative da utilizzare per ogni email inviata, è in qualche modo difficile sintonizzare la giusta quantità di tempo medio che si desidera, con i client che impiegano tempo a calcolare un’intestazione valida. Questo può significare sacrificare l’accessibilità ai sistemi embedded di fascia bassa, oppure correre il rischio che host ostili non siano sfidati abbastanza da fornire un filtro efficace dagli spam.

L’hashcash è anche abbastanza semplice da implementare all’interno degli agenti di posta elettronica e filtri antispam. Non vi è bisogno di nessun server centrale. L’hashcash può essere implementato in modo incrementale – l’intestazione extra dell’hashcash viene ignorata quando è ricevuta dai client delle email che non riescono ad interpretarlo.

Un'analisi plausibile ha concluso che solamente uno dei seguenti casi è probabile: o le email non-spam saranno bloccate a causa della mancanza di potenza di calcolo del mittente, o gli spam riescono comunque a passare. Un esempio di entrambi i casi include, rispettivamente, una topologia di email centralizzate (mailing list), dove alcuni server devono mandare enormi quantità di email legittime, e botnets o cluster farms con il quale gli spammers possono incrementare enormemente la loro potenza di calcolo.

La maggior parte di questi problemi possono essere affrontati. Es. i botnet potrebbero svanire velocemente visto che gli utenti potrebbero accorgersi del grande carico di CPU e prendere delle contromisure, e i server delle mailing list potrebbero essere registrate in delle liste bianche negli host degli iscritti e quindi alleviare le provocazioni dell’hashcash.

Un altro problema analizzato è che, secondo la legge di Moore, i computer diventano ogni giorno più veloci. Quindi la difficoltà dei calcoli richiesti deve essere incrementata con il tempo. Comunque sia, ci si può aspettare che i paesi in via di sviluppo usino vecchi hardware, il che significa che a loro potrebbe risultare molto difficile partecipare a questo sistemai di email. Questo succede anche nei paesi più sviluppati, agli individui con un basso reddito, che non possono permettersi gli hardware più aggiornati.

Come gli hashacash, le criptovalute usano una funzione di hash, come fanno i sistemi proof-of-work. L’ascesa delle criptovalute ha creato una domanda per delle macchine di mining basate sull’ASIC (dei circuiti creati appositamente per uno scopo). Nonostante la maggior parte delle criptovalute usano la funzione di hash SHA-256, la stessa tecnologia ASIC potrebbe essere usata per creare dei risolutori di hashcash che sono tre volte più veloci di una normale CPU, riducendo l’ostacolo di calcolo per gli spammers.

Applicazioni

Bitcoin mining

Al contrario degli hashcash nelle applicazioni di posta, che si affidano al destinatario per impostare manualmente una quantità di lavoro intenzionato a scoraggiare mittenti malvagi, la rete di criptovaluta Bitcoin impiega una differente proof-of-work basata sugli hash che rende competitivo il mining di bitcoin.

Un miner di bitcoin esegue un programma nel pc che raccoglie, da dei commercianti di monete online, tutte le transazioni non confermate. Con altri dati, questi può formare un blocco e far guadagnare al miner, ma il blocco è accettato dalla rete solamente quando il miner scopre tramite un metodo di "prova e sbaglia" un numero nonce (numero arbitrario che può essere usato una sola volta) che quando viene incluso nel blocco, restituisca un hash con un sufficiente numero di zero bit che raggiunga l’obiettivo di ostacolo della rete. I blocchi accettati dai miner formano una blockchain di bitcoin, che è un registro crescente formato da tutte le transazioni di bitcoin dalla prima creazione della moneta stessa.

Mentre gli hashcash utilizzano la politica hash SHA-1 e hanno bisogno che i primi 20 bit di hash su 160 siano zero, la proof-of-work dei bitcoin utilizza altri due hash con politica SHA-256, che originariamente richiedevano che almeno i primi 32 bit di hash su 256 fossero zero. Comunque sia, la rete di bitcoin resetta periodicamente il livello di difficoltà per tenere il numero medio di creazioni di blocchi a 6 per ora.

Filtri spam

Gli hashcash sono usati come una potenziale soluzione per i falsi positivi (o “falso allarme”, ovvero un risultato che indica che una data condizione esista, nonostante non esista) con sistemi di filtro per spam automatizzati, visto che raramente i legittimi utenti saranno disturbati dall’eccesso di tempo che serve per scovare un timbro. Lo SpamAssassin è stato in grado di scovare i timbri hashcash dalla versione 2.70, assegnando un punteggio negativo (i.e. meno probabile che sia spam) valido, timbri hashcash non spesi. Comunque, sebbene il plugin degli hashcash sia teoricamente attivo per impostazione predefinita, ha comunque bisogno di essere configurato con una lista di modelli di indirizzo che devono combaciare con i campi di risorse degli hashcash, quindi, in realtà, non lavora in modo predefinito.

Client email

Su SourceForge, il progetto software Penny Post, implementa l'hashcash nel client email Mozilla Thunderbird. Il progetto prende il nome dal fatto che alcuni servizi di mail costassero al mittente solamente un penny.

Blogs

Proprio come le email, i blog sono molto spesso vittime di spam. Alcuni proprietari di blog hanno utilizzato gli script hashcash scritti in JavaScript per rallentare gli spammer. Alcuni script dichiarano di implementare l’hashcash, ma in realtà dipendono dall’offuscazione JavaScript che costringe il client a generare una chiave corrispondente; sebbene tutto ciò necessita potenza di calcolo, non vengono utilizzati algoritmi hashcash o dei timbri hashcash.

Bibliografia

• Adam Back, "Hashcash - A Denial of Service Counter-Measure", technical report, August 2002 (PDF).
• Ben Laurie and Richard Clayton, "'Proof-of-Work' Proves Not to Work", WEIS 04. (PDF).
• Dwork, C. and Naor, M. (1992) "Pricing via Processing or Combating Junk Mail", Crypto '92, pp. 139–147. (PDF)

Collegamenti esterni

• Hashcash homepage
• Beat spam using hashcash David Mertz's article on hashcash, its applications and an implementation in Python
• RSA IPR note to the IETF about hashcash (2004)