Is a passphrase-protected SSH private key susceptible to a dictionary attack?

Question

If I have a passphrase-protected SSH private key,

AND

if this passphrase is sufficiently random and long (say, 20-, 30-, 40-characters long, or even more!),

AND

if I make this private key of mine publicly available on the Net

THEN,

will it be practically possible for someone to be able to decrypt my private key from its corresponding public key (the latter being publicly available anyway).

My guess the answer is most likely going to be:

"The decryption effort and time taken will be totally dependent on the length and randomness of the passphrase chosen, and there is nothing inherent in SSH authentication algorithms/protocols that would speed up or slow down the decryption effort. Thus, in the current state-of-decryption-art, a 20+ characters long passphrase should be sufficient enough. Even Gmail et al are recommending passphrases much smaller in length."

But I'm not sure if this is the right answer, or if there are any other aspects to it that I need to worry about, etc.

If this SSH private key is really not practically decryptable, then I intend to protect it with a VERY long passphrase and then forget all about securing the key itself. I, for example, could store it in my Gmail inbox (letting even Gmail team see it), or even upload it on my personal website for my easy retrieval (say, when I'm travelling). Etc.

Answer 1

It is not the length of the passphrase which matters, but its randomness; namely, how much different it could have been. Length makes room for randomness, but does not generate it.

Symmetric encryption of SSH private keys is not very well designed; it relies on some old features of OpenSSL, which date from before password hashing was a properly understood problem. See this answer for a detailed analysis. Bottom-line is that attackers will be able to try potential passwords by the billion per second, unless you invest some effort into wrapping your key in a PKCS#8 object with PBKDF2 and enough rounds.

If you generate your passphrase as a sequence of letters, each chosen randomly and uniformly, you will get 4.7 bits of entropy per letter (because 26 is approximately equal to 2^4.7). To reach a decent protection level (say, 100 bits), you will need 22 letters... If you prefer to generate meaningful words, say among a list of 2048 "common words", then you will get 11 bits per word, and 9 words will get you to 99 bits of entropy. There again, each word must be chosen randomly, uniformly, and independently of the other words.

With PKCS#8 + PBKDF2 and one million rounds (OpenSSL would need some coaxing to produce that), you gain 20 bits (because 2²⁰ is approximately equal to one million).

Remember that remembering, indeed, can be tricky. You will remember a very long passphrase, but only if you type it often enough. If you don't, then forgetfulness is almost guaranteed. I suggest that you print your very long passphrase and store it in a bank safe (print with a laser printer, not an inkjet printer: ink from the latter can fade away rather quick). Or, simpler, cut the middle man and print the key itself on the paper which you put in the bank safe.

^{(*) Note: printing systems may keep a cached copy of past printing jobs. Removing all traces can be tricky. You could use a "manual printing" process with a pen and your hand... for really long-time storage, consider engraving on stone or some rust-resistant metal.}

Answer 2

This is a very interesting topic. One that has been answered before on Stack Exchange. Bruce Schneier is an acknowledged and accomplished expert on cryptography. You can find an article on the subject of brute force attacks here:

Why not use larger cipher keys?

The most interesting passages are reproduced here:

Longer key lengths are better, but only up to a point. AES will have 128-bit, 192-bit, and 256-bit key lengths. This is far longer than needed for the foreseeable future. In fact, we cannot even imagine a world where 256-bit brute force searches are possible. It requires some fundamental breakthroughs in physics and our understanding of the universe.

One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that k = 1.38 × 10⁻¹⁶ erg/K, and that the ambient temperature of the universe is 3.2 Kelvin, an ideal computer running at 3.2 K would consume 4.4 × 10⁻¹⁶ ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about 1.21 × 10⁴¹ ergs. This is enough to power about 2.7 × 10⁵⁶ single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2¹⁹². Of course, it wouldn't have the energy left over to perform any useful calculations with this counter.

But that's just one star, and a measly one at that. A typical supernova releases something like 10⁵¹ ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

I hope you find this of interest.

Answer 3

If this SSH private key is really not practically decryptable, then I intend to protect it with a VERY long passphrase and then forget all about securing the key itself.

Encrypted private keys are susceptible to brute-force attacks if they attacker can get his hands on your encrypted private key. And if he can't, then they're not. The encryption isn't magical; it's typically very ordinary triple-DES, and it's always an offline attack, so the attacker is free to use dedicated hardware.

Putting the encrypted key in Gmail box or Google Drive or Dropbox is probably safe enough. The list of people interested in your key doesn't overlap much with the list of people who have access to your Gmail account.

But displaying it publicly on your webpage is a little over-the-top. You're quite literally asking for someone to try to crack it. At the very least put in measures to prevent access to casual observers.

A 20-character alphanumeric password is about 120 bits, which can't be readily brute-forced by today's technology. But even still, a little common sense is probably in order.

Answer 4

This is an old question, but in case someone comes across this looking for answers, things have since changed:

 -o      Causes ssh-keygen to save private keys using the new OpenSSH
         format rather than the more compatible PEM format.  The new
         format has increased resistance to brute-force password cracking
         but is not supported by versions of OpenSSH prior to 6.5. Ed25519
         keys always use the new private key format.

(from the ssh-keygen man page)

Apparently, this uses bcrypt, which is considered a nice slow, strong KDF . While its fixed memory usage renders it more vulnerable to massively parallel attacks using GPUs, FPGAs, or ASICs than something like scrypt (which can be tuned to require abitrary amounts of memory to compute), it's worlds ahead the single round of MD5 that the old format uses.

In addition, you can use the -a option to specify the work factor used, which can be used to massively further increase the brute force resistance of the keyfile. This is worth experimenting with to find the highest tolerable value; I used 200, which on my old 2nd-gen mobile i7 takes about 2 seconds to decrypt.

For reference, here is a benchmark of what a top-of-the-line cracking rig in 2017 can do: ~100k guesses/sec across 8 top-end GPUs. This is with a bcrypt work factor of 5, which is much lower than what OpenSSH uses (which I believe is 16 by default? (it's an exponential scale; increasing the work factor by 1 doubles the hashing time) The relationship between -a's value and the actual bcrypt work factor is unclear.)