Annotation of src/usr.bin/ssh/kex.c, Revision 1.24
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.24 ! provos 26: RCSID("$OpenBSD: kex.c,v 1.23 2001/03/10 17:51:04 markus Exp $");
1.18 markus 27:
28: #include <openssl/crypto.h>
29: #include <openssl/bio.h>
30: #include <openssl/bn.h>
31: #include <openssl/dh.h>
32: #include <openssl/pem.h>
1.1 markus 33:
34: #include "ssh2.h"
35: #include "xmalloc.h"
36: #include "buffer.h"
37: #include "bufaux.h"
1.7 markus 38: #include "packet.h"
1.1 markus 39: #include "compat.h"
1.18 markus 40: #include "cipher.h"
1.1 markus 41: #include "kex.h"
1.13 markus 42: #include "key.h"
1.18 markus 43: #include "log.h"
1.21 markus 44: #include "mac.h"
1.23 markus 45: #include "match.h"
1.1 markus 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;
1.15 markus 53: u_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);
1.19 stevesk 84: packet_put_raw(buffer_ptr(my_kexinit), buffer_len(my_kexinit));
1.7 markus 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.14 provos 141: void
1.22 markus 142: dh_gen_key(DH *dh, int need)
1.11 provos 143: {
1.22 markus 144: int i, bits_set = 0, tries = 0;
1.11 provos 145:
1.22 markus 146: if (dh->p == NULL)
147: fatal("dh_gen_key: dh->p == NULL");
148: if (2*need >= BN_num_bits(dh->p))
149: fatal("dh_gen_key: group too small: %d (2*need %d)",
150: BN_num_bits(dh->p), 2*need);
1.11 provos 151: do {
1.22 markus 152: if (dh->priv_key != NULL)
153: BN_free(dh->priv_key);
154: dh->priv_key = BN_new();
155: if (dh->priv_key == NULL)
156: fatal("dh_gen_key: BN_new failed");
157: /* generate a 2*need bits random private exponent */
158: if (!BN_rand(dh->priv_key, 2*need, 0, 0))
159: fatal("dh_gen_key: BN_rand failed");
1.11 provos 160: if (DH_generate_key(dh) == 0)
161: fatal("DH_generate_key");
1.22 markus 162: for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
163: if (BN_is_bit_set(dh->priv_key, i))
164: bits_set++;
165: debug("dh_gen_key: priv key bits set: %d/%d",
166: bits_set, BN_num_bits(dh->priv_key));
1.11 provos 167: if (tries++ > 10)
1.22 markus 168: fatal("dh_gen_key: too many bad keys: giving up");
1.11 provos 169: } while (!dh_pub_is_valid(dh, dh->pub_key));
170: }
171:
172: DH *
173: dh_new_group_asc(const char *gen, const char *modulus)
174: {
175: DH *dh;
176: int ret;
177:
178: dh = DH_new();
179: if (dh == NULL)
180: fatal("DH_new");
181:
182: if ((ret = BN_hex2bn(&dh->p, modulus)) < 0)
183: fatal("BN_hex2bn p");
184: if ((ret = BN_hex2bn(&dh->g, gen)) < 0)
185: fatal("BN_hex2bn g");
186:
1.14 provos 187: return (dh);
1.11 provos 188: }
189:
1.14 provos 190: /*
191: * This just returns the group, we still need to generate the exchange
192: * value.
193: */
194:
1.11 provos 195: DH *
196: dh_new_group(BIGNUM *gen, BIGNUM *modulus)
197: {
198: DH *dh;
199:
200: dh = DH_new();
201: if (dh == NULL)
202: fatal("DH_new");
203: dh->p = modulus;
204: dh->g = gen;
205:
1.14 provos 206: return (dh);
1.11 provos 207: }
208:
209: DH *
1.16 markus 210: dh_new_group1(void)
1.1 markus 211: {
1.11 provos 212: static char *gen = "2", *group1 =
1.1 markus 213: "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
214: "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
215: "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
216: "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
217: "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
218: "FFFFFFFF" "FFFFFFFF";
1.11 provos 219:
220: return (dh_new_group_asc(gen, group1));
1.1 markus 221: }
222:
1.20 itojun 223: #ifdef DEBUG_KEX
1.1 markus 224: void
1.15 markus 225: dump_digest(u_char *digest, int len)
1.1 markus 226: {
227: int i;
1.5 markus 228: for (i = 0; i< len; i++){
229: fprintf(stderr, "%02x", digest[i]);
1.1 markus 230: if(i%2!=0)
231: fprintf(stderr, " ");
232: }
1.5 markus 233: fprintf(stderr, "\n");
1.1 markus 234: }
1.20 itojun 235: #endif
1.1 markus 236:
1.15 markus 237: u_char *
1.1 markus 238: kex_hash(
239: char *client_version_string,
240: char *server_version_string,
241: char *ckexinit, int ckexinitlen,
242: char *skexinit, int skexinitlen,
243: char *serverhostkeyblob, int sbloblen,
244: BIGNUM *client_dh_pub,
245: BIGNUM *server_dh_pub,
246: BIGNUM *shared_secret)
247: {
248: Buffer b;
1.15 markus 249: static u_char digest[EVP_MAX_MD_SIZE];
1.1 markus 250: EVP_MD *evp_md = EVP_sha1();
251: EVP_MD_CTX md;
252:
253: buffer_init(&b);
254: buffer_put_string(&b, client_version_string, strlen(client_version_string));
255: buffer_put_string(&b, server_version_string, strlen(server_version_string));
256:
257: /* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */
258: buffer_put_int(&b, ckexinitlen+1);
259: buffer_put_char(&b, SSH2_MSG_KEXINIT);
260: buffer_append(&b, ckexinit, ckexinitlen);
261: buffer_put_int(&b, skexinitlen+1);
262: buffer_put_char(&b, SSH2_MSG_KEXINIT);
263: buffer_append(&b, skexinit, skexinitlen);
264:
265: buffer_put_string(&b, serverhostkeyblob, sbloblen);
266: buffer_put_bignum2(&b, client_dh_pub);
267: buffer_put_bignum2(&b, server_dh_pub);
268: buffer_put_bignum2(&b, shared_secret);
1.19 stevesk 269:
1.1 markus 270: #ifdef DEBUG_KEX
271: buffer_dump(&b);
272: #endif
273:
274: EVP_DigestInit(&md, evp_md);
275: EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
276: EVP_DigestFinal(&md, digest, NULL);
277:
278: buffer_free(&b);
279:
280: #ifdef DEBUG_KEX
1.5 markus 281: dump_digest(digest, evp_md->md_size);
1.1 markus 282: #endif
283: return digest;
284: }
285:
1.15 markus 286: u_char *
1.11 provos 287: kex_hash_gex(
288: char *client_version_string,
289: char *server_version_string,
290: char *ckexinit, int ckexinitlen,
291: char *skexinit, int skexinitlen,
292: char *serverhostkeyblob, int sbloblen,
1.24 ! provos 293: int min, int wantbits, int max, BIGNUM *prime, BIGNUM *gen,
1.11 provos 294: BIGNUM *client_dh_pub,
295: BIGNUM *server_dh_pub,
296: BIGNUM *shared_secret)
297: {
298: Buffer b;
1.15 markus 299: static u_char digest[EVP_MAX_MD_SIZE];
1.11 provos 300: EVP_MD *evp_md = EVP_sha1();
301: EVP_MD_CTX md;
302:
303: buffer_init(&b);
304: buffer_put_string(&b, client_version_string, strlen(client_version_string));
305: buffer_put_string(&b, server_version_string, strlen(server_version_string));
306:
307: /* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */
308: buffer_put_int(&b, ckexinitlen+1);
309: buffer_put_char(&b, SSH2_MSG_KEXINIT);
310: buffer_append(&b, ckexinit, ckexinitlen);
311: buffer_put_int(&b, skexinitlen+1);
312: buffer_put_char(&b, SSH2_MSG_KEXINIT);
313: buffer_append(&b, skexinit, skexinitlen);
314:
315: buffer_put_string(&b, serverhostkeyblob, sbloblen);
1.24 ! provos 316: if (min == -1 || max == -1)
! 317: buffer_put_int(&b, wantbits);
! 318: else {
! 319: buffer_put_int(&b, min);
! 320: buffer_put_int(&b, wantbits);
! 321: buffer_put_int(&b, max);
! 322: }
1.11 provos 323: buffer_put_bignum2(&b, prime);
324: buffer_put_bignum2(&b, gen);
325: buffer_put_bignum2(&b, client_dh_pub);
326: buffer_put_bignum2(&b, server_dh_pub);
327: buffer_put_bignum2(&b, shared_secret);
1.19 stevesk 328:
1.11 provos 329: #ifdef DEBUG_KEX
330: buffer_dump(&b);
331: #endif
332:
333: EVP_DigestInit(&md, evp_md);
334: EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
335: EVP_DigestFinal(&md, digest, NULL);
336:
337: buffer_free(&b);
338:
339: #ifdef DEBUG_KEX
340: dump_digest(digest, evp_md->md_size);
341: #endif
342: return digest;
343: }
344:
1.15 markus 345: u_char *
346: derive_key(int id, int need, u_char *hash, BIGNUM *shared_secret)
1.1 markus 347: {
348: Buffer b;
349: EVP_MD *evp_md = EVP_sha1();
350: EVP_MD_CTX md;
351: char c = id;
352: int have;
353: int mdsz = evp_md->md_size;
1.15 markus 354: u_char *digest = xmalloc(((need+mdsz-1)/mdsz)*mdsz);
1.1 markus 355:
356: buffer_init(&b);
357: buffer_put_bignum2(&b, shared_secret);
358:
359: EVP_DigestInit(&md, evp_md);
360: EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b)); /* shared_secret K */
361: EVP_DigestUpdate(&md, hash, mdsz); /* transport-06 */
362: EVP_DigestUpdate(&md, &c, 1); /* key id */
363: EVP_DigestUpdate(&md, hash, mdsz); /* session id */
364: EVP_DigestFinal(&md, digest, NULL);
365:
366: /* expand */
367: for (have = mdsz; need > have; have += mdsz) {
368: EVP_DigestInit(&md, evp_md);
369: EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
370: EVP_DigestUpdate(&md, hash, mdsz);
371: EVP_DigestUpdate(&md, digest, have);
372: EVP_DigestFinal(&md, digest + have, NULL);
373: }
374: buffer_free(&b);
375: #ifdef DEBUG_KEX
376: fprintf(stderr, "Digest '%c'== ", c);
377: dump_digest(digest, need);
378: #endif
379: return digest;
380: }
381:
382: void
383: choose_enc(Enc *enc, char *client, char *server)
384: {
1.23 markus 385: char *name = match_list(client, server, NULL);
1.1 markus 386: if (name == NULL)
387: fatal("no matching cipher found: client %s server %s", client, server);
1.12 markus 388: enc->cipher = cipher_by_name(name);
389: if (enc->cipher == NULL)
390: fatal("matching cipher is not supported: %s", name);
1.1 markus 391: enc->name = name;
392: enc->enabled = 0;
393: enc->iv = NULL;
394: enc->key = NULL;
395: }
396: void
397: choose_mac(Mac *mac, char *client, char *server)
398: {
1.23 markus 399: char *name = match_list(client, server, NULL);
1.1 markus 400: if (name == NULL)
401: fatal("no matching mac found: client %s server %s", client, server);
1.21 markus 402: if (mac_init(mac, name) < 0)
1.1 markus 403: fatal("unsupported mac %s", name);
1.21 markus 404: /* truncate the key */
405: if (datafellows & SSH_BUG_HMAC)
406: mac->key_len = 16;
1.1 markus 407: mac->name = name;
408: mac->key = NULL;
409: mac->enabled = 0;
410: }
411: void
412: choose_comp(Comp *comp, char *client, char *server)
413: {
1.23 markus 414: char *name = match_list(client, server, NULL);
1.1 markus 415: if (name == NULL)
416: fatal("no matching comp found: client %s server %s", client, server);
417: if (strcmp(name, "zlib") == 0) {
418: comp->type = 1;
419: } else if (strcmp(name, "none") == 0) {
420: comp->type = 0;
421: } else {
422: fatal("unsupported comp %s", name);
423: }
424: comp->name = name;
425: }
426: void
427: choose_kex(Kex *k, char *client, char *server)
428: {
1.23 markus 429: k->name = match_list(client, server, NULL);
1.1 markus 430: if (k->name == NULL)
431: fatal("no kex alg");
1.11 provos 432: if (strcmp(k->name, KEX_DH1) == 0) {
433: k->kex_type = DH_GRP1_SHA1;
434: } else if (strcmp(k->name, KEX_DHGEX) == 0) {
435: k->kex_type = DH_GEX_SHA1;
436: } else
1.1 markus 437: fatal("bad kex alg %s", k->name);
438: }
439: void
440: choose_hostkeyalg(Kex *k, char *client, char *server)
441: {
1.23 markus 442: char *hostkeyalg = match_list(client, server, NULL);
1.13 markus 443: if (hostkeyalg == NULL)
1.1 markus 444: fatal("no hostkey alg");
1.13 markus 445: k->hostkey_type = key_type_from_name(hostkeyalg);
446: if (k->hostkey_type == KEY_UNSPEC)
447: fatal("bad hostkey alg '%s'", hostkeyalg);
1.17 markus 448: xfree(hostkeyalg);
1.1 markus 449: }
450:
451: Kex *
452: kex_choose_conf(char *cprop[PROPOSAL_MAX], char *sprop[PROPOSAL_MAX], int server)
453: {
454: int mode;
455: int ctos; /* direction: if true client-to-server */
456: int need;
457: Kex *k;
458:
459: k = xmalloc(sizeof(*k));
460: memset(k, 0, sizeof(*k));
461: k->server = server;
462:
463: for (mode = 0; mode < MODE_MAX; mode++) {
464: int nenc, nmac, ncomp;
465: ctos = (!k->server && mode == MODE_OUT) || (k->server && mode == MODE_IN);
466: nenc = ctos ? PROPOSAL_ENC_ALGS_CTOS : PROPOSAL_ENC_ALGS_STOC;
467: nmac = ctos ? PROPOSAL_MAC_ALGS_CTOS : PROPOSAL_MAC_ALGS_STOC;
468: ncomp = ctos ? PROPOSAL_COMP_ALGS_CTOS : PROPOSAL_COMP_ALGS_STOC;
469: choose_enc (&k->enc [mode], cprop[nenc], sprop[nenc]);
470: choose_mac (&k->mac [mode], cprop[nmac], sprop[nmac]);
471: choose_comp(&k->comp[mode], cprop[ncomp], sprop[ncomp]);
1.2 markus 472: debug("kex: %s %s %s %s",
1.1 markus 473: ctos ? "client->server" : "server->client",
474: k->enc[mode].name,
475: k->mac[mode].name,
476: k->comp[mode].name);
477: }
478: choose_kex(k, cprop[PROPOSAL_KEX_ALGS], sprop[PROPOSAL_KEX_ALGS]);
479: choose_hostkeyalg(k, cprop[PROPOSAL_SERVER_HOST_KEY_ALGS],
480: sprop[PROPOSAL_SERVER_HOST_KEY_ALGS]);
481: need = 0;
482: for (mode = 0; mode < MODE_MAX; mode++) {
1.12 markus 483: if (need < k->enc[mode].cipher->key_len)
484: need = k->enc[mode].cipher->key_len;
485: if (need < k->enc[mode].cipher->block_size)
486: need = k->enc[mode].cipher->block_size;
1.1 markus 487: if (need < k->mac[mode].key_len)
488: need = k->mac[mode].key_len;
489: }
1.7 markus 490: /* XXX need runden? */
1.1 markus 491: k->we_need = need;
492: return k;
493: }
494:
1.23 markus 495: #define NKEYS 6
1.1 markus 496: int
1.15 markus 497: kex_derive_keys(Kex *k, u_char *hash, BIGNUM *shared_secret)
1.1 markus 498: {
499: int i;
500: int mode;
501: int ctos;
1.15 markus 502: u_char *keys[NKEYS];
1.1 markus 503:
504: for (i = 0; i < NKEYS; i++)
505: keys[i] = derive_key('A'+i, k->we_need, hash, shared_secret);
506:
507: for (mode = 0; mode < MODE_MAX; mode++) {
508: ctos = (!k->server && mode == MODE_OUT) || (k->server && mode == MODE_IN);
509: k->enc[mode].iv = keys[ctos ? 0 : 1];
510: k->enc[mode].key = keys[ctos ? 2 : 3];
511: k->mac[mode].key = keys[ctos ? 4 : 5];
512: }
513: return 0;
514: }