Recover an SSH private key?

Question

I have an RSA key (generated by PuTTYgen) that's set up for logging in to a bunch of machines via SSH. Or rather, i HAD such a key. (The computer it was on crashed, to the point that a reinstall of XP was required. The private key file is encrypted by the file system, and now that it's basically on what looks like a whole other OS and user, whatever XP would do to decrypt the key apparently can't be done anymore.)

What i have left is an OpenSSL-compatible base64 of the public key (from one of the machines still set up to accept passwords), and of course the passphrase to the key. I might(!) still have an old backup of the registry from before the machine died as well, but would have to search for it. Either way, it sounds like it might not be possible to recover the key file itself. (If it is possible, that'd be great. But the prospects aren't looking good so far.)

Is there any way to recover the private key, if i can't recover the actual file that contained it? Perhaps by importing the public key into PuTTYgen or openssl and doing some reverse thing on it? Contacting all the admins involved and sending them new keys could be a pain, so that's pretty much a last resort.

Solution 1

Presently the only way of "recovering" the Private key from the Public key is by exhaustive search (brute force). The system was specifically designed this way so that you could issue your public key to anyone without worrying about them being able to figure out your private key.

Edit:
Warning! Simplified explanation ahead!

Assuming you had RSA keys (the most common), the public key has two number in it: n and e. The private key has the same n, and another number d. Originally there were two huge prime numbers p and q which were used to calculate n, d, and e so that n and e could encrypt a text; n and d could decrypt the cyphertext. You have n and e. You can factor n to figure out p and q; the problem is that n is a freaking huge number with tons of possible p and q numbers. Currently there is no known way to do this quickly; I'm not sure if hackers have even bothered with writing tools to try. So in essence, no it's realistically not possible.

When you assign a passphrase to a key, it just does a simple encryption on the private key stored on your computer. The public key isn't affected at all by this. The passphrases are relatively easy to break compared to the private key itself; so this should not be relied on for primary security (you should keep your private key in safe places only).

Solution 2

I'm pretty sure there's no way of recovering the private key if you have the public key - this would be a big security risk otherwise, because anyone with a public key would then be able to determine the private key from it.

Solution 3

If I understand correctly, you want to generate a compatible private key from the public key. If this was possible, the whole system would be pointless. If you do manage it, I'd like to know how to I generate my bank's private key from their SSL certificate.

Solution 4

It is absolutely impossible to recover a private key from a public key. You can generate a public from a private, but not the other way around. It is completely impossible, and is also the point of asymmetrical encryption.

View more solutions

Comments

[Admin]

No. From what I know, you're SOL.

[Zoredache]

How exactly was your XP box encrypted? Where you using EFS, or Truecrypt, or something else?

[Philip]

@cHao, was this computer on a domain with Active Directory Certificate services running? If so, your domain admin might have a key to recover the EFS encrypted files with.

[gWaldo]

You could always start trying "000...0001", "000...0002", and so forth. Unless, that is, you need it within the next hundred years... :P

[Zoredache]

And you didn't backup your EFS certificates? If you use EFS again please read up about the EFS Best practices

[cHao]

@Chris: No, it was on my old (personal) laptop. No domain, no admin aside from me. I posted here cause you guys would know more about encryption and/or recovering stuff than SU would. :)

[cHao]

If i don't care about the old key, and just want another that can map to the same public key...same problem?

[cHao]

So there's way more difference between the keys than just the passphrase used to encrypt them?

[Richard]

Yep. Public keys can be publicly available. So if I had a public key which you knew, and you could create a private key which mapped to my public key, you could pretend to be me, and therefore get access to anywhere using my keys for authentication, e.g. my servers.

[James L]

If PuTTY has stored the key in the registry, it will be under HKEY_CURRENT_USER\Software\SimonTatham\PuTTY - if you have a system state backup you might not be as SOL as it first looked.

[cHao]

I wouldn't say "completely impossible". Anything's possible given enough time and CPU power. :) But yeah, i could definitely see it being infeasible.

[user9517]

The passphrase is only there to protect your private key from being stolen or tampered with. The publik/private keypair are used as part of public key cryptography

[cHao]

I do have my old NTUSER.DAT, iirc. Would that be where HKCU is stored?

[Philip]

@cHao, see my edit. Also, the passphrase only protects the private key, it doesn't do anything to the public key.

[Philip]

@cHao, yes; you can load the hive using regedit and navigate to that key to see if it's there.

[user9517]

I think the term used is Computationally Infeasible

[cHao]

All i see in there are public keys for servers i've connected to, and session settings. The session settings don't seem to have keys set in them...but...LOL! The default settings point to an unencrypted file in \Program Files\PuTTY!

[cHao]

Guess i wasn't protecting stuff as much as i thought i was. :) Oh well. That tip to look in the old registry helped a lot.

[James L]

Judging by the upvotes for the comment I wish I'd put it in the initial answer!

[MadHatter]

You are wrong to say that you can generate a public key from a private; this is equally difficult.

[MadHatter]

cHao: sorry, what? Are you saying that generating a public key from a private is easier than vice-versa?

[cHao]

@MadHatter: Private key files tend to have enough info in them to recreate the public key. (OpenSSH files do, at least, and it'd seem Putty's PPK files do too.) While you can't take the actual key and derive the public key from it, if you have the key file, it apparently contains the private key plus the numbers used to generate both keys.

[MadHatter]

Fascinating, and thank you for drawing that to my attention. I stand by my assertion that recovering one key from just the other is equally hard in both directions, but it's clear that much more than just a private key is cached inside an SSH private keyfile.

[Shadur]

That's called a "key collission" and it's a very bad thing in cryptography, to the point where any algorithm that shows signs of it is pretty much immediately disqualified from use.