Microsoft publicly announces Penny Black PoW postage project

[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
> > 
> > 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 majordomo at metzdowd.com

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