Subject: comments? hashcash based MTA filtering

From: Adam Back <[email-masked]>
Date: Fri, 19 Feb 1999 23:48:50 GMT

Hi,

I have a proposal for another class of filtering criteria: filtering
on the basis of a token which consumes CPU time to produce as a method
to throttle systematic abuse.

I am requesting comments from this group because it seems the closest
match of IETF topic to "technical solutions to UBE".  I am open to
comments as to how best to progress this technical solution.

I proposed "hashcash", a CPU cost function based approach to
throttling systematic abuse of unmetered internet protocols (eg UBE
over SMTP), in March 97.  Hashcash is a cpu cost function with tunable
cpu cost, based on partial hash collisions (where hash = cryptographic
message digest such as SHA1). (http://www.dcs.ex.ac.uk/~aba/hashcash/) 
The construct is quite simple and sample code is provided to tinker with.

I think it is mentioned obliquely in the UBE-solutions document at IMC
(http://www.imc.org/ube-sol.html) as I sent comment on it to the
author.

: 4.3. Filter based on previous acceptance of mail
: 
: A mail client can filter based on whether the user had previously
: accepted a message from this sender.  This happens as the recipient is
: receiving messages. If the sender is new to the recipient, the
: recipient's client somehow "challenges" the sender to prove whether
: the client should accept the message. Some of the types of suggested
: challenges include just a response, a response that takes
: computational power (computing a problem given in the challenge), and
: monetary payment.

The "response that takes computation power" is a reference to hashcash
I think.

A (20 line) description of hashcash (see
http://www.dcs.ex.ac.uk/~aba/hashcash/ for better explanation):

======================================================================
The originator is required to send with email a costly to compute
token bound to that resource name.  Example: Coyote emails Roadrunner,
he computes a hash collision on "[email-masked]".  birdseed.org
runs a MTA filter rejecting mail without hashcash postage.

The collisions are based on SHA1.  With tuning parameter t set to 16
bits, Coyote must find (by brute force) a string of form
"[email-masked]" (where X is a number), which produces
16 bits of hash collision with the hash of [email-masked].
Under unix:

% echo -n [email-masked]'  | sha1
6fc0af015d2b20b545ff44726c6d26e09397d60a

and try sequentially [email-masked] etc until a sha1
output with the last 16 bits the same is found such as (the faked):

% echo -n [email-masked]'  | sha1
af6fb545ff44c0015d2e09ffb20726c6d26fd60a
                                    ^^^^
(the last 4 hex nibbles = 16 bits are the same).
======================================================================

It needs originating support in SMTP clients, and either MTA filtering
or local filtering on the recipient side.

(You can do common sense optimisations such as exemption lists, and
non-expiring free-reply tokens etc. to allow mailing lists to not
require hashcash, and to avoid normal correspondents from needing
hashcash all the time.  And encoding the hashcash in the email
address.)

There are lots of different permutations in which one could use
hashcash.  The major problem as identified in the effects table for
the above quoted section in the UBE-sol document is that:

: Some legitimate mail might go unread if the sender does not reply to
: the challenge. All initial contact will also include challenges,
: which might make the original sender less interested in
: communicating with the recipient.

The problem is of deployment: 5% of people using hashcash is
problematic because lots of bounced mail will ensue.  95% of people
using hashcash would seriously dent a UBE originators volume, and put
pressure on the remaining 5% to convert.  Denting volume won't
_prevent_ UBE people, but it will make them think about targetting
people who are likely to be interested.  A good solution I think.

The problem is how to get from here to there.  One suggestion might be
to have a cut off point.  Jan 2003 turn it on, before that deploy it.
But how realistic is it to achieve that.  Not very probably.

Comments!

Adam

---

From: Tim Showalter <[email-masked]>
Date: 22 Feb 1999 15:46:41 -0500

> Date: Fri, 19 Feb 1999 23:48:50 GMT
> From: Adam Back <[email-masked]>

> comments as to how best to progress this technical solution.

We are not trying to solve the spam problem.  That said, I like
hashcash.  Adding a test for a hashcash value is trivial.  But getting
Sieve out there is a large amount of work in itself.

> runs a MTA filter rejecting mail without hashcash postage.

The problem with this is that it means the amount of computational power 
that a mailing list costs is rather high.

-- 
Tim Showalter <[email-masked]>

---

From: Matthew Wall <[email-masked]>
Date: Mon, 22 Feb 1999 19:07:42 -0500

--On Mon, Feb 22, 1999 3:46 PM -0500 the entity known as Tim Showalter
<[email-masked]> wrote:

>   Adding a test for a hashcash value is trivial.  But getting

To which Matthew Wall offers this response on Mon, 22 Feb 1999 19:06:17
-0500:

This would seem to me to be a trivial (and worthwhile) extension, but not
something that belongs in the base spec. 

Any other comments?

Adam, will you be at the Minneapolis IETF?

- matt

---

From: Adam Back <[email-masked]>
Date: Wed, 24 Feb 1999 16:05:50 GMT

> Sieve out there is a large amount of work in itself.

Possibly a technical anti-spam group could be formed.  One of my
reasons for posting the request for comments was to get feed back on
the question of where hashcash should be progressed.

> that a mailing list costs is rather high.

You need some kind of free-reply tokens (say by subcribing to the
mailing list using an email address of special form), or allow list of
email addresses not requiring hashcash to get around problems like
this.

Adam

---

From: Adam Back <[email-masked]>
Date: Wed, 24 Feb 1999 16:13:12 GMT

> Adam, will you be at the Minneapolis IETF?

Unfortunately not, no.  Further feed back and discussion of the merit
of forming a technical anti-spam group under IETF requested!

As started to come out in my response to Tim Showalter there is some
complexity once you start to think seriously about using hashcash:

- mailing lists

  need a way to by pass postage requirement for list software

- forwarding

  need to be able to forward messages to your other email address
  without needing to pay yourself hashcash

- possibility for ecash (with real $ value) as postage

- privacy

  need to retain privacy if ISP side allow lists are maintained

I think that technical means to deal with UBE are important because
without them we get calls for all manner of anti-UBE laws which
encourage excessive involvment and intrusion of the legal systems into
email and the internet.  In my view laws rarely make anything better.

Adam

---

From: Dave Kristol <[email-masked]>
Date: Wed, 24 Feb 1999 11:48:37 -0500

>   need a way to by pass postage requirement for list software

Unfortunately, mailing lists are hard.  You want to by-pass the postage
requirement, but only if the sender is a legitmate sender.  (And how do
you define that?)  How many lists have you been on where a spammer sent
junk to it?

Also, how do you deal with just lists of recipients (as in the Cc line
of this message?)  Do you attach coins for each recipient?

Dave Kristol

---

From: Tim Showalter <[email-masked]>
Date: 24 Feb 1999 11:49:48 -0500

So I think hashcash is an interesting idea with some technichal merit,
and I'd like to help hammer out the bugs.  I'd be happy to write or help
write a hashcash test for Sieve, although there are some bugs to work
out.

That said, if Adam is willing, perhaps we should hit up Paul for yet
another IMC mailing list.

Tim

---

From: Adam Back <[email-masked]>
Date: Wed, 24 Feb 1999 19:49:46 GMT

> another IMC mailing list.

Which ever is most productive way to go.  It depends how much work is
involved in hammering out details of hashcash, which in turn depends
on how generic it is made.

If you want to play with software, and try something with sieve, take
the hashcash implementation at http://www.dcs.ex.ac.uk/~aba/hashcash/

It includes an (inefficient) double spend database, collision
generator, and collision checker as a command line util complete with
useful exit codes.

Adam

---

From: Adam Back <[email-masked]>
Date: Wed, 24 Feb 1999 19:47:25 GMT

Dave Kristol wrote:
> Unfortunately, mailing lists are hard.  

To be clear, I meant that the list software (eg. majordomo) would be
exempt from including postage for each list subscriber that it will
forward list traffic to.

You could require postage to post to the list, where the list software
could reject posts without sufficient postage.

> You want to by-pass the postage requirement, but only if the sender
> is a legitmate sender.  (And how do you define that?)  How many
> lists have you been on where a spammer sent junk to it?

Sure it happens.  The most sensible solution I have seen for this
problem is moderation, third party filtered versions of lists, and
distributed ratings / filtering using NoCeM.  (NoCeMs can be used for
mailing lists as well as USENET news, and allow any number of people
to submit article ratings that NoCeM aware clients can use).

> of this message?)  Do you attach coins for each recipient?

Well there are at least two things that you could do:

- attach a coin for each recipient (as you suggest)

- send a combined coin (a collision computed over the concatenation of
the recipients)

The first approach could leak the identity of a Bcc if you included
the postage in all copies.

The second approach does not work so well if there are also some
Bcc's.

I think the first approach could work, if you sent the postage in the
email address using the +extension.  eg. for this message:

without hashcash:

To: [email-masked]
CC: [email-masked], [email-masked], [email-masked]

with hashcash:

To: [email-masked]
Cc: [email-masked],
	ietf-mta-filters+10646-b3f5a8831b726fef,
	[email-masked]

(The above are real 20 bit collisions, taking average 8 seconds each
to produce on AMD k6-2/300Mhz linux box.)

using the transform of X@Y -> X+date-cash@Y

The software at http://www.dcs.ex.ac.uk/~aba/hashcash/ creates
hashcash with slightly different form to those I used above.  It
produces:

% hashcash -20 [email-masked]
speed: 126758 hashes per sec
find: 20 bit partial sha1 collision
estimate: 8 seconds
expected: 1048576 tries = 2 ^ 20 tries
collision: [email-masked]
tries: 952419 0.91 x expected
time: 8 seconds

so it's hashcash is of form:

[email-masked]

because it tries to require no other state -- the string the collision
is on is included in the cash.  The alternate format I used above must
be formatted differently because the result must be a valid and
deliverable RFC822 mail address.

Adam

---

From: Tim Showalter <[email-masked]>
Date: 24 Feb 1999 15:52:29 -0500

> Date: Wed, 24 Feb 1999 19:49:46 GMT
> CC: [email-masked], [email-masked]
> 
> Tim writes:

I've sent mail out to Paul Hoffman asking for a mailing list to be created.

Tim