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.

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.

share|improve this question
2  
Note that this isn't actually about RSA. It's just about the private key format OpenSSH uses. –  CodesInChaos Apr 4 '12 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 '12 at 19:28
add comment

migrated from askubuntu.com Apr 4 '12 at 16:21

This question came from our site for Ubuntu users and developers.

3 Answers

up vote 7 down vote accepted

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.

share|improve this answer
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 '12 at 19:24
add comment

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.

share|improve this answer
    
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 '12 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 '12 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 '12 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 '12 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 '12 at 17:26
add comment

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

share|improve this answer
    
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 '12 at 19:05
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.