Giving E-mail back to the users
First Monday

Giving E-mail back to the users: Using digital signatures to solve the spam problem

Giving E-mail back to the users: Using digital signatures to solve the spam problem by Trevor Tompkins and Dan Handley

This paper argues that current legislative and private attempts to stop spam are either ineffective, or involve unacceptable tradeoffs. The key to solving the spam problem is recognizing the importance of e-mail authentication and the granting of permissions. Properly used, digital signatures can easily authenticate e-mail for effective spam control. The ability to manage public keys for verifying digital signatures provides each e-mail user the individual power to control who communicates with her and can therefore completely eliminate the practice of spamming. Finally, we recommend that software developers build the requisite capabilities for managing public keys into their e-mail programs. We argue for a technological solution as opposed to government legislation.


Defining spam
Inadequacy of currently proposed solutions
The origin and evolution of spam
Digital signatures
Public e-mail
Managing signatures





Unsolicited E-mail containing advertisements or objectionable content, colloquially known as "spam," is becoming an ever greater nuisance while consuming valued bandwidth and data storage space. Efforts to stop spam now involve both private and public sectors. Legislators are rushing to introduce new bills aimed at stemming the tide of spam. Charles Schumer (Democrat (D) — New York) is pushing a national "do-not-e-mail" registry similar to the "do-not-call" registries aimed at telemarketers that many states have adopted (Hansell, 2003). Zoe Lofgren (Democrat (D) — California) and Stanford University law professor Lawrence Lessig are proposing that a bounty be placed on spammers to be paid to private citizens who can identify and catch them (Hansell, 2003). Senators Conrad Burns (Republican (R) — Montana) and Ron Wyden (Democrat (D) — Oregon) are suggesting fines for spammers of US$10 per message (Hansell, 2003). America Online (AOL), Yahoo, and Microsoft are forming an alliance to eliminate the automated generation of spam (Hansell, 2003). There is also an Anti-Spam Research Group headed by Paul Judge from Ciphertrust (Anti-Spam Research Group, 2003). Given the growing proliferation of spam and the public’s increasing intolerance for the problem, it is not surprising to see such heightened interest by both corporations and governments.

We fear that some of these efforts to stop spam, particularly the legislative ones, may have unintended and undesirable consequences. Other proposals may offer partial or temporary solutions, and may simply change the nature and sources of spam without addressing the fundamental principles responsible for the problem. While legislative efforts aimed at establishing penalties and bounties may have the best of intentions, solutions based on offering incentives and disincentives for various types of human behavior have proven to be notoriously unreliable at best. We believe the right technology-based solution is more effective.

Current technology-based efforts to stop spam usually rely on filters that classify messages as either wanted or unwanted using a statistical analysis of their content and/or lists of content or senders to be blocked. These classifiers suffer from Type I and Type II errors: They occasionally allow some spam to get through, and worse yet, sometimes block reception of desired messages. Other technological solutions for the spam problem have been discussed widely and usually involve replacing the current Simple Mail Transfer Protocol (SMTP). However, the organizational and economic barriers for that solution’s implementation on every Internet server in the world are very high.

We propose a solution closer to the heart of the problem that relies on authentication of the sender and the deliberate granting of permission for all e-mail transactions. This more modest solution does not suffer from the above drawbacks since it relies on the end user to conduct the authentication process rather than the server. It uses currently available technology and requires very modest efforts by software developers for end users to adopt it [1].

Our solution gives the end user complete control over who can e-mail her, and therefore eliminates the problem of spammers harvesting e-mail addresses from Web pages, transferring or selling e-mail addresses, or subverting blocking by changing e-mail location. Finally, this solution can be implemented by simply educating end users, and if software developers added some conveniences, it can be done so in a form nearly transparent to even the most uninitiated end user.



Defining spam

The first fundamental problem concerning spam is simply defining it. Unsolicited advertisements are usually but not always unwanted. Many people knowingly and willingly sign up on mailing lists to be notified of product announcements or sales, even from companies that openly pass their e-mail addresses on to other companies. Chain letters, jokes, and newsletters from friends and relatives are sometimes wanted, other times unwanted. Clearly then, one person’s spam may be another’s desired message, and vice versa.

Similarly, legislative efforts aimed at addressing spam on the sole basis of being "advertisement" begs the question of what actually defines an "advertisement"? Is a product announcement or corporate newsletter considered advertisement? Are newsletters or announcements from non-profit, religious, or activist groups considered spam as well? What about notifications of upcoming legislation or policies from local or state governments? Many people, both on the sending and receiving side of these sorts of bulk e-mail, view the Internet as a powerful tool for encouraging citizens’ involvement in democracy as well as a force for promoting positive social change.

In proposing a rigorous definition of spam, we are left with something reminiscent of Supreme Court Justice Potter Stewart’s definition of obscenity: "I don’t know how to define it, but I know it when I see it." When even humans cannot deal well with this sort of ambiguity, automated classifiers that rely on examining content certainly cannot be expected to do any better.

We propose that we should not give the sole authority for deciding what spam is to some overseeing body, whether that be an Internet Service Provider (ISP) or a government. Instead, we feel that the individual user can and should make this decision. Therefore, what is needed is a new user-side software-based solution that allows each individual to decide exactly which senders she wishes to receive messages from based on a deliberate (but easy) authentication procedure. This gives the user both maximum control and maximum flexibility in the use of her own e-mail account.



Inadequacy of currently proposed solutions

We are concerned about the consequences of some of the current proposed legislation aimed at controlling spam. The "bounty" proposed for capturing spammers is particularly worrisome. Some readers might be familiar with the story of Rodona Garst, a notorious spammer who happened to rile a particular computer user with the moniker "Man in the Wilderness". "Man in the Wilderness" in turn hacked into her computer exposing her as a spammer (Anonymous, 2000). While many of us who would like to see spammers identified and stopped may applaud the actions taken by "Man in the Wilderness," the problem is that such "online vigilantism" induces citizens to break laws. Legislation putting a bounty on spammers gives hackers an incentive to harass and invade other people’s privacy. Further, such actions circumvent U.S. Constitutional safeguards put in place to keep legitimate law enforcement in check, such as the prohibition of illegal search, rules of evidence, and the right to "due process." Some hackers are sophisticated enough to set up innocent people so they appear to be spammers without their knowledge. Since spammers can physically reside in any country with Internet access, we can anticipate complex legal issues involving jurisdictional boundaries as we currently witness in cases involving hackers throughout the world. Prosecuting cases brought to authorities by "online vigilantes" could be enormously difficult, and will impose an added burden to the already overloaded legal system. Similarly, simple legislation aimed at requiring advertisers to put "ADV" in the title as some have proposed is not a tenable solution. As discussed earlier, what constitutes a true "advertisement" defies an objective and precise definition. Responsible companies sending online notifications concerning a consumer’s recent purchase or legitimate offers the consumer desires may be classified as a commercial communication and therefore require the "ADV" designation. Surreptitious e-mailers sending spam anonymously will likely ignore the requirement. Thus, spam filters that simply block messages containing "ADV" in the subject line may stop wanted messages and still let unwanted ones through.

While Microsoft, Yahoo, and AOL may be able to identify and slow commercial bulk e-mail emanating from the online e-mail accounts they service, such actions seem to underestimate the ingenuity and resourcefulness of determined spam artists. Further, it does nothing to stop spam from those who send bulk e-mail with their own domains or through their own independent ISP. The spammer Rodona Garst mentioned earlier actually had help from a rogue ISP in sending out bulk e-mail. Since senders’ e-mail addresses, domain names, and Internet Protocol (IP) addresses of originating servers are easy to fake or "spoof," attempts at thwarting spam on the basis of identifying the originating server or e-mail address are completely ineffective. Spammers typically change these spoofed addresses frequently, and therefore any method of spam classification based on logging known spammers’ IP addresses usually proves futile. Further, to be able to identify a spammer based on the sender’s e-mail address, one must first receive, and often examine, an initial spam message, completely defeating the ideal of 100 percent spam blocking. "Block sender" lists, commonly used by major Web-based e-mail providers such as Yahoo and MSN’s Hotmail, are therefore especially ineffective. A tempting alternative is to share "known spammer" sender e-mail lists among end users or generate a public registry of such addresses for all to use. Again, since spammers typically change their addresses on each bulk mailing, such lists offer little protection. We might also be tempted to propose blocking spam based on characteristics of the sender. For instance, when e-mail is sent to multiple addresses it is likely to be spam; however, this again suffers from the same problem as ambiguous content. Often, desired e-mail is bulk-mailed, while bulk-mailed spam can be blind carbon-copied so that it appears to be sent to a sole recipient [2]. Some have proposed changing the e-mail protocol. SMTP was the initial mail transfer protocol used from early in the history of the Internet and for this reason has become the de facto standard. Replacing SMTP, if done correctly, could in some cases limit the proliferation of spam, but the organizational and economic barriers for its implementation on every Internet server in the world are high. Replacing SMTP opens a real can of organizational worms since it involves a world-wide change on a system in which there is no clear governing body to set and enforce standards. Therefore, who should decide what particular type of mail protocol should replace SMTP? And whose proposed version would we replace SMTP with? Every software company and server developer with something at stake will want to have input into any proposed standard. We need only look at how resistant the Internet community has been to adopt the latest communications protocol, Internet Protocol version 6 (IPv6), to see how long such a change could take (Lay Networks, 2002).

Similarly, others have proposed imposing a cost on spammers such as through an electronic analog of the postage stamp (Fahlman, 2003; Templeton, 2003). These proposals typically require senders of unsolicited e-mail to pay a fee for each e-mail communication sent to a recipient. Like the SMTP proposal, however, such a plan would involve an enormous undertaking to correctly collect fees and manage online money transactions. Further, any time pay-for-service is involved, there needs to be a system for resolving billing disputes. Such a system would also have to be administered world-wide. Again, either way it is quite easy to anticipate an enormous tangle of legal disputes if this proposal were adopted. However, perhaps the biggest impediment to adopting such a system is that it appears there is no economic incentive to institute such a plan — it seems that the public is not interested in converting to a system where they now have to pay just to send e-mail, and companies likewise do not seem to exhibit much interest in having to deal with administering electronic postage systems. Even if the "fee" involved consisted of a "price" in terms of central processing unit (CPU) cycles (McCullagh, 2003) which obviates the need to administer pecuniary transactions, this still exacts a cost on legitimate users for no good reason. The fatal flaw of any such system is that without a fool-proof form of authenticating all communications, electronic postage can simply be forged by those with the resolve and necessary expertise (i.e., when free e-mail is outlawed, only outlaws will have free e-mail).

In brief, then, we feel that legislative efforts aimed at criminalizing or exposing spammers will not likely result in the elimination of spam, but rather create a complex tangle of legal cases. The simplest and most immediately obvious solution to spam (i.e., identifying and blocking it based on characteristics of its content or manner of transmission) likewise falls short. Finally, experience has shown that we cannot rely on a simultaneous, coordinated Internet-wide adoption of upgraded software on every e-mail server or the instituting of pay-for-service electronic postage to solve the problem.



The origin and evolution of spam

We gain a much better perspective on the spam problem if we briefly examine its origin and growth. In the early days of the Internet, users were more likely to be computer scientists, engineers, and serious hobbyists. As a small community, these users tended to trade information and software with each other for free as a courtesy to like-minded individuals. Charging money for anything via the Internet was considered impolite at best, and most often viewed as simply vulgar [3].

As general home and business users began gaining access to the Internet, fees were charged most often on the basis of connection time. Unlike traditional postal mail which requires a separate postage charge for every individual piece of mail, e-mail can be sent in bulk as quickly and just as easily to a single recipient. It therefore costs the sender the same amount whether she sends e-mail to one recipient or one thousand. Thus, bulk e-mail advertising began to be an irresistible prospect for Internet-based marketers. However, even though the cost of bulk e-mail was low, the problem became simply to find valid e-mail addresses for recipients. Internet marketers, or "spammers," therefore began to amass lists of known e-mail addresses from sign-up boxes on Web-based services, or by using automated scripts known as "bots" to identify the correct syntax of e-mail addresses on Web pages and newsgroup posts and copy the addresses to a list — a process known as "harvesting" e-mail addresses (essentially, nearly any time a person gives out their valid e-mail address, it risks being added one way or another to a spam address list). Once large e-mail address lists were compiled, spammers could simply sell their lists to other spammers not unlike the buying of selling of postal addresses by traditional direct mail merchants.

Spammers continually add e-mail addresses to their lists, but there is little incentive for removing them. An invalid address simply results in the e-mail not being delivered — it may incur a cost to the ISP(s) involved in transmitting the e-mail, but not to the original sender. Thus, spammers’ e-mail address lists have both grown and proliferated. The ease and minimal cost of sending out thousands or millions of simultaneous e-mail messages via mailing lists, combined with the fact that all one needs to receive an e-mail from anyone else is simply one’s e-mail address, has resulted in the problem we have today.




In real-world face-to-face communication, we control who we converse with and when. One of the ways we do this is by authenticating the person’s identity (face and/or voice recognition, or if we don’t recognize the person we "size them up" and look for appearance and behavioral cues indicating whether the person is a threat or not). If we authenticate that person’s identity, we then decide whether or not to grant the person speaking privileges with us. Further, we exert complete control over the degree of interaction with the other person, from a simple nod and a cursory "hi," to the sharing of our most intimate secrets. In most of our daily life, we maintain complete control over whom we decide to speak with as well as the nature of the transaction. Obviously, we perform all these steps automatically and usually without conscious awareness. Ideally then, Internet communications should operate according to the same natural principles associated with face-to-face communications.

Therefore, in Internet communications, the first step should simply be to authenticate the person sending us a message. The vast majority of the time, if a sender can be authenticated and recognized as a person we know, then we usually accept their message gladly. If one only received messages from people one already knew and wanted to correspond with, there would not be a spam problem.

Spam arises when we wish to keep open the possibility of receiving communication initiated by strangers. However, just as in real life, we ideally wish to exert as much control as possible over who contacts us and for what reason. We especially want to maintain this control if that person is a stranger to us. Again, if the first step is authentication of that person’s identity, then we are in a much better position to assess whether we want to grant them communication privileges with us.

Currently there are attempts to perform simple e-mail authentication of individual users by checking incoming e-mail against the contents of an address book. Users not in the address book have to contact the e-mail recipient and authenticate themselves before being added. This verification usually takes the form of a telephone call, or answering some sort of procedural question requiring true human action (as opposed to accepting an automated response). While such a procedure puts an effective block on spam, this process is really too cumbersome to be practical on a widespread basis. Further, some of these procedures may be more of a nuisance than spam itself (i.e., who wants thousands of phone calls?). Automated order systems cannot answer a question or call a phone number to have the order confirmation e-mail read. For e-mail authentication to be practical there has to be a simple process by which verification can be given easily. We propose a system that possesses the following features of authentication:

  • The authentication process should be easy to initiate. Just as in face-to-face communication, users should have an effortless way to grant their family, friends, and coworkers immediate authentication status.
  • Authentication should have the option of being transferable. Users may want their friends to be able to give other friends authentication for your e-mail address. This is not unlike the real life situation — "Bob referred me to you."
  • There should likewise be the option to make authentication non-transferable. Users may not want certain friends to be able to give other friends authentication to contact the user.
  • Re-issuable. Users may want to re-issue permissions.
  • Changeable. Users may want to change the authentication status and/or attributes of a particular person, or groups of people at any time.
  • Revocable. Users need the option to revoke anyone’s authentication — meaning ability to contact them — at any time for any reason they deem fit.
  • Hide or announce authentication status. Users may or may not wish to let someone know that they have revoked their authentication.

An authentication procedure with these user-defined parameters gives e-mail users complete control over her own communications. Currently, once a spammer knows one’s valid e-mail address she can continue spamming a person indefinitely or share one’s e-mail address to other spammers on an e-mail address list. In the proposed system, if an e-mail account holder receives spam, simply revoking the offender’s authentication status solves the problem forever. The offender can no longer spam the user, nor can the offender transfer the right to communicate with that user to anyone else. Spam from this source is completely and permanently stopped.

This system also stops e-mail stalking or harassment. For instance, in the current e-mail system a jilted lover or jealous co-worker can simply sign up for an instant Web-based e-mail account and send threatening messages anonymously. Putting the sender on a "block sender" list is ineffective since all the sender needs to do is sign up for a new instant account under a different false name (masking the IP address through a proxy to prevent being traced by the ISP if necessary). More importantly, using the same techniques it is just as easy for sexual predators to send correspondence and pornography to children. In all of these cases, a permission granting system can eliminate these threats.



Digital signatures

Because spammers often spoof e-mail addresses, using an e-mail address as the basis for authentication is obviously the wrong approach. What is needed is a system that employs a unique identifier for each e-mail sender not available to potential spammers. While the spammer might know a valid e-mail address, the spammer cannot send to that address without the correct identifier.

Existing e-mail encryption programs rely on a system of trusted keys and digital signatures for authentication (Youd, 1996). While e-mail addresses can be spoofed, digital signatures are practically impossible to spoof [4].

Digital signatures are created and verified by cryptography, an area of theoretical computer science concerned with the transformation of messages into unintelligible code and back again. These signatures employ an algorithm using two different but mathematically related "keys," one for creating a digital signature and another for verifying a digital signature (Schneier, 1996).

Because cryptography is more concerned with the secure transmission of data between known parties, its use as a way of controlling spam is not immediately apparent. Also, the terms "keys," "hash values," and "trust" used in cryptography are often confusing to the average e-mail user. However, it is clear that digital signatures from asymmetric key cryptography is all that is needed for end users to gain complete control of spam. The challenge lies in adapting these cryptography tools for use in verifying e-mail authentication, as well as making the process and terminology less confusing for e-mail users.

The complementary keys in asymmetric cryptography are called private and public keys. Private keys are only known to the signer and used to create the digital signature by encrypting a mathematical representation of the original message. Public keys, are used by receivers to verify the digital signature by decrypting the mathematical representation of the message. This mathematical representation is then compared with the received message to confirm that it is unaltered. Although the keys of the pair are mathematically-related, their secure implementation makes it "computationally infeasible" to derive the private key from knowledge of the public key (Schneier, 1996). Thus, widely distributed knowledge of the public key of a given signer does not allow discovery of that signer’s private key for digital signature forgery.

The mathematical representation of the message is computed via hash functions. A hash function is simply an algorithm which creates a digital representation or "fingerprint" in the form of a "hash value" which is much smaller than the original message and unique to it (Schneier, 1996). Any change to the message inevitably produces a different hash value when the same hash function is used. Secure hash functions make it computationally infeasible to derive the original message from knowledge of its hash value (Schneier, 1996). These secure hash functions efficiently provide assurance that there has been no modification of the message since it was digitally signed. But what makes the use of digital signatures valuable for spam control is the private key used to encrypt the hash value. Because the only key that can decrypt (unlock) a hash value is the mathematically-related public key, the receiver can now be assured that the message was sent from the owner of the private key, The hash value provides the assurance that the message hasn’t been altered or switched in transmission. More precisely, the use of digital signatures involves two processes, one performed by the signer and the other by the receiver of the digital signature. Digital signatures use a hash value derived from both the signed message and a given private key. Verification is achieved by checking the digital signature against the original message and a given public key, thereby determining whether the signature was created for that same message using the private key that corresponds to its related public key. To sign a message, a hash function in the signer’s software computes a hash value that is unique (for all practical purposes) to that message. The signer’s software then transforms this value into a digital signature using the signer’s private key. The resulting signature is now unique to both the message and the private key used to create it. This digital signature is attached to its message and stored or transmitted with it. Verification is accomplished by computing a new hash value of the original message by means of the same hash function used to create the digital signature. Then, using the public key and the new hash value, the verifier checks whether the digital signature was created using the corresponding private key and whether the newly computed hash value matches the original. The verification software confirms the digital signature as "verified" if the signer’s private key was used to digitally sign the message, [5] and the message was unaltered [6].

While traditional public key cryptography software contains all the necessary tools to manage secure transactions via e-mail, it has not been expressly set up for authentication-based e-mail for the purpose of controlling spam. We believe that expressly setting up public key cryptography with signature management tools for spam control, users could block messages without signatures and mark signatures for which the user no longer wishes to receive messages from. The user could restrict messages by individual keys, allowing receipt of only those with trusted signings, or only those that she has given trust. But by adapting cryptography tools from encryption to spam control, the keys could have attributes assigned to them, such as the capability of being blocked, unblocked, accepted with certain rights, or accepted temporarily. Alternatively, one could imagine a pool of acceptable keys, for which the end user could move individual keys in and out of. Messages signed with keys in the acceptable pool would be allowed through, others not.

Here’s how such a system might work: An e-mail account holder (referred to as E) sets up an e-mail account in the standard way. E then contacts members of the address book however E chooses and, in a secure way, gives E’s e-mail address and E’s public key. This key is given to each address book member or posted on a Web site known to be E’s so that anyone wishing to receive e-mail from E can verify that it actually came from E. These members in turn send their public keys or post them so that E can retrieve them. E then only keeps keys from people that E wishes to receive e-mail from [7].

By only keeping desired keys E now has effective control over spam. When E gets e-mail, the program performs the computations necessary to determine the validity of the message and then searches against the pool of acceptable keys for signature verification. If the key is in the acceptable pool of keys setup by E, then the e-mail is accepted. E-mail without a signature or not verified by a key in the pool of acceptable keys will simply be denied. Alternatively, the e-mail could be sent back to the user informing them that they need to have their key accepted by E first. At E’s discretion, E could let e-mail through containing new keys from unauthenticated users requesting authentication status if a key was included and marked "valid" (by having a trusted friend’s signature). E could then decide if this new key will be added into E’s pool of acceptable keys allowing that person to continue to e-mail them. This is similar to how we implement face-to-face introductions via friends. Simply removing keys, or moving them in and out of the pool of acceptable keys is easily implemented into software and gives users maximum control of what e-mail actually is accepted.



Public e-mail

So far, this solution addresses communication between users who know each other. However, we quite commonly use e-mail in public ways, which opens the door to spam. Thus, the proposed system needs to address this. How do people — such as professors, senators, public liaison representatives, representatives for whistle blowers, and others who need to have a publicly available e-mail address — ensure strangers can contact them (anonymously if necessary)? Also, how will this work for online merchants who must verify online orders through e-mail?

For those needing publicly available addresses, we suggest putting a text entry form on a publicly-accessible Web page allowing those who wish to e-mail them the opportunity to send them a message. The entry form could simply dump the text into a database, or could e-mail it to the user with its own digital signature [8]. Senders could, of course, use the text entry form to identify themselves and send a public key requesting that it be placed in the pool of acceptable keys. To alleviate concerns that "bots" could be written to scan for these text entry forms and fill them in with spam, a graphically presented phrase could be placed on the Web page that required its typed entry for the text to be accepted by the text box. This is commonly done on Web sites to thwart automatic account generators [9].

Standard business cards would need to list e-mail uniform resource locators (URLs) instead of e-mail addresses. Digital business cards are becoming more popular on personal digital assistants (PDAs) and keys could be beamed to each other along with the e-mail addresses, reducing one’s reliance on e-mail URLs. Further, with the proliferation of flash memory cards, and small universal serial bus (USB) memory devices, it will be quite easy in the near future to exchange e-mail addresses and keys among users at trade shows, conferences or anywhere else one might use a typical business card for address exchange.

Online merchants can simply post a public key that customers can download and mark "acceptable" when signing up for an account or filling out a credit card order form. A secure Web page, properly verified, ensures that the key is from the vendor.

With digital signatures, the resultant process would then consist of selecting the e-mail member from the address book. The user would type the e-mail message, sign it, and send it off. The recipient of the e-mail in turn will have a program that checks for the address in the address book along with the digital signature. If the digital signature is found, is valid, and is signed with a key in the acceptable pool of keys, then the message is passed on for perhaps further filtering or for reading by the recipient. If the signature is found to be signed with a key that is blocked, or does not exist, or is otherwise invalid, the e-mail may simply be deleted automatically or sent back to the user with a message stating the reason why.



Managing signatures

While we have so far outlined the barest necessities for a permission-granting e-mail system, keys used for verifying digital signatures also have useful advanced features that can be incorporated as well. E-mail programs could let users assign a variety of different rights to these verification keys by levels. For example, one could restrict some keys to a certain number of messages in a specific time period, or temporarily block messages from a currently bothersome sender through the associated key. One may also assign keys a certain number of allowable uses or assign an expiration date. One could make temporary keys for public use. For instance, if the user wished to post a message in a public newsgroup and be contacted via e-mail the private key may only allow reception of the first 25 responses from the associated public key, or perhaps only for several days. The trust level for this key could be set to "none" [10]. The temporary nature of this key would limit the number of possible spam messages resulting from public posting of an e-mail address and key.

However, even subsequent to issuing temporary keys, further rights could be assigned as well. If one wished to continue receiving e-mail from a particular person after a limited-use key expired, the permanent public key could be accepted from that person and entered into the pool of acceptable verification keys. Further, rights could be assigned to allow "friends" to mark keys as good or bad to other people’s keys if desired. Since any key’s status is always changeable, the user hardly needs to be concerned about someone distributing her private key to an unwanted party. There are essentially countless scenarios of key and signature transactions that one could envision, and the point here is that assigning and managing rights to the public keys used for verification gives the user complete and far-ranging control over just about any conceivable scenario.

For a would-be spammer, the proposed system would be practically impossible to circumvent. Without a valid signature, e-mail will never be received. In essence, the system blocks all forms of mass e-mailing except for the case when the e-mailer has been given express permission to do so (via a valid verification key on the receiver’s end). As long as key security is maintained, surreptitious attempts at obtaining or forging messages will also be thwarted. The more users who adopt the use of digital signatures in this way, the more difficult it will be for spammers to find targets. Before long the available pool of possible spam targets will shrink dramatically. Once the vast majority of e-mail users convert over, we envision the practice of spamming to cease entirely in short order.

As an added benefit, the system will not merely result in the complete elimination of spam. Since the user exerts complete control over who communicates with her, organizations and legitimate marketers will be forced to be much more responsible in their behaviors (or else have their public keys moved out of the acceptable pool of public keys used for verification). The right to e-mail a person will become a cherished privilege. Since signatures may be blocked without the sender being made aware, companies and organizations will have a powerful incentive to stay on users’ good side.

Finally, since the user maintains control of her e-mail account in this system, those who might still (for what ever reason) wish to receive unsolicited e-mail from credit card companies or porn sites can still do so. However, very importantly, those who don’t need never be bothered by these again.




For any proposed solution to the spam problem to be adopted, there must first be thought given to how difficult it would be to implement in proportion to the anticipated benefits. Every proposed solution has its advantages and disadvantages in this regard.

Software filters tend to be implemented by software developers who then distribute their software to end users. Thus, from the end users’ point of view, spam filters are rather easy to implement initially, but their constant need for updating is not so desirable. No matter how sophisticated filters become, spammers can always find ways to circumvent them. When filter designers make the filters more stringent, they risk inadvertently discarding wanted messages. Therefore, as mentioned previously, the fatal flaw of spam filters is that they inevitably suffer from Type I and Type II errors. Despite the ease of the initial implementation process then, spam filters are not the best solution.

Another common proposal is to change the e-mail protocol. However, unlike filters, this would be much more difficult to implement, even though end users would suffer no changes at all. Again, as mentioned previously it is very difficult to get organizing bodies, server operators, ISPs, and software developers to agree on a standard protocol, let alone adopt them globally within a reasonable time frame. Even if a new protocol were implemented, though, it would have only limited success in controlling spam. For instance, one such proposed change to the e-mail protocol would limit the number of e-mail messages allowed to emanate from a particular account over a specified period of time. No matter what restrictions of this sort are imposed on e-mailing, inevitably spammers will find a way to circumvent them while legitimate users will be the ones whose activities are curtailed. Similarly, any global, server-side restriction on e-mail behavior is bound to suffer from analogous sort of Type I and Type II errors as is the case with filtering.

The attempt to make spam costly replaces one burden with another, viz. spam with e-stamps. Promoters of these ideas point out that the costs would be nominal to casual users, but if the costs are too low, the expense of collection becomes too high how ever it is implemented. In general, we believe per item costs are antithetical to the nature of the Internet — especially when such costs are unnecessary for solving the spam problem. The twist on this idea from monetary costs to CPU cycles does not appear much better. Both suffer from an inherent user backlash and getting an organizational plan accepted across the Internet world seems unlikely.

A completely user-side digital signature-based solution as proposed would not suffer from these problems. With some changes to currently available software, this would be relatively quick and easy to implement. The authentication process through digital signatures requires only that e-mail software developers add extra key management capabilities. End users would simply generate a public and private key pair for digital signatures. In most instances, the act of sending an e-mail may remain as simple as just selecting the recipient from the address book and hitting the "send" button. The software would calculate and attach a digital signature for that message and send it off to the recipient. On the receiving side, the recipient’s e-mail program automatically detects the signature and then determines whether it is valid or not. If the signature is valid, the e-mail is placed into the in-box, otherwise the e-mail is deleted, or sent back with a message indicating why. Implementing this solution may therefore involve little more than modifying existing e-mail programs — in which case the user is merely inconvenienced by nothing more than a software version upgrade.

The implementation of this process need not be done all at once. Existing e-mail programs will still be able to receive e-mails with digital signatures. In this case, the signature would either be ignored by the software or simply appear as a string of nonsense characters at the top or bottom of the message body, depending on how the software is implemented. Thus, people with the newer software version can always e-mail people with the older software, but not vice versa unless there is some provision for sequestering "unsigned e-mail" into a separate folder. We envision that as users begin adopting the new system, they will simply maintain these separate folders and divert unsigned e-mail to a designated folder. E-mail with valid signatures would similarly go into its own folder. As more users began using digital signatures, the content of the unsigned folder will ever more likely be spam. Eventually, the user may wish to simply phase out the "unsigned E-mail" folder altogether. When a sufficiently high proportion of users adopt the new system — reaching a critical point — e-mail spammers will be effectively shut out of all possible entry into legitimate electronic communication.

The next question to be addressed is: Who should begin implementing personal authentication-based e-mail? The obvious first choice is for those already possessing the lion’s share of e-mail applications. With Outlook and Outlook Express, Microsoft certainly has overwhelming market share in e-mail applications. Fortunately, Pretty Good Privacy (PGP), an asymmetric cryptography system for e-mail is popularly added to these e-mail programs. Other major programs such as Eudora and Mac Mail also have the capability to add PGP. There are forms of PGP for e-mail that is freely downloadable at the time of this writing. Unfortunately, the necessary key management tools for spam control are not available in any system we have seen to date. However, it merely takes the action of any person, company, or group of people to add these features so that users can completely rid the Internet of e-mail spam [11]. As opposed to server-side changes to the e-mail protocol, a PGP implementation merely needs to add more appropriate digital signature management tools to make the process of combating spam easier. PGP has a long history as a freeware and "profit ware" product, and has therefore seen extensive use world-wide. This makes it a good software implementation for adoption. Further, its publicly available source code allows for individuals and the public community at large, the opportunity to build the necessary key management tools to implement this proposal. Because PGP is not freely licensed to corporations, PGP Inc. would have to implement at this level, or transfer the right to corporations through licensing sales or other legal transactions [12]. We expect that large ISPs and corporations would see the value to their enterprises and encourage their users to adopt systems that implement spam controlling digital signatures.

Some might argue that the bother involved in this proposal is too great. We believe that proper integration into e-mail programs minimizes this. We also note that certain operations in our lives involve inconvenience. Changing the oil in your car is an inconvenience, but not doing so eventually becomes more of a hassle. We live in a world where it is now important to regularly check our credit histories and examine our credit card and telephone bills for unauthorized charges, which are inconveniences we live with in modern times. Many of us also have to delete spam messages every day despite using filters and guarding our e-mail addresses from being harvested. Maintaining a list of keys and marking them "good" or "bad" so as to verify that messages are wanted seems a small added inconvenience in comparison to the nuisance of receiving spam and other unwanted E-mail.




As mentioned before, legislation aimed at providing incentives or disincentives for certain types of human behavior has an historically poor track record — and providing punishments for spamming behavior will certainly be difficult if not impossible to enforce. Many of the proposed legislations described above will likely have all sorts of undesirable and unforeseen consequences. Further, once legislation is adopted and is subsequently shown to have unappealing flaws, it is very difficult to have it repealed. However, since the spam problem may be solved easily through a modest technological solution as we have outlined in this paper, legislative action may be better aimed at measures and campaigns that might promote adoption of permission granting e-mail. We suggest that the interest of everyone — large software companies, ISPs, consumers, and the government alike — is best served by quickly developing, adopting, and encouraging the use of an e-mail system using digital signatures for spam control. End of article


About the Authors

Trevor Tompkins is the founder of a private organization dedicated towards the technological solution of SPAM through the use of digital signatures. He holds a B.S. in Economics and is working on his M.S. thesis in Logic and Computation, both from Carnegie Mellon University.

Dan Handley holds an M.S. in Logic and Computation from Carnegie Mellon University and is a researcher in the Computational Systems Biology Group at Carnegie Mellon University. He is also currently a Ph.D. student in Human Genetics at the University of Pittsburgh.



1. It can in fact be implemented in some form already by using currently available software.

2. Some spammers use messages in the form of graphics instead of ASCII text in an attempt to conceal content from spam filters that examine content for key words indicating spam.

3. Due to its sheer volume and perceived worthlessness, the word "spam" was therefore coined as a derisive term for messages from strangers who offered something for money.

4. Spoofing could take place by fooling the user that a key is from someone it actually is not from. Users should be aware of this and therefore require a trusted signature, or some other way of ensuring the key and signature are from who they say they are.

5. This is known if the signer’s public key was used to verify the signature because the signer’s public key verifies only a digital signatures created by the signer’s private key.

6. This is known if the hash value computed by the verifier matches the hash value from the digital signature.

7. This could be accomplished with current encryption programs by simply signing the public keys.

8. Trusted because it was set up by the user.

9. PayPal uses this for generating accounts, Geocities does for internet Web sites, Yahoo Personals, and Club accounts also use this type of verification procedure.

10. The e-mail sender would need to digitally sign the message with the uploaded temporary public key instead of his usual private key for this to work. Good software would make these differences transparent to the user so as to appear much like his normal operation. The only difference should be the temporary nature of the key.

11. To this end Trevor has started work on a plug-in for Outlook that will be freely downloadable at

12. GPG (Gnu Privacy Gaurd) is a crypto system designed for e-mail very similarly to PGP. Its main advantage is that it is completely free of any commercial licensing. It is available for Linux, Windows, and Apple operating systems. GPG and PGP cannot be mixed, but they operate very similarly.



Anonymous, 2000. "Man-in-the-Wilderness," at, accessed 3 May 2003.

Anti-Spam Research Group, 2003. Anti-Spam Research Group Web site, at, accessed 3 May 2003.

Scott E. Fahlman, 2003. "Spam and Telemarketing,", accessed 26 May 2003.

Saul Hansell, 2003. "Finding Solution to Secret World of Spam," New York Times (5 May) Late Edition — Final, Section C, p. 8, Column 4, and at, accessed 5 May 2003.

Lay Networks, 2002. "IPv6 or IPng (IP Next generation):" at, accessed 5 May 2003.

Declan McCullagh, 2003. "Best way to stop spammers? Make them pay!," at, accessed 26 May 2003.

Bruce Schneier, 1996. Applied Cryptography: Protocols, Algorithms, and Source Code in C. Second edition. New York: John Wiley.

Brad Templeton, 2003. "A variety of weapons against SPAM that don’t require laws," at, accessed 26 May 2003.

David Youd, 1996. "What is a Digital Signature? An introduction to Digital Signatures," at, accessed 3 June 2003.

Editorial history

Paper received 6 June 2003; accepted 7 August 2003.

Contents Index

Copyright ©2003, First Monday

Copyright ©2003, Trevor Tompkins and Dan Handley

CGiving E-mail back to the users: Using digital signatures to solve the spam problem by Trevor Tompkins and Dan Handley
First Monday, volume 8, number 9 (September 2003),

A Great Cities Initiative of the University of Illinois at Chicago University Library.

© First Monday, 1995-2016.