A Better Way To Squelch Spam?

An open-source scheme would impose a computational "cost" on junk mailers while leaving legitimate users of e-mail alone.

By Eric S. Johansson and Keith Dawson

March 26, 2004

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).

Story continues below

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.