I have a github account: http://github.com/mwolfe38
which I just created a month or two ago for hosting some scripts I was working on at the time.
Just today I updated my virtualbox ubuntu guest OS on my work laptop (running windows xp) . I now have version 9.04 of ubuntu linux and it runs great.
So anyways, I installed git and went to clone my github repositories, and then remembered that I needed to generate an rsa public/private key first. So I ran the command
ssh-keygen
and proceeded to press enter through all the prompts (I don't bother with a passphrase). I've done this before and its fairly common to not use a passphrase (although as of a few months ago I noticed more and more sites encouraging using a passphrase). So anyways, I generate this 2048 bit rsa key (I had thought it was 1024 bit but I checked the man pages and it turns out 2048 is the default). I then took my new rsa key and added it to github, which complained that this RSA key was already taken. What? already Taken, that can't be.. I first thought that maybe I hadn't generated a new key and this one was from my old system somehow. So I checked on github that this key didn't match any of the keys I had already stored. Sure enough, it wasn't on there for my account.
Now I know ssh-keygen can't be completely random about how it generates ssh-keys but with a 2048 bit key shouldn't it be very very unlikely that two people have the same key? I know this problem involves the birthday paradox, meaning if you pick elements at random from a set N you only need a small percentage before it becomes likely you'll see the same value come up twice. Still, 2^2048 is pretty damn large number. I'm pretty sure statistically that given an even distribution you'd need only a few orders of magnitude less than the total before a match is likely to occur, and the number of ssh keys on github is likely to be in the millions at most (which is many many orders of magnitude less than 2^2048).
I'm going to have to review some statistics so I can show that the odds of this happening are basically 0, meaning it must be due to a flaw in ssh-keygen. This should never happen. Perhaps the debian folks have been applying more patches to ssh-keygen.
Wow! Someone else' private
Wow! Someone else' private key is revealed to you then. Please tell me if you have found that person.
nope
No I haven't found that person. I quickly regenerated a new keypair and didn't even bother to record the one which was a duplicate. I probably should have posted this on a mailing list for ssh-keygen or something to see if there was a known bug with the version I was using.. This happened like a year ago with a brand new version of ubuntu, I know that a couple years before that debian had submitted a bug to ssh-keygen making for easy dictionary attacks on keypairs created with that version, but I had a much newer version than that..
Interesting stuff. I've upgraded many systems since and added lots of keypairs but have never had the same error message again on github.
Mathematically speaking I probably have a much better chance of winning the lottery 5 times in a row than getting an existing 2048 bit keypair (if they were generated truly randomly).