2
\$\begingroup\$

Given a public key, I want to generate a corresponding private key. I know this will take at least decades or centuries on average to achieve.

I am wanting to increase performance as my current code is not likely to finish within my lifetime. It does not need to use Bash or calling ssh-keygen as a new process each time if it increases performance.

The code I provide below:

  1. sets the public key I want to break into a variable named id_rsa_pub
  2. randomly generates new private keys until the public key matches the one I want to break
    1. provides status updates (shows number of attempts so far) after every 1000 attempts
  3. prints a message when a corresponding private key is found
## SETUP

# 1024 bits is the minimum allowed by my ssh-keygen
# Generate private RSA key (-t) with 1024 bits (-b) into id_rsa (-f) with no password (-N) and empty comment (-C)
# ssh-keygen -t rsa -b 1024 -f id_rsa -N "" -C ""

# Show details of public key
# ssh-keygen -l -f id_rsa.pub

# Simulate loss of private key
# rm id_rsa


## ACTUAL CODE

function generate_new_key() {
    # yes to overwrite old key
    yes | ssh-keygen -t rsa -b 1024 -f id_rsa -N "" -C "" -q > /dev/null
}

# Contents of id_rsa.pub I want to break
# I generated a new one randomly for testing, so it shouldn't contain any sensitive information
id_rsa_pub='ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAAAgQCvuSATmaLfCPvWIs5K2+dScg9e2l11EqU7mS0atteklEm9M8paYsUPu1/KzlQp+6MXCFy3rDAWX7GcIiGovpI4llGm5fFmSwUI6U2E6zy+v7IKu0KdjMeIfCuXi8JWX1HovYSz3id3yTQc/RrHwymdXTjXog0SFXugQvk4WFw+2w=='

generate_new_key

attempts=1

while [[ $(< id_rsa) != "$id_rsa_pub" ]]; do
    generate_new_key
    attempts=$((attempts + 1))

    if ((attempts % 1000 == 0)); then
        echo "Trying attempt #${attempts}"
    fi
done

echo "Corresponding private key saved in id_rsa after ${attempts} attempts"
\$\endgroup\$
1
  • \$\begingroup\$ 1024 bits are completely out of reach. For smaller keys, the best way to crack RSA is to factor the modulus, for which various techniques exist. If you do that then it takes 2^80 operations to complete. The SHAttered attack at 2^63 ops was equivalent to 6,500 years of single-CPU computations and 110 years of single-GPU computations. \$\endgroup\$ Commented Aug 9, 2023 at 15:22

1 Answer 1

1
\$\begingroup\$

Interesting exercise.

I would try to simplify things a bit. Use fingerprints instead of comparing whole keys. For example, here is how to get fingerprints for an existing key pair from file:

ssh-keygen -lf ~/.ssh/id_rsa.pub 
3072 SHA256:vtNNKQH3r+MhK5W4ZqUl9O6V/RZKOcoNK4QJQuxMjle kate@bastion (RSA)

ssh-keygen -lf ~/.ssh/id_rsa
3072 SHA256:vtNNKQH3r+MhK5W4ZqUl9O6V/RZKOcoNK4QJQuxMjle kate@bastion (RSA)

Different formats are possible, so choose one which you find suitable and stick with it.

When designing a brute force tool, I would usually keep track of the latest iteration value, whether it be an incremented number or the current position in a word list, so that you can resume the process after an interruption (or crash). Here you don't really care, because there is no "seeding" and each call to ssh-keygen will produce a "random" key.

For your purpose it could be interesting to use a different tool to generate keys in a deterministic way and I found this: https://github.com/mithrandi/ssh-key-generator. Introducing reproducibility by removing randomness in seeding can help in the early stages at least, while you're debugging and testing your program.

You could even write a unit test to validate your code based on static sample data.

But we agree the exercise is theoretical. It's unlike to complete in your lifetime.

If you add parallelism, there is a remote chance of success. But renting out the necessary resources on the cloud or from a calculus center won't come cheap.

Suggested improvement: don't write the key to file, don't read the key from file. Pipe the results instead.

Tip: openssl should be able to do the same as ssh-keygen. Have a look and compare performance.

\$\endgroup\$
5
  • \$\begingroup\$ "Use fingerprints instead of comparing whole keys": what does this achieve? Wouldn't the extra SHA 256 be slower than comparing the string directly and potentially cause collisions? (SHA 256 is 256 bits, but key is 1024 bits in example) \$\endgroup\$
    – hflvegmnc
    Commented Jun 25, 2023 at 15:22
  • \$\begingroup\$ "generate keys in a deterministic way and I found this": the README says "using any 32-byte input to generate a keypair ... and infeasible in others (DSA/RSA, probably)". The example I gave is RSA 1024, so not applicable. \$\endgroup\$
    – hflvegmnc
    Commented Jun 25, 2023 at 15:24
  • \$\begingroup\$ @hflvegmnc: that's the whole point of it: cause collisions although they are extremely unlikely to occur. It could be that my understanding is wrong, but if you generate a different key with the same moduli isn't it what we want? \$\endgroup\$
    – Kate
    Commented Jun 25, 2023 at 19:40
  • \$\begingroup\$ I mean collisions in the 256-bit fingerprints (fingerprint of key 1 might be the same as key 2, but with different primes). The cardinality of RSA-1024 primes is ~2^1001. 1001-256=745, so I expect that there are 2^745 collisions in the fingerprints if we go through every valid 1024-bit RSA key. That is, collisions are not "extremely unlikely" in this case, but with certainty, and extremely common. \$\endgroup\$
    – hflvegmnc
    Commented Jun 25, 2023 at 20:32
  • \$\begingroup\$ "If you add parallelism, there is a remote chance of success. But renting out the necessary resources on the cloud or from a calculus center won't come cheap." No, never. Would probably require more energy resources than available in our solar system, and electricity isn't that cheap anymore. \$\endgroup\$ Commented Aug 9, 2023 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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