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.

hashcash.org is down..?

[ArghBlarg]

Funny this story should appear today.. I have been trying to find a mirror of hashcash.org for the last few days to read up on the whole idea. It's been down for a while now (or is there just some problem on my end?)

Please post mirrors.

cf Penny Black

[r]

Funny, isn't there a Microsoft Research project that did this already?

Oh yeah, so there is [microsoft.com], along with papers explaining how it works. So much for giving credit for prior work.

Won't work. Zombies will generate the stamps

[Animats]

Spammers will just offload stamp generation work onto their zombies. 0wned PCs on cable modems will burn even more CPU time.

If you want a virus built to generate stamps on zombies, just go over to Spamforum.biz [spamforum.biz] and advertise for one. New ads over there this week include "PushMail Webmailer v1.0.2 ~ New, Fast WAP Webmailer for Sale (Gets by Filters)". There's even a banner ad for a firm that wants spammers [s-rx.com]: "3 different sites - Pharma - OEM - Cigarettes".

Greylisting worked for my company

[alen]

We bought a vanilla smtp server for our gateway called Xwall. A few months ago they introduced greylisting.

Basically what it does is temporarily block suspicious emails. If it's a real SMPT server it will resend the message and the second time it will be allowed to go through. Spammers never use RFC compatible SMTP servers and simply send once in bulk and forget about it. This cut down our spam by over 90%.

Re:Right cause, wrong solution.

[Anonymous Coward]

Oddly enough, I notice when it takes more than two or three seconds. Typically that's an indication that there's a DNS problem.

Re:Right cause, wrong solution.

[gateman9]

Okay, do a little math. Spammers want to spam millions of addresses. So, even with a theoretically large network of zombies (say a thousand for one spammmer), the zombies can compute an equivalent 1000 hours of work in an hour. That's 1000 emails. The spammer would need to get his zombies to do 1000 hours of work to send a million emails. Eventually, the excessive work being doen on these zombies would get someone's attention and they would either be cut from the network or reclaimed from zombie status.

I don't know about you, but I RTFA, and once you and your friends have done a little grunt work once, you no longer need to do grunt-work.

Also, if I read correctly, the hashes may only take a few minutes per address, even on the minute scale, it is too economically expensive for spammers to send email.

More or less, spammers would need the equivalent super-computer on the scale of the Columbia installation or the Earth Simulator to effectively continue spamming.

Re:You asked for it - the spam rebuttal!!!

[Ckwop]

(x) Microsoft will not put up with it

Except that Microsoft are *ahead* of the hash cash scheme. They've developed a scheme that does the computation with something memory intensive.

Main memory is much much slower than the CPU and the difference in memory access speeds in a cell phone and a PC are much less than their CPU speed.

Memory based computations are harder to run in parrell. In principle you could have many computers working on signing a single message.

They've made is very difficult to run their algorithm in parrell. The Microsoft scheme is much better.

More information here: http://research.microsoft.com/research/sv/PennyBla ck/demo/lbdgn.pdf

Simon.

Put it this way

[Morosoph]

It can make Baysian filtering work better.

Someone with a valid stamp is less likely to be a spammer. Simply include it as a factor when calculating probabilities!

Or ignore the X-Hashcash field completely. As you choose.

If you read the article, you'd see that this was precisely the way in which SpamAssassin uses hashcash [ibm.com] : as one factor amoungst many in a general system of spam classification.

Re:The real problem here is not header forging.

[NoOneInParticular]

hmm, you're right. Didn't think of web-based email. Still, you might be able to hack something together with javascript in order to do the calculation client-side. Getting it widely implemented doesn't seem to be such a big deal, as you might be able to start with whitelisting anything that used a hash to generate the email and notify people that didn't use it that their mail was almost rejected.

That's Odd

[Greyfox]

We use Lotus Notes at work and I have no trouble E-mailing my greylisting server at home. Our mail relays happily delay the message for 6 hours and then resend it.

Re: I'll bite...

[Anonymous Coward]

Your suggestion that handlehelds, phones, etc won't be able to send mail is just a red herring. Those systems already do so via some kind of gateway. That gateway is perfectly capable of paying the postage for the underpowered device.

Now, with that said... I should point out that the real error in this system is that spammers will just build a database of known hashes.

If the postage is 20 bits, then that's only a search space of 1 million. Just precompute them all (would take less than 12 CPU-days) and you can answer any question in O(1).

Raise it to 25-bit postage, and the spammers spend 32x longer computing 32x more keys, and it'll take them 34 CPU-years to populate the database. With a cluster of 1-million zombie pcs, they'll have that cracked in less than 20 minutes! Whoops.

Raise it to 30-bit postage, and suddenly it takes 17 CPU-minutes just to send one mail. Ouch. Meanwhile, the spammers need 34800-cpu-years. But fortunately for them, their army of zombie computers will have that cracked in ~12 days. Now the spammers are the only ones who can send mail without a 17 minute delay.

Just for grins, let's consider 35-bit postage. That might actually deter spammers, since it would take them 34 years to build the database with their army of zombie PCs. But *nobody* is going to be willing to waste 9 cpu-hours to send a single mail.

My personal belief is that the only viable solution to spam is a whitelist augmented with a CAPTCHA [parc.com] challenge-response system.

Another Stupid Suggestion

[Titusdot Groan]

I've read the article and the FAQ...

Adoption will be slow. Many companies already have maxed out mail servers. Adding even an 1 second compute cycle to all outbound mail requires a fairly hefty increase in available resources, especially since most mail systems are chosen for bandwidth and IO not math processing power. What happens to a system during peak business hours when 100 people send mail with an average of 5 recipients each ... 500 seconds of computing ... ummm. Imagine a company that sends 5000 messages an hour, or 50000, or ...

If it's not at least a second on a reasonable machine than it's not going to cause ANY headaches for a spammer -- they are just text pumps they can send SO much more mail than a normal server because they don't care about logging, errors, bounces, rejects and retries.

The "use clients inside the company" idea is idiotic -- my mail server is going to punch through the DMZ directly to the desktop of my accounting staff and ask it to generate a key? I don't think so. There is a reason every company with any brains bans Seti/IM/etc. from their internal desktops.

Zombie writers will just interleave writing packets of the current message with SHA-1 calculation for the next message they are sending. Spammers have some really good programmers on their side. If you don't think of them as being at least as good as you are then you have already lost. They are already generating random text at the front and back of the payload, this isn't SHA-1 thing isn't a big deal.

Like SPF, spammers will be the FIRST people to generate proper keys. For the near future a valid key will be a STRONG indicator of spam not a "potential whitelist" feature.

Practical usage scenario

[Henry Stern]

Judging by the +3 and higher comments, it seems that nobody is thinking outside the box. There is no mutual information between an e-mail not having a hashcash stamp on it and being spam. However, if an e-mail has a valid hashcash stamp, it's probably legitimate. Thus, while hashcash can't really help your spam filter reduce false negatives (spams that it lets through), it helps reduce false positives (legitimate e-mails that are blocked).

I personally stamp all of my outgoing e-mail with 20 bits of hashcash postage. It's easy to do and requires very little CPU time. Here's how I do it:

I have stunnel listening on port 465 which forwards connections to MEsmtpd [edenhofer.de]. After authenticating the sender, MEsmtpd pipes the message to hashcash-sendmail [toehold.com] which adds 20-bit stamps for each recipient to the e-mail and passes it on to sendmail. I don't have to do anything at all in my e-mail clients. There you have it, easy as pie.

Regarding that stupid "your spam solution won't work" checklist, Spam classification is a hard problem. It can't be solved by any one approach. Even though Hashcash won't stop any spam, it can still make your spam filter more effective.

P.S. SpamAssassin supports Hashcash. See Mail::SpamAssassin::Plugin::Hashcash.

Turing Test Based email Filter

[Anonymous Coward]

Ok, how about this one:

1. Users keep contacts list on a mail server. Mail server blindly accepts incoming mail if it's in your contacts list.

2. Non-contacts email get bounced with a turing test request. Sender has to effectively authenticate themselves as intelligent enough to pass.

3. Once authenticated (for this single email), the message is delivered.

4. Recipient has the option to add new contact to the list. Otherwise subsequent emails get bounced the same way.

So, this solves bulk-spam and allows new contacts to trivially send email to people, but at the same time completely blocks bulk spam.

Thoughts?

Reactionary hyperbole

[Vainglorious Coward]

You're being silly. I dare wager that I've expended considerably more effort in administering email systems than you have. But just to be clear : I *want* to solve the problem of Unsolicited Bulk Email. *Solve*, that is, not mitigate. And re-read my post. Would you conclude from it that I don't use such tactics on my own mail servers? Or indeed a range of other measures that sure, work quite effectively today, but likely won't work tomorrow?

Another example : some spamware chokes on multi-line 220 greetings - that's a handy tip that those in the know can take advantage of, but it's not a solution to the problem of Unsolicited Bulk Email. Ditto for secondary MXs that always respond with a 451. Indeed, the irony is that the more widespread such idiosyncracies become known, the less effective the tactics become. That's the nature of the current arms race, and half-baked solutions that don't actually solve the problem just lead us in circles. Hash cash is a half-baked idea. TMDA and challenge response are half-baked ideas. SPF is partially baked at best. SenderID inhabits an alternative reality. DomainKeys shows a glimmer of potential. Internet Mail 2000 [cr.yp.to] is an example of something that I think actually attempts to *solve* the problem, but I won't deny that it's anything other than radical.

So please, for everyone's sake, don't stop showering.