<div dir="ltr">Hi Tom,<div><br></div><div>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)?</div>
<div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>Cheers,<br><br>Joe</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Jul 3, 2014 at 6:38 AM, Tom Ritter <span dir="ltr"><<a href="mailto:tom@ritter.vg" target="_blank">tom@ritter.vg</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">So I went and tried to do enough statistics to make me dangerous.<br>
There's a few things at play here.<br>
<br>
First off, an attacker generating random fingerprints (say, 4 random<br>
fingerprints) and trying to match a 2-bit fingerprint is not<br>
guaranteed to hit the one they're trying to match. True, they have<br>
the capacity to iteratively count up to all the fingerprints, but by<br>
randomly generating them, there is a chance they won't 'hit'.<br>
Similarly, an attacker generating 2^80 fingerprints is not guaranteed<br>
to match 80 of those bits on a fingerprint, even though they had even<br>
computation power to _count_ to an exact match for the first 80 bits.<br>
<br>
The odds of an attacker matching a 2-bit fingerprint (2^2<br>
combinations, 25% probability of an exact match for a single<br>
generation) in 4 trials, is 68.36%. This is calculated using the<br>
binomial distribution with number of trials n=4 and probability of<br>
success p=.25 (or 1/2^2). Look at "at least one success" at<br>
<a href="http://www.wolframalpha.com/input/?i=binomial+distribution+n%3D4+p%3D1%2F%282%5E2%29" target="_blank">http://www.wolframalpha.com/input/?i=binomial+distribution+n%3D4+p%3D1%2F%282%5E2%29</a><br>
<br>
The odds of an attacker matching (at least) X bits of a 126-bit<br>
fingerprint is given by the probability density function of binomial<br>
distribution: <a href="http://www.wolframalpha.com/input/?i=binomial+distribution+n%3D126+p%3D.5" target="_blank">http://www.wolframalpha.com/input/?i=binomial+distribution+n%3D126+p%3D.5</a><br>
Take the pdf from that and plug it into a sum from (say) 80..126 -<br>
that's the probability of matching at least 80 bits in a single<br>
generation: .00156280. Plug that probability into a binomial<br>
distribution with 2^15 (yes, 2^15 not 2^80) trials and you get an 'at<br>
least one sucess' rate of near 100%. Which makes sense. An attacker<br>
who can run 2^15 trials can match 80 of 126 bits pretty easily. (You<br>
match 63 on average in a single trial).<br>
<br>
We ratchet the difficulty, and say we're aiming for matching 90 of the<br>
bits. Sum of probability of matching at least 90 bits is<br>
8.22382x10^-7 <a href="http://www.wolframalpha.com/input/?i=sum%28x%3D90..126%2C+%281.17549*10%5E-38%29+*+binomial%28126%2C+x%29%29" target="_blank">http://www.wolframalpha.com/input/?i=sum%28x%3D90..126%2C+%281.17549*10%5E-38%29+*+binomial%28126%2C+x%29%29</a><br>
In 2^15 trials, probability of getting a result that matches 90 bits<br>
or more is ~2.7%<br>
<a href="http://www.wolframalpha.com/input/?i=binomial+distribution+n%3D2%5E15+p%3D%288.22382x10%5E-7%29" target="_blank">http://www.wolframalpha.com/input/?i=binomial+distribution+n%3D2%5E15+p%3D%288.22382x10%5E-7%29</a><br>
<br>
So I think these calculations can guide us in how many bits to flip.<br>
Experimenting shows me that 86 bits yields a 56% probability for 2^15<br>
trials. I'd love to ratchet that up to 2^80 trials, but it breaks WA<br>
=(<br>
<br>
<br>
<br>
But what about _specific_ bits instead of _any_ bits.<br>
<br>
What are the odds of any single random fingerprint generation matching<br>
the first 9 and last 9 bits of a 126-bit fingerprint? This is not a<br>
binomial distribution, it's just a straight .5^18, or 1/262144. The<br>
odds that an attacker who can generate 2^15 (again not 2^80, but 2^15)<br>
fingerprints will hit the 9+9 match is ~11.75%.<br>
<a href="http://www.wolframalpha.com/input/?i=binomial+distribution+n%3D2%5E15+p%3D1%2F262144" target="_blank">http://www.wolframalpha.com/input/?i=binomial+distribution+n%3D2%5E15+p%3D1%2F262144</a><br>
I'd love to ratchet that up to 2^80, but again, it breaks WA. =(<br>
<br>
But..... probabilities don't guide us to an attacker's methodology<br>
exactly. I'm not aiming to hit exactly 9 bits in the front and 9 bits<br>
in the back and if I don't get it then all my results are useless.<br>
Instead I'm going to save the 'best' fingerprints I see and go with<br>
the best one I get.<br>
<br>
But it can still guide us if we wanted it to. We could say "We're<br>
going to model an attacker who aims for a 50% chance of hitting his<br>
mark", and run a binomial distribution with n=2^80 trials, and adjust<br>
the probability p, looking for an answer of 50%. Then for each<br>
fingerprint type, we'd adjust p until we hit that 50%, with p being<br>
calculated as the probability of getting a match on a single<br>
generation for matching {any M bits of 126, matching the first and<br>
last N bits of 126, matching N 9-bit sequences, ...}<br>
<span><font color="#888888"><br>
-tom<br>
</font></span><div><div>_______________________________________________<br>
Messaging mailing list<br>
<a href="mailto:Messaging@moderncrypto.org" target="_blank">Messaging@moderncrypto.org</a><br>
<a href="https://moderncrypto.org/mailman/listinfo/messaging" target="_blank">https://moderncrypto.org/mailman/listinfo/messaging</a><br>
</div></div></blockquote></div><br></div></div>