On 17.02.2019 15:46, Yuriy M. Kaminskiy wrote:
> See attached:
>
> I hacked a bit regress/unittests/kex, and benchmarked
> do_kex_with_key("curve25519-sha256@xxxxxxxxxx", KEY_ED25519, 256);
> Before:
> 0.3295s per call
> After:
> 0.2183s per call
>
> That is, 50% speedup; assuming ed25519 (added to openssl in 1.1.1) takes about same time as ecdh/x25519,
> there are potential for total 200% speedup in KEX.
(Very slightly tested) patch attached.
Guess what? I was wrong:
0.0113s per call (with both curve25519 and ed25519 patches applied, and openssl-1.1.1a)
2800% faster.
openssh's ed25519 was not just slow. It was *very* slow.
FWIW, ecdh-sha2-nistp256/ecdsa-sha2-nistp256:
0.0288s per call
(still 1000% faster than current openssh's {ed,curve}25519 combo)
(I also attached patch I used for benchmarking, it is *not* for upstream inclusion for sure)
> P.S. given amount of feedback I received so far, it seems everyone follows motto "it cannot be secure
> if it is not slow".
>From 141d7b5713f8650d4696d3f80937530b0f93ea1e Mon Sep 17 00:00:00 2001
From: "Yuriy M. Kaminskiy" <yumkam@xxxxxxxxx>
Date: Mon, 18 Feb 2019 00:07:41 +0300
Subject: [PATCH] use ed25519 (sig) from openssl when possible
---
Makefile.in | 16 ++++-----
ed25519.c | 113 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
ssh-ed25519.c | 76 ++++++++++++++++++++++++++++++++++++++-
3 files changed, 196 insertions(+), 9 deletions(-)
diff --git a/Makefile.in b/Makefile.in
index 6f001bb3..6add0023 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -170,22 +170,22 @@ libssh.a: $(LIBSSH_OBJS)
$(RANLIB) $@
ssh$(EXEEXT): $(LIBCOMPAT) libssh.a $(SSHOBJS)
- $(LD) -o $@ $(SSHOBJS) $(LDFLAGS) -lssh -lopenbsd-compat $(SSHLIBS) $(LIBS) $(GSSLIBS)
+ $(LD) -o $@ $(SSHOBJS) $(LDFLAGS) -lssh -lopenbsd-compat -lssh $(SSHLIBS) $(LIBS) $(GSSLIBS)
sshd$(EXEEXT): libssh.a $(LIBCOMPAT) $(SSHDOBJS)
- $(LD) -o $@ $(SSHDOBJS) $(LDFLAGS) -lssh -lopenbsd-compat $(SSHDLIBS) $(LIBS) $(GSSLIBS) $(K5LIBS)
+ $(LD) -o $@ $(SSHDOBJS) $(LDFLAGS) -lssh -lopenbsd-compat -lssh $(SSHDLIBS) $(LIBS) $(GSSLIBS) $(K5LIBS)
scp$(EXEEXT): $(LIBCOMPAT) libssh.a scp.o progressmeter.o
- $(LD) -o $@ scp.o progressmeter.o $(LDFLAGS) -lssh -lopenbsd-compat $(LIBS)
+ $(LD) -o $@ scp.o progressmeter.o $(LDFLAGS) -lssh -lopenbsd-compat -lssh $(LIBS)
ssh-add$(EXEEXT): $(LIBCOMPAT) libssh.a ssh-add.o
- $(LD) -o $@ ssh-add.o $(LDFLAGS) -lssh -lopenbsd-compat $(LIBS)
+ $(LD) -o $@ ssh-add.o $(LDFLAGS) -lssh -lopenbsd-compat -lssh $(LIBS)
ssh-agent$(EXEEXT): $(LIBCOMPAT) libssh.a ssh-agent.o ssh-pkcs11-client.o
- $(LD) -o $@ ssh-agent.o ssh-pkcs11-client.o $(LDFLAGS) -lssh -lopenbsd-compat $(LIBS)
+ $(LD) -o $@ ssh-agent.o ssh-pkcs11-client.o $(LDFLAGS) -lssh -lopenbsd-compat -lssh $(LIBS)
ssh-keygen$(EXEEXT): $(LIBCOMPAT) libssh.a ssh-keygen.o
- $(LD) -o $@ ssh-keygen.o $(LDFLAGS) -lssh -lopenbsd-compat $(LIBS)
+ $(LD) -o $@ ssh-keygen.o $(LDFLAGS) -lssh -lopenbsd-compat -lssh $(LIBS)
ssh-keysign$(EXEEXT): $(LIBCOMPAT) libssh.a ssh-keysign.o readconf.o uidswap.o compat.o
$(LD) -o $@ ssh-keysign.o readconf.o uidswap.o $(LDFLAGS) -lssh -lopenbsd-compat $(LIBS)
@@ -197,10 +197,10 @@ ssh-keyscan$(EXEEXT): $(LIBCOMPAT) libssh.a ssh-keyscan.o
$(LD) -o $@ ssh-keyscan.o $(LDFLAGS) -lssh -lopenbsd-compat -lssh $(LIBS)
sftp-server$(EXEEXT): $(LIBCOMPAT) libssh.a sftp.o sftp-common.o sftp-server.o sftp-server-main.o
- $(LD) -o $@ sftp-server.o sftp-common.o sftp-server-main.o $(LDFLAGS) -lssh -lopenbsd-compat $(LIBS)
+ $(LD) -o $@ sftp-server.o sftp-common.o sftp-server-main.o $(LDFLAGS) -lssh -lopenbsd-compat -lssh $(LIBS)
sftp$(EXEEXT): $(LIBCOMPAT) libssh.a sftp.o sftp-client.o sftp-common.o sftp-glob.o progressmeter.o
- $(LD) -o $@ progressmeter.o sftp.o sftp-client.o sftp-common.o sftp-glob.o $(LDFLAGS) -lssh -lopenbsd-compat $(LIBS) $(LIBEDIT)
+ $(LD) -o $@ progressmeter.o sftp.o sftp-client.o sftp-common.o sftp-glob.o $(LDFLAGS) -lssh -lopenbsd-compat -lssh $(LIBS) $(LIBEDIT)
# test driver for the loginrec code - not built by default
logintest: logintest.o $(LIBCOMPAT) libssh.a loginrec.o
diff --git a/ed25519.c b/ed25519.c
index 767ec24d..dcb41145 100644
--- a/ed25519.c
+++ b/ed25519.c
@@ -9,6 +9,16 @@
#include "includes.h"
#include "crypto_api.h"
+#ifdef WITH_OPENSSL
+# include <openssl/evp.h>
+# if defined(EVP_PKEY_ED25519)
+# define WITH_OPENSSL_ED25519
+# endif
+#endif
+
+#ifdef WITH_OPENSSL_ED25519
+#include <string.h>
+#else
#include "ge25519.h"
static void get_hram(unsigned char *hram, const unsigned char *sm, const unsigned char *pk, unsigned char *playground, unsigned long long smlen)
@@ -21,6 +31,7 @@ static void get_hram(unsigned char *hram, const unsigned char *sm, const unsigne
crypto_hash_sha512(hram,playground,smlen);
}
+#endif
int crypto_sign_ed25519_keypair(
@@ -28,6 +39,36 @@ int crypto_sign_ed25519_keypair(
unsigned char *sk
)
{
+#ifdef WITH_OPENSSL_ED25519
+ EVP_PKEY_CTX *pctx = EVP_PKEY_CTX_new_id(EVP_PKEY_ED25519, NULL);
+ EVP_PKEY *pkey = NULL;
+ size_t privsz, pubsz;
+ int r = -1;
+ if (pctx == NULL)
+ goto out;
+ if (EVP_PKEY_keygen_init(pctx) <= 0)
+ goto out;
+ if (EVP_PKEY_keygen(pctx, &pkey) <= 0)
+ goto out;
+ if (EVP_PKEY_get_raw_private_key(pkey, NULL, &privsz) <= 0)
+ goto out;
+ if (privsz != 32U)
+ goto out;
+ if (EVP_PKEY_get_raw_private_key(pkey, sk, &privsz) <= 0)
+ goto out;
+ if (EVP_PKEY_get_raw_public_key(pkey, NULL, &pubsz) <= 0)
+ goto out;
+ if (pubsz != 32U)
+ goto out;
+ if (EVP_PKEY_get_raw_public_key(pkey, pk, &pubsz) <= 0)
+ goto out;
+ memcpy(sk + 32U, pk, 32U);
+ r = 0;
+out:
+ EVP_PKEY_CTX_free(pctx);
+ EVP_PKEY_free(pkey);
+ return r;
+#else
sc25519 scsk;
ge25519 gepk;
unsigned char extsk[64];
@@ -46,6 +87,7 @@ int crypto_sign_ed25519_keypair(
for(i=0;i<32;i++)
sk[32 + i] = pk[i];
return 0;
+#endif
}
int crypto_sign_ed25519(
@@ -54,6 +96,44 @@ int crypto_sign_ed25519(
const unsigned char *sk
)
{
+#ifdef WITH_OPENSSL_ED25519
+ /* EVP_PKEY_CTX *pctx = NULL; */
+ EVP_PKEY *pkey = NULL;
+ EVP_MD_CTX *md = NULL;
+ size_t siglen;
+ int r = -1;
+
+ *smlen = 0;
+
+ pkey = EVP_PKEY_new_raw_private_key(EVP_PKEY_ED25519, NULL, sk, 32U);
+ if (pkey == NULL)
+ goto out;
+
+ if ((md = EVP_MD_CTX_new()) == NULL)
+ goto out;
+
+ if (EVP_DigestSignInit(md, /* &pctx */ NULL, NULL, NULL, pkey) <= 0)
+ goto out;
+
+ if (EVP_DigestSign(md, NULL, &siglen, m, mlen) <= 0)
+ goto out;
+ if (siglen != 64U)
+ goto out;
+
+ memmove(sm + 64, m, mlen);
+
+ if (EVP_DigestSign(md, sm, &siglen, sm + 64, mlen) <= 0)
+ goto out;
+ if (siglen != 64U)
+ goto out;
+
+ *smlen = mlen + 64U;
+ r = 0;
+out:
+ EVP_PKEY_free(pkey);
+ EVP_MD_CTX_free(md);
+ return r;
+#else
sc25519 sck, scs, scsk;
ge25519 ger;
unsigned char r[32];
@@ -98,6 +178,7 @@ int crypto_sign_ed25519(
sm[32 + i] = s[i];
return 0;
+#endif
}
int crypto_sign_ed25519_open(
@@ -106,6 +187,37 @@ int crypto_sign_ed25519_open(
const unsigned char *pk
)
{
+#ifdef WITH_OPENSSL_ED25519
+ /* EVP_PKEY_CTX *pctx = NULL; */
+ EVP_PKEY *pkey = NULL;
+ EVP_MD_CTX *md = NULL;
+ int r = -1;
+
+ *mlen = (unsigned long long) -1;
+ if (smlen < 64) return -1;
+
+ pkey = EVP_PKEY_new_raw_public_key(EVP_PKEY_ED25519, NULL, pk, 32U);
+ if (pkey == NULL)
+ goto out;
+ md = EVP_MD_CTX_new();
+ if (md == NULL)
+ goto out;
+ if (EVP_DigestVerifyInit(md, /* &pctx */ NULL, NULL, NULL, pkey) <= 0)
+ goto out;
+ r = EVP_DigestVerify(md, sm, 64U, sm + 64U, smlen - 64U);
+ if (r == 1) {
+ *mlen = smlen - 64U;
+ memmove(m, sm + 64, *mlen);
+ r = 0;
+ } else {
+ memset(m, 0, smlen - 64);
+ r = -1;
+ }
+out:
+ EVP_PKEY_free(pkey);
+ EVP_MD_CTX_free(md);
+ return r;
+#else
unsigned int i;
int ret;
unsigned char t2[32];
@@ -141,4 +253,5 @@ int crypto_sign_ed25519_open(
m[i] = 0;
}
return ret;
+#endif
}
diff --git a/ssh-ed25519.c b/ssh-ed25519.c
index 5163e029..e0f4d111 100644
--- a/ssh-ed25519.c
+++ b/ssh-ed25519.c
@@ -32,13 +32,27 @@
#include "ssherr.h"
#include "ssh.h"
+#ifdef WITH_OPENSSL
+# include <openssl/evp.h>
+# if defined(EVP_PKEY_ED25519)
+# define WITH_OPENSSL_ED25519
+# endif
+#endif
+
int
ssh_ed25519_sign(const struct sshkey *key, u_char **sigp, size_t *lenp,
const u_char *data, size_t datalen, u_int compat)
{
+#ifdef WITH_OPENSSL_ED25519
+ EVP_PKEY *pkey = NULL;
+ EVP_MD_CTX *md = NULL;
+ u_char sig[crypto_sign_ed25519_BYTES];
+ size_t len, siglen;
+#else
u_char *sig = NULL;
size_t slen = 0, len;
unsigned long long smlen;
+#endif
int r, ret;
struct sshbuf *b = NULL;
@@ -52,6 +66,29 @@ ssh_ed25519_sign(const struct sshkey *key, u_char **sigp, size_t *lenp,
key->ed25519_sk == NULL ||
datalen >= INT_MAX - crypto_sign_ed25519_BYTES)
return SSH_ERR_INVALID_ARGUMENT;
+#ifdef WITH_OPENSSL_ED25519
+ r = SSH_ERR_LIBCRYPTO_ERROR;
+
+ pkey = EVP_PKEY_new_raw_private_key(EVP_PKEY_ED25519, NULL, key->ed25519_sk, 32U);
+ if (pkey == NULL)
+ goto out;
+
+ if ((md = EVP_MD_CTX_new()) == NULL)
+ goto out;
+
+ if (EVP_DigestSignInit(md, /* &pctx */ NULL, NULL, NULL, pkey) <= 0)
+ goto out;
+
+ if (EVP_DigestSign(md, NULL, &siglen, data, datalen) <= 0)
+ goto out;
+ if (siglen != crypto_sign_ed25519_BYTES)
+ goto out;
+
+ if (EVP_DigestSign(md, sig, &siglen, data, datalen) <= 0)
+ goto out;
+ if (siglen != crypto_sign_ed25519_BYTES)
+ goto out;
+#else
smlen = slen = datalen + crypto_sign_ed25519_BYTES;
if ((sig = malloc(slen)) == NULL)
return SSH_ERR_ALLOC_FAIL;
@@ -61,13 +98,14 @@ ssh_ed25519_sign(const struct sshkey *key, u_char **sigp, size_t *lenp,
r = SSH_ERR_INVALID_ARGUMENT; /* XXX better error? */
goto out;
}
+#endif
/* encode signature */
if ((b = sshbuf_new()) == NULL) {
r = SSH_ERR_ALLOC_FAIL;
goto out;
}
if ((r = sshbuf_put_cstring(b, "ssh-ed25519")) != 0 ||
- (r = sshbuf_put_string(b, sig, smlen - datalen)) != 0)
+ (r = sshbuf_put_string(b, sig, crypto_sign_ed25519_BYTES)) != 0)
goto out;
len = sshbuf_len(b);
if (sigp != NULL) {
@@ -83,10 +121,16 @@ ssh_ed25519_sign(const struct sshkey *key, u_char **sigp, size_t *lenp,
r = 0;
out:
sshbuf_free(b);
+#ifdef WITH_OPENSSL_ED25519
+ EVP_PKEY_free(pkey);
+ EVP_MD_CTX_free(md);
+ explicit_bzero(sig, crypto_sign_ed25519_BYTES);
+#else
if (sig != NULL) {
explicit_bzero(sig, slen);
free(sig);
}
+#endif
return r;
}
@@ -99,9 +143,15 @@ ssh_ed25519_verify(const struct sshkey *key,
struct sshbuf *b = NULL;
char *ktype = NULL;
const u_char *sigblob;
+#ifdef WITH_OPENSSL_ED25519
+ EVP_PKEY *pkey = NULL;
+ EVP_MD_CTX *md = NULL;
+ size_t len;
+#else
u_char *sm = NULL, *m = NULL;
size_t len;
unsigned long long smlen = 0, mlen = 0;
+#endif
int r, ret;
if (key == NULL ||
@@ -124,6 +174,29 @@ ssh_ed25519_verify(const struct sshkey *key,
r = SSH_ERR_UNEXPECTED_TRAILING_DATA;
goto out;
}
+#ifdef WITH_OPENSSL_ED25519
+ r = SSH_ERR_LIBCRYPTO_ERROR;
+ pkey = EVP_PKEY_new_raw_public_key(EVP_PKEY_ED25519, NULL, key->ed25519_pk, 32U);
+ if (pkey == NULL)
+ goto out;
+ if ((md = EVP_MD_CTX_new()) == NULL)
+ goto out;
+ if (EVP_DigestVerifyInit(md, /* &pctx */ NULL, NULL, NULL, pkey) <= 0)
+ goto out;
+ switch(EVP_DigestVerify(md, sigblob, len, data, datalen)) {
+ case 1:
+ r = 0; /* signature valid */
+ break;
+ case 0:
+ r = SSH_ERR_SIGNATURE_INVALID;
+ /* fallthrough */
+ default:
+ goto out;
+ }
+out:
+ EVP_PKEY_free(pkey);
+ EVP_MD_CTX_free(md);
+#else
if (len > crypto_sign_ed25519_BYTES) {
r = SSH_ERR_INVALID_FORMAT;
goto out;
@@ -161,6 +234,7 @@ ssh_ed25519_verify(const struct sshkey *key,
explicit_bzero(m, smlen); /* NB mlen may be invalid if r != 0 */
free(m);
}
+#endif
sshbuf_free(b);
free(ktype);
return r;
--
2.11.0
--- a/regress/unittests/kex/test_kex.c 2019-02-17 13:44:27.041873885 +0300
+++ b/regress/unittests/kex/test_kex.c 2019-02-18 00:39:04.666882792 +0300
@@ -183,9 +183,30 @@
do_kex_with_key(kex, KEY_ED25519, 256);
}
+#include <time.h>
void
kex_tests(void)
{
+ char *t;
+ if ((t = getenv("BENCHMARK")) != NULL) {
+ struct timespec t0, t1;
+ const char * s = getenv("BENCHMARK_COUNT");
+ int i = s ? atoi(s) : 100;
+ int pubkey_algo = KEY_ED25519;
+ int pubkey_bits = 256;
+ if ((s = getenv("PUBKEY_ALGO")))
+ pubkey_algo = atoi(s);
+ if ((s = getenv("PUBKEY_BITS")))
+ pubkey_bits = atoi(s);
+ clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t0);
+ while(i-- > 0)
+ do_kex_with_key(t, pubkey_algo, pubkey_bits);
+ clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t1);
+ t1.tv_sec -= t0.tv_sec;
+ t1.tv_nsec -= t0.tv_nsec;
+ fprintf(stderr, "time: %g\n", (t1.tv_sec + t1.tv_nsec*1e-9));
+ return;
+ }
do_kex("curve25519-sha256@xxxxxxxxxx");
#ifdef OPENSSL_HAS_ECC
do_kex("ecdh-sha2-nistp256");
_______________________________________________
openssh-unix-dev mailing list
openssh-unix-dev@xxxxxxxxxxx
https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
