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