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

   1 /* -*-c-*-
   2  *
   3  * $Id: keyset.c,v 1.10 2004/04/08 01:36:17 mdw Exp $
   4  *
   5  * Handling of symmetric keysets
   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 /*----- Tunable parameters ------------------------------------------------*/
  34
  35 /* --- Note on size limits --- *
  36  *
  37  * For a 64-bit block cipher (e.g., Blowfish), the probability of a collision
  38  * occurring after 32 MB is less than %$2^{-21}$%, and the probability of a
  39  * collision occurring after 64 MB is less than %$2^{-19}$%.
  40  */
  41
  42 #define T_EXP MIN(60)                   /* Expiry time for a key */
  43 #define T_REGEN MIN(45)                 /* Regeneration time for a key */
  44 #define SZ_EXP MEG(64)                  /* Expiry data size for a key */
  45 #define SZ_REGEN MEG(32)                /* Data size threshold for regen */
  46
  47 /*----- Handy macros ------------------------------------------------------*/
  48
  49 #define KEYOK(ks, now) ((ks)->sz_exp > 0 && (ks)->t_exp > now)
  50
  51 /*----- Low-level packet encryption and decryption ------------------------*/
  52
  53 /* --- Encrypted data format --- *
  54  *
  55  * Let %$p_i$% be the %$i$%-th plaintext message, with type %$t$%.  We first
  56  * compute
  57  *
  58  *   %$c_i = \mathcal{E}\textrm{-CBC}_{K_{\text{E}}}(p_i)$%
  59  *
  60  * as the CBC-ciphertext of %$p_i$%, and then
  61  *
  62  *   %$\sigma_i = \mathcal{T}_{K_{\text{M}}}(t, i, c_i)$%
  63  *
  64  * as a MAC on the %%\emph{ciphertext}%%.  The message sent is then the pair
  65  * %$(\sigma_i, c_i)$%.  This construction is provably secure in the NM-CCA
  66  * sense (assuming that the cipher is IND-CPA, and the MAC is SUF-CMA)
  67  * [Bellare and Namprempre].
  68  *
  69  * This also ensures that, assuming the key is good, we have a secure channel
  70  * [Krawczyk].  Actually, [Krawczyk] shows that, if the cipher is either a
  71  * simple stream cipher or a block cipher in CBC mode, we can use the MAC-
  72  * then-encrypt scheme and still have a secure channel.  However, I like the
  73  * NM-CCA guarantee from [Bellare and Namprempre].  I'm less worried about
  74  * the Horton Principle [Wagner and Schneier].
  75  */
  76
  77 /* --- @doencrypt@ --- *
  78  *
  79  * Arguments:   @keyset *ks@ = pointer to keyset to use
  80  *              @unsigned ty@ = type of message this is
  81  *              @buf *b@ = pointer to an input buffer
  82  *              @buf *bb@ = pointer to an output buffer
  83  *
  84  * Returns:     Zero if OK, nonzero if a new key is required.
  85  *
  86  * Use:         Encrypts a message with the given key.  We assume that the
  87  *              keyset is OK to use.
  88  */
  89
  90 static int doencrypt(keyset *ks, unsigned ty, buf *b, buf *bb)
  91 {
  92   ghash *h;
  93   gcipher *c;
  94   const octet *p = BCUR(b);
  95   size_t sz = BLEFT(b);
  96   octet *qmac, *qseq, *qiv, *qpk;
  97   uint32 oseq;
  98   size_t osz, nsz;
  99   octet t[4];
 100   int rc = 0;
 101
 102   /* --- Allocate the required buffer space --- */
 103
 104   c = ks->cout;
 105   if (buf_ensure(bb, MACSZ + SEQSZ + IVSZ + sz))
 106     return (0); /* Caution! */
 107   qmac = BCUR(bb); qseq = qmac + MACSZ; qiv = qseq + SEQSZ; qpk = qiv + IVSZ;
 108   BSTEP(bb, MACSZ + SEQSZ + IVSZ + sz);
 109   STORE32(t, ty);
 110
 111   /* --- Encrypt the packet --- */
 112
 113   oseq = ks->oseq++; STORE32(qseq, oseq);
 114   rand_get(RAND_GLOBAL, qiv, IVSZ);
 115   c->ops->setiv(c, qiv);
 116   c->ops->encrypt(c, p, qpk, sz);
 117   IF_TRACING(T_KEYSET, {
 118     trace(T_KEYSET, "keyset: encrypting packet %lu using keyset %u",
 119           (unsigned long)oseq, ks->seq);
 120     trace_block(T_CRYPTO, "crypto: encrypted packet", qpk, sz);
 121   })
 122
 123   /* --- Now compute the MAC --- */
 124
 125   h = ks->mout->ops->init(ks->mout);
 126   h->ops->hash(h, t, sizeof(t));
 127   h->ops->hash(h, qseq, SEQSZ + IVSZ + sz);
 128   memcpy(qmac, h->ops->done(h, 0), MACSZ);
 129   h->ops->destroy(h);
 130   IF_TRACING(T_KEYSET, {
 131     trace_block(T_CRYPTO, "crypto: computed MAC", qmac, MACSZ);
 132   })
 133
 134   /* --- Deduct the packet size from the key's data life --- */
 135
 136   osz = ks->sz_exp;
 137   if (osz > sz)
 138     nsz = osz - sz;
 139   else
 140     nsz = 0;
 141   if (osz >= SZ_REGEN && nsz < SZ_REGEN) {
 142     T( trace(T_KEYSET, "keyset: keyset %u data regen limit exceeded -- "
 143              "forcing exchange", ks->seq); )
 144     rc = -1;
 145   }
 146   ks->sz_exp = nsz;
 147   return (rc);
 148 }
 149
 150 /* --- @dodecrypt@ --- *
 151  *
 152  * Arguments:   @keyset *ks@ = pointer to keyset to use
 153  *              @unsigned ty@ = expected type code
 154  *              @buf *b@ = pointer to an input buffer
 155  *              @buf *bb@ = pointer to an output buffer
 156  *              @uint32 *seq@ = where to store the sequence number
 157  *
 158  * Returns:     Zero if OK, nonzero if it failed.
 159  *
 160  * Use:         Attempts to decrypt a message with the given key.  No other
 161  *              checking (e.g., sequence number checks) is performed.  We
 162  *              assume that the keyset is OK to use, and that there is
 163  *              sufficient output buffer space reserved.  If the decryption
 164  *              is successful, the buffer pointer is moved past the decrypted
 165  *              packet, and the packet's sequence number is stored in @*seq@.
 166  */
 167
 168 static int dodecrypt(keyset *ks, unsigned ty, buf *b, buf *bb, uint32 *seq)
 169 {
 170   const octet *pmac, *piv, *pseq, *ppk;
 171   size_t psz = BLEFT(b);
 172   size_t sz;
 173   octet *q = BCUR(bb);
 174   ghash *h;
 175   gcipher *c = ks->cin;
 176   size_t ivsz = c->ops->c->blksz;
 177   octet *mac;
 178   int eq;
 179   octet t[4];
 180
 181   /* --- Break up the packet into its components --- */
 182
 183   if (psz < ivsz + 4) {
 184     T( trace(T_KEYSET, "keyset: block too small for keyset %u", ks->seq); )
 185     return (-1);
 186   }
 187   sz = psz - IVSZ - SEQSZ - MACSZ;
 188   pmac = BCUR(b); pseq = pmac + MACSZ; piv = pseq + SEQSZ; ppk = piv + IVSZ;
 189   STORE32(t, ty);
 190
 191   /* --- Verify the MAC on the packet --- */
 192
 193   h = ks->min->ops->init(ks->min);
 194   h->ops->hash(h, t, sizeof(t));
 195   h->ops->hash(h, pseq, SEQSZ + IVSZ + sz);
 196   mac = h->ops->done(h, 0);
 197   eq = !memcmp(mac, pmac, MACSZ);
 198   IF_TRACING(T_KEYSET, {
 199     trace(T_KEYSET, "keyset: decrypting using keyset %u", ks->seq);
 200     trace_block(T_CRYPTO, "crypto: computed MAC", mac, MACSZ);
 201   })
 202   h->ops->destroy(h);
 203   if (!eq) {
 204     IF_TRACING(T_KEYSET, {
 205       trace(T_KEYSET, "keyset: incorrect MAC: decryption failed");
 206       trace_block(T_CRYPTO, "crypto: expected MAC", pmac, MACSZ);
 207     })
 208     return (-1);
 209   }
 210
 211   /* --- Decrypt the packet --- */
 212
 213   c->ops->setiv(c, piv);
 214   c->ops->decrypt(c, ppk, q, sz);
 215   if (seq)
 216     *seq = LOAD32(pseq);
 217   IF_TRACING(T_KEYSET, {
 218     trace(T_KEYSET, "keyset: decrypted OK (sequence = %lu)",
 219           (unsigned long)LOAD32(pseq));
 220     trace_block(T_CRYPTO, "crypto: decrypted packet", q, sz);
 221   })
 222   BSTEP(bb, sz);
 223   return (0);
 224 }
 225
 226 /* --- @dosequence@ --- *
 227  *
 228  * Arguments:   @keyset *ks@ = pointer to a keyset
 229  *              @uint32 seq@ = a sequence number from a packet
 230  *
 231  * Returns:     Zero if the sequence number is OK, nonzero if it's not.
 232  *
 233  * Use:         Checks a sequence number.  The data in the keyset which keeps
 234  *              track of valid sequence numbers is updated if the sequence
 235  *              number given is good.  It's assumed that the sequence number
 236  *              has already been checked for authenticity.
 237  */
 238
 239 static int dosequence(keyset *ks, uint32 seq)
 240 {
 241   uint32 seqbit;
 242   uint32 n;
 243
 244   if (seq < ks->iseq) {
 245     a_warn("received packet has old sequence number (possible replay)");
 246     return (-1);
 247   }
 248   if (seq >= ks->iseq + KS_SEQWINSZ) {
 249     n = seq - (ks->iseq + KS_SEQWINSZ - 1);
 250     if (n < KS_SEQWINSZ)
 251       ks->iwin >>= n;
 252     else
 253       ks->iwin = 0;
 254     ks->iseq += n;
 255   }
 256   seqbit = 1 << (seq - ks->iseq);
 257   if (ks->iwin & seqbit) {
 258     a_warn("received packet repeats old sequence number");
 259     return (-1);
 260   }
 261   ks->iwin |= seqbit;
 262   return (0);
 263 }
 264
 265 /*----- Operations on a single keyset -------------------------------------*/
 266
 267 /* --- @ks_drop@ --- *
 268  *
 269  * Arguments:   @keyset *ks@ = pointer to a keyset
 270  *
 271  * Returns:     ---
 272  *
 273  * Use:         Decrements a keyset's reference counter.  If the counter hits
 274  *              zero, the keyset is freed.
 275  */
 276
 277 void ks_drop(keyset *ks)
 278 {
 279   if (--ks->ref)
 280     return;
 281   ks->cin->ops->destroy(ks->cin);
 282   ks->cout->ops->destroy(ks->cout);
 283   ks->min->ops->destroy(ks->min);
 284   ks->mout->ops->destroy(ks->mout);
 285   DESTROY(ks);
 286 }
 287
 288 /* --- @ks_gen@ --- *
 289  *
 290  * Arguments:   @const void *k@ = pointer to key material
 291  *              @size_t x, y, z@ = offsets into key material (see below)
 292  *              @peer *p@ = pointer to peer information
 293  *
 294  * Returns:     A pointer to the new keyset.
 295  *
 296  * Use:         Derives a new keyset from the given key material.  The
 297  *              offsets @x@, @y@ and @z@ separate the key material into three
 298  *              parts.  Between the @k@ and @k + x@ is `my' contribution to
 299  *              the key material; between @k + x@ and @k + y@ is `your'
 300  *              contribution; and between @k + y@ and @k + z@ is a shared
 301  *              value we made together.  These are used to construct two
 302  *              pairs of symmetric keys.  Each pair consists of an encryption
 303  *              key and a message authentication key.  One pair is used for
 304  *              outgoing messages, the other for incoming messages.
 305  *
 306  *              The new key is marked so that it won't be selected for output
 307  *              by @ksl_encrypt@.  You can still encrypt data with it by
 308  *              calling @ks_encrypt@ directly.
 309  */
 310
 311 keyset *ks_gen(const void *k, size_t x, size_t y, size_t z, peer *p)
 312 {
 313   HASH_CTX h;
 314   octet buf[HASHSZ];
 315   keyset *ks = CREATE(keyset);
 316   time_t now = time(0);
 317   const octet *pp = k;
 318   T( static unsigned seq = 0; )
 319
 320   T( trace(T_KEYSET, "keyset: adding new keyset %u", seq); )
 321
 322   /* --- Construct the various keys --- *
 323    *
 324    * This is done with macros, because it's quite tedious.
 325    */
 326
 327 #define MINE HASH(&h, pp, x)
 328 #define YOURS HASH(&h, pp + x, y - x)
 329 #define OURS HASH(&h, pp + y, z - y)
 330
 331 #define IN MINE; YOURS; OURS
 332 #define OUT YOURS; MINE; OURS
 333 #define STR_IN "incoming"
 334 #define STR_OUT "outgoing"
 335
 336 #define GETHASH(str, dir) do {                                          \
 337   HASH_INIT(&h);                                                        \
 338   HASH_STRING(&h, "tripe-" str);                                        \
 339   dir;                                                                  \
 340   HASH_DONE(&h, buf);                                                   \
 341   IF_TRACING(T_KEYSET, {                                                \
 342     trace_block(T_CRYPTO, "crypto: " STR_##dir " key " str,             \
 343                 buf, sizeof(buf));                                      \
 344   })                                                                    \
 345 } while (0)
 346
 347   GETHASH("encryption", IN); ks->cin = CIPHER->init(buf, sizeof(buf));
 348   GETHASH("integrity", IN); ks->min = MAC->key(buf, sizeof(buf));
 349   GETHASH("encryption", OUT); ks->cout = CIPHER->init(buf, sizeof(buf));
 350   GETHASH("integrity", OUT); ks->mout = MAC->key(buf, sizeof(buf));
 351
 352 #undef MINE
 353 #undef YOURS
 354 #undef OURS
 355 #undef IN
 356 #undef OUT
 357 #undef STR_IN
 358 #undef STR_OUT
 359 #undef GETHASH
 360
 361   T( ks->seq = seq++; )
 362   ks->ref = 1;
 363   ks->t_exp = now + T_EXP;
 364   ks->sz_exp = SZ_EXP;
 365   ks->oseq = ks->iseq = 0;
 366   ks->iwin = 0;
 367   ks->next = 0;
 368   ks->p = p;
 369   ks->f = KSF_LISTEN;
 370   BURN(buf);
 371   return (ks);
 372 }
 373
 374 /* --- @ks_tregen@ --- *
 375  *
 376  * Arguments:   @keyset *ks@ = pointer to a keyset
 377  *
 378  * Returns:     The time at which moves ought to be made to replace this key.
 379  */
 380
 381 time_t ks_tregen(keyset *ks) { return (ks->t_exp - T_EXP + T_REGEN); }
 382
 383 /* --- @ks_activate@ --- *
 384  *
 385  * Arguments:   @keyset *ks@ = pointer to a keyset
 386  *
 387  * Returns:     ---
 388  *
 389  * Use:         Activates a keyset, so that it can be used for encrypting
 390  *              outgoing messages.
 391  */
 392
 393 void ks_activate(keyset *ks)
 394 {
 395   if (ks->f & KSF_LISTEN) {
 396     T( trace(T_KEYSET, "keyset: activating keyset %u", ks->seq); )
 397     ks->f &= ~KSF_LISTEN;
 398   }
 399 }
 400
 401 /* --- @ks_encrypt@ --- *
 402  *
 403  * Arguments:   @keyset *ks@ = pointer to a keyset
 404  *              @unsigned ty@ = message type
 405  *              @buf *b@ = pointer to input buffer
 406  *              @buf *bb@ = pointer to output buffer
 407  *
 408  * Returns:     Zero if OK, nonzero if the key needs replacing.  If the
 409  *              encryption failed, the output buffer is broken and zero is
 410  *              returned.
 411  *
 412  * Use:         Encrypts a block of data using the key.  Note that the `key
 413  *              ought to be replaced' notification is only ever given once
 414  *              for each key.  Also note that this call forces a keyset to be
 415  *              used even if it's marked as not for data output.
 416  */
 417
 418 int ks_encrypt(keyset *ks, unsigned ty, buf *b, buf *bb)
 419 {
 420   time_t now = time(0);
 421
 422   if (!KEYOK(ks, now)) {
 423     buf_break(bb);
 424     return (0);
 425   }
 426   return (doencrypt(ks, ty, b, bb));
 427 }
 428
 429 /* --- @ks_decrypt@ --- *
 430  *
 431  * Arguments:   @keyset *ks@ = pointer to a keyset
 432  *              @unsigned ty@ = expected type code
 433  *              @buf *b@ = pointer to an input buffer
 434  *              @buf *bb@ = pointer to an output buffer
 435  *
 436  * Returns:     Zero on success, or nonzero if there was some problem.
 437  *
 438  * Use:         Attempts to decrypt a message using a given key.  Note that
 439  *              requesting decryption with a key directly won't clear a
 440  *              marking that it's not for encryption.
 441  */
 442
 443 int ks_decrypt(keyset *ks, unsigned ty, buf *b, buf *bb)
 444 {
 445   time_t now = time(0);
 446   uint32 seq;
 447
 448   if (!KEYOK(ks, now) ||
 449       buf_ensure(bb, BLEN(b)) ||
 450       dodecrypt(ks, ty, b, bb, &seq) ||
 451       dosequence(ks, seq))
 452     return (-1);
 453   return (0);
 454 }
 455
 456 /*----- Keyset list handling ----------------------------------------------*/
 457
 458 /* --- @ksl_free@ --- *
 459  *
 460  * Arguments:   @keyset **ksroot@ = pointer to keyset list head
 461  *
 462  * Returns:     ---
 463  *
 464  * Use:         Frees (releases references to) all of the keys in a keyset.
 465  */
 466
 467 void ksl_free(keyset **ksroot)
 468 {
 469   keyset *ks, *ksn;
 470   for (ks = *ksroot; ks; ks = ksn) {
 471     ksn = ks->next;
 472     ks->f &= ~KSF_LINK;
 473     ks_drop(ks);
 474   }
 475 }
 476
 477 /* --- @ksl_link@ --- *
 478  *
 479  * Arguments:   @keyset **ksroot@ = pointer to keyset list head
 480  *              @keyset *ks@ = pointer to a keyset
 481  *
 482  * Returns:     ---
 483  *
 484  * Use:         Links a keyset into a list.  A keyset can only be on one list
 485  *              at a time.  Bad things happen otherwise.
 486  */
 487
 488 void ksl_link(keyset **ksroot, keyset *ks)
 489 {
 490   assert(!(ks->f & KSF_LINK));
 491   ks->next = *ksroot;
 492   *ksroot = ks;
 493   ks->f |= KSF_LINK;
 494   ks->ref++;
 495 }
 496
 497 /* --- @ksl_prune@ --- *
 498  *
 499  * Arguments:   @keyset **ksroot@ = pointer to keyset list head
 500  *
 501  * Returns:     ---
 502  *
 503  * Use:         Prunes the keyset list by removing keys which mustn't be used
 504  *              any more.
 505  */
 506
 507 void ksl_prune(keyset **ksroot)
 508 {
 509   time_t now = time(0);
 510
 511   while (*ksroot) {
 512     keyset *ks = *ksroot;
 513
 514     if (ks->t_exp <= now) {
 515       T( trace(T_KEYSET, "keyset: expiring keyset %u (time limit reached)",
 516                ks->seq); )
 517       goto kill;
 518     } else if (ks->sz_exp == 0) {
 519       T( trace(T_KEYSET, "keyset: expiring keyset %u (data limit reached)",
 520                ks->seq); )
 521       goto kill;
 522     } else {
 523       ksroot = &ks->next;
 524       continue;
 525     }
 526
 527   kill:
 528     *ksroot = ks->next;
 529     ks->f &= ~KSF_LINK;
 530     ks_drop(ks);
 531   }
 532 }
 533
 534 /* --- @ksl_encrypt@ --- *
 535  *
 536  * Arguments:   @keyset **ksroot@ = pointer to keyset list head
 537  *              @unsigned ty@ = message type
 538  *              @buf *b@ = pointer to input buffer
 539  *              @buf *bb@ = pointer to output buffer
 540  *
 541  * Returns:     Nonzero if a new key is needed.
 542  *
 543  * Use:         Encrypts a packet.
 544  */
 545
 546 int ksl_encrypt(keyset **ksroot, unsigned ty, buf *b, buf *bb)
 547 {
 548   time_t now = time(0);
 549   keyset *ks = *ksroot;
 550
 551   for (;;) {
 552     if (!ks) {
 553       T( trace(T_KEYSET, "keyset: no suitable keysets found"); )
 554       buf_break(bb);
 555       return (-1);
 556     }
 557     if (KEYOK(ks, now) && !(ks->f & KSF_LISTEN))
 558       break;
 559     ks = ks->next;
 560   }
 561
 562   return (doencrypt(ks, ty, b, bb));
 563 }
 564
 565 /* --- @ksl_decrypt@ --- *
 566  *
 567  * Arguments:   @keyset **ksroot@ = pointer to keyset list head
 568  *              @unsigned ty@ = expected type code
 569  *              @buf *b@ = pointer to input buffer
 570  *              @buf *bb@ = pointer to output buffer
 571  *
 572  * Returns:     Nonzero if the packet couldn't be decrypted.
 573  *
 574  * Use:         Decrypts a packet.
 575  */
 576
 577 int ksl_decrypt(keyset **ksroot, unsigned ty, buf *b, buf *bb)
 578 {
 579   time_t now = time(0);
 580   keyset *ks;
 581   uint32 seq;
 582
 583   if (buf_ensure(bb, BLEN(b)))
 584     return (-1);
 585
 586   for (ks = *ksroot; ks; ks = ks->next) {
 587     if (!KEYOK(ks, now))
 588       continue;
 589     if (!dodecrypt(ks, ty, b, bb, &seq)) {
 590       if (ks->f & KSF_LISTEN) {
 591         T( trace(T_KEYSET, "keyset: implicitly activating keyset %u",
 592                  ks->seq); )
 593         ks->f &= ~KSF_LISTEN;
 594       }
 595       return (dosequence(ks, seq));
 596     }
 597   }
 598   T( trace(T_KEYSET, "keyset: no matching keys, or incorrect MAC"); )
 599   return (-1);
 600 }
 601
 602 /*----- That's all, folks -------------------------------------------------*/