Hashcash
Encyclopedia
Hashcash is a proof-of-work system
designed to limit email spam
and denial-of-service attack
s. It was proposed in March 1997 by Adam Back
.
of an email to prove the sender has expended a modest amount of CPU time calculating the stamp prior to sending the email. In other words, as the sender has taken a certain amount of time to generate the stamp and send the email, it is unlikely that they are a spammer. The receiver can, at negligible computational cost, verify that the stamp is valid. However, the only known way to find a header with the necessary properties is brute force
, trying random values until the answer is found; though testing an individual string is easy, if satisfactory answers are rare enough it will require a substantial number of tries to find the answer.
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.
X-Hashcash: 1:20:060408:adam@cypherspace.org::1QTjaYd7niiQA/sc:ePa
The header contains: the recipient's email address, the date, and information proving the required computation has been performed. The presence of the recipient's email address requires that a new header be computed for each recipient, and the date allows the recipient to record headers received recently and make sure the header is unique to this email.
A normal user on a desktop PC would not be significantly impacted by the processing time required to generate the Hashcash string. However, spammers would suffer a significant impact due to the high number of spam messages required.
All these tests take far less time and disk space than receiving the rest of the e-mail.
with the number of zero bits. So one 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 are required for a valid header.)
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.
On the other hand, as Hashcash requires significant computational resources to be expended on each e-mail being sent, it is impractical to use with low-end embedded systems without the help of an external server.
Hashcash 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.
Some plausible estimates come to the conclusion that you can only have one of these: Either good e-mail
will get stuck due to lack of processing power of the sender, or bad
e-mail is bound to still get through. The reasons for this are
botnet
s or cluster farms with which spammers can increase their
processing power enormously, or centralized e-mail-topologies like
mailing lists, in which some server is to send an enormous amount of
legitimate e-mails.
Most of these issues may be addressed. E.g., botnets may expire
faster because users notice the high CPU load and take
counter-measures, and mailing list servers can be registered in white
lists on the subscribers' hosts and thus be relieved from the hashcash
challenges. But they represent serious obstacles to hashcash
deployment that need to be addressed somehow.
Another projected problem is that computers continue to get faster according to Moore's law
. So the difficulty of the calculations required must be increased over time. However, developing countries can be expected to use older hardware, which means that they will find it increasingly difficult to participate in the email system. This also applies to lower-income individuals in developed countries who cannot afford the latest hardware.
implements Hashcash in the Mozilla Thunderbird
email client. The project is named for the historical availability of conventional mailing services that cost the sender just one penny; see Penny Post
for information about such mailing services in history.
s often fall victim to comment spam.
Some blog owners have used hashcash scripts written in the JavaScript
language to slow down comment spammers. Some scripts (such as wp-hashcash) claim to implement hashcash but instead depend on JavaScript obfuscation to force the client to generate a matching key; while this does require some processing power, it does not use the hashcash algorithm or hashcash stamps.
Proof-of-work system
A proof-of-work system is an economic measure to deter denial of service attacks and other service abuses such as spam on a network by requiring some work from the service requester, usually meaning processing time by a computer...
designed to limit email spam
E-mail spam
Email spam, also known as junk email or unsolicited bulk email , is a subset of spam that involves nearly identical messages sent to numerous recipients by email. Definitions of spam usually include the aspects that email is unsolicited and sent in bulk. One subset of UBE is UCE...
and denial-of-service attack
Denial-of-service attack
A denial-of-service attack or distributed denial-of-service attack is an attempt to make a computer resource unavailable to its intended users...
s. It was proposed in March 1997 by Adam Back
Adam Back
Adam Back is a British cryptographer and crypto-hacker.He is the inventor of hashcash, a proof-of-work system for protecting against email spam and other denial-of-service attacks. He wrote credlib...
.
How it works
Hashcash is a method of adding a textual stamp to the headerHeader (information technology)
In information technology, header refers to supplemental data placed at the beginning of a block of data being stored or transmitted. In data transmission, the data following the header are sometimes called the payload or body....
of an email to prove the sender has expended a modest amount of CPU time calculating the stamp prior to sending the email. In other words, as the sender has taken a certain amount of time to generate the stamp and send the email, it is unlikely that they are a spammer. The receiver can, at negligible computational cost, verify that the stamp is valid. However, the only known way to find a header with the necessary properties is brute force
Brute force attack
In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...
, trying random values until the answer is found; though testing an individual string is easy, if satisfactory answers are rare enough it will require a substantial number of tries to find the answer.
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 this:X-Hashcash: 1:20:060408:adam@cypherspace.org::1QTjaYd7niiQA/sc:ePa
The header contains: the recipient's email address, the date, and information proving the required computation has been performed. The presence of the recipient's email address requires that a new header be computed for each recipient, and the date allows the recipient to record headers received recently and make sure the header is unique to this email.
Sender's side
The sender prepares a header and adds an initial random number. It then computes the 160 bit SHA-1 hash of the header. If the first 20 bits of the hash are zeros then this is an acceptable header. If not then the sender increments the random number and tries again. Since about 1 in 220 headers will have 20 zeros as the beginning of the hash the sender will on average have to try half that many (220 / 2 = 219 = 524288) random numbers to find a valid header. Given reasonable estimates of the time needed to compute the hash, this would take about 1 second to find. At this time no more efficient method is known to find a valid header.A normal user on a desktop PC would not be significantly impacted by the processing time required to generate the Hashcash string. However, spammers would suffer a significant impact due to the high number of spam messages required.
Recipient's side
Technically the system is implemented as follows:- The recipient's computer calculates the 160 bit SHA-1 hash of the entire string "1:20:060408:adam@cypherspace.org::1QTjaYd7niiQA/sc:ePa". This takes about two microseconds on a 1 GHz machine—far shorter than the time it took for the rest of the e-mail to be received. If the first 20 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 "060408" (8 Apr 2006). 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 e-mail address in the hashcash header is (any of) the valid e-mail 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 e-mail.
Required effort
The time needed to compute such a hash collision is exponentialExponential growth
Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...
with the number of zero bits. So one 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 are required for a valid header.)
Advantages and disadvantages
The Hashcash system has the advantage over micropaymentMicropayment
A micropayment is a financial transaction involving a very small sum of money and usually one that occurs online. PayPal defines a micropayment as a transaction of less than 12 USD while Visa prefers transactions under 20 Australian dollars, and though micropayments were originally envisioned to...
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.
On the other hand, as Hashcash requires significant computational resources to be expended on each e-mail being sent, it is impractical to use with low-end embedded systems without the help of an external server.
Hashcash 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.
Some plausible estimates come to the conclusion that you can only have one of these: Either good e-mail
will get stuck due to lack of processing power of the sender, or bad
e-mail is bound to still get through. The reasons for this are
botnet
Botnet
A botnet is a collection of compromised computers connected to the Internet. Termed "bots," they are generally used for malicious purposes. When a computer becomes compromised, it becomes a part of a botnet...
s or cluster farms with which spammers can increase their
processing power enormously, or centralized e-mail-topologies like
mailing lists, in which some server is to send an enormous amount of
legitimate e-mails.
Most of these issues may be addressed. E.g., botnets may expire
faster because users notice the high CPU load and take
counter-measures, and mailing list servers can be registered in white
lists on the subscribers' hosts and thus be relieved from the hashcash
challenges. But they represent serious obstacles to hashcash
deployment that need to be addressed somehow.
Another projected problem is that computers continue to get faster according to Moore's law
Moore's Law
Moore's law describes a long-term trend in the history of computing hardware: the number of transistors that can be placed inexpensively on an integrated circuit doubles approximately every two years....
. So the difficulty of the calculations required must be increased over time. However, developing countries can be expected to use older hardware, which means that they will find it increasingly difficult to participate in the email system. This also applies to lower-income individuals in developed countries who cannot afford the latest hardware.
Email clients
The Penny Post software project on SourceForgeSourceForge
SourceForge Enterprise Edition is a collaborative revision control and software development management system. It provides a front-end to a range of software development lifecycle services and integrates with a number of free software / open source software applications .While originally itself...
implements Hashcash in the Mozilla Thunderbird
Mozilla Thunderbird
Mozilla Thunderbird is a free, open source, cross-platform e-mail and news client developed by the Mozilla Foundation. The project strategy is modeled after Mozilla Firefox, a project aimed at creating a web browser...
email client. The project is named for the historical availability of conventional mailing services that cost the sender just one penny; see Penny Post
Penny Post
The Penny Post is any one of several postal systems in which normal letters could be sent for one penny.-London Penny Post:In England, the Post Office had a monopoly on the collection and carriage of letters between post towns but there was no delivery system until the London Penny Post was...
for information about such mailing services in history.
Blogs
Like e-mail, blogBlog
A blog is a type of website or part of a website supposed to be updated with new content from time to time. Blogs are usually maintained by an individual with regular entries of commentary, descriptions of events, or other material such as graphics or video. Entries are commonly displayed in...
s often fall victim to comment spam.
Some blog owners have used hashcash scripts written in the JavaScript
JavaScript
JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....
language to slow down comment spammers. Some scripts (such as wp-hashcash) claim to implement hashcash but instead depend on JavaScript obfuscation to force the client to generate a matching key; while this does require some processing power, it does not use the hashcash algorithm or hashcash stamps.
External links
- http://hashcash.org — 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)