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,
118 unsigned int subnetbits
121 KeyAccT * node = emalloc(sizeof(KeyAccT));
123 memcpy(&node->addr, addr, sizeof(sockaddr_u));
124 node->subnetbits = subnetbits;
130 /* ----------------------------------------------------------------- */
131 /* pop and deallocate the first node of a list of access nodes, if
132 * the list is not empty. Returns the tail of the list.
139 KeyAccT * next = NULL;
147 /* ----------------------------------------------------------------- */
148 /* deallocate the list; returns an empty list. */
155 head = keyacc_pop_free(head);
159 /* ----------------------------------------------------------------- */
160 /* scan a list to see if it contains a given address. Return the
161 * default result value in case of an empty list.
166 const sockaddr_u *addr,
171 if (keyacc_amatch(&head->addr, addr,
174 } while (NULL != (head = head->next));
182 # error "don't know how to handle bytes with that bit size"
185 /* ----------------------------------------------------------------- */
186 /* check two addresses for a match, taking a prefix length into account
187 * when doing the compare.
189 * The ISC lib contains a similar function with not entirely specified
190 * semantics, so it seemed somewhat cleaner to do this from scratch.
192 * Note 1: It *is* assumed that the addresses are stored in network byte
193 * order, that is, most significant byte first!
195 * Note 2: "no address" compares unequal to all other addresses, even to
196 * itself. This has the same semantics as NaNs have for floats: *any*
197 * relational or equality operation involving a NaN returns FALSE, even
198 * equality with itself. "no address" is either a NULL pointer argument
199 * or an address of type AF_UNSPEC.
203 const sockaddr_u * a1,
204 const sockaddr_u * a2,
213 /* 1st check: If any address is not an address, it's inequal. */
214 if ( !a1 || (AF_UNSPEC == AF(a1)) ||
215 !a2 || (AF_UNSPEC == AF(a2)) )
218 /* We could check pointers for equality here and shortcut the
219 * other checks if we find object identity. But that use case is
220 * too rare to care for it.
223 /* 2nd check: Address families must be the same. */
224 if (AF(a1) != AF(a2))
227 /* type check: address family determines buffer & size */
230 /* IPv4 is easy: clamp size, get byte pointers */
231 if (mbits > sizeof(NSRCADR(a1)) * 8)
232 mbits = sizeof(NSRCADR(a1)) * 8;
233 pm1 = (const void*)&NSRCADR(a1);
234 pm2 = (const void*)&NSRCADR(a2);
238 /* IPv6 is slightly different: Both scopes must match,
239 * too, before we even consider doing a match!
241 if ( ! SCOPE_EQ(a1, a2))
243 if (mbits > sizeof(NSRCADR6(a1)) * 8)
244 mbits = sizeof(NSRCADR6(a1)) * 8;
245 pm1 = (const void*)&NSRCADR6(a1);
246 pm2 = (const void*)&NSRCADR6(a2);
250 /* don't know how to compare that!?! */
254 /* Split bit length into byte length and partial byte mask.
255 * Note that the byte mask extends from the MSB of a byte down,
256 * and that zero shift (--> mbits % 8 == 0) results in an
259 msk = 0xFFu ^ (0xFFu >> (mbits & 7));
262 /* 3rd check: Do memcmp() over full bytes, if any */
263 if (len && memcmp(pm1, pm2, len))
266 /* 4th check: compare last incomplete byte, if any */
267 if (msk && ((pm1[len] ^ pm2[len]) & msk))
270 /* If none of the above failed, we're successfully through. */
275 * init_auth - initialize internal data
283 * Initialize hash table and free list
285 newalloc = authhashbuckets * sizeof(key_hash[0]);
287 key_hash = erealloc(key_hash, newalloc);
288 memset(key_hash, '\0', newalloc);
290 INIT_DLIST(key_listhead, llink);
293 atexit(&free_auth_mem);
299 * free_auth_mem - assist in leak detection by freeing all dynamic
300 * allocations from this module.
307 symkey_alloc * alloc;
308 symkey_alloc * next_alloc;
310 while (NULL != (sk = HEAD_DLIST(key_listhead, llink))) {
317 cache_keyacclist = NULL;
318 for (alloc = authallocs; alloc != NULL; alloc = next_alloc) {
319 next_alloc = alloc->link;
329 * auth_moremem - get some more free key structures
340 symkey_alloc * allocrec;
341 # define MOREMEM_EXTRA_ALLOC (sizeof(*allocrec))
343 # define MOREMEM_EXTRA_ALLOC (0)
349 sk = eallocarrayxz(i, sizeof(*sk), MOREMEM_EXTRA_ALLOC);
353 authnumfreekeys += i;
355 for (; i > 0; i--, sk++) {
356 LINK_SLIST(authfreekeys, sk, llink.f);
360 allocrec = (void *)sk;
361 allocrec->mem = base;
362 LINK_SLIST(authallocs, allocrec, link);
368 * auth_prealloc_symkeys
371 auth_prealloc_symkeys(
378 allocated = authnumkeys + authnumfreekeys;
379 additional = keycount - allocated;
381 auth_moremem(additional);
382 auth_resize_hashtable();
390 ** bithack to calculate floor(log2(x))
393 ** - (sizeof(size_t) is a power of two
394 ** - CHAR_BITS is a power of two
395 ** - returning zero for arguments <= 0 is OK.
397 ** Does only shifts, masks and sums in integer arithmetic in
398 ** log2(CHAR_BIT*sizeof(size_t)) steps. (that is, 5/6 steps for
399 ** 32bit/64bit size_t)
403 size_t m = ~(size_t)0;
405 for (s = sizeof(size_t) / 2 * CHAR_BIT; s != 0; s >>= 1) {
416 ipaddr_match_masked(const sockaddr_u *,const sockaddr_u *,
424 if (cache_keyid == id) {
429 cache_secretsize = 0;
430 cache_keyacclist = NULL;
436 * auth_resize_hashtable
438 * Size hash table to average 4 or fewer entries per bucket initially,
439 * within the bounds of at least 4 and no more than 15 bits for the hash
440 * table index. Populate the hash table.
443 auth_resize_hashtable(void)
451 totalkeys = authnumkeys + authnumfreekeys;
452 hashbits = auth_log2(totalkeys / 4) + 1;
453 hashbits = max(4, hashbits);
454 hashbits = min(15, hashbits);
456 authhashbuckets = 1 << hashbits;
457 authhashmask = authhashbuckets - 1;
458 newalloc = authhashbuckets * sizeof(key_hash[0]);
460 key_hash = erealloc(key_hash, newalloc);
461 memset(key_hash, '\0', newalloc);
463 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
464 hash = KEYHASH(sk->keyid);
465 LINK_SLIST(key_hash[hash], sk, hlink);
471 * allocsymkey - common code to allocate and link in symkey
473 * secret must be allocated with a free-compatible allocator. It is
474 * owned by the referring symkey structure, and will be free()d by
491 bucket = &key_hash[KEYHASH(id)];
494 if (authnumfreekeys < 1)
496 UNLINK_HEAD_SLIST(sk, authfreekeys, llink.f);
497 DEBUG_ENSURE(sk != NULL);
501 sk->secretsize = secretsize;
504 sk->lifetime = lifetime;
505 LINK_SLIST(*bucket, sk, hlink);
506 LINK_TAIL_DLIST(key_listhead, sk, llink);
513 * freesymkey - common code to remove a symkey and recycle its entry.
526 authcache_flush_id(sk->keyid);
527 keyacc_all_free(sk->keyacclist);
529 bucket = &key_hash[KEYHASH(sk->keyid)];
530 if (sk->secret != NULL) {
531 memset(sk->secret, '\0', sk->secretsize);
534 UNLINK_SLIST(unlinked, *bucket, sk, hlink, symkey);
535 DEBUG_ENSURE(sk == unlinked);
536 UNLINK_DLIST(sk, llink);
537 memset((char *)sk + offsetof(symkey, symkey_payload), '\0',
538 sizeof(*sk) - offsetof(symkey, symkey_payload));
539 LINK_SLIST(authfreekeys, sk, llink.f);
546 * auth_findkey - find a key in the hash table
555 for (sk = key_hash[KEYHASH(id)]; sk != NULL; sk = sk->hlink)
563 * auth_havekey - return TRUE if the key id is zero or known. The
564 * key needs not to be trusted.
573 (cache_keyid == id) ||
574 (NULL != auth_findkey(id));
579 * authhavekey - return TRUE and cache the key, if zero or both known
590 if (0 == id || cache_keyid == id)
591 return !!(KEY_TRUSTED & cache_flags);
594 * Search the bin for the key. If not found, or found but the key
595 * type is zero, somebody marked it trusted without specifying a
596 * key or key type. In this case consider the key missing.
599 sk = auth_findkey(id);
600 if ((sk == NULL) || (sk->type == 0)) {
606 * If the key is not trusted, the key is not considered found.
608 if ( ! (KEY_TRUSTED & sk->flags)) {
614 * The key is found and trusted. Initialize the key cache.
616 cache_keyid = sk->keyid;
617 cache_type = sk->type;
618 cache_flags = sk->flags;
619 cache_secret = sk->secret;
620 cache_secretsize = sk->secretsize;
621 cache_keyacclist = sk->keyacclist;
628 * authtrust - declare a key to be trusted/untrusted
640 * Search bin for key; if it does not exist and is untrusted,
644 sk = auth_findkey(id);
645 if (!trust && sk == NULL)
649 * There are two conditions remaining. Either it does not
650 * exist and is to be trusted or it does exist and is or is
655 * Key exists. If it is to be trusted, say so and update
656 * its lifetime. If no longer trusted, return it to the
657 * free list. Flush the cache first to be sure there are
660 authcache_flush_id(id);
662 sk->flags |= KEY_TRUSTED;
664 sk->lifetime = current_time + trust;
674 * keyid is not present, but the is to be trusted. We allocate
675 * a new key, but do not specify a key type or secret.
678 lifetime = current_time + trust;
682 allocsymkey(id, KEY_TRUSTED, 0, lifetime, 0, NULL, NULL);
687 * authistrusted - determine whether a key is trusted
696 if (id == cache_keyid)
697 return !!(KEY_TRUSTED & cache_flags);
700 sk = auth_findkey(id);
701 if (sk == NULL || !(KEY_TRUSTED & sk->flags)) {
710 * authistrustedip - determine if the IP is OK for the keyid
720 if (keyno == cache_keyid) {
721 return (KEY_TRUSTED & cache_flags) &&
722 keyacc_contains(cache_keyacclist, sau, TRUE);
725 if (NULL != (sk = auth_findkey(keyno))) {
727 return (KEY_TRUSTED & sk->flags) &&
728 keyacc_contains(sk->keyacclist, sau, TRUE);
735 /* Note: There are two locations below where 'strncpy()' is used. While
736 * this function is a hazard by itself, it's essential that it is used
737 * here. Bug 1243 involved that the secret was filled with NUL bytes
738 * after the first NUL encountered, and 'strlcpy()' simply does NOT have
739 * this behaviour. So disabling the fix and reverting to the buggy
740 * behaviour due to compatibility issues MUST also fill with NUL and
741 * this needs 'strncpy'. Also, the secret is managed as a byte blob of a
742 * given size, and eventually truncating it and replacing the last byte
743 * with a NUL would be a bug.
744 * perlinger@ntp.org 2015-10-10
758 DEBUG_ENSURE(keytype <= USHRT_MAX);
759 DEBUG_ENSURE(secretsize < 4 * 1024);
761 * See if we already have the key. If so just stick in the
764 sk = auth_findkey(keyno);
765 if (sk != NULL && keyno == sk->keyid) {
766 /* TALOS-CAN-0054: make sure we have a new buffer! */
767 if (NULL != sk->secret) {
768 memset(sk->secret, 0, sk->secretsize);
771 sk->secret = emalloc(secretsize + 1);
772 sk->type = (u_short)keytype;
773 sk->secretsize = secretsize;
774 /* make sure access lists don't leak here! */
775 if (ka != sk->keyacclist) {
776 keyacc_all_free(sk->keyacclist);
779 #ifndef DISABLE_BUG1243_FIX
780 memcpy(sk->secret, key, secretsize);
782 /* >MUST< use 'strncpy()' here! See above! */
783 strncpy((char *)sk->secret, (const char *)key,
786 authcache_flush_id(keyno);
791 * Need to allocate new structure. Do it.
793 secret = emalloc(secretsize + 1);
794 #ifndef DISABLE_BUG1243_FIX
795 memcpy(secret, key, secretsize);
797 /* >MUST< use 'strncpy()' here! See above! */
798 strncpy((char *)secret, (const char *)key, secretsize);
800 allocsymkey(keyno, 0, (u_short)keytype, 0,
801 secretsize, secret, ka);
806 printf("auth_setkey: key %d type %d len %d ", (int)keyno,
807 keytype, (int)secretsize);
808 for (j = 0; j < secretsize; j++) {
809 printf("%02x", secret[j]);
818 * auth_delkeys - delete non-autokey untrusted keys, and clear all info
819 * except the trusted bit of non-autokey trusted keys, in
820 * preparation for rereading the keys file.
827 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
828 if (sk->keyid > NTP_MAXKEY) { /* autokey */
833 * Don't lose info as to which keys are trusted. Make
834 * sure there are no dangling pointers!
836 if (KEY_TRUSTED & sk->flags) {
837 if (sk->secret != NULL) {
838 memset(sk->secret, 0, sk->secretsize);
840 sk->secret = NULL; /* TALOS-CAN-0054 */
842 sk->keyacclist = keyacc_all_free(sk->keyacclist);
853 * auth_agekeys - delete keys whose lifetimes have expired
860 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
861 if (sk->lifetime > 0 && current_time > sk->lifetime) {
866 DPRINTF(1, ("auth_agekeys: at %lu keys %lu expired %lu\n",
867 current_time, authnumkeys, authkeyexpired));
872 * authencrypt - generate message authenticator
874 * Returns length of authenticator field, zero if key not found.
884 * A zero key identifier means the sender has not verified
885 * the last message was correctly authenticated. The MAC
886 * consists of a single word with value zero.
889 pkt[length / 4] = htonl(keyno);
893 if (!authhavekey(keyno)) {
897 return MD5authencrypt(cache_type,
898 cache_secret, cache_secretsize,
904 * authdecrypt - verify message authenticator
906 * Returns TRUE if authenticator valid, FALSE if invalid or not found.
917 * A zero key identifier means the sender has not verified
918 * the last message was correctly authenticated. For our
919 * purpose this is an invalid authenticator.
922 if (0 == keyno || !authhavekey(keyno) || size < 4) {
926 return MD5authdecrypt(cache_type,
927 cache_secret, cache_secretsize,