First rough implementation of the diffie-hellman group exchange. The

client can ask the server for bigger groups to perform the diffie-hellman
in, thus increasing the attack complexity when using ciphers with longer
keys.  University of Windsor provided network, T the company.

10 files changed, 762 insertions, 114 deletions

diff --git a/usr.bin/ssh/dh.c b/usr.bin/ssh/dh.c
new file mode 100644
index 00000000000..8f1ad19dd42
--- /dev/null
+++ b/usr.bin/ssh/dh.c
@@ -0,0 +1,158 @@
+/*
+ * Copyright (c) 2000 Niels Provos.  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"
+RCSID("$OpenBSD: dh.c,v 1.1 2000/10/11 04:02:16 provos Exp $");
+
+#include "xmalloc.h"
+
+#include <openssl/bn.h>
+#include <openssl/dh.h>
+#include <openssl/evp.h>
+
+#include "ssh.h"
+#include "buffer.h"
+#include "kex.h"
+#include "dh.h"
+
+int
+parse_prime(int linenum, char *line, struct dhgroup *dhg)
+{
+	char *cp, *arg;
+	char *strsize, *gen, *prime;
+
+	cp = line;
+	arg = strdelim(&cp);
+	/* Ignore leading whitespace */
+	if (*arg == '\0')
+		arg = strdelim(&cp);
+	if (!*arg || *arg == '#')
+		return 0;
+
+	/* time */
+	if (cp == NULL || *arg == '\0')
+		goto fail;
+	arg = strsep(&cp, " "); /* type */
+	if (cp == NULL || *arg == '\0')
+		goto fail;
+	arg = strsep(&cp, " "); /* tests */
+	if (cp == NULL || *arg == '\0')
+		goto fail;
+	arg = strsep(&cp, " "); /* tries */
+	if (cp == NULL || *arg == '\0')
+		goto fail;
+	strsize = strsep(&cp, " "); /* size */
+	if (cp == NULL || *strsize == '\0' ||
+	    (dhg->size = atoi(strsize)) == 0)
+		goto fail;
+	gen = strsep(&cp, " "); /* gen */
+	if (cp == NULL || *gen == '\0')
+		goto fail;
+	prime = strsep(&cp, " "); /* prime */
+	if (cp != NULL || *prime == '\0')
+		goto fail;
+
+	dhg->g = BN_new();
+	if (BN_hex2bn(&dhg->g, gen) < 0) {
+		BN_free(dhg->g);
+		goto fail;
+	}
+	dhg->p = BN_new();
+	if (BN_hex2bn(&dhg->p, prime) < 0) {
+		BN_free(dhg->g);
+		BN_free(dhg->p);
+		goto fail;
+	}
+
+	return (1);
+ fail:
+	fprintf(stderr, "Bad prime description in line %d\n", linenum);
+	return (0);
+}
+
+DH *
+choose_dh(int minbits)
+{
+	FILE *f;
+	char line[1024];
+	char *cp, *arg;
+	int best, bestcount, which;
+	int linenum;
+	struct dhgroup dhg;
+
+	f = fopen(DH_PRIMES, "r");
+	if (!f) {
+		perror(DH_PRIMES);
+		log("WARNING: %s does not exist, using old prime", DH_PRIMES);
+		return (dh_new_group1());
+	}
+
+	linenum = 0;
+	best = bestcount = 0;
+	while (fgets(line, sizeof(line), f)) {
+		linenum++;
+		if (!parse_prime(linenum, line, &dhg))
+			continue;
+		BN_free(dhg.g);
+		BN_free(dhg.p);
+
+		if ((dhg.size > minbits && dhg.size < best) ||
+		    (dhg.size > best && best < minbits)) {
+			best = dhg.size;
+			bestcount = 0;
+		}
+		if (dhg.size == best)
+			bestcount++;
+	}
+	fclose (f);
+
+	if (bestcount == 0) {
+		log("WARNING: no primes in %s, using old prime", DH_PRIMES);
+		return (dh_new_group1());
+	}
+
+	f = fopen(DH_PRIMES, "r");
+	if (!f) {
+		perror(DH_PRIMES);
+		exit(1);
+	}
+
+	linenum = 0;
+	which = arc4random() % bestcount;
+	while (fgets(line, sizeof(line), f)) {
+		if (!parse_prime(linenum, line, &dhg))
+			continue;
+		if (dhg.size != best)
+			continue;
+		if (linenum++ != which) {
+			BN_free(dhg.g);
+			BN_free(dhg.p);
+			continue;
+		}
+		break;
+	}
+	fclose(f);
+
+	return (dh_new_group(dhg.g, dhg.p));
+}
diff --git a/usr.bin/ssh/dh.h b/usr.bin/ssh/dh.h
new file mode 100644
index 00000000000..09b11fdbb80
--- /dev/null
+++ b/usr.bin/ssh/dh.h
@@ -0,0 +1,35 @@
+/*
+ * Copyright (c) 2000 Niels Provos.  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.
+ */
+#ifndef DH_H
+#define DH_H
+
+struct dhgroup {
+	int size;
+	BIGNUM *g;
+	BIGNUM *p;
+};
+
+DH *choose_dh(int minbits);
+
+#endif
diff --git a/usr.bin/ssh/kex.c b/usr.bin/ssh/kex.c
index 8a83db47e80..151dc1cffa4 100644
--- a/usr.bin/ssh/kex.c
+++ b/usr.bin/ssh/kex.c
@@ -23,7 +23,7 @@
  */
 
 #include "includes.h"
-RCSID("$OpenBSD: kex.c,v 1.10 2000/09/07 20:27:51 deraadt Exp $");
+RCSID("$OpenBSD: kex.c,v 1.11 2000/10/11 04:02:17 provos Exp $");
 
 #include "ssh.h"
 #include "ssh2.h"
@@ -123,11 +123,6 @@ dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 	int n = BN_num_bits(dh_pub);
 	int bits_set = 0;
 
-	/* we only accept g==2 */
-	if (!BN_is_word(dh->g, 2)) {
-		log("invalid DH base != 2");
-		return 0;
-	}
 	if (dh_pub->neg) {
 		log("invalid public DH value: negativ");
 		return 0;
@@ -145,27 +140,10 @@ dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 }
 
 DH *
-dh_new_group1()
+dh_gen_key(DH *dh)
 {
-	static char *group1 =
-	    "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
-	    "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
-	    "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
-	    "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
-	    "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
-	    "FFFFFFFF" "FFFFFFFF";
-	DH *dh;
-	int ret, tries = 0;
-	dh = DH_new();
-	if(dh == NULL)
-		fatal("DH_new");
-	ret = BN_hex2bn(&dh->p, group1);
-	if(ret<0)
-		fatal("BN_hex2bn");
-	dh->g = BN_new();
-	if(dh->g == NULL)
-		fatal("DH_new g");
-	BN_set_word(dh->g, 2);
+	int tries = 0;
+
 	do {
 		if (DH_generate_key(dh) == 0)
 			fatal("DH_generate_key");
@@ -175,6 +153,52 @@ dh_new_group1()
 	return dh;
 }
 
+DH *
+dh_new_group_asc(const char *gen, const char *modulus)
+{
+	DH *dh;
+	int ret;
+
+	dh = DH_new();
+	if (dh == NULL)
+		fatal("DH_new");
+
+	if ((ret = BN_hex2bn(&dh->p, modulus)) < 0)
+		fatal("BN_hex2bn p");
+	if ((ret = BN_hex2bn(&dh->g, gen)) < 0)
+		fatal("BN_hex2bn g");
+
+	return (dh_gen_key(dh));
+}
+
+DH *
+dh_new_group(BIGNUM *gen, BIGNUM *modulus)
+{
+	DH *dh;
+
+	dh = DH_new();
+	if (dh == NULL)
+		fatal("DH_new");
+	dh->p = modulus;
+	dh->g = gen;
+
+	return (dh_gen_key(dh));
+}
+
+DH *
+dh_new_group1()
+{
+	static char *gen = "2", *group1 =
+	    "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
+	    "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
+	    "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
+	    "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
+	    "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
+	    "FFFFFFFF" "FFFFFFFF";
+
+	return (dh_new_group_asc(gen, group1));
+}
+
 void
 dump_digest(unsigned char *digest, int len)
 {
@@ -237,6 +261,59 @@ kex_hash(
 }
 
 unsigned char *
+kex_hash_gex(
+    char *client_version_string,
+    char *server_version_string,
+    char *ckexinit, int ckexinitlen,
+    char *skexinit, int skexinitlen,
+    char *serverhostkeyblob, int sbloblen,
+    int minbits, BIGNUM *prime, BIGNUM *gen,
+    BIGNUM *client_dh_pub,
+    BIGNUM *server_dh_pub,
+    BIGNUM *shared_secret)
+{
+	Buffer b;
+	static unsigned char digest[EVP_MAX_MD_SIZE];
+	EVP_MD *evp_md = EVP_sha1();
+	EVP_MD_CTX md;
+
+	buffer_init(&b);
+	buffer_put_string(&b, client_version_string, strlen(client_version_string));
+	buffer_put_string(&b, server_version_string, strlen(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_int(&b, minbits);
+	buffer_put_bignum2(&b, prime);
+	buffer_put_bignum2(&b, gen);
+	buffer_put_bignum2(&b, client_dh_pub);
+	buffer_put_bignum2(&b, server_dh_pub);
+	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(digest, evp_md->md_size);
+#endif
+	return digest;
+}
+
+unsigned char *
 derive_key(int id, int need, char unsigned *hash, BIGNUM *shared_secret)
 {
 	Buffer b;
@@ -387,7 +464,11 @@ choose_kex(Kex *k, char *client, char *server)
 	k->name = get_match(client, server);
 	if (k->name == NULL)
 		fatal("no kex alg");
-	if (strcmp(k->name, KEX_DH1) != 0)
+	if (strcmp(k->name, KEX_DH1) == 0) {
+		k->kex_type = DH_GRP1_SHA1;
+	} else if (strcmp(k->name, KEX_DHGEX) == 0) {
+		k->kex_type = DH_GEX_SHA1;
+	} else
 		fatal("bad kex alg %s", k->name);
 }
 void
diff --git a/usr.bin/ssh/kex.h b/usr.bin/ssh/kex.h
index 8c89687b606..36af701e495 100644
--- a/usr.bin/ssh/kex.h
+++ b/usr.bin/ssh/kex.h
@@ -24,8 +24,9 @@
 #ifndef KEX_H
 #define KEX_H
 
-#define	KEX_DH1	"diffie-hellman-group1-sha1"
-#define KEX_DSS	"ssh-dss"
+#define	KEX_DH1		"diffie-hellman-group1-sha1"
+#define	KEX_DHGEX	"diffie-hellman-group-exchange-sha1"
+#define	KEX_DSS		"ssh-dss"
 
 enum kex_init_proposals {
 	PROPOSAL_KEX_ALGS,
@@ -47,6 +48,11 @@ enum kex_modes {
 	MODE_MAX
 };
 
+enum kex_exchange {
+	DH_GRP1_SHA1,
+	DH_GEX_SHA1
+};
+		
 typedef struct Kex Kex;
 typedef struct Mac Mac;
 typedef struct Comp Comp;
@@ -83,6 +89,7 @@ struct Kex {
 	int		server;
 	char		*name;
 	char		*hostkeyalg;
+	int		kex_type;
 };
 
 Buffer	*kex_init(char *myproposal[PROPOSAL_MAX]);
@@ -96,6 +103,8 @@ kex_choose_conf(char *cprop[PROPOSAL_MAX],
 int	kex_derive_keys(Kex *k, unsigned char *hash, BIGNUM *shared_secret);
 void	packet_set_kex(Kex *k);
 int	dh_pub_is_valid(DH *dh, BIGNUM *dh_pub);
+DH	*dh_new_group_asc(const char *, const char *);
+DH	*dh_new_group(BIGNUM *, BIGNUM *);
 DH	*dh_new_group1();
 
 unsigned char *
@@ -109,4 +118,15 @@ kex_hash(
     BIGNUM *server_dh_pub,
     BIGNUM *shared_secret);
 
+unsigned char *
+kex_hash_gex(
+    char *client_version_string,
+    char *server_version_string,
+    char *ckexinit, int ckexinitlen,
+    char *skexinit, int skexinitlen,
+    char *serverhostkeyblob, int sbloblen,
+    int minbits, BIGNUM *prime, BIGNUM *gen,
+    BIGNUM *client_dh_pub,
+    BIGNUM *server_dh_pub,
+    BIGNUM *shared_secret);
 #endif
diff --git a/usr.bin/ssh/myproposal.h b/usr.bin/ssh/myproposal.h
index 18db954c588..1d368239604 100644
--- a/usr.bin/ssh/myproposal.h
+++ b/usr.bin/ssh/myproposal.h
@@ -21,7 +21,7 @@
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
-#define KEX_DEFAULT_KEX		"diffie-hellman-group1-sha1"
+#define KEX_DEFAULT_KEX		"diffie-hellman-group-exchange-sha1,diffie-hellman-group1-sha1"
 #define	KEX_DEFAULT_PK_ALG	"ssh-dss"
 #define	KEX_DEFAULT_ENCRYPT	"3des-cbc,blowfish-cbc,arcfour,cast128-cbc"
 #define	KEX_DEFAULT_MAC		"hmac-sha1,hmac-md5,hmac-ripemd160@openssh.com"
diff --git a/usr.bin/ssh/ssh.h b/usr.bin/ssh/ssh.h
index 0200307690e..3092d220e58 100644
--- a/usr.bin/ssh/ssh.h
+++ b/usr.bin/ssh/ssh.h
@@ -12,7 +12,7 @@
  * called by a name other than "ssh" or "Secure Shell".
  */
 
-/* RCSID("$OpenBSD: ssh.h,v 1.51 2000/09/12 20:53:10 markus Exp $"); */
+/* RCSID("$OpenBSD: ssh.h,v 1.52 2000/10/11 04:02:17 provos Exp $"); */
 
 #ifndef SSH_H
 #define SSH_H
@@ -81,6 +81,7 @@
 #define SERVER_CONFIG_FILE	ETCDIR "/sshd_config"
 #define HOST_CONFIG_FILE	ETCDIR "/ssh_config"
 #define HOST_DSA_KEY_FILE	ETCDIR "/ssh_host_dsa_key"
+#define DH_PRIMES		ETCDIR "/primes"
 
 #define SSH_PROGRAM		"/usr/bin/ssh"
 
diff --git a/usr.bin/ssh/ssh2.h b/usr.bin/ssh/ssh2.h
index 47628ddd4ba..fe0146cbdb9 100644
--- a/usr.bin/ssh/ssh2.h
+++ b/usr.bin/ssh/ssh2.h
@@ -52,7 +52,7 @@
  *
  *     192-255  Local extensions
  */
-/* RCSID("$OpenBSD: ssh2.h,v 1.4 2000/09/07 20:27:54 deraadt Exp $"); */
+/* RCSID("$OpenBSD: ssh2.h,v 1.5 2000/10/11 04:02:17 provos Exp $"); */
 
 /* transport layer: generic */
 
@@ -73,6 +73,12 @@
 #define SSH2_MSG_KEXDH_INIT				30
 #define SSH2_MSG_KEXDH_REPLY				31
 
+/* dh-group-exchange */
+#define SSH2_MSG_KEX_DH_GEX_REQUEST			30
+#define SSH2_MSG_KEX_DH_GEX_GROUP			31
+#define SSH2_MSG_KEX_DH_GEX_INIT			32
+#define SSH2_MSG_KEX_DH_GEX_REPLY			33
+
 /* user authentication: generic */
 
 #define SSH2_MSG_USERAUTH_REQUEST			50
diff --git a/usr.bin/ssh/sshconnect2.c b/usr.bin/ssh/sshconnect2.c
index eee09a19ca8..455850eebc6 100644
--- a/usr.bin/ssh/sshconnect2.c
+++ b/usr.bin/ssh/sshconnect2.c
@@ -23,7 +23,7 @@
  */
 
 #include "includes.h"
-RCSID("$OpenBSD: sshconnect2.c,v 1.21 2000/09/27 21:41:34 markus Exp $");
+RCSID("$OpenBSD: sshconnect2.c,v 1.22 2000/10/11 04:02:17 provos Exp $");
 
 #include <openssl/bn.h>
 #include <openssl/rsa.h>
@@ -52,6 +52,9 @@ RCSID("$OpenBSD: sshconnect2.c,v 1.21 2000/09/27 21:41:34 markus Exp $");
 #include "dispatch.h"
 #include "authfd.h"
 
+void ssh_dh1_client(Kex *, char *, struct sockaddr *, Buffer *, Buffer *);
+void ssh_dhgex_client(Kex *, char *, struct sockaddr *, Buffer *, Buffer *);
+
 /* import */
 extern char *client_version_string;
 extern char *server_version_string;
@@ -65,8 +68,89 @@ unsigned char *session_id2 = NULL;
 int session_id2_len = 0;
 
 void
-ssh_kex_dh(Kex *kex, char *host, struct sockaddr *hostaddr,
-    Buffer *client_kexinit, Buffer *server_kexinit)
+ssh_kex2(char *host, struct sockaddr *hostaddr)
+{
+	int i, plen;
+	Kex *kex;
+	Buffer *client_kexinit, *server_kexinit;
+	char *sprop[PROPOSAL_MAX];
+
+	if (options.ciphers != NULL) {
+		myproposal[PROPOSAL_ENC_ALGS_CTOS] =
+		myproposal[PROPOSAL_ENC_ALGS_STOC] = options.ciphers;
+	} else if (options.cipher == SSH_CIPHER_3DES) {
+		myproposal[PROPOSAL_ENC_ALGS_CTOS] =
+		myproposal[PROPOSAL_ENC_ALGS_STOC] =
+		    (char *) cipher_name(SSH_CIPHER_3DES_CBC);
+	} else if (options.cipher == SSH_CIPHER_BLOWFISH) {
+		myproposal[PROPOSAL_ENC_ALGS_CTOS] =
+		myproposal[PROPOSAL_ENC_ALGS_STOC] =
+		    (char *) cipher_name(SSH_CIPHER_BLOWFISH_CBC);
+	}
+	if (options.compression) {
+		myproposal[PROPOSAL_COMP_ALGS_CTOS] = "zlib";
+		myproposal[PROPOSAL_COMP_ALGS_STOC] = "zlib";
+	} else {
+		myproposal[PROPOSAL_COMP_ALGS_CTOS] = "none";
+		myproposal[PROPOSAL_COMP_ALGS_STOC] = "none";
+	}
+
+	/* buffers with raw kexinit messages */
+	server_kexinit = xmalloc(sizeof(*server_kexinit));
+	buffer_init(server_kexinit);
+	client_kexinit = kex_init(myproposal);
+
+	/* algorithm negotiation */
+	kex_exchange_kexinit(client_kexinit, server_kexinit, sprop);
+	kex = kex_choose_conf(myproposal, sprop, 0);
+	for (i = 0; i < PROPOSAL_MAX; i++)
+		xfree(sprop[i]);
+
+	/* server authentication and session key agreement */
+	switch(kex->kex_type) {
+	case DH_GRP1_SHA1:
+		ssh_dh1_client(kex, host, hostaddr,
+			       client_kexinit, server_kexinit);
+		break;
+	case DH_GEX_SHA1:
+		ssh_dhgex_client(kex, host, hostaddr, client_kexinit,
+				 server_kexinit);
+		break;
+	default:
+		fatal("Unsupported key exchange %d", kex->kex_type);
+	}
+
+	buffer_free(client_kexinit);
+	buffer_free(server_kexinit);
+	xfree(client_kexinit);
+	xfree(server_kexinit);
+
+	debug("Wait SSH2_MSG_NEWKEYS.");
+	packet_read_expect(&plen, SSH2_MSG_NEWKEYS);
+	packet_done();
+	debug("GOT SSH2_MSG_NEWKEYS.");
+
+	debug("send SSH2_MSG_NEWKEYS.");
+	packet_start(SSH2_MSG_NEWKEYS);
+	packet_send();
+	packet_write_wait();
+	debug("done: send SSH2_MSG_NEWKEYS.");
+
+#ifdef DEBUG_KEXDH
+	/* send 1st encrypted/maced/compressed message */
+	packet_start(SSH2_MSG_IGNORE);
+	packet_put_cstring("markus");
+	packet_send();
+	packet_write_wait();
+#endif
+	debug("done: KEX2.");
+}
+
+/* diffie-hellman-group1-sha1 */
+
+void
+ssh_dh1_client(Kex *kex, char *host, struct sockaddr *hostaddr, 
+	       Buffer *client_kexinit, Buffer *server_kexinit)
 {
 #ifdef DEBUG_KEXDH
 	int i;
@@ -116,7 +200,7 @@ ssh_kex_dh(Kex *kex, char *host, struct sockaddr *hostaddr,
 		fatal("cannot decode server_host_key_blob");
 
 	check_host_key(host, hostaddr, server_host_key,
-	    options.user_hostfile2, options.system_hostfile2);
+		       options.user_hostfile2, options.system_hostfile2);
 
 	/* DH paramter f, server public DH key */
 	dh_server_pub = BN_new();
@@ -186,72 +270,175 @@ ssh_kex_dh(Kex *kex, char *host, struct sockaddr *hostaddr,
 	memcpy(session_id2, hash, session_id2_len);
 }
 
+/* diffie-hellman-group-exchange-sha1 */
+
+/*
+ * Estimates the group order for a Diffie-Hellman group that has an
+ * attack complexity approximately the same as O(2**bits).  Estimate
+ * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
+ */
+
+int
+dh_estimate(int bits)
+{
+	
+	if (bits < 64)
+		return (512);	/* O(2**63) */
+	if (bits < 128)
+		return (1024);	/* O(2**86) */
+	if (bits < 192)
+		return (2048);	/* O(2**116) */
+	return (4096);		/* O(2**156) */
+}
+
 void
-ssh_kex2(char *host, struct sockaddr *hostaddr)
+ssh_dhgex_client(Kex *kex, char *host, struct sockaddr *hostaddr,
+		 Buffer *client_kexinit, Buffer *server_kexinit)
 {
-	int i, plen;
-	Kex *kex;
-	Buffer *client_kexinit, *server_kexinit;
-	char *sprop[PROPOSAL_MAX];
+#ifdef DEBUG_KEXDH
+	int i;
+#endif
+	int plen, dlen;
+	unsigned int klen, kout;
+	char *signature = NULL;
+	unsigned int slen, nbits;
+	char *server_host_key_blob = NULL;
+	Key *server_host_key;
+	unsigned int sbloblen;
+	DH *dh;
+	BIGNUM *dh_server_pub = 0;
+	BIGNUM *shared_secret = 0;
+	BIGNUM *p = 0, *g = 0;
+	unsigned char *kbuf;
+	unsigned char *hash;
 
-	if (options.ciphers != NULL) {
-		myproposal[PROPOSAL_ENC_ALGS_CTOS] =
-		myproposal[PROPOSAL_ENC_ALGS_STOC] = options.ciphers;
-	} else if (options.cipher == SSH_CIPHER_3DES) {
-		myproposal[PROPOSAL_ENC_ALGS_CTOS] =
-		myproposal[PROPOSAL_ENC_ALGS_STOC] =
-		    (char *) cipher_name(SSH_CIPHER_3DES_CBC);
-	} else if (options.cipher == SSH_CIPHER_BLOWFISH) {
-		myproposal[PROPOSAL_ENC_ALGS_CTOS] =
-		myproposal[PROPOSAL_ENC_ALGS_STOC] =
-		    (char *) cipher_name(SSH_CIPHER_BLOWFISH_CBC);
-	}
-	if (options.compression) {
-		myproposal[PROPOSAL_COMP_ALGS_CTOS] = "zlib";
-		myproposal[PROPOSAL_COMP_ALGS_STOC] = "zlib";
-	} else {
-		myproposal[PROPOSAL_COMP_ALGS_CTOS] = "none";
-		myproposal[PROPOSAL_COMP_ALGS_STOC] = "none";
-	}
+	nbits = dh_estimate(kex->enc[MODE_OUT].key_len * 8);
 
-	/* buffers with raw kexinit messages */
-	server_kexinit = xmalloc(sizeof(*server_kexinit));
-	buffer_init(server_kexinit);
-	client_kexinit = kex_init(myproposal);
+	debug("Sending SSH2_MSG_KEX_DH_GEX_REQUEST.");
+	packet_start(SSH2_MSG_KEX_DH_GEX_REQUEST);
+	packet_put_int(nbits);
+	packet_send();
+	packet_write_wait();
 
-	/* algorithm negotiation */
-	kex_exchange_kexinit(client_kexinit, server_kexinit, sprop);
-	kex = kex_choose_conf(myproposal, sprop, 0);
-	for (i = 0; i < PROPOSAL_MAX; i++)
-		xfree(sprop[i]);
+#ifdef DEBUG_KEXDH
+	fprintf(stderr, "\nnbits = %d", nbits);
+#endif
 
-	/* server authentication and session key agreement */
-	ssh_kex_dh(kex, host, hostaddr, client_kexinit, server_kexinit);
+	debug("Wait SSH2_MSG_KEX_DH_GEX_GROUP.");
 
-	buffer_free(client_kexinit);
-	buffer_free(server_kexinit);
-	xfree(client_kexinit);
-	xfree(server_kexinit);
+	packet_read_expect(&plen, SSH2_MSG_KEX_DH_GEX_GROUP);
 
-	debug("Wait SSH2_MSG_NEWKEYS.");
-	packet_read_expect(&plen, SSH2_MSG_NEWKEYS);
-	packet_done();
-	debug("GOT SSH2_MSG_NEWKEYS.");
+	debug("Got SSH2_MSG_KEX_DH_GEX_GROUP.");
 
-	debug("send SSH2_MSG_NEWKEYS.");
-	packet_start(SSH2_MSG_NEWKEYS);
-	packet_send();
-	packet_write_wait();
-	debug("done: send SSH2_MSG_NEWKEYS.");
+	if ((p = BN_new()) == NULL)
+		fatal("BN_new");
+	packet_get_bignum2(p, &dlen);
+	if ((g = BN_new()) == NULL)
+		fatal("BN_new");
+	packet_get_bignum2(g, &dlen);
+	if ((dh = dh_new_group(g, p)) == NULL)
+		fatal("dh_new_group");
 
 #ifdef DEBUG_KEXDH
-	/* send 1st encrypted/maced/compressed message */
-	packet_start(SSH2_MSG_IGNORE);
-	packet_put_cstring("markus");
+	fprintf(stderr, "\np= ");
+	BN_print_fp(stderr, dh->p);
+	fprintf(stderr, "\ng= ");
+	BN_print_fp(stderr, dh->g);
+	fprintf(stderr, "\npub= ");
+	BN_print_fp(stderr, dh->pub_key);
+	fprintf(stderr, "\n");
+	DHparams_print_fp(stderr, dh);
+#endif
+
+	debug("Sending SSH2_MSG_KEX_DH_GEX_INIT.");
+	/* generate and send 'e', client DH public key */
+	packet_start(SSH2_MSG_KEX_DH_GEX_INIT);
+	packet_put_bignum2(dh->pub_key);
 	packet_send();
 	packet_write_wait();
+
+	debug("Wait SSH2_MSG_KEX_DH_GEX_REPLY.");
+
+	packet_read_expect(&plen, SSH2_MSG_KEX_DH_GEX_REPLY);
+
+	debug("Got SSH2_MSG_KEXDH_REPLY.");
+
+	/* key, cert */
+	server_host_key_blob = packet_get_string(&sbloblen);
+	server_host_key = dsa_key_from_blob(server_host_key_blob, sbloblen);
+	if (server_host_key == NULL)
+		fatal("cannot decode server_host_key_blob");
+
+	check_host_key(host, hostaddr, server_host_key,
+		       options.user_hostfile2, options.system_hostfile2);
+
+	/* DH paramter f, server public DH key */
+	dh_server_pub = BN_new();
+	if (dh_server_pub == NULL)
+		fatal("dh_server_pub == NULL");
+	packet_get_bignum2(dh_server_pub, &dlen);
+
+#ifdef DEBUG_KEXDH
+	fprintf(stderr, "\ndh_server_pub= ");
+	BN_print_fp(stderr, dh_server_pub);
+	fprintf(stderr, "\n");
+	debug("bits %d", BN_num_bits(dh_server_pub));
 #endif
-	debug("done: KEX2.");
+
+	/* signed H */
+	signature = packet_get_string(&slen);
+	packet_done();
+
+	if (!dh_pub_is_valid(dh, dh_server_pub))
+		packet_disconnect("bad server public DH value");
+
+	klen = DH_size(dh);
+	kbuf = xmalloc(klen);
+	kout = DH_compute_key(kbuf, dh_server_pub, dh);
+#ifdef DEBUG_KEXDH
+	debug("shared secret: len %d/%d", klen, kout);
+	fprintf(stderr, "shared secret == ");
+	for (i = 0; i< kout; i++)
+		fprintf(stderr, "%02x", (kbuf[i])&0xff);
+	fprintf(stderr, "\n");
+#endif
+	shared_secret = BN_new();
+
+	BN_bin2bn(kbuf, kout, shared_secret);
+	memset(kbuf, 0, klen);
+	xfree(kbuf);
+
+	/* calc and verify H */
+	hash = kex_hash_gex(
+	    client_version_string,
+	    server_version_string,
+	    buffer_ptr(client_kexinit), buffer_len(client_kexinit),
+	    buffer_ptr(server_kexinit), buffer_len(server_kexinit),
+	    server_host_key_blob, sbloblen,
+	    nbits, dh->p, dh->g, 
+	    dh->pub_key,
+	    dh_server_pub,
+	    shared_secret
+	);
+	xfree(server_host_key_blob);
+	DH_free(dh);
+#ifdef DEBUG_KEXDH
+	fprintf(stderr, "hash == ");
+	for (i = 0; i< 20; i++)
+		fprintf(stderr, "%02x", (hash[i])&0xff);
+	fprintf(stderr, "\n");
+#endif
+	if (dsa_verify(server_host_key, (unsigned char *)signature, slen, hash, 20) != 1)
+		fatal("dsa_verify failed for server_host_key");
+	key_free(server_host_key);
+
+	kex_derive_keys(kex, hash, shared_secret);
+	packet_set_kex(kex);
+
+	/* save session id */
+	session_id2_len = 20;
+	session_id2 = xmalloc(session_id2_len);
+	memcpy(session_id2, hash, session_id2_len);
 }
 
 /*
diff --git a/usr.bin/ssh/sshd.c b/usr.bin/ssh/sshd.c
index b6a3556e180..3426b68ced7 100644
--- a/usr.bin/ssh/sshd.c
+++ b/usr.bin/ssh/sshd.c
@@ -40,7 +40,7 @@
  */
 
 #include "includes.h"
-RCSID("$OpenBSD: sshd.c,v 1.128 2000/09/17 15:38:59 markus Exp $");
+RCSID("$OpenBSD: sshd.c,v 1.129 2000/10/11 04:02:17 provos Exp $");
 
 #include "xmalloc.h"
 #include "rsa.h"
@@ -63,6 +63,7 @@ RCSID("$OpenBSD: sshd.c,v 1.128 2000/09/17 15:38:59 markus Exp $");
 #include <openssl/rsa.h>
 #include "key.h"
 #include "dsa.h"
+#include "dh.h"
 
 #include "auth.h"
 #include "myproposal.h"
@@ -167,6 +168,9 @@ unsigned int utmp_len = MAXHOSTNAMELEN;
 void do_ssh1_kex();
 void do_ssh2_kex();
 
+void ssh_dh1_server(Kex *, Buffer *_kexinit, Buffer *);
+void ssh_dhgex_server(Kex *, Buffer *_kexinit, Buffer *);
+
 /*
  * Close all listening sockets
  */
@@ -1277,18 +1281,8 @@ do_ssh2_kex()
 {
 	Buffer *server_kexinit;
 	Buffer *client_kexinit;
-	int payload_len, dlen;
-	int slen;
-	unsigned int klen, kout;
-	unsigned char *signature = NULL;
-	unsigned char *server_host_key_blob = NULL;
-	unsigned int sbloblen;
-	DH *dh;
-	BIGNUM *dh_client_pub = 0;
-	BIGNUM *shared_secret = 0;
+	int payload_len;
 	int i;
-	unsigned char *kbuf;
-	unsigned char *hash;
 	Kex *kex;
 	char *cprop[PROPOSAL_MAX];
 
@@ -1308,8 +1302,60 @@ do_ssh2_kex()
 	for (i = 0; i < PROPOSAL_MAX; i++)
 		xfree(cprop[i]);
 
-/* KEXDH */
+	switch (kex->kex_type) {
+	case DH_GRP1_SHA1:
+		ssh_dh1_server(kex, client_kexinit, server_kexinit);
+		break;
+	case DH_GEX_SHA1:
+		ssh_dhgex_server(kex, client_kexinit, server_kexinit);
+		break;
+	default:
+		fatal("Unsupported key exchange %d", kex->kex_type);
+	}
+
+	debug("send SSH2_MSG_NEWKEYS.");
+	packet_start(SSH2_MSG_NEWKEYS);
+	packet_send();
+	packet_write_wait();
+	debug("done: send SSH2_MSG_NEWKEYS.");
+
+	debug("Wait SSH2_MSG_NEWKEYS.");
+	packet_read_expect(&payload_len, SSH2_MSG_NEWKEYS);
+	debug("GOT SSH2_MSG_NEWKEYS.");
+
+#ifdef DEBUG_KEXDH
+	/* send 1st encrypted/maced/compressed message */
+	packet_start(SSH2_MSG_IGNORE);
+	packet_put_cstring("markus");
+	packet_send();
+	packet_write_wait();
+#endif
+
+	debug("done: KEX2.");
+}
 
+/*
+ * SSH2 key exchange
+ */
+
+/* diffie-hellman-group1-sha1 */
+
+void
+ssh_dh1_server(Kex *kex, Buffer *client_kexinit, Buffer *server_kexinit)
+{
+	int payload_len, dlen;
+	int slen;
+	unsigned char *signature = NULL;
+	unsigned char *server_host_key_blob = NULL;
+	unsigned int sbloblen;
+	unsigned int klen, kout;
+	unsigned char *kbuf;
+	unsigned char *hash;
+	BIGNUM *shared_secret = 0;
+	DH *dh;
+	BIGNUM *dh_client_pub = 0;
+
+/* KEXDH */
 	debug("Wait SSH2_MSG_KEXDH_INIT.");
 	packet_read_expect(&payload_len, SSH2_MSG_KEXDH_INIT);
 
@@ -1360,7 +1406,8 @@ do_ssh2_kex()
 	xfree(kbuf);
 
 	/* XXX precompute? */
-	dsa_make_key_blob(sensitive_data.dsa_host_key, &server_host_key_blob, &sbloblen);
+	dsa_make_key_blob(sensitive_data.dsa_host_key,
+			  &server_host_key_blob, &sbloblen);
 
 	/* calc H */			/* XXX depends on 'kex' */
 	hash = kex_hash(
@@ -1410,23 +1457,136 @@ do_ssh2_kex()
 
 	/* have keys, free DH */
 	DH_free(dh);
+}
 
-	debug("send SSH2_MSG_NEWKEYS.");
-	packet_start(SSH2_MSG_NEWKEYS);
+/* diffie-hellman-group-exchange-sha1 */
+
+void
+ssh_dhgex_server(Kex *kex, Buffer *client_kexinit, Buffer *server_kexinit)
+{
+	int payload_len, dlen;
+	int slen, nbits;
+	unsigned char *signature = NULL;
+	unsigned char *server_host_key_blob = NULL;
+	unsigned int sbloblen;
+	unsigned int klen, kout;
+	unsigned char *kbuf;
+	unsigned char *hash;
+	BIGNUM *shared_secret = 0;
+	DH *dh;
+	BIGNUM *dh_client_pub = 0;
+
+/* KEXDHGEX */
+	debug("Wait SSH2_MSG_KEX_DH_GEX_REQUEST.");
+	packet_read_expect(&payload_len, SSH2_MSG_KEX_DH_GEX_REQUEST);
+	nbits = packet_get_int();
+	dh = choose_dh(nbits);
+
+	debug("Sending SSH2_MSG_KEX_DH_GEX_GROUP.");
+	packet_start(SSH2_MSG_KEX_DH_GEX_GROUP);
+	packet_put_bignum2(dh->p);
+	packet_put_bignum2(dh->g);
 	packet_send();
 	packet_write_wait();
-	debug("done: send SSH2_MSG_NEWKEYS.");
 
-	debug("Wait SSH2_MSG_NEWKEYS.");
-	packet_read_expect(&payload_len, SSH2_MSG_NEWKEYS);
-	debug("GOT SSH2_MSG_NEWKEYS.");
+	debug("Wait SSH2_MSG_KEX_DH_GEX_INIT.");
+	packet_read_expect(&payload_len, SSH2_MSG_KEX_DH_GEX_INIT);
+
+	/* key, cert */
+	dh_client_pub = BN_new();
+	if (dh_client_pub == NULL)
+		fatal("dh_client_pub == NULL");
+	packet_get_bignum2(dh_client_pub, &dlen);
 
 #ifdef DEBUG_KEXDH
-	/* send 1st encrypted/maced/compressed message */
-	packet_start(SSH2_MSG_IGNORE);
-	packet_put_cstring("markus");
+	fprintf(stderr, "\ndh_client_pub= ");
+	BN_print_fp(stderr, dh_client_pub);
+	fprintf(stderr, "\n");
+	debug("bits %d", BN_num_bits(dh_client_pub));
+#endif
+
+#ifdef DEBUG_KEXDH
+	fprintf(stderr, "\np= ");
+	BN_print_fp(stderr, dh->p);
+	fprintf(stderr, "\ng= ");
+	bn_print(dh->g);
+	fprintf(stderr, "\npub= ");
+	BN_print_fp(stderr, dh->pub_key);
+	fprintf(stderr, "\n");
+        DHparams_print_fp(stderr, dh);
+#endif
+	if (!dh_pub_is_valid(dh, dh_client_pub))
+		packet_disconnect("bad client public DH value");
+
+	klen = DH_size(dh);
+	kbuf = xmalloc(klen);
+	kout = DH_compute_key(kbuf, dh_client_pub, dh);
+
+#ifdef DEBUG_KEXDH
+	debug("shared secret: len %d/%d", klen, kout);
+	fprintf(stderr, "shared secret == ");
+	for (i = 0; i< kout; i++)
+		fprintf(stderr, "%02x", (kbuf[i])&0xff);
+	fprintf(stderr, "\n");
+#endif
+	shared_secret = BN_new();
+
+	BN_bin2bn(kbuf, kout, shared_secret);
+	memset(kbuf, 0, klen);
+	xfree(kbuf);
+
+	/* XXX precompute? */
+	dsa_make_key_blob(sensitive_data.dsa_host_key,
+			  &server_host_key_blob, &sbloblen);
+
+	/* calc H */			/* XXX depends on 'kex' */
+	hash = kex_hash_gex(
+	    client_version_string,
+	    server_version_string,
+	    buffer_ptr(client_kexinit), buffer_len(client_kexinit),
+	    buffer_ptr(server_kexinit), buffer_len(server_kexinit),
+	    (char *)server_host_key_blob, sbloblen,
+	    nbits, dh->p, dh->g,
+	    dh_client_pub,
+	    dh->pub_key,
+	    shared_secret
+	);
+	buffer_free(client_kexinit);
+	buffer_free(server_kexinit);
+	xfree(client_kexinit);
+	xfree(server_kexinit);
+#ifdef DEBUG_KEXDH
+	fprintf(stderr, "hash == ");
+	for (i = 0; i< 20; i++)
+		fprintf(stderr, "%02x", (hash[i])&0xff);
+	fprintf(stderr, "\n");
+#endif
+	/* save session id := H */
+	/* XXX hashlen depends on KEX */
+	session_id2_len = 20;
+	session_id2 = xmalloc(session_id2_len);
+	memcpy(session_id2, hash, session_id2_len);
+
+	/* sign H */
+	/* XXX hashlen depends on KEX */
+	dsa_sign(sensitive_data.dsa_host_key, &signature, &slen, hash, 20);
+
+	destroy_sensitive_data();
+
+	/* send server hostkey, DH pubkey 'f' and singed H */
+	packet_start(SSH2_MSG_KEX_DH_GEX_REPLY);
+	packet_put_string((char *)server_host_key_blob, sbloblen);
+	packet_put_bignum2(dh->pub_key);	/* f */
+	packet_put_string((char *)signature, slen);
 	packet_send();
+	xfree(signature);
+	xfree(server_host_key_blob);
 	packet_write_wait();
-#endif
-	debug("done: KEX2.");
+
+	kex_derive_keys(kex, hash, shared_secret);
+	packet_set_kex(kex);
+
+	/* have keys, free DH */
+	DH_free(dh);
 }
+
diff --git a/usr.bin/ssh/sshd/Makefile b/usr.bin/ssh/sshd/Makefile
index 0adfcd6391f..4938d58744d 100644
--- a/usr.bin/ssh/sshd/Makefile
+++ b/usr.bin/ssh/sshd/Makefile
@@ -9,7 +9,7 @@ CFLAGS+=-DHAVE_LOGIN_CAP
 
 SRCS=	sshd.c auth-rhosts.c auth-passwd.c auth-rsa.c auth-rh-rsa.c \
 	pty.c log-server.c login.c servconf.c serverloop.c \
-	auth.c auth1.c auth2.c auth-options.c session.c
+	auth.c auth1.c auth2.c auth-options.c session.c dh.c
 
 .include <bsd.own.mk> # for KERBEROS and AFS