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 <[email protected]> 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 > [email protected] > https://moderncrypto.org/mailman/listinfo/messaging >
_______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
