Subject: Re: Why spam is a problem.

From: stanislav shalunov <[email-masked]>
Date: 14 Aug 2002 16:35:42 -0400

Melinda Shore <[email-masked]> writes:

> I think it's pretty unreasonable to put any but a trivial
> computational load on the recipient.

The scheme that I describe (I am not sure about its origins) satisfies
this condition: if the challenge string has n bits (randomly
generated), the recipient needs to do O(1) work (generate random bits
and compute MD5 of a short string once) while the sender needs to do
O(2^n) work to find a hash collision.

There are numerous other techniques that would accomplish the same goal.

> This is clearly an economic problem, but it's not just that it's
> inexpensive to send spam, it's also that ISPs make money from
> spammers and they lose revenue if they cut them off.  One problem to
> think about is how to change the balance so that hosting spammers is
> more expensive than not hosting spammers.

The scheme that I describe puts an effective throttle on how much spam
a given host can send.  Open relays keep disappearing.  The spammer
will soon have to own the machines that spew.  If this is the case,
and the heuristic algorithms are any good, the CPU on the spammer's
machines will be 100% occupied with finding hash collisions.  Thus,
sending spam becomes more expensive (you'll need large clusters to
send any significant amounts).

This needn't affect legitimate bulk mail senders: they can demand to
be whitelisted (at signup time) and refuse to do any computations.  If
I want the traffic of a mailing list, I will have to accept it without
making the distributuion machine jump over hoops.

The scheme is -- to an extent -- similar to charging a fee for reading
mail.  The currency, however, is CPU cycles rather than money.

> > P.S. If people complained more to the ISPs it would help.
> > http://www.internet2.edu/~shalunov/uce/reporting-spam.html
>
> I think so, too.  Also, when I do take the time to look at spam and
> see that it contains a freephone (1-800, etc.)  number, I always
> give them a call to let them know that I'd like to be removed from
> their mailing list.

Placing fake orders must hurt the spammers.  Unfortunately, it takes
just as much recipient's time.  (Same problem as with toll-free
numbers: it's 5 cents/minute for the spammer while your time is
probably worth as much or more.)

-- 
Stanislav Shalunov		http://www.internet2.edu/~shalunov/

"Nuclear war would really set back cable [television]."  -- Ted Turner

---

From: [email-masked]
Date: Thu, 15 Aug 2002 10:31:55 -0700

On Wed, Aug 14, 2002 at 04:35:42PM -0400, stanislav shalunov wrote:
> this condition:

search on "hashcash" on google?

--
Kent Crispin
[email-masked]

---

From: stanislav shalunov <[email-masked]>
Date: 15 Aug 2002 14:16:39 -0400

> search on "hashcash" on google?

Right.  Something along these lines, but with a challenge system that
would make double-spending moot and pre-computing useless.  If I
understand the system correctly, the hashcash system as it is now
appears to be vulnerable to attacks that involve pre-computing things
(and, e.g., shipping them on the same CD as the rest of the spammer's
kit).  Not that these are hard to address if there's a protocol
negotiation involved (and it is involved anyway).

The solution that I mention doesn't involve keeping any databases of
old tokens.  (In the case of spam, they're mostly useless as you could
use the same token with multiple servers.)  Note that it would have to
work on SMTP level rather than on the header-insertion level as
hashcash -- you *want* to have a challenge-response system.

Sex is the mathematics urge sublimated.                 -- M. C. Reed.