On Sat, May 31, 2008 at 2:32 PM, Yves Rutschle <[EMAIL PROTECTED]> wrote:
> On Wed, May 28, 2008 at 07:55:35PM +1200, Deane Sloan wrote:
>> Finally - how real is this concern? What is the probability that say a
>> 2048bit generated key could fall into the 32,767 keys in the metasploit
>> SSH example on unaffected systems?
>
> 32,768 = 2^15
>
> number of 2048 bit keys: 2^2048
>
> Probability that a "proper" key falls in the space of the
> "bad debian" keys: 2^15 / 2^2048 = 1 / 2^2033.
>
> That's a lot of zeros before the first non-zero digit.
Put differently, if you were to start generating keys now at a rate
of, say, 1000/s, how long would you have to wait before you got one of
the Debian keys? This is a fun math problem for probability theory
students.
The probability that the first key you generate is from the Debian set
is the probability shown above, call it p.
The probability that the second key you generate is known is (1-p)p,
the probability that the first one generated isn't known but the
second one is. Similarly, the third: p(1-p)^2. In general,
p(1-p)^(n-1) that it's the nth key.
The expected value is sum(xP(x)) for all values of x: sum_{x=1..inf}
(xp(1-p)^(x-1)).
Expanded:
1p(1-p)^0 + 2p(1-p) + 3p(1-p)^2 + 4p(1-p)^3...
For simplicity, let's define q to be 1-p: the probability that a
randomly generated key isn't known. The series becomes:
1(1-q)+2(1-q)q+3(1-q)q^2+4(1-q)q^3...
which is the same as
1-q + 2q-2q^2 + 3q^2+3q^3 + 4q^3-4q^4...
This reduces to
1+q+q^2+q^3...
This is the Maclaurin series for 1/(1-q) or 1/p:
http://en.wikipedia.org/wiki/Maclaurin_series
So the expected or average number of keys that will need to be
generated to get a single compromised key is 2^2033.
If we generate 1000 keys per second, every minute of every hour of
every day, python can tell us how many years this should take:
>>> 2**2033/1000/60/60/24/365
31273362428568397592339282651453150725927505483211674133457883903086002935187835628713902368959626676044355690433939619266697318127399331450487165278264227276952422607302843373297384824699247125847270814985691932082882361644413681612675805034740192979033275985559364836461601752345605100835466698544385055087087441932283729948709580608277506656401101528311256762947115091869664100469360191068701154131313187262849700051439632063137802627522490247771629992729670120799681243732768067704095846963793730355643106032512997622948135372447337202554569376369649862450650606037557559006417097486452568315050050L
-JP
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List openssl-users@openssl.org
Automated List Manager [EMAIL PROTECTED]
