(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?
_______________________________________________
Messaging mailing list
[email protected]
https://moderncrypto.org/mailman/listinfo/messaging
