What are the chances to generate the same ssh key?

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.

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.

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.