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