Nice to see progress in ed25519 support in OpenSSL.
The only concern I'd have with basing the ed25519 implementation on the BoringSSL implementation of ed25519 is that it would be slower than the ed25519-donna implementation on Intel processors.

From a benchmark I did on an Intel core i7 processor:
BoringSSL (standard build):
5K signatures/second
2.2K verifications/second

Libsodium (ISC License):
18K signatures/second
7K verifications/second

BoringSSL (with optimisations enabled release build):
23K signatures/second
7.3K verifications/second

ed25519-donna (public domain):
42K signatures/second
12K verifications/second

As a comparison P-256 in OpenSSL 1.1.0e:
21K signatures/second
8.6K verifications/second

[contains a correction for Boringssl optimisations thanks to davidben]

There are licensing issues. We'll improve the speed over time.

@richsalz Thank you for your reply.
I wondered about the license issues. The ed25519-donna implementation is put into public domain. How can there be license issues with something that is put into public domain?

It's an unknown path, as opposed to someone explicitly signing the CLA. Shrug. Speed will be addressed later.

@yugits Are you building with optimizations on? BoringSSL's default standalone build is primarily intended for those of us working on it and produces a debug build.

@richsalz If it's public domain, and I took the code and submitted it under CLA, would that pass the legal requirements?

@davidben I added a correction for that in my previous post. I should also mention that the values are fluctuating and there's an error margin that should be taken into account. I might come back to that later.

I also tested this WIP by calling the ED25519_sign and ED25519_verify functions through EVP_DigestSign and EVP_DigestVerify and got signing and verification speeds that were similar to the BoringSSL release build with optimisations on.

Are there any plans to include the amd64 optimisations for ed25519 (see the amd64-51-30k and amd64-64-24k implementations) into BoringSSL?

amd64-51-30k. Assembly-language implementation for the amd64 architecture, using radix 2^51 and a 30KB precomputed table.
amd64-64-24k. Assembly-language implementation for the amd64 architecture, using radix 2^64 and a 24KB precomputed table.

Do you have any thoughts on ARM (NEON) specific optimisations for ed25519? Because there is an ARM assembly language implementation for X25519 available in BoringSSL, but there's no ARM assembly language implementation for ed25519.

Speaking about ARM...
From a benchmark I did on an ARM Cortex-A53:
Libsodium:
1482 signatures/second
549 verifications/second

BoringSSL (release build):
1785 signatures/second
573 verifications/second

ed25519-donna:
2256 signatures/second
720 verification/second

As a comparison, P-256 in OpenSSL 1.1.0e:
2029 signatures/second
790 verifications/second

PS: @floodyberry Do you know why ed25519-donna is faster than ref10 based implementations of ed25519 on an ARM processor?

My goal with this PR is to get the appropriate EVP API in place and see that it behaves as expected (test vectors and signature verification OK). To do that we need a low level implementation and the easiest was to just use what we already have: we'd actually removed Ed25519 code in the past because it was unused.

The internal API between OpenSSL and the low level algorithm is very simple: 5 functions covering X25519 and Ed25519. It can be replaced with optimised versions in future.

Adding X448/Ed448 support should also be much easier by following a similar model but we're lacking the low level algorithm code in a form we can use.

@snhensen What would be needed to get this PR into OpenSSL?

As for ed448, The best C code implementation of ed448 at the moment would be probably the implementation of the author of ed448 ( Mike Hamburg [ @bitwiseshiftleft ] ) in libdecaf. This version can verify the testvectors for ed448 in RFC8032 correctly and contains a reference implementation and implementations with inline assembly code optimisations for x86/64 and ARM (NEON) processors.
This code currently still contains some bugs preventing some people from compiling it, but Mike Hamburg is working on fixing these bugs.

For those who are interested in ed448, below is a mini-tutorial of how to work with ed448, if you can compile the code on your computer:

1. Download libdecaf:
   git clone https://git.code.sf.net/p/ed448goldilocks/code ed448goldilocks-code
2. Libdecaf is constantly updated. A specific version of libdecaf was selected that could be compiled on Ubuntu 16.04 Compile this specific version as follows:

cd ed448goldilocks-code
git checkout 92b2cb464abb670c1891ed2dfb6024771dc669f4
make

But this is also the point where most people experience problems.

Note the complexity of the makefile: It consists of several phases such as first regenerating files in the "GENERATED" folder, then compiling a program to generate tables, and then finally compiling the library itself.
Also note that the makefile is currently hardcoded for the x86/64 processor architecture:

$(eval $(call define_field,p25519,arch_x86_64))
$(eval $(call define_field,p448,arch_x86_64))

There are implementations for other architectures (arch_32, arch_arm_32, arch_neon, arch_ref64) available, but compiling for these architectures could require more changes to the makefile or alternatively you could compile and link the files manually.

3. Optionally, run some additional tests to check if everything is okay:
   make test

4. After compiling it successfully, create a new file called hello_ed448_world.c in the same directory to link against libdecaf with following code

#include <string.h>
#include <stdio.h>
#include <decaf.h>
#include <decaf/spongerng.h>
#include <decaf/point_255.h>
#include <decaf/ed255.h>
#include <decaf/point_448.h>
#include <decaf/ed448.h>
#include <decaf/shake.h>

int main(){

	/* buffer for the private key */
	uint8_t privatekey[DECAF_EDDSA_448_PRIVATE_BYTES]; 

	/* buffer for the public key */
	uint8_t publickey[DECAF_EDDSA_448_PUBLIC_BYTES]; 

	/* buffer for the signature */
	uint8_t signature[DECAF_EDDSA_448_SIGNATURE_BYTES]; 

	/* the message to sign */
	uint8_t message[2] = {0x04, 0x48}; 

	/* set the size of the message*/
	size_t messageSize = 2; 

	/* Set the context */
	uint8_t *contextData = NULL; 

	/* set the size of the context */
	size_t contextSize = 0;

	/* Create pseudo random number generator object. */
	decaf_keccak_prng_t rng; 

	/* Set an initial value for the pseudo random number generator */
	uint8_t buf[] = "bench_cfrg_crypto"; 

	printf("Initializing a sponge-based CSPRNG from a buffer...\n");
	decaf_spongerng_init_from_buffer( 
	rng, /* The PRNG object. */
	buf, /*  The initialization data. */
	17, /* The length of the initialization data. */
	1 /* Make it deterministic */
	);

	/* Create output buffer for the sponge-based CSPRNG. */
	uint8_t CSPRNGbuffer[DECAF_EDDSA_448_PRIVATE_BYTES];

	printf("Outputting bytes from a sponge-based CSPRNG...\n");
	decaf_spongerng_next(  
	rng, /* The PRNG object. */
	CSPRNGbuffer, /* The output buffer for the sponge-based CSPRNG. */
	DECAF_EDDSA_448_PRIVATE_BYTES /* Number of bytes to output. */
	);

	printf("Using the random number that was generated as private key...\n");
	memcpy(privatekey, CSPRNGbuffer, DECAF_EDDSA_448_PRIVATE_BYTES);

	printf("generate the public key from the private key...\n");
	decaf_ed448_derive_public_key(publickey, privatekey); 

	printf("signing the message using ed448...\n");
	decaf_ed448_sign( 
		signature,
		privatekey,
		publickey,
		message,
		messageSize,
		0, /* prehash (a.k.a ed448_ph): 0=false. non-zero=true. */
		contextData,
		contextSize
	);

	printf("verifying the message using ed448...\n");
	decaf_error_t verificationstatus = decaf_ed448_verify(   
		signature, 
		publickey, 
		message, 
		messageSize, 
		0, /* prehash (a.k.a ed448_ph): 0=false. non-zero=true. */
		contextData, 
		contextSize
	); 

	if (verificationstatus == DECAF_SUCCESS)
	{
		printf("verification succeeded!\n");
	}
	else
	{
		printf("verification failed!\n");
	}

	return 0;
}

5. Compile hello_ed448_world.c:
   gcc -Wl,-rpath,`pwd`/build/lib hello_ed448_world.c -o hello_ed448_world -Isrc/GENERATED/include -Lbuild/lib -ldecaf -O2

6. Run it:
   ./hello_ed448_world

Compiling the library required the generation and linking of several object files, such as the ones below.
build/obj/bench_decaf.o build/obj/utils.o build/obj/shake.o build/obj/sha512.o build/obj/spongerng.o

x448/ed448 specific:
build/obj/p448/f_impl.o build/obj/p448/f_arithmetic.o build/obj/p448/f_generic.o

build/obj/ed448goldilocks/decaf.o build/obj/ed448goldilocks/elligator.o build/obj/ed448goldilocks/scalar.o build/obj/ed448goldilocks/eddsa.o build/obj/ed448goldilocks/decaf_tables.o

x25519/ed448 specific:
build/obj/p25519/f_impl.o build/obj/p25519/f_arithmetic.o build/obj/p25519/f_generic.o

build/obj/curve25519/decaf.o build/obj/curve25519/elligator.o build/obj/curve25519/scalar.o build/obj/curve25519/eddsa.o build/obj/curve25519/decaf_tables.o

Update: cleanse some sensitive data, rebase against master. Taken out of WIP. This should now be ready for review.

Update: rebased against master to resolve conflict.

Thanks to everyone for the comments. Pushed.