Hash Cash

km790816 writes: "I was reading an article in US News about a novel way to end spam: Hash Cash. From US News: 'our E-mail systems could be configured to reject every message from a stranger until the sender's computer had performed a difficult math problem and sent back the correct result. For one-to-one correspondence, this preliminary step would be unnoticed. But bulk E-mailings to strangers would become too costly in terms of needed computational cycles to be feasible, even with a supercomputer.'" If you've heard of Hash Cash before, don't click through, there's nothing new here. But if you haven't, here's a good introduction to the concept.

Comments

Re:It will affect the wrong people

[Stormie]

Ok, sure, there are servers out there that definitely cater to spam, and certainly something like this is going to hurt them. But the bulk of spammers today use throwaway accounts.

True, this is not a spammer-hurting technique, but rather a spam-reducing technique. Yes, most spammers use throwaway accounts. They find an open relay and hurl a million mails at it. Then the account gets deleted, but they don't care.

However: I believe that in most cases, they don't get anywhere near all of their spam out before they get the plug pulled on them. Again, they don't care. As long as they get to spew spam for a few hours for the price of a throwaway account, they're happy.

The point of this is to reduce the damage that can be done before the plug is pulled. If you can flood 100 emails down the line per second (that's just a figure I pulled out of my ass), that's 360,000 an hour until you get stopped. But if you slow it down so you can only send one a second, you've really reduced the amount of harm a spammer can do in a couple of hours to a negligible amount.

..which means that effectively, we'd need something like a bit array on the order of N^2 to store the fact the handshake has passed, N being the total number of email addresses in existence. If N starts bordering on 1 billion (we're close to that, easily), you are talking about a roughly 100,000 terabyte storage unit. Sure, this would be distributed among all mail servers, but this is highly impractical..

You've totally lost me here. Nobody stores handshakes anywhere. Currently, one SMTP server connects to another, and says "hey, I have a mail for joe_bloggs!". Under this scheme, it would connect, say "hey, I have a mail for joe_bloggs!", but then joe_bloggs' server would reply, "OK, but give me the square root of 981364293874691 before I accept the mail". Just to slow it down.

Having a spammer rape your open relay SMTP server would still leave you screwed, but at least most of the screwage would be your CPU cycles being wasted, not everyone else's bandwidth too..

It will affect the wrong people

[Masem]

Ok, sure, there are servers out there that definitely cater to spam, and certainly something like this is going to hurt them. But the bulk of spammers today use throwaway accounts. From when I read this, it suggests that they are talking about the SMTP to SMTP servers (I cannot see it operating on the user-to-user level, since it would require that the end user's computer be active and running an email client such that you can send mail to him at *any* time). So if I was a spammer, I'd simply toss my 10,000,000 addresses at the open relay STMP server; that server would talk with other servers and it would be the item boggled down with those excess calculations. And, as suggested by the article, it's not just this handshake for server to server, but it's the handshake for mailbox to mailbox, which means that effectively, we'd need something like a bit array on the order of N^2 to store the fact the handshake has passed, N being the total number of email addresses in existence. If N starts bordering on 1 billion (we're close to that, easily), you are talking about a roughly 100,000 terabyte storage unit. Sure, this would be distributed among all mail servers, but this is highly impractical.

Of course, given the terseness of US News & WR, I'm sure there are some key details missing from the article. It's a nice idea, but when you look at the habits of the worst spammers, it won't work.

Re:It will affect the wrong people

[Masem]

The way I read the article (again, USN&WR vaguity abounds), was that the *first* time a@b.com sent x@y.com an email, y.com would challenge b.com's SMTP's server with the math problem; when b.com's replies with the right answer, y.com happily accepts the message, and notes that "a@b.com" has now sent "x@y.com" a message. The next time that happens, y.com's SMTP sees that there's already been a correspondence, and therefore does not challenge it.

If you didn't store this, that meant for *every* email message sent, you'd have this hash calculation before the email can be sent. I would fear that this alone would bog down most major email providers more so than spam efforts due to the volume of legitimate email alone. So there's still a problem in implementation.

Re:It will affect the wrong people

[nlvp]

No, it doesn't say that.

I think the problem sort of implies the necessity - not all email sent to multiple recipients is Spam, and you therefore need a way to cater for people sending emails to lists of approved recipients (in the opt-in sense). To do this, they may be willing to pay the price of calculating 80,000 square roots on the basis of sending a confirmation email to each email address the day it is registered, but calculating the whole lot every time a message is sent may be seen as an excessive overhead

Don't yell at me - I say burn the fuckers, and to hell with it costing legitimate services a fortune to send me email so long as it clears my inbox of all the junk - but they're businesses, and they will, quite justifiably, be dead against it.

I also think that the handshake has to occur on the individual's computer rather than at server level.

1. Servers are overloaded as it is, and the additional processing power required to send email messages that require legitimacy confirmation would be an unacceptable capital cost to firms running the email servers
2. If it's not on the individual computer, then you have failed to push the cost of the spam back to the spammer, you've just shifted it to your ISP, which means its going to get charged right back to you and you have solved nothing.

It's a good idea, but it needs a lot of thought regarding how this should be implemented before anything gets rolled out.

Perhaps making it so that it's a service you can choose to turn on or leave off in your current email program is the first step - this has the virtue of making it your choice whether you want to make it difficult for people to send you email, and would allow the less clued-in to gradually adopt the functionality as it gets streamlined, and as more people migrate to "always-on" internet access.

Re:It will affect the wrong people

[edp]

"I also think that the handshake has to occur on the individual's computer rather than at server level.

It is not clear to me what part of the process you mean. Is it the hash cash generation you mean should occur on the individual's computer (the sending computer) or is it the hash cash verification you mean should occur on the individual's computer (the receiving computer)?

If the former, yes, the calculations should occur on the originating computer or a computer the originator pays for the use of. If the latter, no, the calculations need not occur on the actual recipient's computer. They could occur on the recipient ISP's computer, and at little cost.

Hash cash essentially involves two functions, say MINT and VERIFY. MINT is expensive to compute. VERIFY is cheap. The sender must compute MINT(x), where x is something determined by the recipient -- x could be the recipient's email address, the recipient's email address concatenated with the current time, or a value provided by the recipient upon each request. Note that the former two do not involve a handshake (after initial publication of the specification of x); there does not have to be any exchange, just a one-way transmission. Calculating MINT(x) is expensive, and this is the "hash cash" that the spender is providing.

VERIFICATION is cheap. VERIFICATION(y) returns true or false according to whether y is MINT(x) or not. VERIFICATION is very cheap, cheap enough that ISPs shouldn't mind computing it.

This scheme does not shift the cost of spam to the recipient's ISP. The spammer has to compute a great many very expensive MINT functions. The ISP only has to compute cheap VERIFICATION functions on actually received email -- and the number of email messages received will decrease since this scheme will make spam unprofitable and hence decrease it, so there can be a net saving to the ISP.

Re:It will affect the wrong people

[edp]

"The next time that happens, y.com's SMTP sees that there's already been a correspondence, and therefore does not challenge it."

No, it doesn't say that. It only suggests remembering approved mailing list senders. Although a recipient would be free to remember other senders if they wish and offer those senders postage-free receipt. And your calculation of an N^2 bit array is excessive. The N^2 function is extremely sparse. If you communicate with one new person with a 30-character email address per day for your entire life, you need less than a megabyte of memory.

But this still doesn't acknowledge the flexibility of hash cash postage, and it need not impose any burden on the relayers, except to relay the data. I don't see it spelled out on the linked-to page, but there are a variety of ways to implement this. A recipient might merely require that the sender send hash cash that is a function of the recipient's email address. The sender computes it and puts it in the email. The SMTP relays do no computation. The sender can reuse the hash cash since it is an unchanging function of destination address. Each sender has to compute the hash once -- unwieldy for spammers, easy for normal correspondents.

Another implementation could require the sender to send hash cash that is a function of the recipient's email address and the current time. (The sender would send plaintext of the actual time they used, and the recipient would require that be a reasonable approximation of the time the mail was actually sent, estimated from its receipt.) Then each sender would have to spend hash cash each time they transmitted.

Re:A more advanced scheme

[esj at harvee]

it turns out this technique has been reasonably discredited not because of any cryptographic flaws about because of the amount of power, air-conditioning, floorspace, etc. it would take to create a viable mint. Don't forget all so that you would need to replace your hardware on an ongoing basis to keep up with advances in semiconductor speeds.

---eric

Throwaway accounts...

[meldroc]

But the bulk of spammers today use throwaway accounts.

IIRC, some ISPs are trying to address the throwaway account problem by slapping spammers with a $500 cleanup fee when they terminate the account for TOS violations. I wish that more ISPs would do this - discourage spammers and make some badly needed cash.

Re:Web Mail ?

[Dust Puppy]

I assume the idea is that Yahoo or Hotmail could get the machine you use to write the email to do the calculation, via a Java applet.

Rejecting spam with a procmail accept list

[mellonhead]

http://angel.net/~nic/spam-x.html

How it works

When someone sends you mail from an address from which you've never received mail before, procmail will store their mail away without delivering it to you, and send them a message explaining that their mail hasn't been delivered yet. When they reply to that message as instructed, their original message will be delivered instead, and their address will be added to the list of addresses from which to accept mail in the future.

That's really about it - your friends and correspondents won't be inconvenienced much, and you may never get another piece of spam!

DAMN!

[CaptainZapp]

I was thinking in terms of a monthly allowance to obtain - err! smokeables...

Filter HTML

[scott1853]

How about just rejecting messages with HTML content. Even the ones sent to me from family members I could chalk up as spam. Or atleast anything containing an IMG tag.

I'm just waiting for my boss to see some of the porno spam that comes in, complete with tags.

Alternative

[ShaunC]

I like the idea. Unfortunately, it's not going to work as proposed, for reasons already pointed out earlier in the thread.

I've always thought it would be much simpler (and more effective) to implement IP volume checking at the relay level. There are very few users who generate more than 100 legitimate emails per hour. There are likely NO users who generate 1000 legitimate emails in an hour. Thus there's no reason that smtp.ignorant-admin.tw should accept 5,000 distinct RCPT TOs from 153-122-05.dialup.uu.net in an hour's time!!

Why don't the sendmail folks integrate some sort of IP filter, which prevents more than X (100, 1000, or whatever user-configurable default is reasonable) distinct messages from the same IP in an hour? If that limit gets exceeded, the admin gets alerted and the IP gets tempbanned. As best I can tell, this shouldn't cause a problem for large ISPs who are legitimately generating large email volume - they (should) know better than to be running open relays to begin with, and they'll be able to adjust their "Max incoming messages per IP per hour" setting to something they see as logical. For example, AOL would want to accept more than 1000 messages an hour from Hotmail (and vice versa) but the guy running a wide-open linux box on RoadRunner wouldn't be such relay rape potential if his copy of sendmail defaulted to blocking IPs who tried to send more than 100 mails an hour.

Granted, most of the relay rapes are due to people running outdated versions of sendmail, so adding IP filters to a future version wouldn't stop spam immediately... But if they were to implement a filter now, we could perhaps see a reduction in the "efficiency" of relay abuse in the future. If a spammer found a relay, but that relay only allowed him to send 100 separate messages in an hour, spamming wouldn't be quite so easy.

Why hasn't this been done? Am I missing something?

Shaun

Web Mail ?

[popeyethesailor]

What about webmail ? I cant ask yahoo or hotmail to do a fancy calculation before sending a mail to me can I?

Wouldn't work for me

[WickedLittleSlaveBoy]

I keep a hotmail account for everything I do on the web, so the bulk of the spam I get is from people I know. I would most likely give my spammers the easy way in and have to block them anyway, just like I do now.

doesn't really sound practical to begin with. my ISP blocked mail.com and it took me 3 days for a seller at eBay to figure out how to respond to my pay confirmation....it would seem like this, just like my ISP's "plan", punishes everyone regardless of guilt.