stronger encryption for SSH keys

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

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

stronger encryption for SSH keys

Tags:

Encryption

Ssh

Openssl

Related

Recent Posts