[messaging] Bounding hash 2d preimage bits (was Re:...Test Data)
David Leon Gil
coruus at gmail.com
Wed Jul 23 16:59:07 PDT 2014
(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...
More information about the Messaging