Add support for Curve25519 using the public domain code that is found

in OpenSSH.  The "private use" DH group 1034 is based on the value
that was picked by strongswan recently.

OK mikeb@ markus@

7 files changed, 362 insertions, 15 deletions

diff --git a/sbin/iked/Makefile b/sbin/iked/Makefile
index 94b5f13a4ac..85d4c39330a 100644
--- a/sbin/iked/Makefile
+++ b/sbin/iked/Makefile
@@ -1,9 +1,10 @@
-# $OpenBSD: Makefile,v 1.11 2014/02/17 15:07:23 markus Exp $
+# $OpenBSD: Makefile,v 1.12 2014/08/27 10:28:57 reyk Exp $
 
 PROG=		iked
 SRCS=		ca.c chap_ms.c config.c control.c crypto.c dh.c \
 		eap.c iked.c ikev1.c ikev2.c ikev2_msg.c ikev2_pld.c \
-		log.c ocsp.c pfkey.c policy.c proc.c timer.c util.c imsg_util.c
+		log.c ocsp.c pfkey.c policy.c proc.c timer.c util.c \
+		imsg_util.c smult_curve25519_ref.c
 SRCS+=		eap_map.c ikev2_map.c
 SRCS+=		parse.y
 MAN=		iked.conf.5 iked.8
diff --git a/sbin/iked/dh.c b/sbin/iked/dh.c
index 8033a026564..7a26712a2bb 100644
--- a/sbin/iked/dh.c
+++ b/sbin/iked/dh.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: dh.c,v 1.13 2014/08/25 14:36:10 reyk Exp $	*/
+/*	$OpenBSD: dh.c,v 1.14 2014/08/27 10:28:57 reyk Exp $	*/
 
 /*
  * Copyright (c) 2010-2014 Reyk Floeter <reyk@openbsd.org>
@@ -29,11 +29,13 @@
 
 int	dh_init(struct group *);
 
+/* MODP */
 int	modp_init(struct group *);
 int	modp_getlen(struct group *);
 int	modp_create_exchange(struct group *, u_int8_t *);
 int	modp_create_shared(struct group *, u_int8_t *, u_int8_t *);
 
+/* EC2N/ECP */
 int	ec_init(struct group *);
 int	ec_getlen(struct group *);
 int	ec_create_exchange(struct group *, u_int8_t *);
@@ -43,6 +45,23 @@ int	ec_point2raw(struct group *, const EC_POINT *, u_int8_t *, size_t);
 EC_POINT *
 	ec_raw2point(struct group *, u_int8_t *, size_t);
 
+/* curve25519 */
+int	ec25519_init(struct group *);
+int	ec25519_getlen(struct group *);
+int	ec25519_create_exchange(struct group *, u_int8_t *);
+int	ec25519_create_shared(struct group *, u_int8_t *, u_int8_t *);
+
+#define CURVE25519_SIZE 32	/* 256 bits */
+struct curve25519_key {
+	u_int8_t	 secret[CURVE25519_SIZE];
+	u_int8_t	 public[CURVE25519_SIZE];
+};
+extern int crypto_scalarmult_curve25519(u_char a[CURVE25519_SIZE],
+    const u_char b[CURVE25519_SIZE], const u_char c[CURVE25519_SIZE])
+	__attribute__((__bounded__(__minbytes__, 1, CURVE25519_SIZE)))
+	__attribute__((__bounded__(__minbytes__, 2, CURVE25519_SIZE)))
+	__attribute__((__bounded__(__minbytes__, 3, CURVE25519_SIZE)));
+
 struct group_id ike_groups[] = {
 	{ GROUP_MODP, 1, 768,
 	    "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
@@ -282,7 +301,10 @@ struct group_id ike_groups[] = {
 	{ GROUP_ECP, 27, 224, NULL, NULL, NID_brainpoolP224r1 },
 	{ GROUP_ECP, 28, 256, NULL, NULL, NID_brainpoolP256r1 },
 	{ GROUP_ECP, 29, 384, NULL, NULL, NID_brainpoolP384r1 },
-	{ GROUP_ECP, 30, 512, NULL, NULL, NID_brainpoolP512r1 }
+	{ GROUP_ECP, 30, 512, NULL, NULL, NID_brainpoolP512r1 },
+
+	/* "Private use" extensions */
+	{ GROUP_CURVE25519, 1034, CURVE25519_SIZE * 8 }
 };
 
 void
@@ -301,6 +323,11 @@ group_free(struct group *group)
 		DH_free(group->dh);
 	if (group->ec != NULL)
 		EC_KEY_free(group->ec);
+	if (group->curve25519 != NULL) {
+		explicit_bzero(group->curve25519,
+		    sizeof(struct curve25519_key));
+		free(group->curve25519);
+	}
 	group->spec = NULL;
 	free(group);
 }
@@ -342,6 +369,12 @@ group_get(u_int32_t id)
 		group->exchange = ec_create_exchange;
 		group->shared = ec_create_shared;
 		break;
+	case GROUP_CURVE25519:
+		group->init = ec25519_init;
+		group->getlen = ec25519_getlen;
+		group->exchange = ec25519_create_exchange;
+		group->shared = ec25519_create_shared;
+		break;
 	default:
 		group_free(group);
 		return (NULL);
@@ -650,3 +683,47 @@ ec_raw2point(struct group *group, u_int8_t *buf, size_t len)
 
 	return (point);
 }
+
+int
+ec25519_init(struct group *group)
+{
+	static const u_int8_t	 basepoint[CURVE25519_SIZE] = { 9 };
+	struct curve25519_key	*curve25519;
+
+	if ((curve25519 = calloc(1, sizeof(*curve25519))) == NULL)
+		return (-1);
+
+	group->curve25519 = curve25519;
+
+	arc4random_buf(curve25519->secret, CURVE25519_SIZE);
+	crypto_scalarmult_curve25519(curve25519->public,
+	    curve25519->secret, basepoint);
+
+	return (0);
+}
+
+int
+ec25519_getlen(struct group *group)
+{
+	if (group->spec == NULL)
+		return (0);
+	return (CURVE25519_SIZE);
+}
+
+int
+ec25519_create_exchange(struct group *group, u_int8_t *buf)
+{
+	struct curve25519_key	*curve25519 = group->curve25519;
+
+	memcpy(buf, curve25519->public, ec25519_getlen(group));
+	return (0);
+}
+
+int
+ec25519_create_shared(struct group *group, u_int8_t *shared, u_int8_t *public)
+{
+	struct curve25519_key	*curve25519 = group->curve25519;
+
+	crypto_scalarmult_curve25519(shared, curve25519->secret, public);
+	return (0);
+}
diff --git a/sbin/iked/dh.h b/sbin/iked/dh.h
index d7b8ea805a5..1abd9952af9 100644
--- a/sbin/iked/dh.h
+++ b/sbin/iked/dh.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: dh.h,v 1.5 2013/01/08 10:38:19 reyk Exp $	*/
+/*	$OpenBSD: dh.h,v 1.6 2014/08/27 10:28:57 reyk Exp $	*/
 
 /*
  * Copyright (c) 2010-2013 Reyk Floeter <reyk@openbsd.org>
@@ -20,9 +20,10 @@
 #define _DH_H_
 
 enum group_type {
-	GROUP_MODP	= 0,
-	GROUP_EC2N	= 1,
-	GROUP_ECP	= 2
+	GROUP_MODP		= 0,
+	GROUP_EC2N		= 1,
+	GROUP_ECP		= 2,
+	GROUP_CURVE25519	= 3
 };
 
 struct group_id {
@@ -40,6 +41,7 @@ struct group {
 
 	void		*dh;
 	void		*ec;
+	void		*curve25519;
 
 	int		(*init)(struct group *);
 	int		(*getlen)(struct group *);
diff --git a/sbin/iked/iked.conf.5 b/sbin/iked/iked.conf.5
index fbe71bb154f..ccb8f5cbc73 100644
--- a/sbin/iked/iked.conf.5
+++ b/sbin/iked/iked.conf.5
@@ -1,4 +1,4 @@
-.\" $OpenBSD: iked.conf.5,v 1.34 2014/08/25 14:36:10 reyk Exp $
+.\" $OpenBSD: iked.conf.5,v 1.35 2014/08/27 10:28:57 reyk Exp $
 .\"
 .\" Copyright (c) 2010 - 2014 Reyk Floeter <reyk@openbsd.org>
 .\" Copyright (c) 2004 Mathieu Sauve-Frankel  All rights reserved.
@@ -15,7 +15,7 @@
 .\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 .\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 .\"
-.Dd $Mdocdate: August 25 2014 $
+.Dd $Mdocdate: August 27 2014 $
 .Dt IKED.CONF 5
 .Os
 .Sh NAME
@@ -820,13 +820,14 @@ keyword:
 .It Li brainpool256 Ta grp28 Ta 256 Ta "ECP, brainpoolP256r1"
 .It Li brainpool384 Ta grp29 Ta 384 Ta "ECP, brainpoolP384r1"
 .It Li brainpool512 Ta grp30 Ta 512 Ta "ECP, brainpoolP512r1"
+.It Li curve25519 Ta - Ta 256 Ta "Curve25519"
 .El
 .Pp
 The currently supported group types are either
 MODP (exponentiation groups modulo a prime),
 EC2N (elliptic curve groups over GF[2^N]),
-or
-ECP (elliptic curve groups modulo a prime).
+ECP (elliptic curve groups modulo a prime),
+or the non-standard Curve25519.
 Please note that the EC2N groups are considered as insecure and only
 provided for backwards compatibility.
 .Sh EXAMPLES
diff --git a/sbin/iked/ikev2.h b/sbin/iked/ikev2.h
index 652cf875bea..5fed74ea0f9 100644
--- a/sbin/iked/ikev2.h
+++ b/sbin/iked/ikev2.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ikev2.h,v 1.15 2014/05/06 10:24:22 markus Exp $	*/
+/*	$OpenBSD: ikev2.h,v 1.16 2014/08/27 10:28:57 reyk Exp $	*/
 
 /*
  * Copyright (c) 2010-2013 Reyk Floeter <reyk@openbsd.org>
@@ -241,7 +241,7 @@ extern struct iked_constmap ikev2_xformauth_map[];
 #define IKEV2_XFORMDH_BRAINPOOL_P256R1	28	/* DH Group 28 */
 #define IKEV2_XFORMDH_BRAINPOOL_P384R1	29	/* DH Group 29 */
 #define IKEV2_XFORMDH_BRAINPOOL_P512R1	30	/* DH Group 30 */
-#define IKEV2_XFORMDH_MAX		31
+#define IKEV2_XFORMDH_X_CURVE25519	1034	/* curve25519 */
 
 extern struct iked_constmap ikev2_xformdh_map[];
 
diff --git a/sbin/iked/parse.y b/sbin/iked/parse.y
index 9e8efeeb4d1..ba300bfc427 100644
--- a/sbin/iked/parse.y
+++ b/sbin/iked/parse.y
@@ -1,4 +1,4 @@
-/*	$OpenBSD: parse.y,v 1.39 2014/08/25 14:36:10 reyk Exp $	*/
+/*	$OpenBSD: parse.y,v 1.40 2014/08/27 10:28:57 reyk Exp $	*/
 
 /*
  * Copyright (c) 2010-2013 Reyk Floeter <reyk@openbsd.org>
@@ -245,6 +245,7 @@ const struct ipsec_xf groupxfs[] = {
 	{ "grp29",		IKEV2_XFORMDH_BRAINPOOL_P384R1 },
 	{ "brainpool512",	IKEV2_XFORMDH_BRAINPOOL_P512R1 },
 	{ "grp30",		IKEV2_XFORMDH_BRAINPOOL_P512R1 },
+	{ "curve25519",		IKEV2_XFORMDH_X_CURVE25519 },
 	{ NULL }
 };
 
diff --git a/sbin/iked/smult_curve25519_ref.c b/sbin/iked/smult_curve25519_ref.c
new file mode 100644
index 00000000000..71c106a2c8d
--- /dev/null
+++ b/sbin/iked/smult_curve25519_ref.c
@@ -0,0 +1,265 @@
+/* $OpenBSD: smult_curve25519_ref.c,v 1.1 2014/08/27 10:28:57 reyk Exp $ */
+/*
+version 20081011
+Matthew Dempsky
+Public domain.
+Derived from public domain code by D. J. Bernstein.
+*/
+
+int crypto_scalarmult_curve25519(unsigned char *, const unsigned char *, const unsigned char *);
+
+static void add(unsigned int out[32],const unsigned int a[32],const unsigned int b[32])
+{
+  unsigned int j;
+  unsigned int u;
+  u = 0;
+  for (j = 0;j < 31;++j) { u += a[j] + b[j]; out[j] = u & 255; u >>= 8; }
+  u += a[31] + b[31]; out[31] = u;
+}
+
+static void sub(unsigned int out[32],const unsigned int a[32],const unsigned int b[32])
+{
+  unsigned int j;
+  unsigned int u;
+  u = 218;
+  for (j = 0;j < 31;++j) {
+    u += a[j] + 65280 - b[j];
+    out[j] = u & 255;
+    u >>= 8;
+  }
+  u += a[31] - b[31];
+  out[31] = u;
+}
+
+static void squeeze(unsigned int a[32])
+{
+  unsigned int j;
+  unsigned int u;
+  u = 0;
+  for (j = 0;j < 31;++j) { u += a[j]; a[j] = u & 255; u >>= 8; }
+  u += a[31]; a[31] = u & 127;
+  u = 19 * (u >> 7);
+  for (j = 0;j < 31;++j) { u += a[j]; a[j] = u & 255; u >>= 8; }
+  u += a[31]; a[31] = u;
+}
+
+static const unsigned int minusp[32] = {
+ 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128
+} ;
+
+static void freeze(unsigned int a[32])
+{
+  unsigned int aorig[32];
+  unsigned int j;
+  unsigned int negative;
+
+  for (j = 0;j < 32;++j) aorig[j] = a[j];
+  add(a,a,minusp);
+  negative = -((a[31] >> 7) & 1);
+  for (j = 0;j < 32;++j) a[j] ^= negative & (aorig[j] ^ a[j]);
+}
+
+static void mult(unsigned int out[32],const unsigned int a[32],const unsigned int b[32])
+{
+  unsigned int i;
+  unsigned int j;
+  unsigned int u;
+
+  for (i = 0;i < 32;++i) {
+    u = 0;
+    for (j = 0;j <= i;++j) u += a[j] * b[i - j];
+    for (j = i + 1;j < 32;++j) u += 38 * a[j] * b[i + 32 - j];
+    out[i] = u;
+  }
+  squeeze(out);
+}
+
+static void mult121665(unsigned int out[32],const unsigned int a[32])
+{
+  unsigned int j;
+  unsigned int u;
+
+  u = 0;
+  for (j = 0;j < 31;++j) { u += 121665 * a[j]; out[j] = u & 255; u >>= 8; }
+  u += 121665 * a[31]; out[31] = u & 127;
+  u = 19 * (u >> 7);
+  for (j = 0;j < 31;++j) { u += out[j]; out[j] = u & 255; u >>= 8; }
+  u += out[j]; out[j] = u;
+}
+
+static void square(unsigned int out[32],const unsigned int a[32])
+{
+  unsigned int i;
+  unsigned int j;
+  unsigned int u;
+
+  for (i = 0;i < 32;++i) {
+    u = 0;
+    for (j = 0;j < i - j;++j) u += a[j] * a[i - j];
+    for (j = i + 1;j < i + 32 - j;++j) u += 38 * a[j] * a[i + 32 - j];
+    u *= 2;
+    if ((i & 1) == 0) {
+      u += a[i / 2] * a[i / 2];
+      u += 38 * a[i / 2 + 16] * a[i / 2 + 16];
+    }
+    out[i] = u;
+  }
+  squeeze(out);
+}
+
+static void select(unsigned int p[64],unsigned int q[64],const unsigned int r[64],const unsigned int s[64],unsigned int b)
+{
+  unsigned int j;
+  unsigned int t;
+  unsigned int bminus1;
+
+  bminus1 = b - 1;
+  for (j = 0;j < 64;++j) {
+    t = bminus1 & (r[j] ^ s[j]);
+    p[j] = s[j] ^ t;
+    q[j] = r[j] ^ t;
+  }
+}
+
+static void mainloop(unsigned int work[64],const unsigned char e[32])
+{
+  unsigned int xzm1[64];
+  unsigned int xzm[64];
+  unsigned int xzmb[64];
+  unsigned int xzm1b[64];
+  unsigned int xznb[64];
+  unsigned int xzn1b[64];
+  unsigned int a0[64];
+  unsigned int a1[64];
+  unsigned int b0[64];
+  unsigned int b1[64];
+  unsigned int c1[64];
+  unsigned int r[32];
+  unsigned int s[32];
+  unsigned int t[32];
+  unsigned int u[32];
+  unsigned int j;
+  unsigned int b;
+  int pos;
+
+  for (j = 0;j < 32;++j) xzm1[j] = work[j];
+  xzm1[32] = 1;
+  for (j = 33;j < 64;++j) xzm1[j] = 0;
+
+  xzm[0] = 1;
+  for (j = 1;j < 64;++j) xzm[j] = 0;
+
+  for (pos = 254;pos >= 0;--pos) {
+    b = e[pos / 8] >> (pos & 7);
+    b &= 1;
+    select(xzmb,xzm1b,xzm,xzm1,b);
+    add(a0,xzmb,xzmb + 32);
+    sub(a0 + 32,xzmb,xzmb + 32);
+    add(a1,xzm1b,xzm1b + 32);
+    sub(a1 + 32,xzm1b,xzm1b + 32);
+    square(b0,a0);
+    square(b0 + 32,a0 + 32);
+    mult(b1,a1,a0 + 32);
+    mult(b1 + 32,a1 + 32,a0);
+    add(c1,b1,b1 + 32);
+    sub(c1 + 32,b1,b1 + 32);
+    square(r,c1 + 32);
+    sub(s,b0,b0 + 32);
+    mult121665(t,s);
+    add(u,t,b0);
+    mult(xznb,b0,b0 + 32);
+    mult(xznb + 32,s,u);
+    square(xzn1b,c1);
+    mult(xzn1b + 32,r,work);
+    select(xzm,xzm1,xznb,xzn1b,b);
+  }
+
+  for (j = 0;j < 64;++j) work[j] = xzm[j];
+}
+
+static void recip(unsigned int out[32],const unsigned int z[32])
+{
+  unsigned int z2[32];
+  unsigned int z9[32];
+  unsigned int z11[32];
+  unsigned int z2_5_0[32];
+  unsigned int z2_10_0[32];
+  unsigned int z2_20_0[32];
+  unsigned int z2_50_0[32];
+  unsigned int z2_100_0[32];
+  unsigned int t0[32];
+  unsigned int t1[32];
+  int i;
+
+  /* 2 */ square(z2,z);
+  /* 4 */ square(t1,z2);
+  /* 8 */ square(t0,t1);
+  /* 9 */ mult(z9,t0,z);
+  /* 11 */ mult(z11,z9,z2);
+  /* 22 */ square(t0,z11);
+  /* 2^5 - 2^0 = 31 */ mult(z2_5_0,t0,z9);
+
+  /* 2^6 - 2^1 */ square(t0,z2_5_0);
+  /* 2^7 - 2^2 */ square(t1,t0);
+  /* 2^8 - 2^3 */ square(t0,t1);
+  /* 2^9 - 2^4 */ square(t1,t0);
+  /* 2^10 - 2^5 */ square(t0,t1);
+  /* 2^10 - 2^0 */ mult(z2_10_0,t0,z2_5_0);
+
+  /* 2^11 - 2^1 */ square(t0,z2_10_0);
+  /* 2^12 - 2^2 */ square(t1,t0);
+  /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { square(t0,t1); square(t1,t0); }
+  /* 2^20 - 2^0 */ mult(z2_20_0,t1,z2_10_0);
+
+  /* 2^21 - 2^1 */ square(t0,z2_20_0);
+  /* 2^22 - 2^2 */ square(t1,t0);
+  /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { square(t0,t1); square(t1,t0); }
+  /* 2^40 - 2^0 */ mult(t0,t1,z2_20_0);
+
+  /* 2^41 - 2^1 */ square(t1,t0);
+  /* 2^42 - 2^2 */ square(t0,t1);
+  /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { square(t1,t0); square(t0,t1); }
+  /* 2^50 - 2^0 */ mult(z2_50_0,t0,z2_10_0);
+
+  /* 2^51 - 2^1 */ square(t0,z2_50_0);
+  /* 2^52 - 2^2 */ square(t1,t0);
+  /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { square(t0,t1); square(t1,t0); }
+  /* 2^100 - 2^0 */ mult(z2_100_0,t1,z2_50_0);
+
+  /* 2^101 - 2^1 */ square(t1,z2_100_0);
+  /* 2^102 - 2^2 */ square(t0,t1);
+  /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { square(t1,t0); square(t0,t1); }
+  /* 2^200 - 2^0 */ mult(t1,t0,z2_100_0);
+
+  /* 2^201 - 2^1 */ square(t0,t1);
+  /* 2^202 - 2^2 */ square(t1,t0);
+  /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { square(t0,t1); square(t1,t0); }
+  /* 2^250 - 2^0 */ mult(t0,t1,z2_50_0);
+
+  /* 2^251 - 2^1 */ square(t1,t0);
+  /* 2^252 - 2^2 */ square(t0,t1);
+  /* 2^253 - 2^3 */ square(t1,t0);
+  /* 2^254 - 2^4 */ square(t0,t1);
+  /* 2^255 - 2^5 */ square(t1,t0);
+  /* 2^255 - 21 */ mult(out,t1,z11);
+}
+
+int crypto_scalarmult_curve25519(unsigned char *q,
+  const unsigned char *n,
+  const unsigned char *p)
+{
+  unsigned int work[96];
+  unsigned char e[32];
+  unsigned int i;
+  for (i = 0;i < 32;++i) e[i] = n[i];
+  e[0] &= 248;
+  e[31] &= 127;
+  e[31] |= 64;
+  for (i = 0;i < 32;++i) work[i] = p[i];
+  mainloop(work,e);
+  recip(work + 32,work + 32);
+  mult(work + 64,work,work + 32);
+  freeze(work + 64);
+  for (i = 0;i < 32;++i) q[i] = work[64 + i];
+  return 0;
+}