Subject: [Asrg] 3. Proof-of-work analysis

From: Richard Clayton <[email-masked]>
Date: Mon, 17 May 2004 23:15:46 +0100

I hope this is useful:

I'm in the Security Group of the Computer Laboratory at the University
of Cambridge. Ben Laurie (yes, that Ben Laurie) and I have recently
been doing some sums on proof-of-work / client puzzles / hashcash
methods of imposing economic constraints upon the sending of spam...

Ben wanted to know how big a proof was needed for a practical scheme
he was considering -- and I told him it wasn't going to work. We then
carefully worked through all the calculations, using the best data
that we could obtain -- and we did indeed come to the conclusion that
proof-of-work is not a viable proposal :(

The paper we wrote about this was presented last week in Minneapolis
at the (academic, peer-reviewed) "Third Annual Workshop on Economics
and Information Security" (WEAS04)

We've doubtless duplicated the figures on the back of many an
envelope, but it is clearly useful to have the analysis in the formal
literature where our assumptions and figures can be considered and
possibly even improved upon by others.

Paper:

     http://www.cl.cam.ac.uk/~rnc1/proofwork.pdf

Slides from talk:

     http://www.cl.cam.ac.uk/~rnc1/talks/040514-ProofWork.pdf

Abstract:

     A frequently proposed method of reducing unsolicited bulk email
     ("spam") is for senders to pay for each email they send. Proof-
     of-work schemes avoid charging real money by requiring senders to
     demonstrate that they have expended processing time in solving a
     cryptographic puzzle. We attempt to determine how difficult that
     puzzle should be so as to be effective in preventing spam. We
     analyse this both from an economic perspective, "how can we stop
     it being cost-effective to send spam", and from a security
     perspective, "spammers can access insecure end-user machines and
     will steal processing cycles to solve puzzles". Both analyses
     lead to similar values of puzzle difficulty. Unfortunately, real-
     world data from a large ISP shows that these difficulty levels
     would mean that significant numbers of senders of legitimate
     email would be unable to continue their current levels of
     activity. We conclude that proof-of-work will not be a solution
     to the problem of spam.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

For the avoidance of doubt, the type of scheme we believe we have
shown is not viable is one where all email (except "mailing list"
email) carries a "proof-of-work" along with it.

It may be that it is still sensible to consider composite schemes
where puzzles are only solved per sending host or where receivers use
puzzles to admit senders into whitelists...

... however, we would consider it incumbent on any proposer of such a
scheme to do similar calculations to ours before putting it forward.

     [ off-topic for here, but we also suspect that a number of proof-
     of-work schemes in peer-to-peer networks would fall to our type
     of real-world analysis :( people tend to use client puzzles as a
     kind of "magic fairy dust" to scatter over systems when they get
     stuck in their design :( ]

- -- 
richard                                              Richard Clayton

They that can give up essential liberty to obtain a little temporary
safety deserve neither liberty nor safety.         Benjamin Franklin

_______________________________________________
Asrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/asrg

---

From: Barry Shein <[email-masked]>
Date: Mon, 17 May 2004 21:27:32 -0400

I'm just idly curious (like you I have zero confidence in
proof-of-work schemes) but why wouldn't they all be equivalent to
"don't send me your next command for (at least) N seconds or I'll drop
the connection"? That'd be independent of CPU speed wouldn't it!

Or for that matter just don't respond with a 250 to their HELO for N
seconds and if they continue talking anyhow drop the connection
(something like this is in the current beta sendmail, 8.13.0beta.)

That's fairly easy to implement and how can a conformant MTA
distinguish a sneaky delay from a slow network? Most MTAs are
configured to wait a minute or two for the initial HELO anyhow.

Unless someone has a good answer this is why I've always thought these
proof-of-work/hashcash schemes were the product of dopes.

-- 
        -Barry Shein

Software Tool & Die    | [email-masked]           | http://www.TheWorld.com
Purveyors to the Trade | Voice: 617-739-0202        | Login: 617-739-WRLD
The World              | Public Access Internet     | Since 1989     *oo*

---

From: Seth Breidbart <[email-masked]>
Date: Mon, 17 May 2004 21:53:25 -0400 (EDT)

Barry Shein <[email-masked]> wrote:

> "don't send me your next command for (at least) N seconds or I'll
> drop the connection"? That'd be independent of CPU speed wouldn't
> it!

Spamware could parallel connections to umpteen million recipients and
send at full speed if all it had to do was wait.

> (something like this is in the current beta sendmail, 8.13.0beta.)

That works currently against spamware that pipelines illegally.  If it
becomes more common, that spamware will become less common.

Seth

---

From: der Mouse <[email-masked]>
Date: Tue, 18 May 2004 01:04:31 -0400 (EDT)

> drop the connection"?

No, because "wait for N seconds" is parallelizable across many
connections, whereas "do N cpu-seconds of work" isn't.

At the root of one of the problems with p-o-w schemes is that there is
no easy way to tell what constitutes N cpu-seconds of work for the SMTP
client, so instead a problem of standardized hardness is substituted
(eg, "find a data block containing this random cookie whose SHA-1 hash
begins with N zero bits")....

> seconds and if they continue talking anyhow drop the connection

Yes, that can be very effective.  (It will stay that way for a while,
too, until ratware authors implement one of the possible workarounds to
it...I'm already trying to think of workarounds and defenses against
them, against that day.)

> distinguish a sneaky delay from a slow network?

It can't.  But that's not what p-o-w schemes ask for; they ask for a
solution to a nonce problem of whatever hardness the server demands.

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML	       [email-masked]
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

---

From: Jonathan Morton <[email-masked]>
Date: Tue, 18 May 2004 10:14:40 +0100

> proof-of-work is not a viable proposal :(

That's a very interesting paper, thank you.  I wonder, however, what 
the distribution curves are like when "regular correspondents" are 
exempted from proof-of-work, not just mailing lists.  Would it be 
possible to re-examine the MTA logs for this type of pattern?

By "regular correspondents" I mean people who know each other well 
enough to send mail regularly, not necessarily frequently - even once a 
week over a period of months.  I ask this because I expect that users 
with slow machines - who would otherwise be the group most 
inconvenienced by proof-of-work schemes - send mail that mostly falls 
into this category.  I don't know, however, how much of the overall 
picture is accounted for by these.

For future work, it might be instructive to identify various non-spam 
use-cases which appear to have a high proof-of-work load - ie. on the 
"long tail" of the distribution curves presented - and consider 
practical ways of relieving or accommodating it.

--------------------------------------------------------------
from:     Jonathan "Chromatix" Morton
mail:     [email-masked]
website:  http://www.chromatix.uklinux.net/
tagline:  The key to knowledge is not to rely on people to teach you it.

---

From: "Alan DeKok" <[email-masked]>
Date: Tue, 18 May 2004 11:40:39 -0400

> connections, whereas "do N cpu-seconds of work" isn't.

  Many MTA's can limit the number of simultaneous connections from
clients, and can group the connections into pools.  Until the spam
attempts went up by another order of magnitude, I was quite successful
in limiting my MTA to ~50 connections, with ~10 reserved for the pool
of MX's that most of my traffic came from.

  In the end, it was easier to discard the domain, and move to another
one.  But that solution doesn't scale, which is why we're here.

  Alan DeKok.

---

From: Richard Clayton <[email-masked]>
Date: Tue, 18 May 2004 13:10:34 +0100

In article <[email-masked]>,
Jonathan Morton <[email-masked]> writes

>> We then

in principle yes ... however I doubt that the systems at the top of the
curve (sending lots of email per day) would have regular correspondents.
Besides the people running mailing lists, they will be e-commerce
systems sending acknowledgements, hospitals confirming appointments, fax
delivery systems relaying incoming messages etc.

However, I could not be sure of that statement without a fair amount of
processing. Since I'd like to know how much of the top of the curve
involves mailing lists, that's not processing that I'm averse to doing.

>picture is accounted for by these.

I don't see why one should expect any correlation between machine speed
and regularity of sending email. Many businesses will not splash out for
admin staff machines, so it is they as well as aged parents who might be
expected to have old kit :)

>practical ways of relieving or accommodating it.

indeed so ... though you should note that there is not much difference
between spam viability thresholds and the average case, let alone power-
users.

For proof-of-work to look plausible (and not a high-risk strategy) I'd
like to see factors of a thousand or more between plausible workloads
for legitimate senders and any economically viable spamming activity :-(

- -- 
richard                                              Richard Clayton

---

From: Jonathan Morton <[email-masked]>
Date: Wed, 19 May 2004 01:11:02 +0100

> delivery systems relaying incoming messages etc.

Let's think about the statistical significance a bit.  The Net-wide 
average is about 3 people per host, but most hosts have only one or two 
people behind them.  The discrepancy may well be made up for by a small 
number of hosts handling very large numbers of people.

As an example, Lancaster University provides a central UNIX-shell 
cluster for all students, among the services of which was the official 
e-mail system.  Because it's a UNIX shell system, the mail is sent from 
the members of the cluster, not from the terminal used to log on.  So, 
in theory, the Internet sees 10,000 students sharing three 4-way Sun 
workstations (this, at least, was what the configuration used to be).

In practice, about 60% of those students are off-campus and typically 
use third-party ISPs for personal correspondence anyway, and an 
increasingly large proportion of the remainder use personal computers 
from their rooms - but you can see the principle.

And yes, I agree that this particular use-case is fairly pessimal in 
terms of proof-of-work scenarios.  However, intra-campus communications 
are typically quite well-ordered, so (with careful management around 
the beginning of the academic year) it could still be possible to use 
the same three workstations in a proof-of-work world.

> expected to have old kit :)

I'm afraid I don't have much insight into how business e-mail patterns 
go.  That's why I'm asking you for the statistics.  :)

Point taken, anyway - chalk this one up as another use-case to be 
considered.  It could be that the business might set up it's own 
proof-of-work server cluster for internal use, rather than upgrading 
individual workstations, or else rent time as needed on a third-party's 
cluster.

FWIW, I treat mailing lists as a special case of "regular 
correspondent", and as such I don't think it's necessary to distinguish 
them per se.  You might like to consider this when compiling your 
statistics.

> between spam viability thresholds and the average case, let alone 

For the brute-force proof-of-work scheme you assume in the paper, this 
is undoubtedly true.  I'm asking for more statistics to try and reveal 
whether the ways we've thought of, for making it less brute-force, are 
viable.

> for legitimate senders and any economically viable spamming activity 

For my own usage pattern, assuming proof-of-work is exempted for 
regular correspondents, this is approximately true.  I talk almost 
exclusively to mailing lists and people I know pretty well.

Occasionally I get a question from someone I don't know, but this is 
rare enough that I could, if necessary, give up 60 seconds of my 
PowerBook's CPU time to send a reply, without too much fuss - after 
all, it would have taken me at least that long to write it.  I'd still 
be concerned about the time taken on a slower machine, though.

However, looking instead at the mail I *receive*, I can see a number of 
remote systems which could, potentially, be heavily burdened by 
proof-of-work.  However, these aren't as common as you might think.

Forum update notifications?  These come in frequently and from 
predictable sources, so I might as well whitelist them as a regular 
correspondent.  The same goes for news and status mailings from my ISP 
and various other organisations.

E-commerce transaction confirmations?  If it only costs a fractional 
cent per PoW token (because you're managing the hardware in bulk), it 
disappears next to the cost of the currency handling.  Remember, I'm 
imagining that you can centralise the effort and effectively rent space 
on someone else's cluster for this, so even small shops see the same 
kinds of low cost.  In practice, most e-commerce systems I've seen use 
a double-opt-in e-mail registration process, very similar to mailing 
lists, so similar mechanisms could apply.

As for tech support and sales enquiries, you're paying the staff 
sitting at the workstation at least national minimum wage (several 
dollars an hour), and they have a physical limit to how fast they can 
type and send mails.  The cost of attaching tokens to those mails is 
miniscule in comparison.  Whether it happens on the workstation or 
centrally is a matter of logistics - but if the workstation is already 
fast enough, the costs become essentially nil.

Registration confirmations?  Seriously, these are *supposed* to be 
rare.  I'd like to know what kind of system processes more 
registrations than actual service, before I consider this to be a 
problem.

I used to get e-cards from a few people.  These are typically sent from 
the e-card vendor's system at present - a bad practice, but oh well.  
If the cost of generating proof-of-work is too high for the e-card 
vendor, they can get the sender to download the e-card and send it 
themselves.  I'm not too worried about that.

That leaves one big category:  Web Mail.  The likes of Hotmail and 
Yahoo don't charge for sending e-mail from their systems, except 
perhaps in terms of banner ads.  They also handle ginormous amounts of 
said mail, which could make a proof-of-work switch-on relatively 
difficult for them.  However, most of their clients are low-end home 
users, who, on average, may have relatively favourable contact 
patterns.  For this, we could do with more statistics.

Any more?

---

From: Adam Back <[email-masked]>
Date: Tue, 18 May 2004 23:49:11 +0100

Here's a forward of parts of an email I sent to Richard with comments on
his and Ben's paper (sent me a pre-print off-list a couple of weeks ago):

One obvious comment is that the calculations do not take account of
the CAMRAM approach of charging for introductions only.  You mention
this in the final para of conclusions as another possible.

My presumption tho don't have hard stats to measure the effect is that
much of email is to-and-fro between existing correspondents.  So if I
were only to incur the cost of creating a stamp at time of sending to
a new recipient, I could bear a higher cost without running into
limits.

However the types of levels of cost envisaged are aesthetically
unpleasing; I'd say 15 seconds is not very noticeable 15 mins is
noticeable and 1.5 hrs is definately noticeable.

Of course your other point that we don't know how spammers will adapt
is valid.  My presumption is that spam would continue apace, the best
you could hope for would be that it is more targetted, that there are
financial incentives in place to make it worth while buying
demographics data.  (After all when you consider the cost of sending
junk paper mail is way higher, printing plus postage, and yet we still
receive plenty of that).

Also as you observe if the cost of spamming goes up, perhaps they'll
just charge more.  We don't know how elastic the demand curve is.
Profitability, success rates etc are one part of it.  There is an
interplay also: if quantity goes down, perhaps the success rate on the
remaining goes up.  Another theory is that a sizeable chunk of spam is
just a ponzi scheme: the person paying does not make money, but a lot
of dummy's keep paying for it anyway.

Another potential problem with proof-of-work on introductions only, is
that if the introduction is fully automated without recipient opt-in,
spammers could also benefit from this amortized cost.  So I would say
something like the sender sent a proof-of-work, and the recipient took
some positive action, like replying, filing otherwise than junk or
such should be the minimum to get white-listed.

On the ebiz web site problem, I think these guys present a problem for
the whole approach.  An ebiz site will want to send lots of mail to
apparent new recipients (no introductions only saving), a popular ebiz
site may need to send lots of mail.

Well it is ebiz so perhaps they just pass the cost on to the consumer
and buy some more servers.

Another possibility is the user has to opt-in by pre-white-listing
them, however the integration to achieve this is currently missing and
would seem a difficult piece of automation to retrofit.

One of the distinguishing characteristics of a spammer is the
imbalance between mail sent and mail received.  Unfortunately I do not
see a convenient way to penalize people who fall into this category.

Also because of network effect concerns my current hashcash deployment
is to use it as a way to reduce false positives, rather than directly
requiring hashcash.  Well over time this could come to the same thing,
but it gives it a gentle start, so we'll see how long it is before the
1st genuine spam with hashcash attached.

CAMRAM's approach is distinct and is literally going straight for the
objective of bouncing mail without some kind of proof (hashcash or
reverse-turing, or short term ability to reply to email
challenge-response).

Adam

Richard Clayton wrote:
> [...] Ben Laurie) and I have recently

---

From: Richard Clayton <[email-masked]>
Date: Wed, 19 May 2004 10:17:10 +0100

In article <[email-masked]>,
Jonathan Morton <[email-masked]> writes

>> however I doubt that the systems at the top of the
>average is about 3 people per host, 

in the paper we calculate this as 2.5 -- but given the nature of the
figures we are using, 3 is just about as accurate :)

>but most hosts have only one or two 
>people behind them.  

hmm... I think you're forgetting how many children use the Internet

>The discrepancy may well be made up for by a small 

perhaps

>workstations (this, at least, was what the configuration used to be).

sorry, you're not counting hosts here, but MTAs. I have no global
figures on MTA populations to hand -- and I'm not sure if anyone else
has that sort of data

looking at RIPE I see that Lancaster has 144.88.0.0/16 (as well as a /20
and some IPv6 space). You aren't allowed /16s with just 4 hosts, so
though I doubt that the 10K students are actually using 64K hosts, I
suspect that the ratio of people to hosts is somewhere near the overall
Internet average

>from their rooms - but you can see the principle.

sorry, no -- the people with their own machines would generate their own
proof-of-work. It just isn't plausible to think that a central cluster
could do that for 10K legitimate users :(

>the same three workstations in a proof-of-work world.

we disagree --- unless of course you have in mind some sort of composite
scheme where not all email carries a proof-of-work.

As I tried to make clear, we have shown that simpleminded schemes are
only marginally viable if at all -- but if you can realistically ensure
that only a small proportion of legitimate email would incur a proof-of-
work then your scheme would not fall at the first fence -- though Adam's
point about latency times in sending any email that did need a proof-of-
work calculation is one that should cause pause for thought -- that
pause being several times longer that the calculation itself :)

[big snip]

>be concerned about the time taken on a slower machine, though.

60 seconds implies that you limit people to 1440 emails per day. If you
look again at the paper you will see that at this level the spammers who
use zombies would be restricted to only about 5% of current activity (ie
the solution would perceptually be no better than filtering) or
alternatively (if you think spammers will purchase kit to do the proof-
of-work sums "legitimately") you are forcing the price of spam up to
around 0.1 cents/email -- which is not sufficient to remove a lot of
topics from our mailboxes.

To get the work factor high enough to have an impact, you need to be
thinking in terms of an hour or so :(

... or of course you need to change the landscape by reducing the zombie
population or by making the cost of spamming much higher (regulatory
fines, prison terms etc). These latter approaches are probably not on
topic here, leastwise not with the current subject line.

[another big snip]

>patterns.  For this, we could do with more statistics.

Goodman & Rounthwaite have an interesting paper on using Captchas to
limit webmail usage (one conclusion is that you need quite a number of
them). It was presented at EC'04 yesterday, but the link on Joshua's
home page is not currently working -- I expect he'll fix it when he gets
home :(

        http://research.microsoft.com/~joshuago/

- -- 
richard                                              Richard Clayton

---

From: Adam Back <[email-masked]>
Date: Wed, 19 May 2004 07:45:22 +0100

Jonathan Morton wrote:
> That leaves one big category:  Web Mail.  The likes of Hotmail and Yahoo
> don't charge for sending e-mail from their systems, except perhaps in
> terms of banner ads.  They also handle ginormous amounts of said mail,
> which could make a proof-of-work switch-on relatively difficult for
> them.  However, most of their clients are low-end home users, who, on
> average, may have relatively favourable contact patterns.  For this, we
> could do with more statistics.

There is also possibility of the senders browser computing the token.  See:

http://www.lapo.it/HashCash.html

Adam

---

From: Adam Back <[email-masked]>
Date: Wed, 19 May 2004 07:45:22 +0100

Adam

---

From: Tony Finch <[email-masked]>
Date: Wed, 19 May 2004 17:18:24 +0100

>        http://research.microsoft.com/~joshuago/

Do they address the captcha-solving porn surfers attack?
	http://catless.ncl.ac.uk/Risks/23.17.html#subj4

Tony.
-- 
f.a.n.finch  <[email-masked]>  http://dotat.at/
FITZROY: VARIABLE 3 OR LESS IN SOUTH, OTHERWISE NORTHEASTERLY 3 OR 4,
OCCASIONALLY 5. FAIR. MODERATE WITH FOG PATCHES.

---

From: Seth Breidbart <[email-masked]>
Date: Wed, 19 May 2004 12:53:03 -0400 (EDT)

Richard Clayton <[email-masked]> wrote:

> 60 seconds implies that you limit people to 1440 emails per day. If
> you look again at the paper you will see that at this level the
> spammers who use zombies would be restricted to only about 5% of
> current activity (ie the solution would perceptually be no better
> than filtering)

But it would be independent of filtering, so together they'd eliminate
99.75% of spam (assuming your statement of 95% effectiveness each).

> or alternatively (if you think spammers will purchase kit to do the
> proof- of-work sums "legitimately") you are forcing the price of
> spam up to around 0.1 cents/email -- which is not sufficient to
> remove a lot of topics from our mailboxes.

That's a several order of magnitude increase in the price of spam so
yes, I do think it would remove a lot of spam from my mailbox.

Seth

---

From: Jonathan Morton <[email-masked]>
Date: Wed, 19 May 2004 21:39:28 +0100

> http://www.lapo.it/HashCash.html

That doesn't work in my browser.  Downloading the .jar makes it work 
locally, but about 10x slower than native (on my PowerBook G4).

---

From: Barry Shein <[email-masked]>
Date: Wed, 19 May 2004 18:02:07 -0400

I'm still amazed that anyone takes this proof-of-work/hashcash stuff
seriously.

At best it's the "War Games" approach, let's make the server play
tic-tac-toe with itself to avoid nuclear holocaust, or the Bill
Shatner logical paradox that makes the robot's head blow up.

The Sphinx's riddle also comes to mind, works better for supernatural
beings however.

I realize the defense of the dumbest ideas is always that any
criticism can be represented as rudeness, ``how rude of you not to see
the brilliance of my ideas!'', so one goes on and on anyhow but I
wonder if there's any way to disabuse this nonsense once and for all,
particularly in the minds of those who think it's a good idea?

In the words of someone famous whose name I'll leave out of this: This
idea isn't right, why, it isn't even wrong!

-- 
        -Barry Shein

---

From: Jonathan Morton <[email-masked]>
Date: Wed, 19 May 2004 23:04:26 +0100

> figures on MTA populations to hand -- and I'm not sure if anyone else

On the contrary, I explicitly pointed out that the three physical 
machines involved were at least capable of running MUAs for up to 10000 
students.  The fact that the physical displays are scattered around the 
campus, and possibly the city to some extent, is irrelevant.  The fact 
that many students use alternative e-mail systems is relevant, but a 
sufficiently high proportion do still use the UNIX shell.

> suspect that the ratio of people to hosts is somewhere near the overall

Most of the address space is taken by the labs and staff office 
computers.  I purposefully left the staff (about 1000 or so) out of the 
population figure for that reason.  It might also be reasonable to 
exclude the research students, as these often have assigned computers 
as well, but they are a relatively small section of the student 
population.  FWIW, the bedroom LAN connections are behind a NAT system 
and do not contribute to the address space.

My point is that there are a few systems that genuinely handle large 
numbers of users for e-mail.  Web-mail systems and UNIX shells are 
probably the prime members of this group.  I believe some vendors are 
actively pushing "thin client" systems, which would also fall into this 
category.

> scheme where not all email carries a proof-of-work.

...which I do.  I thought I'd made that clear.

While I don't yet have a document describing exactly how it works, the 
essence is that high-value hashcash can be replaced by a low-value 
hashcash combined with a whitelisted signature.  The signature is also 
included with high-value hashcash tokens so that whitelists can be 
built easily.  The required hashcash value for return mail is indicated 
by another header.

I don't have any strong opinion on how the whitelist should be built - 
that's a matter between the recipient and their MUA.  In the case of 
Lancaster University, each student could be given a default whitelist 
upon enrolment that included various campus-wide and departmental 
mailing lists, along with relevant professors and admin staff.  Study 
groups, friends, relatives, and clubs could then be added in the normal 
way.

> Adam's point about latency times in sending any email that did need a 
> proof-of-work calculation is one that should cause pause for thought 
> -- that pause being several times longer that the calculation itself 
> :)

Right.  Sending latency is not really a problem for end-users with 
always-on connections, but it could easily be for a dial-up user, or 
for an e-commerce system.  Some proof-of-work schemes - including 
hashcash - can precompute a token from the moment the recipient list is 
known, which might overlap the time the user spends creating the 
message.

Even so, it's clear that an (on average) hour-long computation is going 
to be unacceptable - for one thing, it would drain up to half a typical 
laptop's battery.  Ten minutes is probably pushing it, too, though it's 
still possibly acceptable.  I consider 60 seconds to be the practical 
upper limit, and *that* has to fit into the midrange machines from a 
couple of years ago, which are still in common use.

> topics from our mailboxes.

Reducing the capacity of the zombie network is bound to be worthwhile.  
I would also suggest that victims are more likely to notice their 
infected machine if it has high CPU usage than if it has high network 
usage.

I would also suggest that 0.1c per mail would make for less frivolity 
than the present 0.001c per mail.  Your paper says that 0.1c/mail was 
used by spammers as a price in the past.  The pertinent question is:  
how far in the past, and what were the spamming levels like back then?

> thinking in terms of an hour or so :(

Strongly disagree.  To make an impact, the worst-case I can think of 
would demand about a minute of work on average, and I would hope we 
could work with less.

Your idea of "make an impact", however, seems to be equivalent to our 
idea of "virtually eliminate the problem single-handed".  My idea of 
"make an impact" starts from "prevent the problem from getting even 
worse than at present" and works from there.

---

From: Philip Miller <[email-masked]>
Date: Wed, 19 May 2004 18:10:01 -0400

> home page is not currently working -- I expect he'll fix it when he gets

In addition to the favorable contact patterns, webmail providers have other 
options (that are not particularly restricted to webmail providers):
1. Ask/require their customers to download a small applet that would do the 
work on the client machine (obviously doesn't work when the client is 
something like an underpowered cell phone with WAP access)
2. Tell customers that mail delivery may be delayed unless they pay for 
service while the provider does the proof-of-work as cycles are available
3. Rate-limit customers both by login ID and by client host address or other 
identifying info

If proof-of-work were implemented and demanded on a large (Internet) scale, 
I don't think webmail providers would suffer as much as they would appear to 
on the surface.

I'd also like to note that any of these methods could be used by webmail 
providers to limit spam sent through their systems regardless of any 
receiving-end demand for proof-of-work.

Philip Miller

---

From: "Jon Kyme" <[email-masked]>
Date: Wed, 19 May 2004 23:29:37 +0100

> 	http://catless.ncl.ac.uk/Risks/23.17.html#subj4

Ah, this one again :-)
I'd be very interested in any reference showing that that this "attack" has
actually been exploited.
cf. (may wrap)
http://www1.ietf.org/mail-archive/working-groups/asrg/current/msg09194.html

---

From: Mark Baugher <[email-masked]>
Date: Wed, 19 May 2004 16:38:32 -0700

>I'm still amazed that anyone takes this proof-of-work/hashcash stuff

I think it's grounded in some well-accepted DoS defence principles that are 
found in cookie protocols like Photuris and ISAKMP.

Mark

---

From: Adam Back <[email-masked]>
Date: Thu, 20 May 2004 19:20:36 +0100

Jonathan Morton wrote:
> included with high-value hashcash tokens so that whitelists can be built
> easily.  The required hashcash value for return mail is indicated by
> another header.

CAMRAM proposes to do something like this.  Their whitelists are based
on signatures.

btw I've been working on an extensible v1 hashcash format, and your
comments about hashing sigs also occurred to me in that context.  See
thread on apr 18-19 on:

	http://news.gmane.org/gmane.mail.spam.hashcash

my motivation for having hashcash of signatures was that verifying a
signature costs order of 2ms (on 3 Ghz P4) where as verifying a hashcash
takes order of 20ns O(10^5) higher cost (rough calc based on openssl
speed dsa1024 and openssl speed sha1).  So one could have eg a 12 bit
stamp (est 5ms to produce) to defend against people wasting the servers
time.  ie the server would verify the hashcash before verifying the
signature.

Of course other reasons to sign hashcash tokens, hashcash auth signature
keys etc are to facilitate the CAMRAM like logic where signatures are
introduced as whitelisting mechanisms.

> My idea of

Well I think we can make a negative-proof for just about all current
anti-spam systems.  Ie "this doesn't work in the limit and here's why
and how a spammer can work around or adapt to your anti-spam system".
blacklists, whitelists, keyword filter, bayesian filter, traded
checksums, the works.  Well that should be self-evident given the volume
of spam despite these attempts.

So I'd say hashcash is still an interesting ingredient into the mix.

> idea of "virtually eliminate the problem single-handed".  

Adam

---

From: Adam Back <[email-masked]>
Date: Thu, 20 May 2004 19:20:36 +0100

Adam

---

From: Richard Clayton <[email-masked]>
Date: Thu, 20 May 2004 23:09:53 +0100

In article <[email-masked]>, Richard Clayton
<[email-masked]> writes

>     http://www.cl.cam.ac.uk/~rnc1/proofwork.pdf

we're grateful (albeit a little embarrassed) for the consideration given
to one of our figures by Ted Wobber (MS Research) who has pointed out a
tenfold error in our sum involving an 0.0023% response rate  :-(

we'll be revising our text accordingly -- since this will weaken our
statements about the "economic argument" ... though it does _not_ affect
our analysis based on use of zombies  

- -- 
richard                                              Richard Clayton

---

From: Jonathan Morton <[email-masked]>
Date: Fri, 21 May 2004 00:40:00 +0100

>> built

I hadn't seen the v1 format before, it looks like a worthwhile 
development.  I have some comments on it, though.

Instead of separating the random and count fields, I would include the 
sender's address in the stamp as well as the recipient's.  As well as 
genuinely eliminating the collision problem, having a monolithic "salt" 
means it is easier to implement an ultra-efficient generator - just add 
one and redo the block, instead of potentially lengthening a string.

Taking the time to pseudo-implement SHA-1 for the 6502 tends to 
concentrate the mind on efficiency, and made me realise that the 
present implementation is far from efficient - especially on x86.  I 
might end up fixing your SHA-1 implementation to be more efficient - if 
so, I'll send it back-channel.

I would also strongly suggest to keep the hashcash header format simple 
and monopurpose.  Some of your later examples are no longer 
human-readable, and could even be relatively difficult to 
machine-parse.  The plain v1 format, with optional extensions, is much 
better than that.  I feel that signatures can most cleanly be added in 
separate headers, especially if they sign the hash (which prevents 
replaying the signature) rather than the hash covering the signature.

> So one could have eg a 12 bit stamp (est 5ms to produce) to defend 
> against people wasting the servers time.  ie the server would verify 
> the hashcash before verifying the signature.

The aforementioned 6502 would take about 80 seconds to produce that 
12-bit stamp.  I was thinking of more like 8 bits, which could allow 
8-bit microcontrollers (many of which can usefully run TCP stacks) to 
use a hashcash/signature system.  To be fair, I don't think many people 
receive mail from 8-bit machines, so this could be a minor issue.

Anyway, I was thinking of signing the hashcash, rather than hashing on 
the signature.  The signature is still only valid if the hashcash is, 
which actually strengthens the signature because it must be unique and 
tailored to the recipient.

---

From: Adam Back <[email-masked]>
Date: Mon, 24 May 2004 10:18:37 +0100

> tenfold error in our sum involving an 0.0023% response rate  :-(

Well that's a little better.  For hashcash.  Of course it would still be
desirable to have a factor 1000 margin of safety or similar.

> our analysis based on use of zombies  

I'm wondering about the zombie argument.  So clearly it is valid,
spammers can and do obtain zombies through viruses etc.  However it is
somewhat demanding of a threat model on any anti-spam system to say that
it should remain secure if the spammers 0wn some significant fraction of
user machines.

For example consider the following anti-spam systems and the effect of
owning the machines:

- signature based / verified sender -- broken, spammer just installs
malware on zombie which abuses the users credential

- white-list based -- broken (more limited perhaps can only reach the
set of users who have white-listed the zombie owners) spammer harvests
white-listed pairs of addresses and optionally sends from the same
zombie harvested from.  (You see this with the virus payload that sends
from random pairs from address book -- where you frequently receive
virus propagation and/or spam mail from people who's email addresses
your recognize.)

likely similar problems apply to most other anti-spam approaches if the
person you are defending against 0wns lots of machines.

Adam

---

From: "william(at)elan.net" <[email-masked]>
Date: Mon, 24 May 2004 05:27:37 -0700 (PDT)

While I agree with you that "owned" machines is a security problem due 
to the fact that it gives ability to fully impersonate that user, its also 
that fact that makes it easy to tell which machine is "owned" and likely 
embarasses user enough to clean it up quickly (rather then current zombie 
emails coming from unknown joe user on dynamic ip).

Spammers actually already started using user settings setup in outlook 
or mozilla on zombie computer to relay authenticated spam emails from 
zombie infected machines though ISP mail server, but that does not seem
to provide good results because number of emails they can send is often 
limited as ISPs would notice if thousands emails started showing up 
and authenticated emails often lead to showing up identify of zombie user 
and that leads to quicker repair or disconnection of the infected pc.

So current use of zombies is primarily based on the notion that you can 
send 10,000 - 100,000 emails from that zombie pc in only few minutes and 
then move on to another computer and primary there is ability to send very 
high number of messages through that computer and avoid that being flagged
by ISP. Additionally the fact is while number of zombies seems too high, 
if you count it as percent of total hosts it would be well less then 
0.001%. As such using ONLY zombie PCs to send emails to whitelists users 
will likely not provide any signifacant reach to spammers.

---

From: Richard Clayton <[email-masked]>
Date: Mon, 24 May 2004 13:41:06 +0100

In article <[email-masked]>, Adam Back
<[email-masked]> writes

>> it does _not_ affect our analysis based on use of zombies  
>
>spammers can and do obtain zombies through viruses etc.  

If you include insecure end-users along with the zombies, then you're
looking at a very substantial part of the current problem. I've seen
estimates of 70%

>However it is

I think it is important that we use a threat model that is a good
approximation to the Real World, not just one that a particular system
is good at countering :)

It seems quite realistic to assume that there are currently several
million machines which are 0wned by the bad guys. I can see nothing on
the horizon that suggests that end-user security is going to undergo a
major step change this decade ... so we must plan to cope with this sort
of level of problem.

Viewing these numbers as a fraction (circa one in two hundred) is not
very illuminating -- the total number is more significant. However, it
does show (because you need to deal with more than 199 in 200 people)
the sort of penetration you need for education or platform change or
whatever solution you think will effectively address the issue.

>malware on zombie which abuses the users credential

yes indeed -- and if there is money involved (paying per email, paying
for certs which then get revoked when the credential is misused) then
you end up with a million or more very unhappy people...   now you might
imagine them ganging up on their service providers (hardware, software,
connectivity) but that just means that the whole community eventually
bears the cost since it will not be coming from the insecure
individual's pockets :(

>virus propagation and/or spam mail from people who's email addresses

there seems to be an assumption that <n> spams will come from <n>
different senders and hence there must be <n> whitelist entries...

... why should the spammmers (who provide a service to many clients) not
set up <1> whitelist entry for <1> sender and still send you <n> spams

If they have many millions of sender machines you won't spot the pattern
in people requesting whitelist relationships with you :(

Of course clever designs will address this, but only, I suspect at the
cost of significant human decision-making input :(

>person you are defending against 0wns lots of machines.

so perhaps that means that spam won't have a technical solution ?  That
conclusion doesn't faze me, but clearly it upsets many technical people
who provide solutions in other spheres and would like to provide one
here :(

- -- 
richard                                              Richard Clayton

---

From: Richard Clayton <[email-masked]>
Date: Mon, 24 May 2004 13:53:08 +0100

In article <[email-masked]>,
william(at)elan.net <[email-masked]> writes

>emails coming from unknown joe user on dynamic ip).

addressing proof-of-work schemes specifically -- one must note very
carefully that if the main use of zombies becomes the performing of
calculations and not the sending of email, then it will become much
harder than today to tell which machines are 0wned -- because they will
not be creating lots of spurious email traffic

>zombie infected machines though ISP mail server, 

yes, there have been reports of this for several years, but there was a
step change in activity last September when one particular spammer
started doing this on an industrial scale....

>but that does not seem

... as the figures in the paper show, ISPs already have numerous
customers who are already sending thousands of emails a day [assuming of
course that the email passes through the ISP and does not go direct].

At present, ISPs can detect spamming activity through their smarthosts
fairly effectively (though in fact I suspect few do more than examine
the "top 50" details from their daily mail summaries); see my slides
from a relevant talk:

        http://www.cl.cam.ac.uk/~rnc1/talks/040203-Extrusion.pdf

The related academic paper is currently in "to appear" state.

>and that leads to quicker repair or disconnection of the infected pc.

yes -- though the authentication issue can be complex to repair if no-
one realises that that is the mechanism. Certainly last September it
took several iterations to get the customer properly locked down because
other things (update all the patches, fix config issues [there are
always out-of-date patches, there are always config issues]) were done
before the actual mechanism was detected

>then move on to another computer 

some spammers send considerably less and considerably more slowly. Their
mental model seems to be that this reduces their risk of detection.

Since they don't write academic papers about their tactics, it is hard
to assess or critique their analysis :(

- -- 
richard                                              Richard Clayton

---

From: "william(at)elan.net" <[email-masked]>
Date: Mon, 24 May 2004 09:43:50 -0700 (PDT)

> to assess or critique their analysis :(

Well, we can look at the some released numbers, lets just take latest article
to appear on CNET on this topic (read it yourself its good article and based 
on interviews with John Levine, Brian Martin, etc):
http://news.com.com/Attack+of+Comcast%27s+Internet+zombies/2010-1034_3-5218178.html
"Attack of Comcast's Internet zombies
 May 24, 2004, 4:00 AM PT 
 By Declan McCullagh 

Comcast's high-speed Internet subscribers have long been rumored to be an 
unusually persistent source of junk e-mail. 

Now someone from Comcast is confirming it. 'We're the biggest spammer on 
the Internet,' network engineer Sean Lutner said at a meeting of an 
antispam working group in Washington, D.C., last week. 

Lutner said Comcast users send out about 800 million messages a day, but a 
mere 100 million flow through the company's official servers. Almost all 
of the remaining 700 million represent spam erupting from so-called zombie 
computers--a breathtaking figure that adds up to six or seven spam-o-grams 
for each American family every day. 
...
Brian Martin, a computer security consultant in Denver, experienced 
Comcast zombies firsthand. Last year, a Comcast subscriber apparently 
infected by zombieware disgorged approximately 10,000 e-mail messages an 
hour to Martin's e-mail address
..."