Pure-PHP Implementation of X25519/Ed25519

[paragonie-scott]

Hi phpseclib team!

I've been working on sodium_compat for a while. I'm fairly confident that my curve25519 implementation is side-channel-free (it's a port of the ref10 code from libsodium, with care taken to side-step the risks of side-channels that I know of).

It has yet to be audited, but as a fallback to the PHP extension not being installed, it may be worthwhile to consider in the future.

The "get this audited" ticket resides at https://github.com/paragonie/sodium_compat/issues/8 if anyone is interested.

[terrafrost]

Do you know how Ed25519 compares to ECDSA? The curves are different - ECDSA uses NIST curves whereas Ed25519 isn't a NIST curve. But beyond that idk.

I have an implementation of DSA with support for a wide array of key formats (PKCS1, PKCS8, PuTTY, raw, etc) in my clone of phpseclib - I plan on doing ECDSA next (whilst modernizing phpseclib dev-master / 3.0) and had been thinking about doing Ed25519 after that. One question that I do not currently know the answer to is how much common code there'd be between ECDSA / Ed25519.

[paragonie-scott]

Do you know how Ed25519 compares to ECDSA?

The short answer is that it's more secure.

One question that I do not currently know the answer to is how much common code there'd be between ECDSA / Ed25519.

Pretty much zero. The NIST curves are Weierstrass curves, while Ed25519 is a Twisted Edwards curve. The formulas are different, with TE curves being easier to implement in constant-time. Additionally, thanks to the point compression scheme used by most (all?) Ed25519 implementations, you don't have to deal with invalid curve attacks. Ed25519 also uses deterministic nonces, so you'll never have to worry about leaking your secret key.

Our recent article about automatic updates had a section on public key digital signature algorithms and their order of preference.

Recommended for anyone curious in learning about these nuances: https://www.youtube.com/watch?v=l6jTFxQaUJA

[terrafrost]

Well I still want to do ECDSA lol. Like for algorithm negotiation for SSH2. ECDSA may be supported whereas Ed25519 isn't.

Also, some of the end goal is to have something like this:

PublicKey::load('...');

You don't have to know the format of the public key - it'd auto-detect that and return an RSA / DSA / ECDSA / EdDSA instance as appropriate. SSH2 (and X509 / CMS / etc) would then do a switch statement or something and do whatever needs to be done based on the object type that was passed to it.

But, anyway, I'll look into this EdDSA as time permits - thanks!

[paragonie-scott]

Well I still want to do ECDSA lol. Like for algorithm negotiation for SSH2. ECDSA may be supported whereas Ed25519 isn't.

That's fine. If possible, only support RFC 6979.

[terrafrost]

You can see what I've done for DSA here:

https://github.com/terrafrost/phpseclib/blob/dsa-test-1/phpseclib/Crypt/DSA.php

(RFC 6979 applies to DSA as well)

The signing method is here:

https://github.com/terrafrost/phpseclib/blob/dsa-test-1/phpseclib/Crypt/DSA.php#L386

My current thoughts on that are... if the CSPRNG is good then using RFC 6979 is unnecessary. Quoting the author of that RFC in post on crypto.stackexchange.com:

It so happens that having a good random generator is a tough requirement; some systems (especially embedded) do not have such a generator; it can also be quite inconvenient to make an external PRNG available to the signing engine (it's an extra parameter to pass through several API layers).

source: http://crypto.stackexchange.com/a/42551/

phpseclib (dev-master) uses your random_compat implementation and has it's own implementation as a fall back. Your random_compat implementation looks at /dev/random, openssl_pseudo_random_bytes (when appropriate), etc. If those aren't secure phpseclib is gonna be adversely impacted in more ways than just (EC|Ed)DSA signing (key generation would be affected, diffie-hellman key exchange, etc).

Now, I think the pure-PHP fallback could be improved upon. Right now it's a mix of a stream cipher with ANSI X9.31. But I think making that do HMAC_DRBG instead would prob be better (HMAC_DRBG is the basis of RFC 6979).

But that said, DSA is still under development! I don't have too much left to do on it. An RFC 6979 implementation of signing exists but is commented out. All the underlying methods (computek, bits2int, etc) are implemented already.

(also, if I'm gonna do the random approach, it'd probably be a good idea to include a unit test that attempts to sign twice and makes sure that the result is different for each one; with RFC 6979 it would be but if k is random it shouldn't be).

[paragonie-scott]

it'd probably be a good idea to include a unit test that attempts to sign twice and makes sure that the result is different for each one; with RFC 6979 it would be but if k is random it shouldn't be

Oh, definitely. Please do that.

RFC 6979 is a general recommendation. Given the presence of a CSPRNG we should be golden. Maybe something like this:

try {
    $nonce = random_bytes(/* number necessary here */);
} catch (Exception $ex) {
    // Fallback to RFC 6979 
}

...but like you said, there will be bigger problems if that did happen. Might be better to just let the Exception bring down the script (fail closed).

[terrafrost]

Might be better to just let the Exception bring down the script (fail closed).

Yah - that's not a bad idea. I figure I'll revisit that at some point lol. Lots of things I want to do in the mean time lol. dev-master isn't gonna be production ready any time soon lol.

I appreciate the feedback!

[paragonie-scott]

Hey @terrafrost sodium_compat v1.0 is out now if you'd like to use our X25519 or Ed25519 implementations.

• ParagonIE_Sodium_Compat::crypto_scalarmult() for ECDH over Curve25519
• ParagonIE_Sodium_Compat::crypto_sign_detached() / ParagonIE_Sodium_Compat::crypto_sign_verify_detached() for Ed25519

[terrafrost]

Thanks for the update and congrats on the release!

Right now and for the past few months I've been working on a total refactor of BigInteger.php. The Pure-PHP implementation is showing some pretty impressive speedup's for modular exponentiation. But more than that it's a lot more modularized. RunKit is also no longer needed to test the various modes. This is all part of an effort to make phpseclib 3.0 implement more modern coding practices.

I'm getting pretty close to being done with this. Maybe a few weeks out? idk. But once I'm done with that (and maybe a few small updates, like variadic functions, etc) I'm gonna move onto ECDSA and EdDSA (eg. Ed25519). Not only do I want phpseclib 3.0 to implement more modern coding practices but also more modern crypto algorithms.

Anyway, I appreciate the work that you do and thank you!

[terrafrost]

I was looking at the format for ECDSA private keys and it seems like that can support custom curves?

Quoting RFC5480,

specifiedCurve, which is of type SpecifiedECDomain type (defined in [X9.62]), allows all of the elliptic curve domain parameters to be explicitly specified.  This choice MUST NOT be used.  See Section 5, "ASN.1 Considerations".

[X9.62] defines additional options for ECParameters and ECDSA-Sig-Value [PKI-ALG].  If an implementation needs to use these options, then use the [X9.62] ASN.1 module.  This RFC contains a conformant subset of the ASN.1 module defined in [X9.62].

In spite of what the RFC says, however, OpenSSL supports the parameter:

https://wiki.openssl.org/index.php/Command_Line_Elliptic_Curve_Operations

Scroll down to the bottom and you'll see this:

Parameters and key files can be generated to include the full explicit parameters instead of just the name of the curve if desired. This might be important if, for example, not all the target systems know the details of the named curve. In OpenSSL version 1.0.2 new named curves have been added such as brainpool512t1. Attempting to use a parameters file or key file in versions of OpenSSL less than 1.0.2 with this curve will result in an error

This problem can be avoided if explicit parameters are used instead. So under OpenSSL 1.0.2 you could create a parameters file like this

(the text continues)

OpenSSL recently implemented EdDSA per https://github.com/openssl/openssl/issues/487 - it'll be interesting to see how they do the private keys for EdDSA as time permits.

ssh-keygen -t ed25519 does it's own format ( https://pastebin.com/kL8ftXuP ) but I'm pretty sure OpenSSL won't be using that format lol.

[terrafrost]

I'm also gonna play around with your shim as time permits. It looks like PHP 7.2.0alpha1 doesn't have libsodium support yet: https://bugs.php.net/74826

[terrafrost]

In my latest ECDSA stuff sodium_compat is being used. It doesn't look like libsodium / sodium_compat supports Ed25519 with contexts as discussed in RFC8032 so I do have my own Ed25519 implementation as well. I also plan on implementing Ed448 but that'll require a pure-PHP SHA-3 implementation so that'll take more time.

sodium_compat is about twice as fast as my own implementation in PHP64 mode. My implementation (in PHP64 mode) can create and verify a signature in 0.47s on my local machine whereas sodium_compat does it in 0.22s. In GMP mode my implementation can create / verify a signature in 0.07s (sodium_compat does not appear to use gmp).

My library supports EdDSA keys in the OpenSSH format (ie. the kind that ssh-keygen would generate), the PuTTY format (ie. the kind puttygen would generate), in libsodium format and in the format specified in this IETF Draft:

https://tools.ietf.org/html/draft-ietf-curdle-pkix-07

If libsodium / sodium_compat are being used the keys are converted from whatever format they were in to the libsodium format to facilitate libsodium's use.

Encrypted OpenSSH private keys are not supported for the same reason sodium_compat does not support Argon2i - it's too slow. OpenSSH uses a custom form of bcrypt that does bcrypt 128 times as I recall and encrypts a different string etc so PHP's bcrypt implementation cannot be used and since bcrypt uses a custom key expansion OpenSSL's implementation of Blowfish can't be used either.

One thing I do like about EdDSA vs ECDSA is that the specs discussing EdDSA actually discuss more optimal coordinate systems. Most discussions of ECDSA discuss how to do point addition and doubling using affine coordinates but it turns out that it's much faster to do ECDSA using jacobian coordinates. The EdDSA specs don't even bother discussing how to do stuff in affine coordinates. Their only discussion of point addition / doubling is in the context of the more optimal coordinate system.

I use the montgomery ladder for point multiplication and my API basically treats EdDSA and the SEC curves the same. eg. you do this:

//$ec = new ECDSA('secp256k1');
$ec = new ECDSA('Ed25519');

$message = 'zzz';
$signature = $ec->sign($message);
echo $ec->verify($signature, $message) ? 'good' : 'bad';

I also want to support curves the SEC curves over binary finite fields. I've designed the API in such a way that I believe it should be extensible enough to support this but idk for sure. I suppose one could debate the need for such an implementation given that curves over binary finite fields are pretty much utilized nowhere but idk it's still an intellectual curiosity lol.

[terrafrost]

Also, I'm not ready to make my code public yet. I just thought I'd post a progress report for anyone interested.

[paragonie-scott]

In GMP mode my implementation can create / verify a signature in 0.07s (sodium_compat does not appear to use gmp).

That's something I plan to support in the future, as an attempt to optimize my code.

[terrafrost]

From that link:

Sodium_Compat support for BCMath

You're liable to be disappointed with BCMath's speed. I'm not able to do benchmarks right now (I'm not at home lol) but if memory serves BCMath took 2-3x as long as PHP64. idk how it compares to PHP32 but I wouldn't be surprised if it was slower than PHP32 as well for elliptic curve stuff.

Overall, PHP's BCMath implementation is one of the worst bigint implementations I've ever seen. Like phpseclib's PHP64 / PHP32 implementations use base 2*31 / 2*26. GMP has limbs that probably do something similar but idk the GMP internals. BCMath otoh... last time I looked at it it looked like it was using Base-10. Which is just super inefficient.

[paragonie-scott]

You're liable to be disappointed with BCMath's speed.

That's what I was afraid of. GMP seems viable, however.