MS's new antispam idea

Fri Dec 26 18:13:08 UTC 2003

In message <20031226163658.DE74E10DAD at gateway.wvi.com>, "Jeff Shultz" writes:

>
>I'm sure I've heard this one before, so it's not even a new idea...
>hope whoever came up with it originally patented it. 8-) Then again,
>maybe it was MS that I heard about the first time, and the Beeb is
>simply late to the game here. 

Yes, puzzles have been suggested before as defenses against SYN floods 
and SSL DoS attacks, and many other things as well.
>
>Has anyone calculated the increased server load, the extra storage
>needed for the now lengthened outgoing mail queue, and the extra
>bandwidth required to handle all this extra back and forth puzzle
>thing?  YahooGroups and the like would definitely be impacted. It would
>be interesting to see what protections will be built into the puzzle
>thing as well... I can see some joker setting up his server to require
>that the sending computer calculate PI to some ridiculous number of
>decimals... although that might make a good honeypot. Or, if the puzzle
>is open source (which would be a good thing), how soon before the
>spammers (or even legit MTA authors) hardcode the answers into the
>server software? I suppose there would have to be some random elements. 

The usual way this is done is to pick a puzzle that's hard to compute 
but easy to verify.  For example, the server could pick a random number,
take the top N bits, and challenge the 
client to find *any* number whose SHA1 hash has the same high-order N 
bits *and* includes some other random string as the high-order bits of
the answer.  There are no known short cuts; the only feasible strategy is
to calculate lots of SHA1 hashes for different input values.   (The 
server sends some other random number to avoid precomputation attacks.)

Bandwidth is probably not an issue; it's one extra round trip, and it's 
not very much text.  Mail sender queues are more of an issue, as is the 
load on the sender; if I were doing this, I'd make it adaptive, with a 
high cost being required for unknown senders, or those that have sent 
suspected spam.  For example, start with a 12-bit puzzle, i.e., one of 
client difficulty 4096.  For each piece of non-spam, subtract some 
small value from the difficulty.  For each piece of spam, double the 
difficulty rating for that client.  There are lots of ways to do things 
like this; it will take more than back-of-the-envelope calculcations to 
understand all the knobs, let alone what countermeasures the spammers 
will deploy.

For an introduction to schemes like this, see Stubblefield, A.., and
D. Dean, "Using Client Puzzles to Protect TLS,"  Proceedings of the
Tenth USENIX Security Symposium, Washington, DC, August 2001, available 
at http://www.csl.sri.com/users/ddean/papers/usenix01b.pdf .

>It is interesting.... as an extension it might be nice to be able to
>set up a "whitelist" of trusted servers that don't have to go through
>the computational gyrations to send you mail - that way it would,
>hopefully, eventually impact the spammers more than it would impact
>legitimate e-mail servers.
>

According to the article, that is indeed part of the scheme.

		--Steve Bellovin, http://www.research.att.com/~smb