Crypto and Spam

19 June 2004
In my last essay, I talked about fraudulent emails. With this essay, I am starting a series on how cryptography applies to fighting spam-and also, more importantly, how it doesn't. There are many problems cryptography can solve, and many that it cannot. We often see systems that have cryptography added into them fail for subtle reasons, often ones that involve the humans who have to use the system.

There are a number of potential spam solutions being discussed among technical organizations. These proposals fall into three broad categories:

• Cryptographic solutions
• Network-based solutions
• Payment solutions

I will not cover potential legal solutions. However, much of the spam problem can be solved by law enforcement; unlike many virus writers, spammers have a real-world presence that can be used to find them. The key issue in a successful law enforcement approach to spam is one of funding more than anything else.

In this first essay, I will discuss some of the issues around cryptographic systems and why they are likely to fail under an attack from criminal spammers. I'll also take a look at ways to mitigate such attacks and how new hybrid solutions such as Yahoo's DomainKeysT system may prove useful in fighting spam.

Examining the Attackers
The attackers in the spam problem are, of course, the spammers themselves. Spammers are motivated and well funded. A 2003 raid on an herbal supplement seller by the U.S. Federal Trade Commission (FTC) turned up 6,000 orders averaging just under $100 dollars per order. There is money in spam because a small percentage of the people who get it actually reply.

Spammers (as opposed to bulk mailers) are also criminal. Some of the most annoying spam violates product and trade law (there is no such thing as generic Viagra). Some of it is outright fraud, such as the Nigerian 419 ("advance fee") fraud. Other spam is a con to enable different types of theft, such as phishing, which I have already discussed.

The spammers also use network crime to send their emails. They use viruses and worms to hijack systems that can then be used to send out spam as well as compromise other systems.

Spam is not a natural phenomenon like a thunderstorm. It is sent by people who are well-paid and don't care about legalities. They adapt, counter-attack, and work diligently to continue to send out spam. Consequently, any solution must take this behavior into account. We must assume the spammers will not sit passively by and let our lightning-rod-equivalent channel them away from their goal, but will instead adapt and do whatever they can to continue spamming.

Cryptographic Solutions
Cryptographic solutions to spam fighting are based on a simple principle: If you know who sent the message, you have a much easier time in determining what is and isn't spam. Fraud messages are the most easily eliminated because it becomes easy to tell that a message claiming to come from a bank didn't.

One way to identify the sender of a particular message is by authentication. For example, attaching a digital signature to messages can authenticate them. Verifying the signature verifies the authenticity of the message.

Although conceptually simple, there must also be an infrastructure to support these digital signatures. If any spammer can simply start signing messages and have them be reliably delivered, then this isn't an effective spam-fighting solution. Therefore, there has to be a set of authorities that issue certificates to email senders, and the signatures on messages have to be verified as coming from some bona fide sender. The user's certificate thus becomes a license to send email.

The infrastructure must also contain a complaint system to provide accountability for email senders so the license of a bad actor can be revoked, if necessary. There must also be a dispute system so that someone who is unjustly accused of being a spammer can fight that accusation. There must also be a mechanism to prevent a spammer from simply getting another license and also for someone who is no longer a spammer to get a new license.

This system can be created either as an end-user authentication system, where each person who sends email holds a license to do so, or it can be set up such that every server holds a license, and the servers verify the source of the sending server.

Of the various solutions seriously being discussed, there are no pure cryptographic solutions. The closest to a cryptographic solution, Yahoo's DomainKeys system, is actually a hybrid network and cryptographic system.

I often see discussions of spam-fighting that simply assert that signing messages will make this spam thing go away, and all we have to do is to just use the existing systems. Alas, if it were really that easy, we at PGP Corporation would be would be the first to embrace that approach. Below, I'll present an attack on a cryptographic system to show why it is actually a bad idea.

Attacking Cryptographic Solutions
A spammer who attacks the email authentication system can attack it two ways. One way is a direct attack: the goal is to get licenses that permit attackers to send spam that will be authenticated as legitimate email. The second way is an indirect attack: an attack against the system itself to cause it to be ineffective or to collapse.

Here is how an attacker can mount an effective attack against the authentication system:

• First, the attacker acquires a number of legitimate licenses. Because every user or server must have a license to send email, these licenses have to be easy to get. There cannot be much of a background check required to obtain them. Spammers can get licenses as easily as anyone else.
• Next, the attacker starts writing or modifying viruses to not only take over systems, but to steal existing licenses.
• When the attacker has a supply of legitimate and illegitimate licenses, it starts the attack. The attack consists of a number of specific tactics:
  • With some of the legitimate licenses, the attacker starts sending spam. It also does so with some of the stolen licenses.
  • With some of the stolen licenses, the attacker issues complaints against both some its own spamming licenses and innocent licenses.
  • With some of the legitimate licenses, the attacker issues complaints against spamming licenses so as to make these look further like legitimate users.
  • The attacker also disputes complaints against its own licenses. It also works to rehabilitate any licenses that become invalid.

The purpose of this attack is to flood the authority with complaints and to have a combination of legitimate and illegitimate complaints against legitimate and illegitimate users. This approach increases the workload for the authorities that issue licenses and makes it as difficult as possible for them to tell legitimate users from illegitimate users and disputes from each other. Ironically, the attack is more successful if the complaint system is more draconian than liberal. The goal of the attack is to undermine confidence in the authentication system while making it more expensive for the authorities to process the customer satisfaction issues. If the attacker can make the system unprofitable and despised (or a laughing stock), then it wins. Because the success of the system requires thorough, competent, back-end support, flooding it is relatively easy to do.

The attacker can also engage in a whispering campaign against the authentication system by sending messages that are not spam per se but urban-legend horror stories about people and businesses that have had problems with the authentication system. These messages also imply the license authorities are making lots of money while providing shoddy service and can include websites, news stories, and other formats that claim, "We were better off before."

Because the authentication system will not be enabled all at once, this attack can keep the system from ever becoming effective.

Mitigating Attacks against Cryptographic Solutions
If the cryptographic authentication system is deployed to end users, it can never work. Because of the poor state of operating system security on end-user systems, it is far too easy for a small group of organized attackers to mount an attack on the system itself and too difficult for an authority to provide effective support. If the system becomes widespread enough to effectively limit spam, it is widespread enough to attack.

Mitigating the attack requires that the authorities issue a relatively few number of licenses, issue them to reasonably savvy end users, and build automatic mechanisms into the dispute system. Eliminating authorities by using a distributed system is even better.

These steps are easier to accomplish than it appears. If licenses are issued only to servers, not end users, that step satisfies the first two requirements. However, any organization that becomes an authority for a cryptographic solution should expect the business to be low-margin and to cause brand damage because they will be blamed for any difficulties in it. That is why I not only have serious doubts about a cryptographic solution but VeriSign, a natural candidate for an authority, is backing SPF, a network-based solution.

How DomainKeys Addresses These Attacks
As I mentioned above, Yahoo's DomainKeys is a hybrid system, using cryptography and networks. Here's how it works:

• A domain places in their DNS the keys they will use for signing. There can be one key for the whole domain or a number of them, including keys for subdomains.
• The sending mail server signs a message with an appropriate key as the message is sent. The signature is placed in the email headers.
• The receiving mail server verifies the signature, thus establishing its authenticity. If the signature verifies correctly, you know it was sent by the responsible server.

This system avoids the attack I described by cleverly using DNS as the authority. DNS is a fine distributed authority. Every domain runs its own DNS and any attack on the authority of the keys is nothing more than an attack on DNS itself. This setup sidesteps any liabilities the issuing authority would have because the issuing authority is the sender. Thus there is also no need for a dispute system over the keys.

There still have to be disputes over the mail itself. For example, suppose one of our users sends messages that are unequivocally spam. The recipient of the message can come back to us, the people who run the domain, and show us that one of our users sent spam and here is the digital signature to prove it.

There is only one major drawback with DomainKeys: it cannot spool messages. The sending server must hold the entire message from the end user before it can send it, and the recipient must receive the entire message before verifying its authenticity. Presently, my server could start sending your message before I receive it all. Similarly, the receiving server must accept the entire message before it can reject it.

I have thought of attacks on the system that involve sending someone very large bogus messages and forcing them to receive the entire bogus message before being able to reject it. There are countermeasures against these attacks, however, which I will discuss in my next essay.

Overall, DomainKeys can work effectively and is resistant to systemic attacks.

Summary

• Potential spam solutions fall into three categories: cryptographic, network-based, and payment solutions
• Cryptographic spam solutions depend on authenticating the sender of a message
• Attacks on cryptographic authentication systems can be mitigated by limiting deployment
• Hybrid network-based cryptographic spam solutions such as Yahoo's DomainKeys can be effective in mitigating such attacks

What about other spam solutions?
In my second essay, I will look at the pros and cons of network-based spam solutions.

Background reading
Delany, Mark, "Domain-based Email Authentication Using Public-Keys Advertised in the DNS (DomainKeys)," IETF Draft, May 2004

"DomainKeys: Proving and Protecting Email Sender Identity"

Krawetz, Dr. Neal, "Anti-Spam Solutions and Security," Part 1, February 26, 2004

Krawetz, Dr. Neal, "Anti-Spam Solutions and Security," Part 2, March 9, 2004

"Sendmail and Yahoo! Mail Collaborate to Develop and Deploy DomainKeys," February 24, 2004