Status: Just a cool idea. (See disclaimer at end.)
Here's another approach to ending the problem of spam. In phase one, where it's only adopted by a few people, it just provides a solution to the growing problem of false-positives in spam filters, where important mail goes unseen because it was misfiled as spam. In phase two, when implementations are widely available and many people are using it for phase-one benefits, people can begin to reject all non-compliant mail, forcing everyone else to adopt the protocol. Once this has happened, sending unsolicited bulk email will be prohibitively expensive, and the problem of spam will be gone. (A slight open question remains: how much would spammers really be willing to spend per message? How can we know?)
This proposal uses a computational challenge to make spam uneconomical. This is an old idea. The most prominant current proposal is HashCash (perhaps in concert with CAMRAM), discussed below. This proposal should not be taken as an attack on HashCash; rather it comes at the problem from a slightly different angle and may raise some design issues for people trying to thoroughly explore the design space. In particular, people concerned with HashCash's mailing-list race condition might compare the mailing list behavior provided here.
Spam is a problem because a single message transport agent (MTA) can send email to many thousands of users each day. If we could bring the number down from the thousands into the tens, spam would cease to be a signficant burden. We can do this by requiring MTAs to become "acquainted" with each destination address and making the process of becoming acquainted require the sender to perform a task which consumes several minutes of CPU time. But acquaintance can be stored, and even conferred in advance, so that most normal mail transactions have little additional burden.
The exact difficulty of the task can be set by each recipient to reflect a personal decision about how strongly to prevent contact by unknown senders. The bulk nature of spam puts the burden disproportionally on the spammers (where it belongs), so the exact value of this setting is likely to be of little importance. A long-lost friend sending e-mail probably would not even mind his computer working for an hour in the background while sending you e-mail. For a spammer, even a few seconds of computation could be the difference which drives him out of business.
This proposal involves extending SMTP so that the receiver can ask the sender to do some computation before proceeding. There are many SMTP extensions; each on is supposed to be document in an RFC. See D. J. Bernstein's EHLO page for more details.
Mail delivery normally looks like this in SMTP. (The >>> lines are the ones from the sender, the ones starting with a number are the receiver's output. This is "mail -v" output.)
Connecting to w3.org. via esmtp... 220 dr-nick.w3.org ESMTP Postfix (Debian/GNU) >>> EHLO sarlacc.w3.org 250-dr-nick.w3.org 250-PIPELINING 250-SIZE 10240000 250-VRFY 250-ETRN 250-XVERP 250 8BITMIME >>> MAIL From:<root@sarlacc.w3.org> SIZE=33 250 Ok >>> RCPT To:<sandro@w3.org> 250 Ok >>> DATA 354 End data with <CR><LF>.<CR><LF> >>> . 250 Ok: queued as 8839C135CDThe lines like "250-PIPELINING" announce server extensions. This proposal is for an extension BEWILLINGTOWORK. Clients (senders) who understand this extension will, after issuing the "RCPT To" line, say "WILLINGTOWORK", like this:
Connecting to w3.org. via esmtp... 220 dr-nick.w3.org ESMTP Postfix (Debian/GNU) >>> EHLO sarlacc.w3.org 250-dr-nick.w3.org 250-BEWILLINGTOWORK 250-PIPELINING 250-SIZE 10240000 250-VRFY 250-ETRN 250-XVERP 250 8BITMIME >>> MAIL From:<root@sarlacc.w3.org> SIZE=33 250 Ok >>> RCPT To:<sandro@w3.org> 250 Ok (now please offer to do some work) >>> WILLINGTOWORK aes-128-sum 250-PLEASEDO aes-128-sum 6b4ac1ecb2cb718a2feabf6fe6e0506dfd1200000/114 5eb46c2a81067c1c439972e49fe918baadaa38d9da39a3ee5e6b4b0d3255bfef95601890afd80709 >>> DIDWORK 6b4ac1ecb2cb718a2feabf6fe6e0506dfd124fac49 250 Ok (great work, go ahead and send data) >>> DATA
The actual computation here, referred to as aes-128-sum is this: given a partial AES key (here the leading 114 bits are given as true) and some ciphertext (n*64 bits, n=4 here), find the full key such that the 64-bit-signed-integer checksum of plaintext comes out to zero.
This computation is proposed here as a strawman, but shows the essential quality: that spammers not have access to significantly faster ways to solve this problem than everyone else. There is already a great deal of public research about fast AES implementations, and its unlikely a radical improvement will occur.
The speed of factoring algorithms, on the other hand, is being effectively improved by research, so if a factoring problem were used, people using the latest research software might have a 100-fold faster algorithm than people running generic slightly-out-dated code.
Systems like mail.w3.org need to send a lot e-mail. The main trick to making this work is to say that the task posed to a sender should be stable with respect to the sender's IP address. This allows the sender to solve the problem once, then save the answer, knowing it will be asked the same problem (and can give the same answer) next time.
If either side forget the task, or the IP address changes, they just fall back to using a new task.
A second trick, to save even more work on mailing list hubs, is that MTAs should offer the task and its solution when they are transmitting mail from an address for which they might receive mail.
When I send email (perhaps to new-list-subscribe@w3.org) from sandro@hawke.org, it should look like this:
... 250-WILLREMEMBERSOLUTIONS ... >>> SOLUTION FOR: sandro@hawke.org aes-128-sum 6b4ac1ecb2cb718a2feabf6fe6e0506dfd124fac49 250 ok (thanks! I'll remember that in case I need to send to him) ... >>> RCPT FROM: sandro@hawke.org 250 ok >>> MAIL TO: new-list-subscribe@w3.org ...
This only helps if mail is symmetrically routed, but it still seems like a good idea. If it fails, we fall back gracefully to having to do the computation.
If an acquaintence is compromised it may start to send annoying stuff faster than you would like. Recieving MTAs should provide way for users to (in addition to turning the barrier-to-acquaintance knob [with perhaps a per-IP-addr exception]) mark particular acquaintances as suspect (that is, to change the problem they are using on that IP address), so they are forced to re-acquaint themselves. If w3.org got compromised, it would be slowed down arbitrarily when it started to send out spam.
None yet!
Needs new code in every MTA. shouldn't be that much code, though. Probably put it into postfix first, then try to get maintainers of other code to follow. Or put it into a custom python MTA for experimentation.
Also needs code in spam filters so they know to let the mail from acqauintances through unmolested.
Don't refuse e-mail from MTAs who wont work; just set a header which users can use to direct it into another mailbox.
Decide when you want to move to phase 2. Wait until all the "cool people" (oponion leaders) are listed as acquaintences
Tell the MTA to reject mail with a message like this:
"Your mail was rejected because your mail software does not support the WillingToWork extension, which we use to block spam. Sorry. For a list of open source and commercial software which does support this protocol, please visit: ....."Let's say running a computer on the network costs $100/month. True rock bottom $500 hardware every two years, 100 watt total power usage, and miraculously free network connection comes out to $25 per month, but the rock-bottom co-location facilities charge $100-$200 per month to put something on their network, with or without supplying a machine.
Faster machines cost a lot more and have CPUs which are not much faster. The cheapo $500 system is perhaps an Athlon 2200. Is there anything twice as fast that isn't ten times as much money?
So CPU on a very cheap sending MTA is worth about $100/(24*30), or 14 cents per hour. Pretty cheap.
So if give them a problem that takes an Althon 2200 about four minutes to solve, we are requiring them spend one cent per e-mail.
Ostensibly legitimate bulk e-mailers ("100% spam free, Opt-In") who advertize on google range in price from 0.08 cents per message down to 0.00004 cents per message. So even the most expensive service will need to raise prices more than 12-fold just to cover the CPU cost from a 4-minute acquaintance task. The cheaper services would need to raise rates by a factor of 25,000.
Alternatives like paying people to send spam from their home computers (almost certainly in violation of their agreements with their ISPs) don't look much better. The four minute problem still limits them to 360 messages per day or 10,000 per month. For the 0.08 cent per message company to only double its rates, it would have to pay these folks no more than $8 per month for using 100% of their CPU.
Both systems use the idea (dating from at least [Dwork and Naor, 1992. Postscript]) of forcing senders to perform computation to demonstrate they are not sending cheap bulk e-mail. The essential difference is in whether the protocol operates at the interactive transport (MTA) level or the non-interactive user-agent (MUA) level. HashCash operates at the MUA level, where this acquaintance protocol operates between MTAs.
It may turn out to be easier to upgrade MTAs than MUAs, since edges of the e-mail universe which are hardest to upgrade are likely to be running only MUAs.
An important question for both systems is what happens when the reciever's price setting is off. If it's too low, they'll get spam. If it's too high, non-spam will be turned away. In the MTA protocol, this "turning away" is immediately known on the sender's machine; it occurs when the receiver presents a problem that is too hard and the sender is alerted. With an MUA based approach, it's important that rejection e-mail be sent to the sender who has used HashCash, but just not enough. The end effect should appear similar to users.
Perhaps that biggest difference in effect is that with HashCash the sender's machine will need to perform many calculations which would not be needed by the MTA Acquainance Protocol, since it needs to solve a new problem with every e-mail, not just when meeting a "stranger".
This extra workload with HashCash may mean the price cannot be set high enough to dissuade spammers. The HashCash site talks about a few seconds work being enough to deter spammers (suggesting they need to send 10K+ spams per minute to stay in business). Let's call that 5 seconds on our $100-per-month machine, or 0.02 cents per e-mail. What if that's not enough? The most expensive bulk mailer running Google ads, Spam Alternative charges $39 per 50,000 messages, or 0.08 cents per message. The HashCash 0.02 cents per e-mail would not dissuade them. But how much higher can HashCash go before legitimate e-mailers start to complain that e-mail is really too slow?
This work is being done on my own time, with no comment yet from W3C management. :-) This work is most certainly not on the W3C recommendation track and not the product of a W3C working group or interest group.
Sandro Hawke
First: Sun Oct 12 2003
This: 2003/10/21 18:40:07 $