Brute forcing ssh keys

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.