the proposal in the past has been that ISPs filter spam at ingress from their customers. the counter-argument has been that there are lots of ISPs that can't be trusted to do it. So it is much easier for ISPs to have lists of other trusted &/or untrusted ISPs that they will accept email from. It is orders of magnitude easier (and more efficient) for ISPs to do ingress filtering for SPAM and effectively ISP blacklists than it is to populate the whole consumer infrastructure. There are still some ways to slip thru the cracks with small amounts .... but it isn't the 40-80% volume of all email that is seen today. It does have an analogous downside to the individual privacy issues ... which are that the big ISPs could use blacklisting for other purposes than addressing SPAM issues. Some of the ingress filtering pushback may be similar to the early counter-arguments for packet ingress filtering related to ip-address spoofing. however, that seemed to be more a case of disparity among the router vendors in which could & could not implement ingress filtering. as majority of the router vendors achieved such capability ... the push-back significantly reduced. http://www.garlic.com/~lynn/rfcidx7.htm#2267 2267 - Network Ingress Filtering: Defeating Denial of Service Attacks which employ IP Source Address Spoofing, Ferguson P., Senie D., 1998/01/23 (10pp) (.txt=21032) (Obsoleted by 2827) there already are logs relating ingress email to originating ISP customer id. that could be made available via some sort of legal action. the only issue then is the strength of authentication that is performed on customer connection to the ISP ... rather than some sort of origin authentication for every email. At 03:40 AM 5/9/2003 +0100, Adam Back wrote:

Yes, there is some discussion of it on slashdot, including several other people who have commented similarly to anonymous that it is a pretty big privacy invasion and centralised control point problem.

The claim that you can optionally be anonymous and not use a cert, or get an anonymous cert is plainly practically bogus. You'd stand about as much chance of having your mail read as if you shared mail hub with spamford wallace -- ie 90+% of internet mail infrastructure would drop your mail on the floor on the presumption it was spam.

Plus a point I made in that thread is that it is often not in the internet user's interests to non-repudiably sign every message they send just to be able to send mail because that lends amunition to hostile recipients who from time-to-time target internet users for bullshit libel and unauthorised investment advice etc.

Companies also are I would expect somewhat sensitive to not signing everything for similar reasons as those behind their retention policies where they have policies of deleteing emails, files and shredding paper files after some period.

In addition PKIs because of the infrastructure requirements have probem complex to setup and administer. So now we've taken one hard problem (stopping spam) and added another hard problem (hierarchical PKI deployment) and somehow this is supposed to be effective at stopping spam.

In addition unless there is significant financial cost for certificates and/or signifcant and enforceable financial penalty and good identification and registration procedures enforced by the CAs it wouldn't even slow spammers who would just get a cert, spam, get revoked, get another cert and repeat.

Certificate revocation is already a weak point of PKI technology, and to reasonably stop spam before the spammer manages to send too many millions of spams with a cert, you have to revoke the cert PDQ!

And finally it all ends up being no more than an expensive implementation of blacklists (or I suppose more properly whitelists), because the CAs are maintaining lists of people who have not yet been revoked as spammers. Some click through agreement isn't going to stop spammers. Legislation or legal or financial threat is going to stop spammers either because any level of registration time identity verification that is plausibly going to be accepted by users, and this is also limited by the cost -- higher assurance is more cost which users also won't be willing to accept -- will be too easy for the spammers to fake. And email is international and laws are not.

It is pretty much an "internet drivers license" for email.

I also think that fully distributed systems such as hashcash are more suitable for a global internet service. My preferred method for deploying hashcash is as a token exempting it's sender from bayesian filtering, and any other content based or sender based filtering.

That way as an email user you have an incentive to install a hashcash plugin http://www.cypherspace.org/hashcash/ because it will ensure your mail does not get deleted by ever-more aggressive filtering and scattergun blackhole systems. The camram system http://www.camram.org/ is a variant of this.

It also more directly addresses the problem: it makes it more expensive for spammers to send the volumes of mail they need to to break even.

Adam

On Fri, May 09, 2003 at 03:50:02AM +0200, Nomen Nescio wrote:

...

Lauren Weinstein, founder of People for Internet Responsibility, has come out with a new spam solution at http://www.pfir.org/tripoli-overview.

According to this proposal, the Internet email architecture would be revamped. Each piece of mail would include a PIT, a Payload Identity Token, emphasis on Identity. This would be a token certifying that you were an Authorized Email User as judged by the authorities. Based on your PIT, the receiving email software could decide to reject your email.

It is anticipated that all Pits considered acceptable by the vast majority of all Tripoli-compliant software user would be digitally signed by one or more designated, trustworthy, third-pary authorities who would be delegated the power to certify the validity of identity and other relevant information within Pits.

In other words, here comes Verisign again.

It is anticipated that in most cases, in order for the sender of an e-mail message to become initially certified by a Pit Certification Authority (PCA), the sender would need to first formally accept Terms of Service (ToS) that may well prohibit the sending of spam, and equally importantly, would authorize the certification authority to "downgrade" the sender's authentication certification in the case of spam or other ToS violations.

Thus you have to be politically acceptable to the Powers That Be in order to receive your license to email, aka your PIT. And be careful what you say or your PIT will be downgraded.

Unfortunately he doesn't discuss various crypto protocol issues:

If the PIT is just a datum, what keeps someone from stealing your PIT and spams with it?

If the PIT is a cert on a key, what do you sign? The message? What if it gets munged in transit, as messages do? You've just lost most of your email reliability.

Or maybe you sign the current date/time? Then delayed mail is dead mail.

Or maybe you respond to a challenge and sign that? That won't work if relays are involved, because they can't sign for you.

Spam is a problem, but it's no excuse to add more centralized administrative control to the Internet. Far better to go with a decentralized solution like camram.sourceforge.net, basically a matter of looking for hashcash in the mail headers. This raises the cost to spammers without significantly impacting normal users.

--------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com

-- Anne & Lynn Wheeler http://www.garlic.com/~lynn/ Internet trivia 20th anv http://www.garlic.com/~lynn/rfcietff.htm

Currently ISPs typically "notice" when they get complaints. ISPs could do a much better job of actively noticing and limiting mail at ingress ... as opposed to waiting for somebody to complain and canceling the account. Many of the recent statements about ISPs can't limit email at ingress dynamically are similar to the comments about not being able to filter ingress packets if their origin address didn't match the ip address of the sender (as stated in the original posting) ... per the ingress packet filtering RFC referenced in the original post. My original post mentioned that the ISPs could then do their own effort of blacklisting (of other ISPs). Currently spam blacklists can be somewhat like vigilantes .... with the argument analogy that since vigilantly justice can make mistakes then there shouldn't be any highway patrol, FBI, and/or secret service. ISPs would be expected to filter on ingress of email from their own customers .... and even if the 10 top ISPs blacklisted other ISPs that didn't do a reasonable job of ingress filtering ... it could start to put a big dent in the spamming business, possibly cutting it from 40-80% of existing email down under 5-10%. It is sort of like stop signs and stop lights .... there are typically hundreds of more intersections than there are traffic enforcers .... however with sufficient leverage ... it can significantly improve the situation ... even if it can be proved that it can't, absolutely, 100% guarantee one hundred percent compliance. I didn't make any statement about ISPs attempting to identify spammers when they register the account .... the original post was only with regard to ISPs doing active email ingress filtering. My ISP recognizes and bills me extra if I'm simultaneously connected multiple times ... there is a little latitude for modem hanging, my dropping the line ... but the modem not reporting it ... and my connecting on a different modem. It also does traffic load-leveling if I really try and hit it hard. If it can bill extra for simultaneous connects and traffic load leveling, it can do both packet ingress filtering and email ingress filtering. past thread drawing the analogy that the information superhighway is something like the wild west .... w/o traffic rules, traffic signs, traffic lights, speed limits, and enforcement. start with a couple hundred people in town .... and went to millions ... and there still isn't even any rule about which side of the road people should be driving on. http://www.garlic.com/~lynn/2001m.html#30 Internet like city w/o traffic rules, traffic signs, traffic lights and traffic enforcement At 06:02 AM 5/10/2003 +0100, Adam Back wrote:

On Fri, May 09, 2003 at 10:11:52AM -0600, Anne & Lynn Wheeler wrote:

...

So it is much easier for ISPs to have lists of other trusted &/or untrusted ISPs that they will accept email from.

Any internet user needs to be able to send mail to any other internet user. Which means the default has to be open (blacklists rather than whitelists). Then you have the blackhole lists like ORBs etc, which block domains used predominantly by spammers. But the problem is spammers don't stay in one place, they buy service from ISPs and spam flat-out until the ISP notices and cancels the account. Some ISPs are more grey -- they want to make money from spammers by providing them service, and some ISPs just don't notice or respond that quickly. The ISP can't distinguish spammers from non-spammers when they receive customer orders. The blackhole people are arbitrary vigilantes by and large, so the overall effect you might argue does reduce spam, but it also results in lost mail.

My experience was I couldn't get mail from my brother who was using btinternet, one of the largest ISPs in the UK because some idiot blackholer blackholed their dynamic IPs. Not doubt there were at some time some spammers using BTinternet as with just about any other ISP. Recently I couldn't receive mail from John Gilmore, and so it goes.

So I don't see how this is a "solution", rather it is just a broken countermeasure with scatter gun fall-out of false positives for all the other people who find themselves sharing the same ISP as spammers long enough for the blackhole people to add them.

Adam

-- Anne & Lynn Wheeler http://www.garlic.com/~lynn/ Internet trivia 20th anv http://www.garlic.com/~lynn/rfcietff.htm

do you think that earthlink would automatically blacklist aol if it found incoming spam from aol? I think that earthlink would contact aol and say ... your ingress filtering doesn't seem to be working. It would only be after all attempts to understand aol's ingress filtering that earthlink might take action. again ... it is analogous to somebody hearing about traffic lights for the first time and coming up with all the reasons why people would ignore traffic lights. I would claim that the current issue isn't that spam exists (aka traffic violations), it is that there are billions of spams each day. and that this easily cuts the majority of it if the top ten start doing ingress mail filtering and that ingress mail filtering is orders of magnitude more efficient than other kinds of solutions. the blacklisting isn't for the mistakes ... it is for the ISPs that obviously aren't going to follow the traffic rules. so there are lots of kinds of tunneling. the major ISPs are already doing ingress filtering for email not coming from a recognizable customer. so tunneling actually reduces to a common vulnerability with ISPs not doing ingress email filtering (aka the tunneling issue to a ISP that isn't doing ingress email filtering is common vulnerability with a customer directly getting an email account with ISP that isn't doing ingress email filtering). So the issue comes back to ISPs that are recognized as not doing ingress email filtering. So lets say this gets something like 80 percent of the traffic violations. So the majority of the random traffic violations are now starting to be taken care of. There are 1) the corporations effectively operating as private ISPs, 2) compromised machines, 3) random anarchy. So both #2 and #3 are vulnerabilities treated just the same as a real spammer getting a real account and directly doing spam. These two vulnerabilities should be caught be ingress email filtering. Real spammers caught by ISP ingress filtering, compromised machines caught by ISP ingress filtering, and hit&run anarchist caught by ingress filtering .... all appear to be a common vulnerability caught by ingress email filtering. The issues actual reduce to a very few simple, non-complex vulnerabilities from a business process standpoint (ignoring all the technology twists and turns): 1) ISPs that do ingress email filtering and 2) ISPs that do not do ingress email filtering. If ISPs are doing ingress email filtering .... then all the situations of known spammers, spammers masquerading enormously getting accounts, spammers compromising other machines and masquerading enormously, tunneling, etc ... all get taken care of. There are still the periodic traffic accidents where somebody might be able to do a couple hundred before getting cut .... but it probably reduces over 90 percent of the traffic. So the remain issue is whether an ISP is following the traffic laws and doing ingress email filtering or flagrantly flaunting the law and letting millions of spam thru. This is regardless of whether it is a real public ISP ... or effectively a corporate/private ISP. The other ISPs then use blacklisting. The first line of defense is that all ISPs are to do ingress email filtering and the 2nd line of defense is that the major ISPs do blacklisting on the ISPs that obviously are flaunting the law. The primary business issue is that majority of spam is being done for some profit .... that the cost of sending the spam is less than the expected financial return. This should address the 99 percentile. Again, it is very simple, first line of defense is ingress email filtering. This is only a moderate extension of what the major ISPs are currently doing with regard to not accepting email from entities that are obviously not their customers, current traffic limiting business rules, etc. The second line of defense is blacklisting ISPs that aren't following the traffic rules. I claim, it actually is rather much simpler and much more effective. So back to the obvious traffic violations. One is the compromised machines. Large proportion of the compromised machines are their because they all got hit by spamming virus. I claim, that over time if over 90 percent of spamming gets cut ... then 90 percent of the machines that get compromised by virus in spam can also get cut. Situation is now down to large number of compromised machines each sending couple hundred emails each ... staying under the ingress filtering radar. That is orders of magnitude better than the current situation but it is starting to reduce the case to manageable traffic violations. So this scenario gets down to providing significantly more focus on compromised machines ... and back to a recent comment about lots of vendors saying that consumers won't pay for better security ... because they have no motivation. This is somewhat the insurance industry theory of improving on severity of traffic accidents (what motivated automobile manufactory to build safer cars). My ISP currently charges me extra over the flat rate for certain behavioral activities. Violating ingress email filtering rules would be such a valid inducement. I get ingress email filtering accident insurance the premiums are based on the integrity of the machine i'm operating. So, two simple rules .... 1) ISPs do ingress email filtering, and 2) ISPs blacklist other ISPs that flagrantly violate the ingress email filtering rules. With a sizeable reduction in spam, there is corresponding sizeable reduction in compromised machines. However, compromised machines that do spam and hit the ISPs ingress email filtering rules, get fined. It is treated as accident and operating an unsafe vehicle. You can get accident and fine insurance .... but the premium is related to kind of machine you operate. Some inducement for consuming public to purchase safer machines. The two simple rules ... with the fines for violations then provides some inducement for consumer buying habit regarding purchasing safer machines. And it is all quite similar to policies and practices currently in place. -- Anne & Lynn Wheeler http://www.garlic.com/~lynn/ Internet trivia 20th anv http://www.garlic.com/~lynn/rfcietff.htm

I rather liked the suggestion someone made a while ago that involves paying the recipient when sending email to them. If they reply, you get your money back. But if you spam, it would rapidly become expensive. However, that involves financial payments again, and nobody is willing to do financial anything in a way that allows anonymous players. So if we care about the ability to have anonymous email, we can simply eliminate from consideration anything that requires a paid email license or financial payments to be made in exchange for the right to send mail. There is a better way, of course. But it may not be as profitable for the people who want to sell certs, so nobody's pushing it right now. Remember the "hashcash" proposal from a few years ago? It basically involved the recipient setting some computational task that would take a couple of CPU seconds to complete and demanding the results (from the sending machine) before it would accept an email. IIRC, it was proposed with a probabilistic task, but there's no reason why it couldn't be done with a more precisely controlled linear task such as repeated squaring under a modulus. Or maybe you could ask distributed.net to find a way to use CPU cycles beneficially and provably, and require some number of work-packets to be completed before the mail is delivered. The computational task can get arbitrarily larger, if the recipient system doesn't like the look of the mail. I can picture the MDA going, "wow, I decrypted this one, but it scores 9.2 on my procmail filter scale, so I better ask for and get fifteen MIPS-minutes of CPU time before I actually deliver it." Stuff like this can be done anonymously, can be done on the recipient and sender machines, can depend on filters (the MDA sees it after it arrives and gets decrypted) and limits the per-machine rate at which a spammer can send spam. It requires no central keying authority, no registrations or controls, allows random email from people you don't know or haven't heard from in a while to reach you, is a barrier that's fully customizable at the recipient site, can be implemented purely in software (meaning nobody has to get a licence or a subscription or vouched for by someone else to send mail), and if someone really *does* care enough to dedicate fifteen MIPS-minutes of CPU to getting an advertisement through to you, it probably means he's got a specific reason to believe that it's actually something you'll be interested in, rather than just being a "bottom feeder" who sends out a million emails in the hopes of one response. SMTP is a hole, and needs replaced. We have the technology. It'll work. Bear --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com

The computational task can get arbitrarily larger, if the recipient system doesn't like the look of the mail. I can picture the MDA going, "wow, I decrypted this one, but it scores 9.2 on my procmail filter scale, so I better ask for and get fifteen MIPS-minutes of CPU time before I actually deliver it."

Stuff like this can be done anonymously, can be done on the recipient and sender machines, can depend on filters (the MDA sees it after it arrives and gets decrypted) and limits the per-machine rate at which a spammer can send spam.

This doesn't fit Joe Lunchbox's current model in which he dumps his outgoing mail onto his provider's server and turns off his machine. His provider either has to deliver synchronously and bounce the computational payment burden back to Joe, pay it for him, or bounce the message. In the latter case, the receiver who demanded cycles needs to recognize the problem it set and accept the answer on a later date. Matt Crawford

And what about people that use something underpowered like a Palm IV to send email? Does it really make sense to force their little dragonball powered machines to do a whole lot of math? ----------------------Kaos-Keraunos-Kybernetos--------------------------- + ^ + :25Kliters anthrax, 38K liters botulinum toxin, 500 tons of /|\ \|/ :sarin, mustard and VX gas, mobile bio-weapons labs, nukular /\|/\ <--*-->:weapons.. Reasons for war on Iraq - GWB 2003-01-28 speech. \/|\/ /|\ :Found to date: 0. Cost of war: $800,000,000,000 USD. \|/ + v + : The look on Sadam's face - priceless! --------_sunder_@_sunder_._net_------- http://www.sunder.net ------------ On Mon, 12 May 2003, bear wrote:

I submit that if Joe Lunchbox is not spamming, he is unlikely to need to change his habits regarding having his machine available for a computational burden. The mail he sends to people known to him will not ordinarily trip spamfilters at the recieving end that would make such requests.

Likewise, all the people who use remailers to send anonymously. As long as what they're sending isn't identifiable as spam, the remailer won't get a CPU-time request.

On Mon, May 12, 2003 at 03:46:05PM -0400, Bill Sommerfeld wrote:

So, what's my reason to accept a "payment in cpu time"? As best as I can tell, a "payment in cpu time" means that someone *else* doesn't get a payment in cpu time with their spam. I still get the spam.

In the short term (when hardly anyone is sending hashcash tokens) accepting a payment means that you exempt it from your other filtering rules, which means that your filters are less likely to accidentally delete mail you wanted to read. Your reason to send hashcash tokens is to make it less likely that the recipient's filters will accidentally delete your mail.

It seems analagous to a protocol that proves that someone burned a dollar bill.

Very analogous.

A scheme where I actually get something of value might have a bit more traction..

I think I agree that a real cashable payment for 0.1c would be preferable; however the infrastructure to support it is many orders of magnitude harder to setup. It will also likely have to be run as a business because of the setup and ongoing hierarchically organized infrastructure costs. And it's not clear it will profitably scale down to payments that low. And if there is real money on your machine you'll start to see viruses attempting to steal that money. Also the payment system better support privacy or email privacy would have just disappeared. Adam

At 03:46 PM 5/12/03 -0400, Bill Sommerfeld wrote:

So, what's my reason to accept a "payment in cpu time"? As best as I can tell, a "payment in cpu time" means that someone *else* doesn't get a payment in cpu time with their spam. I still get the spam.

The realistic benefit is that you can use something like hashcash as one of your spam filtering rules. Anyone who is spending 1/2 sec on a reasonable machine per e-mail sent isn't likely to be spamming you, because that won't scale up very well for sending out thousands of e-mails at a time. The problem is that until it is widely adopted, it's not a very useful additional filter. There are actually dozens of similar ways to stop nearly all spam, if you can deploy them all over the net at once. But deploying anything all over the net at once isn't practical, so instead, each user or ISP tries to find some workable solution for the problem, typically involving changing his filtering rules every few months and spending a minute or two a day going through his spam folder, making sure he's not throwing away something valuable.

- Bill

--John Kelsey, kelsey.j@ix.netcom.com PGP: FA48 3237 9AD5 30AC EEDD BBC8 2A80 6948 4CAA F259 --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com

On Tue, May 13, 2003 at 08:21:16PM -0700, Joseph Ashwood wrote:

From: "John Kelsey" <kelsey.j@ix.netcom.com>

...

[...]. Anyone who is spending 1/2 sec on a reasonable machine per e-mail sent isn't likely to be spamming you, because that won't scale up very well for sending out thousands of e-mails at a time. The problem is that until it is widely adopted, it's not a very useful additional filter.

The short term usefulness of a hashcash / PoW filter when used with bayesian filters (which I think is what Joseph is saying below) is that you are less likely to accidentally lose mail due to Bayesian filters. Ideally blackhole lists should also be exempted if there is hashcash (they are another big source of loss of email, I've been hit by that a number of times). I suspect increasngly more email will be lost to filters and blackhole lists because the anti-spam people are becoming increasingly gung-ho and sweeping in their blackholing and filtering because the problem is accelerating out of control, so the short term function of hashcash to improve email reliability could be a useful extra function. (Estimates vary but at ASRG kick off at IETF there were some very high per month growth figures (10% and higher per month) for spam which were far in excess of (non-spam) email growth). Similarly your incentive to send hashcash in the short term is to avoid your own mail similarly being swallowed by blackholes and Bayesian filtering false positives. The limitation with blackholes is it depends on the blackhole implementation, some are simply refusing the TCP connection at firewall level; others are accepting but giving you a 500 (or whatever it is) response code explaining why -- but that is already too early for them to have read the X-Hashcash headder. One way around that is to include hashcash as an ESMTP address parameter which I understand allows you to say things after the RCPT TO, but even that may be too late (if they already said go away after the HELO). Another approach but only longer term and it is debatably too aggressive/draconian, and in the short term has same problem as TCP rejection of blackholed IPs would be integration of hashcash into TCP like syncookie (see section 4.2 hashcash cookies of [1]) so that the mailer can reject port 25 connections which don't have hashcash tokens. Or perhaps (less aggressively) to use a getsocketops or ioctl to read from the socket whether the sender is using hashcash or not. One problem with this approach is the PoW received by the MTA may not be convincing to the recipient, so there remains risk that the recipient could be spammed by a colluding or host compromised MTA at their ISP. (You could add envelope recipient emails to the puzzle, but that's sufficiently SMTP related you'd just as well send it in SMTP). Another integration point could be IPSEC. On the interactive connection DoS hardening side, there was a paper about using Juel's and Brainard's Client Puzzles [2] (which is a known solution puzzle where the server has to issue the challenge interactively) for SSL DoS hardening [3]. More recently, though I haven't obtained a copy yet, Xiaofeng Wang and Michael Reiter have a paper about an implementation hardening the linux kernel TCP stack against DoS using puzzles [4], I'm presuming this is similar to the hashcash-cookie approach from the abstract, though I'm not sure which puzzle they used. (Not sure what the puzzle auction mechanism is). Adam [1] Aug 02 - "Hashcash - A Denial of Service Counter Measure" (5 years on), Tech Report, Adam Back http://www.cypherspace.org/adam/hashcash/hashcash.pdf [2] Ari Juels and John Brainard. Client puzzles: A cryptographic countermeasure against connection depletion attacks. In Network and Distributed System Security Symposium, 1999. Also available as http://www.rsasecurity.com/rsalabs/staff/bios/ajuels/publications/client-puz... [3] Drew Dean and Adam Stubblefield. Using cleint puzzles to protect tls. In Proceedings of the 10th USENIX Security Symposium, Aug 2001. Also available as http://www.cs.rice.edu/~astubble/papers.html [4] XiaoFeng Wang and Michael Reiter, "Defending Against Denial-of-Service Attacks with Puzzle Auctions", IEEE Symposium on Security and Privacy 2003 http://www.computer.org/proceedings/sp/1940/19400078abs.htm Joseph Ashwood wrote:

I disagree. If you assume that the entire internet will eventually take up on the process, start with a rule that says "if it has a hashcash token don't process the other rules." Obviously at first this rule would be hit rarely, but a big PR campaign surrounding it would get to people, as would implementing it in Outlook. Eventually your other rules would be rarely hit, and you could change them to simply discard. Once it's everywhere you can begin culling the bad ones. I just don't see where the necessary overhead bult into the servers will take place, or be justified.

--------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com

At 10:22 AM 05/16/2003 -0700, Eric Murray wrote:

There is already a reasonably good proof-of-work mechanism built into SMTP-- START_TLS.

Any server that is willing to do TLS with mine is very unlikely to be a spammer. In fact a quick check of about 8000 spams I have shows that two of them used TLS. (both in the last week. hmm.)

Steve Bellovin pointed out that spammers who use open relays and open proxies will happily burn those CPUs doing proof-of-work as well as burning their bandwidth multiplying spam. That's not necessarily a _bad_ thing, if it gets the attention of the people running the relay/proxy machines (:-) But it's a basic problem with link-based proof-of-work like START_TLS as opposed to end-to-end proof-of-work mechanisms in the message itself. If you do link-based, the pnly last relay site needs to do the work, so the spammer can steal CPU from lots of machines without burning his own. If you do message-based proof-of-work, it's much harder to get a proxy or relay to do the work, as opposed to using the spammer's own machine. START_TLS and other link-based mechanisms _do_ have the benefit of harassing dialup and DSL spammers, who are using their own CPUs without relays, so it at least gets rid of some of the ankle-biters and forces spammers to abuse relays and proxies, which may be easier to identify (especially because they're using START_TLS...) This has the side benefit that it cuts down on the use of dial/dsl blacklists, which are one of the extremely annoying sources of collateral damage in the anti-spam world.

...

I submit that if Joe Lunchbox is not spamming, he is unlikely to need to change his habits regarding having his machine available

Mostly unrelated to this, but something's just occurred to me. Probably I'm being really stupid, but ... for the receiving MTA to know that the

----- Original Message ----- From: "Paul Walker" <paul@black-sun.demon.co.uk> Subject: Re: A Trial Balloon to Ban Email? problem

has been processed properly, it would have to know the answer. How does it know what the answer should be?

That one's easy. Use a problem that is not in P but is in NP. To make it clearer to most people, use a problem that can be verified cheaply, but that can't be solved cheaply. Since it's only everyone's computer Minesweeper is an example of such a problem. Once a solution has been found it is easy enough to verify that it is correct (all bombs marked, all non-bomb places revealed), but it can be prohibitively expensive to compute a large grid. Other common examples include jigsaw puzzles, digits of pi, etc. More functional puzzles for this purpose are NP-complete problems; e.g. traveling salesman, Hamiltonian cycle, SAT, etc. Right now another couple of good examples would be discrete logarithm, and integer factoring. In all these cases verifying the solution is cheap (generally travelling the path in the NP-complete problems, or computing the values in the DL and IF). Verifying that the puzzle is valid is only slightly more difficult, but retaining an active list of problems would solve the issue (but open up the possibility of DOS attacks). Basically it's a fairly easily solved problem. Joe

At 11:52 PM 05/12/2003 -0500, Roy M.Silvernail wrote:

On Monday 12 May 2003 07:09 pm, Joseph Ashwood wrote:

...

That one's easy. Use a problem that is not in P but is in NP. To make it clearer to most people, use a problem that can be verified cheaply, but that can't be solved cheaply.

Please permit me to join the dense crowd. Now that I've proved my labor, how do I attach the proof to the email? Obviously, some parts of the message are added to a hash, but which parts? If it's the body, is whitespace damage still an issue?

The obvious mechanisms for including it are a header line, X-Hashcash-Version-1212: 0x20A13490B8219048243 which is easy pretty easy for almost anybody to add. You could also do an ESMTP extension of some sort, which is much more annoying to add, but lets you reject non-hashcashed messages before receiving them. (The ESMTP approach also has the problem that it's only useful for direct connections, as opposed to mail relayed through your ISP, so that probably isn't as interesting.) Some of the hashcash proposals have required near-real-time interaction between the sender's client and the recipient's server, to collect the string of the day or string of the moment, which has privacy/anonymity problems, while others either use a fixed or slowly changing parameter set, e.g. find a string that matches the first N bits of the SHA1 of recipient@example.com-YYYYMMDDHH or recipient@example.com-YYYYMMDDHH-KEYPHRASE So the recipient's mail server or client looks for the X-Hashcash string, makes sure it isn't recipient@example.com-YYYYMMDDHH-KEYPHRASE, hashes it and makes sure that the number matches, and you're good to go.

On Tuesday 13 May 2003 01:02 pm, Justin wrote:

The message-id would need to be included. Lots of people filter duplicate messages, and those who don't probably should. If spammers try to replay, their duplicates get dropped. If they don't reply using the same message id, they're forced to regenerate hashcash tokens. Using duplicate message ids is an RFC violation, and just using those in the hash avoids the complication of mangled message bodies. It also gets rid of idiot MUAs which don't include message ids.

The mess seems to occur when considering how to verify that that particular message, with a particular message id, wasn't bcc'd to) to 10 billion other people.

Right you are, unless the tokens are centrally cleared. Dupe message-ids are only a violation if you get caught by the same server, so power spamers will sort their lists into bombing runs of one address per victim SMTP server and only need one token per run. Doesn't eliminate their work factor, but it does reduce it.

I don't know that including a Date: header in the hash improves the situation.

Don't think so. Dates can be duped along with message-ids and they still get one trip around the servers on the same token. I don't see this working without some kind of online clearing. Hey, you DBC guys... how do you stiffen up an offline clearing protocol like this?

And what happens when there's a network outage and a message gets stuck in the queue for a day on another server? You know a backup MX server when yours is hosed? Do you not accept the mail because the current day doesn't match what's in the message? Or do you accept mails from a day ago? a week ago? a year ago? 1922? 2nd, why wouldn't the spammer just adjust and send an email to each recipient with a random, but properly hashed token to match the target address + today's date? More work for sure, but if enough targets start adopting it, the spammer will adapt. The token doesn't have to contain an actual valid coin, and you'll only find out when you try to cash it. ----------------------Kaos-Keraunos-Kybernetos--------------------------- + ^ + :25Kliters anthrax, 38K liters botulinum toxin, 500 tons of /|\ \|/ :sarin, mustard and VX gas, mobile bio-weapons labs, nukular /\|/\ <--*-->:weapons.. Reasons for war on Iraq - GWB 2003-01-28 speech. \/|\/ /|\ :Found to date: 0. Cost of war: $800,000,000,000 USD. \|/ + v + : The look on Sadam's face - priceless! --------_sunder_@_sunder_._net_------- http://www.sunder.net ------------ On Wed, 14 May 2003, Adam Back wrote:

Well there are different things you could hash. This simplest is just to hash the recipient address and the current time (to a day resolution).

The recipient looks at the token and knows it is addressed to him because it's his address. He stores it in his double spend database and won't accept the same token twice.

After the validity period of a token has expired he can remove it from his double-psend database to avoid the database growing indefinately. (He can reject out-of-date mail based purely on it's date).

<SNIP>

On Wed, May 14, 2003 at 02:49:34PM +0000, Justin wrote:

Adam Back (2003-05-14 05:27Z) wrote:

...

Well there are different things you could hash. This simplest is just to hash the recipient address and the current time (to a day resolution).

The recipient looks at the token and knows it is addressed to him because it's his address. He stores it in his double spend database and won't accept the same token twice.

This is just broken.

How do you know what address the sender was sending to? You have no reliable access to envelope to: addresses.

Well the address the token was minted for is contined in the hashcash header, and the recipient knows what email addresses he accepts mail for. To take your example:

Joe bcc's james@nowhere.net, politely generating a hashcash token over james@nowhere.net and the mesID. Nowhere.net expands that alias to james.t.doe@treas.gov.

The sender as he Bcc'd james@nowhere.net thinks this the recipient's address, so it delivers to envelope address james@nowhere.net and for that delivery adds header: X-Hashcash: 0:030514:james@nowhere.net:b384c3cc66319383 Then the .forward file forwards to james.t.doe@treas.gov, who reads his mail; his MUA sees that the message is to james@nowhere.net an address he reads mail for, checks the collision: % echo -n 0:030514:james@nowhere.net:b384c3cc66319383 | sha1 000002e07c7aac5697396f41dbb277aee02f6517 sees there are enough bits of collision, and if he hasn't seen this token before he accepts the mail. The message will also contain one hashcash header per to or cc recipient. (Bcc recipients must be delivered separately because otherwise bcc semantics are lost -- other recipients should not learn from the hashcash headers that the bcc recipient received the mail).

Worse, even if there were a reliable mechanism, all it takes is one loose cannon with an open mass-mail list and as long as it doesn't delete whatever header (maybe delivered-to:, maybe something else) that indicates the list was an envelope to: address, one hashcash token works for one email to the entire list.

I take it this comment is about mailing lists? Mailing lists have to be treated separately. The sender probably can't afford to create a token for each recipient. (Also he doesn't know the recipient's addresses). Mailing lists deal with spam with filtered versions of lists.

...

After the validity period of a token has expired he can remove it from his double-psend database to avoid the database growing indefinately. (He can reject out-of-date mail based purely on it's date).

Isn't it simpler to use message IDs for replay detection? No need to look for replays using another mechanism when there's already one that works fine, and that many people use for dup detection today.

You have to cope with multiple hashcash headers when a mail has multiple recipients, Message-ID only suports one header. For USENET postings putting the hashcash token in the Message-ID can work because USENET uses the Message-ID to supress duplicates in it's flooding algorithm, and you could argue that there is just one recipient: USENET (or the cross-posted group list). Adam

At 04:53 PM 05/15/2003 +0100, ken wrote:

So if this was implemented we get incentive to design a new kind of hashing algorithm, one designed to be difficult to run, because all it is needed for is to prove that someone bothered enough to spend the time. Also it needs to map one plaintext to many valid hashes of course as others said thats easier when you include the "from:" in the hash or allow some arbitrary field.

The hash is easy to do - Given a target "T", provide a string "X" for Bit(i,SHA1(X)) == Bit(i,SHA1(T)) for i=1...n, and Substring(SHA1(X),N+1,160) != Substring(SHA1(T),N+1,160). You'll need to try roughly 2**N inputs to find one.

On Sun, 2003-05-11 at 16:05, Paul Walker wrote:

...

I submit that if Joe Lunchbox is not spamming, he is unlikely to need to change his habits regarding having his machine available

Mostly unrelated to this, but something's just occurred to me. Probably I'm being really stupid, but ... for the receiving MTA to know that the problem has been processed properly, it would have to know the answer. How does it know what the answer should be?

I believe the usual approach to this is to have it be a asymmetrictry hard problem - i.e. factor some primes to do the work (hard), multiply them to validate answer (easy). -- Nathan ------------------------------------------------------------ Nathan Neulinger EMail: nneul@umr.edu University of Missouri - Rolla Phone: (573) 341-4841 Computing Services Fax: (573) 341-4216 --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com

"Paul Walker" <paul@black-sun.demon.co.uk> writes:

...

I submit that if Joe Lunchbox is not spamming, he is unlikely to need to change his habits regarding having his machine available

Mostly unrelated to this, but something's just occurred to me. Probably I'm being really stupid, but ... for the receiving MTA to know that the problem has been processed properly, it would have to know the answer. How does it know what the answer should be?

The same way you know you have the right answer with certain other hard problems -- you choose a problem that's one-way hard. For example: factoring. Factoring a large number is hard. Verifying you have the right answer is easy (you just multiply the factors and see if you've got the right answer). So, just choose from the class of self-verifying problems. OTOH, I still think a micro-payment postage system is a better idea. The sender puts a micro-payment into the mail header to pay the recipient to accept/read the message. For non-spam, the receipient doesn't need to cash the payment (or can just return it to the sander). For spam, the receipient collects the money (thereby costing the spammer real $$$ to send spam, if most receipients actually collect). The only remaining architectural problem is how to handle mailing lits. -derek -- Derek Atkins Computer and Internet Security Consultant derek@ihtfp.com www.ihtfp.com --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com

At 12:09 PM 05/13/2003 -0700, Joseph Ashwood wrote:

----- Original Message ----- From: "Derek Atkins" <derek@ihtfp.com> Subject: Re: A Trial Balloon to Ban Email?

[Micropayment, sender pays recipient, refund for non-spam]

So you're expecting that everyone will be honest about cashing micropayments? That seems rather silly, if such a mechanism were to become required on the internet I'd simply retire today, sign my email accounts (all except 1) up on every spam list, every mailing list, everything that would get me thousands of tokens a day, have an automated script cash all the tokens for me, and I'm generally considered fairly scrupulous.

I can see the advertising campaign for this now:

You, yes YOU!! Can M4K3 M0N3Y FA$T! Just By READING EMAIL!!! FIND OUT HOW BY SENDING US $9.95 or 10.2Euros or 1 Gram of e-Gold!

It's frustrating, because just about any set of who-pays-whom-for-email fails badly other than sender-pays-recipient-somehow.

At 1:11 PM -0700 5/13/03, Greg Broiles wrote:

If we assume an environment where a payor/spender can later check to see if their payment was cashed, this also creates a relatively cheap way for spammers to create or validate a list of working email addresses.

This problem could be eliminated if the ISP(s) collected the money, regardless of whether the mail could be delivered or not. It's sounding more and more like the postal system. Perhaps we can get spam-stamps to subsidize regular email. Cheers - Bill ------------------------------------------------------------------------- Bill Frantz | Due process for all | Periwinkle -- Consulting (408)356-8506 | used to be the | 16345 Englewood Ave. frantz@pwpconsult.com | American way. | Los Gatos, CA 95032, USA

Yes, but how will you stop the spammer from double spending the same $0.25 micropayment on all of his 170,000 email addresses? Depending on whether you check that there is a payment attached or not, and also check it with the bank before delivering it, you'd have already wasted your bandwith and possibly have accepted a spam into your mail spool. At that point you have: 1. already had a slice of your bandwidth eaten by the spammer, plus some cpu cycles verifying that there exists a coin. Spammer +1, you -1. 2. You now have to verify that the coin is a coin and not just some random junk - you waste some cpu cycles here. If you don't validate that the coin hasn't been doubly spent, you haven't made that $0.25 and have accepted a spam - not that you will personally read it, but your system did (cpu, bandwith and some disk storage until it throws it to the hungry maw of /dev/null.) spammer +1, you -2. 3. Presumably you'll want to validate/cash the coin. If you do, you'll need to talk to the bank in order to prevent the spammer from double spending and to actually collect your quarter v-cash. By doing that on a spam, you're taking part of a DDoS against the bank as only the 1st guy on the spammer's list to talk to the bank will get the coin - because everyone presumably will chose to cash the coin. If you don't cash nor validate the coin with the bank, you haven't made your vquarted, spammer +10 point, you -1, bank -10,000. The spammer doesn't give a shit, he just wants to get as many emails out there as possible. In fact, he mostly doesn't care whether you filter or not - he makes his money when he sends the spam, not when you read it. Of course, he can charge more for "real, verified" email addresses, but that's less important. What's the score again? Oh yeah, game over, insert quarter to play again. A beautiful example of creating a cryptographic solution that doesn't quite work in real life. ----------------------Kaos-Keraunos-Kybernetos--------------------------- + ^ + :25Kliters anthrax, 38K liters botulinum toxin, 500 tons of /|\ \|/ :sarin, mustard and VX gas, mobile bio-weapons labs, nukular /\|/\ <--*-->:weapons.. Reasons for war on Iraq - GWB 2003-01-28 speech. \/|\/ /|\ :Found to date: 0. Cost of war: $800,000,000,000 USD. \|/ + v + : The look on Sadam's face - priceless! --------_sunder_@_sunder_._net_------- http://www.sunder.net ------------ On Tue, 13 May 2003, Declan McCullagh wrote:

Greg is right, and raises a point I hadn't considered before. But then again if I charge $.25 to send me mail in a hypothetical micropayment system (and I'd hope a social custom would arise making it tacky to retain the money if the mail were not spam), I'd be happy to let everyone know I have a working email address.

In the spirit of I. F. Stone... Buried in the last paragraphs of an article in yesterday's San Jose Mercury News (Thursday, May 15) that starts out talking about members of congress saying that the US is ill-prepared to defend against an attack on critical computer systems is the following gem. "Last fall's legislation authorized the National Science Foundation to spend $110.25 million on cyber-security research, but the agency is requesting only about $51 million. DARPA's unclassified budget for cyber-security research has actually declined, from about $90 million in 2000 to $30 million in 2003. But Tether [Tony Tether, director of DARPA] said those figures were misleading, because more projects are now classified. He estimated the agency will spend about $100 million on cyber-security research in 2004." Note also that DARPA's support of the OpenBSD project has been dropped (see http://www.openbsd.org/). Do these changes mean that the US is trying to protect "critical infrastructure" using classified techniques so other nation's systems can be hacked while US ones are safe? Inquiring minds want to know. Cheers - Bill ------------------------------------------------------------------------- Bill Frantz | Due process for all | Periwinkle -- Consulting (408)356-8506 | used to be the | 16345 Englewood Ave. frantz@pwpconsult.com | American way. | Los Gatos, CA 95032, USA --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com

-- On 13 May 2003 at 9:06, Derek Atkins wrote:

OTOH, I still think a micro-payment postage system is a better idea. The sender puts a micro-payment into the mail header to pay the recipient to accept/read the message. For non-spam, the receipient doesn't need to cash the payment (or can just return it to the sander). For spam, the receipient collects the money (thereby costing the spammer real $$$ to send spam, if most receipients actually collect). The only remaining architectural problem is how to handle mailing lits.

Recipients whitelist the mailing list, or better still its digital signature. Mailing list operator collects the micropayments on submissions. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG Xk9R3hEjL27Vh4JwzxHMmoB1TfEiftAXvdhzpKyb 4fEwddb+ZTQFP9ep7mGzY5moueUOD0FeCIlksgaM6 --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com

At 04:45 PM 5/12/2003, Adam Back wrote:

Whether you think a few seconds is sufficient depends on your views of the economics of spamming. Ie how close to losing break-even the spammers are, and whether a few seconds of CPU per message is enough to significantly increase the cost. This article for example discusses the economics of spam:

http://www.eprivacygroup.com/article/articlestatic/58/1/6

they give an example of a spam campaign with a 0.0023% response rate, and a yeild of $19 per response. They estimate the cost of sending the spam was less than 0.01c per message. I've seen significantly lower estimates for the sending costs. To deter a given spam campaign we just have to increase the cost to the point of making it unprofitable given the response rate and profit per responder. The other side of this equation is what a second of CPU costs in monetary terms to a spammer.

Assuming that a CPU costs $500 and that its value can be amortized over 2 years, CPU costs .0016 cents/second. Based on the numbers enough, the revenue/spam sent is .044 cents. Thus, the breakeven point is 27.6 seconds/message: assuming other costs are minimal, you have to require > 27.6 seconds of CPU calculation from an email submittant to ruin the spamming business model. A few thoughts on this: - You have to adjust the size of the calculation frequently to keep up with Moore's law (although the time/$500 CPU is constant, assuming constant profitability for spam) - If spammers have new technology or economies of scale available to them, it's going to adversely affect everyone else. (That is, if you're using an 18-month-old CPU and CPU-seconds cost you twice what they cost in the volume it costs spammers, your $500 computer will have to spend 2 minutes of time to calculate a token it takes a spammer 30 seconds to calculate). - This is going to dramatically increase the costs of sending bulk e-mail for non-spammers: for example, I get airline specials a few times a week; they must send millions of these. - The CPU time required here is several orders of magnitude larger than the cryptographic costs associated with SSL, and SSL is not broadly accepted at least in part due to the CPU cost associated with with it; this implies to me that there will be substantial resistance. - The CPU costs associated with SSL engendered a substantial market in cryptographic accelerators intended to reduce the cost to do an RSA private key operation. Presumably, a system like this will create such a market for e-mail token accelerators: unfortunately, this is exactly the kind of new tech / economy of scale envisioned above: we may end up with a situation where a calculation which costs a spammer .044 cents will take the average user's CPU 10 minutes or more to calculate. - Tim

... but i would contend that the infrastructure costs associated with a billion or two spams per day are significantly higher than the costs that are currently being incurred by the spammers .... in effect the industry as a whole is underwriting a significant percentage of the actual costs, which makes spamming such an attractive economic activity. one of the issues is to reflect the fully loaded costs of a billion or two spams per day back to the spammers. -- Anne & Lynn Wheeler http://www.garlic.com/~lynn/ Internet trivia 20th anv http://www.garlic.com/~lynn/rfcietff.htm

-- On 12 May 2003 at 21:18, Tim Dierks wrote: Assuming that a CPU costs $500 and that its value can be amortized over 2 years, CPU costs .0016 cents/second. To say the same thing in different words, the spammer's unattended computer costs 0.0016cents per second, the non spammer's computer is worth about 0.5cents per second, because there is an impatient user sitting there waiting for the mail to complete. Thus the non spammer's computer time costs approximately four hundred times as much as the spammer's computer time.

From this, I conclude that hashcash is not economically viable. We have to use a form of cash that is similarly valuable for spammers and non spammers.

--digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG QLQau7uADLb/zG+C/w+cIuiW5I9NSD4m6LNPbwYK 4zNtefDWUbC4Pp6JJTh53TS6UPtqXu/hY1EPp5PPv --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com

At 09:45 PM 5/12/03 +0100, Adam Back wrote:

In addition it is expected that there would be a mechanism whereby regular correspondents would white list each other. (Probably automatically via their mail clients).

Whether you think a few seconds is sufficient depends on your views of the economics of spamming. Ie how close to losing break-even the spammers are, and whether a few seconds of CPU per message is enough to significantly increase the cost.

Two points. First, Joe Sixpack won't use it if it requires an extra click; but he might if the mail queueing is in the background. Second, spammers use trojans that establish local mail relays (!) You think they won't steal some cycles to pollute? Ok, three points. If you're sending from your PDA, either deal with the battery-life-loss as a cost of emailing from your PDA, or have your net-connected host do the work. Again, transparently, or no one will use it. Personally, I favor an Assasination Politics flavor solution, but that's unlikely to gain widespread favor :-)

...

Lauren Weinstein, founder of People for Internet Responsibility, has come out with a new spam solution at http://www.pfir.org/tripoli-overview.

Phil Hallam-Baker made of Verisign made a similar proposal. (I missed responding to an earlier post on this thread that said "here comes Verisign" or such-like.) Unfortunately, I can't find his post any more; I think it was on one of the XML security WG lists, but the message has already been purged from my mailbox. On thing interesting about the VRSN proposal was they they had a hardware implementation of the "velocity checker" as an option. And a patent applied for that. /r$ --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com