merge kexguess branch

15 files changed, 240 insertions, 256 deletions

diff --git a/Makefile.in b/Makefile.in
index 8e1ba52..4bdd845 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -28,12 +28,12 @@ COMMONOBJS=dbutil.o buffer.o \
 		queue.o \
 		atomicio.o compat.o  fake-rfc2553.o 
 
-SVROBJS=svr-kex.o svr-algo.o svr-auth.o sshpty.o \
+SVROBJS=svr-kex.o svr-auth.o sshpty.o \
 		svr-authpasswd.o svr-authpubkey.o svr-authpubkeyoptions.o svr-session.o svr-service.o \
 		svr-chansession.o svr-runopts.o svr-agentfwd.o svr-main.o svr-x11fwd.o\
 		svr-tcpfwd.o svr-authpam.o
 
-CLIOBJS=cli-algo.o cli-main.o cli-auth.o cli-authpasswd.o cli-kex.o \
+CLIOBJS=cli-main.o cli-auth.o cli-authpasswd.o cli-kex.o \
 		cli-session.o cli-runopts.o cli-chansession.o \
 		cli-authpubkey.o cli-tcpfwd.o cli-channel.o cli-authinteract.o \
 		cli-agentfwd.o list.o
diff --git a/algo.h b/algo.h
index ad57037..ad40c0d 100644
--- a/algo.h
+++ b/algo.h
@@ -83,10 +83,18 @@ void crypto_init();
 int have_algo(char* algo, size_t algolen, algo_type algos[]);
 void buf_put_algolist(buffer * buf, algo_type localalgos[]);
 
-algo_type * svr_buf_match_algo(buffer* buf, algo_type localalgos[],
-		int *goodguess);
-algo_type * cli_buf_match_algo(buffer* buf, algo_type localalgos[],
-		int *goodguess);
+enum kexguess2_used {
+	KEXGUESS2_LOOK,
+	KEXGUESS2_NO,
+	KEXGUESS2_YES,
+};
+
+#define KEXGUESS2_ALGO_NAME "kexguess2@matt.ucc.asn.au"
+#define KEXGUESS2_ALGO_ID 99
+
+
+algo_type * buf_match_algo(buffer* buf, algo_type localalgos[],
+		enum kexguess2_used *kexguess2, int *goodguess);
 
 #ifdef ENABLE_USER_ALGO_LIST
 int check_user_algos(const char* user_algo_list, algo_type * algos, 
diff --git a/bignum.h b/bignum.h
index 042f811..cabb4a2 100644
--- a/bignum.h
+++ b/bignum.h
@@ -28,7 +28,7 @@
 #include "includes.h"
 
 void m_mp_init(mp_int *mp);
-void m_mp_init_multi(mp_int *mp, ...);
+void m_mp_init_multi(mp_int *mp, ...) ATTRIB_SENTINEL;
 void bytes_to_mp(mp_int *mp, const unsigned char* bytes, unsigned int len);
 void sha1_process_mp(hash_state *hs, mp_int *mp);
 
diff --git a/cli-algo.c b/cli-algo.c
deleted file mode 100644
index 09da41a..0000000
--- a/cli-algo.c
+++ /dev/null
@@ -1,99 +0,0 @@
-/*
- * Dropbear - a SSH2 server
- * SSH client implementation
- * 
- * Copyright (c) 2002,2003 Matt Johnston
- * Copyright (c) 2004 by Mihnea Stoenescu
- * All rights reserved.
- * 
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to deal
- * in the Software without restriction, including without limitation the rights
- * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- * copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- * 
- * The above copyright notice and this permission notice shall be included in
- * all copies or substantial portions of the Software.
- * 
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE. */
-
-#include "algo.h"
-#include "dbutil.h"
-
-
-/*
- * The chosen [encryption | MAC | compression] algorithm to each 
- * direction MUST be the first algorithm  on the client's list
- * that is also on the server's list.
- */
-algo_type * cli_buf_match_algo(buffer* buf, algo_type localalgos[],
-		int *goodguess) {
-
-	unsigned char * algolist = NULL;
-	unsigned char * remotealgos[MAX_PROPOSED_ALGO];
-	unsigned int len;
-	unsigned int count, i, j;
-	algo_type * ret = NULL;
-
-	*goodguess = 0;
-
-	/* get the comma-separated list from the buffer ie "algo1,algo2,algo3" */
-	algolist = buf_getstring(buf, &len);
-	TRACE(("cli_buf_match_algo: %s", algolist))
-	if (len > MAX_PROPOSED_ALGO*(MAX_NAME_LEN+1)) {
-		goto out; /* just a sanity check, no other use */
-	}
-
-	/* remotealgos will contain a list of the strings parsed out */
-	/* We will have at least one string (even if it's just "") */
-	remotealgos[0] = algolist;
-	count = 1;
-	/* Iterate through, replacing ','s with NULs, to split it into
-	 * words. */
-	for (i = 0; i < len; i++) {
-		if (algolist[i] == '\0') {
-			/* someone is trying something strange */
-			goto out;
-		}
-		if (algolist[i] == ',') {
-			algolist[i] = '\0';
-			remotealgos[count] = &algolist[i+1];
-			count++;
-		}
-		if (count >= MAX_PROPOSED_ALGO) {
-			break;
-		}
-	}
-
-	/* iterate and find the first match */
-
-	for (j = 0; localalgos[j].name != NULL; j++) {
-		if (localalgos[j].usable) {
-		len = strlen(localalgos[j].name);
-			for (i = 0; i < count; i++) {
-				if (len == strlen(remotealgos[i]) 
-						&& strncmp(localalgos[j].name, 
-							remotealgos[i], len) == 0) {
-					if (i == 0 && j == 0) {
-						/* was a good guess */
-						*goodguess = 1;
-					}
-					ret = &localalgos[j];
-					goto out;
-				}
-			}
-		}
-	}
-
-out:
-	m_free(algolist);
-	return ret;
-}
-
diff --git a/cli-kex.c b/cli-kex.c
index e039071..1158aa6 100644
--- a/cli-kex.c
+++ b/cli-kex.c
@@ -42,18 +42,27 @@ static void checkhostkey(unsigned char* keyblob, unsigned int keybloblen);
 #define MAX_KNOWNHOSTS_LINE 4500
 
 void send_msg_kexdh_init() {
+	TRACE(("send_msg_kexdh_init()"))	
+	if ((cli_ses.dh_e && cli_ses.dh_x 
+				&& cli_ses.dh_val_algo == ses.newkeys->algo_kex)) {
+		TRACE(("reusing existing dh_e from first_kex_packet_follows"))
+	} else {
+		if (!cli_ses.dh_e || !cli_ses.dh_e) {
+			cli_ses.dh_e = (mp_int*)m_malloc(sizeof(mp_int));
+			cli_ses.dh_x = (mp_int*)m_malloc(sizeof(mp_int));
+			m_mp_init_multi(cli_ses.dh_e, cli_ses.dh_x, NULL);
+		}
 
-	cli_ses.dh_e = (mp_int*)m_malloc(sizeof(mp_int));
-	cli_ses.dh_x = (mp_int*)m_malloc(sizeof(mp_int));
-	m_mp_init_multi(cli_ses.dh_e, cli_ses.dh_x, NULL);
-
-	gen_kexdh_vals(cli_ses.dh_e, cli_ses.dh_x);
+		gen_kexdh_vals(cli_ses.dh_e, cli_ses.dh_x);
+		cli_ses.dh_val_algo = ses.newkeys->algo_kex;
+	}
 
 	CHECKCLEARTOWRITE();
 	buf_putbyte(ses.writepayload, SSH_MSG_KEXDH_INIT);
 	buf_putmpint(ses.writepayload, cli_ses.dh_e);
 	encrypt_packet();
-	ses.requirenext = SSH_MSG_KEXDH_REPLY;
+	// XXX fixme
+	//ses.requirenext = SSH_MSG_KEXDH_REPLY;
 }
 
 /* Handle a diffie-hellman key exchange reply. */
@@ -98,6 +107,7 @@ void recv_msg_kexdh_reply() {
 	mp_clear_multi(cli_ses.dh_e, cli_ses.dh_x, NULL);
 	m_free(cli_ses.dh_e);
 	m_free(cli_ses.dh_x);
+	cli_ses.dh_val_algo = DROPBEAR_KEX_NONE;
 
 	if (buf_verify(ses.payload, hostkey, ses.hash, SHA1_HASH_SIZE) 
 			!= DROPBEAR_SUCCESS) {
diff --git a/cli-session.c b/cli-session.c
index b13948f..9d4bcde 100644
--- a/cli-session.c
+++ b/cli-session.c
@@ -111,6 +111,13 @@ void cli_session(int sock_in, int sock_out) {
 
 }
 
+#ifdef USE_KEX_FIRST_FOLLOWS
+static void cli_send_kex_first_guess() {
+	send_msg_kexdh_init();
+	dropbear_log(LOG_INFO, "kexdh_init guess sent");
+}
+#endif
+
 static void cli_session_init() {
 
 	cli_ses.state = STATE_NOTHING;
@@ -144,13 +151,18 @@ static void cli_session_init() {
 
 	/* For printing "remote host closed" for the user */
 	ses.remoteclosed = cli_remoteclosed;
+
 	ses.extra_session_cleanup = cli_session_cleanup;
-	ses.buf_match_algo = cli_buf_match_algo;
 
 	/* packet handlers */
 	ses.packettypes = cli_packettypes;
 
 	ses.isserver = 0;
+
+#ifdef USE_KEX_FIRST_FOLLOWS
+	ses.send_kex_first_guess = cli_send_kex_first_guess;
+#endif
+
 }
 
 static void send_msg_service_request(char* servicename) {
@@ -176,16 +188,19 @@ static void cli_sessionloop() {
 
 	TRACE2(("enter cli_sessionloop"))
 
-	if (ses.lastpacket == SSH_MSG_KEXINIT && cli_ses.kex_state == KEX_NOTHING) {
-		cli_ses.kex_state = KEXINIT_RCVD;
+	if (ses.lastpacket == 0) {
+		TRACE2(("exit cli_sessionloop: no real packets yet"))
+		return;
 	}
 
-	if (cli_ses.kex_state == KEXINIT_RCVD) {
-
+	if (ses.lastpacket == SSH_MSG_KEXINIT && cli_ses.kex_state == KEX_NOTHING) {
 		/* We initiate the KEXDH. If DH wasn't the correct type, the KEXINIT
 		 * negotiation would have failed. */
-		send_msg_kexdh_init();
-		cli_ses.kex_state = KEXDH_INIT_SENT;
+		if (!ses.kexstate.our_first_follows_matches) {
+			dropbear_log(LOG_INFO, "kexdh_init after remote's kexinit");
+			send_msg_kexdh_init();
+		}
+		cli_ses.kex_state = KEXDH_INIT_SENT;			
 		TRACE(("leave cli_sessionloop: done with KEXINIT_RCVD"))
 		return;
 	}
@@ -202,10 +217,9 @@ static void cli_sessionloop() {
 		return;
 	}
 
-	/* We should exit if we haven't donefirstkex: we shouldn't reach here
-	 * in normal operation */
 	if (ses.kexstate.donefirstkex == 0) {
-		TRACE(("XXX XXX might be bad! leave cli_sessionloop: haven't donefirstkex"))
+		/* We might reach here if we have partial packet reads or have
+		 * received SSG_MSG_IGNORE etc. Just skip it */
 		return;
 	}
 
diff --git a/common-algo.c b/common-algo.c
index 4a14651..14c157b 100644
--- a/common-algo.c
+++ b/common-algo.c
@@ -24,6 +24,7 @@
  * SOFTWARE. */
 
 #include "algo.h"
+#include "session.h"
 #include "dbutil.h"
 
 /* This file (algo.c) organises the ciphers which can be used, and is used to
@@ -215,6 +216,9 @@ algo_type sshhostkey[] = {
 algo_type sshkex[] = {
 	{"diffie-hellman-group1-sha1", DROPBEAR_KEX_DH_GROUP1, NULL, 1, NULL},
 	{"diffie-hellman-group14-sha1", DROPBEAR_KEX_DH_GROUP14, NULL, 1, NULL},
+#ifdef USE_KEXGUESS2
+	{KEXGUESS2_ALGO_NAME, KEXGUESS2_ALGO_ID, NULL, 1, NULL},
+#endif
 	{NULL, 0, NULL, 0, NULL}
 };
 
@@ -307,6 +311,122 @@ void buf_put_algolist(buffer * buf, algo_type localalgos[]) {
 	buf_free(algolist);
 }
 
+/* match the first algorithm in the comma-separated list in buf which is
+ * also in localalgos[], or return NULL on failure.
+ * (*goodguess) is set to 1 if the preferred client/server algos match,
+ * 0 otherwise. This is used for checking if the kexalgo/hostkeyalgos are
+ * guessed correctly */
+algo_type * buf_match_algo(buffer* buf, algo_type localalgos[],
+		enum kexguess2_used *kexguess2, int *goodguess)
+{
+
+	unsigned char * algolist = NULL;
+	const unsigned char *remotenames[MAX_PROPOSED_ALGO], *localnames[MAX_PROPOSED_ALGO];
+	unsigned int len;
+	unsigned int remotecount, localcount, clicount, servcount, i, j;
+	algo_type * ret = NULL;
+	const unsigned char **clinames, **servnames;
+
+	if (goodguess) {
+		*goodguess = 0;
+	}
+
+	/* get the comma-separated list from the buffer ie "algo1,algo2,algo3" */
+	algolist = buf_getstring(buf, &len);
+	TRACE(("buf_match_algo: %s", algolist))
+	if (len > MAX_PROPOSED_ALGO*(MAX_NAME_LEN+1)) {
+		goto out;
+	}
+
+	/* remotenames will contain a list of the strings parsed out */
+	/* We will have at least one string (even if it's just "") */
+	remotenames[0] = algolist;
+	remotecount = 1;
+	for (i = 0; i < len; i++) {
+		if (algolist[i] == '\0') {
+			/* someone is trying something strange */
+			goto out;
+		}
+		if (algolist[i] == ',') {
+			algolist[i] = '\0';
+			remotenames[remotecount] = &algolist[i+1];
+			remotecount++;
+		}
+		if (remotecount >= MAX_PROPOSED_ALGO) {
+			break;
+		}
+	}
+	if (kexguess2 && *kexguess2 == KEXGUESS2_LOOK) {
+		for (i = 0; i < remotecount; i++)
+		{
+			if (strcmp(remotenames[i], KEXGUESS2_ALGO_NAME) == 0) {
+				*kexguess2 = KEXGUESS2_YES;
+				break;
+			}
+		}
+		if (*kexguess2 == KEXGUESS2_LOOK) {
+			*kexguess2 = KEXGUESS2_NO;
+		}
+	}
+
+	for (i = 0; localalgos[i].name != NULL; i++) {
+		if (localalgos[i].usable) {
+			localnames[i] = localalgos[i].name;
+		} else {
+			localnames[i] = NULL;
+		}
+	}
+	localcount = i;
+
+	if (IS_DROPBEAR_SERVER) {
+		clinames = remotenames;
+		clicount = remotecount;
+		servnames = localnames;
+		servcount = localcount;
+	} else {
+		clinames = localnames;
+		clicount = localcount;
+		servnames = remotenames;
+		servcount = remotecount;
+	}
+
+	/* iterate and find the first match */
+	for (i = 0; i < clicount; i++) {
+		for (j = 0; j < servcount; j++) {
+			if (!(servnames[j] && clinames[i])) {
+				// unusable algos are NULL
+				continue;
+			}
+			if (strcmp(servnames[j], clinames[i]) == 0) {
+				/* set if it was a good guess */
+				if (goodguess && kexguess2) {
+					if (*kexguess2 == KEXGUESS2_YES) {
+						if (i == 0) {
+							*goodguess = 1;
+						}
+
+					} else {
+						if (i == 0 && j == 0) {
+							*goodguess = 1;
+						}
+					}
+				}
+				/* set the algo to return */
+				if (IS_DROPBEAR_SERVER) {
+					ret = &localalgos[j];
+				} else {
+					ret = &localalgos[i];
+				}
+				goto out;
+			}
+		}
+	}
+
+out:
+	m_free(algolist);
+	return ret;
+}
+
 #ifdef DROPBEAR_NONE_CIPHER
 
 void
diff --git a/common-kex.c b/common-kex.c
index 56b206d..6c22600 100644
--- a/common-kex.c
+++ b/common-kex.c
@@ -131,8 +131,8 @@ void send_msg_kexinit() {
 	/* languages_server_to_client */
 	buf_putstring(ses.writepayload, "", 0);
 
-	/* first_kex_packet_follows - unimplemented for now */
-	buf_putbyte(ses.writepayload, 0x00);
+	/* first_kex_packet_follows */
+	buf_putbyte(ses.writepayload, (ses.send_kex_first_guess != NULL));
 
 	/* reserved unit32 */
 	buf_putint(ses.writepayload, 0);
@@ -144,9 +144,19 @@ void send_msg_kexinit() {
 	encrypt_packet();
 	ses.dataallowed = 0; /* don't send other packets during kex */
 
+	ses.kexstate.sentkexinit = 1;
+
+	ses.newkeys = (struct key_context*)m_malloc(sizeof(struct key_context));
+
+	if (ses.send_kex_first_guess) {
+		ses.newkeys->algo_kex = sshkex[0].val;
+		ses.newkeys->algo_hostkey = sshhostkey[0].val;
+		ses.send_kex_first_guess();
+	}
+
 	TRACE(("DATAALLOWED=0"))
 	TRACE(("-> KEXINIT"))
-	ses.kexstate.sentkexinit = 1;
+
 }
 
 /* *** NOTE regarding (send|recv)_msg_newkeys *** 
@@ -236,11 +246,13 @@ static void kexinitialise() {
 	ses.kexstate.sentnewkeys = 0;
 
 	/* first_packet_follows */
-	ses.kexstate.firstfollows = 0;
+	ses.kexstate.them_firstfollows = 0;
 
 	ses.kexstate.datatrans = 0;
 	ses.kexstate.datarecv = 0;
 
+	ses.kexstate.our_first_follows_matches = 0;
+
 	ses.kexstate.lastkextime = time(NULL);
 
 }
@@ -555,7 +567,7 @@ void gen_kexdh_vals(mp_int *dh_pub, mp_int *dh_priv) {
 	DEF_MP_INT(dh_q);
 	DEF_MP_INT(dh_g);
 
-	TRACE(("enter send_msg_kexdh_reply"))
+	TRACE(("enter gen_kexdh_vals"))
 	
 	m_mp_init_multi(&dh_g, &dh_p, &dh_q, NULL);
 
@@ -678,20 +690,27 @@ static void read_kex_algos() {
 
 	buf_incrpos(ses.payload, 16); /* start after the cookie */
 
-	ses.newkeys = (struct key_context*)m_malloc(sizeof(struct key_context));
+	memset(ses.newkeys, 0x0, sizeof(*ses.newkeys));
+
+#ifdef USE_KEXGUESS2
+	enum kexguess2_used kexguess2 = KEXGUESS2_LOOK;
+#else
+	enum kexguess2_used kexguess2 = KEXGUESS2_NO;
+#endif
 
 	/* kex_algorithms */
-	algo = ses.buf_match_algo(ses.payload, sshkex, &goodguess);
+	algo = buf_match_algo(ses.payload, sshkex, &kexguess2, &goodguess);
 	allgood &= goodguess;
-	if (algo == NULL) {
+	if (algo == NULL || algo->val == KEXGUESS2_ALGO_ID) {
 		erralgo = "kex";
 		goto error;
 	}
+	TRACE(("kexguess2 %d", kexguess2))
 	TRACE(("kex algo %s", algo->name))
 	ses.newkeys->algo_kex = algo->val;
 
 	/* server_host_key_algorithms */
-	algo = ses.buf_match_algo(ses.payload, sshhostkey, &goodguess);
+	algo = buf_match_algo(ses.payload, sshhostkey, &kexguess2, &goodguess);
 	allgood &= goodguess;
 	if (algo == NULL) {
 		erralgo = "hostkey";
@@ -701,7 +720,7 @@ static void read_kex_algos() {
 	ses.newkeys->algo_hostkey = algo->val;
 
 	/* encryption_algorithms_client_to_server */
-	c2s_cipher_algo = ses.buf_match_algo(ses.payload, sshciphers, &goodguess);
+	c2s_cipher_algo = buf_match_algo(ses.payload, sshciphers, NULL, NULL);
 	if (c2s_cipher_algo == NULL) {
 		erralgo = "enc c->s";
 		goto error;
@@ -709,7 +728,7 @@ static void read_kex_algos() {
 	TRACE(("enc c2s is  %s", c2s_cipher_algo->name))
 
 	/* encryption_algorithms_server_to_client */
-	s2c_cipher_algo = ses.buf_match_algo(ses.payload, sshciphers, &goodguess);
+	s2c_cipher_algo = buf_match_algo(ses.payload, sshciphers, NULL, NULL);
 	if (s2c_cipher_algo == NULL) {
 		erralgo = "enc s->c";
 		goto error;
@@ -717,7 +736,7 @@ static void read_kex_algos() {
 	TRACE(("enc s2c is  %s", s2c_cipher_algo->name))
 
 	/* mac_algorithms_client_to_server */
-	c2s_hash_algo = ses.buf_match_algo(ses.payload, sshhashes, &goodguess);
+	c2s_hash_algo = buf_match_algo(ses.payload, sshhashes, NULL, NULL);
 	if (c2s_hash_algo == NULL) {
 		erralgo = "mac c->s";
 		goto error;
@@ -725,7 +744,7 @@ static void read_kex_algos() {
 	TRACE(("hash c2s is  %s", c2s_hash_algo->name))
 
 	/* mac_algorithms_server_to_client */
-	s2c_hash_algo = ses.buf_match_algo(ses.payload, sshhashes, &goodguess);
+	s2c_hash_algo = buf_match_algo(ses.payload, sshhashes, NULL, NULL);
 	if (s2c_hash_algo == NULL) {
 		erralgo = "mac s->c";
 		goto error;
@@ -733,7 +752,7 @@ static void read_kex_algos() {
 	TRACE(("hash s2c is  %s", s2c_hash_algo->name))
 
 	/* compression_algorithms_client_to_server */
-	c2s_comp_algo = ses.buf_match_algo(ses.payload, ses.compress_algos, &goodguess);
+	c2s_comp_algo = buf_match_algo(ses.payload, ses.compress_algos, NULL, NULL);
 	if (c2s_comp_algo == NULL) {
 		erralgo = "comp c->s";
 		goto error;
@@ -741,7 +760,7 @@ static void read_kex_algos() {
 	TRACE(("hash c2s is  %s", c2s_comp_algo->name))
 
 	/* compression_algorithms_server_to_client */
-	s2c_comp_algo = ses.buf_match_algo(ses.payload, ses.compress_algos, &goodguess);
+	s2c_comp_algo = buf_match_algo(ses.payload, ses.compress_algos, NULL, NULL);
 	if (s2c_comp_algo == NULL) {
 		erralgo = "comp s->c";
 		goto error;
@@ -754,9 +773,10 @@ static void read_kex_algos() {
 	/* languages_server_to_client */
 	buf_eatstring(ses.payload);
 
-	/* first_kex_packet_follows */
+	/* their first_kex_packet_follows */
 	if (buf_getbool(ses.payload)) {
-		ses.kexstate.firstfollows = 1;
+		TRACE(("them kex firstfollows. allgood %d", allgood))
+		ses.kexstate.them_firstfollows = 1;
 		/* if the guess wasn't good, we ignore the packet sent */
 		if (!allgood) {
 			ses.ignorenext = 1;
@@ -799,6 +819,11 @@ static void read_kex_algos() {
 
 	/* reserved for future extensions */
 	buf_getint(ses.payload);
+
+	if (ses.send_kex_first_guess && allgood) {
+		TRACE(("our_first_follows_matches 1"))
+		ses.kexstate.our_first_follows_matches = 1;
+	}
 	return;
 
 error:
diff --git a/dbutil.h b/dbutil.h
index fc01251..3af79f7 100644
--- a/dbutil.h
+++ b/dbutil.h
@@ -35,14 +35,12 @@ void startsyslog();
 
 #ifdef __GNUC__
 #define ATTRIB_PRINTF(fmt,args) __attribute__((format(printf, fmt, args))) 
-#else
-#define ATTRIB_PRINTF(fmt,args)
-#endif
-
-#ifdef __GNUC__
 #define ATTRIB_NORETURN __attribute__((noreturn))
+#define ATTRIB_SENTINEL __attribute__((sentinel))
 #else
+#define ATTRIB_PRINTF(fmt,args)
 #define ATTRIB_NORETURN
+#define ATTRIB_SENTINEL
 #endif
 
 extern void (*_dropbear_exit)(int exitcode, const char* format, va_list param) ATTRIB_NORETURN;
diff --git a/kex.h b/kex.h
index c89b0a3..72430e9 100644
--- a/kex.h
+++ b/kex.h
@@ -51,19 +51,22 @@ struct KEXState {
 
 	unsigned sentkexinit : 1; /*set when we've sent/recv kexinit packet */
 	unsigned recvkexinit : 1;
-	unsigned firstfollows : 1; /* true when first_kex_packet_follows is set */
+	unsigned them_firstfollows : 1; /* true when first_kex_packet_follows is set */
 	unsigned sentnewkeys : 1; /* set once we've send MSG_NEWKEYS (will be cleared once we have also received */
 	unsigned recvnewkeys : 1; /* set once we've received MSG_NEWKEYS (cleared once we have also sent */
 
 	unsigned donefirstkex : 1; /* Set to 1 after the first kex has completed,
 								  ie the transport layer has been set up */
 
+	unsigned our_first_follows_matches : 1;
+
 	time_t lastkextime; /* time of the last kex */
 	unsigned int datatrans; /* data transmitted since last kex */
 	unsigned int datarecv; /* data received since last kex */
 
 };
 
+
 #define MAX_KEXHASHBUF 2000
 
 #endif /* _KEX_H_ */
diff --git a/options.h b/options.h
index c52d6c2..71d39cc 100644
--- a/options.h
+++ b/options.h
@@ -174,9 +174,9 @@ much traffic. */
  * PAM challenge/response.
  * You can't enable both PASSWORD and PAM. */
 
-#define ENABLE_SVR_PASSWORD_AUTH
+//#define ENABLE_SVR_PASSWORD_AUTH
 /* PAM requires ./configure --enable-pam */
-/*#define ENABLE_SVR_PAM_AUTH*/
+#define ENABLE_SVR_PAM_AUTH
 #define ENABLE_SVR_PUBKEY_AUTH
 
 /* Whether to take public key options in 
diff --git a/session.h b/session.h
index dd486f0..a76fa99 100644
--- a/session.h
+++ b/session.h
@@ -171,16 +171,11 @@ struct sshsession {
 	   concluded (ie, while dataallowed was unset)*/
 	struct packetlist *reply_queue_head, *reply_queue_tail;
 
-	algo_type*(*buf_match_algo)(buffer*buf, algo_type localalgos[],
-			int *goodguess); /* The function to use to choose which algorithm
-								to use from the ones presented by the remote
-								side. Is specific to the client/server mode,
-								hence the function-pointer callback.*/
-
 	void(*remoteclosed)(); /* A callback to handle closure of the
 									  remote connection */
 
 	void(*extra_session_cleanup)(); /* client or server specific cleanup */
+	void(*send_kex_first_guess)();
 
 	struct AuthState authstate; /* Common amongst client and server, since most
 								   struct elements are common */
@@ -245,6 +240,7 @@ typedef enum {
 struct clientsession {
 
 	mp_int *dh_e, *dh_x; /* Used during KEX */
+	int dh_val_algo; /* KEX algorithm corresponding to current dh_e and dh_x */
 	cli_kex_state kex_state; /* Used for progressing KEX */
 	cli_state state; /* Used to progress auth/channelsession etc */
 	unsigned donefirstkex : 1; /* Set when we set sentnewkeys, never reset */
diff --git a/svr-algo.c b/svr-algo.c
deleted file mode 100644
index f8f9055..0000000
--- a/svr-algo.c
+++ /dev/null
@@ -1,100 +0,0 @@
-/*
- * Dropbear - a SSH2 server
- * SSH client implementation
- * 
- * Copyright (c) 2002,2003 Matt Johnston
- * Copyright (c) 2004 by Mihnea Stoenescu
- * All rights reserved.
- * 
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to deal
- * in the Software without restriction, including without limitation the rights
- * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- * copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- * 
- * The above copyright notice and this permission notice shall be included in
- * all copies or substantial portions of the Software.
- * 
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE. */
-
-#include "algo.h"
-#include "dbutil.h"
-
-/* match the first algorithm in the comma-separated list in buf which is
- * also in localalgos[], or return NULL on failure.
- * (*goodguess) is set to 1 if the preferred client/server algos match,
- * 0 otherwise. This is used for checking if the kexalgo/hostkeyalgos are
- * guessed correctly */
-algo_type * svr_buf_match_algo(buffer* buf, algo_type localalgos[],
-		int *goodguess)
-{
-
-	unsigned char * algolist = NULL;
-	unsigned char * remotealgos[MAX_PROPOSED_ALGO];
-	unsigned int len;
-	unsigned int count, i, j;
-	algo_type * ret = NULL;
-
-	*goodguess = 0;
-
-	/* get the comma-separated list from the buffer ie "algo1,algo2,algo3" */
-	algolist = buf_getstring(buf, &len);
-	/* Debug this */
-	TRACE(("buf_match_algo: %s", algolist))
-	if (len > MAX_PROPOSED_ALGO*(MAX_NAME_LEN+1)) {
-		goto out; /* just a sanity check, no other use */
-	}
-
-	/* remotealgos will contain a list of the strings parsed out */
-	/* We will have at least one string (even if it's just "") */
-	remotealgos[0] = algolist;
-	count = 1;
-	/* Iterate through, replacing ','s with NULs, to split it into
-	 * words. */
-	for (i = 0; i < len; i++) {
-		if (algolist[i] == '\0') {
-			/* someone is trying something strange */
-			goto out;
-		}
-		if (algolist[i] == ',') {
-			algolist[i] = '\0';
-			remotealgos[count] = &algolist[i+1];
-			count++;
-		}
-		if (count >= MAX_PROPOSED_ALGO) {
-			break;
-		}
-	}
-
-	/* iterate and find the first match */
-	for (i = 0; i < count; i++) {
-
-		len = strlen(remotealgos[i]);
-
-		for (j = 0; localalgos[j].name != NULL; j++) {
-			if (localalgos[j].usable) {
-				if (len == strlen(localalgos[j].name) &&
-						strncmp(localalgos[j].name, remotealgos[i], len) == 0) {
-					/* set if it was a good guess */
-					if (i == 0 && j == 0) {
-						*goodguess = 1;
-					}
-					/* set the algo to return */
-					ret = &localalgos[j];
-					goto out;
-				}
-			}
-		}
-	}
-
-out:
-	m_free(algolist);
-	return ret;
-}
diff --git a/svr-session.c b/svr-session.c
index c235c8a..3a979a1 100644
--- a/svr-session.c
+++ b/svr-session.c
@@ -114,7 +114,6 @@ void svr_session(int sock, int childpipe) {
 
 	/* packet handlers */
 	ses.packettypes = svr_packettypes;
-	ses.buf_match_algo = svr_buf_match_algo;
 
 	ses.isserver = 1;
 
diff --git a/sysoptions.h b/sysoptions.h
index 6e60294..22c2a4d 100644
--- a/sysoptions.h
+++ b/sysoptions.h
@@ -23,6 +23,15 @@
 #define AUTH_TIMEOUT 300 /* we choose 5 minutes */
 #endif
 
+/* A client should try and send an initial key exchange packet guessing
+ * the algorithm that will match - saves a round trip connecting, has little
+ * overhead if the guess was "wrong". */
+#define USE_KEX_FIRST_FOLLOWS
+/* Use protocol extension to allow "first follows" to succeed more frequently.
+ * This is currently Dropbear-specific but will gracefully fallback when connecting
+ * to other implementations. */
+#define USE_KEXGUESS2
+
 /* Minimum key sizes for DSS and RSA */
 #ifndef MIN_DSS_KEYLEN
 #define MIN_DSS_KEYLEN 512
@@ -61,8 +70,9 @@
 #define DROPBEAR_FAILURE -1
 
 /* various algorithm identifiers */
-#define DROPBEAR_KEX_DH_GROUP1 0
-#define DROPBEAR_KEX_DH_GROUP14 1
+#define DROPBEAR_KEX_NONE 0
+#define DROPBEAR_KEX_DH_GROUP1 1
+#define DROPBEAR_KEX_DH_GROUP14 2
 
 #define DROPBEAR_SIGNKEY_ANY 0
 #define DROPBEAR_SIGNKEY_RSA 1