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