kex.c

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