[messaging] Test Data for the Usability Study

[Joseph Bonneau]

Hi Tom,

So am I correct in reading that your main concern is that an attacker able
to do 2^80 work can't always find an 80-bit match (by which we mean any
desirable type of match that has a probability of 2^-80 of occurring by
chance)?

You can think of the probability that something with a low probability 1/x
*doesn't* happen after x trials. In the limit as x -> infinity we have
(1-1/x)^x = 1/e ~= 0.36 (this is a related form of the classic limit which
led to the discovery of e). So most of the time an attacker doing 2^80 work
will in fact get a 2^80 match (or better). At this kind of scale the
probabilities go down pretty fast too. The probability of not getting a
79-bit match with 2^80 work is 1/e^2 ~=0.14 and in general not getting at
least an (80-k) bit match will have probability 1/(e^k). You have a 99+%
chance of getting at least a 75-bit match.

Personally, for the purposes of a usability experiment I wouldn't worry too
much about all this as the 80-bit attacker is a very rough approximation to
begin with; I'd just assume an 80-bit match can be found.

Cheers,

Joe


On Thu, Jul 3, 2014 at 6:38 AM, Tom Ritter <tom at ritter.vg> wrote:

> 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
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140707/f3e0b71e/attachment.html>