2 * authkeys.c - routines to manage the storage of authentication keys
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"
21 * Structure to store keys in in the hash table.
23 typedef struct savekey symkey;
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 size_t secretsize; /* secret octets */
34 u_short flags; /* KEY_ flags that wave */
37 /* define the payload region of symkey beyond the list pointers */
38 #define symkey_payload secret
40 #define KEY_TRUSTED 0x001 /* this key is trusted */
43 typedef struct symkey_alloc_tag symkey_alloc;
45 struct symkey_alloc_tag {
47 void * mem; /* enable free() atexit */
50 symkey_alloc * authallocs;
53 static u_short auth_log2(size_t);
54 static void auth_resize_hashtable(void);
55 static void allocsymkey(keyid_t, u_short,
56 u_short, u_long, size_t, u_char *, KeyAccT *);
57 static void freesymkey(symkey *);
59 static void free_auth_mem(void);
62 symkey key_listhead; /* list of all in-use keys */;
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.
67 #define DEF_AUTHHASHSIZE 64
68 /*#define HASHMASK ((HASHSIZE)-1)*/
69 #define KEYHASH(keyid) ((keyid) & authhashmask)
72 u_short authhashbuckets = DEF_AUTHHASHSIZE;
73 u_short authhashmask = DEF_AUTHHASHSIZE - 1;
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 */
86 * Storage for free symkey structures. We malloc() such things but
92 #define MEMINC 16 /* number of new free ones to get */
95 * The key cache. We cache the last key we looked at here.
96 * Note: this should hold the last *trusted* key. Also the
97 * cache is only loaded when the digest type / MAC algorithm
100 keyid_t cache_keyid; /* key identifier */
101 u_char *cache_secret; /* secret */
102 size_t cache_secretsize; /* secret length */
103 int cache_type; /* OpenSSL digest NID */
104 u_short cache_flags; /* flags that wave */
105 KeyAccT *cache_keyacclist; /* key access list */
107 /* --------------------------------------------------------------------
108 * manage key access lists
109 * --------------------------------------------------------------------
111 /* allocate and populate new access node and pushes it on the list.
112 * Returns the new head.
117 const sockaddr_u * addr
120 KeyAccT * node = emalloc(sizeof(KeyAccT));
122 memcpy(&node->addr, addr, sizeof(sockaddr_u));
127 /* ----------------------------------------------------------------- */
128 /* pop and deallocate the first node of a list of access nodes, if
129 * the list is not empty. Returns the tail of the list.
136 KeyAccT * next = NULL;
144 /* ----------------------------------------------------------------- */
145 /* deallocate the list; returns an empty list. */
152 head = keyacc_pop_free(head);
156 /* ----------------------------------------------------------------- */
157 /* scan a list to see if it contains a given address. Return the
158 * default result value in case of an empty list.
163 const sockaddr_u *addr,
168 if (SOCK_EQ(&head->addr, addr))
170 } while (NULL != (head = head->next));
179 * init_auth - initialize internal data
187 * Initialize hash table and free list
189 newalloc = authhashbuckets * sizeof(key_hash[0]);
191 key_hash = erealloc(key_hash, newalloc);
192 memset(key_hash, '\0', newalloc);
194 INIT_DLIST(key_listhead, llink);
197 atexit(&free_auth_mem);
203 * free_auth_mem - assist in leak detection by freeing all dynamic
204 * allocations from this module.
211 symkey_alloc * alloc;
212 symkey_alloc * next_alloc;
214 while (NULL != (sk = HEAD_DLIST(key_listhead, llink))) {
221 cache_keyacclist = NULL;
222 for (alloc = authallocs; alloc != NULL; alloc = next_alloc) {
223 next_alloc = alloc->link;
233 * auth_moremem - get some more free key structures
244 symkey_alloc * allocrec;
245 # define MOREMEM_EXTRA_ALLOC (sizeof(*allocrec))
247 # define MOREMEM_EXTRA_ALLOC (0)
253 sk = eallocarrayxz(i, sizeof(*sk), MOREMEM_EXTRA_ALLOC);
257 authnumfreekeys += i;
259 for (; i > 0; i--, sk++) {
260 LINK_SLIST(authfreekeys, sk, llink.f);
264 allocrec = (void *)sk;
265 allocrec->mem = base;
266 LINK_SLIST(authallocs, allocrec, link);
272 * auth_prealloc_symkeys
275 auth_prealloc_symkeys(
282 allocated = authnumkeys + authnumfreekeys;
283 additional = keycount - allocated;
285 auth_moremem(additional);
286 auth_resize_hashtable();
294 ** bithack to calculate floor(log2(x))
297 ** - (sizeof(size_t) is a power of two
298 ** - CHAR_BITS is a power of two
299 ** - returning zero for arguments <= 0 is OK.
301 ** Does only shifts, masks and sums in integer arithmetic in
302 ** log2(CHAR_BIT*sizeof(size_t)) steps. (that is, 5/6 steps for
303 ** 32bit/64bit size_t)
307 size_t m = ~(size_t)0;
309 for (s = sizeof(size_t) / 2 * CHAR_BIT; s != 0; s >>= 1) {
324 if (cache_keyid == id) {
329 cache_secretsize = 0;
330 cache_keyacclist = NULL;
336 * auth_resize_hashtable
338 * Size hash table to average 4 or fewer entries per bucket initially,
339 * within the bounds of at least 4 and no more than 15 bits for the hash
340 * table index. Populate the hash table.
343 auth_resize_hashtable(void)
351 totalkeys = authnumkeys + authnumfreekeys;
352 hashbits = auth_log2(totalkeys / 4) + 1;
353 hashbits = max(4, hashbits);
354 hashbits = min(15, hashbits);
356 authhashbuckets = 1 << hashbits;
357 authhashmask = authhashbuckets - 1;
358 newalloc = authhashbuckets * sizeof(key_hash[0]);
360 key_hash = erealloc(key_hash, newalloc);
361 memset(key_hash, '\0', newalloc);
363 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
364 hash = KEYHASH(sk->keyid);
365 LINK_SLIST(key_hash[hash], sk, hlink);
371 * allocsymkey - common code to allocate and link in symkey
373 * secret must be allocated with a free-compatible allocator. It is
374 * owned by the referring symkey structure, and will be free()d by
391 bucket = &key_hash[KEYHASH(id)];
394 if (authnumfreekeys < 1)
396 UNLINK_HEAD_SLIST(sk, authfreekeys, llink.f);
397 DEBUG_ENSURE(sk != NULL);
401 sk->secretsize = secretsize;
404 sk->lifetime = lifetime;
405 LINK_SLIST(*bucket, sk, hlink);
406 LINK_TAIL_DLIST(key_listhead, sk, llink);
413 * freesymkey - common code to remove a symkey and recycle its entry.
426 authcache_flush_id(sk->keyid);
427 keyacc_all_free(sk->keyacclist);
429 bucket = &key_hash[KEYHASH(sk->keyid)];
430 if (sk->secret != NULL) {
431 memset(sk->secret, '\0', sk->secretsize);
434 UNLINK_SLIST(unlinked, *bucket, sk, hlink, symkey);
435 DEBUG_ENSURE(sk == unlinked);
436 UNLINK_DLIST(sk, llink);
437 memset((char *)sk + offsetof(symkey, symkey_payload), '\0',
438 sizeof(*sk) - offsetof(symkey, symkey_payload));
439 LINK_SLIST(authfreekeys, sk, llink.f);
446 * auth_findkey - find a key in the hash table
455 for (sk = key_hash[KEYHASH(id)]; sk != NULL; sk = sk->hlink)
463 * auth_havekey - return TRUE if the key id is zero or known. The
464 * key needs not to be trusted.
473 (cache_keyid == id) ||
474 (NULL != auth_findkey(id));
479 * authhavekey - return TRUE and cache the key, if zero or both known
490 if (0 == id || cache_keyid == id)
491 return !!(KEY_TRUSTED & cache_flags);
494 * Search the bin for the key. If not found, or found but the key
495 * type is zero, somebody marked it trusted without specifying a
496 * key or key type. In this case consider the key missing.
499 sk = auth_findkey(id);
500 if ((sk == NULL) || (sk->type == 0)) {
506 * If the key is not trusted, the key is not considered found.
508 if ( ! (KEY_TRUSTED & sk->flags)) {
514 * The key is found and trusted. Initialize the key cache.
516 cache_keyid = sk->keyid;
517 cache_type = sk->type;
518 cache_flags = sk->flags;
519 cache_secret = sk->secret;
520 cache_secretsize = sk->secretsize;
521 cache_keyacclist = sk->keyacclist;
528 * authtrust - declare a key to be trusted/untrusted
540 * Search bin for key; if it does not exist and is untrusted,
544 sk = auth_findkey(id);
545 if (!trust && sk == NULL)
549 * There are two conditions remaining. Either it does not
550 * exist and is to be trusted or it does exist and is or is
555 * Key exists. If it is to be trusted, say so and update
556 * its lifetime. If no longer trusted, return it to the
557 * free list. Flush the cache first to be sure there are
560 authcache_flush_id(id);
562 sk->flags |= KEY_TRUSTED;
564 sk->lifetime = current_time + trust;
574 * keyid is not present, but the is to be trusted. We allocate
575 * a new key, but do not specify a key type or secret.
578 lifetime = current_time + trust;
582 allocsymkey(id, KEY_TRUSTED, 0, lifetime, 0, NULL, NULL);
587 * authistrusted - determine whether a key is trusted
596 if (id == cache_keyid)
597 return !!(KEY_TRUSTED & cache_flags);
600 sk = auth_findkey(id);
601 if (sk == NULL || !(KEY_TRUSTED & sk->flags)) {
610 * authistrustedip - determine if the IP is OK for the keyid
620 /* That specific key was already used to authenticate the
621 * packet. Therefore, the key *must* exist... There's a chance
622 * that is not trusted, though.
624 if (keyno == cache_keyid) {
625 return (KEY_TRUSTED & cache_flags) &&
626 keyacc_contains(cache_keyacclist, sau, TRUE);
629 sk = auth_findkey(keyno);
631 return (KEY_TRUSTED & sk->flags) &&
632 keyacc_contains(sk->keyacclist, sau, TRUE);
636 /* Note: There are two locations below where 'strncpy()' is used. While
637 * this function is a hazard by itself, it's essential that it is used
638 * here. Bug 1243 involved that the secret was filled with NUL bytes
639 * after the first NUL encountered, and 'strlcpy()' simply does NOT have
640 * this behaviour. So disabling the fix and reverting to the buggy
641 * behaviour due to compatibility issues MUST also fill with NUL and
642 * this needs 'strncpy'. Also, the secret is managed as a byte blob of a
643 * given size, and eventually truncating it and replacing the last byte
644 * with a NUL would be a bug.
645 * perlinger@ntp.org 2015-10-10
659 DEBUG_ENSURE(keytype <= USHRT_MAX);
660 DEBUG_ENSURE(secretsize < 4 * 1024);
662 * See if we already have the key. If so just stick in the
665 sk = auth_findkey(keyno);
666 if (sk != NULL && keyno == sk->keyid) {
667 /* TALOS-CAN-0054: make sure we have a new buffer! */
668 if (NULL != sk->secret) {
669 memset(sk->secret, 0, sk->secretsize);
672 sk->secret = emalloc(secretsize + 1);
673 sk->type = (u_short)keytype;
674 sk->secretsize = secretsize;
675 /* make sure access lists don't leak here! */
676 if (ka != sk->keyacclist) {
677 keyacc_all_free(sk->keyacclist);
680 #ifndef DISABLE_BUG1243_FIX
681 memcpy(sk->secret, key, secretsize);
683 /* >MUST< use 'strncpy()' here! See above! */
684 strncpy((char *)sk->secret, (const char *)key,
687 authcache_flush_id(keyno);
692 * Need to allocate new structure. Do it.
694 secret = emalloc(secretsize + 1);
695 #ifndef DISABLE_BUG1243_FIX
696 memcpy(secret, key, secretsize);
698 /* >MUST< use 'strncpy()' here! See above! */
699 strncpy((char *)secret, (const char *)key, secretsize);
701 allocsymkey(keyno, 0, (u_short)keytype, 0,
702 secretsize, secret, ka);
707 printf("auth_setkey: key %d type %d len %d ", (int)keyno,
708 keytype, (int)secretsize);
709 for (j = 0; j < secretsize; j++) {
710 printf("%02x", secret[j]);
719 * auth_delkeys - delete non-autokey untrusted keys, and clear all info
720 * except the trusted bit of non-autokey trusted keys, in
721 * preparation for rereading the keys file.
728 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
729 if (sk->keyid > NTP_MAXKEY) { /* autokey */
734 * Don't lose info as to which keys are trusted. Make
735 * sure there are no dangling pointers!
737 if (KEY_TRUSTED & sk->flags) {
738 if (sk->secret != NULL) {
739 memset(sk->secret, 0, sk->secretsize);
741 sk->secret = NULL; /* TALOS-CAN-0054 */
743 sk->keyacclist = keyacc_all_free(sk->keyacclist);
754 * auth_agekeys - delete keys whose lifetimes have expired
761 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
762 if (sk->lifetime > 0 && current_time > sk->lifetime) {
767 DPRINTF(1, ("auth_agekeys: at %lu keys %lu expired %lu\n",
768 current_time, authnumkeys, authkeyexpired));
773 * authencrypt - generate message authenticator
775 * Returns length of authenticator field, zero if key not found.
785 * A zero key identifier means the sender has not verified
786 * the last message was correctly authenticated. The MAC
787 * consists of a single word with value zero.
790 pkt[length / 4] = htonl(keyno);
794 if (!authhavekey(keyno)) {
798 return MD5authencrypt(cache_type, cache_secret, pkt, length);
803 * authdecrypt - verify message authenticator
805 * Returns TRUE if authenticator valid, FALSE if invalid or not found.
816 * A zero key identifier means the sender has not verified
817 * the last message was correctly authenticated. For our
818 * purpose this is an invalid authenticator.
821 if (0 == keyno || !authhavekey(keyno) || size < 4) {
825 return MD5authdecrypt(cache_type, cache_secret, pkt, length,