Beat Spam Using Hashcash

Shell writes "If they want to send spam, make them pay a price. Built on the widely available SHA-1 algorithm, hashcash is a clever system that requires a parameterizable amount of work on the part of a requester while staying "cheap" for an evaluator to check. In other words, the sender has to do real work to put something into your inbox. You can certainly use hashcash in preventing spam, but it has other applications as well, including keeping spam off of Wikis and speeding the work of distributed parallel applications." If you're specifically interested in hashcash for your mail server, Camram has some interesting ideas -- their Frequently Raised Objections page may be illuminating.

Comments

Slashdot Spam Form Response

[Anonymous Coward]

Your post advocates a

(*) technical ( ) legislative ( ) market-based ( ) vigilante

approach to fighting spam. Your idea will not work. Here is why it won't work. (One or more of the following may apply to your particular idea, and it may have other flaws which used to vary from state to state before a bad federal law was passed.)

( ) Spammers can easily use it to harvest email addresses
(*) Mailing lists and other legitimate email uses would be affected
( ) No one will be able to find the guy or collect the money
( ) It is defenseless against brute force attacks
( ) It will stop spam for two weeks and then we'll be stuck with it
(*) Users of email will not put up with it
( ) Microsoft will not put up with it
( ) The police will not put up with it
( ) Requires too much cooperation from spammers
( ) Requires immediate total cooperation from everybody at once
( ) Many email users cannot afford to lose business or alienate potential employers
( ) Spammers don't care about invalid addresses in their lists
( ) Anyone could anonymously destroy anyone else's career or business

Specifically, your plan fails to account for

( ) Laws expressly prohibiting it
( ) Lack of centrally controlling authority for email
( ) Open relays in foreign countries
( ) Ease of searching tiny alphanumeric address space of all email addresses
( ) Asshats
( ) Jurisdictional problems
( ) Unpopularity of weird new taxes
( ) Public reluctance to accept weird new forms of money
( ) Huge existing software investment in SMTP
( ) Susceptibility of protocols other than SMTP to attack
( ) Willingness of users to install OS patches received by email
(*) Armies of worm riddled broadband-connected Windows boxes
( ) Eternal arms race involved in all filtering approaches
( ) Extreme profitability of spam
( ) Joe jobs and/or identity theft
( ) Technically illiterate politicians
( ) Extreme stupidity on the part of people who do business with spammers
( ) Dishonesty on the part of spammers themselves
( ) Bandwidth costs that are unaffected by client filtering
( ) Outlook

and the following philosophical objections may also apply:

(*) Ideas similar to yours are easy to come up with, yet none have ever been shown practical
( ) Any scheme based on opt-out is unacceptable
( ) SMTP headers should not be the subject of legislation
( ) Blacklists suck
( ) Whitelists suck
( ) We should be able to talk about Viagra without being censored
( ) Countermeasures should not involve wire fraud or credit card fraud
( ) Countermeasures should not involve sabotage of public networks
( ) Countermeasures must work if phased in gradually
( ) Sending email should be free
( ) Why should we have to trust you and your servers?
( ) Incompatiblity with open source or open source licenses
( ) Feel-good measures do nothing to solve the problem
( ) Temporary/one-time email addresses are cumbersome
( ) I don't want the government reading my email
( ) Killing them that way is not slow and painful enough

Furthermore, this is what I think about you:

(*) Sorry dude, but I don't think it would work.
( ) This is a stupid idea, and you're a stupid person for suggesting it.
( ) Nice try, assh0le! I'm going to find out where you live and burn your house down!

Re: Slashdot Spam Form Response

[er_col]

Thanks for the usual Spam Form Response. I think it is remarkable that very few choices are marked on it this time around. And if you read the Frequently Raised Objections page, you may well end up with no marks left at all. So this hashcash idea does sound really interesting.

Re: Slashdot Spam Form Response

[955301]

Agreed. I went through the form as well, and found that at least one point the grandparent marked don't apply; users of email don't actually have anything to put up with. The validation is done by the mail server (or other server it's offloaded to).

But the mailing list server would have to take on additional load since they send mail to so many users.

And using zombies to do the hashing has a point as well, although the author points out that loading the zombies with additional work isn't such a bad thing after all.

Re:Slashdot Spam Form Response

[fatphil]

"""
(*) Mailing lists and other legitimate email uses would be affected

One word, one hyphen: white-listing.
"""

One word, one hyphen: header-forging

"""
(*) Users of email will not put up with it

Why? It's not costing them anything
"""

It costs them CPU cycles.

"""
(*) Armies of worm riddled broadband-connected Windows boxes

Need an order more worm riddled boxes, i.e. ONE ORDER LESS SPAM.
"""

What language is that in?

"""
(*) Ideas similar to yours are easy to come up with, yet none have ever been shown practical

None have ever been tried.
"""

If so, it's because none have been shown to be practical.

FP.

Re:Slashdot Spam Form Response

[pclminion]

One word, one hyphen: white-listing.

As a USER of email, I find the need to maintain a white-list simply because spammers are fucking assholes is UNACCEPTABLE. I won't do it. Right now, my Bayesian filters completely hide spam from me. I will not move from that system to a system which requires MORE WORK FOR ME, i.e., maintaining a whitelist.

Feel free to sit there and feel smug about your "solution" which requires you to waste your time.

I find that the people who most strongly advocate sender-side blocking, like HashCash, invariably are network administrators who don't want "their" bandwidth wasted. Guess what: I'm a customer. It's my bandwidth. I really don't give a fuck if spammers are violating the sanctity of your precious network. I am only interested in not seeing spam, not thinking about spam, and not worrying about spam. HashCash is a horrid solution in those respects, and I won't accept it.

Re:Slashdot Spam Form Response

[NoOneInParticular]

For header-forging, you need to know what mailing lists the recipient is subscribed to.
For normal use (except mailing lists), the cpu-cycles to calculate the hash are non-consequential. Modern day computers are too powerful for everyday needs anyway, who cares that it takes 20 extra seconds to send a single email, if its done in the background, no one would notice. If you need to send to 100 addresses, it takes 2000 seconds, still no big deal.
What language is that in?
Mathematical English.

If so, it's because none have been shown to be practical.

No, it's just reluctance to change. Email currently is a very open system and has been around for a long time. Any change in that system is bound to be opposed, and it takes a long time to change. The solution to spam can take three forms:

Abandon email alltogether

Evolve into a system that is robust to spammers (hash cash combined with server-side tracing of senders)

Replace it by something completely different (probably corporate, think Microsoft email)

Re: Slashdot Spam Form Response

[chainsaw1]

However, the zombies, to be effective as more than a single entity, will have to talk to each other. This adds:

-Complexity
-Time (not as much as doing it by thyself, or it would be pointless)
-Something that can be used as a unique trait to distinguish zombies from normal machines

Re:Slashdot Spam Form Response

[ewhac]

I find that the people who most strongly advocate sender-side blocking, like HashCash, invariably are network administrators who don't want "their" bandwidth wasted. Guess what: I'm a customer. It's my bandwidth. I really don't give a fuck if spammers are violating the sanctity of your precious network. [ ... ]

That's nice as far as it goes, but I think you may be failing to consider what happens behind that Bayesian filter hiding all the spam from you. Your bandwidth is being consumed by spammers; you just can't see it right now.

Unless something is done at the head end to choke spam off at the source, you may one day wake up to discover that half your bandwidth is being consumed with spam, which is dilligently and silently being thrown away by your email client with the Bayesian Filter Ultra-Deluxe.

Schwab

Re:Slashdot Spam Form Response

[nahdude812]

Mailing lists exist for several reasons that online forums don't directly address (in no particular order).

* Messages come to you rather than you having to go to them (server push rather than client get, and depending on the list, this can mean basically real-time receipt).
* Easy offline access to the messages
* Not subject to network restrictions in almost any company
* Can be delivered directly to portable devices (eg, Blackberry)
* Can be alerted based on criteria (alert me whenever I see Critical Flaw in a Microsoft-based message on bugtraq, as an example)
* Can automatically sort based on criteria (message rules)
* Ability to maintain your own archive of messages you deem important
* Ability to easily forward messages to others who are not on the list
* Fewer complete chowder-heads exist on mailing lists as they're a bit more techy in general (how much work did Slashdot put into their moderation system to battle trolls?)

All of this exists with out any need for additional technology. Yes, all of it could be accomodated in one way or another with new features on forums etc, but the fact is, the purposes that mailing lists serve is wholly served by them currently.

There's no reason to reinvent the wheel with a device 10x as complex that rolls 2% better.

Re:Slashdot Spam Form Response

[Srass]

Unless you run your own mail server, yes, you would. Just not directly. 1000 times worse means increased transport costs for your provider, and increased costs in maintaining servers that can handle the influx of mail.

Just because you can't see it personally, doesn't mean it isn't affecting you behind the scenes. It is.

Most large ISPs have to maintain a full-time staff dedicated just to handling abuse issues like these. Who do you think is paying their salary?

This doesn't *stop* anything

[hansendc]

Today, spammers buy and sell large lists of email addresses on CDs or other media. Each of these addressess took some mining to find it, and put it on the CD.

In the future (if this takes off), these lists will simply contain the hashes along with the addresses. This temporarily makes the spammers lives a bit difficult, but doesn't have a long term impact.

Spammers share information. The cost of all those hashes amortized over a few years to a large number of spammers is nothing.

Re:This doesn't *stop* anything

[Raul654]

Easily countered - then you simply change the hash question on a per email basis. So I ask potential email A a question about FOO and potential emailer B a question about OOF. There's no way to know in advance what I am going to ask. That way, the only way to email me is to actually compute the answer.

Re:Work for it?

[Anonymous Coward]

There are plenty of available solutions, however they're all designed/implemented/pushed by large companies - viva la open source.

Right cause, wrong solution.

[Anonymous Coward]

The end effect of this is eventually bad, or utterly worthless.

Joe Sixpack wants to send a mail. If it takes him an hour to parse a key, he's not going to mail his mother anymore.

If a spammer has to spend an hour processing the key, he's just going to invest more of his time getting zombie PCs to get the work done for him.

Who wins here? Certainly no one.

Disclaimer: the hour was used as an example. I've no clue how long it takes, but the point should still hold.

The moral being, don't make the end users pay for the actions of spammers. We have laws for spammers now; it's time to start using them.

Re:Right cause, wrong solution.

[Ninja Programmer]

• The general idea is that it will take a relatively small yet significant time to compute. So for example (also random) 30 seconds. Joe Sixpack will not notice 30 second delay on his computer for one email.

Yes he will. Because that 30 seconds of 100% CPU utilization. To make sure its not annoying to mail senders, its got to be something really short like 3 seconds or something (that would be my personal threshold). But then there's the question of whether or not its enough of a burden on spammers.

Stupid idea

[pclminion]

This makes it difficult to send any kind of mass mail.

For example, Sourceforge sends site-wide update messages about once a month or so. They have tens, if not hundreds of thousands of users. If every one of those users used HashCash, Sourceforge would practically need a dedicated server farm computing hashes simply in order to send out its update notices.

This is a really, really stupid idea.

Re:Stupid idea

[chuckgrosvenor]

Not really. If you want the mass email, you can whitelist it so they don't need to computer a hash for you.

Re:Stupid idea

[fatphil]

And then every spammer forges its source to be sourceforge.

Shit, pun not intended.

FP.

Re:Stupid idea

[Anonymous Coward]

I think we just need to accept the fact that mailing lists need to be whitelisted. There is never going to be a simple way of letting "good" SPAM in while blocking "bad" SPAM at the same time. Half the SPAM I get is from mailing lists like Best Buy's. How can I block it at my companies spam filter if 1/3 of the people here actually want the mail?

Blah. Whitelist it if you want it.

Re:Stupid idea

[mypalmike]

So every time I subscribe to a mailing list, I've got to go through some convoluted process of receiving a magic email and then adding the sender to the whitelist.

Don't you already get "magic emails" and go through a convoluted process for most mailing lists to confirm that you want to be on the list?

OK for you and me, but if Microsoft implement this they will just automate the process so you only have to click "ok" on a popup.

POPUP: "Do you wish to receive mail from the sender 'V|4GRA-= CIA7IS =CHEAP'? [Yes] [No]"

So Joe Sixpack will click "ok" when he gets his first spam, and the spammer will be on his whitelist.

If Joe Sixpack makes the mistake of accepting it, he can later simply remove it from his whitelist when he notices. A well-designed UI will make it so that he doesn't even realize he has this "whitelist".

-_-_-

Won't Stop Virus/Worm'd Zombie spamming

[Anonymous Coward]

An awful lot of spam has been generated from machines infected by worms. If the spammer controls a thousand zombie machines, he'll have all the CPU power he needs...

Re:Won't Stop Virus/Worm'd Zombie spamming

[gateman9]

You've never done distributed computing work, have you?

On average, the 1000 zombies will have an average CPU equivalent to a P4. Add to that network latency and all the work that has to go into coordination, and the equivalent CPU power goes down.

So if a spammer had 1000 zombies, he'd get at best a 1000 hours of work in 1 hour, and on average maybe a 100. To send a million emails, even under the best conditions and using the two or three second hash-compute time, he would need approximately 555-833 hours.

Waste of perfectly good CPU time

[iamacat]

Sort of like burning your harvest to keep grain prices high. Just send me a completed work unit of Seti-At-Home or Folding-At-Home in an email header. I am sure, given the incentive of every e-mail message advancing their goal, some of these projects can come up with work units that are difficult to calculate but easy to verify.

Maybe for once zombied Windows boxes will be more productive than they would be under their users' control.

Solution also ignores...

[Croaker]

the fact that not everyone is sending legitimate email with a powerful computing device. Something that could cause an inconvenience to a spammer with a boatload of cheap commodity 2Ghz desktop systems (other their own or a zombie army) will bring more modest systems to their knees. Handhelds, phones, old 486 systems recycled for use in the 3rd world, set top boxes, embedded systems, etc. will no longer be viable systems with which to send mail. And what about web mail providers?

These's simply no reason to resort to kludge solutions that depend on penalizing those who cannot afford top-of-the-line systems.

greylisting is better

[hackstraw]

To me greylisting seems like the best thing to do. See:

http://slett.net/spam-filtering-for-mx/greylisting .html

and/or:

http://projects.puremagic.com/greylisting/

In a nutshell, it simply uses a standard 451 SMTP response that says "Hey, I'm busy now, can you call back in a minute or so?" To my knowledge, all standard SMTP servers respect this request, and little to none of the mass mailers do. And if they do, their bandwidth will triple.

Here's a log example:

Oct 15 15:18:17 example1.example.com sendmail[6955]: [ID 801593 mail.info] i9FJIGH06953: to=, ctladdr= (168/601), delay=00:00:01, xdelay=00:00:01, mailer=esmtp, pri=121994, relay=example2.example.com. [123.390.141.456], dsn=4.3.0, stat=Deferred: 451 4.7.1 Greylisting in action, please come back in 00:01:00

If the mail never comes back, then the sender is now blacklisted. If the mail does come back, the sender is whitelisted.

Simplest and most standards compliant thing that I've heard of, and it seems to work.

Re:greylisting is better

[Em Ellel]

If the mail never comes back, then the sender is now blacklisted. If the mail does come back, the sender is whitelisted. ..so this will work until spammers add a retry to the mailers - at which time they are whitelisted.

-Em

Re:cf Penny Black

[PugMajere]

Hashcash predates the MS Research project.

This article is about the first correct (supposedly) Python implementation of hashcash.

Hashcash is a whitelisting protocol

[Morosoph]

If you add Sourceforge, specifically, to your whitelist, the problem goes away.

Only unsolicited mail needs a hashcash field.

It's a temporary bandaid, not a solution

[Vainglorious Coward]

Spammers never use RFC compatible SMTP servers

And spammer tactics remain static, so the same techniques that worked five hours or five years ago will continue to work indefinitely. Not.

The real problem here is not header forging.

[mellon]

It's that in order for this to be useful, it has to be widely implemented. Anybody who sends a lot of legitimate email (e.g., hotmail) is going to need to buy a lot more CPU. So it's not going to get widely implemented. So it won't help. Sorry. :'(

Okay, some thoughts on the FAO...

[pla]

From the "objections list":

How do you deal with large-scale legitimate mail sources (i.e. mailing lists, mail houses, etc.)?

I consider mailing lists a cute throwback to a much earlier time. Don't get me wrong, I subscribe to three or four myself. But every single one of them, I could just read on-line (and no, not all Yahoo lists, only one in fact).

To effectively eliminate spam, I would gladly visit a web page rather than have the same info appear in my mailbox.

The second issue is that mailing houses that deliver bulk e-mail for legitimate commercial ventures will need to generate stamps for some of their traffic.

Er... How does that differ from actual spam? I don't give two shakes of a rat's ass whether or not UCE comes from a "legitimate" source. I don't want it. Any of it. So, it really doesn't bother me that, for the benefit of no more "Free v1@6ra" email, I also lose out on "buy our totally legit ink cartridges" at the same time. I consider it a perk, not a problem.

acceptance

[krokodil]

The problem with technologies like this is that they need to gather widespread acceptance to become useful.

Quick grep on my mail archive (which is HUGE) failed to find single message with X-HashCash header. That means even if I would enable it now, it will be practically useless.

Of course wide acceptance could be achieved by the means of widespread grassroots campaign, but this is hard way. If somebody big like GMail, Yahoo Mail or MS Outlook or Apple Mail started to use it , that would have snowball effect.

And further

[Anonymous Coward]

Why not have it compute the stamp before you send the mail? You start a new mail window, that least intensive of applications. In the background it calculates the stamp while you type.

Under that system, you could make the stamps as much as a minute. Very few e-mails are written in less than twenty seconds, most take a few minutes. Really short messages go via IM. You still queue it to go after the stamp is ready to deal with the short e-mails, of course.

Re:Wiki Solution with Javascript

[PowerKe]

Just add some javascript that would hash the message, some part of the URL or page, or a salt and that would be a required part of sending.

Unfortunately this means that each installation would need its own javascript function. Otherwise you just take a look at the wiki package, see what sort of computations it does, write a program to perform the same computation in C, do a google search for the wiki engine and compute 1000 hashes in the same time the javascript has calculated one.