kex.c revision 181097 
1/* $OpenBSD: kex.c,v 1.76 2006/08/03 03:34:42 deraadt 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
52#define KEX_COOKIE_LEN	16
53
54#if OPENSSL_VERSION_NUMBER >= 0x00907000L
55# if defined(HAVE_EVP_SHA256)
56# define evp_ssh_sha256 EVP_sha256
57# else
58extern const EVP_MD *evp_ssh_sha256(void);
59# endif
60#endif
61
62/* prototype */
63static void kex_kexinit_finish(Kex *);
64static void kex_choose_conf(Kex *);
65
66/* put algorithm proposal into buffer */
67static void
68kex_prop2buf(Buffer *b, char *proposal[PROPOSAL_MAX])
69{
70	u_int i;
71
72	buffer_clear(b);
73	/*
74	 * add a dummy cookie, the cookie will be overwritten by
75	 * kex_send_kexinit(), each time a kexinit is set
76	 */
77	for (i = 0; i < KEX_COOKIE_LEN; i++)
78		buffer_put_char(b, 0);
79	for (i = 0; i < PROPOSAL_MAX; i++)
80		buffer_put_cstring(b, proposal[i]);
81	buffer_put_char(b, 0);			/* first_kex_packet_follows */
82	buffer_put_int(b, 0);			/* uint32 reserved */
83}
84
85/* parse buffer and return algorithm proposal */
86static char **
87kex_buf2prop(Buffer *raw, int *first_kex_follows)
88{
89	Buffer b;
90	int i;
91	char **proposal;
92
93	proposal = xcalloc(PROPOSAL_MAX, sizeof(char *));
94
95	buffer_init(&b);
96	buffer_append(&b, buffer_ptr(raw), buffer_len(raw));
97	/* skip cookie */
98	for (i = 0; i < KEX_COOKIE_LEN; i++)
99		buffer_get_char(&b);
100	/* extract kex init proposal strings */
101	for (i = 0; i < PROPOSAL_MAX; i++) {
102		proposal[i] = buffer_get_string(&b,NULL);
103		debug2("kex_parse_kexinit: %s", proposal[i]);
104	}
105	/* first kex follows / reserved */
106	i = buffer_get_char(&b);
107	if (first_kex_follows != NULL)
108		*first_kex_follows = i;
109	debug2("kex_parse_kexinit: first_kex_follows %d ", i);
110	i = buffer_get_int(&b);
111	debug2("kex_parse_kexinit: reserved %d ", i);
112	buffer_free(&b);
113	return proposal;
114}
115
116static void
117kex_prop_free(char **proposal)
118{
119	u_int i;
120
121	for (i = 0; i < PROPOSAL_MAX; i++)
122		xfree(proposal[i]);
123	xfree(proposal);
124}
125
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
197void
198kex_input_kexinit(int type, u_int32_t seq, void *ctxt)
199{
200	char *ptr;
201	u_int i, dlen;
202	Kex *kex = (Kex *)ctxt;
203
204	debug("SSH2_MSG_KEXINIT received");
205	if (kex == NULL)
206		fatal("kex_input_kexinit: no kex, cannot rekey");
207
208	ptr = packet_get_raw(&dlen);
209	buffer_append(&kex->peer, ptr, dlen);
210
211	/* discard packet */
212	for (i = 0; i < KEX_COOKIE_LEN; i++)
213		packet_get_char();
214	for (i = 0; i < PROPOSAL_MAX; i++)
215		xfree(packet_get_string(NULL));
216	(void) packet_get_char();
217	(void) packet_get_int();
218	packet_check_eom();
219
220	kex_kexinit_finish(kex);
221}
222
223Kex *
224kex_setup(char *proposal[PROPOSAL_MAX])
225{
226	Kex *kex;
227
228	kex = xcalloc(1, sizeof(*kex));
229	buffer_init(&kex->peer);
230	buffer_init(&kex->my);
231	kex_prop2buf(&kex->my, proposal);
232	kex->done = 0;
233
234	kex_send_kexinit(kex);					/* we start */
235	kex_reset_dispatch();
236
237	return kex;
238}
239
240static void
241kex_kexinit_finish(Kex *kex)
242{
243	if (!(kex->flags & KEX_INIT_SENT))
244		kex_send_kexinit(kex);
245
246	kex_choose_conf(kex);
247
248	if (kex->kex_type >= 0 && kex->kex_type < KEX_MAX &&
249	    kex->kex[kex->kex_type] != NULL) {
250		(kex->kex[kex->kex_type])(kex);
251	} else {
252		fatal("Unsupported key exchange %d", kex->kex_type);
253	}
254}
255
256static void
257choose_enc(Enc *enc, char *client, char *server)
258{
259	char *name = match_list(client, server, NULL);
260	if (name == NULL)
261		fatal("no matching cipher found: client %s server %s", client, server);
262	if ((enc->cipher = cipher_by_name(name)) == NULL)
263		fatal("matching cipher is not supported: %s", name);
264	enc->name = name;
265	enc->enabled = 0;
266	enc->iv = NULL;
267	enc->key = NULL;
268	enc->key_len = cipher_keylen(enc->cipher);
269	enc->block_size = cipher_blocksize(enc->cipher);
270}
271
272static void
273choose_mac(Mac *mac, char *client, char *server)
274{
275	char *name = match_list(client, server, NULL);
276	if (name == NULL)
277		fatal("no matching mac found: client %s server %s", client, server);
278	if (mac_init(mac, name) < 0)
279		fatal("unsupported mac %s", name);
280	/* truncate the key */
281	if (datafellows & SSH_BUG_HMAC)
282		mac->key_len = 16;
283	mac->name = name;
284	mac->key = NULL;
285	mac->enabled = 0;
286}
287
288static void
289choose_comp(Comp *comp, char *client, char *server)
290{
291	char *name = match_list(client, server, NULL);
292	if (name == NULL)
293		fatal("no matching comp found: client %s server %s", client, server);
294	if (strcmp(name, "zlib@openssh.com") == 0) {
295		comp->type = COMP_DELAYED;
296	} else if (strcmp(name, "zlib") == 0) {
297		comp->type = COMP_ZLIB;
298	} else if (strcmp(name, "none") == 0) {
299		comp->type = COMP_NONE;
300	} else {
301		fatal("unsupported comp %s", name);
302	}
303	comp->name = name;
304}
305
306static void
307choose_kex(Kex *k, char *client, char *server)
308{
309	k->name = match_list(client, server, NULL);
310	if (k->name == NULL)
311		fatal("no kex alg");
312	if (strcmp(k->name, KEX_DH1) == 0) {
313		k->kex_type = KEX_DH_GRP1_SHA1;
314		k->evp_md = EVP_sha1();
315	} else if (strcmp(k->name, KEX_DH14) == 0) {
316		k->kex_type = KEX_DH_GRP14_SHA1;
317		k->evp_md = EVP_sha1();
318	} else if (strcmp(k->name, KEX_DHGEX_SHA1) == 0) {
319		k->kex_type = KEX_DH_GEX_SHA1;
320		k->evp_md = EVP_sha1();
321#if OPENSSL_VERSION_NUMBER >= 0x00907000L
322	} else if (strcmp(k->name, KEX_DHGEX_SHA256) == 0) {
323		k->kex_type = KEX_DH_GEX_SHA256;
324		k->evp_md = evp_ssh_sha256();
325#endif
326	} else
327		fatal("bad kex alg %s", k->name);
328}
329
330static void
331choose_hostkeyalg(Kex *k, char *client, char *server)
332{
333	char *hostkeyalg = match_list(client, server, NULL);
334	if (hostkeyalg == NULL)
335		fatal("no hostkey alg");
336	k->hostkey_type = key_type_from_name(hostkeyalg);
337	if (k->hostkey_type == KEY_UNSPEC)
338		fatal("bad hostkey alg '%s'", hostkeyalg);
339	xfree(hostkeyalg);
340}
341
342static int
343proposals_match(char *my[PROPOSAL_MAX], char *peer[PROPOSAL_MAX])
344{
345	static int check[] = {
346		PROPOSAL_KEX_ALGS, PROPOSAL_SERVER_HOST_KEY_ALGS, -1
347	};
348	int *idx;
349	char *p;
350
351	for (idx = &check[0]; *idx != -1; idx++) {
352		if ((p = strchr(my[*idx], ',')) != NULL)
353			*p = '\0';
354		if ((p = strchr(peer[*idx], ',')) != NULL)
355			*p = '\0';
356		if (strcmp(my[*idx], peer[*idx]) != 0) {
357			debug2("proposal mismatch: my %s peer %s",
358			    my[*idx], peer[*idx]);
359			return (0);
360		}
361	}
362	debug2("proposals match");
363	return (1);
364}
365
366static void
367kex_choose_conf(Kex *kex)
368{
369	Newkeys *newkeys;
370	char **my, **peer;
371	char **cprop, **sprop;
372	int nenc, nmac, ncomp;
373	u_int mode, ctos, need;
374	int first_kex_follows, type;
375
376	my   = kex_buf2prop(&kex->my, NULL);
377	peer = kex_buf2prop(&kex->peer, &first_kex_follows);
378
379	if (kex->server) {
380		cprop=peer;
381		sprop=my;
382	} else {
383		cprop=my;
384		sprop=peer;
385	}
386
387	/* Algorithm Negotiation */
388	for (mode = 0; mode < MODE_MAX; mode++) {
389		newkeys = xcalloc(1, sizeof(*newkeys));
390		kex->newkeys[mode] = newkeys;
391		ctos = (!kex->server && mode == MODE_OUT) || (kex->server && mode == MODE_IN);
392		nenc  = ctos ? PROPOSAL_ENC_ALGS_CTOS  : PROPOSAL_ENC_ALGS_STOC;
393		nmac  = ctos ? PROPOSAL_MAC_ALGS_CTOS  : PROPOSAL_MAC_ALGS_STOC;
394		ncomp = ctos ? PROPOSAL_COMP_ALGS_CTOS : PROPOSAL_COMP_ALGS_STOC;
395		choose_enc (&newkeys->enc,  cprop[nenc],  sprop[nenc]);
396		choose_mac (&newkeys->mac,  cprop[nmac],  sprop[nmac]);
397		choose_comp(&newkeys->comp, cprop[ncomp], sprop[ncomp]);
398		debug("kex: %s %s %s %s",
399		    ctos ? "client->server" : "server->client",
400		    newkeys->enc.name,
401		    newkeys->mac.name,
402		    newkeys->comp.name);
403	}
404	choose_kex(kex, cprop[PROPOSAL_KEX_ALGS], sprop[PROPOSAL_KEX_ALGS]);
405	choose_hostkeyalg(kex, cprop[PROPOSAL_SERVER_HOST_KEY_ALGS],
406	    sprop[PROPOSAL_SERVER_HOST_KEY_ALGS]);
407	need = 0;
408	for (mode = 0; mode < MODE_MAX; mode++) {
409		newkeys = kex->newkeys[mode];
410		if (need < newkeys->enc.key_len)
411			need = newkeys->enc.key_len;
412		if (need < newkeys->enc.block_size)
413			need = newkeys->enc.block_size;
414		if (need < newkeys->mac.key_len)
415			need = newkeys->mac.key_len;
416	}
417	/* XXX need runden? */
418	kex->we_need = need;
419
420	/* ignore the next message if the proposals do not match */
421	if (first_kex_follows && !proposals_match(my, peer) &&
422	    !(datafellows & SSH_BUG_FIRSTKEX)) {
423		type = packet_read();
424		debug2("skipping next packet (type %u)", type);
425	}
426
427	kex_prop_free(my);
428	kex_prop_free(peer);
429}
430
431static u_char *
432derive_key(Kex *kex, int id, u_int need, u_char *hash, u_int hashlen,
433    BIGNUM *shared_secret)
434{
435	Buffer b;
436	EVP_MD_CTX md;
437	char c = id;
438	u_int have;
439	int mdsz;
440	u_char *digest;
441
442	if ((mdsz = EVP_MD_size(kex->evp_md)) <= 0)
443		fatal("bad kex md size %d", mdsz);
444	digest = xmalloc(roundup(need, mdsz));
445
446	buffer_init(&b);
447	buffer_put_bignum2(&b, shared_secret);
448
449	/* K1 = HASH(K || H || "A" || session_id) */
450	EVP_DigestInit(&md, kex->evp_md);
451	if (!(datafellows & SSH_BUG_DERIVEKEY))
452		EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
453	EVP_DigestUpdate(&md, hash, hashlen);
454	EVP_DigestUpdate(&md, &c, 1);
455	EVP_DigestUpdate(&md, kex->session_id, kex->session_id_len);
456	EVP_DigestFinal(&md, digest, NULL);
457
458	/*
459	 * expand key:
460	 * Kn = HASH(K || H || K1 || K2 || ... || Kn-1)
461	 * Key = K1 || K2 || ... || Kn
462	 */
463	for (have = mdsz; need > have; have += mdsz) {
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, digest, have);
469		EVP_DigestFinal(&md, digest + have, NULL);
470	}
471	buffer_free(&b);
472#ifdef DEBUG_KEX
473	fprintf(stderr, "key '%c'== ", c);
474	dump_digest("key", digest, need);
475#endif
476	return digest;
477}
478
479Newkeys *current_keys[MODE_MAX];
480
481#define NKEYS	6
482void
483kex_derive_keys(Kex *kex, u_char *hash, u_int hashlen, BIGNUM *shared_secret)
484{
485	u_char *keys[NKEYS];
486	u_int i, mode, ctos;
487
488	for (i = 0; i < NKEYS; i++) {
489		keys[i] = derive_key(kex, 'A'+i, kex->we_need, hash, hashlen,
490		    shared_secret);
491	}
492
493	debug2("kex_derive_keys");
494	for (mode = 0; mode < MODE_MAX; mode++) {
495		current_keys[mode] = kex->newkeys[mode];
496		kex->newkeys[mode] = NULL;
497		ctos = (!kex->server && mode == MODE_OUT) ||
498		    (kex->server && mode == MODE_IN);
499		current_keys[mode]->enc.iv  = keys[ctos ? 0 : 1];
500		current_keys[mode]->enc.key = keys[ctos ? 2 : 3];
501		current_keys[mode]->mac.key = keys[ctos ? 4 : 5];
502	}
503}
504
505Newkeys *
506kex_get_newkeys(int mode)
507{
508	Newkeys *ret;
509
510	ret = current_keys[mode];
511	current_keys[mode] = NULL;
512	return ret;
513}
514
515void
516derive_ssh1_session_id(BIGNUM *host_modulus, BIGNUM *server_modulus,
517    u_int8_t cookie[8], u_int8_t id[16])
518{
519	const EVP_MD *evp_md = EVP_md5();
520	EVP_MD_CTX md;
521	u_int8_t nbuf[2048], obuf[EVP_MAX_MD_SIZE];
522	int len;
523
524	EVP_DigestInit(&md, evp_md);
525
526	len = BN_num_bytes(host_modulus);
527	if (len < (512 / 8) || (u_int)len > sizeof(nbuf))
528		fatal("%s: bad host modulus (len %d)", __func__, len);
529	BN_bn2bin(host_modulus, nbuf);
530	EVP_DigestUpdate(&md, nbuf, len);
531
532	len = BN_num_bytes(server_modulus);
533	if (len < (512 / 8) || (u_int)len > sizeof(nbuf))
534		fatal("%s: bad server modulus (len %d)", __func__, len);
535	BN_bn2bin(server_modulus, nbuf);
536	EVP_DigestUpdate(&md, nbuf, len);
537
538	EVP_DigestUpdate(&md, cookie, 8);
539
540	EVP_DigestFinal(&md, obuf, NULL);
541	memcpy(id, obuf, 16);
542
543	memset(nbuf, 0, sizeof(nbuf));
544	memset(obuf, 0, sizeof(obuf));
545	memset(&md, 0, sizeof(md));
546}
547
548#if defined(DEBUG_KEX) || defined(DEBUG_KEXDH)
549void
550dump_digest(char *msg, u_char *digest, int len)
551{
552	u_int i;
553
554	fprintf(stderr, "%s\n", msg);
555	for (i = 0; i< len; i++) {
556		fprintf(stderr, "%02x", digest[i]);
557		if (i%32 == 31)
558			fprintf(stderr, "\n");
559		else if (i%8 == 7)
560			fprintf(stderr, " ");
561	}
562	fprintf(stderr, "\n");
563}
564#endif
565