chiark - git - mdw - tripe/blob - keyexch.c

   1 /* -*-c-*-
   2  *
   3  * $Id: keyexch.c,v 1.12 2004/04/08 01:36:17 mdw Exp $
   4  *
   5  * Key exchange protocol
   6  *
   7  * (c) 2001 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Trivial IP Encryption (TrIPE).
  13  *
  14  * TrIPE is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU General Public License as published by
  16  * the Free Software Foundation; either version 2 of the License, or
  17  * (at your option) any later version.
  18  *
  19  * TrIPE is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU General Public License
  25  * along with TrIPE; if not, write to the Free Software Foundation,
  26  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  27  */
  28
  29 /*----- Header files ------------------------------------------------------*/
  30
  31 #include "tripe.h"
  32
  33 /*----- Brief protocol overview -------------------------------------------*
  34  *
  35  * Let %$G$% be a cyclic group; let %$g$% be a generator of %$G$%, and let
  36  * %$q$% be the order of %$G$%; for a key %$K$%, let %$E_K(\cdot)$% denote
  37  * application of the symmetric packet protocol to a message; let
  38  * %$H(\cdot)$% be the random oracle.  Let $\alpha \inr \{0,\ldots,q - 1\}$%
  39  * be Alice's private key; let %$a = g^\alpha$% be her public key; let %$b$%
  40  * be Bob's public key.
  41  *
  42  * At the beginning of the session, Alice chooses
  43  *
  44  *   %$\rho_A \inr \{0, \ldots q - 1\}$%
  45  *
  46  * We also have:
  47  *
  48  * %$r_A = g^{\rho_A}$%                 Alice's challenge
  49  * %$c_A = H(\cookie{cookie}, r_A)$%    Alice's cookie
  50  * %$v_A = \rho_A \xor H(\cookie{expected-reply}, r_A, r_B, b^{\rho_A})$%
  51  *                                      Alice's challenge check value
  52  * %$r_B^\alpha = a^{\rho_B}$%          Alice's reply
  53  * %$K = r_B^{\rho_A} = r_B^{\rho_A} = g^{\rho_A\rho_B}$%
  54  *                                      Alice and Bob's shared secret key
  55  * %$w_A = H(\cookie{switch-request}, c_A, c_B)$%
  56  *                                      Alice's switch request value
  57  * %$u_A = H(\cookie{switch-confirm}, c_A, c_B)$%
  58  *                                      Alice's switch confirm value
  59  *
  60  * The messages are then:
  61  *
  62  * %$\cookie{kx-pre-challenge}, r_A$%
  63  *      Initial greeting.  In state @KXS_CHAL@.
  64  *
  65  * %$\cookie{kx-cookie}, r_A, c_B$%
  66  *      My table is full but I got your message.
  67  *
  68  * %$\cookie{kx-challenge}, r_A, c_B, v_A$%
  69  *      Here's a full challenge for you to answer.
  70  *
  71  * %$\cookie{kx-reply}, c_A, c_B, v_A, E_K(r_B^\alpha))$%
  72  *      Challenge accpeted: here's the answer.  Commit to my challenge.  Move
  73  *      to @KXS_COMMIT@.
  74  *
  75  * %$\cookie{kx-switch}, c_A, c_B, E_K(r_B^\alpha, w_A))$%
  76  *      Reply received: here's my reply.  Committed; send data; move to
  77  *      @KXS_SWITCH@.
  78  *
  79  * %$\cookie{kx-switch-ok}, E_K(u_A))$%
  80  *      Switch received.  Committed; send data; move to @KXS_SWITCH@.
  81  */
  82
  83 /*----- Tunable parameters ------------------------------------------------*/
  84
  85 #define T_VALID MIN(2)                  /* Challenge validity period */
  86 #define T_RETRY SEC(10)                 /* Challenge retransmit interval */
  87
  88 #define ISVALID(kx, now) ((now) < (kx)->t_valid)
  89
  90 /*----- Various utilities -------------------------------------------------*/
  91
  92 /* --- @hashge@ --- *
  93  *
  94  * Arguments:   @HASH_CTX *r@ = pointer to hash context
  95  *              @ge *x@ = pointer to group element
  96  *
  97  * Returns:     ---
  98  *
  99  * Use:         Adds the hash of a group element to the context.  Corrupts
 100  *              @buf_t@.
 101  */
 102
 103 static void hashge(HASH_CTX *r, ge *x)
 104 {
 105   buf b;
 106   buf_init(&b, buf_t, sizeof(buf_t));
 107   G_TOBUF(gg, &b, x);
 108   assert(BOK(&b));
 109   HASH(r, BBASE(&b), BLEN(&b));
 110 }
 111
 112 /* --- @mpcrypt@ --- *
 113  *
 114  * Arguments:   @mp *d@ = the destination integer
 115  *              @mp *x@ = the plaintext/ciphertext integer
 116  *              @size_t sz@ = the expected size of the plaintext
 117  *              @const octet *k@ = pointer to key material
 118  *              @size_t ksz@ = size of the key
 119  *
 120  * Returns:     The encrypted/decrypted integer.
 121  *
 122  * Use:         Encrypts (or decrypts) a multiprecision integer.  In fact,
 123  *              the title is a bit of a misnomer: we actually compute
 124  *              %$x \xor H(k)$%, so it's a random oracle thing rather than an
 125  *              encryption thing.
 126  */
 127
 128 static mp *mpcrypt(mp *d, mp *x, size_t sz, const octet *k, size_t ksz)
 129 {
 130   MGF_CTX m;
 131
 132   MGF_INIT(&m, k, ksz, 0);
 133   mp_storeb(x, buf_t, sz);
 134   MGF_CRYPT(&m, buf_t, buf_t, sz);
 135   return (mp_loadb(d, buf_t, sz));
 136 }
 137
 138 /* --- @timer@ --- *
 139  *
 140  * Arguments:   @struct timeval *tv@ = the current time
 141  *              @void *v@ = pointer to key exchange context
 142  *
 143  * Returns:     ---
 144  *
 145  * Use:         Acts when the key exchange timer goes off.
 146  */
 147
 148 static void timer(struct timeval *tv, void *v)
 149 {
 150   keyexch *kx = v;
 151   kx->f &= ~KXF_TIMER;
 152   T( trace(T_KEYEXCH, "keyexch: timer has popped"); )
 153   kx_start(kx);
 154 }
 155
 156 /* --- @settimer@ --- *
 157  *
 158  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 159  *              @time_t t@ = when to set the timer for
 160  *
 161  * Returns:     ---
 162  *
 163  * Use:         Sets the timer for the next key exchange attempt.
 164  */
 165
 166 static void settimer(keyexch *kx, time_t t)
 167 {
 168   struct timeval tv;
 169   if (kx->f & KXF_TIMER)
 170     sel_rmtimer(&kx->t);
 171   tv.tv_sec = t;
 172   tv.tv_usec = 0;
 173   sel_addtimer(&sel, &kx->t, &tv, timer, kx);
 174   kx->f |= KXF_TIMER;
 175 }
 176
 177 /*----- Challenge management ----------------------------------------------*/
 178
 179 /* --- Notes on challenge management --- *
 180  *
 181  * We may get multiple different replies to our key exchange; some will be
 182  * correct, some inserted by attackers.  Up until @KX_THRESH@, all challenges
 183  * received will be added to the table and given a full response.  After
 184  * @KX_THRESH@ distinct challenges are received, we return only a `cookie':
 185  * our existing challenge, followed by a hash of the sender's challenge.  We
 186  * do %%\emph{not}%% give a bare challenge a reply slot at this stage.  All
 187  * properly-formed cookies are assigned a table slot: if none is spare, a
 188  * used slot is randomly selected and destroyed.  A cookie always receives a
 189  * full reply.
 190  */
 191
 192 /* --- @kxc_destroy@ --- *
 193  *
 194  * Arguments:   @kxchal *kxc@ = pointer to the challenge block
 195  *
 196  * Returns:     ---
 197  *
 198  * Use:         Disposes of a challenge block.
 199  */
 200
 201 static void kxc_destroy(kxchal *kxc)
 202 {
 203   if (kxc->f & KXF_TIMER)
 204     sel_rmtimer(&kxc->t);
 205   G_DESTROY(gg, kxc->c);
 206   if (kxc->r) G_DESTROY(gg, kxc->r);
 207   mp_drop(kxc->ck);
 208   ks_drop(kxc->ks);
 209   DESTROY(kxc);
 210 }
 211
 212 /* --- @kxc_stoptimer@ --- *
 213  *
 214  * Arguments:   @kxchal *kxc@ = pointer to the challenge block
 215  *
 216  * Returns:     ---
 217  *
 218  * Use:         Stops the challenge's retry timer from sending messages.
 219  *              Useful when the state machine is in the endgame of the
 220  *              exchange.
 221  */
 222
 223 static void kxc_stoptimer(kxchal *kxc)
 224 {
 225   if (kxc->f & KXF_TIMER)
 226     sel_rmtimer(&kxc->t);
 227   kxc->f &= ~KXF_TIMER;
 228 }
 229
 230 /* --- @kxc_new@ --- *
 231  *
 232  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 233  *
 234  * Returns:     A pointer to the challenge block.
 235  *
 236  * Use:         Returns a pointer to a new challenge block to fill in.
 237  */
 238
 239 static kxchal *kxc_new(keyexch *kx)
 240 {
 241   kxchal *kxc;
 242   unsigned i;
 243
 244   /* --- If we're over reply threshold, discard one at random --- */
 245
 246   if (kx->nr < KX_NCHAL)
 247     i = kx->nr++;
 248   else {
 249     i = rand_global.ops->range(&rand_global, KX_NCHAL);
 250     kxc_destroy(kx->r[i]);
 251   }
 252
 253   /* --- Fill in the new structure --- */
 254
 255   kxc = CREATE(kxchal);
 256   kxc->c = G_CREATE(gg);
 257   kxc->r = 0;
 258   kxc->ck = MP_NEW;
 259   kxc->ks = 0;
 260   kxc->kx = kx;
 261   kxc->f = 0;
 262   kx->r[i] = kxc;
 263   return (kxc);
 264 }
 265
 266 /* --- @kxc_bychal@ --- *
 267  *
 268  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 269  *              @ge *c@ = challenge from remote host
 270  *
 271  * Returns:     Pointer to the challenge block, or null.
 272  *
 273  * Use:         Finds a challenge block, given its challenge.
 274  */
 275
 276 static kxchal *kxc_bychal(keyexch *kx, ge *c)
 277 {
 278   unsigned i;
 279
 280   for (i = 0; i < kx->nr; i++) {
 281     if (G_EQ(gg, c, kx->r[i]->c))
 282       return (kx->r[i]);
 283   }
 284   return (0);
 285 }
 286
 287 /* --- @kxc_byhc@ --- *
 288  *
 289  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 290  *              @const octet *hc@ = challenge hash from remote host
 291  *
 292  * Returns:     Pointer to the challenge block, or null.
 293  *
 294  * Use:         Finds a challenge block, given a hash of its challenge.
 295  */
 296
 297 static kxchal *kxc_byhc(keyexch *kx, const octet *hc)
 298 {
 299   unsigned i;
 300
 301   for (i = 0; i < kx->nr; i++) {
 302     if (memcmp(hc, kx->r[i]->hc, HASHSZ) == 0)
 303       return (kx->r[i]);
 304   }
 305   return (0);
 306 }
 307
 308 /* --- @kxc_answer@ --- *
 309  *
 310  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 311  *              @kxchal *kxc@ = pointer to challenge block
 312  *
 313  * Returns:     ---
 314  *
 315  * Use:         Sends a reply to the remote host, according to the data in
 316  *              this challenge block.
 317  */
 318
 319 static void kxc_answer(keyexch *kx, kxchal *kxc);
 320
 321 static void kxc_timer(struct timeval *tv, void *v)
 322 {
 323   kxchal *kxc = v;
 324   kxc->f &= ~KXF_TIMER;
 325   kxc_answer(kxc->kx, kxc);
 326 }
 327
 328 static void kxc_answer(keyexch *kx, kxchal *kxc)
 329 {
 330   stats *st = p_stats(kx->p);
 331   buf *b = p_txstart(kx->p, MSG_KEYEXCH | (kxc->r ? KX_REPLY : KX_CHAL));
 332   struct timeval tv;
 333   buf bb;
 334
 335   /* --- Build the reply packet --- */
 336
 337   if (!kxc->r)
 338     G_TOBUF(gg, b, kx->c);
 339   else
 340     buf_put(b, kx->hc, HASHSZ);
 341   buf_put(b, kxc->hc, HASHSZ);
 342   buf_putmp(b, kxc->ck);
 343
 344   /* --- Maybe send an actual reply, if we have one --- */
 345
 346   if (!kxc->r) {
 347     T( trace(T_KEYEXCH, "keyexch: resending challenge to `%s'",
 348              p_name(kx->p)); )
 349   } else {
 350     T( trace(T_KEYEXCH, "keyexch: sending reply to `%s'", p_name(kx->p)); )
 351     buf_init(&bb, buf_i, sizeof(buf_i));
 352     G_TOBUF(gg, &bb, kxc->r);
 353     buf_flip(&bb);
 354     ks_encrypt(kxc->ks, MSG_KEYEXCH | KX_REPLY, &bb, b);
 355   }
 356
 357   /* --- Update the statistics --- */
 358
 359   if (BOK(b)) {
 360     st->n_kxout++;
 361     st->sz_kxout += BLEN(b);
 362     p_txend(kx->p);
 363   }
 364
 365   /* --- Schedule another resend --- */
 366
 367   if (kxc->f & KXF_TIMER)
 368     sel_rmtimer(&kxc->t);
 369   gettimeofday(&tv, 0);
 370   tv.tv_sec += T_RETRY;
 371   sel_addtimer(&sel, &kxc->t, &tv, kxc_timer, kxc);
 372   kxc->f |= KXF_TIMER;
 373 }
 374
 375 /*----- Individual message handlers ---------------------------------------*/
 376
 377 /* --- @getreply@ --- *
 378  *
 379  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 380  *              @ge *c@ = a challenge
 381  *              @mp *ck@ = the supplied expected-reply check value
 382  *
 383  * Returns:     A pointer to the reply, or null if the reply-hash was wrong.
 384  *
 385  * Use:         Computes replies to challenges.
 386  */
 387
 388 static ge *getreply(keyexch *kx, ge *c, mp *ck)
 389 {
 390   ge *r = G_CREATE(gg);
 391   ge *y = G_CREATE(gg);
 392   mp *a = MP_NEW;
 393   HASH_CTX h;
 394   octet buf[HASHSZ];
 395   int ok;
 396
 397   G_EXP(gg, r, c, kpriv);
 398   HASH_INIT(&h);
 399   HASH_STRING(&h, "tripe-expected-reply");
 400   hashge(&h, c);
 401   hashge(&h, kx->c);
 402   hashge(&h, r);
 403   HASH_DONE(&h, buf);
 404
 405   a = mpcrypt(MP_NEW, ck, mp_octets(gg->r), buf, sizeof(buf));
 406   IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, {
 407     trace(T_CRYPTO, "crypto: computed reply = %s", gestr(gg, r));
 408     trace_block(T_CRYPTO, "crypto: computed reply hash", buf, HASHSZ);
 409     trace(T_CRYPTO, "crypto: recovered log = %s", mpstr(a));
 410   }))
 411   G_EXP(gg, y, gg->g, a);
 412   ok = G_EQ(gg, y, c);
 413   if (!ok) {
 414     a_warn("invalid expected-reply check from `%s'", p_name(kx->p));
 415     IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, {
 416       trace(T_CRYPTO, "crypto: computed challenge = %s", gestr(gg, y));
 417     }))
 418     G_DESTROY(gg, r);
 419     r = 0;
 420   }
 421   mp_drop(a);
 422   G_DESTROY(gg, y);
 423   return (r);
 424 }
 425
 426 /* --- @dochallenge@ --- *
 427  *
 428  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 429  *              @unsigned msg@ = message code for the packet
 430  *              @buf *b@ = buffer containing the packet
 431  *
 432  * Returns:     Zero if OK, nonzero if the packet was rejected.
 433  *
 434  * Use:         Processes a packet containing a challenge.
 435  */
 436
 437 static int dochallenge(keyexch *kx, unsigned msg, buf *b)
 438 {
 439   ge *c = G_CREATE(gg);
 440   mp *ck = MP_NEW;
 441   const octet *hc = 0;
 442   kxchal *kxc;
 443   HASH_CTX h;
 444   octet buf[HASHSZ];
 445
 446   /* --- Ensure that we're in a sensible state --- */
 447
 448   if (kx->s != KXS_CHAL) {
 449     a_warn("unexpected challenge from `%s'", p_name(kx->p));
 450     goto bad;
 451   }
 452
 453   /* --- Unpack the packet --- */
 454
 455   if (G_FROMBUF(gg, b, c) ||
 456       (msg >= KX_COOKIE && (hc = buf_get(b, HASHSZ)) == 0) ||
 457       (msg >= KX_CHAL && (ck = buf_getmp(b)) == 0) ||
 458       BLEFT(b)) {
 459     a_warn("malformed packet from `%s'", p_name(kx->p));
 460     goto bad;
 461   }
 462
 463   IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, {
 464     trace(T_CRYPTO, "crypto: challenge = %s", gestr(gg, c));
 465     if (hc) trace_block(T_CRYPTO, "crypto: cookie", hc, HASHSZ);
 466     if (ck) trace(T_CRYPTO, "crypto: check value = %s", mpstr(ck));
 467   }))
 468
 469   /* --- First, handle a bare challenge --- *
 470    *
 471    * If the table is heavily loaded, just emit a cookie and return.
 472    */
 473
 474   if (!hc && kx->nr >= KX_THRESH) {
 475     T( trace(T_KEYEXCH, "keyexch: too many challenges -- sending cookie"); )
 476     b = p_txstart(kx->p, MSG_KEYEXCH | KX_COOKIE);
 477     G_TOBUF(gg, b, kx->c);
 478     HASH_INIT(&h);
 479     HASH_STRING(&h, "tripe-cookie");
 480     hashge(&h, c);
 481     HASH_DONE(&h, buf_get(b, HASHSZ));
 482     p_txend(kx->p);
 483     goto tidy;
 484   }
 485
 486   /* --- Discard a packet with an invalid cookie --- */
 487
 488   if (hc && memcmp(hc, kx->hc, HASHSZ) != 0) {
 489     a_warn("incorrect cookie from `%s'", p_name(kx->p));
 490     goto bad;
 491   }
 492
 493   /* --- Find a challenge block for this packet --- *
 494    *
 495    * If there isn't one already, create a new one.
 496    */
 497
 498   if ((kxc = kxc_bychal(kx, c)) == 0) {
 499     size_t x, y, z;
 500     ge *r;
 501
 502     /* --- Be careful here --- *
 503      *
 504      * If this is a full challenge, and it's the first time I've seen it, I
 505      * want to be able to throw it away before committing a table entry to
 506      * it.
 507      */
 508
 509     if (!ck)
 510       kxc = kxc_new(kx);
 511     else {
 512       if ((r = getreply(kx, c, ck)) == 0)
 513         goto bad;
 514       kxc = kxc_new(kx);
 515       kxc->r = r;
 516     }
 517     kxc->c = G_CREATE(gg);
 518     G_COPY(gg, kxc->c, c);
 519
 520     /* --- Work out the cookie for this challenge --- */
 521
 522     HASH_INIT(&h);
 523     HASH_STRING(&h, "tripe-cookie");
 524     hashge(&h, kxc->c);
 525     HASH_DONE(&h, kxc->hc);
 526
 527     /* --- Compute the expected-reply hash --- */
 528
 529     HASH_INIT(&h);
 530     HASH_STRING(&h, "tripe-expected-reply");
 531     hashge(&h, kx->c);
 532     hashge(&h, kxc->c);
 533     hashge(&h, kx->rx);
 534     HASH_DONE(&h, buf);
 535     kxc->ck = mpcrypt(MP_NEW, kx->alpha, mp_octets(gg->r),
 536                       buf, sizeof(buf));
 537
 538     /* --- Work out the shared key --- */
 539
 540     r = G_CREATE(gg);
 541     G_EXP(gg, r, c, kx->alpha);
 542
 543     /* --- Compute the switch messages --- */
 544
 545     HASH_INIT(&h); HASH_STRING(&h, "tripe-switch-request");
 546     hashge(&h, kx->c); hashge(&h, kxc->c);
 547     HASH_DONE(&h, kxc->hswrq_out);
 548     HASH_INIT(&h); HASH_STRING(&h, "tripe-switch-confirm");
 549     hashge(&h, kx->c); hashge(&h, kxc->c);
 550     HASH_DONE(&h, kxc->hswok_out);
 551
 552     HASH_INIT(&h); HASH_STRING(&h, "tripe-switch-request");
 553     hashge(&h, kxc->c); hashge(&h, kx->c);
 554     HASH_DONE(&h, kxc->hswrq_in);
 555     HASH_INIT(&h); HASH_STRING(&h, "tripe-switch-confirm");
 556     hashge(&h, kxc->c); hashge(&h, kx->c);
 557     HASH_DONE(&h, kxc->hswok_in);
 558
 559     IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, {
 560       trace_block(T_CRYPTO, "crypto: computed cookie", kxc->hc, HASHSZ);
 561       trace_block(T_CRYPTO, "crypto: expected-reply hash",
 562                   buf, HASHSZ);
 563       trace(T_CRYPTO, "crypto: my reply check = %s", mpstr(kxc->ck));
 564       trace(T_CRYPTO, "crypto: shared secret = %s", gestr(gg, r));
 565       trace_block(T_CRYPTO, "crypto: outbound switch request",
 566                   kxc->hswrq_out, HASHSZ);
 567       trace_block(T_CRYPTO, "crypto: outbound switch confirm",
 568                   kxc->hswok_out, HASHSZ);
 569       trace_block(T_CRYPTO, "crypto: inbound switch request",
 570                   kxc->hswrq_in, HASHSZ);
 571       trace_block(T_CRYPTO, "crypto: inbound switch confirm",
 572                   kxc->hswok_in, HASHSZ);
 573     }))
 574
 575     /* --- Create a new symmetric keyset --- */
 576
 577     buf_init(b, buf_o, sizeof(buf_o));
 578     G_TOBUF(gg, b, kx->c); x = BLEN(b);
 579     G_TOBUF(gg, b, kxc->c); y = BLEN(b);
 580     G_TOBUF(gg, b, r); z = BLEN(b);
 581     assert(BOK(b));
 582
 583     kxc->ks = ks_gen(BBASE(b), x, y, z, kx->p);
 584     G_DESTROY(gg, r);
 585   }
 586
 587   /* --- Answer the challenge if we need to --- */
 588
 589   if (ck && !kxc->r) {
 590     ge *r;
 591     if ((r = getreply(kx, c, ck)) == 0)
 592       goto bad;
 593     kxc->r = r;
 594   }
 595
 596   kxc_answer(kx, kxc);
 597
 598   /* --- Tidy up and go home --- */
 599
 600 tidy:
 601   G_DESTROY(gg, c);
 602   mp_drop(ck);
 603   return (0);
 604
 605 bad:
 606   G_DESTROY(gg, c);
 607   mp_drop(ck);
 608   return (-1);
 609 }
 610
 611 /* --- @resend@ --- *
 612  *
 613  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 614  *
 615  * Returns:     ---
 616  *
 617  * Use:         Sends the next message for a key exchange.
 618  */
 619
 620 static void resend(keyexch *kx)
 621 {
 622   kxchal *kxc;
 623   buf bb;
 624   stats *st = p_stats(kx->p);
 625   buf *b;
 626
 627   switch (kx->s) {
 628     case KXS_CHAL:
 629       T( trace(T_KEYEXCH, "keyexch: sending prechallenge to `%s'",
 630                p_name(kx->p)); )
 631       b = p_txstart(kx->p, MSG_KEYEXCH | KX_PRECHAL);
 632       G_TOBUF(gg, b, kx->c);
 633       break;
 634     case KXS_COMMIT:
 635       T( trace(T_KEYEXCH, "keyexch: sending switch request to `%s'",
 636                p_name(kx->p)); )
 637       kxc = kx->r[0];
 638       b = p_txstart(kx->p, MSG_KEYEXCH | KX_SWITCH);
 639       buf_put(b, kx->hc, HASHSZ);
 640       buf_put(b, kxc->hc, HASHSZ);
 641       buf_init(&bb, buf_i, sizeof(buf_i));
 642       G_TOBUF(gg, &bb, kxc->r);
 643       buf_put(&bb, kxc->hswrq_out, HASHSZ);
 644       buf_flip(&bb);
 645       ks_encrypt(kxc->ks, MSG_KEYEXCH | KX_SWITCH, &bb, b);
 646       break;
 647     case KXS_SWITCH:
 648       T( trace(T_KEYEXCH, "keyexch: sending switch confirmation to `%s'",
 649                p_name(kx->p)); )
 650       kxc = kx->r[0];
 651       b = p_txstart(kx->p, MSG_KEYEXCH | KX_SWITCHOK);
 652       buf_init(&bb, buf_i, sizeof(buf_i));
 653       buf_put(&bb, kxc->hswok_out, HASHSZ);
 654       buf_flip(&bb);
 655       ks_encrypt(kxc->ks, MSG_KEYEXCH | KX_SWITCHOK, &bb, b);
 656       break;
 657     default:
 658       abort();
 659   }
 660
 661   if (BOK(b)) {
 662     st->n_kxout++;
 663     st->sz_kxout += BLEN(b);
 664     p_txend(kx->p);
 665   }
 666
 667   if (kx->s < KXS_SWITCH)
 668     settimer(kx, time(0) + T_RETRY);
 669 }
 670
 671 /* --- @matchreply@ --- *
 672  *
 673  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 674  *              @unsigned ty@ = type of incoming message
 675  *              @const octet *hc_in@ = a hash of his challenge
 676  *              @const octet *hc_out@ = a hash of my challenge (cookie)
 677  *              @mp *ck@ = his expected-reply hash (optional)
 678  *              @buf *b@ = encrypted remainder of the packet
 679  *
 680  * Returns:     A pointer to the challenge block if OK, or null on failure.
 681  *
 682  * Use:         Checks a reply or switch packet, ensuring that its contents
 683  *              are sensible and correct.  If they are, @*b@ is set to point
 684  *              to the remainder of the encrypted data, and the correct
 685  *              challenge is returned.
 686  */
 687
 688 static kxchal *matchreply(keyexch *kx, unsigned ty, const octet *hc_in,
 689                           const octet *hc_out, mp *ck, buf *b)
 690 {
 691   kxchal *kxc;
 692   buf bb;
 693   ge *r = 0;
 694
 695   /* --- Check the plaintext portions of the data --- */
 696
 697   IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, {
 698     trace_block(T_CRYPTO, "crypto: challenge", hc_in, HASHSZ);
 699     trace_block(T_CRYPTO, "crypto: cookie", hc_out, HASHSZ);
 700     if (ck) trace(T_CRYPTO, "crypto: check value = %s", mpstr(ck));
 701   }))
 702   if (memcmp(hc_out, kx->hc, HASHSZ) != 0) {
 703     a_warn("incorrect cookie from `%s'", p_name(kx->p));
 704     goto bad;
 705   }
 706   if ((kxc = kxc_byhc(kx, hc_in)) == 0) {
 707     a_warn("received reply for unknown challenge from `%s'", p_name(kx->p));
 708     goto bad;
 709   }
 710
 711   /* --- Maybe compute a reply for the challenge --- */
 712
 713   if (!kxc->r) {
 714     if (!ck) {
 715       a_warn("unexpected switch request from `%s'", p_name(kx->p));
 716       goto bad;
 717     }
 718     if ((r = getreply(kx, kxc->c, ck)) == 0)
 719       goto bad;
 720     kxc->r = r;
 721     r = 0;
 722   }
 723
 724   /* --- Decrypt the rest of the packet --- */
 725
 726   buf_init(&bb, buf_o, sizeof(buf_o));
 727   if (ks_decrypt(kxc->ks, ty, b, &bb)) {
 728     a_warn("failed to decrypt reply from `%s'", p_name(kx->p));
 729     goto bad;
 730   }
 731   buf_init(b, BBASE(&bb), BLEN(&bb));
 732   r = G_CREATE(gg);
 733   if (G_FROMBUF(gg, b, r)) {
 734     a_warn("invalid reply packet from `%s'", p_name(kx->p));
 735     goto bad;
 736   }
 737   IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, {
 738     trace(T_CRYPTO, "crypto: reply = %s", gestr(gg, r));
 739   }))
 740   if (!G_EQ(gg, r, kx->rx)) {
 741     a_warn("incorrect reply from `%s'", p_name(kx->p));
 742     goto bad;
 743   }
 744
 745   /* --- Done --- */
 746
 747   G_DESTROY(gg, r);
 748   return (kxc);
 749
 750 bad:
 751   if (r) G_DESTROY(gg, r);
 752   return (0);
 753 }
 754
 755 /* --- @commit@ --- *
 756  *
 757  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 758  *              @kxchal *kxc@ = pointer to challenge to commit to
 759  *
 760  * Returns:     ---
 761  *
 762  * Use:         Commits to a particular challenge as being the `right' one,
 763  *              since a reply has arrived for it.
 764  */
 765
 766 static void commit(keyexch *kx, kxchal *kxc)
 767 {
 768   unsigned i;
 769
 770   for (i = 0; i < kx->nr; i++) {
 771     if (kx->r[i] != kxc)
 772       kxc_destroy(kx->r[i]);
 773   }
 774   kx->r[0] = kxc;
 775   kx->nr = 1;
 776   kxc_stoptimer(kxc);
 777   ksl_link(kx->ks, kxc->ks);
 778 }
 779
 780 /* --- @doreply@ --- *
 781  *
 782  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 783  *              @buf *b@ = buffer containing packet
 784  *
 785  * Returns:     Zero if OK, nonzero if the packet was rejected.
 786  *
 787  * Use:         Handles a reply packet.  This doesn't handle the various
 788  *              switch packets: they're rather too different.
 789  */
 790
 791 static int doreply(keyexch *kx, buf *b)
 792 {
 793   const octet *hc_in, *hc_out;
 794   mp *ck = 0;
 795   kxchal *kxc;
 796
 797   if (kx->s != KXS_CHAL && kx->s != KXS_COMMIT) {
 798     a_warn("unexpected reply from `%s'", p_name(kx->p));
 799     goto bad;
 800   }
 801   if ((hc_in = buf_get(b, HASHSZ)) == 0 ||
 802       (hc_out = buf_get(b, HASHSZ)) == 0 ||
 803       (ck = buf_getmp(b)) == 0) {
 804     a_warn("invalid reply packet from `%s'", p_name(kx->p));
 805     goto bad;
 806   }
 807   if ((kxc = matchreply(kx, MSG_KEYEXCH | KX_REPLY,
 808                         hc_in, hc_out, ck, b)) == 0)
 809     goto bad;
 810   if (BLEFT(b)) {
 811     a_warn("invalid reply packet from `%s'", p_name(kx->p));
 812     goto bad;
 813   }
 814   if (kx->s == KXS_CHAL) {
 815     commit(kx, kxc);
 816     kx->s = KXS_COMMIT;
 817   }
 818   resend(kx);
 819   return (0);
 820
 821 bad:
 822   mp_drop(ck);
 823   return (-1);
 824 }
 825
 826 /* --- @doswitch@ --- *
 827  *
 828  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 829  *              @buf *b@ = pointer to buffer containing packet
 830  *
 831  * Returns:     Zero if OK, nonzero if the packet was rejected.
 832  *
 833  * Use:         Handles a reply with a switch request bolted onto it.
 834  */
 835
 836 static int doswitch(keyexch *kx, buf *b)
 837 {
 838   const octet *hc_in, *hc_out, *hswrq;
 839   kxchal *kxc;
 840
 841   if ((hc_in = buf_get(b, HASHSZ)) == 0 ||
 842       (hc_out = buf_get(b, HASHSZ)) == 0) {
 843     a_warn("invalid switch request from `%s'", p_name(kx->p));
 844     goto bad;
 845   }
 846   if ((kxc = matchreply(kx, MSG_KEYEXCH | KX_SWITCH,
 847                         hc_in, hc_out, 0, b)) == 0)
 848     goto bad;
 849   if ((hswrq = buf_get(b, HASHSZ)) == 0 || BLEFT(b)) {
 850     a_warn("invalid switch request from `%s'", p_name(kx->p));
 851     goto bad;
 852   }
 853   IF_TRACING(T_KEYEXCH, {
 854     trace_block(T_CRYPTO, "crypto: switch request hash", hswrq, HASHSZ);
 855   })
 856   if (memcmp(hswrq, kxc->hswrq_in, HASHSZ) != 0) {
 857     a_warn("incorrect switch request hash from `%s'", p_name(kx->p));
 858     goto bad;
 859   }
 860   switch (kx->s) {
 861     case KXS_CHAL:
 862       commit(kx, kxc);
 863     case KXS_COMMIT:
 864       ks_activate(kxc->ks);
 865       settimer(kx, ks_tregen(kxc->ks));
 866       kx->s = KXS_SWITCH;
 867       break;
 868   }
 869   resend(kx);
 870   return (0);
 871
 872 bad:
 873   return (-1);
 874 }
 875
 876 /* --- @doswitchok@ --- *
 877  *
 878  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 879  *              @buf *b@ = pointer to buffer containing packet
 880  *
 881  * Returns:     Zero if OK, nonzero if the packet was rejected.
 882  *
 883  * Use:         Handles a reply with a switch request bolted onto it.
 884  */
 885
 886 static int doswitchok(keyexch *kx, buf *b)
 887 {
 888   const octet *hswok;
 889   kxchal *kxc;
 890   buf bb;
 891
 892   if (kx->s < KXS_COMMIT) {
 893     a_warn("unexpected switch confirmation from `%s'", p_name(kx->p));
 894     goto bad;
 895   }
 896   kxc = kx->r[0];
 897   buf_init(&bb, buf_o, sizeof(buf_o));
 898   if (ks_decrypt(kxc->ks, MSG_KEYEXCH | KX_SWITCHOK, b, &bb)) {
 899     a_warn("failed to decrypt switch confirmation from `%s'", p_name(kx->p));
 900     goto bad;
 901   }
 902   buf_init(b, BBASE(&bb), BLEN(&bb));
 903   if ((hswok = buf_get(b, HASHSZ)) == 0 || BLEFT(b)) {
 904     a_warn("invalid switch confirmation from `%s'", p_name(kx->p));
 905     goto bad;
 906   }
 907   IF_TRACING(T_KEYEXCH, {
 908     trace_block(T_CRYPTO, "crypto: switch confirmation hash", hswok, HASHSZ);
 909   })
 910   if (memcmp(hswok, kxc->hswok_in, HASHSZ) != 0) {
 911     a_warn("incorrect switch confirmation hash from `%s'", p_name(kx->p));
 912     goto bad;
 913   }
 914   if (kx->s < KXS_SWITCH) {
 915     ks_activate(kxc->ks);
 916     settimer(kx, ks_tregen(kxc->ks));
 917     kx->s = KXS_SWITCH;
 918   }
 919   return (0);
 920
 921 bad:
 922   return (-1);
 923 }
 924
 925 /*----- Main code ---------------------------------------------------------*/
 926
 927 /* --- @stop@ --- *
 928  *
 929  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 930  *
 931  * Returns:     ---
 932  *
 933  * Use:         Stops a key exchange dead in its tracks.  Throws away all of
 934  *              the context information.  The context is left in an
 935  *              inconsistent state.  The only functions which understand this
 936  *              state are @kx_free@ and @kx_init@ (which cause it internally
 937  *              it), and @start@ (which expects it to be the prevailing
 938  *              state).
 939  */
 940
 941 static void stop(keyexch *kx)
 942 {
 943   unsigned i;
 944
 945   if (kx->f & KXF_DEAD)
 946     return;
 947
 948   if (kx->f & KXF_TIMER)
 949     sel_rmtimer(&kx->t);
 950   for (i = 0; i < kx->nr; i++)
 951     kxc_destroy(kx->r[i]);
 952   mp_drop(kx->alpha);
 953   G_DESTROY(gg, kx->c);
 954   G_DESTROY(gg, kx->rx);
 955   kx->t_valid = 0;
 956   kx->f |= KXF_DEAD;
 957   kx->f &= ~KXF_TIMER;
 958 }
 959
 960 /* --- @start@ --- *
 961  *
 962  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 963  *              @time_t now@ = the current time
 964  *
 965  * Returns:     ---
 966  *
 967  * Use:         Starts a new key exchange with the peer.  The context must be
 968  *              in the bizarre state left by @stop@ or @kx_init@.
 969  */
 970
 971 static void start(keyexch *kx, time_t now)
 972 {
 973   HASH_CTX h;
 974
 975   assert(kx->f & KXF_DEAD);
 976
 977   kx->f &= ~KXF_DEAD;
 978   kx->nr = 0;
 979   kx->alpha = mprand_range(MP_NEW, gg->r, &rand_global, 0);
 980   kx->c = G_CREATE(gg); G_EXP(gg, kx->c, gg->g, kx->alpha);
 981   kx->rx = G_CREATE(gg); G_EXP(gg, kx->rx, kx->kpub, kx->alpha);
 982   kx->s = KXS_CHAL;
 983   kx->t_valid = now + T_VALID;
 984
 985   HASH_INIT(&h);
 986   HASH_STRING(&h, "tripe-cookie");
 987   hashge(&h, kx->c);
 988   HASH_DONE(&h, kx->hc);
 989
 990   IF_TRACING(T_KEYEXCH, {
 991     trace(T_KEYEXCH, "keyexch: creating new challenge");
 992     IF_TRACING(T_CRYPTO, {
 993       trace(T_CRYPTO, "crypto: secret = %s", mpstr(kx->alpha));
 994       trace(T_CRYPTO, "crypto: challenge = %s", gestr(gg, kx->c));
 995       trace(T_CRYPTO, "crypto: expected response = %s", gestr(gg, kx->rx));
 996       trace_block(T_CRYPTO, "crypto: challenge cookie", kx->hc, HASHSZ);
 997     })
 998   })
 999 }
1000
1001 /* --- @checkpub@ --- *
1002  *
1003  * Arguments:   @keyexch *kx@ = pointer to key exchange context
1004  *
1005  * Returns:     Zero if OK, nonzero if the peer's public key has expired.
1006  *
1007  * Use:         Deactivates the key-exchange until the peer acquires a new
1008  *              public key.
1009  */
1010
1011 static int checkpub(keyexch *kx)
1012 {
1013   time_t now;
1014   if (kx->f & KXF_DEAD)
1015     return (-1);
1016   now = time(0);
1017   if (KEY_EXPIRED(now, kx->texp_kpub)) {
1018     stop(kx);
1019     a_warn("public key for `%s' has expired", p_name(kx->p));
1020     G_COPY(gg, kx->kpub, gg->i);
1021     kx->f &= ~KXF_PUBKEY;
1022     return (-1);
1023   }
1024   return (0);
1025 }
1026
1027 /* --- @kx_start@ --- *
1028  *
1029  * Arguments:   @keyexch *kx@ = pointer to key exchange context
1030  *
1031  * Returns:     ---
1032  *
1033  * Use:         Stimulates a key exchange.  If a key exchage is in progress,
1034  *              a new challenge is sent (unless the quiet timer forbids
1035  *              this); if no exchange is in progress, one is commenced.
1036  */
1037
1038 void kx_start(keyexch *kx)
1039 {
1040   time_t now = time(0);
1041
1042   if (checkpub(kx))
1043     return;
1044   if (!ISVALID(kx, now)) {
1045     stop(kx);
1046     start(kx, now);
1047   }
1048   resend(kx);
1049 }
1050
1051 /* --- @kx_message@ --- *
1052  *
1053  * Arguments:   @keyexch *kx@ = pointer to key exchange context
1054  *              @unsigned msg@ = the message code
1055  *              @buf *b@ = pointer to buffer containing the packet
1056  *
1057  * Returns:     ---
1058  *
1059  * Use:         Reads a packet containing key exchange messages and handles
1060  *              it.
1061  */
1062
1063 void kx_message(keyexch *kx, unsigned msg, buf *b)
1064 {
1065   time_t now = time(0);
1066   stats *st = p_stats(kx->p);
1067   size_t sz = BSZ(b);
1068   int rc;
1069
1070 #ifndef NTRACE
1071   static const char *const pkname[] = {
1072     "prechallenge", "cookie", "challenge",
1073     "reply", "switch request", "switch confirmation"
1074   };
1075 #endif
1076
1077   if (checkpub(kx))
1078     return;
1079
1080   if (!ISVALID(kx, now)) {
1081     stop(kx);
1082     start(kx, now);
1083   }
1084
1085   T( trace(T_KEYEXCH, "keyexch: processing %s packet from `%s'",
1086            msg < KX_NMSG ? pkname[msg] : "unknown", p_name(kx->p)); )
1087
1088   switch (msg) {
1089     case KX_PRECHAL:
1090     case KX_COOKIE:
1091     case KX_CHAL:
1092       rc = dochallenge(kx, msg, b);
1093       break;
1094     case KX_REPLY:
1095       rc = doreply(kx, b);
1096       break;
1097     case KX_SWITCH:
1098       rc = doswitch(kx, b);
1099       break;
1100     case KX_SWITCHOK:
1101       rc = doswitchok(kx, b);
1102       break;
1103     default:
1104       a_warn("unexpected key exchange message type %u from `%p'",
1105              p_name(kx->p));
1106       rc = -1;
1107       break;
1108   }
1109
1110   if (rc)
1111     st->n_reject++;
1112   else {
1113     st->n_kxin++;
1114     st->sz_kxin += sz;
1115   }
1116 }
1117
1118 /* --- @kx_free@ --- *
1119  *
1120  * Arguments:   @keyexch *kx@ = pointer to key exchange context
1121  *
1122  * Returns:     ---
1123  *
1124  * Use:         Frees everything in a key exchange context.
1125  */
1126
1127 void kx_free(keyexch *kx)
1128 {
1129   stop(kx);
1130   G_DESTROY(gg, kx->kpub);
1131 }
1132
1133 /* --- @kx_newkeys@ --- *
1134  *
1135  * Arguments:   @keyexch *kx@ = pointer to key exchange context
1136  *
1137  * Returns:     ---
1138  *
1139  * Use:         Informs the key exchange module that its keys may have
1140  *              changed.  If fetching the new keys fails, the peer will be
1141  *              destroyed, we log messages and struggle along with the old
1142  *              keys.
1143  */
1144
1145 void kx_newkeys(keyexch *kx)
1146 {
1147   if (km_getpubkey(p_name(kx->p), kx->kpub, &kx->texp_kpub))
1148     return;
1149   kx->f |= KXF_PUBKEY;
1150   if ((kx->f & KXF_DEAD) || kx->s != KXS_SWITCH) {
1151     T( trace(T_KEYEXCH, "keyexch: restarting key negotiation with `%s'",
1152              p_name(kx->p)); )
1153     stop(kx);
1154     start(kx, time(0));
1155     resend(kx);
1156   }
1157 }
1158
1159 /* --- @kx_init@ --- *
1160  *
1161  * Arguments:   @keyexch *kx@ = pointer to key exchange context
1162  *              @peer *p@ = pointer to peer context
1163  *              @keyset **ks@ = pointer to keyset list
1164  *
1165  * Returns:     Zero if OK, nonzero if it failed.
1166  *
1167  * Use:         Initializes a key exchange module.  The module currently
1168  *              contains no keys, and will attempt to initiate a key
1169  *              exchange.
1170  */
1171
1172 int kx_init(keyexch *kx, peer *p, keyset **ks)
1173 {
1174   kx->ks = ks;
1175   kx->p = p;
1176   kx->kpub = G_CREATE(gg);
1177   if (km_getpubkey(p_name(p), kx->kpub, &kx->texp_kpub)) {
1178     G_DESTROY(gg, kx->kpub);
1179     return (-1);
1180   }
1181   kx->f = KXF_DEAD | KXF_PUBKEY;
1182   start(kx, time(0));
1183   resend(kx);
1184   return (0);
1185 }
1186
1187 /*----- That's all, folks -------------------------------------------------*/