[messaging] Bounding hash 2d preimage bits (was Re:...Test Data)

[David Leon Gil]

(Apologies, I'm not sure understand that sentence after re-reading it.)


Here's the tradeoff (for attackers using general-purpose hardware + a GPGU, FPGA, or ASIC accelerator):




Plain hashes: Best attack on general-purpose hardware is a parallel collision search against all targets at once.




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.




(You can use this excess computational power more efficiently than just throwing it away; but it's hard to gain much on standard architectures.)




Plain hashes with leading zero bits: Factor of 2^nz more computational intensity for users and for attackers. This factor is largely hidden for the attacker: it reduces the needed memory bandwidth. 





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!




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







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.







[^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.)







> De-genericizing attacks using 'nonces' in this way does not allow

> avoiding memory accesses, with their huge latency.


???


How do you intend that the nonce be used?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140723/8e3efdba/attachment.html>