What are the chances to generate the same ssh key?

Question

I could generate ssh keys on the client like (without password):

ssh-keygen -b 8192 -t rsa -f /home/THEUSER/.ssh/id_rsa -P '' -v

and copy the generated id_rsa.pub to the server:

ssh-copy-id -i /home/THEUSER/.ssh/id_rsa.pub '-p PORTNUMBER SSHUSER@SERVER-IP-ADDRESS'

How much is the chance that someone would generate the exact same key with ssh-keygen? so that they could log in without password too!

I think it has a very low chance, but I want to know: how much is it?

Answer 1

The chance is very much lower than any of these events:

• The computer spontaneously catches fire during the key generation process.
• Great Britain is wiped out by a falling asteroid during the very same second.
• A rogue gorilla escaped from a zoo enters your living room and mauls you.
• You win millions of dollars at the lottery three times in a row.

So the basic conclusion is that you should not worry about getting twice the same SSH key: it really will not happen in your lifetime.

On a more theoretical point of view, there are about 2⁸¹⁶⁴ possible 8192-bit RSA keys (that's really a lot). However, ssh-keygen will use a pseudo-random number generator which works over a much more reduced internal seed, which depends on the operating system but will typically have size at least 160 bits. This reduces the number of possible keys to a much lower (but still huge) number, 2¹⁶⁰. Even with tremendous computing power (I am not talking about a bored student with a few dozens of PC; rather, think "Google"), probability of finding the very same key after a few years of effort is less than 2^-100. Comparatively, the events I list above can be estimated to occur with probabilities roughly equal to 2^-45, 2^-50, 2^-60 and 2^-71, respectively: these are billions of times more probable.

Of course, with a flawed PRNG, anything goes.

Answer 2

First, read up on the Birthday Attack, which will explain the coincidence and odds of there ever being two keys generated exactly the same. The odds of this are higher than the odds of you picking a key and seeing if anybody ever generated it. (How many people in the room were born on July 7th versus how many people in the room have the same birthday.)

Now, the odds of anybody ever generating YOUR key are 1/2^key_size. In the case of public key cryptography, 1/2^(bits_of_entropy). A 4096 bit RSA key is not expected to have 4096 bits of entropy. I'm not sure what the conversion is myself. A 128 bit symmetric key is expected to have 128 bits of entropy. (This is all ignoring attacks that may break individual rounds, etc.)

Now, that also doesn't take into account bad implementation like a very ugly OpenSSL bug.

But, basically, nobody will ever generate your individual key by accident, and probably not by attack either.

Answer 3

ssh-keygen uses OpenSSL's libcrypto BN_rand() function to generate starting point for key subprime generation, which itself use RAND_bytes() as a source of randomness. It happens in the gen_candidates() function of moduli.c of the OpenSSH source distribution.

On most platforms this will be pretty good quality randomness (what RAND_bytes() does is a bit platform dependant; for more info check rand_lib.c in OpenSSL distribution).

For all practical purposes, unless you happen to use a libcrypto whose PRNG got sabotaged by an overzealous and incompetent maintainer, collisions just won't happen.

Answer 4

Taken from research!rsc:

Last week, Debian announced that in September 2006 they accidentally broke the OpenSSL pseudo-random number generator while trying to silence a Valgrind warning. One effect this had is that the ssh-keygen program installed on recent Debian systems (and Debian-derived systems like Ubuntu) could only generate 32,767 different possible SSH keys of a given type and size, so there are a lot of people walking around with the same keys.

Many people have had fingers pointed at them, but it is not really interesting who made the mistake: everyone makes mistakes. What's interesting is the situation that encouraged making the mistake and that made it possible not to notice it for almost two years.

Like Jeff Ferland said in a former post: "Now, that also doesn't take into account bad implementation like a very ugly OpenSSL bug" (which indeed seems to be the same bug as mentioned above).

“In theory, there is no difference between theory and practice. In practice, there is.”, Yogi Berra