I promised to write a few notes about how SPAM prevention techniques from email might apply to IM and other forms of messaging. 

Spam can, and does, happen in any type of communication. It happens in paper mail in the form of flyers, in traditional phone systems as telemarketing calls, and as junk faxes. Today email, mailing lists, newsgroups have it; and it is clear that spam will happen in IM and voice and video over IP systems too. Fundamentally, there is a large value in allowing someone with whom you have no previous relationship to send you communications. The cost is that people can send you things you really would rather not get, and there is no way to make that problem go away. There are ways to mitigate it, however. 

Many of the problems that complicate SPAM prevention in email also have parallels in IM and VoIP. Mailing lists complicate consent based security because they introduce an intermediary. In the same way, IM and VoIP conferences with a centralized conference server cause almost identical problems. 

IM buddy lists have helped with SPIM by forming white lists. In many ways, buddy lists are similar to the email address books that some programs use to help rate junk mail. I'm aware that there are still some people who don't use email address books, but they are rare at this point. One key difference with IM systems is that most of them have an explicit way for Alice to ask Bob to add her to his buddy list or to grant permission to view his presence information. 

It is worth noting that with all of these messaging systems, some users want features like logging, virus checking, and policy enforcement, and some want strong end to end confidentiality, integrity, and anonymity. Anonymous communications have appeal not only to libertarians, and governments have gone to considerable expense to make sure anonymity is available. 

IM and VoIP also have stored messaging modes. Some people say that it is not IM if it is stored. This may be a matter of definition, but the fact is, the end solutions that users use for IM are all moving to having an option of stored IM because users like it. Users want this stored IM to happen even when their computer is offline. Voice is commonly stored in the form of voicemail as well as video. 

SPAM has been sent over the following media: paper mail, email, news, IM, pagers, SMS, voice phones and radio, and video phones. I would guess that it has probably been sent on just about every communication medium that has a bit rate faster than smoke signals. 

So on to the heart of this. What approaches are there for reducing SPAM in messaging, and which messaging forms can they be applied to. 

I look at these approaches from the perspective of cost. It costs some amount per message to send spam. It costs something for a receiver to dispose of spam. Deleting an unwanted email is clearly cheaper than the interruption typically caused by telemarketers. There is an even larger cost when someone I wish to communicate with gets blocked by an automated spam prevention mechanism. Preventing SPAM will raise the cost of sending and receiving messages that are not spam. The cost of sending bulk flyers in the US is surprisingly low; most people get more than they want, but throwing them out each day does not really cost much. My cost of disposing of SPAM email is many orders of magnitude higher than my cost of disposing of flyers. People seldom accidentally toss out real mail they want. My wedding invitations were constructed to look very much like junk mail (and did not have the senders' identity on the envelope) but only one person accidentally threw it out. It's possible she didn't want it anyway. 

The mostly widely used SPAM prevention technique is content inspection, an effort to determine whether the contents represent value to the receiver. The fact that an email message is a complete communication makes this possible. With IM, this kind of detection is much harder, because it is difficult to discern the value of a conversation from the first message in it. Voice is even more difficult: we have all had the experience of being interrupted by a telemarketer and having to listen for a few moments before we determined this was definitely a telemarketer. Computers will be worse than humans at this. Causality ensures that the more interactive a communication medium is, the more difficult to estimate the value of the communications before the communications occur. This observation pretty much dooms this approach for non-stored voice and video and suggests that it would be very difficult to make it work for IM. It also hints that some techniques that have been proposed for email, in which quarantined senders could only send very small messages, might have exactly the opposite of the desired effect. 

Another technique is black and white lists. Clearly these have little value if it is trivial to spoof the sender's identity. Solving identity issues for IM and VoIP systems is somewhat easier than for email, but the problems are similar. IM and VoIP are more or less only used in an "online" sense so there is less need to check signatures offline and to check signatures or messages that have been archived a long time. This fact makes the problem somewhat easier for VoIP and IM than for email, but on the other hand, email is only sent or received when online, so some solutions that place the burden on the MTA may wind up similar. IM and VoIP do not have the huge existing deployments of email, and generally IM and VoIP relays don't modify headers and bodies as much as email relays do -  such modifications complicate the canonicalization for computing signatures. There are multiple proposals for computing a signature of some group of headers and possibly the body for email and there is one such proposal for SIP. Generally the signature signs on behalf of a user or a domain and asserts the identity of the sender and enough other fields to avoid replay and to integrity protect the critical information in the message (such as subject and body). For me, the more interesting part of this concerns the fetching of the public key used for the signature and who is asserting what about the message. Some schemes rely on whatever the security of a DNS lookup is to find the public key. Some schemes rely on domain certificates issued by well known CAs. I think most people have concluded that a model in which every end user has a certificate issued by a well known CA is unlikely to be deployed. 

It is important to consider who is in the best position to make assertions about the identity of a message sender. If Cisco issues an account to Cullen, the IT department knows that it is fluffy@cisco.com. They give me a shared secret and perhaps a crypto dongle of some sort that I can use to authenticate to them. They'll be told if I get fired and will revoke the account. They care if the account is misused (a typical public CA does not). Cisco is in the best position to assert things about the identity of fluffy@cisco.com. Cisco creates and manages this identity. No matter what the messaging medium is, it seems to me that having cisco.com assert that a message was sent by fluffy@cisco.com is the right thing. Then someone needs to somehow validate that the assertion really was made by cisco.com. 

Once we have some cryptographically strong idea of who sent the message, several techniques can come into play. The first is checking buddy lists or address books. I consider this a 0th order reputation service. Rules like *@cisco.com could easily be added at this stage. A 1st order reputation service might use my address book and all my friends' address books. I don't imagine a user would enter policy rules more complex than today's email filter rules. Reputation services seen like an incredibly complicated problem, and I'm not going to pretend to know anything about them, but I will hazard a few thoughts. Obviously, most SPAM is stuff I don't find valuable but other people sometimes do, or else there would be no value to the advertiser who sends it. There is a value judgment going on, and people whose tastes are like mine can help distribute the effort of killing a particular piece of SPAM. I think there is a coupling between killing SPAM this way and the type of weak trust that social networks generate. Deciding if I will pass on one friend's phone number to another is a hugely complex issue that I could never describe in an algorithm to a computer. (Tell me that a neural net is going to learn how I do this and I will have to slap you with a dead tuna.) Email addresses are often less private than telephone numbers, and telephone numbers may have become more private since email came into widespread existence. Sharing white lists and black lists, and considering the entries on these lists not to be (excuse the pun) black and white but instead evidence that can be combined in a robust bayesian manner to make a decision, seems like an avenue worth exploring. 

Reputation services could take other forms such as a Circle of Trust, in which a group of companies all white listed each other and agreed to play nicely. Each company would accept only a somewhat limited liability for not playing nicely; so at some point, the circle would get large enough that the advertising potential exceeded the cost of the fine for not playing nicely. Because of this, the scaleability of circles of trust is inherently limited. It is not clear how large they do scale. Related to the Circle of Trust is the Star of Trust idea, in which a centralized service provider makes contractual play nicely deals with many companies and becomes a trusted broker in the middle, paid by each point of the star to make sure that only those who play nicely get in the star. In many ways, this is the model of why the PSTN limited spam before do-not-call laws were passed. Many other trusted brokers in the middle of internet business models have failed. 

The approaches to SPAM I describe below are probably best combined with white lists, in that they only operate when you communicate with a person for the first time; after that the other person is put on your white or black list. Since these approaches work when the sender has no preexisting relationship with the receiver, they are basically about raising the cost of sending SPAM.

Computational puzzles. Here Bob's computer asks Alice's computer to compute some problem that is hard to compute but easy for Bob's computer to verify. Because a valid user might have an old PDA that Bob's computer will have to make allowance for, and an attacker could have a new, fast computer, computational problems are not too expensive for spam senders. If we assume that spam sending computers are two orders of magnitude faster and cost $1000 per year and that normal senders (with slow computers) would spend 10 minutes to communicate with someone for the first time, then we get a cost of about 200 micro-cents per message. One argument I hear against this scheme is that spam senders will just harvest zombie computers to do this - at the micro level this will undoubtedly happen. If 5% of the computers that are used for communicating were doing this, this method would still allow only 7 spam messages per day on average, so in the macro sense, this harvesting of computers argument is somewhat bogus. A very rough proposal of how it might be done in SIP is in draft-jennings-sip-hashcash-00. There has also been some work that suggests that, although CPU speed varies by two orders of magnitude, memory access speed is more constant, which makes it possible to design computational puzzles that are limited by memory speed access instead of CPU speed. I have not done a careful counter example to this work, but at the back-of-an-envelope level, I suspect this technique will not hold up in some cases important to messaging. The memory I have looked at in the literature on this ranges from a set top box to a high end PC. However the set top box was running an Intel-compatible processor and basically had a PC bus and memory subsystem design. The comparison was not between a low power cell phone and a Sun server. The amount of memory available at a given speed is also critical. If a cell phone can use 2 megs of memory to compute this function, then the attacker also only has to use 2 megs and can easily get a processor that has this as cache; the speed difference will be more like three orders of magnitude. If we move up to 256 megs, the attacker can use the memory on an AGP graphics card, which has an alarmingly fast bus. 

Turing tests. Basically Alice sends Bob a message, and Bob asks Alice to do some work that only a human can do but that a computer can verify for Bob. This method raises Alice's cost of sending spam to Bob. I estimate that this can raise the cost of each SPAM message to over 400 micro-cents per message. The two relevant assumptions are a low labor rate of $100/year and 30 seconds per message. An interesting side point is that, for very low-cost labor, Turing tests are not much of a win over computational puzzles. If you assume $5/year labor, then Turing tests cost more like 40,000 micro-cents per message. Turing test approaches have had limited deployment with email today, but the people using them still receive spam because there is no cryptographic sender identity; Turing tests will work better if they have sender identity. 

Payment at risk. The idea here is that Alice pays Bob to send him a message, and if he likes it, he refunds the money to Alice. The cost of this scheme is that someone has to pay the fees to process the two payment transactions. At least one vendor is now willing to do this for 15% of transactions as low as 1 penny. If the payment at risk is 5 cents/message and you send messages to 10 new people a day, this will cost you few bucks a month. If you don't send email to new people, it will not cost you anything. It would be interesting to see what this would cost someone like a WG chair who sends email (via lists) to lots of new people every year. The cost might not add up to much at all.  Details of this SWAG are in draft-rosenberg-sipping-spam-00. A proposal of how it might be done in SIP is in draft-jennings-sipping-pay-00. Payment need not be at risk - it could just be required, like postage stamps. And the payment need not be to the receiver but could be to anyone and still reduce spam. For example, if you want to send me an email, you must donate 5 cents to my favorite charity, say ISOC, uh, no, never mind. 

Legal Approaches. Many of these require a spam sender to set the Not Evil bit in the message, and they then try to maximize the legal pounding the sender gets for setting the bit incorrectly. Some try to make the sender violate contractual, trademark, or copyright law by setting the bit. Again, more in draft-rosenberg-sipping-spam-00. In general, these might work if you could be sure that senders were in particular legal jurisdictions and could find them and prove they sent the spam. For traditional telephone, the price of telemarketing to US destinations from outside the US is too high because of long distance rates. From inside the US the phone company has reasonable odds of tracking a sender down due to pre-existing billing-oriented relationships. These circumstances make the do-not-call law in the US work. (WWW.DONOTCALL.GOV or tel:+1-888-382-1222, or TTY tel:+1-866-290-4236) A similar do-not-email registry would just result in people sending email from outside the US or denying they sent it at all. 

So what's the summary of all this.... SPAM/SPIM/SPIT is here to stay. The goal is to move it from today's ridiculous email levels to a level more like that of advertising you get with the paper mail. Sender identity is key for making work the bulk of our communications, which are with people we regularly communicate with. When we do want to accept messages from people we have not communicated with before, we need something else. Reputation services of various types combined with identity are very appealing. Things like computation puzzles, Turing tests, and payments can help raise the cost of SPAM to a level at which there is enough value to the average receiver to make it bearable. 

Many of the ideas here come from conversations with many people, but certainly Eric Rescorla, Jonathan Rosenberg, Rohan Mahy, and Jon Peterson contributed ideas. 


Terminology .....

SPAM  - Uh, I'm sure you know it when you see it. Seriously many of the definitions of it are pretty poor but some of its characteristics are: it is communications you do not want, which usually go to many people and have very low value for most recipients. Some people add the notion that the recipient doesn't consent to receiving the communication, but I find this idea misleading: the only reason we have SPAM at all is that we want to receive communications we have not consented to. 

SPIM  - spam over IM 

SPIT  - spam over internet telephony