kex.c revision 1.9 
1/*
2 * Copyright (c) 2000 Markus Friedl.  All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 *    notice, this list of conditions and the following disclaimer in the
11 *    documentation and/or other materials provided with the distribution.
12 * 3. All advertising materials mentioning features or use of this software
13 *    must display the following acknowledgement:
14 *      This product includes software developed by Markus Friedl.
15 * 4. The name of the author may not be used to endorse or promote products
16 *    derived from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30#include "includes.h"
31RCSID("$OpenBSD: kex.c,v 1.9 2000/07/10 16:30:25 ho Exp $");
32
33#include "ssh.h"
34#include "ssh2.h"
35#include "xmalloc.h"
36#include "buffer.h"
37#include "bufaux.h"
38#include "packet.h"
39#include "cipher.h"
40#include "compat.h"
41
42#include <openssl/bn.h>
43#include <openssl/dh.h>
44
45#include <openssl/crypto.h>
46#include <openssl/bio.h>
47#include <openssl/bn.h>
48#include <openssl/dh.h>
49#include <openssl/pem.h>
50
51#include "kex.h"
52
53#define KEX_COOKIE_LEN	16
54
55Buffer *
56kex_init(char *myproposal[PROPOSAL_MAX])
57{
58	int first_kex_packet_follows = 0;
59	unsigned char cookie[KEX_COOKIE_LEN];
60	u_int32_t rand = 0;
61	int i;
62	Buffer *ki = xmalloc(sizeof(*ki));
63	for (i = 0; i < KEX_COOKIE_LEN; i++) {
64		if (i % 4 == 0)
65			rand = arc4random();
66		cookie[i] = rand & 0xff;
67		rand >>= 8;
68	}
69	buffer_init(ki);
70	buffer_append(ki, (char *)cookie, sizeof cookie);
71	for (i = 0; i < PROPOSAL_MAX; i++)
72		buffer_put_cstring(ki, myproposal[i]);
73	buffer_put_char(ki, first_kex_packet_follows);
74	buffer_put_int(ki, 0);				/* uint32 reserved */
75	return ki;
76}
77
78/* send kexinit, parse and save reply */
79void
80kex_exchange_kexinit(
81    Buffer *my_kexinit, Buffer *peer_kexint,
82    char *peer_proposal[PROPOSAL_MAX])
83{
84	int i;
85	char *ptr;
86	int plen;
87
88	debug("send KEXINIT");
89	packet_start(SSH2_MSG_KEXINIT);
90	packet_put_raw(buffer_ptr(my_kexinit), buffer_len(my_kexinit));
91	packet_send();
92	packet_write_wait();
93	debug("done");
94
95	/*
96	 * read and save raw KEXINIT payload in buffer. this is used during
97	 * computation of the session_id and the session keys.
98	 */
99	debug("wait KEXINIT");
100	packet_read_expect(&plen, SSH2_MSG_KEXINIT);
101	ptr = packet_get_raw(&plen);
102	buffer_append(peer_kexint, ptr, plen);
103
104	/* parse packet and save algorithm proposal */
105	/* skip cookie */
106	for (i = 0; i < KEX_COOKIE_LEN; i++)
107		packet_get_char();
108	/* extract kex init proposal strings */
109	for (i = 0; i < PROPOSAL_MAX; i++) {
110		peer_proposal[i] = packet_get_string(NULL);
111		debug("got kexinit: %s", peer_proposal[i]);
112	}
113	/* first kex follow / reserved */
114	i = packet_get_char();
115	debug("first kex follow: %d ", i);
116	i = packet_get_int();
117	debug("reserved: %d ", i);
118	packet_done();
119	debug("done");
120}
121
122/* diffie-hellman-group1-sha1 */
123
124int
125dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
126{
127	int i;
128	int n = BN_num_bits(dh_pub);
129	int bits_set = 0;
130
131	/* we only accept g==2 */
132	if (!BN_is_word(dh->g, 2)) {
133		log("invalid DH base != 2");
134		return 0;
135	}
136	if (dh_pub->neg) {
137		log("invalid public DH value: negativ");
138		return 0;
139	}
140	for (i = 0; i <= n; i++)
141		if (BN_is_bit_set(dh_pub, i))
142			bits_set++;
143	debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
144
145	/* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
146	if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
147		return 1;
148	log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
149	return 0;
150}
151
152DH *
153dh_new_group1()
154{
155	static char *group1 =
156	    "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
157	    "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
158	    "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
159	    "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
160	    "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
161	    "FFFFFFFF" "FFFFFFFF";
162	DH *dh;
163	int ret, tries = 0;
164	dh = DH_new();
165	if(dh == NULL)
166		fatal("DH_new");
167	ret = BN_hex2bn(&dh->p, group1);
168	if(ret<0)
169		fatal("BN_hex2bn");
170	dh->g = BN_new();
171	if(dh->g == NULL)
172		fatal("DH_new g");
173	BN_set_word(dh->g, 2);
174	do {
175		if (DH_generate_key(dh) == 0)
176			fatal("DH_generate_key");
177		if (tries++ > 10)
178			fatal("dh_new_group1: too many bad keys: giving up");
179	} while (!dh_pub_is_valid(dh, dh->pub_key));
180	return dh;
181}
182
183void
184dump_digest(unsigned char *digest, int len)
185{
186	int i;
187	for (i = 0; i< len; i++){
188		fprintf(stderr, "%02x", digest[i]);
189		if(i%2!=0)
190			fprintf(stderr, " ");
191	}
192	fprintf(stderr, "\n");
193}
194
195unsigned char *
196kex_hash(
197    char *client_version_string,
198    char *server_version_string,
199    char *ckexinit, int ckexinitlen,
200    char *skexinit, int skexinitlen,
201    char *serverhostkeyblob, int sbloblen,
202    BIGNUM *client_dh_pub,
203    BIGNUM *server_dh_pub,
204    BIGNUM *shared_secret)
205{
206	Buffer b;
207	static unsigned char digest[EVP_MAX_MD_SIZE];
208	EVP_MD *evp_md = EVP_sha1();
209	EVP_MD_CTX md;
210
211	buffer_init(&b);
212	buffer_put_string(&b, client_version_string, strlen(client_version_string));
213	buffer_put_string(&b, server_version_string, strlen(server_version_string));
214
215	/* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */
216	buffer_put_int(&b, ckexinitlen+1);
217	buffer_put_char(&b, SSH2_MSG_KEXINIT);
218	buffer_append(&b, ckexinit, ckexinitlen);
219	buffer_put_int(&b, skexinitlen+1);
220	buffer_put_char(&b, SSH2_MSG_KEXINIT);
221	buffer_append(&b, skexinit, skexinitlen);
222
223	buffer_put_string(&b, serverhostkeyblob, sbloblen);
224	buffer_put_bignum2(&b, client_dh_pub);
225	buffer_put_bignum2(&b, server_dh_pub);
226	buffer_put_bignum2(&b, shared_secret);
227
228#ifdef DEBUG_KEX
229	buffer_dump(&b);
230#endif
231
232	EVP_DigestInit(&md, evp_md);
233	EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
234	EVP_DigestFinal(&md, digest, NULL);
235
236	buffer_free(&b);
237
238#ifdef DEBUG_KEX
239	dump_digest(digest, evp_md->md_size);
240#endif
241	return digest;
242}
243
244unsigned char *
245derive_key(int id, int need, char unsigned *hash, BIGNUM *shared_secret)
246{
247	Buffer b;
248	EVP_MD *evp_md = EVP_sha1();
249	EVP_MD_CTX md;
250	char c = id;
251	int have;
252	int mdsz = evp_md->md_size;
253	unsigned char *digest = xmalloc(((need+mdsz-1)/mdsz)*mdsz);
254
255	buffer_init(&b);
256	buffer_put_bignum2(&b, shared_secret);
257
258	EVP_DigestInit(&md, evp_md);
259	EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));	/* shared_secret K */
260	EVP_DigestUpdate(&md, hash, mdsz);		/* transport-06 */
261	EVP_DigestUpdate(&md, &c, 1);			/* key id */
262	EVP_DigestUpdate(&md, hash, mdsz);		/* session id */
263	EVP_DigestFinal(&md, digest, NULL);
264
265	/* expand */
266	for (have = mdsz; need > have; have += mdsz) {
267		EVP_DigestInit(&md, evp_md);
268		EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
269		EVP_DigestUpdate(&md, hash, mdsz);
270		EVP_DigestUpdate(&md, digest, have);
271		EVP_DigestFinal(&md, digest + have, NULL);
272	}
273	buffer_free(&b);
274#ifdef DEBUG_KEX
275	fprintf(stderr, "Digest '%c'== ", c);
276	dump_digest(digest, need);
277#endif
278	return digest;
279}
280
281#define NKEYS	6
282
283#define	MAX_PROP	20
284#define	SEP	","
285
286char *
287get_match(char *client, char *server)
288{
289	char *sproposals[MAX_PROP];
290	char *c, *s, *p, *ret, *cp, *sp;
291	int i, j, nproposals;
292
293	c = cp = xstrdup(client);
294	s = sp = xstrdup(server);
295
296	for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0';
297	     (p = strsep(&sp, SEP)), i++) {
298		if (i < MAX_PROP)
299			sproposals[i] = p;
300		else
301			break;
302	}
303	nproposals = i;
304
305	for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0';
306	     (p = strsep(&cp, SEP)), i++) {
307		for (j = 0; j < nproposals; j++) {
308			if (strcmp(p, sproposals[j]) == 0) {
309				ret = xstrdup(p);
310				xfree(c);
311				xfree(s);
312				return ret;
313			}
314		}
315	}
316	xfree(c);
317	xfree(s);
318	return NULL;
319}
320void
321choose_enc(Enc *enc, char *client, char *server)
322{
323	char *name = get_match(client, server);
324	if (name == NULL)
325		fatal("no matching cipher found: client %s server %s", client, server);
326	enc->type = cipher_number(name);
327
328	switch (enc->type) {
329	case SSH_CIPHER_3DES_CBC:
330		enc->key_len = 24;
331		enc->iv_len = 8;
332		enc->block_size = 8;
333		break;
334	case SSH_CIPHER_BLOWFISH_CBC:
335	case SSH_CIPHER_CAST128_CBC:
336		enc->key_len = 16;
337		enc->iv_len = 8;
338		enc->block_size = 8;
339		break;
340	case SSH_CIPHER_ARCFOUR:
341		enc->key_len = 16;
342		enc->iv_len = 0;
343		enc->block_size = 8;
344		break;
345	default:
346		fatal("unsupported cipher %s", name);
347	}
348	enc->name = name;
349	enc->enabled = 0;
350	enc->iv = NULL;
351	enc->key = NULL;
352}
353void
354choose_mac(Mac *mac, char *client, char *server)
355{
356	char *name = get_match(client, server);
357	if (name == NULL)
358		fatal("no matching mac found: client %s server %s", client, server);
359	if (strcmp(name, "hmac-md5") == 0) {
360		mac->md = EVP_md5();
361	} else if (strcmp(name, "hmac-sha1") == 0) {
362		mac->md = EVP_sha1();
363	} else if (strcmp(name, "hmac-ripemd160@openssh.com") == 0) {
364		mac->md = EVP_ripemd160();
365	} else {
366		fatal("unsupported mac %s", name);
367	}
368	mac->name = name;
369	mac->mac_len = mac->md->md_size;
370	mac->key_len = (datafellows & SSH_BUG_HMAC) ? 16 : mac->mac_len;
371	mac->key = NULL;
372	mac->enabled = 0;
373}
374void
375choose_comp(Comp *comp, char *client, char *server)
376{
377	char *name = get_match(client, server);
378	if (name == NULL)
379		fatal("no matching comp found: client %s server %s", client, server);
380	if (strcmp(name, "zlib") == 0) {
381		comp->type = 1;
382	} else if (strcmp(name, "none") == 0) {
383		comp->type = 0;
384	} else {
385		fatal("unsupported comp %s", name);
386	}
387	comp->name = name;
388}
389void
390choose_kex(Kex *k, char *client, char *server)
391{
392	k->name = get_match(client, server);
393	if (k->name == NULL)
394		fatal("no kex alg");
395	if (strcmp(k->name, KEX_DH1) != 0)
396		fatal("bad kex alg %s", k->name);
397}
398void
399choose_hostkeyalg(Kex *k, char *client, char *server)
400{
401	k->hostkeyalg = get_match(client, server);
402	if (k->hostkeyalg == NULL)
403		fatal("no hostkey alg");
404	if (strcmp(k->hostkeyalg, KEX_DSS) != 0)
405		fatal("bad hostkey alg %s", k->hostkeyalg);
406}
407
408Kex *
409kex_choose_conf(char *cprop[PROPOSAL_MAX], char *sprop[PROPOSAL_MAX], int server)
410{
411	int mode;
412	int ctos;				/* direction: if true client-to-server */
413	int need;
414	Kex *k;
415
416	k = xmalloc(sizeof(*k));
417	memset(k, 0, sizeof(*k));
418	k->server = server;
419
420	for (mode = 0; mode < MODE_MAX; mode++) {
421		int nenc, nmac, ncomp;
422		ctos = (!k->server && mode == MODE_OUT) || (k->server && mode == MODE_IN);
423		nenc  = ctos ? PROPOSAL_ENC_ALGS_CTOS  : PROPOSAL_ENC_ALGS_STOC;
424		nmac  = ctos ? PROPOSAL_MAC_ALGS_CTOS  : PROPOSAL_MAC_ALGS_STOC;
425		ncomp = ctos ? PROPOSAL_COMP_ALGS_CTOS : PROPOSAL_COMP_ALGS_STOC;
426		choose_enc (&k->enc [mode], cprop[nenc],  sprop[nenc]);
427		choose_mac (&k->mac [mode], cprop[nmac],  sprop[nmac]);
428		choose_comp(&k->comp[mode], cprop[ncomp], sprop[ncomp]);
429		debug("kex: %s %s %s %s",
430		    ctos ? "client->server" : "server->client",
431		    k->enc[mode].name,
432		    k->mac[mode].name,
433		    k->comp[mode].name);
434	}
435	choose_kex(k, cprop[PROPOSAL_KEX_ALGS], sprop[PROPOSAL_KEX_ALGS]);
436	choose_hostkeyalg(k, cprop[PROPOSAL_SERVER_HOST_KEY_ALGS],
437	    sprop[PROPOSAL_SERVER_HOST_KEY_ALGS]);
438	need = 0;
439	for (mode = 0; mode < MODE_MAX; mode++) {
440	    if (need < k->enc[mode].key_len)
441		    need = k->enc[mode].key_len;
442	    if (need < k->enc[mode].iv_len)
443		    need = k->enc[mode].iv_len;
444	    if (need < k->mac[mode].key_len)
445		    need = k->mac[mode].key_len;
446	}
447	/* XXX need runden? */
448	k->we_need = need;
449	return k;
450}
451
452int
453kex_derive_keys(Kex *k, unsigned char *hash, BIGNUM *shared_secret)
454{
455	int i;
456	int mode;
457	int ctos;
458	unsigned char *keys[NKEYS];
459
460	for (i = 0; i < NKEYS; i++)
461		keys[i] = derive_key('A'+i, k->we_need, hash, shared_secret);
462
463	for (mode = 0; mode < MODE_MAX; mode++) {
464		ctos = (!k->server && mode == MODE_OUT) || (k->server && mode == MODE_IN);
465		k->enc[mode].iv  = keys[ctos ? 0 : 1];
466		k->enc[mode].key = keys[ctos ? 2 : 3];
467		k->mac[mode].key = keys[ctos ? 4 : 5];
468	}
469	return 0;
470}
471