6

I generate RSA key pairs mostly using the following command:

ssh-keygen -t rsa -b 4096 -C "someemail@hostname.com"

which produces a public-private RSA key pair. If I run this command again and again I get different key pairs.

  1. Will all the key pairs that ssh-keygen generates be unique (not taking collision into account at this point)?

  2. If yes, how does ssh-keygen assure that all key pairs that different people generate at different times are unique and do not end up being the same?

  3. If no, on what factors does the uniqueness of a key pair depend? Other than key length space, and PRNG.

8

Will all the key pairs that ssh-keygengenerates be unique (not taking collision into account at this point)?

Yes, every key pair will be unique, with well above 99.99999% probability. This is largely due to the size of the key space and the quality of the CSPRNG that is used (see below).

If yes, how does ssh-keygen assure that all key pairs that different people generate at different times are unique and do not end up being the same?

It makes no such assurances, but it is effectively guaranteed to be unique anyways. This is because the OS uses a high quality CSPRNG (Cryptographically Secure Pseudo-Random Number Generator) algorithm that is much more reliable (meaning, more unpredictable) than the out-of-the-box PRNG you get with most languages.

If no, on what factors does the uniqueness of a key pair depend? Other than key length space, and PRNG.

The uniqueness comes from the CSPRNG, not a "regular" PRNG. The difference is the choice of entropy.

A PRNG simply takes some seed (usually either "0" if a programmer is lazy, or some arbitrary measure, such as from time()), shuffles the bits around every time something asks for bits, then does more shuffling. It only "appears" to be random until you observe the output for some period of time, at which point you can determine (a) which seed was used, and (b) the next infinite number of outputs that will be observed from that particular PRNG.

A CSPRNG, by contrast, builds entropy the longer it runs. It does this by taking periodic readings from multiple devices and applying some pretty complicated abstractions to the incoming data to generate a pool of "random" bits. This means that if you're running a flavor of Linux when you loaded this answer, odds are some bits of this answer are now floating in your entropy pool (until they are used, at any rate).

Logically, of course, these bits are random in the sense that computers do not actually have the capability to do "random" things (they always precisely follow the instructions given to them), but they are nevertheless random in the sense that no generic algorithm devised by either man or machine can possibly hope to determine the original entropy numbers, which is being constantly replenished as random numbers are generated.

Since computers often receive different types of input from the network, disks, and so on in fairly unpredictable order (because of latency, retries, other physical characteristics of hardware), it would be impossible for two systems to be perfectly synchronized to the point where the CSPRNG would also be in sync. Similarly, it'd be impossible to predict the output of a CSPRNG unless you were literally debugging the kernel, and the very act of doing so, or trying to report the current state, would alter the state of the CSPRNG.

Of course, the official documentation is quite clear on this: it's all theoretical, as we have no way of proving that no key will ever be generated twice. However, the odds are so incredibly stacked against ever finding a random key that was a duplicate that one may as well say it is indeed impossible.

  • 4
    A. K. Lenstra et al. however found duplicates in practice. The cause they said was not known. IMHO it couldn't be excluded that that resulted from manipulations. See infoscience.epfl.ch/record/174943/files/eprint.pdf – Mok-Kong Shen Apr 19 '16 at 7:14
  • @Mok-KongShen I had a feeling I've seen that paper before. Things that are "impossible" tend to inevitably happen, of course, but at least we know people can't randomly accidentally stumble across the private key of, say, a specific CA, or something like that. The odds are simply stacked too far in favor of a serious breach like this ever happening. It's entirely plausible, though, that a user might stumble across some other user's private key over several years of random numbers being generated. Finding the match is the hard part. – phyrfox Apr 19 '16 at 8:05
  • I am afraid that I had not clearly formulated my last comment. By manipulations I meant malicious acts of hackers or other adversaries concerning the keys that the common users somehow obtain. See my post elsewhere: s13.zetaboards.com/Crypto/topic/7487358/1 – Mok-Kong Shen Apr 19 '16 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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