SSH public key authentication -- always require users to generate their own keypair?

I was working with a partner today that I needed to upload files to my server using scp. I have passwords turned off in the server's SSH configuration, so I wanted them to use public key authentication. I generated the key pair for them on the server and gave them the private key and put the public key in the appropriate authorized_keys file.

After a bunch of problems with them setting up their job, they finally got a more experienced sysadmin involved on their end, and he scolded me for handling the key generation this way. He said that by giving them a private key generated on my system, I had enabled them to do a brute-force attack against other keys generated on the same server.

I even asked him "so if I have an account on a server, and I can log in with a password but I want to automate something and I generate a keypair on that system, does that then give me an attack vector for brute forcing other users' keys?" and he said yes.

I've never heard of this, is it true? Can anyone point me to a discussion of this attack?

Well... no, that's not correct in the vast majority of circumstances due to proper randomness generation on a system. However, it is theoretically possible for a server to generate randomness that has a bias if care is not taken by the developers (in the case of Linux, the kernel developers) to ensure that the randomness source is "good". If there is a bias in the randomness, an attack could be executed in faster-than-brute-force time on the server keys. However, that is much more of a theoretical issue than an actual one - in practice, weakness in the RNG (Random Number Generator) is a vastly less likely attack than a side-channel attack on the cryptographic software or gaining access to the server a different manner.

So, long story short, no, he's incorrect. Other than the fundamental cryptographic underpinnings (Are DSA keys generated by default? RSA?), one ssh key does not contain any information about any other ssh key generated on the same system.

The main point of a private key is that it is private to the user, and known only to the user. As a user I would not want other people generating my private key because that means someone else has access to my private key and therefore has opportunity to act is if they are me on systems which have the public half of that key set as valid credentials.

From your PoV you have more responsibility too. Not only do you need to keep you system safe such that inappropriate public keys can not be installed into places, but you have responsibility for keeping the private keys you generate safe through their entire life-cycle. If there is an undesirable action taken with a given key pair as authentication and the user knows someone else has (or had) a copy of the key or the key was transported in a less than perfectly secure manner then they can turn around (rightly or wrongly) and say that they kept their copy perfectly safe so it must be your copy that was compromised either at your end or in transit. This might sound like just arse covering, and this is because it is: from both your PoV and the users as you are making sure who is responsible for what is properly marked.

So whether or not the concerns raised by your expert are valid or not (by my understanding such attacks are theoretically possible, but to my knowledge far from practically implementable in the next generation or few unless a new serious hole in the math or general implementation is found (which is somewhat unlikely)), both when wearing my user hat and when wearing my admin hat I prefer users to be in full control of their private keys and admins (along with everyone else on the planet, of course) to not be permitted anywhere near them.

Even if you disagree with the above, the key transport issue is far from trivial: how can you be 100% sure that the private key has been seen by the intended user and only the intended user and has not been stored (intentionally or accidentally) in a less than secure manner (such as left in an email inbox or temporary file that the resulted from it being detached from said mail and unencrypted). If you use a secure transport method that requires the user to authenticate, how do you get the authentication details for that system to the user securely? There are of course ways to make the key transport matter "secure enough" (where "enough" very much depends on what the keys give people access to) for most uses, but if the user generates their keys and distributes the public parts then you do not have a key distribution issue to worry about in that sense at all (you just need to worry about the users keeping the private parts safe, but there is nothing that can stop a really careless user from being unsafe there so it is an issue no matter what you do).

One final note: one thing that could be an issue if your private keys are all generated in the same place is if that place is later found to have had a bad key generation setup, like the problem found in Debian/Lenny's OpenSSL package last year. In such a case you would have a job of work revoking and regenerating a lot of private keys. This might be part of your external expert's concern on the matter.

I'm pretty sure this is BS. Private should be generated randomly. So as long as there is no bias in this randomness there can't be a connection between different private keys.