openssh unix dev - Sep 2013 - [PATCH] curve25519-sha256@libssh.org key exchange proposal

Dear OpenSSH developers,

I've worked this week on an alternative key exchange mechanism, in
reaction to the whole NSA leaks and claims over cryptographic backdoors
and/or cracking advances. The key exchange is in my opinion the most
critical defense against passive eavesdropping attacks.
I believe Curve25519 from DJB can give users a secure alternative to
classical Diffie-Hellman (with fixed groups or group exchanges) and
NIST-approved elliptic curves.

Here is the rationale from the small specifications draft I wrote,
available on http://tinyurl.com/q22npph :

The reason is the following : During summer of 2013, revelations from
ex-consultant at NSA Edward Snowden gave proof that NSA willingly
inserts backdoors into softwares, hardware components and published
standards. While it is still believed that the mathematics behind ECC
cryptography are still sound and solid,
some people (including Bruce Schneier [SCHNEIER]), showed their lack of
confidence in NIST-published curves such as nistp256, nistp384,
nistp521, for which constant parameters (including the generator point)
are defined without explanation. It is also believed that NSA had a word
to say in their definition. These curves
are not the most secure or fastest possible for their key sizes [DJB],
and researchers think it is possible that NSA have ways of cracking NIST
curves.
It is also interesting to note that SSH belongs to the list of protocols
the NSA claims to be able to eavesdrop. Having a secure replacement
would make passive attacks much harder if such a backdoor exists.

However an alternative exists in the form of Curve25519. This algorithm
has been proposed in 2006 by DJB [Curve25519]. Its main stengths are its
speed, its constant-time run time (and resistance against side-channel
attacks), and its lack of nebulous hard-coded constants.

The reference version being used in this document is the one described
in [Curve25519] as implemented in the library NaCl [NaCl].



I namespaced this method with @libssh.org since I implemented it first
in libssh and intent to release it with the next release.
In attachment, you will find a patch to openssh-6.3p1 (I think
adaptations for OpenSSH are trivial). It links to libnacl. However, my
autotools skills are lacking and I compiled it with LIBS=-libnacl.

I would greatly appreciate feedback and/or a debate on the relevancy of
such kex method, code quality and implementation details.

Aris Adamantiadis
www.libssh.org
-------------- next part --------------
>From c3105fa718ca813a06527a238294c148dfc91287 Mon Sep 17 00:00:00 2001
From: Aris Adamantiadis <aris at 0xbadc0de.be>
Date: Tue, 24 Sep 2013 21:59:36 +0200
Subject: [PATCH] kex: implement curve25519-sha256 at libssh.org

---
 Makefile.in   |    4 +-
 kex.c         |    1 +
 kex.h         |    9 ++++
 kexc25519.c   |   96 +++++++++++++++++++++++++++++++++++++
 kexc25519c.c  |  149 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 kexc25519s.c  |  144 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 myproposal.h  |    1 +
 ssh-keyscan.c |    1 +
 sshconnect2.c |    1 +
 sshd.c        |    1 +
 10 files changed, 405 insertions(+), 2 deletions(-)
 create mode 100644 kexc25519.c
 create mode 100644 kexc25519c.c
 create mode 100644 kexc25519s.c

diff --git a/Makefile.in b/Makefile.in
index 92c95a9..a8e282a 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -73,7 +73,7 @@ LIBSSH_OBJS=authfd.o authfile.o bufaux.o bufbn.o buffer.o \
 	monitor_fdpass.o rijndael.o ssh-dss.o ssh-ecdsa.o ssh-rsa.o dh.o \
 	kexdh.o kexgex.o kexdhc.o kexgexc.o bufec.o kexecdh.o kexecdhc.o \
 	msg.o progressmeter.o dns.o entropy.o gss-genr.o umac.o umac128.o \
-	jpake.o schnorr.o ssh-pkcs11.o krl.o
+	jpake.o schnorr.o ssh-pkcs11.o krl.o kexc25519.o kexc25519c.o
 
 SSHOBJS= ssh.o readconf.o clientloop.o sshtty.o \
 	sshconnect.o sshconnect1.o sshconnect2.o mux.o \
@@ -93,7 +93,7 @@ SSHDOBJS=sshd.o auth-rhosts.o auth-passwd.o auth-rsa.o
auth-rh-rsa.o \
 	sftp-server.o sftp-common.o \
 	roaming_common.o roaming_serv.o \
 	sandbox-null.o sandbox-rlimit.o sandbox-systrace.o sandbox-darwin.o \
-	sandbox-seccomp-filter.o
+	sandbox-seccomp-filter.o kexc25519s.o
 
 MANPAGES	= moduli.5.out scp.1.out ssh-add.1.out ssh-agent.1.out
ssh-keygen.1.out ssh-keyscan.1.out ssh.1.out sshd.8.out sftp-server.8.out
sftp.1.out ssh-keysign.8.out ssh-pkcs11-helper.8.out sshd_config.5.out
ssh_config.5.out
 MANPAGES_IN	= moduli.5 scp.1 ssh-add.1 ssh-agent.1 ssh-keygen.1 ssh-keyscan.1
ssh.1 sshd.8 sftp-server.8 sftp.1 ssh-keysign.8 ssh-pkcs11-helper.8
sshd_config.5 ssh_config.5
diff --git a/kex.c b/kex.c
index 54bd1a4..a27f9c3 100644
--- a/kex.c
+++ b/kex.c
@@ -80,6 +80,7 @@ static const struct kexalg kexalgs[] = {
 	{ KEX_ECDH_SHA2_NISTP384, KEX_ECDH_SHA2, NID_secp384r1, EVP_sha384 },
 	{ KEX_ECDH_SHA2_NISTP521, KEX_ECDH_SHA2, NID_secp521r1, EVP_sha512 },
 #endif
+	{ KEX_CURVE25519_SHA256, KEX_C25519_SHA256, 0, EVP_sha256 },
 	{ NULL, -1, -1, NULL},
 };
 
diff --git a/kex.h b/kex.h
index 9f1e1ad..df89ade 100644
--- a/kex.h
+++ b/kex.h
@@ -43,6 +43,7 @@
 #define	KEX_ECDH_SHA2_NISTP256	"ecdh-sha2-nistp256"
 #define	KEX_ECDH_SHA2_NISTP384	"ecdh-sha2-nistp384"
 #define	KEX_ECDH_SHA2_NISTP521	"ecdh-sha2-nistp521"
+#define KEX_CURVE25519_SHA256   "curve25519-sha256 at libssh.org"
 
 #define COMP_NONE	0
 #define COMP_ZLIB	1
@@ -74,6 +75,7 @@ enum kex_exchange {
 	KEX_DH_GEX_SHA1,
 	KEX_DH_GEX_SHA256,
 	KEX_ECDH_SHA2,
+	KEX_C25519_SHA256,
 	KEX_MAX
 };
 
@@ -161,6 +163,8 @@ void	 kexgex_client(Kex *);
 void	 kexgex_server(Kex *);
 void	 kexecdh_client(Kex *);
 void	 kexecdh_server(Kex *);
+void	 kexc25519_client(Kex *);
+void	 kexc25519_server(Kex *);
 
 void
 kex_dh_hash(char *, char *, char *, int, char *, int, u_char *, int,
@@ -177,6 +181,11 @@ kex_ecdh_hash(const EVP_MD *, const EC_GROUP *, char *,
char *, char *, int,
 #endif
 
 void
+kex_c25519_hash(const EVP_MD *, char *, char *, char *, int,
+    char *, int, u_char *, int, const unsigned char *, const unsigned char *,
+    const BIGNUM *, u_char **, u_int *);
+
+void
 derive_ssh1_session_id(BIGNUM *, BIGNUM *, u_int8_t[8], u_int8_t[16]);
 
 #if defined(DEBUG_KEX) || defined(DEBUG_KEXDH) || defined(DEBUG_KEXECDH)
diff --git a/kexc25519.c b/kexc25519.c
new file mode 100644
index 0000000..8260fad
--- /dev/null
+++ b/kexc25519.c
@@ -0,0 +1,96 @@
+/*
+ * Copyright (c) 2001 Markus Friedl.  All rights reserved.
+ * Copyright (c) 2010 Damien Miller.  All rights reserved.
+ * Copyright (c) 2013 Aris Adamantiadis.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "includes.h"
+
+
+#include <sys/types.h>
+
+#include <signal.h>
+#include <string.h>
+
+#include <openssl/bn.h>
+#include <openssl/evp.h>
+
+#include "buffer.h"
+#include "ssh2.h"
+#include "key.h"
+#include "cipher.h"
+#include "kex.h"
+#include "log.h"
+
+#include <nacl/crypto_scalarmult_curve25519.h>
+#define CURVE25519_PUBKEY_SIZE crypto_scalarmult_curve25519_BYTES
+
+void
+kex_c25519_hash(
+    const EVP_MD *evp_md,
+    char *client_version_string,
+    char *server_version_string,
+    char *ckexinit, int ckexinitlen,
+    char *skexinit, int skexinitlen,
+    u_char *serverhostkeyblob, int sbloblen,
+    const unsigned char client_dh_pub[CURVE25519_PUBKEY_SIZE],
+    const unsigned char server_dh_pub[CURVE25519_PUBKEY_SIZE],
+    const BIGNUM *shared_secret,
+    u_char **hash, u_int *hashlen)
+{
+	Buffer b;
+	EVP_MD_CTX md;
+	static u_char digest[EVP_MAX_MD_SIZE];
+
+	buffer_init(&b);
+	buffer_put_cstring(&b, client_version_string);
+	buffer_put_cstring(&b, server_version_string);
+
+	/* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */
+	buffer_put_int(&b, ckexinitlen+1);
+	buffer_put_char(&b, SSH2_MSG_KEXINIT);
+	buffer_append(&b, ckexinit, ckexinitlen);
+	buffer_put_int(&b, skexinitlen+1);
+	buffer_put_char(&b, SSH2_MSG_KEXINIT);
+	buffer_append(&b, skexinit, skexinitlen);
+
+	buffer_put_string(&b, serverhostkeyblob, sbloblen);
+	buffer_put_string(&b, client_dh_pub, CURVE25519_PUBKEY_SIZE);
+	buffer_put_string(&b, server_dh_pub, CURVE25519_PUBKEY_SIZE);
+	buffer_put_bignum2(&b, shared_secret);
+
+#ifdef DEBUG_KEX
+	buffer_dump(&b);
+#endif
+	EVP_DigestInit(&md, evp_md);
+	EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
+	EVP_DigestFinal(&md, digest, NULL);
+
+	buffer_free(&b);
+
+#ifdef DEBUG_KEX
+	dump_digest("hash", digest, EVP_MD_size(evp_md));
+#endif
+	*hash = digest;
+	*hashlen = EVP_MD_size(evp_md);
+}
diff --git a/kexc25519c.c b/kexc25519c.c
new file mode 100644
index 0000000..b2000f0
--- /dev/null
+++ b/kexc25519c.c
@@ -0,0 +1,149 @@
+/*
+ * Copyright (c) 2001 Markus Friedl.  All rights reserved.
+ * Copyright (c) 2010 Damien Miller.  All rights reserved.
+ * Copyright (c) 2013 Aris Adamantiadis.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "includes.h"
+
+#include <sys/types.h>
+
+#include <stdio.h>
+#include <string.h>
+#include <signal.h>
+
+#include "xmalloc.h"
+#include "buffer.h"
+#include "key.h"
+#include "cipher.h"
+#include "kex.h"
+#include "log.h"
+#include "packet.h"
+#include "dh.h"
+#include "ssh2.h"
+
+#include <nacl/crypto_scalarmult_curve25519.h>
+#define CURVE25519_PUBKEY_SIZE crypto_scalarmult_curve25519_BYTES
+#define CURVE25519_PRIVKEY_SIZE crypto_scalarmult_curve25519_SCALARBYTES
+
+void
+kexc25519_client(Kex *kex)
+{
+	BIGNUM *shared_secret;
+	Key *server_host_key;
+	u_char client_key[CURVE25519_PRIVKEY_SIZE];
+	u_char client_pubkey[CURVE25519_PUBKEY_SIZE];	
+	u_char *server_pubkey = NULL;	
+	u_char shared_secret_raw[CURVE25519_PUBKEY_SIZE];	
+	u_char *server_host_key_blob = NULL, *signature = NULL;
+	u_char *hash;
+	u_int rnd = 0, slen, sbloblen, hashlen, i;
+
+	/* generate private key */
+	for (i = 0; i < sizeof(client_key); i++) {
+		if (i % 4 == 0)
+			rnd = arc4random();
+		client_key[i] = rnd;
+		rnd >>= 8;
+        }
+	crypto_scalarmult_curve25519_base(client_pubkey, client_key);	
+
+	packet_start(SSH2_MSG_KEX_ECDH_INIT);
+	packet_put_string(client_pubkey, sizeof(client_pubkey));
+	packet_send();
+	debug("sending SSH2_MSG_KEX_ECDH_INIT");
+
+#ifdef DEBUG_KEXECDH
+	dump_digest("client private key:", client_key, sizeof(client_key));
+#endif
+
+	debug("expecting SSH2_MSG_KEX_ECDH_REPLY");
+	packet_read_expect(SSH2_MSG_KEX_ECDH_REPLY);
+
+	/* hostkey */
+	server_host_key_blob = packet_get_string(&sbloblen);
+	server_host_key = key_from_blob(server_host_key_blob, sbloblen);
+	if (server_host_key == NULL)
+		fatal("cannot decode server_host_key_blob");
+	if (server_host_key->type != kex->hostkey_type)
+		fatal("type mismatch for decoded server_host_key_blob");
+	if (kex->verify_host_key == NULL)
+		fatal("cannot verify server_host_key");
+	if (kex->verify_host_key(server_host_key) == -1)
+		fatal("server_host_key verification failed");
+
+	/* Q_S, server public key */
+	server_pubkey = packet_get_string(&slen);
+	if (slen != CURVE25519_PUBKEY_SIZE)
+		fatal("Incorrect size for server Curve25519 public key: %d", slen);
+	
+#ifdef DEBUG_KEXECDH
+	dump_digest("server public key:\n", server_pubkey,
CURVE25519_PUBKEY_SIZE);
+#endif
+
+	/* signed H */
+	signature = packet_get_string(&slen);
+	packet_check_eom();
+	
+	crypto_scalarmult_curve25519(shared_secret_raw, client_key, server_pubkey);
+
+#ifdef DEBUG_KEXECDH
+	dump_digest("shared secret", shared_secret_raw,
sizeof(shared_secret_raw));
+#endif
+	if ((shared_secret = BN_new()) == NULL)
+		fatal("%s: BN_new failed", __func__);
+	if (BN_bin2bn(shared_secret_raw, sizeof(shared_secret_raw), shared_secret) ==
NULL)
+		fatal("%s: BN_bin2bn failed", __func__);
+	memset(shared_secret_raw, 0, sizeof(shared_secret_raw));
+
+	/* calc and verify H */
+	kex_c25519_hash(
+	    kex->evp_md,
+	    kex->client_version_string,
+	    kex->server_version_string,
+	    buffer_ptr(&kex->my), buffer_len(&kex->my),
+	    buffer_ptr(&kex->peer), buffer_len(&kex->peer),
+	    server_host_key_blob, sbloblen,
+	    client_pubkey,
+	    server_pubkey,
+	    shared_secret,
+	    &hash, &hashlen
+	);
+	free(server_host_key_blob);
+	free(server_pubkey);
+	if (key_verify(server_host_key, signature, slen, hash, hashlen) != 1)
+		fatal("key_verify failed for server_host_key");
+	key_free(server_host_key);
+	free(signature);
+
+	/* save session id */
+	if (kex->session_id == NULL) {
+		kex->session_id_len = hashlen;
+		kex->session_id = xmalloc(kex->session_id_len);
+		memcpy(kex->session_id, hash, kex->session_id_len);
+	}
+
+	kex_derive_keys(kex, hash, hashlen, shared_secret);
+	BN_clear_free(shared_secret);
+	kex_finish(kex);
+}
diff --git a/kexc25519s.c b/kexc25519s.c
new file mode 100644
index 0000000..51fa24a
--- /dev/null
+++ b/kexc25519s.c
@@ -0,0 +1,144 @@
+/*
+ * Copyright (c) 2001 Markus Friedl.  All rights reserved.
+ * Copyright (c) 2010 Damien Miller.  All rights reserved.
+ * Copyright (c) 2013 Aris Adamantiadis.  All rights reserved.
+ *
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "includes.h"
+
+#include <sys/types.h>
+#include <string.h>
+#include <signal.h>
+
+#include "xmalloc.h"
+#include "buffer.h"
+#include "key.h"
+#include "cipher.h"
+#include "kex.h"
+#include "log.h"
+#include "packet.h"
+#include "dh.h"
+#include "ssh2.h"
+#include "monitor_wrap.h"
+
+#include <nacl/crypto_scalarmult_curve25519.h>
+#define CURVE25519_PUBKEY_SIZE crypto_scalarmult_curve25519_BYTES
+#define CURVE25519_PRIVKEY_SIZE crypto_scalarmult_curve25519_SCALARBYTES
+
+void
+kexc25519_server(Kex *kex)
+{
+	BIGNUM *shared_secret;
+	Key *server_host_private, *server_host_public;
+	u_char *server_host_key_blob = NULL, *signature = NULL;
+        u_char server_key[CURVE25519_PRIVKEY_SIZE];
+        u_char *client_pubkey = NULL;
+        u_char server_pubkey[CURVE25519_PUBKEY_SIZE];
+        u_char shared_secret_raw[CURVE25519_PUBKEY_SIZE];
+	u_char *hash;
+	u_int rnd=0, slen, sbloblen, hashlen, i;
+
+        /* generate private key */
+        for (i = 0; i < sizeof(server_key); i++) {
+                if (i % 4 == 0)
+                        rnd = arc4random();
+                server_key[i] = rnd;
+                rnd >>= 8;
+        }
+        crypto_scalarmult_curve25519_base(server_pubkey, server_key);
+#ifdef DEBUG_KEXECDH
+        dump_digest("server private key:", server_key,
sizeof(server_key));
+#endif
+
+	if (kex->load_host_public_key == NULL ||
+	    kex->load_host_private_key == NULL)
+		fatal("Cannot load hostkey");
+	server_host_public = kex->load_host_public_key(kex->hostkey_type);
+	if (server_host_public == NULL)
+		fatal("Unsupported hostkey type %d", kex->hostkey_type);
+	server_host_private = kex->load_host_private_key(kex->hostkey_type);
+
+	debug("expecting SSH2_MSG_KEX_ECDH_INIT");
+	packet_read_expect(SSH2_MSG_KEX_ECDH_INIT);
+	client_pubkey = packet_get_string(&slen);
+        if (slen != CURVE25519_PUBKEY_SIZE)
+                fatal("Incorrect size for server Curve25519 public key:
%d", slen);
+	packet_check_eom();
+
+#ifdef DEBUG_KEXECDH
+        dump_digest("client public key:\n", client_pubkey,
CURVE25519_PUBKEY_SIZE);
+#endif
+
+	crypto_scalarmult_curve25519(shared_secret_raw, server_key, client_pubkey);
+
+#ifdef DEBUG_KEXECDH
+	dump_digest("shared secret", shared_secret_raw,
sizeof(shared_secret_raw));
+#endif
+	if ((shared_secret = BN_new()) == NULL)
+		fatal("%s: BN_new failed", __func__);
+	if (BN_bin2bn(shared_secret_raw, sizeof(shared_secret_raw), shared_secret) ==
NULL)
+		fatal("%s: BN_bin2bn failed", __func__);
+	memset(shared_secret_raw, 0, sizeof(shared_secret_raw));
+
+	/* calc H */
+	key_to_blob(server_host_public, &server_host_key_blob, &sbloblen);
+        kex_c25519_hash(
+            kex->evp_md,
+            kex->client_version_string,
+            kex->server_version_string,
+            buffer_ptr(&kex->peer), buffer_len(&kex->peer),
+            buffer_ptr(&kex->my), buffer_len(&kex->my),
+            server_host_key_blob, sbloblen,
+            client_pubkey,
+            server_pubkey,
+            shared_secret,
+            &hash, &hashlen
+        );
+
+	/* save session id := H */
+	if (kex->session_id == NULL) {
+		kex->session_id_len = hashlen;
+		kex->session_id = xmalloc(kex->session_id_len);
+		memcpy(kex->session_id, hash, kex->session_id_len);
+	}
+
+	/* sign H */
+	kex->sign(server_host_private, server_host_public, &signature,
&slen,
+	    hash, hashlen);
+
+	/* destroy_sensitive_data(); */
+
+	/* send server hostkey, ECDH pubkey 'Q_S' and signed H */
+	packet_start(SSH2_MSG_KEX_ECDH_REPLY);
+	packet_put_string(server_host_key_blob, sbloblen);
+	packet_put_string(server_pubkey, sizeof(server_pubkey));
+	packet_put_string(signature, slen);
+	packet_send();
+
+	free(signature);
+	free(server_host_key_blob);
+	/* have keys, free server key */
+	free(client_pubkey);
+	kex_derive_keys(kex, hash, hashlen, shared_secret);
+	BN_clear_free(shared_secret);
+	kex_finish(kex);
+}
diff --git a/myproposal.h b/myproposal.h
index 4e913e3..0d88090 100644
--- a/myproposal.h
+++ b/myproposal.h
@@ -66,6 +66,7 @@
 #endif
 
 # define KEX_DEFAULT_KEX \
+	"curve25519-sha256 at libssh.org," \
 	KEX_ECDH_METHODS \
 	KEX_SHA256_METHODS \
 	"diffie-hellman-group-exchange-sha1," \
diff --git a/ssh-keyscan.c b/ssh-keyscan.c
index 8b807c1..dfe561b 100644
--- a/ssh-keyscan.c
+++ b/ssh-keyscan.c
@@ -254,6 +254,7 @@ keygrab_ssh2(con *c)
 	c->c_kex->kex[KEX_DH_GEX_SHA1] = kexgex_client;
 	c->c_kex->kex[KEX_DH_GEX_SHA256] = kexgex_client;
 	c->c_kex->kex[KEX_ECDH_SHA2] = kexecdh_client;
+	c->c_kex->kex[KEX_C25519_SHA256] = kexc25519_client;
 	c->c_kex->verify_host_key = hostjump;
 
 	if (!(j = setjmp(kexjmp))) {
diff --git a/sshconnect2.c b/sshconnect2.c
index 70e3cd8..68031a5 100644
--- a/sshconnect2.c
+++ b/sshconnect2.c
@@ -208,6 +208,7 @@ ssh_kex2(char *host, struct sockaddr *hostaddr, u_short
port)
 	kex->kex[KEX_DH_GEX_SHA1] = kexgex_client;
 	kex->kex[KEX_DH_GEX_SHA256] = kexgex_client;
 	kex->kex[KEX_ECDH_SHA2] = kexecdh_client;
+	kex->kex[KEX_C25519_SHA256] = kexc25519_client;
 	kex->client_version_string=client_version_string;
 	kex->server_version_string=server_version_string;
 	kex->verify_host_key=&verify_host_key_callback;
diff --git a/sshd.c b/sshd.c
index 174cc7a..56f75d9 100644
--- a/sshd.c
+++ b/sshd.c
@@ -2446,6 +2446,7 @@ do_ssh2_kex(void)
 	kex->kex[KEX_DH_GEX_SHA1] = kexgex_server;
 	kex->kex[KEX_DH_GEX_SHA256] = kexgex_server;
 	kex->kex[KEX_ECDH_SHA2] = kexecdh_server;
+	kex->kex[KEX_C25519_SHA256] = kexc25519_server;
 	kex->server = 1;
 	kex->client_version_string=client_version_string;
 	kex->server_version_string=server_version_string;
-- 
1.7.10.4

thanks, i was looking into doing this, too.
still looking for a way to keep the number of dublicated lines down....

Am 24.09.2013 um 22:21 schrieb Aris Adamantiadis <aris at 0xbadc0de.be>:
> <0001-kex-implement-curve25519-sha256-libssh.org.patch>

Cool.

Did you consider ed25519 for the kex?

http://ed25519.cr.yp.to/

-JimC
-- 
James Cloos <cloos at jhcloos.com>         OpenPGP: 1024D/ED7DAEA6

On Tue, 24 Sep 2013, Aris Adamantiadis wrote:
> Dear OpenSSH developers,
> 
> I've worked this week on an alternative key exchange mechanism, in
> reaction to the whole NSA leaks and claims over cryptographic backdoors
> and/or cracking advances. The key exchange is in my opinion the most
> critical defense against passive eavesdropping attacks.
> I believe Curve25519 from DJB can give users a secure alternative to
> classical Diffie-Hellman (with fixed groups or group exchanges) and
> NIST-approved elliptic curves.
...

I just had a quick look at the patch. Overall it's good; some preliminary
comments below.

diff --git a/kexc25519.c b/kexc25519.c
new file mode 100644
index 0000000..8260fad
--- /dev/null
+++ b/kexc25519.c
...
+#include <nacl/crypto_scalarmult_curve25519.h>
+#define CURVE25519_PUBKEY_SIZE crypto_scalarmult_curve25519_BYTES

For OpenSSH, I think we could just include the portable C version from
https://code.google.com/p/curve25519-donna/ rather than depending on
the entirety of nacl. nacl includes a heap of stuff that we don't need
and makes some unusual design choices like choosing between native
implementations by measuring the host it is being compiled on.

The downside to the -donna implementation is that it doesn't promise
constant time execution. AFAIK this isn't a killer for the SSH case as
an attacker doesn't get to measure the processing time for any set of DH
public values more than once. It would be worse if we reused DH values,
but we don't. (-donna also has the disadvantage of being slower, but were
quibbling over single-digit milliseconds here so IMO it doesn't matter at
all.)

+void
+kex_c25519_hash(
+    const EVP_MD *evp_md,
+    char *client_version_string,
+    char *server_version_string,
+    char *ckexinit, int ckexinitlen,
+    char *skexinit, int skexinitlen,
+    u_char *serverhostkeyblob, int sbloblen,
+    const unsigned char client_dh_pub[CURVE25519_PUBKEY_SIZE],
+    const unsigned char server_dh_pub[CURVE25519_PUBKEY_SIZE],
+    const BIGNUM *shared_secret,
...
+	buffer_put_bignum2(&b, shared_secret);

It would be simpler to pass the shared_secret as a const u_char* and
length here - saving a round-trip to BIGNUM and back.

diff --git a/kexc25519c.c b/kexc25519c.c
new file mode 100644
index 0000000..b2000f0
--- /dev/null
+++ b/kexc25519c.c
...
+void
+kexc25519_client(Kex *kex)
+{
...
+	/* generate private key */
+	for (i = 0; i < sizeof(client_key); i++) {
+		if (i % 4 == 0)
+			rnd = arc4random();
+		client_key[i] = rnd;
+		rnd >>= 8;
+        }

easier to use arc4random_buf() here. If we use the -donna implementation
then we need to do the 

client_key[0] &= 248;
client_key[31] &= 127;
client_key[31] |= 64;

ourselves. It might be better to have put a kex_c25519_genkey() in
kexc25519.c that does it all and use it in both the client and server.

-d

Hi,

For my part I chose Curve25519 because it''s there since a while and had
time to be studied. The other curves you mention have all been
introduced in 2013. I don''t know enough mathematics to criticize any of
these curves, but letting some times for others to do so seems prudent.

Aris

Le 4/11/13 21:40, mancha a écrit :
> Curve2213, Curve1174, Curve383187, and Curve3617

Aris Adamantiadis <aris <at> 0xbadc0de.be>
writes:
> Hi,
> 
> For my part I chose Curve25519 because it''s there since a while
and had
> time to be studied. The other curves you mention have all been
> introduced in 2013. I don''t know enough mathematics to criticize
any of
> these curves, but letting some times for others to do so seems prudent.
Aris:

Thank you for your reply.

Let me follow-up my post to make sure I am not misunderstood.

Given questionable explanations/rationale surrounding constant selection
in some NIST curves, there is genuine justification for considering
alternatives. I thank you for your valuable contribution with this and
thank the OpenSSH developers for embracing it.

Dr. Bernstein''s track record is quite impressive and like you I share
the belief that generally in cryptography "older is better". More
specifically, Curve25519 is impervious to Pohlig-Hellman and twist
attacks. Also, we ensure primes are large enough to mitigate attacks
such as Pollard''s rho, Shank''s, etc. As far as implementation,
NaCl''s
certainly appears quite crisp (https://twitter.com/tweetnacl).

That said, a key lesson from the NIST curve controversy is the
importance of retaining a healthy dose of skepticism. And I do.

Finally, there''s a high value to the OpenSSH community in expanding
options available (kexalg, mac, cipher, etc.) so let me express my
hope for continued vigorous activity in this area.

Many thanks.

--mancha

On Tue, 5 Nov 2013, mancha wrote:
> Finally, there''s a high value to the OpenSSH community in
expanding
> options available (kexalg, mac, cipher, etc.) so let me express my
> hope for continued vigorous activity in this area.
There''s also cost. Each new algorithm we add increases attack surface
and maintenance cost. We don''t want to add things just because they
are available, they have to offer something that the current set of
options don''t. 

At the moment, we''re only looking at adding ed25519 as a public-key
algorithm and chacha20+poly1305 as an AEAD similar to Adam Langley''s
proposal for TLS:

http://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-01

-d

On Tue, Nov 05, 2013 at 03:25:15PM +0100, Aris Adamantiadis
wrote:
> Hi,
> 
> For my part I chose Curve25519 because it''s there since a while
and had
> time to be studied. The other curves you mention have all been
> introduced in 2013.
Additional good reasons are that Curve25519 is used elsewhere in real
things: DNSCurve, Tor (newer versions), DNSCrypt, ZeroMQ.  Curve25519
is also in CurveCP, MinimaLT, and will be added to Google''s new QUIC
protocol.

Big thanks to Aris for this!

Nicolai

Damien Miller <djm <at> mindrot.org> writes:
> We don''t want to add things just because they are available, they
have
> to offer something that the current set of options don''t. 
I can see how my comment could be misinterpreted but I''m certainly not
suggesting that. What I tried to say (awkwardly) is that in the current
context there''s value in continually re-visiting assumptions and a 
role for risk-reducing diversification that, if warranted, expands options
beyond the bounds of controversial standards-driven suites.
> At the moment, we''re only looking at adding ed25519 as a
public-key
> algorithm and chacha20+poly1305 as an AEAD similar to Adam
Langley''s
> proposal for TLS
That sounds like a great complement to aes{128,256}-gcm@openssh.com.
Have you been tracking his progress so far? e.g.:
http://git.openssl.org/gitweb/?p=openssl.git;a=commitdiff;h=9a8646510b

PS I was very anxious to test Curve25519 so I ported Markus'' recent
commits to 6.3p1. For those running portable who are interested in giving
this a whirl, I''ve posted here:

http://sf.net/projects/mancha/files/misc/openssh-6.3p1-curve25519.diff

Cheers.

--mancha

On Thu, 7 Nov 2013, Aris Adamantiadis wrote:
> Le 7/11/13 00:28, mancha a ?crit :
> > 
> > That sounds like a great complement to aes{128,256}-gcm@openssh.com.
> > Have you been tracking his progress so far? e.g.:
> > http://git.openssl.org/gitweb/?p=openssl.git;a=commitdiff;h=9a8646510b
> 
> I am not very comfortable with aes*-gcm@openssh.com because the packet
> len is not encrypted under the claim that it is not possible to do both
> encryption and authentication on the length field. I believe
that''s not
> true, a competing authenticated encryption mechanism should fix this
> (e.g. by sending an authentication token on both every encrypted length
> and packet payload).
> 
> This unencrypted length thing brings SSH2 back to the SSH1 days where it
> was trivial to sniff the length of a password. Contrary to what the RFC
> tells, sending ignore packets doesn''t help.
You might be interested in the ChaCha20+Poly1305 proposal diff that I just
sent to the openssh-unix-dev@ mailing list. It uses a separate stream
cipher instance to encrypt the packet lengths.

-d