[messaging] Test Data for the Usability Study

Michael Rogers michael at briarproject.org
Wed Jul 9 06:08:04 PDT 2014

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.


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

Version: GnuPG v1.4.12 (GNU/Linux)


More information about the Messaging mailing list