9

At this link there is a claim that if an RSA key has a strong passphrase security might be broken in a few hours if an attacker has the private key.

Is there something weak about the security of RSA keys that makes this possible? It would seem that strong passwords cannot be broken within a few hours so why is it that RSA keys can be broken in a few hours given the private key?

Just for the purpose of a comparison, a strong passphrase might reasonably be upper and lower case and digits and 15 characters, so a space of almost 8*10^26 and an unreasonably fast computer might try 10^9 guesses per second and if you have a cluster of them 10^12 per second. It would take 8*10^14 seconds or 25 million years to try them all.

Improve this question
2
  • 2
    Note that this isn't actually about RSA. It's just about the private key format OpenSSH uses.
    – CodesInChaos
    Apr 4, 2012 at 16:25
  • 3
    The linked article has some serious flaws. Like, if you use a computer that you don't control, even a strong passphrase won't help. IOW: don't use computers you don't trust absolutely. (Google for "keylogger")
    – Jürgen A. Erhard
    Apr 4, 2012 at 19:28

4 Answers 4

Reset to default
8

No, your SSH key can't be broken in a few hours if you choose a strong passphrase. I read the web page you quoted, and it is just bad writing that leaves a mistaken impression. The statement there is inartfully phrased. The website claims:

An SSH key passphrase is a secondary form of security that gives you a little time when your keys are stolen. If your RSA key has a strong passphrase, it might take your attacker a few hours to guess by brute force. That extra time should be enough to log in to any computers you have an account on, delete your old key from the .ssh/authorized_keys file, and add a new key.

That's phrased in a pretty confusing way. I suspect what they mean to say is that a good passphrase will take at least several hours to crack. In fact, a strong passphrase will take a lot longer than that to crack; probably days or years, or longer, depending upon how strong your passphrase is.

Because of poor phrasing, this web page might leave the impression that even if you choose a strong passphrase, an attacker could still recover your SSH key in at most a few hours. That is not correct. If you have a strong passphrase, it will take a long time for an attacker to recover your SSH private key.

Someone with permission to edit the web page should fix it to correct the confusing phrasing.

Improve this answer
1
  • 1
    I think you're correct. They're describing actions that you could take to mitigate the theft of your private key, so "might take your attacker a few hours" would be meant as a worst-case scenario for the amount of time you have to act. I'm not sure if their worst-case scenario involves NSA-level computational resources, unanticipated exploits, the attacker getting incredibly lucky, or what.
    – octern
    Apr 4, 2012 at 19:24
5

At least in my results from man ssh-keygen:

~/.ssh/identity

Contains the protocol version 1 RSA authentication identity of the user. This file should not be readable by anyone but the user. It is possible to specify a passphrase when generating the key; that passphrase will be used to encrypt the private part of this file using 128-bit AES.

So, the question about a stolen key's time to crack is a factor of the lesser of:

  • Time to crack AES itself
  • Time to crack your chosen password for AES encryption.

That second bullet also includes the reduction code and however many rounds it takes to turn your string of letters into a valid 128 bit key. AES itself is still considered a good symmetric algorithm. Thus, if you have a good passphrase, you'll be safe for more than "a few hours."

Improve this answer
2
  • The interesting question here is how the key is derived from the password. Does it use a salt? Does it use a slow KDF?
    – CodesInChaos
    Apr 4, 2012 at 19:05
  • SSH protocol version 1 was broken last century and should never be used. And OpenSSH's implementation had a unique keyfile format for v1, different from both 'old' and 'new' (since 2014) formats for v2, including the crypto.
    – dave_thompson_085
    Aug 3, 2019 at 13:20
4

The link you provide doesn't say anything about the strength of RSA keys or an attacker having your private key to start with. It refers to an entirely different thing: the strength of the passphrase that is used to control access to your RSA private key:

An SSH key passphrase is a secondary form of security that gives you a little time when your keys are stolen. If your RSA key has a strong passphrase, it might take your attacker a few hours to guess by brute force. That extra time should be enough to log in to any computers you have an account on, delete your old key from the .ssh/authorized_keys file, and add a new key.

Basically - if the attacker has access to the computer where you store your keys, they can try to brute-force your passphrase (not the key). If you've chosen a weak passphrase, then it can be guessed. Guessing the passphrase will allow the attacker to possess your RSA private key. And finally, if they possess your private key, then they can read messages that are encrypted just for you.

EDITED TO ADD: But the quote above is in serious error where it says that a strong passphrase might take an attacker only hours to guess by brute force. A truly strong passphrase should, as others have pointed out, take many many years to guess. I think the point they were trying to make is that the passphrase is the weakest link. If you choose a poor one it can be easily compromised. But if your passphrase is 65 random characters, then it cannot be guessed as they describe.

Improve this answer
5
  • Is the method SSH uses to protect its keys really so weak that even with a strong passphrase it only takes hours to break?
    – TwentyMiles
    Apr 4, 2012 at 16:58
  • @TwentyMiles it's not really the method of storage, but really how strong a passphrase you chose. This attack assumes they have unrestricted access to your console for the whole period. All the attacker is doing is basically trying different passphrases over and over until one works. If you chose "a" as your passphrase they'd get it on the first try.
    – Mark Beadles
    Apr 4, 2012 at 17:05
  • I understand that, what confuses me is that the text you quoted says "If your RSA key has a strong passphrase, it might take your attacker a few hours to guess by brute force." Normally if you protect something with a strong passphrase it should take a few billion years to compute, not hours.
    – TwentyMiles
    Apr 4, 2012 at 17:09
  • 1
    @TwentyMiles Ooohhhh...yes, I see you're point. (slaps forehead). They must have meant weak passphrase, or maybe were just wrong.
    – Mark Beadles
    Apr 4, 2012 at 17:12
  • 1
    I took a look at the man page for ssh-keygen and it says that the passphrase is used to encrypt the private keys with 3DES. Sounds to me like you were right, and the article was just written erroneously.
    – TwentyMiles
    Apr 4, 2012 at 17:26
0

Yes, SSH keyfile security is broken.

https://latacora.micro.blog/the-default-openssh/

OpenSSH by default uses MD5 to make the AES key to protect the SSH key. Even though it does use a salt MD5 as a key derivation function (KDF) just isn't good enough.

Also, a discussion of the above link: https://news.ycombinator.com/item?id=17682946

Improve this answer
5
  • Interesting that OpenSSH defaults to using a fast KDF for passwords, definitely a problem. I wouldn't go so far as to say that it's "worse than plaintext" though, some of us use passwords with over 60 bits of entropy, and some use over 100 bits. Even with trillions of guesses per second a 60 bit entropy password is going to take days to crack, not hours, and 100 bits of entropy isn't going to be cracked any time soon.
    – AndrolGenhald
    Jan 11, 2019 at 23:57
  • @AndrolGenhald Yes, I agree that it might not be "worse than plaintext". I didn't write the article I linked to, I just thought it was overall good coverage of the topic. I found the linked discussion super interesting as well. Mainly I posted so that information that is pertinent and wasn't widely known when others answered is here.
    – Gregory Arenius
    Jan 12, 2019 at 0:05
  • 1
    Have a +1 then. Only thing I take issue with is that MD5 is bad for a KDF. While I wouldn't really recommend it, there aren't any known issues with using MD5 in HKDF. The real issue is using a fast KDF with a password. HKDF with SHA256 would be a bad idea to use for a password too, but it's still a perfectly good KDF.
    – AndrolGenhald
    Jan 12, 2019 at 0:16
  • 1
    Your first link is dead, and my life isn't long enough to read ycombinator. But OpenSSH 7.8, released that same month (2018-08-23), changed the default to OpenSSH's 'new' format, which uses (much-better) bcrypt. New format was selectable with -o since 6.5 2014-01-29, but default only for ed25519 (for which there was no OpenSSL traditional format).
    – dave_thompson_085
    Aug 3, 2019 at 13:14
  • @dave_thompson_085 I fixed the link.
    – Gregory Arenius
    Aug 3, 2019 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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