Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

My problem is a common one: I deleted my SSH key, and forgot to set rm to point to a .trash file. I have the public key, and I need to get in this server. I am not doing this on anyone else's server. I have enough resources to do it, I just need a program.

share|improve this question
add comment

3 Answers

If it was possible (with existing technology) to rebuild the private key from the public key, then everybody would be doing it.

Asymmetric algorithms are designed to avoid that. In the case of RSA, rebuilding the private key from the public key is equivalent(*) to integer factorization, which is a hard problem whose difficulty raises quite sharply when the integer size is increased. Current world record for a non-special integer (i.e. a properly generated RSA key) is 768 bits and it took some substantial effort, estimated to about 2000 CPU-year. An important point is that part of the algorithm requires a system with a lot of very fast RAM (we are talking terabytes here), and nobody knows yet how to handle that part with existing technology in the case of a 1024-bit RSA modulus. We have some preliminary designs for specialized hardware which might achieve it, but would cost a lot (not mere millions of dollars) and be rather bulky.

Bottom-line is that you won't succeed in cracking your SSH key, even if you use the best available hardware.


(*) Cracking RSA, as in "computing a forged signature", is not proven equivalent to integer factorization; but rebuilding the private key is equivalent to factoring the modulus.

share|improve this answer
    
Thanks everyone for the answers! I realized that while SSH uses keys, I should be able to just go into SFTP and edit my authorized_keys file. –  Ian Carroll Mar 27 '13 at 18:38
    
EDIT: I realize that I can't do that. Oops! –  Ian Carroll Mar 27 '13 at 18:40
add comment

As other answers already tell you, forget about brute-forcing the key. It can't be done. Not in a million years (or at least not for a million dollars).

(Unless the key was generated with a buggy implementation.)

What you may be able to do, but even that is by no means assured, is recover the deleted file. Deleting a file only removes it from the directory listing, it doesn't wipe the file contents, so the contents may still be sitting around on the disk. The space is marked as free, so it may be reused by another file. So you must immediately stop writing to the disk. A dirty shutdown is preferable.

Make a copy of the partition containing the file and work from that copy, it's safer. Use a carving tool (TestDisk is a bootable Linux distribution that contains a good collection) to locate free blocks that contain something that looks like a private key file. It's very recognizable: the file begins with -----BEGIN RSA PRIVATE KEY-----. A private key file is less than one block long on most filesystems, so it won't be fragmented: once you find the first block, you have the whole thing.

You may or may not be able to find the private key file this way. It may already have been overwritten. Even if you do find it, expect to spend hours setting up your recovery environment and digging through deleted blocks. Arranging for an alternate way to access the server is likely to be less effort.

In the future, remember to make backups of all critical data such as private keys. Store them in a safe place, of course, but to remember that availability (keeping stuff accessible) is a security property, it's not all about confidentiality (keeping stuff inaccessible).

share|improve this answer
    
Actually, EXT3 deletes the whole file, writing it over with 0's. –  Ian Carroll Mar 27 '13 at 18:41
    
@IanCarroll No, it doesn't. That would make deletion needlessly slow. Ext3 only zeroes out the directory entry (the file name, its metadata and the location of the block table) and part of the block table. It doesn't zero the file data, so it is possible (but never assured) that you will be able to find the deleted data in the free space. –  Gilles Mar 27 '13 at 20:14
    
Ah, sorry! Didn't know that. –  Ian Carroll Mar 28 '13 at 21:50
add comment

The whole points of asymmetric encryption is that it is impossible to recover a private key from a public key. So what you want to do is completely unfeasible.

Generate a new key pair and forget about recovering the old one.

share|improve this answer
    
Impossible? There's nothing impossible in this world, but if I had 36 cores and 244GB's of RAM, is it feasible at all? –  Ian Carroll Mar 26 '13 at 16:22
3  
Actually, there are some things that are impossible with our current knowledge of the laws of physics. security.stackexchange.com/a/6149/10211 And no, unless you have access to a working quantum computer it isn't feasible. –  Terry Chia Mar 26 '13 at 16:25
    
I've got one in my basement, I'll fire it up now :) –  Ian Carroll Mar 26 '13 at 16:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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