The greylisting concept is presented by Evan Harris in a whitepaper at: http://projects.puremagic.com/greylisting/.
Like SMTP transaction delays, greylisting is a simple but highly effective mechanism to weed out messages that are being delivered via Ratware. The idea is to establish whether a prior relationship exists between the sender and the receiver of a message. For most legitimate mail it does, and the delivery proceeds normally.
On the other hand, if no prior relationship exists, the delivery is temporariliy rejected (with a 451 SMTP response). Legitimate MTAs will treat this response accordingly, and retry the delivery in a little while[9]. In contrast, ratware will either make repeated delivery attempts right away, and/or simply give up and move on to the next target in its address list.
Three pieces of information from a delivery attempt, referred to a as a triplet are used to uniquely identify the relationship between a sender and a receiver:
The Envelope Sender.
The sending host's IP address.
The Envelope Recipient.
If a delivery attempt was temporarily rejected, this triplet is cached. It remains greylisted for a given amount of time (nominally 1 hour), after which it is whitelisted, and new delivery attempts would succeed. If no new delivery attempts occur prior to a given timeout (nominally 4 hours), then the triplet expires from the cache.
If a whitelisted triplet has not been seen for an extended duration (at minimum one month, to account for monthly billing statements and the like), it is expired. This prevents unlimited growth of the list.
These timeouts are taken from Evan Harris' original greylisting whitepaper (or should we say, ahem, “greypaper”?) Some people have found that a larger timeout may be needed before greylisted triplets expire, because certain ISPs (such as earthlink.net) retry deliveries only every 6 hours or similar. [10]
If you operate more than one incoming mail exchangers, and each exchanger maintains its own greylisting cache, then:
First-time deliveries from a given sender to one of your
users may theoretically be delayed up to
N times the initial 1-hour delay,
where N is the number of mail
exchangers. This is because the message would likely be
retried at a different server than the one that issued the
451 response to the initial delivery.
In the worst case, the sender host may not get around to
retrying the delivery to the first exchanger for 4 hours,
or until after the greylist triplet has expired, thereby
causing the delivery attempt to be rejected over and over
again, until the sender gives up (usually after 4 days or
so).
In practice, this is unlikely. If a delivery attempt temporarily fails, the sender host normally retries the delivery immediately, using a different MX. Thus, after one hour, any of these MX hosts would accept the message.
Even after a triplet has been whitelisted in one of your MXs, the next message with the same triplet will be greylisted if it is delivered to a different MX.
For these reasons, you may want to implement a solution where the database of greylist triplets is shared between your incoming mail exchangers. However, since the machine that hosts this database would become a single point of failure, you would have to take a sensible action if that machine is down (e.g. accept all deliveries). Or you could use database replication techniques and have the SMTP server fall back to one of the replicating servers for lookups.
In my own experience, greylisting gets rid of about 90% of unique junk mail deliveries, after most of the SMTP checks previously described are applied! If you used greylisting as a first defense, it would likely catch an even higher percentage of incoming junk mail.
Conversely, there are virtually zero False Positives resulting from this technique. All major Mail Transport Agents perform delivery retries after a temporary failure, in a manner that will eventually result in a successful delivery.
The downside to greylisting is a legitimate mail from people who have not e-mailed a particular recipient in the past is subject to a one-hour delay (or maybe several hours, if you operate several MX hosts).
See also What happens when spammers adapt....
[9]
Although rare, some “legitimate” bulk mail
senders, such as groups.yahoo.com, will not
retry temporarily failed deliveries. Evan Harris has
compiled a list of such senders, suitable for whitelisting
purposes:
http://cvs.puremagic.com/viewcvs/greylisting/schema/whitelist_ip.txt?view=markup.
[10] Large sites often use multiple servers to handle outgoing mail. For instance, one server or pool of servers may be used for immediate delivery. If the first delivery attempt fails, the mail is handed off to a fallback server which has been tuned for large queues. Hence, from such sites, the first two delivery attempts will fail.