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

[Brian Warner]

On 7/21/14 3:26 PM, Joseph Bonneau wrote:

> Our argument is that you can estimate brute-force costs by looking at
> the total amount earned by miners over an extended period (all of 2013
> in our example), based on the USD value at the time the Bitcoins were
> earned.

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

My argument was that an ASIC that mines bitcoin efficiently (2*SHA256 on
counter-based fixed-size messages) could just as easily be designed to
run PBKDF2 (N*SHA256 on wordlist-generated messages). Getting wordlists
into an ASIC requires a lot more bandwidth than letting the chip run a
counter, so it might be most efficient if your defender uses a large N
(lots of iterations, so fewer guesses-per-second).

http://keywrapping.appspot.com/ is a little stretching-vs-attack-cost
app I put together to help us decide what PBKDF2/scrypt parameters to
use.

> With a little work this could also be patched to look at Litecoin
> data, or another scrypt-based formula

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

For non-trivial scrypt, I ran some benchmarks to find the most
cost-effective EC2 instance type (which was a spot-price c1.xlarge a
year ago), and estimated attack cost based on its hourly price. I'm sure
you could build something more efficient than fully-functional
computers, but I don't think it'd get you more than an order or
magnitude or two. For scrypt(N,r,p) = 64k,8,1 (which uses 64MB of ram,
and takes maybe 250ms on modern hardware) I got 1.2 picodollars per
operation, which makes a 2^80 attack cost 1.4 trillion USD.

cheers,
 -Brian


[1]: https://wiki.mozilla.org/Identity/CryptoIdeas/01-PBKDF-scrypt