Curve25519 Montgomery Format load destroys key

[soulseekah]

As per https://datatracker.ietf.org/doc/html/rfc7748#section-6.1 the public key is 32 random bytes, however, Montgomery loading does a reduction over the Prime Field 2^255 - 19 when loading which destroys the key. The tested vectors from the RFC happen to all be mod 2^255 - 19 so the tests pass fine. But here are valid keypairs generated by sodium_crypto_box_keypair which phpseclib Montgomery loaders are mangling up:

private 8426220e7a57dc8d685d3966e3a23600e32563ce6033e07d0c89dbb5bd296577
public 9d486149a3ab59e1342c031d9f88e3a75c89b6bc5e56719e04d9a14efc54776c

$k = phpseclib3\Crypt\EC::loadFormat('MontgomeryPrivate', hex2bin('8426220e7a57dc8d685d3966e3a23600e32563ce6033e07d0c89dbb5bd296577' ));
echo bin2hex($k->toString('MontgomeryPrivate'));
> 0426220e7a57dc8d685d3966e3a23600e32563ce6033e07d0c89dbb5bd29658a
echo bin2hex($k->getPublicKey()->toString('MontgomeryPublic'));
> ddf67d3d353e40fafa8814f86643c7f46a19a0418157784d7fb7d8bb2c29180d

The key got mangled by phpseclib3\Crypt\EC\Formats\Keys\MongomeryPrivate::load due to a reduction over 2^255-19 inside Curve25519::convertInteger.

8426220e7a57dc8d685d3966e3a23600e32563ce6033e07d0c89dbb5bd296577 mod 7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed is 0426220e7a57dc8d685d3966e3a23600e32563ce6033e07d0c89dbb5bd29658a

libsodium handles random keys perfectly well without destroying them:

$kp = sodium_crypto_box_keypair();
> 8426220e7a57dc8d685d3966e3a23600e32563ce6033e07d0c89dbb5bd2965779d486149a3ab59e1342c031d9f88e3a75c89b6bc5e56719e04d9a14efc54776c

$sk = sodium_crypto_box_secretkey( $kp );
> 8426220e7a57dc8d685d3966e3a23600e32563ce6033e07d0c89dbb5bd296577

sodium_crypto_box_publickey( $kp );
> 9d486149a3ab59e1342c031d9f88e3a75c89b6bc5e56719e04d9a14efc54776c

sodium_crypto_box_publickey_from_secretkey( $sk );
> 9d486149a3ab59e1342c031d9f88e3a75c89b6bc5e56719e04d9a14efc54776c

Keys generated in Curve25519 via phpseclib are also all reduced to the field, which is not correct as per RFC generated keys are 32-byte randoms without reduction in the field.

I've tested a couple of Python libraries and JS libraries all generated keys are random and if they don't fall into the 2^255 - 19 field they are mangled in phpseclib3.

Unfortunately the two random test vectors in the RFC fall in the field. I'd love to add the above keys as additional test vectors.

This is also an issue with MontgomeryPublic format. Its reverse is modded which makes even less sense.

[terrafrost]

So I think the problem is a little broader than this.

With the SECG prime field curves (eg. secp256k1, as used by bitcoin, NIST P-256, etc) the scalar / private key is supposed to be between 1 and p-1, where p is the same p as used in GF(p).

phpseclib enforces this by doing a reduction over p on the scalar. That works okay for the SECG prime field curves but as you noted it doesn't work so well for Curve25519.

The fact that this approach breaks valid keys for Curve25519 notwithstanding it also means that phpseclib can accept keys whose scalar is larger than it ought to be. Instead of failing phpseclib just does the modulo and trudges happily along. OpenSSL doesn't do this.

Example with phpseclib successfully generating a signature (with 4eb9cbd):

<?php
require __DIR__ . '/vendor/autoload.php'; 

use phpseclib3\Crypt\PublicKeyLoader;

$key = '-----BEGIN PRIVATE KEY-----
MIIEDwIBADATBgcqhkjOPQIBBggqhkjOPQMBBwSCA/MwggPvAgEBBIID6P//////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
//////////////////////////////////////////////8=
-----END PRIVATE KEY-----';

$private = PublicKeyLoader::load($key);
$sig = $private->sign('hello, world!');

echo base64_encode($sig);

Example with OpenSSL erroring out (with the same key):

<?php
$signature = '';
$key = '-----BEGIN PRIVATE KEY-----
MIIEDwIBADATBgcqhkjOPQIBBggqhkjOPQMBBwSCA/MwggPvAgEBBIID6P//////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
//////////////////////////////////////////////8=
-----END PRIVATE KEY-----';
openssl_sign('hello, world!', $signature, $key, OPENSSL_ALGO_SHA256);
echo openssl_error_string();

echo $signature;

I think the solution is to do the following:

1. make all private key classes load the scalar (dA) as a BigInteger instead of doing $components['dA'] = $components['curve']->convertInteger(new BigInteger($key, 256));
2. change the function definition of multiplyPoint in EC/Base.php from public function multiplyPoint(array $p, FiniteField\Integer $d) to public function multiplyPoint(array $p, BigInteger $d)

I'll need to figure out another way to check the size of the scalar and I'll need to update $curve->createRandomMultiplier() as well. For most curves it works well but for curve25519 and presumably curve448, as well, it doesn't.

I'll try to have something out next weekend. It's gonna take a little bit of time to implement all this and I got other stuff I gotta do this weekend.

Thanks for the bug report!

[terrafrost]

c4b571a should fix this.

Thanks!

[soulseekah]

Thank you!