Security of passphrase-protected private key

Question

If an attacker obtains a private key that was created with no passphrase, he obviously gains access to everything protected with that key. How secure are private keys set up with a passphrase? If an attacker steals a passphrase-protected key, how hard it is to compromise the key? In other words, is a private key with a good passphrase secure even if accessed by an attacker?

Answer 1

With OpenSSL, OpenSSH and GPG/PGP the wrapping algorithm will be strong enough that you don't need to worry about it (and if you do need to worry about it then you have bigger problems, and this is the least of your worries).

Like any password or passphrase, it depends on the strength of the passphrase. A 40 character passphrase is as hard to brute force as a 256-bit key (since ASCII only uses 7 bits). The same rules for strong passwords apply here:

• Random is better
• Longer is stronger

Answer 2

Once an encrypted block of data is in the hands of an attacker, it is never secure forever - it's a question of how long and what means are available to crack it.

Here's things to consider:

• strength of wrapping algorithm - I'm willing to believe bahamat about OpenSSL, OpenSSH and GPG/PGP - these are fairly well-vetted components.

• size of key space - i.e. - size and complexity of password - the typical costs of brute force guessing apply. Of note, some forms of key storage limit the types of characters that can be used in a password - for example, JKS (the Java Key Store) eliminated quite a few special characters, reducing the potential size of the key space. Also be wary of systems that crop the key size to a certain number of characters.

• cost of the attempt how computationally expensive is it to attempt to unwrap the key? That will slow down the brute force attempt.

• what algorithm? - depends on how the secure file is stored - is it obvious what algorithm was used for encryption?

• is there available cipher text to compare with? how will the attacker know he's successful - what is his test mechanism? One of the more powerful elements of capturing a key store is that the attacker may be able to test his attempts without further detection by the system storing the key.

• how many resources are at the attacker's disposal? - generally threat analysis involves analyzing what the attacker's resources are. Does he have 1 computer? A bank of computers? And entire viral network of stolen CPU power at his disposal? Depends on whether you're talking about the 13 year old script kiddie next door or a rogue nation.

• how long until the key is changed? & how long must the data stay protected? - if it takes the attacker longer to crack the password store than the usefulness of the data inside the store, then the store is considered secure enough

Answer 3

According to Martin Kleppmann:

the [default OpenSSH] private key protection has two weaknesses:

• The digest algorithm is hard-coded to be MD5, which means that without changing the format, it's not possible to upgrade to another hash function (e.g. SHA-1). This could be a problem if MD5 turns out not to be good enough.
• The hash function is only applied once --- there is no stretching. This is a problem because MD5 and AES are both fast to compute, and thus a short passphrase is quite easy to break with brute force.

If your private SSH key ever gets into the wrong hands [and if it was passphrase-protected using the default OpenSSH settings and if] your passphrase is a dictionary word, it can probably be [decrypted] in a matter of seconds. ... But there is good news: you can upgrade to a more secure private key format, and everything continues to work!

He then goes on to explain how to use "PKCS#8" as per RFC 5208 to obtain a more securely encrypted private key:

$ mv test_rsa_key test_rsa_key.old
$ openssl pkcs8 -topk8 -v2 des3 \
    -in test_rsa_key.old -passin 'pass:super secret passphrase' \
    -out test_rsa_key -passout 'pass:super secret passphrase'

Answer 4

Encryption of OpenSSH private key is vulnerable?

Protecting a private key with a passphrase needs to be done carefully, as is usually the case in crypto matters. Generally the approach is to encrypt the private key with a symmetric algorithm using a key derived from the passphrase via a key derivation function. A classic example of a suitable key derivation function is PBKDF2 from RFC 2898 - PKCS #5: Password-Based Cryptography Specification Version 2.0.

According to Colin Percival's scrypt presentation, "OpenSSH uses MD5 as a key derivation function for passphrases on key files". From the context it seems that he's saying they don't use salts or iterations, which is scary given how fast brute-forcing is these days. There are a few different formats OpenSSH uses for storing private keys, so I'd like to know some more details and exactly what versions are affected, but that sounds like a far cry from PBKDF2 or the other iterated, salted techniques that have been around since 1978.

I see a reference claiming that PGP and GPG do use iteration/stretching techniques when protecting a private key stored in a file, but again don't know the details yet.