Slow load of a password protected key

[scollovati]

It seems that unencrypting a password protected key is very slow. The same key, if not password protected is super fast to load. I've also tried to be as specific as possible in the loading, but I gained just a few milliseconds. The login method works fine and it is very fast.

I use PHP8.3, library 3.0.37 and all extensions are enabled (GMP, libsodium, DOM, openSSL). I use, for now, only ed25519 keys generated with openSSH.

Slow code (around ~2.4s):

$key = EC\PrivateKey::loadPrivateKeyFormat('OpenSSH', $_ENV['SSH_PRIVATE_KEY'], $_ENV['SSH_PASSWORD']);

Fast code (around ~0.06s):

$key = EC\PrivateKey::loadPrivateKeyFormat('OpenSSH', $_ENV['SSH_PRIVATE_KEY']);

I've read several issues here before posting, but I was not able to find a similar one.

[terrafrost]

Unfortunately, there's nothing that can really be done about that. The fact that encrypted OpenSSH private keys are supported at all is a small miracle. https://www.reddit.com/r/PHP/comments/vrcypr/my_php_port_of_some_js_code_is_24x_as_slow_as_the/ talks about some of the difficulty of getting them to decrypt in anything resembling a reasonable amount of time. ie. 2.4s is def more time than 0.06s but 2.4s is waaaay better than 24s.

To recap the reddit.com post, phpseclib needs a pure-PHP implementation of bcrypt for OpenSSH private keys because (for reasons elaborated in the reddit post) the existing implementations PHP provides aren't suitable, specifically for OpenSSH private keys.

As https://security.stackexchange.com/a/150624 elaborates, password hashing algorithms like bcrypt are designed to be slow. The slowness may not be perceptible when you're loading a key with a program implemented in C or assembly or whatever but PHP is neither C or assembly.

[scollovati]

Thanks for clarifiyng that. PHP is written in C, so a better native functionality is needed. Are you aware of any tracked issue in the repo https://github.com/php/php-src?
I've searched for similar requests but I was not able to find anything. Thanks!

[terrafrost]

No - I've not opened one. It's hard to know where an RFC would be required vs a GitHub issue.

I'd also be surprised if anyone has ever requested it because it's pretty niche. Unless you're working with encrypted OpenSSH keys it's not something that'd be all that useful.

Prob the best way for php-src to be modified would be to have password_hash modified to accept an additional option for PASSWORD_BCRYPT - basetext or some such. I think that's the only change that'd be needed. It'd prob be best to give me a few days to verify that that is indeed the only needed change before taking any action yourself.

[terrafrost]

So it looks like there are other changes that are needed.

With normal bcrypt the salt is 16 bytes long. In OpenSSH it's 64 bytes long.

So in the pseudo code at https://en.wikipedia.org/wiki/Bcrypt you have this:

block ← block xor saltHalf[(n-1) mod 2] //each iteration 

OpenSSH is removing the mod 2 bit, changing the above to this:

block ← block xor saltChunks[n-1] //each iteration 

Whereas saltHalf is salt split into 2x 64-bit chunks saltChunks is salt split into 8x 64-bit chunks.

Another change:

In wikipedia's EksBlowfishSetup method there's this:

   //This is the "Expensive" part of the "Expensive Key Setup".
   //Otherwise the key setup is identical to Blowfish.
   repeat (2**cost)
      P, S ← ExpandKey(P, S, password, 0)
      P, S ← ExpandKey(P, S, salt, 0)

OpenSSH does those in reverse order so you'll need to swap the two self::expand0state() function calls in phpseclib's bcrypt_hash() method.

Yet another change is that OpenSSH switches the endianness of the long (32-bit int)'s. So whereas phpseclib's bcrypt_hash() is doing pack('L*', ...$cdata) (it should prob be doing pack('V*', ...$cdata)) PHP's bcrypt is basically doing pack('N*', ...$cdata).

If the only change were the change from OrpheanBeholderScryDoubt (24 bytes) to OxychromaticBlowfishSwatDynamite (32 bytes) you could make that an optional third parameter to crypt() or an option for password_hash() but that's apparently far from the only change. And speaking of that change, if one were to update phpseclib's bcrypt code to produce identical output to crypt() you'd also need to change the inner for loop of bcrypt_hash() from $j < 8 to $j < 6.

Assuming you made all those changes - and assuming you made Blowfish::bcrypt_hash() public, then you'd still need to call it differently. eg.

$salt = '1234567812345678';
$pass = 'aaaaaaaabbbbbbbbccccccccddddddddaaaaaaaabbbbbbbbccccccccdddddddd';

// we concatenate $salt to itself so that it's 64 bytes long
echo encodeBase64(Blowfish::bcrypt_hash($pass, $salt . $salt . $salt . $salt)) . "\n";

// we concatente substr($pass, 0, 8) to $pass because that's what OpenSSH's bcrypt does
// the $2a$ part of the salt tells bcrypt to add a null byte to the end. as https://en.wikipedia.org/wiki/Bcrypt
// notes you're suppossed to "treat the password as cyclic" but if you're adding a null byte to the end you're
// essentially doing "\0" . substr($pass, 0, 7) vs substr($pass, 0, 8)
// some bcrypt implementations support $2$, which doesn't specify whether or not a null byte ought to be tacked
// onto the end or not, so of those that do support $2$ it's a tossup as to how it'd behave.
// $2x$ and $2y$ behave as $2a$ does w.r.t. the null byte. PHP doesn't support $2$
// the $06$ bit means that OpenSSH's implementation has a "cost" of 6
echo crypt($pass . substr($pass, 0, 8), '$2a$06$' . encodeBase64($salt));

// encodeBase64() is used vs base64_encode() because apparently bcrypt (well not OpenSSH's version because it doesn't do any "ASCII Armor" type stuff) uses it's own custom alphabet.

[terrafrost]

So if PHP were to incorporate the OpenSSH method into password_hash() prob the best approach would be to create a whole new algorithm - PASSWORD_OPENSSH - or some such. There are too many changes imho to repurpose PASSWORD_BCRYPT.

That said, you wouldn't necessarily need to fork every bcrypt function as https://github.com/openssh/openssh-portable/blob/master/openbsd-compat/bcrypt_pbkdf.c demonstrates. Like in that file the Blowfish_expand0state calls would need to be switched (among the other changes that'd need to be made) if you wanted to change that file to give the same output as PASSWORD_BCRYPT but nothing in Blowfish_expand0state itself has changed.

If you wanted to create a bug report or whatever to PHP that'd be cool. I kinda doubt php-src would implement a whole new algorithm just for phpseclib (I can't imagine anyone else really benefiting from such a change) but who knows.

[terrafrost]

I also have to say... the fact that OpenSSH made all those changes is kinda obnoxious. It's like they were going for security through obscurity. Like if I wanted to make a secure protocol one approach I could employ would be to make small trivial tweaks to SSH. So let's call this new company Acme Co. Instead of servers identifying themselves as SSH-2.0-whatever they could identify themselves as ACME-1.0. And instead of running on port 22 they could run on port 54134. And instead of using little endian or whatever endianness they use the opposite endianness. And whamo, nmap is now not going to find the server and metasploit exploits won't be able to run on it! Woo hoo! Security through obscurity at the expense of interoperability.

Also unhelpful is the fact that altho https://github.com/openssh/openssh-portable/blob/master/openbsd-compat/bcrypt_pbkdf.c mentions some of these changes it does not mention all of them.

[scollovati]

Got it. Hope that this issue at least was useful for documenting all the difficulties in decrypting openSSH keys.