The CAN-SPAM Act, signed into law yesterday by President Bush, will take effect on January 1. The Act asks the Federal Trade Commission to study whether a national do-not-spam list, akin to the much-loved do-not-call list, should be implemented. It’s an interesting question.

The crux of the problem is the danger that the do-not-spam list would become, in the hands of unscrupulous spammers, a who-to-spam list. We know that spammers pay money for lists of known-to-be-active email addresses. Surely, they would be more than happy to get such a list – and an unusually large and accurate one – from the government for free.

There are countermeasures, though. If we put some newly minted, fictitious addresses on the list, any mail sent to those addresses later must have involved misuse of the list. If we give out separate copies of the list to different spammers, we might put different fictitious addresses into each copy, so we can tell later whose copy was misused. Of course, spammers may collude and compare their copies to find the bogus addresses, so we want some of the bogus addresses to appear in multiple copies so that we have an idea of who to blame even if lists are combined. Figuring out how best to use duplicate bogus addresses for this purpose is a nice little exercise in theoretical computer science.

Some have suggested another approach, in which bulk emailers are given access to an “oracle” that will answer queries about whether a particular address is on the do-not-spam list. This could be done by providing an on-line service that answers queries, or by giving giving out cryptographic information (i.e., the cryptographic hashes of the addresses on the list) that allows address-by-address querying. In either case, the worry is that spammers will use the oracle to “purify” their address lists, by discarding addresses that aren’t on the do-not-spam list.

Another approach, perhaps ironically, is to provide a mailing service that will forward email to any recipient, except those on the do-not-spam list. Bulk emailers who used such a forwarding service would be able to send mail, via the service, to anybody who isn’t on the list, but they would have no easy way to test for membership of an arbitrary address on the list.

What’s the right answer? I don’t know. But I’m glad that we’re not rushing ahead with a list before we figure out how to do it or whether it’s a good idea in the first place.

Some have argued that we can address the spam problem by redesigning SMTP, the basic email-handling protocol used on the Net. Eric Rescorla rebuts that argument with a clear and cogent explanation of why the real problems lie elsewhere. Required reading for those who want to understand what can be done about spam.

The case for replacing SMTP (which Eric rebuts) reflects a general fallacy about the Internet. The fallacy goes like this: the Internet was not originally designed with security in mind; the Internet as designed fails to provide some desired security guarantee; therefore if we redesign the Internet we can achieve the desired guarantee. The error, of course, is in the hidden assumption that the desired guarantee is achievable at all. In the case of spam, there doesn’t seem to be a technical solution.

One of the trendy ideas these days is challenge-response (CR) anti-spam technologies. The idea is simple: incoming email is intercepted before you see it, and a “challenge” email is returned to the sender. If the sender replies to the challenge message, then the original message is forwarded on to you; otherwise it is discarded. The idea is to require some kind of human involvement in the sending of each message. Sometimes the sender has to answer some kind of puzzle that is supposed to be easy for people but hard for computers.

Whenever we analyze a security technology – and that is what CR is – we need to look not only at the immediate effect of the technology, but also at how people will adapt to it. We need to look especially at how the bad guys will adapt. Will they adjust their attack strategy to defeat the new defense? Will the new defense create new opportunities for malicious attacks? Will the technology lead to an arms race between defenders and attackers? If so, can we predict the outcome of the arms race?

CR stands up poorly to this kind of analysis. To see why, suppose that Alice sends an email to Bob, and Bob is using CR. Bob’s computer sends a challenge message back to Alice and awaits her response. This challenge message had better get through to Alice; if it doesn’t, the whole scheme breaks down. If Alice is using anti-spam technology that blocks the challenge message, then she’ll never see the challenge – her original message won’t get through to Bob, and she won’t know what went wrong.

We can fix this problem by making sure that Alice’s anti-spam technology has a loophole for challenge messages, to make sure they are never blocked. (Note that although Bob is the one using CR, it is Alice who has to create the loophole.) If CR is going to succeed, most of the Alices out there will have to open the loophole. Messages with certain “challenge-ish” attributes will be mostly immune from spam controls.

At this point, the bad guys’ response is obvious: create spam that can exploit the loophole, spam that looks like a challenge message. If they can do this, then CR will have made things worse – spam will pour in through the loophole.

We might try to solve this problem by narrowing the loophole, requiring the challenge messages to be so narrowly stylized that they cannot carry a spam. This too creates an opportunity for the spammers. If the challenges are so predictable, then the spammers will be able to develop computer programs that spot the challenges and auto-send the required responses. If they can do this, then the spammers can just add automated CR responses to their automated email-sending software, and continue to pollute our inboxes.

Given all of this, I’m skeptical of CR as a response to email. If you’re the first on your block to adopt CR, and if nobody else uses anti-spam technology, then CR might provide you some modest benefit. But it’s hard to see how CR can be widely successful in a world where most people use some kind of spam defense.

Don’t miss Declan McCullagh’s column this week, in which he offers a particularly astute view of how to address the spam problem. In a nutshell, he argues that we need to change the economic incentives for the spammers, and he discusses some practical ways to do that.

Declan McCullagh reports that his Politech server has been blacklisted by SpamCop – for the third time. Longtime readers may recall this site being wrongly blacklisted by SpamCop in its early days. The scary part is that SpamCop is apparently one of the more responsible spam blacklisters.

Amy Wohl reports being on another blacklist.

UPDATE (3pm): Seth Finkelstein thinks he has diagnosed Amy’s Wohl’s problem.