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

[David Leon Gil]

Michael: Agreed.

All these calculations raise an interesting point: What do we *mean*
when we say a "2^80 attacker".

If we're assuming an attacker who can, for each key exchange of
interest, do 2^80 hash evals, this is an attacker that *yearly* does a
huge amount of computation: Suppose that you need to perform the
computation in < 2^8 seconds. There are ~ 2^25 seconds per year, so
the attacker can do 2^97 hash-eval-equivalents per year.

Is this realistic?

Looking very quickly at Bitcoin (which I know fairly little about, so
take calculations with a grain of salt):

Right now log2(probability of solving a block) is ~ -66. The
difficulty is set so that blocks are found every 600 seconds. This
gives ~ 2^57 hashes per second, and thus 2^82 hashes per
year.[^bitops]

Does anyone have an estimate of the total cost of "mining" equipment
in use? (An upper bound for computational effort would then be
cost-per-hash * NSA's budget + Moore's law.)

(And does anyone know the comparable numbers for Litecoin, which uses
scrypt? Buying scrypt ASICs in bulk, the cost is $9 per chip. Each
chip does 2^20 scrypt[params=?] evals per second.)

[^bitops]: Btw, quick estimate is that SHA2-256 requires about 2^15
bitops, in the sense of djb's papers (if not optimized for partial
evaluation). So Bitcoin is doing perhaps 2^97 bitops per year. (This
makes 2^112 strength elliptic curves look rather dicey...)


On Wed, Jul 9, 2014 at 9:08 AM, Michael Rogers <michael at briarproject.org> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> On 03/07/14 14:38, Tom Ritter wrote:
>> The odds of an attacker matching (at least) X bits of a 126-bit
>> fingerprint is given by the probability density function of
>> binomial distribution:
>> http://www.wolframalpha.com/input/?i=binomial+distribution+n%3D126+p%3D.5
>>
>>
> Take the pdf from that and plug it into a sum from (say) 80..126 -
>> that's the probability of matching at least 80 bits in a single
>> generation: .00156280.  Plug that probability into a binomial
>> distribution with 2^15 (yes, 2^15 not 2^80) trials and you get an
>> 'at least one sucess' rate of near 100%.  Which makes sense.  An
>> attacker who can run 2^15 trials can match 80 of 126 bits pretty
>> easily.  (You match 63 on average in a single trial).
>
> I think you're right that the binomial distribution is the tool to use
> here, but there's another way we can use it.
>
> The probability of matching exactly x of 128 bits in a single attempt
> is P(X = x) = 2.93874 * 10^-39 * binomial(128, x). We can take the sum
> from x = b..128 to find the probability of matching at least b bits in
> a single attempt, P(X >= b) = sum(x = b..128, P(X = x)).
>
> Now, the attacker has 2^80 independent attempts. So we're looking for
> the value of b that makes P(X >= b) = 1/2^80. Or, since there's
> unlikely to be an integer value of b that's exactly right, we're
> looking for the highest value of b that makes P(X >= b) >= 1/2^80.
>
> By trial and error, that's b = 117.
>
> http://www.wolframalpha.com/input/?i=1%2F2^80
> http://www.wolframalpha.com/input/?i=sum%28x%3D117..128%2C%282.93874*10^-39%29*binomial%28128%2Cx%29%29
> http://www.wolframalpha.com/input/?i=sum%28x%3D118..128%2C%282.93874*10^-39%29*binomial%28128%2Cx%29%29
>
>> But what about _specific_ bits instead of _any_ bits.
>>
>> What are the odds of any single random fingerprint generation
>> matching the first 9 and last 9 bits of a 126-bit fingerprint?
>> This is not a binomial distribution, it's just a straight .5^18, or
>> 1/262144.  The odds that an attacker who can generate 2^15 (again
>> not 2^80, but 2^15) fingerprints will hit the 9+9 match is
>> ~11.75%.
>> http://www.wolframalpha.com/input/?i=binomial+distribution+n%3D2%5E15+p%3D1%2F262144
>>
>>
> I'd love to ratchet that up to 2^80, but again, it breaks WA. =(
>
> Fortunately, I don't think we need the binomial distribution for this
> case. As you say, the probability of each attempt matching b specific
> bits is simply 1/2^b, so a 2^80 attacker can expect to match 80
> specific bits. Half the remaining bits will also match, on average.
>
> Cheers,
> Michael
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.12 (GNU/Linux)
>
> iQEcBAEBCAAGBQJTvT60AAoJEBEET9GfxSfM+LcH/0jDNyZMAkgjqbo+DQ1axMI/
> z3omfZlkozWaYAuqucakdKXfpyyUFYc7PYBBrwqkDV89FCdxrTmU4IDWPsSfIx1J
> +ZqEpi4ufVjFldn6zs1JnVxHPYFzS4C6ak0NZjruO5y8/o1HuMrLfZUd2R9GiU5l
> 3wmQZY0NNWsHQMRVAZADMiPn/JAgXxiU4e650Br+oV4mJXtjlEWxbHDcYx2FoEtr
> AqpNJq25WqmRH4jvCuZgTc07d777lHBzT2rDgX0YHmVFu6gjYbSrK9+ME/u6FqXe
> D/bWZE9KxEdSvFMcnTYbm4b2VOa71Lvb5m80FSNJWosxZpXtxDOjiSaDSzofM2A=
> =rnrj
> -----END PGP SIGNATURE-----
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging