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