<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd"> <html><body> <span id="mailbox-conversation">(Apologies, I'm not sure understand that sentence after re-reading it.)<div><br></div> <div>Here's the tradeoff (for attackers using general-purpose hardware + a GPGU, FPGA, or ASIC accelerator):</div> <div><br></div> <div>Plain hashes: Best attack on general-purpose hardware is a parallel collision search against all targets at once.</div> <div><br></div> <div>If you use an ASIC -- like the Bitcoin ones -- you can hash at a rate much higher than feasible memory bandwidth to look up the hashes.[^gpu] The 'computational intensity' of an ASIC is too high.</div> <div><br></div> <div>(You can use this excess computational power more efficiently than just throwing it away; but it's hard to gain much on standard architectures.)</div> <div><br></div> <div>Plain hashes with leading zero bits: Factor of 2^nz more computational intensity for users and for attackers. <span style="-webkit-tap-highlight-color: transparent;">This factor is largely hidden for the attacker: it reduces the needed memory bandwidth. </span> </div> <div><br></div> <div>Hashes, salted uniquely: Best attack: parallel collision search per nonce. In general N times more expensive. (Hardware costs a little lower: Give each ASIC a unique target; no need for memory.) But the attacker is now paying all of the additional costs over a single-target attack. And it doesn't cost the users anything!</div> <div><br></div> <div>(So if you make single-target attacks more expensive, costs to the attacker increase at the same rate; if users have equipment similar to the attacker's, then the leading zero idea does increase cost as one would expect in this case.)</div> <div><br></div> <div><br></div> <div>I think there are really two cases: 1. You need unique identifiers/key ids for *programs* to use. Here, all that's needed is a sufficiently long hash. 2. People need fingerprints to verify other people. Here, don't throw away the other thing they know: Who the other person is. Use that to gain an advantage over attackers.</div> <div><br></div> <div><br></div> <div>[^gpu]: This, in fact, is still the case even on cheap GPUs today. (The really expensive GPGPU cards have sufficiently high memory-bandwidth that this is only true for really trivial hash functions.)</div> <div><br></div></span><br><br><span class="mailbox-reply"><blockquote class="gmail_quote"> <br>> De-genericizing attacks using 'nonces' in this way does not allow <br>> avoiding memory accesses, with their huge latency. <br><br>??? <br><br>How do you intend that the nonce be used? </blockquote> <blockquote class="gmail_quote"><br></blockquote> <blockquote class="gmail_quote"><br></blockquote> <blockquote class="gmail_quote"><br></blockquote> <blockquote class="gmail_quote"><br></blockquote> <blockquote class="gmail_quote"><br></blockquote></span> </body></html>