kex.c revision 204917 
1/* $OpenBSD: kex.c,v 1.82 2009/10/24 11:13:54 andreas Exp $ */
2/*
3 * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "includes.h"
27
28#include <sys/param.h>
29
30#include <signal.h>
31#include <stdarg.h>
32#include <stdio.h>
33#include <stdlib.h>
34#include <string.h>
35
36#include <openssl/crypto.h>
37
38#include "xmalloc.h"
39#include "ssh2.h"
40#include "buffer.h"
41#include "packet.h"
42#include "compat.h"
43#include "cipher.h"
44#include "key.h"
45#include "kex.h"
46#include "log.h"
47#include "mac.h"
48#include "match.h"
49#include "dispatch.h"
50#include "monitor.h"
51#include "roaming.h"
52
53#if OPENSSL_VERSION_NUMBER >= 0x00907000L
54# if defined(HAVE_EVP_SHA256)
55# define evp_ssh_sha256 EVP_sha256
56# else
57extern const EVP_MD *evp_ssh_sha256(void);
58# endif
59#endif
60
61/* prototype */
62static void kex_kexinit_finish(Kex *);
63static void kex_choose_conf(Kex *);
64
65/* put algorithm proposal into buffer */
66static void
67kex_prop2buf(Buffer *b, char *proposal[PROPOSAL_MAX])
68{
69	u_int i;
70
71	buffer_clear(b);
72	/*
73	 * add a dummy cookie, the cookie will be overwritten by
74	 * kex_send_kexinit(), each time a kexinit is set
75	 */
76	for (i = 0; i < KEX_COOKIE_LEN; i++)
77		buffer_put_char(b, 0);
78	for (i = 0; i < PROPOSAL_MAX; i++)
79		buffer_put_cstring(b, proposal[i]);
80	buffer_put_char(b, 0);			/* first_kex_packet_follows */
81	buffer_put_int(b, 0);			/* uint32 reserved */
82}
83
84/* parse buffer and return algorithm proposal */
85static char **
86kex_buf2prop(Buffer *raw, int *first_kex_follows)
87{
88	Buffer b;
89	u_int i;
90	char **proposal;
91
92	proposal = xcalloc(PROPOSAL_MAX, sizeof(char *));
93
94	buffer_init(&b);
95	buffer_append(&b, buffer_ptr(raw), buffer_len(raw));
96	/* skip cookie */
97	for (i = 0; i < KEX_COOKIE_LEN; i++)
98		buffer_get_char(&b);
99	/* extract kex init proposal strings */
100	for (i = 0; i < PROPOSAL_MAX; i++) {
101		proposal[i] = buffer_get_string(&b,NULL);
102		debug2("kex_parse_kexinit: %s", proposal[i]);
103	}
104	/* first kex follows / reserved */
105	i = buffer_get_char(&b);
106	if (first_kex_follows != NULL)
107		*first_kex_follows = i;
108	debug2("kex_parse_kexinit: first_kex_follows %d ", i);
109	i = buffer_get_int(&b);
110	debug2("kex_parse_kexinit: reserved %u ", i);
111	buffer_free(&b);
112	return proposal;
113}
114
115static void
116kex_prop_free(char **proposal)
117{
118	u_int i;
119
120	for (i = 0; i < PROPOSAL_MAX; i++)
121		xfree(proposal[i]);
122	xfree(proposal);
123}
124
125/* ARGSUSED */
126static void
127kex_protocol_error(int type, u_int32_t seq, void *ctxt)
128{
129	error("Hm, kex protocol error: type %d seq %u", type, seq);
130}
131
132static void
133kex_reset_dispatch(void)
134{
135	dispatch_range(SSH2_MSG_TRANSPORT_MIN,
136	    SSH2_MSG_TRANSPORT_MAX, &kex_protocol_error);
137	dispatch_set(SSH2_MSG_KEXINIT, &kex_input_kexinit);
138}
139
140void
141kex_finish(Kex *kex)
142{
143	kex_reset_dispatch();
144
145	packet_start(SSH2_MSG_NEWKEYS);
146	packet_send();
147	/* packet_write_wait(); */
148	debug("SSH2_MSG_NEWKEYS sent");
149
150	debug("expecting SSH2_MSG_NEWKEYS");
151	packet_read_expect(SSH2_MSG_NEWKEYS);
152	packet_check_eom();
153	debug("SSH2_MSG_NEWKEYS received");
154
155	kex->done = 1;
156	buffer_clear(&kex->peer);
157	/* buffer_clear(&kex->my); */
158	kex->flags &= ~KEX_INIT_SENT;
159	xfree(kex->name);
160	kex->name = NULL;
161}
162
163void
164kex_send_kexinit(Kex *kex)
165{
166	u_int32_t rnd = 0;
167	u_char *cookie;
168	u_int i;
169
170	if (kex == NULL) {
171		error("kex_send_kexinit: no kex, cannot rekey");
172		return;
173	}
174	if (kex->flags & KEX_INIT_SENT) {
175		debug("KEX_INIT_SENT");
176		return;
177	}
178	kex->done = 0;
179
180	/* generate a random cookie */
181	if (buffer_len(&kex->my) < KEX_COOKIE_LEN)
182		fatal("kex_send_kexinit: kex proposal too short");
183	cookie = buffer_ptr(&kex->my);
184	for (i = 0; i < KEX_COOKIE_LEN; i++) {
185		if (i % 4 == 0)
186			rnd = arc4random();
187		cookie[i] = rnd;
188		rnd >>= 8;
189	}
190	packet_start(SSH2_MSG_KEXINIT);
191	packet_put_raw(buffer_ptr(&kex->my), buffer_len(&kex->my));
192	packet_send();
193	debug("SSH2_MSG_KEXINIT sent");
194	kex->flags |= KEX_INIT_SENT;
195}
196
197/* ARGSUSED */
198void
199kex_input_kexinit(int type, u_int32_t seq, void *ctxt)
200{
201	char *ptr;
202	u_int i, dlen;
203	Kex *kex = (Kex *)ctxt;
204
205	debug("SSH2_MSG_KEXINIT received");
206	if (kex == NULL)
207		fatal("kex_input_kexinit: no kex, cannot rekey");
208
209	ptr = packet_get_raw(&dlen);
210	buffer_append(&kex->peer, ptr, dlen);
211
212	/* discard packet */
213	for (i = 0; i < KEX_COOKIE_LEN; i++)
214		packet_get_char();
215	for (i = 0; i < PROPOSAL_MAX; i++)
216		xfree(packet_get_string(NULL));
217	(void) packet_get_char();
218	(void) packet_get_int();
219	packet_check_eom();
220
221	kex_kexinit_finish(kex);
222}
223
224Kex *
225kex_setup(char *proposal[PROPOSAL_MAX])
226{
227	Kex *kex;
228
229	kex = xcalloc(1, sizeof(*kex));
230	buffer_init(&kex->peer);
231	buffer_init(&kex->my);
232	kex_prop2buf(&kex->my, proposal);
233	kex->done = 0;
234
235	kex_send_kexinit(kex);					/* we start */
236	kex_reset_dispatch();
237
238	return kex;
239}
240
241static void
242kex_kexinit_finish(Kex *kex)
243{
244	if (!(kex->flags & KEX_INIT_SENT))
245		kex_send_kexinit(kex);
246
247	kex_choose_conf(kex);
248
249	if (kex->kex_type >= 0 && kex->kex_type < KEX_MAX &&
250	    kex->kex[kex->kex_type] != NULL) {
251		(kex->kex[kex->kex_type])(kex);
252	} else {
253		fatal("Unsupported key exchange %d", kex->kex_type);
254	}
255}
256
257static void
258choose_enc(Enc *enc, char *client, char *server)
259{
260	char *name = match_list(client, server, NULL);
261	if (name == NULL)
262		fatal("no matching cipher found: client %s server %s",
263		    client, server);
264	if ((enc->cipher = cipher_by_name(name)) == NULL)
265		fatal("matching cipher is not supported: %s", name);
266	enc->name = name;
267	enc->enabled = 0;
268	enc->iv = NULL;
269	enc->key = NULL;
270	enc->key_len = cipher_keylen(enc->cipher);
271	enc->block_size = cipher_blocksize(enc->cipher);
272}
273
274static void
275choose_mac(Mac *mac, char *client, char *server)
276{
277	char *name = match_list(client, server, NULL);
278	if (name == NULL)
279		fatal("no matching mac found: client %s server %s",
280		    client, server);
281	if (mac_setup(mac, name) < 0)
282		fatal("unsupported mac %s", name);
283	/* truncate the key */
284	if (datafellows & SSH_BUG_HMAC)
285		mac->key_len = 16;
286	mac->name = name;
287	mac->key = NULL;
288	mac->enabled = 0;
289}
290
291static void
292choose_comp(Comp *comp, char *client, char *server)
293{
294	char *name = match_list(client, server, NULL);
295	if (name == NULL)
296		fatal("no matching comp found: client %s server %s", client, server);
297	if (strcmp(name, "zlib@openssh.com") == 0) {
298		comp->type = COMP_DELAYED;
299	} else if (strcmp(name, "zlib") == 0) {
300		comp->type = COMP_ZLIB;
301	} else if (strcmp(name, "none") == 0) {
302		comp->type = COMP_NONE;
303	} else {
304		fatal("unsupported comp %s", name);
305	}
306	comp->name = name;
307}
308
309static void
310choose_kex(Kex *k, char *client, char *server)
311{
312	k->name = match_list(client, server, NULL);
313	if (k->name == NULL)
314		fatal("Unable to negotiate a key exchange method");
315	if (strcmp(k->name, KEX_DH1) == 0) {
316		k->kex_type = KEX_DH_GRP1_SHA1;
317		k->evp_md = EVP_sha1();
318	} else if (strcmp(k->name, KEX_DH14) == 0) {
319		k->kex_type = KEX_DH_GRP14_SHA1;
320		k->evp_md = EVP_sha1();
321	} else if (strcmp(k->name, KEX_DHGEX_SHA1) == 0) {
322		k->kex_type = KEX_DH_GEX_SHA1;
323		k->evp_md = EVP_sha1();
324#if OPENSSL_VERSION_NUMBER >= 0x00907000L
325	} else if (strcmp(k->name, KEX_DHGEX_SHA256) == 0) {
326		k->kex_type = KEX_DH_GEX_SHA256;
327		k->evp_md = evp_ssh_sha256();
328#endif
329	} else
330		fatal("bad kex alg %s", k->name);
331}
332
333static void
334choose_hostkeyalg(Kex *k, char *client, char *server)
335{
336	char *hostkeyalg = match_list(client, server, NULL);
337	if (hostkeyalg == NULL)
338		fatal("no hostkey alg");
339	k->hostkey_type = key_type_from_name(hostkeyalg);
340	if (k->hostkey_type == KEY_UNSPEC)
341		fatal("bad hostkey alg '%s'", hostkeyalg);
342	xfree(hostkeyalg);
343}
344
345static int
346proposals_match(char *my[PROPOSAL_MAX], char *peer[PROPOSAL_MAX])
347{
348	static int check[] = {
349		PROPOSAL_KEX_ALGS, PROPOSAL_SERVER_HOST_KEY_ALGS, -1
350	};
351	int *idx;
352	char *p;
353
354	for (idx = &check[0]; *idx != -1; idx++) {
355		if ((p = strchr(my[*idx], ',')) != NULL)
356			*p = '\0';
357		if ((p = strchr(peer[*idx], ',')) != NULL)
358			*p = '\0';
359		if (strcmp(my[*idx], peer[*idx]) != 0) {
360			debug2("proposal mismatch: my %s peer %s",
361			    my[*idx], peer[*idx]);
362			return (0);
363		}
364	}
365	debug2("proposals match");
366	return (1);
367}
368
369static void
370kex_choose_conf(Kex *kex)
371{
372	Newkeys *newkeys;
373	char **my, **peer;
374	char **cprop, **sprop;
375	int nenc, nmac, ncomp;
376	u_int mode, ctos, need;
377	int first_kex_follows, type;
378
379	my   = kex_buf2prop(&kex->my, NULL);
380	peer = kex_buf2prop(&kex->peer, &first_kex_follows);
381
382	if (kex->server) {
383		cprop=peer;
384		sprop=my;
385	} else {
386		cprop=my;
387		sprop=peer;
388	}
389
390	/* Check whether server offers roaming */
391	if (!kex->server) {
392		char *roaming;
393		roaming = match_list(KEX_RESUME, peer[PROPOSAL_KEX_ALGS], NULL);
394		if (roaming) {
395			kex->roaming = 1;
396			xfree(roaming);
397		}
398	}
399
400	/* Algorithm Negotiation */
401	for (mode = 0; mode < MODE_MAX; mode++) {
402		newkeys = xcalloc(1, sizeof(*newkeys));
403		kex->newkeys[mode] = newkeys;
404		ctos = (!kex->server && mode == MODE_OUT) ||
405		    (kex->server && mode == MODE_IN);
406		nenc  = ctos ? PROPOSAL_ENC_ALGS_CTOS  : PROPOSAL_ENC_ALGS_STOC;
407		nmac  = ctos ? PROPOSAL_MAC_ALGS_CTOS  : PROPOSAL_MAC_ALGS_STOC;
408		ncomp = ctos ? PROPOSAL_COMP_ALGS_CTOS : PROPOSAL_COMP_ALGS_STOC;
409		choose_enc (&newkeys->enc,  cprop[nenc],  sprop[nenc]);
410		choose_mac (&newkeys->mac,  cprop[nmac],  sprop[nmac]);
411		choose_comp(&newkeys->comp, cprop[ncomp], sprop[ncomp]);
412		debug("kex: %s %s %s %s",
413		    ctos ? "client->server" : "server->client",
414		    newkeys->enc.name,
415		    newkeys->mac.name,
416		    newkeys->comp.name);
417	}
418	choose_kex(kex, cprop[PROPOSAL_KEX_ALGS], sprop[PROPOSAL_KEX_ALGS]);
419	choose_hostkeyalg(kex, cprop[PROPOSAL_SERVER_HOST_KEY_ALGS],
420	    sprop[PROPOSAL_SERVER_HOST_KEY_ALGS]);
421	need = 0;
422	for (mode = 0; mode < MODE_MAX; mode++) {
423		newkeys = kex->newkeys[mode];
424		if (need < newkeys->enc.key_len)
425			need = newkeys->enc.key_len;
426		if (need < newkeys->enc.block_size)
427			need = newkeys->enc.block_size;
428		if (need < newkeys->mac.key_len)
429			need = newkeys->mac.key_len;
430	}
431	/* XXX need runden? */
432	kex->we_need = need;
433
434	/* ignore the next message if the proposals do not match */
435	if (first_kex_follows && !proposals_match(my, peer) &&
436	    !(datafellows & SSH_BUG_FIRSTKEX)) {
437		type = packet_read();
438		debug2("skipping next packet (type %u)", type);
439	}
440
441	kex_prop_free(my);
442	kex_prop_free(peer);
443}
444
445static u_char *
446derive_key(Kex *kex, int id, u_int need, u_char *hash, u_int hashlen,
447    BIGNUM *shared_secret)
448{
449	Buffer b;
450	EVP_MD_CTX md;
451	char c = id;
452	u_int have;
453	int mdsz;
454	u_char *digest;
455
456	if ((mdsz = EVP_MD_size(kex->evp_md)) <= 0)
457		fatal("bad kex md size %d", mdsz);
458	digest = xmalloc(roundup(need, mdsz));
459
460	buffer_init(&b);
461	buffer_put_bignum2(&b, shared_secret);
462
463	/* K1 = HASH(K || H || "A" || session_id) */
464	EVP_DigestInit(&md, kex->evp_md);
465	if (!(datafellows & SSH_BUG_DERIVEKEY))
466		EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
467	EVP_DigestUpdate(&md, hash, hashlen);
468	EVP_DigestUpdate(&md, &c, 1);
469	EVP_DigestUpdate(&md, kex->session_id, kex->session_id_len);
470	EVP_DigestFinal(&md, digest, NULL);
471
472	/*
473	 * expand key:
474	 * Kn = HASH(K || H || K1 || K2 || ... || Kn-1)
475	 * Key = K1 || K2 || ... || Kn
476	 */
477	for (have = mdsz; need > have; have += mdsz) {
478		EVP_DigestInit(&md, kex->evp_md);
479		if (!(datafellows & SSH_BUG_DERIVEKEY))
480			EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
481		EVP_DigestUpdate(&md, hash, hashlen);
482		EVP_DigestUpdate(&md, digest, have);
483		EVP_DigestFinal(&md, digest + have, NULL);
484	}
485	buffer_free(&b);
486#ifdef DEBUG_KEX
487	fprintf(stderr, "key '%c'== ", c);
488	dump_digest("key", digest, need);
489#endif
490	return digest;
491}
492
493Newkeys *current_keys[MODE_MAX];
494
495#define NKEYS	6
496void
497kex_derive_keys(Kex *kex, u_char *hash, u_int hashlen, BIGNUM *shared_secret)
498{
499	u_char *keys[NKEYS];
500	u_int i, mode, ctos;
501
502	for (i = 0; i < NKEYS; i++) {
503		keys[i] = derive_key(kex, 'A'+i, kex->we_need, hash, hashlen,
504		    shared_secret);
505	}
506
507	debug2("kex_derive_keys");
508	for (mode = 0; mode < MODE_MAX; mode++) {
509		current_keys[mode] = kex->newkeys[mode];
510		kex->newkeys[mode] = NULL;
511		ctos = (!kex->server && mode == MODE_OUT) ||
512		    (kex->server && mode == MODE_IN);
513		current_keys[mode]->enc.iv  = keys[ctos ? 0 : 1];
514		current_keys[mode]->enc.key = keys[ctos ? 2 : 3];
515		current_keys[mode]->mac.key = keys[ctos ? 4 : 5];
516	}
517}
518
519Newkeys *
520kex_get_newkeys(int mode)
521{
522	Newkeys *ret;
523
524	ret = current_keys[mode];
525	current_keys[mode] = NULL;
526	return ret;
527}
528
529void
530derive_ssh1_session_id(BIGNUM *host_modulus, BIGNUM *server_modulus,
531    u_int8_t cookie[8], u_int8_t id[16])
532{
533	const EVP_MD *evp_md = EVP_md5();
534	EVP_MD_CTX md;
535	u_int8_t nbuf[2048], obuf[EVP_MAX_MD_SIZE];
536	int len;
537
538	EVP_DigestInit(&md, evp_md);
539
540	len = BN_num_bytes(host_modulus);
541	if (len < (512 / 8) || (u_int)len > sizeof(nbuf))
542		fatal("%s: bad host modulus (len %d)", __func__, len);
543	BN_bn2bin(host_modulus, nbuf);
544	EVP_DigestUpdate(&md, nbuf, len);
545
546	len = BN_num_bytes(server_modulus);
547	if (len < (512 / 8) || (u_int)len > sizeof(nbuf))
548		fatal("%s: bad server modulus (len %d)", __func__, len);
549	BN_bn2bin(server_modulus, nbuf);
550	EVP_DigestUpdate(&md, nbuf, len);
551
552	EVP_DigestUpdate(&md, cookie, 8);
553
554	EVP_DigestFinal(&md, obuf, NULL);
555	memcpy(id, obuf, 16);
556
557	memset(nbuf, 0, sizeof(nbuf));
558	memset(obuf, 0, sizeof(obuf));
559	memset(&md, 0, sizeof(md));
560}
561
562#if defined(DEBUG_KEX) || defined(DEBUG_KEXDH)
563void
564dump_digest(char *msg, u_char *digest, int len)
565{
566	u_int i;
567
568	fprintf(stderr, "%s\n", msg);
569	for (i = 0; i < len; i++) {
570		fprintf(stderr, "%02x", digest[i]);
571		if (i%32 == 31)
572			fprintf(stderr, "\n");
573		else if (i%8 == 7)
574			fprintf(stderr, " ");
575	}
576	fprintf(stderr, "\n");
577}
578#endif
579