-----BEGIN PGP SIGNED MESSAGE----- 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. http://www.wolframalpha.com/input/?i=1%2F2^80 http://www.wolframalpha.com/input/?i=sum%28x%3D117..128%2C%282.93874*10^-39%29*binomial%28128%2Cx%29%29 http://www.wolframalpha.com/input/?i=sum%28x%3D118..128%2C%282.93874*10^-39%29*binomial%28128%2Cx%29%29 > 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. Cheers, Michael -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iQEcBAEBCAAGBQJTvT60AAoJEBEET9GfxSfM+LcH/0jDNyZMAkgjqbo+DQ1axMI/ z3omfZlkozWaYAuqucakdKXfpyyUFYc7PYBBrwqkDV89FCdxrTmU4IDWPsSfIx1J +ZqEpi4ufVjFldn6zs1JnVxHPYFzS4C6ak0NZjruO5y8/o1HuMrLfZUd2R9GiU5l 3wmQZY0NNWsHQMRVAZADMiPn/JAgXxiU4e650Br+oV4mJXtjlEWxbHDcYx2FoEtr AqpNJq25WqmRH4jvCuZgTc07d777lHBzT2rDgX0YHmVFu6gjYbSrK9+ME/u6FqXe D/bWZE9KxEdSvFMcnTYbm4b2VOa71Lvb5m80FSNJWosxZpXtxDOjiSaDSzofM2A= =rnrj -----END PGP SIGNATURE----- _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
