Re: [camram-spam] Re: Microsoft publicly announces Penny Black PoW postage project

2004-01-02 Thread Alan Brown
On Tue, 30 Dec 2003, Bill Stewart wrote:

 The reason it's partly a cryptographic problem is forgeries.
 Once everybody starts whitelisting, spammers are going to
 start forging headers to pretend to come from big mailing lists
 and popular machines and authors, so now you'll not only
 need to whitelist Dave Farber or Declan McCullough if you read their lists,
 or Bob Hettinga if you're Tim (:-), you'll need to verify the
 signature so that you can discard the forgeries that
 pretend to be from them.

 You'll also see spammers increasingly _joining_ large mailing lists,
 so that they can get around members-only features.

This has already happened:

Krazy Kevin pulled this stunt 5 years ago on at least one list I was on,
joining the list to harvest the most common posters, then spamming using
them as sender envelopes after he'd been kicked off.

 At least one large mailing list farm on which I've joined a list
 used a Turing-test GIF to make automated list joining difficult,

...discrimination against blind users - this is legally actionable in
several countries. There is a blind group in the UK taking action
against a number of companies for this and the Australian Olympic
committee ended up being fined several million AU$ for the same offence
in 1999.

 and Yahoo limits the number of Yahoogroups you can join in a day,
 but that's the kind of job which you hire groups of Indians
 or other English-speaking third-world-wagers to do for you.

To underscore that point, I've _watched_ cybercafes full of SE asians(*)
doing exactly this kind of thing for the princely sum of US$5/day -
twice the average wage of the area, even after the cafe fees were
deducted.

(*) Philippines and east Malaysia.

AB

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: [camram-spam] Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-31 Thread R. A. Hettinga
At 7:46 PM + 12/30/03, Richard Clayton wrote:
where does our esteemed moderator get _his_ stamps
from ?

A whitelist for my friends, etc...

Whitelist [EMAIL PROTECTED]

Cheers,
RAH

-- 
-
R. A. Hettinga mailto: [EMAIL PROTECTED]
The Internet Bearer Underwriting Corporation http://www.ibuc.com/
44 Farquhar Street, Boston, MA 02131 USA
... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire'

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: [camram-spam] Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-31 Thread Bill Stewart
At 07:46 PM 12/30/2003 +, Richard Clayton [EMAIL PROTECTED] wrote:
 [what about mailing lists]
Obviously you'd have to whitelist anybody's list you're joining
if you don't want your spam filters to robo-discard it.
moan
I never understand why people think spam is a technical problem :( let
alone a cryptographic one :-(
/moan
The reason it's partly a cryptographic problem is forgeries.
Once everybody starts whitelisting, spammers are going to
start forging headers to pretend to come from big mailing lists
and popular machines and authors, so now you'll not only
need to whitelist Dave Farber or Declan McCullough if you read their lists,
or Bob Hettinga if you're Tim (:-), you'll need to verify the
signature so that you can discard the forgeries that
pretend to be from them.
You'll also see spammers increasingly _joining_ large mailing lists,
so that they can get around members-only features.
At least one large mailing list farm on which I've joined a list
used a Turing-test GIF to make automated list joining difficult,
and Yahoo limits the number of Yahoogroups you can join in a day,
but that's the kind of job which you hire groups of Indians
or other English-speaking third-world-wagers to do for you.






-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: [camram-spam] Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-31 Thread jal
On Tue, 30 Dec 2003, Bill Stewart wrote:

 At 07:46 PM 12/30/2003 +, Richard Clayton [EMAIL PROTECTED] 
 wrote:
  [what about mailing lists]
 Obviously you'd have to whitelist anybody's list you're joining
 if you don't want your spam filters to robo-discard it.
 
 moan
 I never understand why people think spam is a technical problem :( let
 alone a cryptographic one :-(
 /moan

It has always been mostly a technical problem, and only partially a
social problem. 

 The reason it's partly a cryptographic problem is forgeries.
 Once everybody starts whitelisting, spammers are going to
 start forging headers to pretend to come from big mailing lists
 and popular machines and authors, so now you'll not only
 need to whitelist Dave Farber or Declan McCullough if you read their lists,
 or Bob Hettinga if you're Tim (:-), you'll need to verify the
 signature so that you can discard the forgeries that
 pretend to be from them.

I had to change my (admittedly simple) whitelisting recently, when
spammers started using the same domain name we do business under, or the
name of partners.

 You'll also see spammers increasingly _joining_ large mailing lists,
 so that they can get around members-only features.
 At least one large mailing list farm on which I've joined a list
 used a Turing-test GIF to make automated list joining difficult,
 and Yahoo limits the number of Yahoogroups you can join in a day,
 but that's the kind of job which you hire groups of Indians
 or other English-speaking third-world-wagers to do for you.

Yep. Spam rates have been creeping up on Debian lists, lately.
Another list I'm on having to do with Oracle has been having similar
problems. 

Who is a meaningful member?

That's a tough question, if you don't charge, and if you do, you miss
quite a bit, thus lowering the value. Commons, tragedy, etc.

-j


-- 
Jamie Lawrence[EMAIL PROTECTED]
Those who make peaceful revolution impossible will make violent revolution
inevitable. 
   -John F. Kennedy


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: [camram-spam] Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-31 Thread Ben Laurie
Richard Clayton wrote:
and in these schemes, where does our esteemed moderator get _his_ stamps
from ? remember that not all bulk email is spam by any means...  or do
we end up with whitelists all over the place and the focus of attacks
moves to the ingress to the mailing lists :(
He uses the stamp that you generated. Each subscruber adds 
[EMAIL PROTECTED] as an address they receive mail at. Done. Trivial.

Cheers,

Ben.

--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/
There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit. - Robert Woodruff
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: [camram-spam] Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-30 Thread Eric S. Johansson
Scott Nelson wrote:

d*b
---
s
where: d = stamp delay in seconds
  s = spam size in bytes
  b = bandwidth in bytes per second


I don't understand this equation at all.

It's the rate limiting factor that counts, not a combination of
stamp speed + bandwidth.
well, stamp speed is method of rate limiting.  This equation/formula 
gives you the ratio of performance degradation.  So,

Given d=15, b=49152 (aka 384kbps) and s=1000

the slowdown ratio or factor is 737.28 times over what an unimpeded 
spammer can send.  But as you increase spam size, the slowdown factor 
declines.

Assuming 128Kbps up, without a stamp it takes about .6 seconds to
send a typical 10K spam.
If it takes 15 seconds to generate the stamp, then it will take
15 seconds to send a stamped spam.  It won't even take 15.6 seconds,
because the calculation can be done in parallel with the sending.
actually, it would take 15 but only because you can be sending one 
stamped piece of spam at the same time as you're generating the next 
stamp.  But using your spam size, , the slowdown factor becomes roughly 
73 times.  So they would need 73 machines running full tilt all the time 
to regain their old throughput.  It's entirely possible that one 
evolutionary response to stamps would be to generate larger pieces of 
spam but that would also slow them down so we still win, kind of, sort of...


assuming unlimited bandwidth, if a stamp spammer compromises roughly the 
same number of PCs as were compromised during the last worm attack 
(350,000) at 15 seconds per stamp, you end up with 1.4 million stamps 
per minute or 2 billion stamps per day.  When you compare that to the 
amount of spam generated per day (high hundred billion to low trillion), 



Not according to the best estimates I have.
The average email address receives 20-30 spams a day (almost twice 
what it was last year) and there are only 200-400 million 
email addresses, which works out to less than 10 billion spams per day.
actually, I'm hearing that there are roughly one billion addresses but 
unfortunately have lost the source.  The numbers for spam I'm hearing 
are on the order of 76 billion to 2 trillion
(
2 tril spams /day 
http://www.pacificresearch.org/press/clip/2003/clip_03-05-08.html
76 bil http://www.marketinglaw.co.uk/open.asp?A=703
)

If you have a better source (and I am sure there are some), I would like 
to hear it.


But there's a much easier way to do the math.

If 1% of the machines on the internet are compromised,
and a stamp takes 15 seconds to generate, then spammers can send
50-60 spams to each person.
(86400 seconds per day / 15 seconds per stamp * 1% of everybody = 57.6)
unfortunately, I think you making some assumptions that are not fully 
warranted.  I will try to do some research and figure out the number of 
machines compromised.  The best No. I had seen to date was about 350,000.

You can reduce that by factoring in the average amount of time
that a compromised machine is on per day.
I fully expect that stamps will rise in price to several minutes,
if camram actually gets any traction.
well, that might be the case but I must have a who cares attitude about 
that.  For the most part I rarely send mail to strangers and the stamp 
generation process is in background.  So if it take several minutes to 
queue up and send a piece of mail a few times a month.  What's the 
problem? (yes, I know I'm being cavalier)

Custom hardware?
I can buy a network ready PC at Fry's for $199.
If it takes that machine 30 seconds to generate a stamp, and I leave
it running 24/7, and replace it after 5 months, then the cost
of a hashstamp is still less than 1/500 of a snail-mail stamp.
Granted it's a significant increase in costs over current email,
and therefore potentially a vast improvement, 
but it's still not expensive.
wrong unit of costs.  The stamps still take 15 seconds (give or take) 
which means approximately 5760 stamps per day.  Hardware acceleration is 
an attack against stamps by using dedicated hardware to shrink the cost 
in time of a given size stamp.  so, if and evil someone can build an 
ASIC to shrink the cost of a stamped by 100 times, then mercenary 
somebody else can build the same functionality and performance as well. 
 Plop it onto a USB interface chip, sell for $15 and balance is restored

---eric

--
Speech recognition in use.  Incorrect endings, words, and case is
closer than it appears
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: [camram-spam] Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-30 Thread Alan Brown
On Tue, 30 Dec 2003, Eric S. Johansson wrote:

  But using your spam size, , the slowdown factor becomes roughly
 73 times.  So they would need 73 machines running full tilt all the time
 to regain their old throughput.

Believe me, the professionals have enough 0wned machines that this is
trivial.

On the flipside, it means the machines are burned faster.

 unfortunately, I think you making some assumptions that are not fully
 warranted.  I will try to do some research and figure out the number of
 machines compromised.  The best No. I had seen to date was about 350,000.

It's at least an order of magnitude higher than this, possibly 2 orders,
thanks to rampaging worms with spamware installation payloads
compromising cablemodem- and adsl- connected Windows machines worldwide.

AB




-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: [camram-spam] Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-30 Thread Jerrold Leichter
(The use of memory speed leads to an interesting notion:  Functions that are
designed to be differentially expensive on different kinds of fielded hardware.
On a theoretical basis, of course, all hardware is interchangeable; but in
practice, something differentially expensive to calculate on an x86 will remain
expensive for many years to come.)

In fact, such things are probably pretty easy to do - as was determined during
arguments over the design of Java.  The original Java specs pinned down
floating point arithmetic exactly:  A conforming implementation was required
to use IEEE single- and double-precision arithmetic, and give answers
identical at the bit level to a reference implementation.  This is easy to do
on a SPARC.  It's extremely difficult to do on an x86, because x86 FP
arithmetic is done to a higher precision.  The hardware provides only one way
to round an intermediate result to true IEEE single or double precision:
Store to memory, then read back.  This imposes a huge cost.  No one could find
any significantly better way to get the bit-for-bit same results on an x86.
(The Java standards were ultimately loosened up.)

So one should be able to define an highly FP-intensive, highly numerically
unstable, calculation all of whose final bits were considered to be part of
the answer.  This would be extremely difficult to calculate rapidly on an
x86.

Conversely, one could define the answer - possibly to the same problem - as
that produced using the higher intermediate precision of the x86.  This would
be very hard to compute quickly on machines whose FP hardware doesn't provide
exactly the same length intermediate results as the x86.

One can probably find problems that are linked to other kinds of hardware. For
example, the IBM PowerPC chip doesn't have generic extended precision values,
but does have a fused multiply/add with extended intermediate values.

Some machines provide fast transfers between FP and integer registers; others
require you to go to memory.  Vector-like processing - often of a specialized,
limited sort intended for graphics - is available on some architectures and
not others.  Problems requiring more than 32 bits of address space will pick
out the 64-bit machines.  (Imagine requiring lookups in a table with 2^33
entries.  8 Gig of real memory isn't unreasonable today - a few thousand
dollars - and is becoming cheaper all the time.  But using it effectively on a
the 32-bit machines out there is very hard, typically requiring changes to
the memory mapping or segment registers and such, at a cost equivalent to
hundreds or even thousands of instructions.)

-- Jerry

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: [camram-spam] Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-30 Thread Richard Clayton
On Tue, 30 Dec 2003, Eric S. Johansson wrote:

  But using your spam size, , the slowdown factor becomes roughly
 73 times.  So they would need 73 machines running full tilt all the time
 to regain their old throughput.

Believe me, the professionals have enough 0wned machines that this is
trivial.

On the flipside, it means the machines are burned faster.

only if the professionals are dumb enough to use the machines that are
making the stamps to actually send the email (since it is only the
latter which are, in practice, traceable)

 unfortunately, I think you making some assumptions that are not fully
 warranted.  I will try to do some research and figure out the number of
 machines compromised.  The best No. I had seen to date was about 350,000.

It's at least an order of magnitude higher than this, possibly 2 orders,
thanks to rampaging worms with spamware installation payloads
compromising cablemodem- and adsl- connected Windows machines worldwide.

the easynet.nl list (recently demised) listed nearly 700K machines that
had been detected (allegedly) sending spam... so since their detection
was not universal it would certainly be more than 700K :(

-
The Cryptography Mailing List

and in these schemes, where does our esteemed moderator get _his_ stamps
from ? remember that not all bulk email is spam by any means...  or do
we end up with whitelists all over the place and the focus of attacks
moves to the ingress to the mailing lists :(

moan
I never understand why people think spam is a technical problem :( let
alone a cryptographic one :-(
/moan

-- 
richard  Richard Clayton

They that can give up essential liberty to obtain a little temporary
safety deserve neither liberty nor safety. Benjamin Franklin

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-29 Thread R. A. Hettinga
At 11:49 AM -0800 12/28/03, Jim Gillogly wrote:
wouldn't it be preferable to prove that you've contributed
the same amount of power to a useful compute-bound project, such as
NFSNET.org or GIMPS or [EMAIL PROTECTED] or [EMAIL PROTECTED]

Simple economics. If you're going to go so far as using some cryptographic
proof of paying a transfer-price (work, good or otherwise :-)), you
might as well just pay a straight price to the recipient instead, in the
same way that contributed cycles for such efforts like the above -- and
open source software, for that matter -- would increase dramatically if
transaction costs were low enough to *pay* for such things as they're
produced.


Certainly the implicit price of free email keeps going up. I notice,
lately, that the less-than-a-year-old Bayesian filters on Eudora are
completely circumvented now by messages containing a word-salad of a
hundred random words or so and a web-bug graphic containing the spam
message inside. Frankly, I expect that the only thing of real value is the
web-bug itself, which proves that a message has been received by a working
email address, so it can be sold to other spammers in some greater-fool
market of email lists.



As most people here learned a long time ago, the only real way to solve the
spam problem is with good old fashioned cash, payable to the recipient of
the message: A white list for my friends, all others pay cash.

Everything else is just barter and transfer pricing. Though I might grant
that such stuff *might* make a good first step to some cash-settled
end-state, I personally think it's a waste of, well, time, if not actual
money. I suppose proving it doesn't work is worth something, I suppose.
And, now that I think of it, stuff like camram and hash cash *did* require
the invention of exchange protocol of some kind, which is, actually, quite
necessary to exchanging real money for service later on.


Which is one way of saying that doing cash-settled transactions for mail at
the SMTP-protocol level just not that hard anymore, people. And, the more
spam there is, the easier it becomes. Think of it as the charging of an
economic capacitor or something, and I think lots of people on this list
will be in a position to earn some serious money when it goes off.

Of course, it *would* be fun to calculate what the threshold transaction
cost might be to make this happen or something, but like all financial
experiments, this stuff must be observed in an actual market, or nobody
will believe the data anyway. It's just a matter of integrating, and not
necessarily writing, code, now.


Again, the cost of doing this keeps falling, and the cost of free email
keeps going up. Somebody's going to just stick a mint onto an online store
of value and see if it works someday. Then things are going to get
interesting.


Cheers,
RAH

-- 
-
R. A. Hettinga mailto: [EMAIL PROTECTED]
The Internet Bearer Underwriting Corporation http://www.ibuc.com/
44 Farquhar Street, Boston, MA 02131 USA
... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience. -- Edward Gibbon, 'Decline and Fall of the Roman Empire'

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-29 Thread Bill Stewart
At 09:37 PM 12/26/2003 -0500, Adam Back wrote:
The 2nd memory [3] bound paper (by Dwork, Goldber and Naor) finds a
flaw in in the first memory-bound function paper (by Adabi, Burrows,
Manasse, and Wobber) which admits a time-space trade-off, proposes an
improved memory-bound function and also in the conclusion suggests
that memory bound functions may be more vulnerable to hardware attack
than computationally bound functions.  Their argument on that latter
point is that the hardware attack is an economic attack and it may be
that memory-bound functions are more vulnerable to hardware attack
because you could in their view build cheaper hardware more []
Once nice thing about memory-bound functions is that,
while spammers could build custom hardware farms in Florida or China,
a large amount of spam is delivered by hijacked PCs or abused relays/proxies,
which run on standard PC hardware, not custom, so it'll still be slow.
Penny Black or any other system that involves tweaking the email protocols
gets a one-time win in blocking spam, because older badly-administered
mail relays won't be running the new system - if their administrators
upgrade them to support the new features, hopefully that will turn off
any relay capabilities.  That doesn't apply to cracked zombie machines,
since the crackers can install whatever features they need,
but at least all of those Korean cable-modem boxes won't run it.




-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Microsoft publicly announces Penny Black PoW postage project

2003-12-28 Thread Steve Schear


http://news.bbc.co.uk/2/hi/technology/3324883.stm

Adam Back is part of this team, I think.

Similar approach to Camram/hahscash.  Memory-based approaches have been 
discussed.  Why hasn't Camram explored them?

steve

BTW, Penny Black stamp was only used briefly.  It was the Penny Red which 
was used for decades. 

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-28 Thread David Honig
At 09:13 AM 12/26/03 -0800, Steve Schear wrote:
http://news.bbc.co.uk/2/hi/technology/3324883.stm


Mr Wobber and his group calculated that if there are 80,000
seconds in a day, a computational price of a 10-second levy
would mean spammers would only be able to send about 8,000
messages a day, at most. 

Spammers are sending tens of millions of e-mails, so if they had
to do that with all the messages, they would have to invest
heavily in machines. 


Replace invest with trojan and remind Mr. W. that he
works for the major facilitator of trojaned machines.







-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-28 Thread Adam Back
I did work at Microsoft for about a year after leaving ZKS, but I quit
a month or so ago (working for another startup again).

But for accuracy while I was at Microsoft I was not part of the
microsoft research/academic team that worked on penny black, though I
did exchange a few emails related to that project and hashcash etc
with the researchers.

I thought the memory-bound approaches discussed on CAMRAM before were
along the lines of hash functions which chewed off artificially large
code foot-print as a way to impose the need for memory.  

Arnold Reinhold's HEKS [1] (Hash Extended Key Stretcher) key stretching
algorithm is related also.  HEKS aims to make hardware attacks on key
stretching more costly: both by increasing the memory footprint
required to efficiently compute it, and by requiring operations that
are more expensive in silicon (32 bit multiplies, floating point is
another suggestion he makes).

The relationship to hashcash is you could simply use HEKS in place of
SHA1 to get the desired complexity and hence silicon cost increase.

The main design goal of this algorithm is to make massively parallel
key search machines it as expensive as possible by requiring many
32-bit multiplies and large amounts of memory.

I think I also recall discussing with Peter Gutmann the idea of using
more complex hash functions (composed of existing hash functions for
security) to increase the cost of hardware attacks.


The innovation in the papers referred to by the Penny Black project
was the notion of building a cost function that was limited by memory
bandwidth rather CPU speed.  In otherwords unlike hashcash (which is
CPU bound and has minimal working memory or code footprint) or a
notional hashcash built on HEKS or other similar system (which is
supposed to take memory and generaly expensive operations to build in
silicon), the two candidate memory-bound functions are designed to be
computationally cheap but require a lot of random access memroy
utilization in a way which frustrates time-space trade-offs (to reduce
space consumption by using a faster CPU).  They then argue that this
is desirable because there is less discrepency in memory latency
between high end systems and low end systems than there is discrepency
in CPU power.

The 2nd memory [3] bound paper (by Dwork, Goldber and Naor) finds a
flaw in in the first memory-bound function paper (by Adabi, Burrows,
Manasse, and Wobber) which admits a time-space trade-off, proposes an
improved memory-bound function and also in the conclusion suggests
that memory bound functions may be more vulnerable to hardware attack
than computationally bound functions.  Their argument on that latter
point is that the hardware attack is an economic attack and it may be
that memory-bound functions are more vulnerable to hardware attack
because you could in their view build cheaper hardware more
effectively as the most basic 8-bit CPU with slow clock rate could
marshall enough fast memory to under-cut the cost of general purpose
CPUs by a larger margin than a custom hardware optimized
hashcash/computationally bound function.

I'm not sure if their conclusion is right, but I'm not really
qualified -- it's a complex silicon optimization / hardware
acceleration type question.

Adam

[1] http://world.std.com/~reinhold/HEKSproposal.html

[2] Abadi, Burrows, Manasse and Wobber Moderately Hard, Memory-bound
Functions, Proceedings of the 10th Annual Network and Distributed
System Security Symposium, February 2003

http://research.microsoft.com/research/sv/PennyBlack/demo/memory-final-ndss.pdf

[3] Dwork, Goldberg, and Naor, On Memory-Bound Functions for Fighting
Spam, Proceedings of the 23rd Annual International Cryptology
Conference (CRYPTO 2003), August 2003.

http://research.microsoft.com/research/sv/PennyBlack/demo/lbdgn.pdf


On Fri, Dec 26, 2003 at 09:13:23AM -0800, Steve Schear wrote:
 http://news.bbc.co.uk/2/hi/technology/3324883.stm
 
 Adam Back is part of this team, I think.
 
 Similar approach to Camram/hahscash.  Memory-based approaches have been 
 discussed.  Why hasn't Camram explored them?
 
 steve

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-28 Thread Ben Laurie
Steve Schear wrote:

http://news.bbc.co.uk/2/hi/technology/3324883.stm

Adam Back is part of this team, I think.

Similar approach to Camram/hahscash.  Memory-based approaches have been 
discussed.  Why hasn't Camram explored them?
They were only invented recently, and indeed, I've been planning to 
introduce them to the camram arena. I wonder if they're being discussed 
as a result of the pub conversation I had recently with a Microsoft 
person on this very subject?

One major advantage of memory-based proof-of-work over hashcash is that 
the variation between machines is much smaller (estimated to be a factor 
of 4 from slowest to fastest PCs, for example).

BTW, for those who don't know, SpamAssassin now supports hashcash.

Cheers,

Ben.

--
http://www.apache-ssl.org/ben.html   http://www.thebunker.net/
There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit. - Robert Woodruff
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Microsoft publicly announces Penny Black PoW postage project

2003-12-28 Thread Adam Back
Oh yes forgot one comment:

One down-side of memory bound is that it is memory bound.  That is to
say it will be allocated some amount of memory, and this would be
chosen to be enough memory to that a high end machine should not have
that much cache so think multiple MB, maybe 8MB, 16MB or whatever.
(Not sure what is the max L2 cache on high end servers).

And what the algorithm will do is make random accesses to that memory
as fast as it can.

So effectively it will play badly with other applications -- tend to
increase likelihood of swapping, decrease memory available for other
applications etc.  You could think of the performance implications as
a bit like pulling 8MB of ram or whatever the chosen value is.

hashcash / computationally bound functions on the other hand have a
tiny footprint and CPU consumption by hashcash can be throttled to
avoid noticeable impact on other applications.

Adam

On Fri, Dec 26, 2003 at 09:37:18PM -0500, Adam Back wrote:
 I did work at Microsoft for about a year after leaving ZKS, but I quit
 a month or so ago (working for another startup again).
 
 But for accuracy while I was at Microsoft I was not part of the
 microsoft research/academic team that worked on penny black, though I
 did exchange a few emails related to that project and hashcash etc
 with the researchers.
 
 I thought the memory-bound approaches discussed on CAMRAM before were
 along the lines of hash functions which chewed off artificially large
 code foot-print as a way to impose the need for memory.  
 
 Arnold Reinhold's HEKS [1] (Hash Extended Key Stretcher) key stretching
 algorithm is related also.  HEKS aims to make hardware attacks on key
 stretching more costly: both by increasing the memory footprint
 required to efficiently compute it, and by requiring operations that
 are more expensive in silicon (32 bit multiplies, floating point is
 another suggestion he makes).
 
 The relationship to hashcash is you could simply use HEKS in place of
 SHA1 to get the desired complexity and hence silicon cost increase.
 
 The main design goal of this algorithm is to make massively parallel
 key search machines it as expensive as possible by requiring many
 32-bit multiplies and large amounts of memory.
 
 I think I also recall discussing with Peter Gutmann the idea of using
 more complex hash functions (composed of existing hash functions for
 security) to increase the cost of hardware attacks.
 
 
 The innovation in the papers referred to by the Penny Black project
 was the notion of building a cost function that was limited by memory
 bandwidth rather CPU speed.  In otherwords unlike hashcash (which is
 CPU bound and has minimal working memory or code footprint) or a
 notional hashcash built on HEKS or other similar system (which is
 supposed to take memory and generaly expensive operations to build in
 silicon), the two candidate memory-bound functions are designed to be
 computationally cheap but require a lot of random access memroy
 utilization in a way which frustrates time-space trade-offs (to reduce
 space consumption by using a faster CPU).  They then argue that this
 is desirable because there is less discrepency in memory latency
 between high end systems and low end systems than there is discrepency
 in CPU power.
 
 The 2nd memory [3] bound paper (by Dwork, Goldber and Naor) finds a
 flaw in in the first memory-bound function paper (by Adabi, Burrows,
 Manasse, and Wobber) which admits a time-space trade-off, proposes an
 improved memory-bound function and also in the conclusion suggests
 that memory bound functions may be more vulnerable to hardware attack
 than computationally bound functions.  Their argument on that latter
 point is that the hardware attack is an economic attack and it may be
 that memory-bound functions are more vulnerable to hardware attack
 because you could in their view build cheaper hardware more
 effectively as the most basic 8-bit CPU with slow clock rate could
 marshall enough fast memory to under-cut the cost of general purpose
 CPUs by a larger margin than a custom hardware optimized
 hashcash/computationally bound function.
 
 I'm not sure if their conclusion is right, but I'm not really
 qualified -- it's a complex silicon optimization / hardware
 acceleration type question.
 
 Adam
 
 [1] http://world.std.com/~reinhold/HEKSproposal.html
 
 [2] Abadi, Burrows, Manasse and Wobber Moderately Hard, Memory-bound
 Functions, Proceedings of the 10th Annual Network and Distributed
 System Security Symposium, February 2003
 
 http://research.microsoft.com/research/sv/PennyBlack/demo/memory-final-ndss.pdf
 
 [3] Dwork, Goldberg, and Naor, On Memory-Bound Functions for Fighting
 Spam, Proceedings of the 23rd Annual International Cryptology
 Conference (CRYPTO 2003), August 2003.
 
 http://research.microsoft.com/research/sv/PennyBlack/demo/lbdgn.pdf
 
 
 On Fri, Dec 26, 2003 at 09:13:23AM -0800, Steve Schear wrote:
  http://news.bbc.co.uk/2/hi/technology/3324883.stm