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

[Joseph Bonneau]

On Jul 22, 2014 2:50 PM, "Brian Warner" <warner at lothar.com> wrote:

> I've used a similar (but more hand-wavey) approach for estimating the
> cost of brute-forcing the PBKDF2 portion of the Firefox Account password
> stretch (which is supplemented with scrypt, since it turns out that
> PBKDF2 is insanely cheap)[1].


I prefer aggregating over time, just because the bitcoin exchange rate
moves (or has moved) much more quickly than the network hash rate.


> I went with instantaneous numbers,
> pretending that miners are perfectly rational, don't look at expected
> future value, and immediately sell their rewards for dollars. I measured
> USD/hash as = reward * price / (difficultyfactor * 2^32). It's currently
> 209 attodollars per hash, which comes out to US$250M for a 2^80 attack.
> (I'm probably off by a factor of two somewhere.. the double-SHA256 keeps
> winding up on the wrong side of my equation, but it's all
> order-of-magnitude guestimates anyways).
>

I ignored the double SHA-256, so my estimate would be more accurate if
divided in two for base SHA-256 operations.


> (note that Litecoin uses a somewhat-trivial scrypt, with parameters so
> low that GPU mining is actually a win)
>

Yes, they are trivial memory-wise, but they still take more CPU than double
SHA-256. They use scrypt with N=1024, so about 2*1024 basic crypto ops
(Salsa8 instead of SHA256). When you take that factor of 1000 out, you end
up back with about $1 billion for 2^80 basic crypto ops, and the difference
there is plausible with the smaller scale/efficiency of Litecoin and the
memory accesses which still aren't free.

It's never possible to precisely compare brute-force but we should try to
steer it around basic symmetric-key crypto block operations as a standard.
On which note, steering back to public key search, the cost of generating a
new public key when trying to come up with colliding fingerprints is far
more costly than the hash, so setting 80 bits is probably at least 1000x
more expensive than doing 2^80 SHA-256 ops.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140723/30c2304c/attachment.html>