Over the past few months, major players in the world of e-mail have proposed schemes for combating the rising tide of spam. In December, for example, Yahoo! proposed an approach called DomainKeys for validating which messages come from which e-mail servers. In January, speaking to journalists at the World Economic Forum in Davos, Switzerland, Microsoft chairman Bill Gates suggested using a sender-pays system, with money-based e-mail stamps. And at the RSA security conference in February, Gates touted as a spam solution Microsoft’s Caller ID-a variation on the Sender Policy Framework (SPF), which is an anti-spoofing technique that reduces the ability to falsify “From” addresses in e-mail messages.
Unfortunately, upon close examination these techniques turn out to be unworkable or ineffective. They represent centralized solutions that serve the needs of large Internet service providers and, less directly, of large advertisers. Such ideas would be only marginally effective against spam. Worse, they would break services users count on.
Where these proposals fail is in depending on centralized infrastructure and control. Services on the Internet have been widely adopted only when they have embraced decentralized operation. We are developing a spam-blocking solution called Camram that avoids the problems inherent with centralization.
Yahoo!, Microsoft, and the SPF working group are all backing competing proposals that have been characterized as “designated sender.” (America Online has endorsed and is experimenting with the SPF version.) They all attempt to give a receiving e-mail server a way to determine whether the “From” address on an incoming message has been forged.
These anti-spam methods, if widely adopted, would certainly devalue one important tool in the spammers’ current repertoire. We should keep in mind, however, that spammers have many tools. The best these techniques can do is to keep a spammer from using your domain (or AOL’s, or Yahoo!’s) as a “From” address. Spammers could legally acquire thousands of valid domains at little cost, provide valid SPF and Caller ID records for them, and discard them when they drew the attention of spam-fighting organizations.
Such designated sender techniques have other drawbacks as well. One problem is that legitimate mailing lists would become difficult to operate. Another is that e-mail forwarding services, such as those supplied by MIT alumni and other affinity groups, would be broken.
Postage Without Money
The idea of fighting spam on an economic basis using some form of postage has been discussed since 1992. This technique is known as sender-pays because it forces the sender to incur some cost before sending a message. Sender-pays systems can employ one of two different types of postage: money stamps, such as what Gates has proposed, or proof-of-work stamps.
Money stamps are a kind of electronic micropayment. Since the dawn of the Internet era, dozens of micropayment schemes have been proposed. Building the centralized infrastructure required for a worldwide micropayment system is a daunting challenge, however. Not surprisingly, none of these systems has taken off. And there is no reason to believe that value-bearing e-postage would fare any better than its predecessors.
Money stamps raise other significant issues: Who redeems the stamp? Who has taxing authority on the income? Who bears legal liability for erroneous or absent stamp validation? Who controls access to your mailbox and for how big a stamp? These questions make it clear why we and many others distrust money stamps as a solution to spam.
A proof-of-work stamp-or “work stamp”-is a mathematical puzzle that is hard to solve and has a solution that is easy to verify. Another important property of this puzzle is that it has no cheats-that is, there is no way to solve the puzzle by a shortcut.
The major impediment to adoption of any form of sender-pays has been the apparent requirement for wholesale changes to the e-mail system. The Camram (Campaign for real mail) open-source project has developed a hybrid system that solves the problems of classical sender-pays and provides a clear path to incremental adoption. Avoiding problematic money stamps and using proof-of-work stamps, Camram deters spam while maintaining decentralized operation.
The cheat-proof puzzle used by the Camram project is called “hashcash.” The details of hashcash are complex, but here’s a quick explanation. Hashcash uses a seed value consisting of date, e-mail address, and a random number. This seed is fed to a mathematical function called a “hash.” The function performs a calculation based on the input. If the first N bits of the returned number are 0, then the input value is the stamp. Otherwise the input value is incremented by one and the process is repeated until the result is a valid stamp (0 bits in the first N places).
The process of solving such a puzzle is analogous to trying to open a safe when you have only the first two numbers of its combination. The only way to solve the puzzle is to try each of the possible remaining combinations until you find the one that works. The salient features of such stamps are that they require a significant amount of CPU time to generate and demand no central infrastructure. (More details on hashcash can be found here.)
Generating stamps should impose no appreciable penalty on ordinary users, while slowing down spammers so much that their operations become unprofitable. The 23-bit stamps currently used by the Camram project take about 15 seconds to generate on a modern computer. Microsoft has in its research labs a project focused on work stamps called Penny Black, but the company has not announced any product plans for this classical sender-pays technology.
Strangers Pay, Friends Fly Free
The Camram project has coined the term “hybrid sender-pays” to describe a system in which work stamps are combined with other anti-spam techniques in a “cocktail” that stops unwanted e-mail from reaching your inbox while enhancing your ability to communicate with people you know. Mail that arrives without a stamp has the same chance of getting through to your inbox as ordinary mail does in the current anti-spam environment.
The Camram project has learned that the most effective anti-spam cocktail contains at minimum three filters: a stamp filter, a smart “white list,” and a content filter. The white list is a roster of those with whom you exchange e-mail; it is used to let this friendly mail in unchallenged. The content filter looks at the content of the message and makes a probabilistic assessment as to whether the message is spam. Taken together, these three measures implement the principle of “strangers pay, friends fly free.” In other words, strangers who stamp their mail, and friends with whom you regularly communicate, have easy access to your inbox. All others go through the content filter.
To understand hybrid sender-pays techniques by analogy to the real world, imagine a postal system that delivers anything to anybody-for no cost. The Camram filters would function something like an administrative assistant. This assistant passes to you, unopened, mail from friends, as well as all mail, regardless of sender, bearing a valid stamp. After reading the remainder, the assistant tosses the junk, delivers the good mail, and asks your opinion about the questionable mail.
Camram’s hybrid sender-pays system has several advantages over other anti-spam techniques. It is completely decentralized: stamps can be generated and validated at any point in the process, and even offline. It is incrementally adoptable: it benefits the first user, and benefits accrue as the number of users grows. And the techniques can be used over a wide range of configurations, from the individual through the enterprise and ISPs.
The two most common objections to sender-pays systems are the impact on mailing lists and the risks from “zombie” systems generating stamps. Mailing lists present spammer-like loads to an e-mail system, and therefore Camram-like systems would indeed slow them down. The short-term solution is not to use stamps on mailing-list messages-let them traverse the content filter and, after a short time, the recipients’ training of their filters will assure that such messages pass through unhindered. The longer-term solution is to employ a different kind of stamp based on cryptographic signatures. Such signature stamps present a much lower computational load than work stamps and therefore could be used by mailing lists and other bulk mailers to identify themselves to list members as “friends.”
The zombie challenge comes from security flaws in Microsoft software. In the last year, as many as 1.5 million systems running Windows XP or Windows 2000 have been taken over in virus or worm attacks. By some estimates as much as half of all spam sent today is relayed through such zombies.
Even if spammers controlled all of these systems-which is almost certainly not the case-they still would lack the computational power to generate enough 23-bit stamps to deliver today’s volume of spam. And if spammers do begin exploiting zombies to generate stamps, the computational cost of a stamp could easily be raised by increasing the number of bits in a valid stamp. (Individual Camram users are able to decide how many bits comprise an acceptable stamp.) Every additional bit doubles the workload for the spammer.
Hybrid sender-pays systems as exemplified by the Camram project have the potential to make e-mail friendly again. Worries about e-mail from business associates or friends and family going astray become a thing of the past. The work of slogging through a spam trap to recover miscategorized messages is significantly reduced. Good e-mail gets through and bad e-mail is filtered, and these benefits ensue with an absolute minimum of extra work on the part of the email recipient. If compatible sender-pays systems become widely deployed, spammers will have to begin to look for another line of work.