[messaging] Test Data for the Usability Study

[Tom Ritter]

So I went and tried to do enough statistics to make me dangerous.
There's a few things at play here.

First off, an attacker generating random fingerprints (say, 4 random
fingerprints) and trying to match a 2-bit fingerprint is not
guaranteed to hit the one they're trying to match.  True, they have
the capacity to iteratively count up to all the fingerprints, but by
randomly generating them, there is a chance they won't 'hit'.
Similarly, an attacker generating 2^80 fingerprints is not guaranteed
to match 80 of those bits on a fingerprint, even though they had even
computation power to _count_ to an exact match for the first 80 bits.

The odds of an attacker matching a 2-bit fingerprint (2^2
combinations, 25% probability of an exact match for a single
generation) in 4 trials, is 68.36%.  This is calculated using the
binomial distribution with number of trials n=4 and probability of
success p=.25 (or 1/2^2).  Look at "at least one success" at
http://www.wolframalpha.com/input/?i=binomial+distribution+n%3D4+p%3D1%2F%282%5E2%29

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

We ratchet the difficulty, and say we're aiming for matching 90 of the
bits.  Sum of probability of matching at least 90 bits is
8.22382x10^-7 http://www.wolframalpha.com/input/?i=sum%28x%3D90..126%2C+%281.17549*10%5E-38%29+*+binomial%28126%2C+x%29%29
  In 2^15 trials, probability of getting a result that matches 90 bits
or more is ~2.7%
http://www.wolframalpha.com/input/?i=binomial+distribution+n%3D2%5E15+p%3D%288.22382x10%5E-7%29

So I think these calculations can guide us in how many bits to flip.
Experimenting shows me that 86 bits yields a 56% probability for 2^15
trials.  I'd love to ratchet that up to 2^80 trials, but it breaks WA
=(



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

But..... probabilities don't guide us to an attacker's methodology
exactly.  I'm not aiming to hit exactly 9 bits in the front and 9 bits
in the back and if I don't get it then all my results are useless.
Instead I'm going to save the 'best' fingerprints I see and go with
the best one I get.

But it can still guide us if we wanted it to.  We could say "We're
going to model an attacker who aims for a 50% chance of hitting his
mark", and run a binomial distribution with n=2^80 trials, and adjust
the probability p, looking for an answer of 50%.  Then for each
fingerprint type, we'd adjust p until we hit that 50%, with p being
calculated as the probability of getting a match on a single
generation for matching {any M bits of 126, matching the first and
last N bits of 126, matching N 9-bit sequences, ...}

-tom