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