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

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