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.

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

share|improve this question
    
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 6:53

2 Answers 2

up vote 24 down vote accepted

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:

-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQDQ33ndDr5N/AI8y2PzrqGbadLeS5fSf2GsVJx2B2KxhazL2z5O
ufin+wjJ1hW12/zWyQs/9CFYQFrife+PrMUOdLitsmlD3l4lBQ29+XKsmPabtINP
JQ0n4dxgBGeFxTCd4lJwiysmVsXPnNrgQTcx2nirrIk1C7wSW9Ai9W3fZQIDAQAB
AoGBAKiKSvkW9nRSzzNjIwn0da7EG0UIVj+iTZwSwhVzLC32oVH1XTeFVKGnLJZA
y0/tbP2bSBqY0Xc2pp9v4yhZzr6/BUPX+N1FOW8Q5OXHMD4fXSixrX0vYOT8hQuC
ehTAXsStjkZqzCdCsKV9YIduTHoyjL2jG6QBvFQK7kHaYUwZAkEA+rp2b+eBDJrg
lqcPOE2HkCkQcReSW0OIoUgd2tIiPFL8HSNwKvvAAH+QBKL6jvecLswJneecon8Z
jsgn4K/EpwJBANVDultbYq/h3F5FbAQ4r6cMQ2ZmmhMFdt8rRvAdEz18CuobGvAQ
y31hU/InW0n+Z0oHCsIgyowSeCGwRLMJYRMCQGKDXQG+/k+Lku7emPZQUBFucQ1e
a5z8PfTQtxpBMj5thK2WPP5GiDwp4tZPiw8dbvpcJPMsC7k1Iz+cmT6JEUUCQBxz
X54mb+D06bgt3L4nbc+ERE2Z7H4TIYueM2V/C30NWktm+E4Ef5EnddJ9S6Fwbgkj
LV0+kKblI9+iq1eTLb8CQQC+QDF7Y1o4IpDGcu+3WhS/pI/CkXD2pDMJM6rGBgG6
g9D1VTPCx0LZAWK4GdmELhPM+0ePH4P24/VsJY4mvutQ
-----END RSA PRIVATE KEY-----

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

-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: AES-128-CBC,8680A1BEAE5661AAD8DA344B7495BCD4

4cvmuk8onrB5IQVRr6xRUBt6yRcjNUGcUWq0CcyX4p4iijANv/S7H5Ga8e5e+12m
k6UUt65mF54Ddh+WE4lHHy5yYEPa25tr/KBMErEhHJxYFiwRwgw/KoF2V8Cpgidd
BA5aeO+5/FmCiTkx/tGYbpE2emfcQ+oNdAKRhIEjIAfItrU4Bj2nQZdiiY0tFEfT
hn5HZ0X1i1yi63nxVGQH+oQQH9+ccPk87cIRLf3IK1B3M0J0j11XDhQdIXwAx9hV
52GXgkk0NX7EtT5Cq3x0Q513e70QA9ua1lt8yaCynkLrYKmMQQCKsLlJDSh+sUyu
ndiVl0g73cUPd962Tp/WCLOV4/DWShfZexfjoibjCkR81OVa9cguYITCXV3QGRCM
wo09DI/INOs1s6FS4ZKugpwgKEX6knh0Fo1i6DdVJQfeQvUo+MhbFjjK0SXT4QWc
4rlQv0Q1YoNn1EzFzsVwx7PhtU9wo4PU1978+582mrJBjteIN9a8z+7lZT1qKynD
BG3XUjnWAq4k5KUj5mEJkSSs2R2AIhHNiSmwmcuzHf67er1KrWvL+g8AXXJ8xLjh
P6ImJeMoEI7P2zb4FvSkQFF5SDjmaPNPpo6xe330EdSSWZTZtcgc9yH++I8ZX9Kb
0UnWic5HTZOx0VLqEqDw+iWufnUDMvq98tGD5c+BQqqofBZae5YNYfko1tCGoz/3
ZygMcOdRqRugur5SiCZnYCnIeQvVNi7nwfp2Bb3K0XMCr12IdeRDuoe45MzoG9zD
hLk0Y3VHS3eANvEsBMAwcyTBjgs8Q3bHdHwnPjVcAo3auOkyXUHZ7DEIxnmvVfaS
-----END RSA PRIVATE KEY-----

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:

-----BEGIN PRIVATE KEY-----
MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBANDfed0Ovk38AjzL
Y/OuoZtp0t5Ll9J/YaxUnHYHYrGFrMvbPk65+Kf7CMnWFbXb/NbJCz/0IVhAWuJ9
74+sxQ50uK2yaUPeXiUFDb35cqyY9pu0g08lDSfh3GAEZ4XFMJ3iUnCLKyZWxc+c
2uBBNzHaeKusiTULvBJb0CL1bd9lAgMBAAECgYEAqIpK+Rb2dFLPM2MjCfR1rsQb
RQhWP6JNnBLCFXMsLfahUfVdN4VUoacslkDLT+1s/ZtIGpjRdzamn2/jKFnOvr8F
Q9f43UU5bxDk5ccwPh9dKLGtfS9g5PyFC4J6FMBexK2ORmrMJ0KwpX1gh25MejKM
vaMbpAG8VAruQdphTBkCQQD6unZv54EMmuCWpw84TYeQKRBxF5JbQ4ihSB3a0iI8
UvwdI3Aq+8AAf5AEovqO95wuzAmd55yifxmOyCfgr8SnAkEA1UO6W1tir+HcXkVs
BDivpwxDZmaaEwV23ytG8B0TPXwK6hsa8BDLfWFT8idbSf5nSgcKwiDKjBJ4IbBE
swlhEwJAYoNdAb7+T4uS7t6Y9lBQEW5xDV5rnPw99NC3GkEyPm2ErZY8/kaIPCni
1k+LDx1u+lwk8ywLuTUjP5yZPokRRQJAHHNfniZv4PTpuC3cvidtz4RETZnsfhMh
i54zZX8LfQ1aS2b4TgR/kSd10n1LoXBuCSMtXT6QpuUj36KrV5MtvwJBAL5AMXtj
WjgikMZy77daFL+kj8KRcPakMwkzqsYGAbqD0PVVM8LHQtkBYrgZ2YQuE8z7R48f
g/bj9Wwljia+61A=
-----END PRIVATE KEY-----

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:

-----BEGIN ENCRYPTED PRIVATE KEY-----
MIICxjBABgkqhkiG9w0BBQ0wMzAbBgkqhkiG9w0BBQwwDgQIZT3rvVU85p0CAggA
MBQGCCqGSIb3DQMHBAgtYXWrNG+OYgSCAoCewt8WkgCDaBCSOoe88WTpV2haxUFW
iWkdJQtEkzkpYnwA0E0Bj5CBnSd3EdSRmup0rP9WxzdMe+qx2N+GGLTcmA7pMyBV
XK9OTdiixMWvlG64lrLFtQxoKaxo48zUVobLuRrtaVLvwZ7OpO4hA2zsl6qaWaV7
8GEiAWz28K3DIBDVr1CKpEdFf7epkC7e1/ojJDNAwPiE9rxkaqGHpogqJQKb5s8X
ZyGhVG3rPuwgOxhU5d1G7K6+N9wKYkZXiCmsoqZxD94M3QH8sM8YF41rxBsbPSJ/
7JgGQMOJQxxrdeHSAt5P1iasI7lNXa7HacTZl1nPDXpnpjKA5E/jNMf1EgV+sN3f
pL4GoFvw8zImOF4OHdo9KBz61oKFylQrGQM6WhCsTqsSVZxR0tH8ERSOhhWn2wmy
NgiagfVT4nED9XFInEwTKoXKUjTSOHUmbTl/HF637NrYjSBLgT/e+XBQBmFMSaNc
+KLlJRHpjB8QZ8cIdDFwVIYkmm4Po7h1uYob1d2/4saxjHrtZ8f7GqmT/SGXMpj5
eL0bXDXdjcapDkLx5X0/BYI3AYTlFXEZU0UJT8aad0Fiygw1bLVDR8yDl63Bthlb
gS15LhjqGYGhgX3tARS94HtBvlSAtgV6AB5QjEJfU7jgyu0lFn1hTULmwFJVkjj6
Oy2WeuHseOZ1X45V7DvNcS1iT7fttwQZoSvdks8WulsodpOr7sbtaJbsUUToTxIN
GtNQo9Ce/QAeONmSf8G9jbBURBmLH+kzzzptYcCsVaaUnWPpgebH/WJRa83quPw6
fwy3xZgg9pPHFBiFAG2c3Uuelat/eXhXdW74XlDgOIpmbMfsDxaVOiuM
-----END ENCRYPTED PRIVATE KEY-----

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

share|improve this answer
    
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
1  
Tom Leek has also described how to patch OpenSSL to increase iteration count. –  Lekensteyn Dec 25 '13 at 10:41
1  
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

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

To generate one, use pass the -o option to ssh-keygen, this will force the use of the new OpenSSH format. The resulting private key looks like:

-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAACmFlczI1Ni1jYmMAAAAGYmNyeXB0AAAAGAAAABCm1gDucj
atDrjXom9j2Hb8AAAAEAAAAAEAAAEXAAAAB3NzaC1yc2EAAAADAQABAAABAQCquRcOc4bw
...
59VrTpkgqVZYc88GJwFFU+8awxP0qm+ZBHdR/ZlcCHdYt4XmIbfIR8GPtNQQ84Ft7YbMTF
mqCJOcWg==                                                                 
-----END OPENSSH PRIVATE KEY-----

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

share|improve this answer

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.