stronger encryption for SSH keys

Question

I configured my server to encrypt user passwords using 500,000 rounds of SHA-512.

The question is, how does the standard AES-128-CBC encrypted SSH private key stack up to that, provided the same (or similar length) password/passphrase is used? This must be a human-typeable passphrase, of course, and the lack of entropy in this is (hopefully) the weakest link here. My understanding is that key-strengthening will extend the effort required to brute-force the passphrase, no matter how weak the passphrase is.

It's clear to me that since the public key is public, and can be used to verify the private key, the security of that private key will depend on the passphrase (the length of the RSA key will not factor in to how easy it is to reveal it). I imagine that check would be quite fast, so I would ideally want to increase the number of rounds and use stronger cipher suites so that the process of bruteforcing the passphrase is slowed down.

How much extra security on the passphrase can be gained by using PKCS#8 for a SSH private key?

I'm also wondering about ways to potentially improve upon this. Is there a way to make this encryption

openssl pkcs8 -topk8 -v2 des3

use even more rounds than the default (and still be accepted by ssh)? Also, are there even stronger suites that can be used? I'm dealing with Centos 6.4 here for now (since I like kickstart scripts), so it's probably a good idea not to be messing with the secure program suite if I can help it, but maybe there exists an even stronger symmetric cipher suite than PKCS#8 that can be used?

One thing I noticed is that the PBKDF2 here doesn't seem to specify the underlying hash used. Looking at the list it doesn't get any better than SHA1 it seems.

I want to find a way to make the best use of the ~0.5 second tolerable for successful authentication to help maximize the amount of computation required for brute-forcing.

I guess if I really cared about strengthening I should be looking at scrypt, but there is no native support in the tools for it, so this can't be used for day-to-day SSH private key management (but it could be suitable for use in special applications).

Edit: Interesting. My encrypted private-key on CentOS looks like this:

-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: DES-EDE3-CBC,D3A046CD...

I suppose this isn't necessarily any worse than AES-128-CBC (which is what my Mac produced).

I think that the approach I will take is to carefully roll an `scrypt` based encryption for the initial rollout of systems (which may occur over initially insecure channels) in order to have the least known compromising exposure of identity, and then set the machines up to use the regular non-fancy crypto suites, because neither `/etc/shadow` nor `~/.ssh/id_rsa` ought to be accessible without physical access. Do note, however that the original question itself is about what happens **after** physical access is gained. — Steven Lu, Jul 21 '13 at 06:53

score 54 · Accepted Answer · edited Mar 17 '17 at 13:21

What happens for private key storage is a bit intricate because it involves several layers of underspecified crud accumulated over years and kept for backward compatibility. Let's unravel the mystery.

For its cryptographic operations, including private key storage (that which we are presently interested in), OpenSSH relies on the OpenSSL library. So OpenSSH will support what OpenSSL supports.

A private key is a bunch of mathematical objects which can be encoded in a structure which is, normally, binary (i.e. a bunch of bytes, not printable characters). Let's assume a RSA key. The format for a RSA private key is defined in PKCS#1 as an ASN.1 structure which will be encoded using the DER encoding rules.

Since a lot of crypto-related tools began their life in the early and mid-1990s and, at that time, email was most fashionable (the Web was still young), tools strived at using characters which could be pasted into an email (attached files were not yet common in these days). Notably, there was an early standard called Privacy-enhanced Electronic Mail, or "PEM". That standard was never really deployed or used, and other systems trumped it (namely PGP and S/MIME), but one feature of PEM stuck: a way to encode binary object into printable text. This is the PEM format. It looks like this:

-----BEGIN SOMETHING-----
Some-optional: headers

Base64+Encoded+Data==
-----END SOMETHING-----

So PEM is a kind of wrapper with the binary data being encoded in Base64, and header and footer lines added, which include a type (the "SOMETHING"). The "optional headers" is a later addition of OpenSSL, and it has never been standardized, so PEM-with-headers is documented only as "what OpenSSL does". OpenSSL documentation being what it is, this means that, in order to know what this process exactly entails, you have to dive in the dreaded OpenSSL source code.

Here is an unencrypted RSA private key, in PEM format:

As you can see, the type is "RSA PRIVATE KEY". The ASN.1 structure can be explored with openssl asn1parse:

$ openssl asn1parse -i -in keyraw.pem
    0:d=0  hl=4 l= 605 cons: SEQUENCE       
    4:d=1  hl=2 l=   1 prim:  INTEGER           :00
    7:d=1  hl=3 l= 129 prim:  INTEGER           :D0DF79DD0EBE4DFC023CCB63F3AEA19B69D2DE4B97D27F61AC549C760762B185ACCBDB3E4EB9F8A7FB08C9D615B5DBFCD6C90B3FF42158405AE27DEF8FACC50E74B8ADB26943DE5E25050DBDF972AC98F69BB4834F250D27E1DC60046785C5309DE252708B2B2656C5CF9CDAE0413731DA78ABAC89350BBC125BD022F56DDF65
  139:d=1  hl=2 l=   3 prim:  INTEGER           :010001
  144:d=1  hl=3 l= 129 prim:  INTEGER           :A88A4AF916F67452CF33632309F475AEC41B4508563FA24D9C12C215732C2DF6A151F55D378554A1A72C9640CB4FED6CFD9B481A98D17736A69F6FE32859CEBEBF0543D7F8DD45396F10E4E5C7303E1F5D28B1AD7D2F60E4FC850B827A14C05EC4AD8E466ACC2742B0A57D60876E4C7A328CBDA31BA401BC540AEE41DA614C19
  276:d=1  hl=2 l=  65 prim:  INTEGER           :FABA766FE7810C9AE096A70F384D879029107117925B4388A1481DDAD2223C52FC1D23702AFBC0007F9004A2FA8EF79C2ECC099DE79CA27F198EC827E0AFC4A7
  343:d=1  hl=2 l=  65 prim:  INTEGER           :D543BA5B5B62AFE1DC5E456C0438AFA70C4366669A130576DF2B46F01D133D7C0AEA1B1AF010CB7D6153F2275B49FE674A070AC220CA8C127821B044B3096113
  410:d=1  hl=2 l=  64 prim:  INTEGER           :62835D01BEFE4F8B92EEDE98F65050116E710D5E6B9CFC3DF4D0B71A41323E6D84AD963CFE46883C29E2D64F8B0F1D6EFA5C24F32C0BB935233F9C993E891145
  476:d=1  hl=2 l=  64 prim:  INTEGER           :1C735F9E266FE0F4E9B82DDCBE276DCF84444D99EC7E13218B9E33657F0B7D0D5A4B66F84E047F912775D27D4BA1706E09232D5D3E90A6E523DFA2AB57932DBF
  542:d=1  hl=2 l=  65 prim:  INTEGER           :BE40317B635A382290C672EFB75A14BFA48FC29170F6A4330933AAC60601BA83D0F55533C2C742D90162B819D9842E13CCFB478F1F83F6E3F56C258E26BEEB50

We recognize here the components of a RSA private key: some big integers. See PKCS#1 for mathematical details.

It so happens that the PEM-extended format that OpenSSL uses supports password-based encryption. After some code reading, it turns out that encryption uses CBC mode, with an IV and algorithm specified in the headers; and the password-to-key transform relies on EVP_BytesToKey() (defined in crypto\evp\evp_key.c) with the following features:

This is a non-standard hash-based key derivation function.
The IV for encryption is also used as salt.
The hash function is MD5.
The hash is used repeatedly, for n iterations, but in the case of PEM encryption, the iteration count n is set to 1.

That the KDF is non-standard is a source of worry. Reusing the encryption IV for a salt is a minor worry (that's mathematically unclean, but probably not a real problem -- and, at least, there is a salt). Use of MD5 is also a minor worry (though MD5 is thoroughly broken with regards to collisions, key derivation usually relies on preimage resistance, for which MD5 is still quite strong, almost as good as new). The iteration count set to 1 (which means, no loop at all) is a serious issue.

This means that if an attacker tries to guess the password for a PEM-encrypted key, the computational cost for each try will be minimal. With a good GPU, that attacker could try several billions of passwords per second. That's way too fast for comfort. Password-based key derivation should be both salted and slow, and the OpenSSL PEM-encryption format fails on the second point. See this answer for a detailed discussion.

Here is a PEM-encrypted private key; encryption algorithm was set to AES-128. The password is "1234":

Because of the encryption, the bytes can no longer be analysed with asn1parse.

PKCS#8 is an unrelated standard for encoding private keys. It is actually a wrapper. A PKCS#8 object is an ASN.1 structure which includes some type information and, as a sub-object, a private key. The type information will state "this is a RSA private key". Since PKCS#8 is ASN.1-based, it results in non-printable binary, so OpenSSL will happily wrap it again in a PEM object.

Thus, here is the same RSA private key as above, as a PKCS#8 object, itself PEM-encoded:

As you see, the type indicated in the PEM header is no longer "RSA PRIVATE KEY" but just "PRIVATE KEY". If we apply asn1parse on it, we get this:

    0:d=0  hl=4 l= 631 cons: SEQUENCE       
    4:d=1  hl=2 l=   1 prim:  INTEGER           :00
    7:d=1  hl=2 l=  13 cons:  SEQUENCE       
    9:d=2  hl=2 l=   9 prim:   OBJECT            :rsaEncryption
   20:d=2  hl=2 l=   0 prim:   NULL           
   22:d=1  hl=4 l= 609 prim:  OCTET STRING      [HEX DUMP]:30820<skip...>

(I have cut a lot of bytes in the last line). We see that the structure begins by an identifier which says "this is a RSA private key", and the private key itself is included as an OCTET STRING (and the contents of that string are exactly the ASN.1-based structure described above).

PKCS#8 optionally supports password-based encryption. This is a very open format so it is potentially compatible with every password-based encryption system in the world, but software has to support it. OpenSSL supports old DES+MD5 encryption, or the newer PBKDF2 and a configurable algorithm. DES (not 3DES) is a minor issue: DES is relatively weak because of its small key size (56 bits) making a break through exhaustive search technologically feasible (it has been done); however, this would be quite expensive for an amateur. Still, it is better to use PBKDF2 and a better encryption algorithm.

Given a raw private key as shown above, here is an OpenSSL command-line which turns it into a PKCS#8 object, with 3DES encryption and PBKDF2 for the password-based key derivation:

openssl pkcs8 -topk8 -in keyraw.pem -out keypk8.pem -v2 des3

which yields:

So now that's an "ENCRYPTED PRIVATE KEY". Let's see what asn1parse can say about it:

    0:d=0  hl=4 l= 710 cons: SEQUENCE      
    4:d=1  hl=2 l=  64 cons:  SEQUENCE       
    6:d=2  hl=2 l=   9 prim:   OBJECT            :PBES2
   17:d=2  hl=2 l=  51 cons:   SEQUENCE       
   19:d=3  hl=2 l=  27 cons:    SEQUENCE       
   21:d=4  hl=2 l=   9 prim:     OBJECT            :PBKDF2
   32:d=4  hl=2 l=  14 cons:     SEQUENCE       
   34:d=5  hl=2 l=   8 prim:      OCTET STRING      [HEX DUMP]:653DEBBD553CE69D
   44:d=5  hl=2 l=   2 prim:      INTEGER           :0800
   48:d=3  hl=2 l=  20 cons:    SEQUENCE          
   50:d=4  hl=2 l=   8 prim:     OBJECT            :des-ede3-cbc
   60:d=4  hl=2 l=   8 prim:     OCTET STRING      [HEX DUMP]:2D6175AB346F8E62
   70:d=1  hl=4 l= 640 prim:  OCTET STRING      [HEX DUMP]:9EC2DF16920<skip...>

We see there that PBKDF2 is used. The OCTET STRING with contents 653DEBBD553CE69D is the salt for PBKDF2. The INTEGER of value 0800 (that's hexadecimal for 2048) is the iteration count. Encryption itself uses 3DES in CBC mode, with its own randomly generated IV (2D6175AB346F8E62). That's fine. PBKDF2 uses SHA-1 by default, which is not an issue.

It so happens that while OpenSSL supports somewhat arbitrary iteration counts (well, keep it under 2 billions to avoid issues with 32-bit signed integers), the openssl pkcs8 command-line tool does not allow you to change the iteration count from the default 2048, except to set it to 1 (with the -noiter option). So that's 2048 or 1, nothing else. 2048 is much better than 1 (say, it is 2048 times better), but it still is quite low by today's standard.

Summary: OpenSSH can accept private keys in raw RSA/PEM format, RSA/PEM with encryption, PKCS#8 with no encryption, or PKCS#8 with encryption (which can be "old-style" or PBKDF2). For password protection of the private key, against attackers who could steal a copy of your private key file, you really want to use the last option: PKCS#8 with encryption with PBKDF2. Unfortunately, with the openssl command-line tool, you cannot configure PBKDF2 much; you cannot choose the hash function (that's SHA-1, and that's it -- and that's not a real problem), and, more importantly, you cannot choose the iteration count, with a default of 2048 which is a bit low for comfort.

You could encrypt your key with some other tool, with a higher PBKDF2 iteration count, but I don't know of any readily available tool for that. This would be a matter of some programming with a crypto library.

In any case, you'd better have a strong password. 15 random lowercase letters (easy to type, not that hard to remember) will offer 70 bits of entropy, which is quite enough to thwart attackers, even when bad password derivation is used (iteration count of 1).

Fantastic! Thanks for taking the time to explain. So basically this means that the KDF used by PKCS#8 (as implemented by OpenSSL) is limited to SHA-1 at 2048 iterations only? Supposing the 3DES symmetric encryption part (the component present in encrypting the SSH private key, but not present during password login) is completely fine, then this means in my original question I'm comparing 2048 iters of SHA-1 to 500,000 iters of SHA-512. Would you agree this is a significant difference? Does the additional step of decryption reduce the bruteforcing speed enough to make it comparative to it? — Steven Lu, Jul 21 '13 at 16:43
I suppose one thing to take away from all this is that everything will be fine if I just extend my password a bit. — Steven Lu, Jul 21 '13 at 16:45
And furthermore I am realizing just how silly it is to worry about this exact problem (key strengthening) for use with users on a server. Since the time it takes to brute-force is exponential in the length of the password, just use a tried-and-proven method on your server, use a good password. When deploying a secure web application, where you cannot easily **force** people to use good passwords without detracting from user experience, use scrypt to get a few extra characters for "free" on everybody's password by trading in more susceptibility to DoS. — Steven Lu, Jul 21 '13 at 17:22
Tom Leek has also described [how to patch OpenSSL to increase iteration count](http://security.stackexchange.com/q/39896/2630). — Lekensteyn, Dec 25 '13 at 10:41
Note: `des3` is recommended by the manual page, but AES can also be used by specifying `-v2 AES-128-CBC`. — Lekensteyn, Dec 25 '13 at 11:26
An excellent answer by @tom-leek! I'd like to point out that this answer http://security.stackexchange.com/a/52564/46473 by @Lekensteyn covers newer versions of OpenSSH that support a better KDF and encryption natively in ssh-keygen. — zorlem, May 13 '14 at 03:00
I'd really like to see the same sort of analysis of putty's keygen... — Dustin Wyatt, Feb 03 '16 at 01:53
Really helpful info! Note that the KDF equals `MD5(password + salt)`, where salt is *the first 8 bytes* of the IV. — Mark, Jan 20 '17 at 16:17
Note: Keys created with `-v2 AES-128-CBC` are broken since OpenSSH 7.5, see [bug 2699](https://bugzilla.mindrot.org/show_bug.cgi?id=2699). Workaround: use the [new key format](https://security.stackexchange.com/a/52564/2630). — Lekensteyn, Mar 25 '17 at 15:26
@Lekensteyn: OpenSSH still reads those (and other OpenSSL) files just fine; the only problem in that 'bug' was a misleading error message when using the wrong password. PBE files _shouldn't_ open with the wrong password. // Also **update:** in OpenSSL 1.1.0 (2016) up commandline **`pkcs8 -topk8` now supports `-niter N`** — dave_thompson_085, Sep 27 '18 at 01:24
Minor correction about OpenSSL’s PKCS#8 support: In fact, even with the old (PBKDF1-based) encryption, more modes than DES+MD5 are supported. This includes the even more horrible DES+MD2, but also other combinations described in [PKCS#5 v2](https://datatracker.ietf.org/doc/html/rfc8018), e.g. using SHA1. These are still undesirable, of course. See the "PKCS#5 v1.5 and PKCS#12 algorithms“ section in the OpenSSL pkcs8 manpage. — F30, Jul 15 '21 at 12:10

Lekensteyn · Answer 2 · 2018-08-31T23:34:35.980

13

Newer OpenSSH client versions (>= 6.5) support a newer OpenSSH-specific private key format that uses a proper key-derivated function. Right now only bcrypt is supported as kdfname (see this specification document). This format is used by default since OpenSSH 7.8.

For older versions (< 7.8), pass the -o option to ssh-keygen, this will force the use of the new OpenSSH format. The resulting private key looks like:

This post mentions other considerations such as the use of a custom number of rounds with the -a option (see also the manual page of ssh-keygen).

If you have an old PKCS#8 key with a higher iteration count, decrypt it first and then convert it to the new format by setting a password:

# WARNING: /tmp/mykey will contain the unencrypted key.
# If /tmp is a tmpfs, this is ok.
openssl pkcs8 -in ~/.ssh/id_rsa -out /tmp/mykey
ssh-keygen -p -f /tmp/mykey
# validate the key and then move back:
mv /tmp/mykey ~/.ssh/id_rsa

edited Aug 31 '18 at 23:34

answered Mar 02 '14 at 21:45

Lekensteyn

5,958
5
38
62

There is no need to use a temporary file with the unencrypted key. [Try `ssh-keygen` over stdin](https://stackoverflow.com/a/36493479). – forest Aug 31 '18 at 23:47
@forest `ssh-keygen` only accepts one parameter (for both input *and* output) and for some options (such as `ssh-keygen -pf-`), the `-f -` option does not select stdin/stdout. – Lekensteyn Sep 01 '18 at 08:33
1

Ah, OK. Then I would at least suggest using `/dev/shm` which should be guaranteed to be tmpfs. – forest Sep 01 '18 at 20:26
@forest at least for Linux distributions, `/tmp` is often located on tmpfs (with systemd). For the sake of brevity I'll leave it at `/tmp` here. People who managed to go through the trouble of creating a PKCS#8 key probably have FDE so the unencrypted key should not hit the disk. (Even with tmpfs, there is a risk of writing stuff to disk when swap is enabled.) – Lekensteyn Sep 02 '18 at 10:49

stronger encryption for SSH keys

2 Answers2

Linked