Subject: [Asrg] New proposal for spam blocking: Greylisting

From: Evan Harris <[email-masked]>
Date: Fri, 20 Jun 2003 10:29:15 -0500 (CDT)

Over the past few months, I've been working on a new method of blocking spam
that I've termed "Greylisting".  From my testing it appears to be over 97%
effective.

It requires no changes to the infrastructure, is resistant to spammer
adaptation, and is very effective, yet very lightweight.

The paper outlining the method is at
http://projects.puremagic.com/greylisting/ and I have also posted an example
implementation for a Sendmail Milter written in perl.

Please look it over and try to poke holes in it, but I've worked pretty hard
to make it as bulletproof as possible.

Evan

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

---

From: Vernon Schryver <[email-masked]>
Date: Fri, 20 Jun 2003 10:01:55 -0600 (MDT)

> From: Evan Harris <[email-masked]>

> ...
> ...

To deal with sharing the database among servers, have you considered
any of the obvious tactics?  I'm thinking of such as NFS (with NFS
clients and servers that do proper locking) or an inter-system protocol
for sharing the triples and their timestamps?

"Dictionary attack" is a more common term for what you call "trolling."

The biggest problem I see with the tactic is "scaling."  It's the same
as the biggest problem with spam, which can be phrased as "What if
everyone does it?"  Contemplate the effects on very large mail servers.

A smaller but still significant problem is that the mechanism addresses
only the current spam problem that involves literal crimes.  The big
corporate spammers run proper SMTP clients that retransmit.  This
tactic will only increase their extremely low per-target costs by a
little bit.

Still, it appears to be a worthy tool.  Running code and technical
details count outmatch any amount of enthusiastic sales talk, bluster,
and arm waving.

Vernon Schryver    [email-masked]

---

From: "Jon Kyme" <[email-masked]>
Date: Fri, 20 Jun 2003 17:12:48 +0100

> to make it as bulletproof as possible.

You mention Exim and sender callback verification, it's probably
worth pointing out that this isn't default behaviour and the Exim docs
suggest that:
"This facility should be used with care, because it adds a lot of resource
usage to the cost of verifying an address."
Exim also provides a "callout_defer_ok" options to allow success in the
face of a temporary failure.

Whatever... any spam that *is* retried after the "block" is aged gets
through. Or have I got that wrong?

--

---

From: Yakov Shafranovich <[email-masked]>
Date: Fri, 20 Jun 2003 12:16:42 -0400

At 05:12 PM 6/20/2003 +0100, Jon Kyme wrote:

>[..]

Lets say a spammers has gained control over a specific IP address for an X 
amount of time. He normally sends out 1M messages via that IP. So now to 
get around this block, he will send out 2M messages retrying delivery. This 
increases his costs slightly but not to the point where it becomes 
unprofitable. The reason why spammers have not tried this approach yet 
become this blocking method has not been widespread.

Yakov

---

From: Evan Harris <[email-masked]>
Date: Fri, 20 Jun 2003 11:18:13 -0500 (CDT)

> for sharing the triples and their timestamps?

Depends on the database implementation, but since I used mysql, sharing is
as easy as opening another connection to the db.  No need for nfs or file
locking or all of that.

> everyone does it?"  Contemplate the effects on very large mail servers.

Well, keep in mind that the longer you run the system, the more
"relationships" that are observed and whitelisted.  The majority of the
impact is in the first few days of running the system.  After that, I should
think it would scale very well.

There are other ways of avoiding it also.  Change the code so that you don't
block any emails but do record the triplets.  After running the system for a
couple weeks, then add in the delays.  Most of the legit relationships will
already have been learned without any blocking.  The drawback is spammers
will have been learned too, but this is an easy way to minimize the new
system impact.

> tactic will only increase their extremely low per-target costs by a

The semi-legit spammers are better handled through dns blacklists and other
methods.  I'm not too concerned with spam from these sources, since those
can be (and probably will be soon) resolved with legislation.

My concern is for the fly-by-night spammer that forges headers, and this
should work pretty well for them.

> details count outmatch any amount of enthusiastic sales talk, bluster,

Thanks.  I've been very happy with the results, as have the users on my test
systems.

Evan

---

From: Evan Harris <[email-masked]>
Date: Fri, 20 Jun 2003 11:21:30 -0500 (CDT)

> face of a temporary failure.

Well, all I know is that sourceforge bit me with this, which is why I made
that modification.  Since my main target for using this is techie types, not
good to have problems with sourceforge.  :)

> through. Or have I got that wrong?

Yes, unless it is blocked by other means, like dns blacklists or normal
spam catching methods.

But letting the block age requires spammers stick to an IP address, which
makes the dns blacklists work better.  Still results in farily good success.

Evan

---

From: John Morris <[email-masked]>
Date: Fri, 20 Jun 2003 12:47:15 -0400

At 11:18 AM -0500 6/20/03, Evan Harris wrote:

>"relationships" that are observed and whitelisted.

As with any whitelist, there are potential privacy concerns, but 
these concerns would be greater here because of the additional data 
tracked in the database.  Of greatest concern would be:

    relay_ip                # sending relay in IPV4 ascii dotted quad notation
    mail_from           # ascii address of sender
    rcpt_to                 # the recipient address.
    blocked_count   # num of blocked attempts to deliver
    passed_count   # num of passed attempts we have allowed
    create_time       # timestamp of creation time of this record
    last_update       # timestamp of last change to this record

[http://projects.puremagic.com/greylisting/source/dbdef.sql]

This extra data would provide a useful "permanent" record that would 
be subject to criminal or civil subpoena.  Some users would gladly 
choose to allow this type of database to be created if it effectively 
reduces spam, but users would need to be fully appraised of the 
privacy risks.

John

---

From: Vernon Schryver <[email-masked]>
Date: Fri, 20 Jun 2003 11:01:36 -0600 (MDT)

> think it would scale very well.

That makes sense for a small site, but I wonder if AOL or Microsoft
would agree.

> already have been learned without any blocking.  ...

Again, that's plausible for a small company or a vanity domain, but
I suspect an ISP would have other views.  
(A system handling fewer than 50,000 to 150,000 mail messages/day
is small today.)

> can be (and probably will be soon) resolved with legislation.

My bet is the opposite and that the employers of legislators will
never let them outlaw "mainsleaze" even as they instruct them to outlaw
the current spammers.  To prove the point at an extreme, consider the
likelihood of congresscritters outlawing their own spam.

> should work pretty well for them. ...

I agree, although I find your 95% effectiveness results surprisingly
high.   Other people who have tried the same idea have reported
significantly lower numbers, although still worthwhile.

---

From: Evan Harris <[email-masked]>
Date: Fri, 20 Jun 2003 12:18:13 -0500 (CDT)

> tracked in the database.  Of greatest concern would be:

I disagree.  One of the nice things about this method is that it keeps
very little profiling info.  It certainly doesn't look at the body or
even the headers of the messages.  The only statistics kept are things that
could easily be retrieved from the mailer logs anyway.

> reduces spam, but users would need to be fully appraised of the

I would agree that users should be made aware of any possible privacy risks,
but most users are already aware that mailer level statistics are kept, and
this is just the same thing, just a different format.

If anyone wanted to, cleaning the database of long term info would be
simple.  But it wouldn't help anything, because all the info there could be
gotten from the mail logs anyway.

If your concern is the longevity of the information, consider running this
as a nightly script:

DELETE FROM relaytofrom WHERE record_expires < NOW();
UPDATE relaytofrom SET create_time = NOW();
UPDATE relaytofrom SET blocked_count = 1 WHERE blocked_count > 1;
UPDATE relaytofrom SET passed_count = 1 WHERE passed_count > 1;
UPDATE relaytofrom SET aborted_count = 1 WHERE aborted_count > 1;

With these, there is no data kept in the database for longer than the
longest expiration time, which is a little over a month.  Most mail servers
keep logs for longer than that anyway.

Evan

---

From: Evan Harris <[email-masked]>
Date: Fri, 20 Jun 2003 12:36:26 -0500 (CDT)

> That makes sense for a small site, but I wonder if AOL or Microsoft

The fact that they have systems that can handle those volumes of mail means
that they also probably already have the needed infrastructure in the way of
distributed scalable database backends.

In the overall picture of handling any individual mail, the checks for
greylisting is a tiny amount.  Multiply that by a million mails an hour, and
it's still the same small percent, which means it should be straightforward
to implement it in a manner that scales with whatever infrastructure is
already in place.

Places like AOL and yahoo already use databases to store their user
accounts, and all the contacts for those user accounts.  Reimplement it to
take advantage of those existing databases, and the impact becomes even
less.

> likelihood of congresscritters outlawing their own spam.

So let them be handled by blacklists.  In either case, the fact that they
are trying to be legit means they are easily blocked since the headers
should not be forged.

> significantly lower numbers, although still worthwhile.

That may be due to the fact that I'm counting all blocked deliveries in my
totals.  Many delivery attempts are to non-existant users, which would have
been blocked by sendmail anyway, but aren't yet at the point that the milter
gets the info.  I didn't have an easy way of eliminating those, but don't
think I should have anyway.  I don't think that the fact that the spam may
have also been caught by another method (even one so simple as if the user
exists) should not be counted against it.  It still blocked the mail before
that check was done.

Evan

---

From: Dave Crocker <[email-masked]>
Date: Fri, 20 Jun 2003 09:32:46 -0700

YS> Lets say a spammers has gained control over a specific IP address for an X
YS> amount of time. He normally sends out 1M messages via that IP. So now to
YS> get around this block, he will send out 2M messages retrying delivery. This
YS> increases his costs slightly but not to the point where it becomes 
YS> unprofitable.

right.

YS> The reason why spammers have not tried this approach yet
YS> become this blocking method has not been widespread.

right.

d/
--
 Dave Crocker <mailto:[email-masked]>
 Brandenburg InternetWorking <http://www.brandenburg.com>
 Sunnyvale, CA  USA <tel:+1.408.246.8253>, <fax:+1.866.358.5301>

---

From: Vernon Schryver <[email-masked]>
Date: Fri, 20 Jun 2003 11:47:47 -0600 (MDT)

> could easily be retrieved from the mailer logs anyway.

Please reconsider.  Contemplate the value of knowing that Bill Gates has
recieved a message from Steve Case (or vice versa) even without knowing
the contents.  Your database doesn't contain messages, but traffic analysis
can be very valuable.  That's why "pen recorders" are used by the police.
It's why the legitimacy of some traffic analysis of email and phone
calls is a continuing issue in federal criminal court cases.

> this is just the same thing, just a different format.

That mailer logs are also quite sensitive does not make your records
less sensitive.

Most users are only a little less clue challenged about their privacy
than about whether their mail involves HTML.  But we're not most users
and must pay attention such issues.

> longest expiration time, which is a little over a month. 

That sounds like a very good idea.

>                                                         Most mail servers

"Most" is a strong word, particularly on issues like this that are
subject to corporate "document retention" policies.  Those policies
should be called "burn after reading policies" because they require
the desctruction of archives and backups lest they be used in future
court cases.

Note also that some few librarians are burning records as soon as books
are returned to avoid their use by snoopers.

---

From: Vernon Schryver <[email-masked]>
Date: Fri, 20 Jun 2003 12:01:48 -0600 (MDT)

> distributed scalable database backends.

It's one thing to have machinery that can send a half a billion messages
per day with currently typical queue delays.  It like something quite
different to have machinery that could send 500M messages/day, many
retransmitted 1-3 times more than currently and spending 1000 times
longer in the queue.

If all of AOL's peers used your system, a lot of AOL's mail would
start spending 10s or 100s of minutes instead of seconds in AOLs queue.

The cost of a retransmission is about the same as the cost of sending
a message.  Given an average message size of ~5K bytes, most of the
round trips as well as all of the DNS and TCP SYN delays in an SMTP
transaction are burned by the end of the Rcpt_TO command.  Contrary
to common naive calculations, the 6 packets and 3 or 4 round trips of
the DATA command are often the tail of the dog.

> take advantage of those existing databases, and the impact becomes even

I'm not talking about the costs for the recipients running your system
but for the senders.

> should not be forged. ...

Blacklists do not work for "mainsleaze" because a significant part
and usually most of those spews is not spam because it is wanted by
its targets.

---

From: Evan Harris <[email-masked]>
Date: Fri, 20 Jun 2003 13:24:36 -0500 (CDT)

> That mailer logs are also quite sensitive does not make your records

The only issue I had with the original statement was the claim that this
method should cause greater concern for privacy.  While there are privacy
concerns with any statistics, I wouldn't consider this method any more of a
danger than normal server logs, since nothing is kept that couldn't be found
there.

Evan

---

From: Yakov Shafranovich <[email-masked]>
Date: Fri, 20 Jun 2003 14:00:50 -0400

>calls is a continuing issue in federal criminal court cases.

There are ways to reduce the problem by storing the sensitive information 
not in plain text, perhaps using some one way function like many systems do 
for passwords. Still it is an issue.

>the desctruction of archives and backups lest they be used in future

Some time ago I was in touch with a CIO-level executive of a major 
university. Their retention policies call for ALL logs to be destroyed 
after merely 10 days due to the increased number of court orders.

Also, the SEC/NASD rules require all email to be stored for three years at 
US-based investment firms. These whitelists just add to the equation.

>are returned to avoid their use by snoopers.

Being a former librarian I definitely agree with that. I had also recently 
wrote a library program used for small schools and specifically put in a 
feature to erase records after the books are returned.

Yakov

---

From: Evan Harris <[email-masked]>
Date: Fri, 20 Jun 2003 13:46:07 -0500 (CDT)

> start spending 10s or 100s of minutes instead of seconds in AOLs queue.

Excellent.  Then AOL will make damn sure that what it sends is not spam.

Seriously, after initial learning, the amount of legitimate mail that
results in a temporary block is pretty small.  How often do you get mail
from someone you've never had contact with versus how much mail do you get
from established relationships?

Speaking for myself and the users on the test systems, that ratio is pretty
small.

> the DATA command are often the tail of the dog.

I did it by packets because that was the easiest, and definitly does impact
people with less than ample connections.  Show me a way to measure the other
qualities on a significant scale, and I'll be happy to attempt to.

> I'm not talking about the costs for the recipients running your system

Admittedly, there is some amount of penalty to senders of email.  But isn't
that the point?  The whole problem of spam stems from the fact that sending
it is abysmally cheap.  And the penalty will be larger for spammers since
they generally don't stick around to establish relationships.

I think this method of "increasing the cost" of emailing is a lot better
than other suggested methods of doing so, an increasing the cost is the only
way we will stop spam.  As long as it remains profitable, it will continue
to be a problem.

> and usually most of those spews is not spam because it is wanted by

Then I guess I don't see the problem.  If the mail is wanted, why should I
be trying to block it?

Evan

---

From: Vernon Schryver <[email-masked]>
Date: Fri, 20 Jun 2003 12:59:15 -0600 (MDT)

> that the point?  ...

No, the point is to penalize senders of spam while doing minimal harm.

> Then I guess I don't see the problem.  If the mail is wanted, why should I

Private blacklists are not practical for any except crazy users
to maintain.  As proof, consider the 7000 entries in
http://www.rhyolite.com/anti-spam/spammers.html
Those are all justified by spam sent toward mailboxes @rhyolite.com
or various spam traps.

System wide blacklists don't work.  For example, dell.com is in my
blacklist for good, sufficient, and continuing reasons, but I'm sure some
of their targets want those "newsletter."  A system-wide blacklist of
dell.com is unworkable except at trivially tiny domains like rhyolite.com

---

From: Benjamin Geer <[email-masked]>
Date: Fri, 20 Jun 2003 22:16:51 +0100

On Fri, Jun 20, 2003 at 01:46:07PM -0500, Evan Harris wrote:
> How often do you get mail

It would be worth testing this assumption in a variety of large and small
corporate environments, rather than relying on your own experience and that
of people you know.

Ben

---

From: Evan Harris <[email-masked]>
Date: Fri, 20 Jun 2003 16:38:36 -0500 (CDT)

> corporate environments, rather than relying on your own experience and that

Absolutely, please do!  I'm very interested in hearing about your results.

Evan

---

From: John Morris <[email-masked]>
Date: Fri, 20 Jun 2003 18:07:33 -0400

>danger than normal server logs, since nothing is kept that couldn't be found

FWIW, my original point was that the grey list approach is a greater 
cause for concern than a simple white list approach (which can reveal 
a user's correspondents but not the date and time of the first and 
last e-mail and the number of successful e-mails).

I agree that the grey  list approach is not radically more 
problematic than mail server logs.  But even on that point, having 
two places where private info aggregates is worse than having one.

Moreover, the greylist might in some cases be easier to locate or 
access -- in some situations, for example a civil litigant might have 
fairly direct access to his or her grey list (and thus be easily 
required to produce it), but the related mail server logs might be 
held by a third party ISP not under the litigant's control.  And, 
once produced, the greylist can serve as an incomplete but still 
useful index into the mail server logs.

By pressing these points, I am not intending to be negative toward 
the proposal -- it certainly looks to be worth exploring further. 
But, when stacking this up against some of the other ideas and 
proposals, I think it is unavoidable that this has greater privacy 
implications than some other approaches.  Now if it is also 
significantly more effective, then greylists may well be worth the 
greater privacy risk (and there may be techniques that can reduce the 
privacy risks, such as the use of one way hashes of the triplets).

John

---

From: Elric Pedder <[email-masked]>
Date: Sat, 21 Jun 2003 00:23:40 -0400

John Morris in <a05200f09bb193252834d@[10.0.1.19]>

> At 1:24 PM -0500 6/20/03, Evan Harris wrote:

[snip]

> useful index into the mail server logs.

If only a hash of the triplet were stored, would this solve
the privacy issue?

Regard,
      - Elric

-- 
Elric Pedder
Mailtraq Development (www.mailtraq.com)

---

From: Vernon Schryver <[email-masked]>
Date: Fri, 20 Jun 2003 22:49:11 -0600 (MDT)

> From: Elric Pedder <[email-masked]>

> If only a hash of the triplet were stored, would this solve

No.  Consider a "dictionary attack."  If you have a copy of the database
and want to know if Steve Case sent Bill Gates a message, you hash
those two addresses with a likely IP address and see if you can get
a hit in the database.  If you do not know the exact IP address, you
can guess it is one of a few thousand (or at most a billion) and make
the corresponding few thousand (or billion) probes of your copy of
the database.  Like a dictionary attack on /etc/passwd, this attack
may not be quick, but it is effective.

Whether the hash is easily reversible like CRC-32 or a cryptographic
function like SHA or MD5 is irrelevant except perhaps for the speed
of the attack.

This sort of thing is why hashes of target addresses are not sent by
DCC clients to servers to be stored in the distributed database.  It
is also why none of the hashes of mail from white-listed senders or
to non-participating receivers is sent to DCC servers by clients.

It might be interesting to consider something similar for the
Greylisting database.  What if only the IP address of the SMTP
client and the Rcpt_To value is checked?

I saw some comments about available counter-attacks by spammers, but
I don't recall seeing a clear description of the easiest.  Spammers
do not need to do real queuing to get though a greylist.  They need
only send to the same target list from the same SMTP client a few
hours after an initial spew.  Mailboxes protected by a greylist will
accept the second copy.  Other mailboxes will see two copies.  That
wouldn't be remarkable, because some spammers are already hitting
individual addresses with several copies per spew.

---

From: Kee Hinckley <[email-masked]>
Date: Sat, 21 Jun 2003 13:38:48 -0400

>individual addresses with several copies per spew.

I agree.  In fact, I think this makes greylisting a very bad idea. 
It magnifies the tragedy of the commons.  Everyone tries to protect 
themselves and ends up making the problem worse for everyone else. 
In the short term it works well for individuals.  As soon as it 
becomes popular, it doubles the spam traffic and solves nothing.
-- 
Kee Hinckley
http://www.messagefire.com/          Anti-Spam Service for your POP Account
http://commons.somewhere.com/buzz/   Writings on Technology and Society

I'm not sure which upsets me more: that people are so unwilling to accept
responsibility for their own actions, or that they are so eager to regulate
everyone else's.

---

From: "Elric Pedder" <[email-masked]>
Date: Sun, 22 Jun 2003 20:19:45 -0400

> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of Vernon Schryver
> Sent: June 21, 2003 00:49
> To: [email-masked]
> Subject: Re: [Asrg] New proposal for spam blocking: Greylisting
 
> No.  Consider a "dictionary attack."  If you have a copy of 
> the database and want to know if Steve Case sent Bill Gates 
> a message, you hash those two addresses with a likely IP address 
> and see if you can get a hit in the database.  If you do not know 
> the exact IP address, you can guess it is one of a few thousand 
> (or at most a billion) and make the corresponding few thousand 
> (or billion) probes of your copy of the database.  Like a 
> dictionary attack on /etc/passwd, this attack may not be quick, 
> but it is effective.

I see what you mean.  I was thinking of the privacy issue from
the perspective of creating new information rather than verifying
that something occurred.  What about a weaker hash?  Such as MD5
reduced to 16 bits?  It would depend on the volume of mail you
received, but I guess at some point the weaker the hash the more 
false positives you'll hit -- probably before the necessary privacy 
level is reached.  I'm interested in this element as other possible 
methods may also involve recording the SMTP envelope and the 
privacy issues will always come up.

Regardless, I'm not an advocate of greylisting.  I agree with
the points you and others have made and the most significant is
that it has a relatively short life span.  However it is one of 
the more interesting solutions to appear recently.

Best regards,
	- Elric

---

From: Vernon Schryver <[email-masked]>
Date: Sun, 22 Jun 2003 18:39:03 -0600 (MDT)

> From: "Elric Pedder" <[email-masked]>

> the more interesting solutions to appear recently.

I agree with the last sentence, but not all of the rest.  Others have
reported that similar tactics are around 30% effective.  The high
effectiveness reported here might be because, as was said, the high
rate included dictionary attacks.  You'd expect dictionary attack spam
to be particularly likely to be "hit-and-run."

My random guess is that should it become popular, its effectiveness will
drop from 30% to 10-20%, because it will ever become universal and many
spammers blocked by it will choose to send to more addresses than go to
the substantial trouble to send to the same targets through the same open
proxies.  If I'm right, 10-20% is nothing to sneeze at, and is as good as
or better than the realistic prospects of several other, purely theoretical
spam defenses whose advocates promise us more.

Note that greylisting can be seen as a variety of quarantine mechanism.

---

From: Evan Harris <[email-masked]>
Date: Wed, 25 Jun 2003 20:57:10 -0500 (CDT)

It should be noted that the 30% is actually quite a low estimate of the
effectiveness, which was based on numbers derived from a slightly similar
implementation.  But the newer implementation has significant advancements
that make a marked increase in the effectiveness, as many others are coming
to realize as they start implementing it.

Here's a key quote from a user on the greylisting-users list hosted at
http://lists.puremagic.com/

> RBLs are weak when new ip addresses are used to spam. Greylists are weak
> when the same ip address is used for repeated spam. Combined they can work
> better than either alone since each attacks the others weakness.
> - Martin Dempsey

Evan