Subject: [Sip] jennings-sip-hashcash - does it help - does it work

From: Cullen Jennings <[email-masked]>
Date: Wed, 02 Mar 2005 12:10:15 -0800

Long email, but I think it is worth reading.....

There have been several comments that this draft does not work. This is of
course true - I will go on to prove why it is impossible for anything "to
work" then I will explain why I think this helps even though it does not
work.

The problem we are trying to solve is to let people with no previous
relationship contact us and yet not get contacts that we find undesirable.
How much is a bad guy willing to spend? Can we make that greater than the
amount a good guy can reasonable spend?

Let's consider how much bad guys will spend. Founders of acquired startups
are often contacted by random financial companies to help manage their new
riches. These people offer to fly from New York to San Jose and spend hours
taking to you. They are clearly willing to spend in the order of 100s of
dollars to contact you. This happens to a very narrow and targeted market.
LL Bean is willing to paper mail a gloss catalog to house will reasonable
looking demographics. This is order $1. People are willing to send Viagra
emails to random email addresses and hope they work. As the costs go down,
the volume goes up.

Let's consider how much good guys will spend. Some student in Fiji wants to
send me an email asking my about my draft. Doubt he will spend much but I
would like to get that email. There s no way he will spend the 100s of
dollars. 

So what's our goal here, it's simple - as you raise the cost, you reduce
both the good and bad people that are willing to contact you. My assumption
would be to make the cost very low such that anyone that had the most
pathetic CPU could still contact you in say 10 seconds. A key part of this
draft is the person receiving the communications can set this at will. Now
what will this do to bad guys - well I argue it will raise their costs. Will
it stop the financial advisors, not a hope of it, will it stop the people
that do telemarketing today, nope, will it stop Viagra adds, it might. The
expected return on those is low, will is stop a single users from ringing
every Vonage phone is in 5 seconds before any operator or system can react
at 2 am and making Vonage a service that people turn off - probably. It's
classic type I/type II error problem and the receiver gets to choose how to
balance these two errors.

As I clearly say in the SPAM draft - whitelists are the best thing. After
that, we need to consider multiple other options - this is one of them.

In general there are two camps on why this won't work. One is the bad guys
CPU is way way faster than good guys. I think I addressed this above. The
other camps is that the bad guy has an army of zombie PC and basically has
infinite CPU time and my argument above is bogus. The Luarie/Clayton "Proof
of Work Proves not to work" paper is the crescendo of this flawed argument.
To understand the problem with this paper, you A needs to assume white
lists, and B need to look at a macro not the micro argument. Yes it is true,
some bad guy will have an ton of zombies and get all their stuff thought.
However, our goal is not to stop messages from any single one person but to
reduce the overall number of bad messages received. I agree with Mike that
the Zombie issue is far more worrying to me about the viability of this
approach than the relative speeds of various CPU issues.

If you assume that some percentage of the machines in the world each year
get owned and used as a zombie. Let's say that a given machine has 1% of
having this happen to it in a year and it manages to send zombie traffic for
24 hours before it gets shut down and that mechanism here limits it to 10
messages per second. In this case, each machine on the internet will receive
an average of about 1 bad msg per hour. If you assume there are more users
than machine, this looks appealing. If you assume that msg sending
technology detects users that are sending lots of messages and shuts them
down in less than 24 ours, it gets better, if you live in the wonderful
world of hope that OS might get better or users might pick better OS so
there are less zombies, like gets better. The next one is a hard explanation
to make mathematical models around but it is true. The people that have the
best financial incentive to send bad guy messages, do not what to be subject
to the legal and reputation problems of using zombies to get their message
across.  

So in summary, White Listing is your first and best defense. Make sure the
Identity work gets done soon. Caller Identity is critical for this - get
that work done. However, white list can not be "your first, last and only
line of defense" - we have to have something else or give up getting
messages from people with no previous direct or indirect relationship.
Hashcash can not work in stopping all bad messages - that is not the goal -
the goal is to raise the cost thus decrease the number of times it makes
economic sense to send bad messages. It does assume that the bad guy will
have more CPU than the good guy - and the zombie attacks will be a way to
still send lots of messages. However, this will still reduce the number of
bad messages - how much - no ones knows. In fact no one will ever know
because there is no way to do a controlled experiment.

Is it perfect - no. Will it make things better - yes. Noticeably better - no
one knows. Does someone have a better plan - right now the only think that
limits the rate I can ring every SIP phone in the world is proxies getting
overloaded. And of course that most sip phones are not connected to the
public internet and this is one of the reasons why. There are some other
approaches as we outlined in the spam draft. They have different pro's and
cons - we probably need to do most of them.

Cullen

PS - this conversation is more about the spam draft than the hashcash draft.

On 2/25/05 5:31 PM, "Dan Wing" <[email-masked]> wrote:

> 
> On Feb 25, 2005, at 8:03 AM, Cullen Jennings wrote:
> 
>> 
>>  The idea would be to have a very skewed amount of computation to help
>> rate limit attacks. Whatever amount of computation is "reasonable" for
>> a valid client to do, an attacker is going to be able to apply a lot
>> more computation to the problem. However, this still limits the number
>> of messages the attacker can do and thus raises the cost. I discuss
>> this some what in the SPAM draft.
>> 
>>  This could all happen in different ways. Imagine a case where my
>> enterprise proxy compute the puzzles on behalf of my phone when I call
>> another domain. Say in a large enterprise, it has 10,000 people and
>> during a busy hour makes 10 calls per second that are to an address
>> external to the domain. Of these only 2 are not whitelists. If the
>> enterprise proxy was willing to spend say 3GHz worth of CPU at
>> computing challenges for these 2cps, well that is a pretty hefty
>> amount of hash that could be required.
>> 
>> Another ways is perhaps all the UAC are willing to do about the amount
>> of hashing that 1 second of G.729 compression would take. It's hard to
>> imagine that most UAs (even large GWs) could not do this. This would
>> limit the rate of attack of a single computer to in the 100s of
>> messages per second. This is a lot less hashing that the example above
>> but contrast this to what is possible today. Today I can send in the
>> order of 100,000 message per second. Increasing the cost of an attack
>> by 1000 is good. It slows it down and give you time to trace the
>> source and cut it off before it is everywhere. It makes is less worth
>> while to advertise products that a very very small percentage of the
>> receivers would buy.
>> 
>>  As discussed in the SPAM draft, you would always want to use white
>> lists first then if the person was not on the white list fallback to
>> something else like this.
> 
> Unstated in either document is the assumption that every legitimate
> caller and every spammer has, at their disposal, one and only one
> machine that has the CPU capacity of a modern off-the-shelf PC -- "1
> Pentium Unit".  If a legitimate user has less, or a spammer has more, I
> don't see hashcash being very valuable.
> 
> If a legitimate caller has less than 1 Pentium Unit, it seems that
> person is SOL -- they either upgrade their UA, upgrade their SIP proxy
> to solve the puzzle for them, buy puzzle-solving MIPS from someone
> else, or simply not complete a call to someone with a difficult
> challenge?
> 
> I do agree that hashcash makes spamming more expensive, but
> significantly more expensive.  Today, email spammers own botnets which
> are used to send email spam.  Tomorrow, SIP spammers can modify those
> same botnets to solve hashcash puzzles _and_ send (SIP or email) spam
> -- afterall, it isn't computationally-expensive to send email spam
> (it's mostly bandwidth), so each PC can do a computational puzzle in
> addition to its normal spam duties.  And the PCs that a spammer 'owns',
> which can't send spam due to a clueful ISP, can still solve hashcash
> puzzles on behalf of a SIP spammer.
> 
> And ven without a botnet of PCs, a spammer can buy a workstation with
> substantially more than 1 Pentium Unit.  And I expect spammers will
> write software running on off-the-shelf speciality hardware, such as
> graphics accelerators, to solve hashcash puzzles faster than 1 Pentium
> Unit.
> 
> -d
> 
> 
>>  Cullen
>> 
>> 
>>  On 2/24/05 11:30 AM, "Francois Audet" <[email-masked]> wrote:
>> 
>> 
>> We may need to explain some of the limitations of this. It seems to me
>> that this mechanism would not be terribly appropriate for applications
>> that aggregate a large number of clients onto a single platform. For
>> example, this may be too computationally intensive for a large PSTN
>> Gateway, or even a large Proxy.
>> 
>> Any ideas of how a UAS would make the decision to send the 419 without
>> burdening the UAC? Should there be a supported/require header for this
>> functionality, so that a UAC could "opt out"?
>> 
>> 
>>   
>> -----Original Message-----
>> From:  [email-masked] [mailto:[email-masked]] On Behalf Of
>> Cullen  Jennings
>> Sent: Tuesday, February 22, 2005 16:46
>> To:  [email-masked]
>> Subject: [Sip]  draft-jennings-sip-hashcash-01
>> 
>> 
>>  I updated  this draft on "SIP Computational Puzzles" so it has enough
>> detail to implement  it. (Previous version did not). It is in the
>> drafts directory and also in HTML  form at:
>> 
>> http://scm.sipfoundry.org/rep/ietf-drafts/fluffy/draft-jennings-sip-
>> hashcash-01.html
>> 
>>  Cullen
>> 
>> 
>> 
>> _______________________________________________
>>  Sip mailing list  https://www1.ietf.org/mailman/listinfo/sip
>>  This list is for NEW development of the core SIP Protocol
>>  Use [email-masked] for questions on current sip
>>  Use [email-masked] for new developments on the application of sip
>> 
>> 
>>   _______________________________________________
>> Sip mailing list  https://www1.ietf.org/mailman/listinfo/sip
>> This list is for NEW development of the core SIP Protocol
>> Use [email-masked] for questions on current sip
>> Use [email-masked] for new developments on the application of sip

_______________________________________________
Sip mailing list  https://www1.ietf.org/mailman/listinfo/sip
This list is for NEW development of the core SIP Protocol
Use [email-masked] for questions on current sip
Use [email-masked] for new developments on the application of sip

---

From: Michael Thomas <[email-masked]>
Date: Wed, 02 Mar 2005 12:59:08 -0800

I think you're forgetting to factor in the harm done
by such a scheme in whether it's useful or not. That
is: what is the percentage of false positives who simply
decide to tell your hashcash enabled box to shove it
rather than putting their phone into toaster mode for
20 seconds? And then you next need to factor in whether
you're actually causing harm to your intended victims.

As I said, the advent for free CPU resources for the
bad guys and very finite CPU resources for small 
embedded widgets doesn't seem like you're going to 
make very worthwhile dent in things. The same is
pretty much true with challenge response schemes
for email: you need to factor in the number of people
who will simply decide that the onerous work you're
putting them through is not worth the effort, and...
chalk up another false positive. From an enterprise
standpoint, I think it's even worse: the false positive
rate -- at least at Cisco, but probably elsewhere --
needs to be *very* small.

Lastly, I'd be concerned about the transition
model here. Not everything is going implement this
right away: how do differentiate non-implementers from
purposeful non-implementors? Is it realistic to just
say no to non-implementors? Especially when you consider
that as a PSTN replacement there is a general expectation
of call success rather than call failure (unlike, say,
IM).

		Mike

---

From: Jonathan Rosenberg <[email-masked]>
Date: Wed, 02 Mar 2005 17:55:41 -0500

inline.

> of call success rather than call failure (unlike, say,

Transition is a big deal, I agree.

I think here, the answer is that if the caller claims that they don't do 
hashcash, you probably need to fall back into other mechanisms for 
dealing with anti-spam, such as the consent framework or a reputation 
system.

-Jonathan R.

-- 
Jonathan D. Rosenberg, Ph.D.                   600 Lanidex Plaza
Director, Service Provider VoIP Architecture   Parsippany, NJ 07054-2711
Cisco Systems
[email-masked]                              FAX:   (973) 952-5050
http://www.jdrosen.net                         PHONE: (973) 952-5000
http://www.cisco.com