Petmail Design

Introduction

Petmail is an anti-spam SMTP replacement. It is a mail system that helps people communicate while reducing the impact of machine-generated junk mail. It also aims to improve privacy, ease address mobility, and reduce the costs involved in providing mail services.

This document describes the basic design of the Petmail system.

For more information, please visit the Petmail home page at http://petmail.lothar.com .

Spam: What is the problem?

The basic problem with spam is that it consumes your time against your permission. We each get about 2.5e9 seconds on this planet (about 80 years, more commonly known as one metric lifetime), and it is annoying beyond description to have those seconds wasted by strangers who have no interest in actual communication. Simply scanning the start of the message to see if it is interesting can take several seconds. My personal spam rate is up to about 300 per day, which (if I didn't have SpamAssassin to help) would take nearly an hour to deal with. Anything that consumes my time without my permission is a problem.

On the other hand, we enjoy spending time on friends, and on strangers who are just friends we haven't met yet. It is easy to argue that free access to your inbox by all people is the very definition of free speech. Many of the most obvious approaches to limiting spam (systems which try to limit that access to people who are willing to use some trusted ISP's mail system, or do not live in a dialup-blacklisted IP ghetto, or are unwilling to pay a penny per message) all have the potential to threaten that access. The great thing about using computers in communication is that they can reduce the costs of humans talking to each other, rather than put up obstacles.

On the surface, these two goals appear to be at odds. Certainly many of the current anti-spam systems treat it as such. Are we forced to pick one or the other?

The answer comes by noticing that we used the term people as those entities who should have access to our mailbox. People, not computers.

Spammers Are Not People

Cockroach jokes aside, the real problem with spammers is that they aren't really just people. Most spam outfits consist of a person or two with a bunch of fast, well-connected computers. If we could remove that advantage they'd be much easier to deal with.

There is a social equivalent to aim for here. Imagine a stranger at a party coming up to meet you, or a person calling you on the phone. They have to put their own time into consuming some of yours.. it is not easy to get your attention at a party, and the phone call consumes as much of their energy as it does yours. Sometimes we like the way the encounter turns out, and we're glad that we let them use some of our time. Sometimes we don't. The pest at the coffee shop who won't leave you alone despite your indications that you don't want to be bothered is annoying, but you know that eventually they will give up and go away, because they're wasting their own time too.

Telemarketing became far more obnoxious when it transformed from phone-calls-from-strangers into fully automated voicemail-delivering robots. Even the telemarketing system that uses live operators, but puts you on hold for a few seconds first to try to verify that a real human has picked up the phone, indicates the value they place on their time as opposed to yours. Likewise, when spam consisted of a few off-topic postings by stubborn interlopers in a popular newsgroup, it was far easier to deal with than the system-crushing load that email spam represents today. In those times, newsgroups and mailing lists were the only sensible venues for unsolicited commercial messages: sending them to individuals simply could not ever get enough of a response to make up for the time spent sending them.

The Solution

So the first step towards a solution is to find ways to make the social aspect of email look more like traditional human communications. The new standard is thus:

To consume some of my time without explicit permission, you must be willing to give up some of your own.

Human time, not machine-augmented-human time. This means we need a way to determine human-ness without consuming our own time, which means CAPTCHA. We use CAPTCHA tests to rate-limit new senders to human speeds, enforcing this social standard. Each recipient gets to decide just how much their time is worth, choosing different CAPTCHA challenges to suit their mood.

The Problem with The Solution

Obviously it would be annoying to require our friends to spend a few seconds of human time for each message they send to us. In the real world, we accomodate our friends more than strangers: we give them more intimate contact information (like home phone numbers), and are willing to tolerate inanities that would make us close the door on a traveling salesman.

And yet, it would be nice to be able to apply some kinds of policies to even our friends' messages. I have only a few friends from whom I would accept a phone call at 3am, and I prefer that nobody mail me HTML or MSWord attachments. So this suggests that it would be nice to be able to identify the sender of any given message, and apply different policies to each (including rate limits and CAPTCHA requirements).

These policies need to be known up front, so the sender is not surprised when their message is rejected. (I think the big resistance to current Challenge/Response systems, apart from spoofed sender addresses, is this delayed-reaction surprise: hours after I pushed Send and it looked like everything was ok, something went wrong and now I have to do more work). Any violations should be flagged by the senders own mail client, giving them a chance to fix the problem (if possible) right away. The policies must be consistently enforced, so there is no incentive to just send anyway and hope it gets accepted.

Finally, spammers are evil, and will do anything they can to get their messages accepted. They will spoof sender addresses to take advantage of accepting policies. Those one million email addresses CDs would simply turn into one million address-plus-trusted-sender-address CDs. To fix this, we need cryptography. Only messages with a valid signature are eligible to take advantage of per-sender policies.

Other human communication patterns to adopt

Apart from the my-time-for-yours pattern, what are other ways that humans communicate in the real world that we might carry over into a new mail system?

• Reciprocity: most communication is bidirectional, and it is considered rude to talk to someone without giving them the ability to talk back. Except for pre-arranged situations like lectures and speeches, sending a message to someone should automatically give them permission to respond.
• Introduction: transitive friend-of-a-friend relationships are likely to be worthwhile, at least more likely than ones with random strangers. If my friend introduces me to their friends, it should be easy for me to communicate with them and vice versa. This automatic granting of permission will depend upon the trust relationships: I don't trust all of my friends as introducers, and there are people who I would not introduce to everybody.

Petmail is designed to enable these communication patterns with no overhead relative to traditional email: no CAPTCHA challenges to pass.

Other problems to solve

The system we've described so far requires digital signatures, published recipient policies, and something to enforce those policies on both the sending and receiving ends. This involves, at the very least, replacing the mail clients at each end. While we're developing the tools to implement these things, what other common email problems could we solve?

• Privacy: Encrypt everything we can. Do not reveal anything that the sender does not care to reveal.
• Authentication: The client program should verify the sender, as much as is reasonable. This means affirming that two messages are from the same source. It does not include making any claims about the real-world identity of that source.
• Address Mobility: We should decouple identity from addressability, and from routability. Make it easier for people to change their email provider, reducing lock-in and improving competition. People should not be defined by their email addresses.
• Reliability: The end-to-end argument, when applied to email, suggests that messages should be acknowledged, and retransmitted if an ack is not received in a reasonable time. SMTP bounce messages are usually unparseable, and thus effectively out-of-band, sent to a human in response to something sent by a computer. The new system should handle delivery status messages without human involvement.

Petmail has features to improve all these aspects of mail delivery.

Petmail Architecture

This section describes the architecture of the Petmail system. It does not go into detail about the protocols used to exchange data, but you should be able to get a fair idea about what kind of messages are necessary from the description here.

The Petmail Agent

Each user has an Agent which communicates with the rest of the world on their behalf. This Agent enforces the user's policies, and implements the Petmail protocols. Different users' Agents communicate with each other directly. Each Agent accepts commands from its' user, and occasionally hands an email message up to them. The Agent program may run on the user's local computer, or it might run as part of a remote webmail system.

[TODO: picture goes here]

The Petmail Agent should eventually be incorporated into the user's MUA (Mail User Agent), but during development it can be made to run as a proxy, which sits between an existing MUA and the outside world. In this position it appears as an SMTP and POP/IMAP server to the MUA. Inbound messages from other Agents are consumed by the Petmail Agent. When those messages cause an email to be made available to the user, the Petmail Agent adds a new message to the list of available messages which can be retrieved by the MUA.

When the MUA is implemented as a webmail service, the Petmail Agent can be incorporated into the same program that provides the web service.

Recipients and IDRecords

Each recipient is known as an Identity, and is described by an Identity Record, or IDRecord for short. The Identity is a destination of email messages. Each human can have multiple Identities, each with separate names, keys, and permissions.

IDRecords are signed binary blobs about 1kb in size, which also be exchanged in an ascii-armored form like the following sample:

-----BEGIN PETMAIL IDRECORD-----

V3l4clpYbHBaRGczTXpFMk5qazFNaXdJZ0FxQ1pHbGpkR2x2Ym1GeWVRS0FDWUpoWkdSeVpYTnpa
WE1DZ0FTQ2JHbHpkQTJDWVd4cApZMlZBWm05dkxtTnZiUUtBQ29Kd1pYSnRhWE56YVc5dUFZQUVn
azV2Ym1VQ2dBcUNkSEpoYm5Od2IzSjBjd09BQklKc2FYTjBDNEpFCmRXMXRlVHBoYkdsalpReUNS
SFZ0YlhrNllXeHBZMlV5QW9BSGdtVjRjR2x5WlhOUGNpc0JCSUVDZ0FhQ2NIVmlhMlY1RDRKd2RX
SnIKWlhrNE56TXhOalk1TlRJQ2dBS0NTVVFPZ210bGVXbGtPRGN6TVRZMk9UVXlBb0FFZ201aGJX
VUZnbUZzYVdObFhRPT0K
-----END PETMAIL IDRECORD-----

The Identity Record contains the following components:

• the public key
• identifying information
• new-correspondent policy
• transport information
• extension records

Public Keys

Petmail uses standard GnuPG public keys, and simply forks off gpg for all cryptographic operations. The public key contained in the IDRecord is used for both signing and encryption. This key is not required to be signed by anyone. The key's fingerprint is used as an ID Number to uniquely identify the recipient, which can be used anywhere the protocol requires a reference to a known Identity. When one Agent needs to describe a new Identity to someone else, it will just include a full copy of the IDRecord.

Names

The Identity Record can include a set of names used to describe the recipient who uses the Identity. Those names can include anything the recipient desires: it could be empty, it could be a pseudonym, or it could even be real contact information (name, organization, job title, phone number, etc). The recipient has complete control over how they describe themselves to others.

The name information in the IDRecord is used to help the holder of that record figure out what they have and who it represents. It can also be used to help search engines (see below) locate an IDRecord which match a particular query.

The name information also includes a list of addresses, described in detail below, which have the same properties as regular SMTP email addresses, and serve as memorable search keys to help humans locate IDRecords for people they encounter.

Generic Permission

The recipient's policy for new senders is expressed in a record called the Generic Permission Record. This specifies a limit on the message size and content-type (such as insisting on only text/plain messages), but also specifies a set of Ticket Servers (described below) which will implement their desired CAPTCHA challenges.

All senders who do have not been granted more specific Permission must use this Generic Permission.

Transport Record

This portion of the IDRecord gives a list of ways to get a message to the recipient's agent. There may be multiple ways to deliver the inter-Agent message, each with different properties: the only requirement is that the message is queued if the recipient's Agent is not immediately available. Most people will probably use the encapsulate-in-SMTP transport, which wraps the encrypted Petmail message in a regular SMTP message and mails it to the other Agent.

Recipients who wish to prevent others from determining their location can specify a Transport that instructs the sender to post the message to a newsgroup like alt.anonymous.messages, or point to a Transport Server (described below) which can hand out Type3 SURBs to get the message to its destination.

The Jabber protocol is also a distinct possibility.

Identity Extensions

The ID Record is also a useful place for Agent plugins to advertise their capabilities. Petmail is designed to be modular, and users can install new components that add additional features. These components can add new nodes to the ID Record so that similar components in other user's Agents will recognize them. Those components can then exchange additional data (inside the same Petmail message that carries email between the users) to accomplish whatever snazzy new feature they provide.

Record Expiration

IDRecords have a validity date, just like DNS records do. The goal is to minimize both queries (by allowing Agents to cache the record for a certain period of time) and the confusion that occurs when information changes (by limiting the time for which they can be cached).

Tracking ID Records: the Address Book

The IDRecord fully describes a recipient. Once your Agent has one, you know how to send a message to them. That knowledge includes both the Permission (the steps you must take to make sure your message is accepted), and the routing (the mechanics of getting the message to their Agent).

ID Records are kept in an Address Book, indexed by their unique IDNumber but displayed and sorted with a locally-defined Pet Name, described in more detail below. Each local Identity has a separate address book. In addition to the IDRecord, each Address Book Entry also contains a record of whatever inbound Permission you have granted to them, and a copy of whatever outbound Permission they may have granted to you. When you send that Identity a message, you must conform to the restrictions they have imposed upon you. Those restrictions will be much more lenient than the Generic Permission used by strangers: in general your correspondents will not require you to prove your humanity with each message.

The Specific Permission you grant to known senders can also include a rate limit (currently expressed as the number of seconds that must elapse between sequential messages). As part of an online purchase, you might want to grant permission to the seller to send you mail, but only when it relates to the transaction you've just committed. Giving them permission to send one message per day is a way to prevent abuse while still granting some limited communication.

Agent plugins can also keep per-correspondent state in the Address Book Entry.

Obtaining ID Records

So, given that the ID Record has replaced the email address as the piece of information you need to contact somebody, how do you go about obtaining one? More importantly, how do you obtain the IDRecord for a particular known recipient that you want to communicate with?

• IDRecords are automatically included in messages to new recipients (unless disabled, when sending purely anonymously). Any time someone writes to you, you will have the information necessary to write back to them.
• IDRecords of third parties can be included in messages sent to you by a common correspondent. When you tell your friends about your other friends, they get the data they need to communicate directly.
• IDRecords can be pasted into other forms of media (web pages, news messages, etc), just like PGP keys.
• Address Servers (described below) can help you search for an IDRecord.

Names: a brief interlude

When it comes to person-to-person messaging systems, there are roughly three different namespaces to choose from, each with different properties. Two papers describe the properties of these namespaces in great detail: one by Zooko, and a second by Mark Miller on the E Language web site.

The short version is this:

Global, Secure, Memorable: pick two

The ID Record is (to use the PNML paper's terminology) the Key, a globally-unique string that unambiguously refers to a specific Identity, which is not subject to the whims of any centralized authority (as a DNS name would be). It is not, however, easy to memorize, and is unlikely to be used by humans to refer to other humans.

The Address Book Entry has a local name selected by whichever person added it to their Address Book (like Mom or Bill at Work): this is the Pet Name. It is easy to memorize, and is not dependent upon any external authority, but suffers from the lack of global uniqueness: you can't just do a web search for my friend Bob and hope to find your friend Bob instead of somebody else's.

The IDRecord has a list of addresses, which serve as the PNML paper's Nicknames. These look like regular email addresses. They have the properties of being globally unique, and easy to remember (and print on business cards), but suffer from being tied to a centralized authority. You can't just make up anything you like: you have to have a namespace delegated to you by the owner of the next branch up the hierarchy. Eventually you get to a root (ICANN/VeriSign). Each step of the hierarchy has an incentive to extract as much value as they can out of the control they wield over part of the namespace.

These addresses, because they are hierarchical, are also suitable as keys for an efficient/scalable distributed lookup (just like DNS names). Humans can take a short string from a business card or other citation and do a search to get the corresponding ID Record.

IDNumbers, on the other hand, are suitable for big-central-repository searches (like PGP keyids in the existing PGP keyservers), or for looking up in distributed hash tables (DHTs). If you know the ID Number, you can use such a system to get the ID Record, but only if you already know the ID Number. Other, higher-effort search techniques (which are being developed for pretty much every distributed data project in existence) are needed to use such a system to locate records based upon their contents.

Address Servers

Address Servers convert the short human-memorizable address strings into IDRecords. These strings may as well look just like email addresses, with a user@host format. When asked to send a message via such a string, the Petmail Agent will use the host portion to locate an Address Server, and ask it for the IDRecord corresponding to user.

The Address Server is a service. Everybody wants to have an unambiguous name that is cool, short, easy to remember, and relatively stable over the long-term. This is a service that may be worth paying for, either with money or with attention (to advertisements, another way of converting some of your 2.5e9 seconds into payment). It may also be a service that organizations provide for their members, as most companies do when they give @example.com addresses to their employees.

Running an Address Server is less effort and less expensive than actually providing an SMTP mailbox or even a forwarding service. The server doesn't have to store mail or handle the bandwidth requirements of sending/receiving message bodies. It only has to store a 1kb IDRecord for each name and provide it upon request, and have some additional protocol support for keeping those records up to date. This is roughly the same scale as running an organization's LDAP server.

Users can change addresses whenever they like without interrupting their established correspondences (as their recipients already have their IDRecord, and don't need the address to reach the Identity). Users can have multiple addresses. If you have some other way to convey your ID Record to the sender, you don't even need an address.

All this serves to create a better market for Address Servers, as the operating expenses are much lower, and the providers are competing based upon just the names (and long-term stability) they can provide instead of the size of their mail spool or the speed of their network connection. Existing mail providers can offer Address Service in addition to the other services Petmail uses, but they don't have to.

[TODO: picture: addresses point to IDRecord]

URLs can also be used as Addresses, by putting a (machine-traversable) link to the IDRecord in the page served by the URL. This is vaguely similar to the OpenID identity system, and allows the user who has control over the web space to publish their own IDRecord. This approach still needs some mechanism to allow the Agent to update the IDRecord periodically, because IDRecords will become stale after their validity period has ended. The Agent could easily use FTP, scp, or WebDAV to update the file on the server each time the IDRecord has changed.

Ticket Servers

Ticket Servers are the machines which implement CAPTCHA challenges. The Ticket Server produces signed Tickets, which are a statement that some given sender has passed some challenge. This Ticket is labeled with the Ticket Server's URL or other identifying string, and then included in a Petmail message to make it eligible for acceptance by a given recipient.

Different Ticket Servers can assert different things, filling a varity of points along the reliability/annoyingness spectrum. A given TS can use multiple types of challenges to provide for users who prefer or require specific visual, audible, or other kinds of tests. Recipients subscribe to the Ticket Servers that implement whatever level of challenge they wish to impose upon their new correspondents. The most likely challenge being asserted is that a human has spent some amount of effort proving that they are, in fact, human (i.e. some kind of CAPTCHA), but servers could be set up to assert all sorts of things: IQ tests, hash cash spending, membership in some organization, reputation, or even the spending actual money. If you want to restrict your mailbox to people who are willing to donate $5 to your favorite charity first, that's your perogative.

The recipient subscribes to a Ticket Server by publishing its URL in their IDRecord, in the Generic Permission section, and contacting the TS to download its public key (needed to verify the Tickets it generates). Prospective senders will see the list of TS URLs in that record and pick the one that best suits their users' preferences. The sending Agent will have their user complete the challenge, retrieve the Ticket, and include it in the message.

Each Ticket is single-use: a unique ticket ID (verified by the recipient) prevents reuse, and a loose timestamp is used to reduce the size of the history that must be kept. Tickets are bound to the recipient by a committed hash of their IDNumber, to prevent a single ticket from being used for multiple messages to different senders. Tickets may also (optionally) be bound to the sender with the same scheme, this is up to the sender (who might not use this option if they wished to be completely anonymous).

Ticket Server: the Service

The TS represents a valuable service, one that may be worth paying for. Distinguishing computers from humans is a critical piece of Petmail, as it is the only way to enforce the your time for my time fairness principle and rate-limit unsolicited messages down to a manageable (human-initiated) level. Recipients can always let in all messages and make the determination themselves, but that consumes expensive human time, part of those 2.5e9 seconds per lifetime. Recipients are transferring that effort to something else, and that is a service, with some value.

The Ticket Server may be run free-of-charge, or it can seek payment for its services in the form of money or attention (advertising). TSs which use a subscription model will require that their tickets be bound to known recipient IDs, so they can refuse to issue tickets for non-subscribers. Servers which do not use this model can issue tickets for blind-committed recipients (where the TS issues a Ticket that includes a hash of the recipient ID Number and a random string, and the sender provides both the Ticket and the string to the recipient). This mode improves privacy by preventing an observer from learning which recipient the sender is obtaining a Ticket for.

Each recipient can choose which set of Ticket Servers they will accept Tickets from, and can change that list at any time. Ticket Servers will publish the goals and policies of their different offerings (at different URLs), and can charge differently for each service. This creates a market for the TS service, as the TSs have an incentive to provide a good service at an acceptable price, and the users are free to change TSs at will.

The CAPTCHA Arms Race

Delegating out the CAPTCHA service is especially important because of the volatile nature of the field. OCR algorithms get better each year, speech recognition improves all the time, and AI research is continually seeking to create systems which can pass the original Turing Test. Over time, various CAPTCHA methods will be broken, and new ones will be created. Each method will make a new tradeoff between annoyingness, defeatability, accessibility, and implementation cost. CAPTCHA is used because it does not require expensive human time to validate: if recipients found the service worth the price, the original Turing Test (a human at the other end of a teletype, deciding if you seemed human or not) could even be used as a Ticket Server's challenge mechanism, requiring a paid human operator but very unlikely to be tricked.

Ticket Servers will be inclined to develop new verification mechanisms, because if their scheme is broken by the spammers (who might, for example, deploy an OCR system to pass the challenges, receive Tickets, and send spam), they will lose subscribers to servers who provide better CAPTCHA technology. Better techniques may cost more to develop or deploy, but if it provides a better service, then recipients may be willing to pay a higher price. This should create a competitive market for human-verification services.

By making a separate party responsible for the CAPTCHA mechanism, Petmail seeks to avoid being locked into a single (eventually defeatable) technology, and to create a market for the development of new verification techniques.

Message Transport

After all the encryption and signing and Ticket work, the sender's Agent winds up with a message (a simple binary blob of data) that must be delivered to the recipient's Agent. The requirement is that the message get to the other Agent in a timely fashion, and with reasonable level of reliability. Any means can be used to get it there, as long as it works.

The recipient specifies in what ways they are capable of receiving messages by publishing a list of Transports in their IDRecord. Each Transport is of a given type, and the Agent will simply use whatever Transport seems most likely to work. If one Transport fails to get the message through after a reasonable delay, another is attempted.

Basic Transports

The simplest type of Transport is a direct TCP connection with some well-known protocol, but this only works for actual Internet participants, who represent a smaller fraction of the networked nodes each year, as more and more computers are stuck behind NAT boxes, or simply taken offline for significant periods of time (even -- horrors! -- turned off at night).

Some form of queueing is convenient, and the existing SMTP network is an obvious resource. When a recipient publishes an SMTP Transport, they are stating that they are capable of receiving messages sent to a given SMTP email address. Senders who choose to use this method will ASCII-armor their binary Petmail messages and send them over SMTP with a special subject line (PETMAIL MESSAGE). The recipient receives the message by polling a POP or IMAP server (configured locally), or polling some webmail service in an automated fashion. When the message is seen, it is de-encapsulated, decrypted, the signature is verified, and processing proceeds as normal.

The Jabber system can provide similar message routing and queueing facilities, and (with some more research) could probably be used in a similar fashion.

Transport service is probably the most resource-intensive component of current email systems: storage space is required to hold the queued messages, and bandwidth is required on both the incoming and the outgoing sides. In Petmail, this service is decoupled from the Addressing and Permission services. In particular, recipients can change their Transport mechanism without changing any other aspect of their Identity. Organizations may provide queueing for their members, and email service is an assumed feature of nearly every ISP subscription in the world. There are probably thousands of paid email services available on the net, and scores of free (advertising-supported) providers. Any of these (even multiple ones) can be used to receive SMTP-encapsulated Petmail messages.

Remailer Transports

While the Petmail ID Record carries only as much identifying information (names) as the recipient wishes to publish, the act of getting messages to and from their Agent can reveal more than they would care to divulge. Transports which use direct TCP will allow the other end to determine the user's IP address, which can eventually be turned into an account name, an identity, or even a physical location. Transports which use SMTP involve a direct TCP hop to an MTA which probably keeps logs, and places Received: headers in the message that will be visible to anyone along the message's path.

Petmail is intended to be capable of using Type III remailer networks, which are currently under development by the Mixminion project. The Petmail Agent of a sender who wishes to conceal their location can send SMTP-encapsulated messages through the remailer network by spawning the mixminion program, which will wrap the message in layers of encryption and send it on a roundabout path through multiple remailer hops. Mixminion sending is only used if the user marks the Identity as secure, for three reasons: it requires an external program (mixminion) be installed, remailer paths are less reliable (due to the variety of servers involved, none of which trust each other), and remailer paths have significant latency, somewhere on the order of one to ten hours (and highly variable).

SURBs

The Type III remailer network has the interesting feature of providing SURBs: Single Use Response Blocks, which provide encrypted routing information that can be used to get a chunk of data (about 28kb) to an untraceable destination. An anonymous user can hand one of these SURBs to a correspondent (through an untraceable channel, of course), and the recipient can use the SURB to get a response back to the original sender, without ever being able to determine anything about the sender's location. These SURBs expire after a pre-determined time (usually 7 days), and can only be used once.

The Petmail Agent is in a unique position to use these SURBs to maintain pseudonymous communication with other Agents. It can create SURBs as necessary to make sure any known correspondent has a reasonable supply, re-stocking them when it determines that their supply is running low (either because they've used them all, or because the SURBs have expired). Two anonymous users can maintain a communication path (once it is established) by supplying each other with SURBs: in this case neither user can determine anything about the other except that each message is signed by the same entity.

Contacting Pseudonymous Users

Establishing communication with an otherwise anonymous user is tricky. The recipient can use secure means to publish their ID Record, giving the rest of the world a way to locate their contact information through whatever pseudonym they choose. However, once the prospective Sender has their hands on a copy of the ID Record, the question remains of what kind of Transport record can be used to get the first message to the pseudonymous recipient. We could create a SURB Transport and publish that in the ID Record, but it could only be used once, and only within the lifetime of the SURB (which is usually 7 days), whereas the ID Record is intended to remain stable over a span of months.

In the remailer world, this problem is solved with the use of a nymserver, which provides a publically-visible address for a pseudonymous user. The user sends special commands (over an untraceable channel) to the nymserver to create the account (the nym) and provide it with the means of returning messages (in the case of Type III nymservers, this means keeping it stocked with a supply of SURBs). When a message is sent to the nym (over regular, traceable SMTP), the nymserver uses one of the SURBs to deliver it to the (hidden) user living behind that nym. The user is responsible for keeping the nymserver stocked with SURBs, to make sure they do not lose any messages. If the nymserver ever runs dry, messages may be queued until the user provides it with the means to resume delivery.

The Petmail Agent can be used to feed the nymserver, but since the sending Petmail agent is doing ID Record lookups anyway, we can improve efficiency by having the intermediary only serve SURBs instead of asking that it handle message traffic as well. To this end we can define a Transport Server, which provides SURBs for given Identities, and a Transport Record type which says go ask the Transport Server at X for a new Transport Record.

The Agent can contact this server (over a secure channel) to create an account and maintain their SURB supply. The Transport Server can maintain two separate queues of SURBs, one for external callers and a second (smaller) supply for sending status messages to the Agent. The last SURB is kept in reserve to ask for more SURBs. The SURB supply does not need to be particularly large, as it is only depleted by new senders. Once the sender contacts the pseudonymous recipient, their Agents can exchange SURBs directly and the Transport Server is no longer involved.

The Transport Server can also require Tickets to rate-limit the SURB requests, to prevent a DoS attack in which the attacker seeks to deplete the TS's SURB supply faster than it can be replenished, thus preventing other new senders from establishing contact with the recipient.

Being Anonymous

In Petmail, anonymous strictly means nobody knows who you are, and is a stronger claim than pseudonymity. Recipients of anonymous messages have no information about the sender, not even enough to connect two anonymous messages to the same sender. Anonymous messages cannot be replied to.

Unlike several other anti-spam systems being developed today, Petmail does not place any restrictions upon anonymous messages. It does, however, allow recipients to require that messages from anonymous senders meet the same conditions as ones from non-anonymous senders: they must all conform to the policy as published in the Generic Permission section of the recipient's ID Record. Anonymous senders are obviously never eligible for Specific Permission, but as long as they include the right Tickets, their messages will be accepted.

Users can send anonymous messages by simply settng their From field to -anonymous-. This tells the Agent to do several things:

• Don't include an IDRecord in the message, since we aren't claiming the message is from any particular Identity.
• Don't sign the message, for the same reason.
• Send the message through an untraceable channel (if possible).
• Don't automatically grant return permission to the recipient, since they won't know how to get back to us anyway.

Maintaining Pseudonymity

Being anonymous is hard work. There are plenty of ways to accidentally reveal your location or identity. Each contact you have with the outside world must either be untraceable or indistinguishable from normal traffic. This requires that all Petmail servers be reachable through untraceable means. Calling Bob from a payphone (with a disguised voice) is a good start, but fails badly if you had to ask his best friend for the phone number. Likewise it is of dubious utility for Alice to use untraceable remailer chains to get a message to Bob if she must first make a public query for his IDRecord.

The design to accomplish this is still in progress, but the general idea is that Petmail services can be described by ID Records themselves, with special flags to indicate that they represent services instead of human recipients. By offering an SMTP-encapsulated Transport in this ID Record, Agents which wish to contact them can use untraceable Type III means to send their query. The query will include a SURB so the server can return the response.

There are other, more subtle attacks, which seek to partition a given pseudonym into a set of likely identities, or to establish a relationship between two different pseudonyms. These attacks tend to be applied over a long period of time, and are tricky to defend against when applied by a resourceful attacker. Any variation in publically-visible data (client versions, typical protocol behavior, implementation bugs) can become an identifying fingerprint which makes one user different from the others, which can help advance a partitioning attack.

These attacks are somewhat mitigated by hiding as much information from the attacker as possible, which is why all Petmail messages are encrypted by default.

Reliability

The end-to-end argument encourages network systems to make the middle of the network as simple as possible, and push decisions out to the edges where they can be made with more information. When applied to email, this suggests that the receiving Agent should acknowledge receipt to the sending Agent. We can follow the model of TCP and have the sending Agent retransmit a copy of the message if it has not been received in a timely fashion.

Petmail provides certain features to support this:

• Message IDs: each message has a unique ID number. This prevents replay attacks, but also serves to remove the possibility that retransmissions are misinterpreted as brand-new messages. Petmail messages are thus idempotent.
• Published Acknowledgement Policy: each Agent, in the IDRecord, publishes whether it does or does not send receipts. Some users (particularly those behind a remailer) may not want to provide any indication that a message was received: by publishing this fact the sender will know to not expect an ack. Likewise, each message indicates whether an acknowledgement is desired, so that senders (including mailing lists) can choose to avoid holding a copy of the outbound message for an extended period of time.

Individual Transport types may provide error indications (for instance SMTP-encapsulated messages can be sent with unique subject lines or envelope-from addresses to improve the chance that a bounce message can be correlated with a sent message), but with end-to-end acknowledgement these NAKS are not required. They only serve to speed up the retransmission process.

Petmail Messages

Petmail messages, as exchanged between Agents, are signed/encrypted extensible serialized tree structures. The top-level nodes include things like the IDRecord of the sender, the ID Number of the recipient, query requests, and rfc822 email nodes. These email nodes carry the actual contents of the user's email message, along with any Tickets that are required.

The serialization scheme is not yet finalized. The current implementation uses Twisted's native Jelly system, which is based upon s-expressions. Any serialization scheme is required to handle trees of objects of the following types: binary strings, 32-bit integers, variable-length lists, and dictionaries which map ASCII-string keys to arbitrary object values. This set of data types has been restricted to retain the possibility of using an XML format for the serialized data, but it is not yet clear what advantage such a scheme might offer.

Agent plugins can add nodes to outbound messages, using node names that do not conflict with existing Petmail node names. These nodes can carry state between matching plugins in different users' Agents, allowing new functionality to piggyback upon the same delivery path used by all other Petmail messages. For example, SURB restocking will be implemented using these extension nodes.

The receipt of an inter-Agent messages does not necessarily cause email to be delivered to the user. Likewise, Agents can send messages to each other independently of their users. The Agents communicate with each other on one level, supporting inter-user communication on a higher level, just like TCP handles the low-level details of maintaining a reliable byte pipe on behalf of a higher-level application protocol.

For example, each time the Identity Record is changed, a variety of recipients need to find out about the new contents. The Agent will send (signed) IDRecord updates to all known correspondents, whose Agents will update their Address Book Entries without involving the user.

Common Patterns

To accomplish the goals set forth earlier, Petmail uses additional message nodes and inter-Agent queries to minimize overhead (user effort) in traditional real-world human communication patterns.

Return Permission

In the real world, when you speak to someone, you are generally extending them an invitation to speak back. This is why we say we are talking with someone instead of talking at them. Petmail is all about making email more like human conversation.

With additional message nodes, Reciprocity is easy to implement. Part of the process of sending mail to a new recipient is the retrieval of their ID Record, which contains their public key. Petmail will, by default, grant specific return permission to anyone you send email to. When you hit Send, the Agent notices that the recipient's Address Book Entry has a Permission record, and includes a copy in a special yourPermission node. This node is delivered in the same message that carries your email. Upon receipt, in addition to handling the email node, the receiving Agent sees the yourPermission node and updates their own Entry.

This permission-grant can be disabled for specific senders by setting a flag in their Address Book Entry, or disabled altogether on a per-Identity basis. Individual parameters of the Permission thus granted can be changed at any time, and the Agent will send an update message to notify the remote user's Agent of the change This update message can be sent without an accompanying email message, and is completely consumed by the recipient's Agent.

Introductions

Petmail is designed to make typical communication patterns as natural and efficient as possible. One drawback of typical Challenge/Response systems is that they do not take advantage of possible transitive relationships between the prospective sender and their intended recipient.

Think about the names in your own email address book. How did they get there? I believe most of them can be put into one of the following categories:

1. People who found you: someone found your email address through some published form, decided they wanted to strike up a conversation with you, and sent you mail.
2. People that you found: you found someone's email address through some published form, decided you wanted to strike up a conversation with them, so you sent them mail.
3. People that your friends have found: your friend (someone already in your address book) tells you about one of their friends, or they tell one of their friends about you.

The first two cases are handled by Return Permission. The third is in the realm of Introductions.

In Petmail, when Alice (the Sender) wants to tell Bob (the Recipient) about her friend Carol (the Reference), Alice's Agent adds a special reference node to the message. This action can be explicit (i.e. a Add A Reference button), or implicit (the Agent simply scans the message body and Cc: headers for things that look like email addresses). Bob's Agent sees these Reference nodes and, if the described user is not already in his address book, offers to add them. This could take the form of a set of Add Carol to your Address Book buttons at the bottom of the message, or by turning the inline references into hyperlinks which perform the addition, etc.

When the button is pressed, the Agent knows that the Recipient (Bob) is now interested in talking with the Reference (Carol). The Petmail goal is to make this happen transparently, if at all possible. To this end, Bob's Agent will seek to obtain Specific Permission from Carol to deliver email to her.

To accomplish this, two trust relationships must be established. The first is between Alice and Bob. Alice must vouch for Bob, making the statement that Bob is worth introducing to third parties. This is controlled by a flag in same Address Book Entry where Alice can configure other aspects of her relationship with Bob (specific permission, pet name, etc). Bob is not directly informed about the state of this flag. Alice would vouch for Bob, but she would probably not vouch for the Identity that represents her bank, or a mailing list.

The second relationship is between Alice and Carol. Carol must trust Alice as an Introducer. This means that Carol is willing to grant permission to Identities that Alice vouches for. This is also controlled by a flag in the Entry, and is communicated to Alice's Agent (but not actually displayed to Alice herself) whenever it changes state. (It is actually a flag in the Specific Permission record).

When Alice's agent gets ready to send the Reference node to Bob, it checks these two flags (do I vouch for the Recipient? does the Reference trust me as an Introducer?), and if both are set, it marks the Reference node as being an Introduction. This tells Bob's agent that, if he chooses to add Carol to his address book, the agent should then try to obtain Permission from Carol.

When Bob adds Carol to his address book, his Agent sends a Permission Request message to Carol's agent, claiming Alice as the one who will vouch for him. Carol's agent checks her address book see if she trusts introductions from Alice. If so, the agent sends a Vouch-For Query to Alice's agent, which checks the vouch-for bit and returns a response. If this comes back positive, Carol's agent adds Bob to the address book and grants him Specific Permission, then sends Bob's agent a permission update. Bob's agent receives this and updates his address book to reflect the new permission he now has.

This process all happens automatically when Bob pushes the Add Carol button. If the message latency isn't too high, Bob will have permission before he even gets around to composing a message to Carol.

Permission Lineage

Every Permission record is granted for a reason: the user may have granted it directly, it may have been granted as Return Permission because of an outbound message, or it may have been extended because of an Introduction. The Agent keeps track of the reason for each such grant. Introductions can lead to a lineage of Permission: Alice introduced Carol to Bob, Carol introduces Dave to Bob, Dave introduces Eddie to Bob. Bob's address book entry for Eddie will indicate that his permission is derived from a path that leads me->Alice->Carol->Dave->Eddie. If Eddie turns out to be a spammer, then Bob can revoke his permission with a single click. If Dave turns out to have a habit of Introducing Bob to lots of spammers, but is otherwise a nice guy, Bob can disable Dave's Introducer capability without taking away his permission to send email. If Bob decides that letting Carol be an Introducer was just a bad idea in the first place, he can recursively revoke permission or introducer status for everyone whose Permision derived from her.

Mailing Lists

In Petmail, mailing lists are slightly more involved than in traditional SMTP systems. The mailing list manager software is treated as a distinct Identity. Each subscriber must grant permission to that Identity so they can receive list postings. The List Identity grants permission to the subscribers so they can send to the list.

In this situation, a specialized agent which can send the same message to large numbers of recipients is used. In this mode, per-recipient encryption can be disabled, to reduce the computational burden of re-encrypting the message hundreds of times. The message is still signed, of course, but each message only needs to be signed once.

Attacks

Spammers are continually getting more vicious in their attacks. Here is a partial list of conceivable attacks against Petmail.

Send Anyway

Spammers ignore the protocol and send messages (without Tickets) anyway. 100% of the messages are dropped by the recipient's Agents. Spoofing sender addresses and stealing IP blocks do not help the spammer's message get through.

Steal Recipients' Private Keys

Spammers unlease a new Outlook worm and program it to send back a copy of the victim's Petmail private key (and a copy of their address book). They also program it to change the victim's ID Record to no require any Tickets on inbound messages. This lets them spam the victim, and the victim's correspondents, but nobody else, and only up to the message rate limits imposed by those correspondents. If the victim was trusted as an Introducer, it may also let the spammers grant permission to new spammer Identities, which the trusting party would have to revoke with the permission lineage feature described above.

Hire People To Solve CAPTCHA Challenges

Spammers set up a sweatshop (which I will call a Turing Farm) to employ people to look at computer screens and answer CAPTCHA challenges. They get to send one message to one recipient for each challenge passed. Assuming 10 seconds per challenge, and paying roughly $5/hour, that represents $14 per thousand messages. A typical spam run of 1 million messages per day would cost $14000 per day and require 116 people working 24/7.

This would break the economic model used by most current spammers. A recent Wired article showed one spammer earning $10 for each successful sale. At that rate, $14k/1Mspam requires a 1 in 1000 success rate just to break even, whereas current spammers are managing a 1/100k or even 1/1M sucess rate.

Steal People's Time To Solve CAPTCHA Challenges

A recent slashdot article described a trick that has been floating around the ASRG list since last November, which I will call a Turing Porn Farm, in which spammers also run a porn site that is gated by CAPTCHA challenges, which are actually ripped directly from Yahoo's new-account creation page. The humans unwittingly solve the challenge on behalf of the spammers, who can therefore automate a process that was meant to be rate-limited to humans.

This is a classic man-in-the-middle attack, which cannot be solved with traditional authentication means because the CAPTCHA design is validating a human (who, as a species, are not known for being very good at doing kilobit modular exponentiation in their heads), not some computer agent which sits in front of them. The spammers can implement the entire Petmail Agent, right up to the part which displays a CAPTCHA challenge, but then send that challenge to the unwitting human, and use their response when it arrives.

It is also valid to treat this attack as simply another way of paying the workers of a Turing Farm.

This attack is still limited to one message (to one recipient) per CAPTCHA challenge, which may make the economics unfeasible (porn hosting costs money too). Ticket Servers can rate-limit requests from a single address, which may help somewhat. The CAPTCHA challenges can be marked to let the victim know what their effort is being used for.

Invent New AI Technology To Solve CAPTCHA

Spammers put millions into R+D and build a system that can pass an extended Turing Test, one that can go beyond the original boundaries (run over a teletype to remove voice synthesis and recognition from the criteria).

We solve this by granting the spammers a PhD in computer science and allowing their new sentient creations free run of a computer-controlled future. I for one welcome our new robotic overlords.

On a smaller scale, advances in OCR technology are inevitable, but so are advances in CAPTCHA technology. The Ticket Service providers have an incentive to contribute to this research. Ticket Servers can also offer more expensive (and more effective) means to rate-limit new senders, such as offering a 1-800 number with an operator that spends a minute talking to the prospective sender before granting them a ticket. Such a service will cost money, but some recipients may decide it is worth the price. CAPTCHA is used because it is cheap (to verify), not because computer-verification is a necessity.

Steal Ticket Server's Private Keys

Spammers break into trusted Ticket Servers and steal their private keys, enabling them to make their own Tickets and send spam to anyone who subscribes to that Ticket Server.

Ticket Servers are central resources run with similar security policies as professional web sites, and are therefore less likely to be compromised than a typical home computer. Once recipients notice the flood of spam arriving with Tickets from the compromised server, they will unsubscribe from that service. The Ticket Server can generate new keys, improve their site security, and try to convince the subscribers to come back.

Run Bogus Ticket Servers

Spammers run their own Ticket Servers, attempt to convince recipients that they are trustworthy, then secretly grant themselves Tickets to spam those recipients.

When recipients get too much spam on Tickets from a particular server, they will switch servers, just as they would if that server were compromised. The servers (and their operators) can establish a reputation for quality service.

Markets

As envisioned, Petmail will create a market for four distinct services. Traditional SMTP email systems bundle most of these into a single monolithic block, reducing flexibility and user mobility.

• Ticket Servers get paid for rate-limiting new senders by evaluating human-ness and expected worth (to the recipient) of an inbound message
• Address Servers get paid for the use of cool / memorable / stable addresses
• Transport Providers get paid for bandwidth and spooling storage
• Transport Servers get paid for publishing SURBs on behalf of pseudonymous users

Decoupled services are cheaper to provide than bundled ones. The organization that has plenty of bandwidth (but not a cool name) can offer a queueing services but not Addresses. The group that administers cool.org can offer name service off a small computer and a low-bandwidth connection.

Decoupling the services also improves competition by making it easier for users to change providers. Being able to switch to a faster mail server without changing your email address means that provider has a stronger incentive to provide good service: offering a cool name (which is hard to change because it has been printed on a thousand business cards) will not make up for poor service.

Other Directions

Email is just a single point in a vast communications space with many dimensions. Voice mail, live phone calls, IM, faxes, blog entries, web pages, all occupy their own niches within this space. The axes of this space are parameters like bandwidth, latency, interactivity, expectation of attentiveness (I expect you to put more attention into a face-to-face meeting or a phone call than to my voice mail), reliability, persistence (IMs tend to be ephemeral, email sticks around forever), intrusiveness, etc. The unoccupied regions of this space suggest new communication modes: email that expires if not read by a certain time (Bob, are you free for lunch today?), phone calls that go directly to a voicemail system without interrupting the recipient, IM that only gets delivered if the recipient has the time to participate in the conversation right now. People have certain expectations about where various existing modes sit in this space (calling someone is intrusive, but sending them email is not), and choose a different medium based upon what they want and need for any given message.

This has bearing on Petmail in two ways. The first is that the Permission Records should be useable for more than simply email: I should be able to grant permission to IM me just as I would grant permission to send me email. When I choose Alice's entry in my Petmail Agent, I should get a list of communication modes for which she has granted me permission, and selecting IM or VoIP should be as easy as picking the email option.

Using this unified permission scheme for IM and voice would provide a useful answer to the current concerns about spim and VoIP spam, since the content filters used for email don't work (spim is too short, and filtering voice messages is completely intractable). Many IM users now use exclusive whitelists, effectively pushing the how do you contact new people question out-of-band (send me email and maybe I'll add you to my IM whitelist). VoIP will likely go the same way once the spammers start making automated telemarketer-style calls with advertising content.

The second way in which it would be useful to have a dedicated Agent on each end is in mode negotiation: Alice wants to tell Bob something about a project they're both working on. She clicks some buttons to tell her Agent what she needs (does she need to talk to him live? in person? how long will the message be relevant?), effectively choosing a subset of the communication space described above. Bob's Agent knows what Bob is available for right now: perhaps he is in a meeting, and could look at a short message and make a brief reply, but he won't be available for real interaction for another hour. The two Agents can collaborate to decide upon a mode of communication that satifies both parties' requirements, or at least give Alice enough information to let her make better decisions (Alice needs an answer now, perhaps she should talk to someone else). In a workgroup environment, Bob's agent could know that Carol is also involved in this project, and that she may be available in ways that Bob is not. Alice's agent could then handle the details of letting her communication with someone who can answer her question.

Different modes could be made available to different people, for different reasons. I might grant certain friends the right to use an Emergency tag, but not my coworkers, which would give them the ability to interrupt me in a meeting. My coworkers would get the right to use tags associated with different work projects, which could let them communicate with me when I'm in the zone and don't want to be distracted anything outside a particular project for an hour.