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

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....

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

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

Bill Stewart wrote:

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.

do the math. d*b --- s where: d = stamp delay in seconds s = spam size in bytes b = bandwidth in bytes per second 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), they are still a few machine short of what is necessary to totally render stamps useless. Yes, maybe one spammer could muster a few machines to be a nuisance but that's the extent of it. When dealing with hardware acceleration, it becomes a hardware war. If they can make a custom hardware, Taiwan can make us USB stamp generators, postage goes to a period of rapid inflation, and the world goes back to where was before with no advantage to spammer's.

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.

again, work the numbers to figure out the basic model and where the threat roughly lives. Personally, I think that any system that tweaks the e-mail protocols basically loses for reasons of adoption and backwards compatibility. I've put a lot of effort into the camram implementation to create significant backwards compatibility without leaving someone vulnerable to spam. also, zombied machines are a threat but the beauty of any proof of work system is that the machine will start overheating if it's used too much and the CPU load will become noticeable to the user. So in a way, stand generating zombies might actually do the net some good and takeout these machines. or cause another blackout in New York State... ---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 majordomo@metzdowd.com