7

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.

cHao
  • 463
  • 1
  • 3
  • 10
  • 1
    No. From what I know, you're SOL. –  Sep 22 '10 at 17:40
  • How exactly was your XP box encrypted? Where you using EFS, or Truecrypt, or something else? – Zoredache Sep 22 '10 at 17:51
  • @Zoredache: It was encrypted with EFS, i assume. (I just checked the box in the file attributes that said "Encrypt this file to secure data" or something like that.) – cHao Sep 22 '10 at 17:54
  • @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. – Chris S Sep 22 '10 at 18:14
  • You could always start trying "000...0001", "000...0002", and so forth. Unless, that is, you need it within the next hundred years... :P – gWaldo Sep 22 '10 at 18:17
  • 1
    And you didn't [backup your EFS certificates](http://technet.microsoft.com/en-us/library/cc756891\(WS.10\).aspx)? If you use EFS again please read up about the EFS [Best practices](http://support.microsoft.com/kb/223316) – Zoredache Sep 22 '10 at 18:37
  • @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 Sep 22 '10 at 18:39

5 Answers5

14

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).

Chris S
  • 77,337
  • 11
  • 120
  • 212
  • So there's way more difference between the keys than just the passphrase used to encrypt them? – cHao Sep 22 '10 at 17:50
  • 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](http://en.wikipedia.org/wiki/Public-key_cryptography) – user9517 Sep 22 '10 at 17:59
  • @cHao, see my edit. Also, the passphrase only protects the private key, it doesn't do anything to the public key. – Chris S Sep 22 '10 at 18:04
5

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.

Richard
  • 826
  • 2
  • 8
  • 20
  • If i don't care about the old key, and just want another that can map to the same public key...same problem? – cHao Sep 22 '10 at 17:48
  • 1
    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. – Richard Sep 22 '10 at 17:53
  • 1
    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. – Shadur Feb 06 '16 at 14:36
4

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.

James L
  • 5,915
  • 1
  • 19
  • 24
  • 3
    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. – James L Sep 22 '10 at 17:57
  • I do have my old NTUSER.DAT, iirc. Would that be where HKCU is stored? – cHao Sep 22 '10 at 18:02
  • @cHao, yes; you can load the hive using regedit and navigate to that key to see if it's there. – Chris S Sep 22 '10 at 18:05
  • 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 Sep 22 '10 at 18:13
  • 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. – cHao Sep 22 '10 at 18:30
  • Judging by the upvotes for the comment I wish I'd put it in the initial answer! – James L Sep 22 '10 at 18:34
1

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.

Robbie Mckennie
  • 1,083
  • 1
  • 8
  • 21
DrDamnit
  • 348
  • 4
  • 16
  • 1
    I wouldn't say "completely impossible". Anything's possible given enough time and CPU power. :) But yeah, i could definitely see it being infeasible. – cHao Sep 22 '10 at 17:58
  • 4
    I think the term used is Computationally Infeasible – user9517 Sep 22 '10 at 18:08
  • 1
    It's not impossible, just Very Hard and it's designed to be hard. Periodically there are improvements in the quality of the attacks that can be brought to bear, and computers are always getting harder and faster, so the key length is made longer. PGP users used to use 512 bit RSA keys, and now 1024 is far more common. Statements of impossibility lead to over-confidence and hubris. Just settle for "designed to be far harder than you should be able to achieve". – Phil P Oct 13 '10 at 22:00
  • You are wrong to say that you can generate a public key from a private; this is equally difficult. – MadHatter Feb 17 '11 at 22:00
  • @MadHatter: [Apparently not.](http://serverfault.com/q/52285/48784) – cHao Mar 27 '11 at 12:40
  • cHao: sorry, what? Are you saying that generating a public key from a private is easier than vice-versa? – MadHatter Mar 29 '11 at 08:27
  • 1
    @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. – cHao Nov 21 '11 at 21:04
  • 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. – MadHatter Dec 01 '11 at 09:39
0

The only thing you can do quickly is generate a new set of private and public key sets and replace the public keys on the servers you are trying to access, however, to do this you must have physical access to the servers that you had the public keys stored on before.

If you don't have physical access to the machines it will be virtually impossible for you.

Also, even if you have physical access to the servers, if the hard drives or the area where the keys were stored are encrypted, again, it will be virtually impossible for you.

Doug Pan

Doug Pan
  • 1