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