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  *
  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"
  26 RCSID("$OpenBSD: kex.c,v 1.10 2000/09/07 20:27:51 deraadt 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 "cipher.h"
  35 #include "compat.h"
  36
  37 #include <openssl/bn.h>
  38 #include <openssl/dh.h>
  39
  40 #include <openssl/crypto.h>
  41 #include <openssl/bio.h>
  42 #include <openssl/bn.h>
  43 #include <openssl/dh.h>
  44 #include <openssl/pem.h>
  45
  46 #include "kex.h"
  47
  48 #define KEX_COOKIE_LEN  16
  49
  50 Buffer *
  51 kex_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 */
  74 void
  75 kex_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
 119 int
 120 dh_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         /* we only accept g==2 */
 127         if (!BN_is_word(dh->g, 2)) {
 128                 log("invalid DH base != 2");
 129                 return 0;
 130         }
 131         if (dh_pub->neg) {
 132                 log("invalid public DH value: negativ");
 133                 return 0;
 134         }
 135         for (i = 0; i <= n; i++)
 136                 if (BN_is_bit_set(dh_pub, i))
 137                         bits_set++;
 138         debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 139
 140         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 141         if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
 142                 return 1;
 143         log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 144         return 0;
 145 }
 146
 147 DH *
 148 dh_new_group1()
 149 {
 150         static char *group1 =
 151             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 152             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 153             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 154             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 155             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 156             "FFFFFFFF" "FFFFFFFF";
 157         DH *dh;
 158         int ret, tries = 0;
 159         dh = DH_new();
 160         if(dh == NULL)
 161                 fatal("DH_new");
 162         ret = BN_hex2bn(&dh->p, group1);
 163         if(ret<0)
 164                 fatal("BN_hex2bn");
 165         dh->g = BN_new();
 166         if(dh->g == NULL)
 167                 fatal("DH_new g");
 168         BN_set_word(dh->g, 2);
 169         do {
 170                 if (DH_generate_key(dh) == 0)
 171                         fatal("DH_generate_key");
 172                 if (tries++ > 10)
 173                         fatal("dh_new_group1: too many bad keys: giving up");
 174         } while (!dh_pub_is_valid(dh, dh->pub_key));
 175         return dh;
 176 }
 177
 178 void
 179 dump_digest(unsigned char *digest, int len)
 180 {
 181         int i;
 182         for (i = 0; i< len; i++){
 183                 fprintf(stderr, "%02x", digest[i]);
 184                 if(i%2!=0)
 185                         fprintf(stderr, " ");
 186         }
 187         fprintf(stderr, "\n");
 188 }
 189
 190 unsigned char *
 191 kex_hash(
 192     char *client_version_string,
 193     char *server_version_string,
 194     char *ckexinit, int ckexinitlen,
 195     char *skexinit, int skexinitlen,
 196     char *serverhostkeyblob, int sbloblen,
 197     BIGNUM *client_dh_pub,
 198     BIGNUM *server_dh_pub,
 199     BIGNUM *shared_secret)
 200 {
 201         Buffer b;
 202         static unsigned char digest[EVP_MAX_MD_SIZE];
 203         EVP_MD *evp_md = EVP_sha1();
 204         EVP_MD_CTX md;
 205
 206         buffer_init(&b);
 207         buffer_put_string(&b, client_version_string, strlen(client_version_string));
 208         buffer_put_string(&b, server_version_string, strlen(server_version_string));
 209
 210         /* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */
 211         buffer_put_int(&b, ckexinitlen+1);
 212         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 213         buffer_append(&b, ckexinit, ckexinitlen);
 214         buffer_put_int(&b, skexinitlen+1);
 215         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 216         buffer_append(&b, skexinit, skexinitlen);
 217
 218         buffer_put_string(&b, serverhostkeyblob, sbloblen);
 219         buffer_put_bignum2(&b, client_dh_pub);
 220         buffer_put_bignum2(&b, server_dh_pub);
 221         buffer_put_bignum2(&b, shared_secret);
 222
 223 #ifdef DEBUG_KEX
 224         buffer_dump(&b);
 225 #endif
 226
 227         EVP_DigestInit(&md, evp_md);
 228         EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
 229         EVP_DigestFinal(&md, digest, NULL);
 230
 231         buffer_free(&b);
 232
 233 #ifdef DEBUG_KEX
 234         dump_digest(digest, evp_md->md_size);
 235 #endif
 236         return digest;
 237 }
 238
 239 unsigned char *
 240 derive_key(int id, int need, char unsigned *hash, BIGNUM *shared_secret)
 241 {
 242         Buffer b;
 243         EVP_MD *evp_md = EVP_sha1();
 244         EVP_MD_CTX md;
 245         char c = id;
 246         int have;
 247         int mdsz = evp_md->md_size;
 248         unsigned char *digest = xmalloc(((need+mdsz-1)/mdsz)*mdsz);
 249
 250         buffer_init(&b);
 251         buffer_put_bignum2(&b, shared_secret);
 252
 253         EVP_DigestInit(&md, evp_md);
 254         EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));  /* shared_secret K */
 255         EVP_DigestUpdate(&md, hash, mdsz);              /* transport-06 */
 256         EVP_DigestUpdate(&md, &c, 1);                   /* key id */
 257         EVP_DigestUpdate(&md, hash, mdsz);              /* session id */
 258         EVP_DigestFinal(&md, digest, NULL);
 259
 260         /* expand */
 261         for (have = mdsz; need > have; have += mdsz) {
 262                 EVP_DigestInit(&md, evp_md);
 263                 EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
 264                 EVP_DigestUpdate(&md, hash, mdsz);
 265                 EVP_DigestUpdate(&md, digest, have);
 266                 EVP_DigestFinal(&md, digest + have, NULL);
 267         }
 268         buffer_free(&b);
 269 #ifdef DEBUG_KEX
 270         fprintf(stderr, "Digest '%c'== ", c);
 271         dump_digest(digest, need);
 272 #endif
 273         return digest;
 274 }
 275
 276 #define NKEYS   6
 277
 278 #define MAX_PROP        20
 279 #define SEP     ","
 280
 281 char *
 282 get_match(char *client, char *server)
 283 {
 284         char *sproposals[MAX_PROP];
 285         char *c, *s, *p, *ret, *cp, *sp;
 286         int i, j, nproposals;
 287
 288         c = cp = xstrdup(client);
 289         s = sp = xstrdup(server);
 290
 291         for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0';
 292              (p = strsep(&sp, SEP)), i++) {
 293                 if (i < MAX_PROP)
 294                         sproposals[i] = p;
 295                 else
 296                         break;
 297         }
 298         nproposals = i;
 299
 300         for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0';
 301              (p = strsep(&cp, SEP)), i++) {
 302                 for (j = 0; j < nproposals; j++) {
 303                         if (strcmp(p, sproposals[j]) == 0) {
 304                                 ret = xstrdup(p);
 305                                 xfree(c);
 306                                 xfree(s);
 307                                 return ret;
 308                         }
 309                 }
 310         }
 311         xfree(c);
 312         xfree(s);
 313         return NULL;
 314 }
 315 void
 316 choose_enc(Enc *enc, char *client, char *server)
 317 {
 318         char *name = get_match(client, server);
 319         if (name == NULL)
 320                 fatal("no matching cipher found: client %s server %s", client, server);
 321         enc->type = cipher_number(name);
 322
 323         switch (enc->type) {
 324         case SSH_CIPHER_3DES_CBC:
 325                 enc->key_len = 24;
 326                 enc->iv_len = 8;
 327                 enc->block_size = 8;
 328                 break;
 329         case SSH_CIPHER_BLOWFISH_CBC:
 330         case SSH_CIPHER_CAST128_CBC:
 331                 enc->key_len = 16;
 332                 enc->iv_len = 8;
 333                 enc->block_size = 8;
 334                 break;
 335         case SSH_CIPHER_ARCFOUR:
 336                 enc->key_len = 16;
 337                 enc->iv_len = 0;
 338                 enc->block_size = 8;
 339                 break;
 340         default:
 341                 fatal("unsupported cipher %s", name);
 342         }
 343         enc->name = name;
 344         enc->enabled = 0;
 345         enc->iv = NULL;
 346         enc->key = NULL;
 347 }
 348 void
 349 choose_mac(Mac *mac, char *client, char *server)
 350 {
 351         char *name = get_match(client, server);
 352         if (name == NULL)
 353                 fatal("no matching mac found: client %s server %s", client, server);
 354         if (strcmp(name, "hmac-md5") == 0) {
 355                 mac->md = EVP_md5();
 356         } else if (strcmp(name, "hmac-sha1") == 0) {
 357                 mac->md = EVP_sha1();
 358         } else if (strcmp(name, "hmac-ripemd160@openssh.com") == 0) {
 359                 mac->md = EVP_ripemd160();
 360         } else {
 361                 fatal("unsupported mac %s", name);
 362         }
 363         mac->name = name;
 364         mac->mac_len = mac->md->md_size;
 365         mac->key_len = (datafellows & SSH_BUG_HMAC) ? 16 : mac->mac_len;
 366         mac->key = NULL;
 367         mac->enabled = 0;
 368 }
 369 void
 370 choose_comp(Comp *comp, char *client, char *server)
 371 {
 372         char *name = get_match(client, server);
 373         if (name == NULL)
 374                 fatal("no matching comp found: client %s server %s", client, server);
 375         if (strcmp(name, "zlib") == 0) {
 376                 comp->type = 1;
 377         } else if (strcmp(name, "none") == 0) {
 378                 comp->type = 0;
 379         } else {
 380                 fatal("unsupported comp %s", name);
 381         }
 382         comp->name = name;
 383 }
 384 void
 385 choose_kex(Kex *k, char *client, char *server)
 386 {
 387         k->name = get_match(client, server);
 388         if (k->name == NULL)
 389                 fatal("no kex alg");
 390         if (strcmp(k->name, KEX_DH1) != 0)
 391                 fatal("bad kex alg %s", k->name);
 392 }
 393 void
 394 choose_hostkeyalg(Kex *k, char *client, char *server)
 395 {
 396         k->hostkeyalg = get_match(client, server);
 397         if (k->hostkeyalg == NULL)
 398                 fatal("no hostkey alg");
 399         if (strcmp(k->hostkeyalg, KEX_DSS) != 0)
 400                 fatal("bad hostkey alg %s", k->hostkeyalg);
 401 }
 402
 403 Kex *
 404 kex_choose_conf(char *cprop[PROPOSAL_MAX], char *sprop[PROPOSAL_MAX], int server)
 405 {
 406         int mode;
 407         int ctos;                               /* direction: if true client-to-server */
 408         int need;
 409         Kex *k;
 410
 411         k = xmalloc(sizeof(*k));
 412         memset(k, 0, sizeof(*k));
 413         k->server = server;
 414
 415         for (mode = 0; mode < MODE_MAX; mode++) {
 416                 int nenc, nmac, ncomp;
 417                 ctos = (!k->server && mode == MODE_OUT) || (k->server && mode == MODE_IN);
 418                 nenc  = ctos ? PROPOSAL_ENC_ALGS_CTOS  : PROPOSAL_ENC_ALGS_STOC;
 419                 nmac  = ctos ? PROPOSAL_MAC_ALGS_CTOS  : PROPOSAL_MAC_ALGS_STOC;
 420                 ncomp = ctos ? PROPOSAL_COMP_ALGS_CTOS : PROPOSAL_COMP_ALGS_STOC;
 421                 choose_enc (&k->enc [mode], cprop[nenc],  sprop[nenc]);
 422                 choose_mac (&k->mac [mode], cprop[nmac],  sprop[nmac]);
 423                 choose_comp(&k->comp[mode], cprop[ncomp], sprop[ncomp]);
 424                 debug("kex: %s %s %s %s",
 425                     ctos ? "client->server" : "server->client",
 426                     k->enc[mode].name,
 427                     k->mac[mode].name,
 428                     k->comp[mode].name);
 429         }
 430         choose_kex(k, cprop[PROPOSAL_KEX_ALGS], sprop[PROPOSAL_KEX_ALGS]);
 431         choose_hostkeyalg(k, cprop[PROPOSAL_SERVER_HOST_KEY_ALGS],
 432             sprop[PROPOSAL_SERVER_HOST_KEY_ALGS]);
 433         need = 0;
 434         for (mode = 0; mode < MODE_MAX; mode++) {
 435             if (need < k->enc[mode].key_len)
 436                     need = k->enc[mode].key_len;
 437             if (need < k->enc[mode].iv_len)
 438                     need = k->enc[mode].iv_len;
 439             if (need < k->mac[mode].key_len)
 440                     need = k->mac[mode].key_len;
 441         }
 442         /* XXX need runden? */
 443         k->we_need = need;
 444         return k;
 445 }
 446
 447 int
 448 kex_derive_keys(Kex *k, unsigned char *hash, BIGNUM *shared_secret)
 449 {
 450         int i;
 451         int mode;
 452         int ctos;
 453         unsigned char *keys[NKEYS];
 454
 455         for (i = 0; i < NKEYS; i++)
 456                 keys[i] = derive_key('A'+i, k->we_need, hash, shared_secret);
 457
 458         for (mode = 0; mode < MODE_MAX; mode++) {
 459                 ctos = (!k->server && mode == MODE_OUT) || (k->server && mode == MODE_IN);
 460                 k->enc[mode].iv  = keys[ctos ? 0 : 1];
 461                 k->enc[mode].key = keys[ctos ? 2 : 3];
 462                 k->mac[mode].key = keys[ctos ? 4 : 5];
 463         }
 464         return 0;
 465 }