]> CyberLeo.Net >> Repos - FreeBSD/releng/9.3.git/blob - contrib/ntp/libntp/authkeys.c
Fix BIND remote denial of service vulnerability. [SA-16:08]
[FreeBSD/releng/9.3.git] / contrib / ntp / libntp / authkeys.c
1 /*
2  * authkeys.c - routines to manage the storage of authentication keys
3  */
4 #ifdef HAVE_CONFIG_H
5 # include <config.h>
6 #endif
7
8 #include <math.h>
9 #include <stdio.h>
10
11 #include "ntp.h"
12 #include "ntp_fp.h"
13 #include "ntpd.h"
14 #include "ntp_lists.h"
15 #include "ntp_string.h"
16 #include "ntp_malloc.h"
17 #include "ntp_stdlib.h"
18 #include "ntp_keyacc.h"
19
20 /*
21  * Structure to store keys in in the hash table.
22  */
23 typedef struct savekey symkey;
24
25 struct savekey {
26         symkey *        hlink;          /* next in hash bucket */
27         DECL_DLIST_LINK(symkey, llink); /* for overall & free lists */
28         u_char *        secret;         /* shared secret */
29         KeyAccT *       keyacclist;     /* Private key access list */
30         u_long          lifetime;       /* remaining lifetime */
31         keyid_t         keyid;          /* key identifier */
32         u_short         type;           /* OpenSSL digest NID */
33         u_short         secretsize;     /* secret octets */
34         u_short         flags;          /* KEY_ flags that wave */
35 };
36
37 /* define the payload region of symkey beyond the list pointers */
38 #define symkey_payload  secret
39
40 #define KEY_TRUSTED     0x001   /* this key is trusted */
41
42 #ifdef DEBUG
43 typedef struct symkey_alloc_tag symkey_alloc;
44
45 struct symkey_alloc_tag {
46         symkey_alloc *  link;
47         void *          mem;            /* enable free() atexit */
48 };
49
50 symkey_alloc *  authallocs;
51 #endif  /* DEBUG */
52
53 static u_short  auth_log2(size_t);
54 static void     auth_resize_hashtable(void);
55 static void     allocsymkey(symkey **, keyid_t, u_short, u_short,
56                             u_long, u_short, u_char *, KeyAccT *);
57 static void     freesymkey(symkey *, symkey **);
58 #ifdef DEBUG
59 static void     free_auth_mem(void);
60 #endif
61
62 symkey  key_listhead;           /* list of all in-use keys */;
63 /*
64  * The hash table. This is indexed by the low order bits of the
65  * keyid. We make this fairly big for potentially busy servers.
66  */
67 #define DEF_AUTHHASHSIZE        64
68 /*#define       HASHMASK        ((HASHSIZE)-1)*/
69 #define KEYHASH(keyid)  ((keyid) & authhashmask)
70
71 int     authhashdisabled;
72 u_short authhashbuckets = DEF_AUTHHASHSIZE;
73 u_short authhashmask = DEF_AUTHHASHSIZE - 1;
74 symkey **key_hash;
75
76 u_long authkeynotfound;         /* keys not found */
77 u_long authkeylookups;          /* calls to lookup keys */
78 u_long authnumkeys;             /* number of active keys */
79 u_long authkeyexpired;          /* key lifetime expirations */
80 u_long authkeyuncached;         /* cache misses */
81 u_long authnokey;               /* calls to encrypt with no key */
82 u_long authencryptions;         /* calls to encrypt */
83 u_long authdecryptions;         /* calls to decrypt */
84
85 /*
86  * Storage for free symkey structures.  We malloc() such things but
87  * never free them.
88  */
89 symkey *authfreekeys;
90 int authnumfreekeys;
91
92 #define MEMINC  16              /* number of new free ones to get */
93
94 /*
95  * The key cache. We cache the last key we looked at here.
96  */
97 keyid_t cache_keyid;            /* key identifier */
98 u_char *cache_secret;           /* secret */
99 u_short cache_secretsize;       /* secret length */
100 int     cache_type;             /* OpenSSL digest NID */
101 u_short cache_flags;            /* flags that wave */
102 KeyAccT *cache_keyacclist;      /* key access list */
103
104
105 /*
106  * init_auth - initialize internal data
107  */
108 void
109 init_auth(void)
110 {
111         size_t newalloc;
112
113         /*
114          * Initialize hash table and free list
115          */
116         newalloc = authhashbuckets * sizeof(key_hash[0]);
117
118         key_hash = erealloc(key_hash, newalloc);
119         memset(key_hash, '\0', newalloc);
120
121         INIT_DLIST(key_listhead, llink);
122
123 #ifdef DEBUG
124         atexit(&free_auth_mem);
125 #endif
126 }
127
128
129 /*
130  * free_auth_mem - assist in leak detection by freeing all dynamic
131  *                 allocations from this module.
132  */
133 #ifdef DEBUG
134 static void
135 free_auth_mem(void)
136 {
137         symkey *        sk;
138         symkey_alloc *  alloc;
139         symkey_alloc *  next_alloc;
140
141         while (NULL != (sk = HEAD_DLIST(key_listhead, llink))) {
142                 freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]);
143         }
144         free(key_hash);
145         key_hash = NULL;
146         cache_keyid = 0;
147         cache_flags = 0;
148         cache_keyacclist = NULL;
149         for (alloc = authallocs; alloc != NULL; alloc = next_alloc) {
150                 next_alloc = alloc->link;
151                 free(alloc->mem);       
152         }
153         authfreekeys = NULL;
154         authnumfreekeys = 0;
155 }
156 #endif  /* DEBUG */
157
158
159 /*
160  * auth_moremem - get some more free key structures
161  */
162 void
163 auth_moremem(
164         int     keycount
165         )
166 {
167         symkey *        sk;
168         int             i;
169 #ifdef DEBUG
170         void *          base;
171         symkey_alloc *  allocrec;
172 # define MOREMEM_EXTRA_ALLOC    (sizeof(*allocrec))
173 #else
174 # define MOREMEM_EXTRA_ALLOC    (0)
175 #endif
176
177         i = (keycount > 0)
178                 ? keycount
179                 : MEMINC;
180         sk = emalloc_zero(i * sizeof(*sk) + MOREMEM_EXTRA_ALLOC);
181 #ifdef DEBUG
182         base = sk;
183 #endif
184         authnumfreekeys += i;
185
186         for (; i > 0; i--, sk++) {
187                 LINK_SLIST(authfreekeys, sk, llink.f);
188         }
189
190 #ifdef DEBUG
191         allocrec = (void *)sk;
192         allocrec->mem = base;
193         LINK_SLIST(authallocs, allocrec, link);
194 #endif
195 }
196
197
198 /*
199  * auth_prealloc_symkeys
200  */
201 void
202 auth_prealloc_symkeys(
203         int     keycount
204         )
205 {
206         int     allocated;
207         int     additional;
208
209         allocated = authnumkeys + authnumfreekeys;
210         additional = keycount - allocated;
211         if (additional > 0)
212                 auth_moremem(additional);
213         auth_resize_hashtable();
214 }
215
216
217 static u_short
218 auth_log2(size_t x)
219 {
220         /*
221         ** bithack to calculate floor(log2(x))
222         **
223         ** This assumes
224         **   - (sizeof(size_t) is a power of two
225         **   - CHAR_BITS is a power of two
226         **   - returning zero for arguments <= 0 is OK.
227         **
228         ** Does only shifts, masks and sums in integer arithmetic in
229         ** log2(CHAR_BIT*sizeof(size_t)) steps. (that is, 5/6 steps for
230         ** 32bit/64bit size_t)
231         */
232         int     s;
233         int     r = 0;
234         size_t  m = ~(size_t)0;
235
236         for (s = sizeof(size_t) / 2 * CHAR_BIT; s != 0; s >>= 1) {
237                 m <<= s;
238                 if (x & m)
239                         r += s;
240                 else
241                         x <<= s;
242         }
243         return (u_short)r;
244 }
245
246
247 /*
248  * auth_resize_hashtable
249  *
250  * Size hash table to average 4 or fewer entries per bucket initially,
251  * within the bounds of at least 4 and no more than 15 bits for the hash
252  * table index.  Populate the hash table.
253  */
254 static void
255 auth_resize_hashtable(void)
256 {
257         u_long          totalkeys;
258         u_short         hashbits;
259         u_short         hash;
260         size_t          newalloc;
261         symkey *        sk;
262
263         totalkeys = authnumkeys + authnumfreekeys;
264         hashbits = auth_log2(totalkeys / 4) + 1;
265         hashbits = max(4, hashbits);
266         hashbits = min(15, hashbits);
267
268         authhashbuckets = 1 << hashbits;
269         authhashmask = authhashbuckets - 1;
270         newalloc = authhashbuckets * sizeof(key_hash[0]);
271
272         key_hash = erealloc(key_hash, newalloc);
273         memset(key_hash, '\0', newalloc);
274
275         ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
276                 hash = KEYHASH(sk->keyid);
277                 LINK_SLIST(key_hash[hash], sk, hlink);
278         ITER_DLIST_END()
279 }
280
281
282 /*
283  * allocsymkey - common code to allocate and link in symkey
284  *
285  * secret must be allocated with a free-compatible allocator.  It is
286  * owned by the referring symkey structure, and will be free()d by
287  * freesymkey().
288  */
289 static void
290 allocsymkey(
291         symkey **       bucket,
292         keyid_t         id,
293         u_short         flags,
294         u_short         type,
295         u_long          lifetime,
296         u_short         secretsize,
297         u_char *        secret,
298         KeyAccT *       ka
299         )
300 {
301         symkey *        sk;
302
303         if (authnumfreekeys < 1)
304                 auth_moremem(-1);
305         UNLINK_HEAD_SLIST(sk, authfreekeys, llink.f);
306         DEBUG_ENSURE(sk != NULL);
307         sk->keyid = id;
308         sk->flags = flags;
309         sk->type = type;
310         sk->secretsize = secretsize;
311         sk->secret = secret;
312         sk->keyacclist = ka;
313         sk->lifetime = lifetime;
314         LINK_SLIST(*bucket, sk, hlink);
315         LINK_TAIL_DLIST(key_listhead, sk, llink);
316         authnumfreekeys--;
317         authnumkeys++;
318 }
319
320
321 /*
322  * freesymkey - common code to remove a symkey and recycle its entry.
323  */
324 static void
325 freesymkey(
326         symkey *        sk,
327         symkey **       bucket
328         )
329 {
330         symkey *        unlinked;
331
332         if (sk->secret != NULL) {
333                 memset(sk->secret, '\0', sk->secretsize);
334                 free(sk->secret);
335         }
336         UNLINK_SLIST(unlinked, *bucket, sk, hlink, symkey);
337         DEBUG_ENSURE(sk == unlinked);
338         UNLINK_DLIST(sk, llink);
339         memset((char *)sk + offsetof(symkey, symkey_payload), '\0',
340                sizeof(*sk) - offsetof(symkey, symkey_payload));
341         LINK_SLIST(authfreekeys, sk, llink.f);
342         authnumkeys--;
343         authnumfreekeys++;
344 }
345
346
347 /*
348  * auth_findkey - find a key in the hash table
349  */
350 struct savekey *
351 auth_findkey(
352         keyid_t         id
353         )
354 {
355         symkey *        sk;
356
357         for (sk = key_hash[KEYHASH(id)]; sk != NULL; sk = sk->hlink) {
358                 if (id == sk->keyid) {
359                         return sk;
360                 }
361         }
362
363         return NULL;
364 }
365
366
367 /*
368  * auth_havekey - return TRUE if the key id is zero or known
369  */
370 int
371 auth_havekey(
372         keyid_t         id
373         )
374 {
375         symkey *        sk;
376
377         if (0 == id || cache_keyid == id) {
378                 return TRUE;
379         }
380
381         for (sk = key_hash[KEYHASH(id)]; sk != NULL; sk = sk->hlink) {
382                 if (id == sk->keyid) {
383                         return TRUE;
384                 }
385         }
386
387         return FALSE;
388 }
389
390
391 /*
392  * authhavekey - return TRUE and cache the key, if zero or both known
393  *               and trusted.
394  */
395 int
396 authhavekey(
397         keyid_t         id
398         )
399 {
400         symkey *        sk;
401
402         authkeylookups++;
403         if (0 == id || cache_keyid == id) {
404                 return TRUE;
405         }
406
407         /*
408          * Seach the bin for the key. If found and the key type
409          * is zero, somebody marked it trusted without specifying
410          * a key or key type. In this case consider the key missing.
411          */
412         authkeyuncached++;
413         for (sk = key_hash[KEYHASH(id)]; sk != NULL; sk = sk->hlink) {
414                 if (id == sk->keyid) {
415                         if (0 == sk->type) {
416                                 authkeynotfound++;
417                                 return FALSE;
418                         }
419                         break;
420                 }
421         }
422
423         /*
424          * If the key is not found, or if it is found but not trusted,
425          * the key is not considered found.
426          */
427         if (NULL == sk) {
428                 authkeynotfound++;
429                 return FALSE;
430         }
431         if (!(KEY_TRUSTED & sk->flags)) {
432                 authnokey++;
433                 return FALSE;
434         }
435
436         /*
437          * The key is found and trusted. Initialize the key cache.
438          */
439         cache_keyid = sk->keyid;
440         cache_type = sk->type;
441         cache_flags = sk->flags;
442         cache_secret = sk->secret;
443         cache_secretsize = sk->secretsize;
444         cache_keyacclist = sk->keyacclist;
445
446         return TRUE;
447 }
448
449
450 /*
451  * authtrust - declare a key to be trusted/untrusted
452  */
453 void
454 authtrust(
455         keyid_t         id,
456         u_long          trust
457         )
458 {
459         symkey **       bucket;
460         symkey *        sk;
461         u_long          lifetime;
462
463         /*
464          * Search bin for key; if it does not exist and is untrusted,
465          * forget it.
466          */
467         bucket = &key_hash[KEYHASH(id)];
468         for (sk = *bucket; sk != NULL; sk = sk->hlink) {
469                 if (id == sk->keyid)
470                         break;
471         }
472         if (!trust && NULL == sk)
473                 return;
474
475         /*
476          * There are two conditions remaining. Either it does not
477          * exist and is to be trusted or it does exist and is or is
478          * not to be trusted.
479          */     
480         if (sk != NULL) {
481                 if (cache_keyid == id) {
482                         cache_flags = 0;
483                         cache_keyid = 0;
484                         cache_keyacclist = NULL;
485                 }
486
487                 /*
488                  * Key exists. If it is to be trusted, say so and
489                  * update its lifetime. 
490                  */
491                 if (trust > 0) {
492                         sk->flags |= KEY_TRUSTED;
493                         if (trust > 1)
494                                 sk->lifetime = current_time + trust;
495                         else
496                                 sk->lifetime = 0;
497                         return;
498                 }
499
500                 /* No longer trusted, return it to the free list. */
501                 freesymkey(sk, bucket);
502                 return;
503         }
504
505         /*
506          * keyid is not present, but the is to be trusted.  We allocate
507          * a new key, but do not specify a key type or secret.
508          */
509         if (trust > 1) {
510                 lifetime = current_time + trust;
511         } else {
512                 lifetime = 0;
513         }
514         allocsymkey(bucket, id, KEY_TRUSTED, 0, lifetime, 0, NULL, NULL);
515 }
516
517
518 /*
519  * authistrusted - determine whether a key is trusted
520  */
521 int
522 authistrusted(
523         keyid_t         keyno
524         )
525 {
526         symkey *        sk;
527         symkey **       bucket;
528
529         if (keyno == cache_keyid)
530                 return !!(KEY_TRUSTED & cache_flags);
531
532         authkeyuncached++;
533         bucket = &key_hash[KEYHASH(keyno)];
534         for (sk = *bucket; sk != NULL; sk = sk->hlink) {
535                 if (keyno == sk->keyid)
536                         break;
537         }
538         if (NULL == sk || !(KEY_TRUSTED & sk->flags)) {
539                 authkeynotfound++;
540                 return FALSE;
541         }
542         return TRUE;
543 }
544
545
546 /*
547  * authistrustedip - determine if the IP is OK for the keyid
548  */
549  int
550  authistrustedip(
551         keyid_t         keyno,
552         sockaddr_u *    sau
553         )
554 {
555         symkey *        sk;
556         symkey **       bucket;
557         KeyAccT *       kal;
558         KeyAccT *       k;
559
560         if (keyno == cache_keyid)
561                 kal = cache_keyacclist;
562         else {
563                 authkeyuncached++;
564                 bucket = &key_hash[KEYHASH(keyno)];
565                 for (sk = *bucket; sk != NULL; sk = sk->hlink) {
566                         if (keyno == sk->keyid)
567                                 break;
568                 }
569                 if (NULL == sk || !(KEY_TRUSTED & sk->flags)) {
570                         INSIST(!"authistrustedip: keyid not found/trusted!");
571                         return FALSE;
572                 }
573                 kal = sk->keyacclist;
574         }
575
576         if (NULL == kal)
577                 return TRUE;
578
579         for (k = kal; k; k = k->next) {
580                 if (SOCK_EQ(&k->addr, sau))
581                         return TRUE;
582         }
583
584         return FALSE;
585 }
586
587
588 /* Note: There are two locations below where 'strncpy()' is used. While
589  * this function is a hazard by itself, it's essential that it is used
590  * here. Bug 1243 involved that the secret was filled with NUL bytes
591  * after the first NUL encountered, and 'strlcpy()' simply does NOT have
592  * this behaviour. So disabling the fix and reverting to the buggy
593  * behaviour due to compatibility issues MUST also fill with NUL and
594  * this needs 'strncpy'. Also, the secret is managed as a byte blob of a
595  * given size, and eventually truncating it and replacing the last byte
596  * with a NUL would be a bug.
597  * perlinger@ntp.org 2015-10-10
598  */
599 void
600 MD5auth_setkey(
601         keyid_t keyno,
602         int     keytype,
603         const u_char *key,
604         size_t  len,
605         KeyAccT *ka
606         )
607 {
608         symkey *        sk;
609         symkey **       bucket;
610         u_char *        secret;
611         size_t          secretsize;
612         
613         DEBUG_ENSURE(keytype <= USHRT_MAX);
614         DEBUG_ENSURE(len < 4 * 1024);
615         /*
616          * See if we already have the key.  If so just stick in the
617          * new value.
618          */
619         bucket = &key_hash[KEYHASH(keyno)];
620         for (sk = *bucket; sk != NULL; sk = sk->hlink) {
621                 if (keyno == sk->keyid) {
622                         /* TALOS-CAN-0054: make sure we have a new buffer! */
623                         if (NULL != sk->secret) {
624                                 memset(sk->secret, 0, sk->secretsize);
625                                 free(sk->secret);
626                         }
627                         sk->secret = emalloc(len);
628                         sk->type = (u_short)keytype;
629                         secretsize = len;
630                         sk->secretsize = (u_short)secretsize;
631                         sk->keyacclist = ka;
632 #ifndef DISABLE_BUG1243_FIX
633                         memcpy(sk->secret, key, secretsize);
634 #else
635                         /* >MUST< use 'strncpy()' here! See above! */
636                         strncpy((char *)sk->secret, (const char *)key,
637                                 secretsize);
638 #endif
639                         if (cache_keyid == keyno) {
640                                 cache_flags = 0;
641                                 cache_keyid = 0;
642                                 cache_keyacclist = NULL;
643                         }
644                         return;
645                 }
646         }
647
648         /*
649          * Need to allocate new structure.  Do it.
650          */
651         secretsize = len;
652         secret = emalloc(secretsize);
653 #ifndef DISABLE_BUG1243_FIX
654         memcpy(secret, key, secretsize);
655 #else
656         /* >MUST< use 'strncpy()' here! See above! */
657         strncpy((char *)secret, (const char *)key, secretsize);
658 #endif
659         allocsymkey(bucket, keyno, 0, (u_short)keytype, 0,
660                     (u_short)secretsize, secret, ka);
661 #ifdef DEBUG
662         if (debug >= 4) {
663                 size_t  j;
664
665                 printf("auth_setkey: key %d type %d len %d ", (int)keyno,
666                     keytype, (int)secretsize);
667                 for (j = 0; j < secretsize; j++)
668                         printf("%02x", secret[j]);
669                 printf("\n");
670         }       
671 #endif
672 }
673
674
675 /*
676  * auth_delkeys - delete non-autokey untrusted keys, and clear all info
677  *                except the trusted bit of non-autokey trusted keys, in
678  *                preparation for rereading the keys file.
679  */
680 void
681 auth_delkeys(void)
682 {
683         symkey *        sk;
684
685         ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
686                 if (sk->keyid > NTP_MAXKEY) {   /* autokey */
687                         continue;
688                 }
689
690                 /*
691                  * Don't lose info as to which keys are trusted. Make
692                  * sure there are no dangling pointers!
693                  */
694                 if (KEY_TRUSTED & sk->flags) {
695                         if (sk->secret != NULL) {
696                                 memset(sk->secret, 0, sk->secretsize);
697                                 free(sk->secret);
698                                 sk->secret = NULL; /* TALOS-CAN-0054 */
699                         }
700                         sk->secretsize = 0;
701                         sk->lifetime = 0;
702                 } else {
703                         freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]);
704                 }
705         ITER_DLIST_END()
706 }
707
708
709 /*
710  * auth_agekeys - delete keys whose lifetimes have expired
711  */
712 void
713 auth_agekeys(void)
714 {
715         symkey *        sk;
716
717         ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
718                 if (sk->lifetime > 0 && current_time > sk->lifetime) {
719                         freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]);
720                         authkeyexpired++;
721                 }
722         ITER_DLIST_END()
723         DPRINTF(1, ("auth_agekeys: at %lu keys %lu expired %lu\n",
724                     current_time, authnumkeys, authkeyexpired));
725 }
726
727
728 /*
729  * authencrypt - generate message authenticator
730  *
731  * Returns length of authenticator field, zero if key not found.
732  */
733 size_t
734 authencrypt(
735         keyid_t         keyno,
736         u_int32 *       pkt,
737         size_t          length
738         )
739 {
740         /*
741          * A zero key identifier means the sender has not verified
742          * the last message was correctly authenticated. The MAC
743          * consists of a single word with value zero.
744          */
745         authencryptions++;
746         pkt[length / 4] = htonl(keyno);
747         if (0 == keyno) {
748                 return 4;
749         }
750         if (!authhavekey(keyno)) {
751                 return 0;
752         }
753
754         return MD5authencrypt(cache_type, cache_secret, pkt, length);
755 }
756
757
758 /*
759  * authdecrypt - verify message authenticator
760  *
761  * Returns TRUE if authenticator valid, FALSE if invalid or not found.
762  */
763 int
764 authdecrypt(
765         keyid_t         keyno,
766         u_int32 *       pkt,
767         size_t          length,
768         size_t          size
769         )
770 {
771         /*
772          * A zero key identifier means the sender has not verified
773          * the last message was correctly authenticated.  For our
774          * purpose this is an invalid authenticator.
775          */
776         authdecryptions++;
777         if (0 == keyno || !authhavekey(keyno) || size < 4) {
778                 return FALSE;
779         }
780
781         return MD5authdecrypt(cache_type, cache_secret, pkt, length,
782                               size);
783 }