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