Hashcash
|
|
Hashcash is a proof-of-work system designed to limit email spam and denial of service attacks. It was proposed in March 1997 by Adam Back [1] (http://www.hashcash.org/papers/announce.txt).
| Contents |
How it works
A sender of non-spam email attaches a header line to his email which proves that he has invested a modest amount of computer time into solving a small puzzle, often involving the recipient's email address. The receiver can, at negligible computational cost, verify that a sender had solved the puzzle. This can be regarded as a form of numerical stamp, where the 'cash' part is the effort invested by the sender.
The theory is that spammers, whose business model relies on their ability to send large numbers of emails with very little cost per message, cannot afford this investment into each individual piece of spam they send. Receivers can verify whether a sender made such an investment and use the results to help filter email.
technical details
The header line looks something like [2] (http://hashcash.org/faq/)
X-Hashcash: 0:030626:adam@cypherspace.org:6470e06d773e05a8
Technically the system is implemented as follows:
- The recipient's computer calculates the 160 bit SHA-1 hash of the entire string "0:030626:adam@cypherspace.org:6470e06d773e05a8". This takes about 2 microseconds on a 1 Ghz machine -- far less than amount of time it took for the rest of the email to be received. If the first 19 bits are all zero, then it is valid (later versions may require more bits to be zero).
- The recipient's computer checks the date in that header "030626" (2003-06-26). If it's within 2 days of today, it's valid (to compensate for clock skew and routing time).
- The recipient's computer checks to see if the email address in that header is (any of) the valid email address(es) of the recipient (or any mailing lists to which the recipient is subscribed).
- If all the other checks are valid, the recipient's computer puts that string in a database. If that string was *not* already in the database, it is valid.
All these tests take far less time and disk space than receiving the rest of the email.
The sender "merely" needs to generate a header line that will pass all the tests. The sender's computer first generates an initial Hashcash string (the date, the email address, and a random number at the end). The sender's computer then repeatedly increments that random number and runs SHA-1, over and over again, until SHA-1 gives enough zeros. Getting the first 19 bits to be zero requires about 2^19 iterations, or about 1 second on a 1 GHz machine.
A normal person wouldn't even notice the computer taking a second to generate the Hashcash string.
Currently, spammers would prefer to spend that 1 second sending out hundreds of pieces of spam, rather than calculating Hashcash for a single piece of spam.
The time needed to compute such a hash collision is exponential with the number of zero bits. So we can keep adding zero bits (doubling the amount of time needed to send with each zero bit) until it is too expensive for spammers to generate valid header lines. (Confirming the header is valid always takes the same amount of time, no matter how many zero bits we add).
Advantages and disadvantages
The Hashcash system has the advantage over micropayment proposals applying to legitimate email that no real money is involved. Neither the sender nor recipient need pay, thus the administrative issues involved with all micropayment systems are entirely avoided. It is also fairly simple to implement in mail user agents and spam filters. No central server is needed. Hashcash can be incrementally deployed -- the extra Hashcash header is ignored when it is received by mail clients that do not understand it.
One weakness is that this method will only slow down, and not completely stop, spam sent through large collections of zombie computers, which run malware that send e-mail at the command of a spammer. These large networks have a large total computational power, which can be used to generate legitimate hashes for the spam emails they send. But the extra CPU usage will often be noticed by the owners of the machines, who will then be more likely to fix them.
References
- Adam Back, "Hashcash - A Denial of Service Counter-Measure", technical report, August 2002 (PDF) (http://www.hashcash.org/papers/hashcash.pdf).
External links
- http://hashcash.org — Hashcash homepage
- Frequently raised objections (http://camram.org/frequently-raised-objections)
- Beat spam using hashcash (http://www-106.ibm.com/developerworks/linux/library/l-hashcash.html?ca=dgr-lnxw01HashCash) — David Mertz's article on hashcash, its applications and an implementation in Python.de:Hashcash