Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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?

share|improve this question

migrated from unix.stackexchange.com Apr 6 '11 at 20:14

This question came from our site for users of Linux, FreeBSD and other Un*x-like operating systems..

3 Answers 3

up vote 21 down vote accepted

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 28164 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, 2160. 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.

share|improve this answer
2  
That just made my head hurt. –  Steve Apr 6 '11 at 21:26
4  
yeah, but in a good way :D –  AviD Apr 6 '11 at 22:14
1  
Doesn't ssh-keygen use /dev/random, so it should be getting at least some of those bits from "real" random sources. –  Brendan Long Apr 7 '11 at 0:31
3  
+1 for rogue gorilla :-) –  Rory Alsop Apr 7 '11 at 7:55
1  
+1 for a correct, but approachable answer. And your beautifully understated description of a 8192 key space "(that's really a lot)" –  Scott Pack May 6 '11 at 17:24

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.

share|improve this answer

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.

share|improve this answer
1  
hehe, you're referring to Debian...? :D –  AviD Apr 7 '11 at 21:37
    
Who else could it be? Someone else fixed stuff than needed no fixing breaking it in the process? –  Bruno Rohée Apr 7 '11 at 21:59
    
Oh I see it all the time. Just usually not so counter-productive, and also not so high-profile... –  AviD Apr 7 '11 at 22:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.