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 u_short 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(symkey **, keyid_t, u_short, u_short,
56 u_long, u_short, u_char *, KeyAccT *);
57 static void freesymkey(symkey *, 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.
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 */
106 * init_auth - initialize internal data
114 * Initialize hash table and free list
116 newalloc = authhashbuckets * sizeof(key_hash[0]);
118 key_hash = erealloc(key_hash, newalloc);
119 memset(key_hash, '\0', newalloc);
121 INIT_DLIST(key_listhead, llink);
124 atexit(&free_auth_mem);
130 * free_auth_mem - assist in leak detection by freeing all dynamic
131 * allocations from this module.
138 symkey_alloc * alloc;
139 symkey_alloc * next_alloc;
141 while (NULL != (sk = HEAD_DLIST(key_listhead, llink))) {
142 freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]);
148 cache_keyacclist = NULL;
149 for (alloc = authallocs; alloc != NULL; alloc = next_alloc) {
150 next_alloc = alloc->link;
160 * auth_moremem - get some more free key structures
171 symkey_alloc * allocrec;
172 # define MOREMEM_EXTRA_ALLOC (sizeof(*allocrec))
174 # define MOREMEM_EXTRA_ALLOC (0)
180 sk = emalloc_zero(i * sizeof(*sk) + MOREMEM_EXTRA_ALLOC);
184 authnumfreekeys += i;
186 for (; i > 0; i--, sk++) {
187 LINK_SLIST(authfreekeys, sk, llink.f);
191 allocrec = (void *)sk;
192 allocrec->mem = base;
193 LINK_SLIST(authallocs, allocrec, link);
199 * auth_prealloc_symkeys
202 auth_prealloc_symkeys(
209 allocated = authnumkeys + authnumfreekeys;
210 additional = keycount - allocated;
212 auth_moremem(additional);
213 auth_resize_hashtable();
221 ** bithack to calculate floor(log2(x))
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.
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)
234 size_t m = ~(size_t)0;
236 for (s = sizeof(size_t) / 2 * CHAR_BIT; s != 0; s >>= 1) {
248 * auth_resize_hashtable
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.
255 auth_resize_hashtable(void)
263 totalkeys = authnumkeys + authnumfreekeys;
264 hashbits = auth_log2(totalkeys / 4) + 1;
265 hashbits = max(4, hashbits);
266 hashbits = min(15, hashbits);
268 authhashbuckets = 1 << hashbits;
269 authhashmask = authhashbuckets - 1;
270 newalloc = authhashbuckets * sizeof(key_hash[0]);
272 key_hash = erealloc(key_hash, newalloc);
273 memset(key_hash, '\0', newalloc);
275 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
276 hash = KEYHASH(sk->keyid);
277 LINK_SLIST(key_hash[hash], sk, hlink);
283 * allocsymkey - common code to allocate and link in symkey
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
303 if (authnumfreekeys < 1)
305 UNLINK_HEAD_SLIST(sk, authfreekeys, llink.f);
306 DEBUG_ENSURE(sk != NULL);
310 sk->secretsize = secretsize;
313 sk->lifetime = lifetime;
314 LINK_SLIST(*bucket, sk, hlink);
315 LINK_TAIL_DLIST(key_listhead, sk, llink);
322 * freesymkey - common code to remove a symkey and recycle its entry.
332 if (sk->secret != NULL) {
333 memset(sk->secret, '\0', sk->secretsize);
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);
348 * auth_findkey - find a key in the hash table
357 for (sk = key_hash[KEYHASH(id)]; sk != NULL; sk = sk->hlink) {
358 if (id == sk->keyid) {
368 * auth_havekey - return TRUE if the key id is zero or known
377 if (0 == id || cache_keyid == id) {
381 for (sk = key_hash[KEYHASH(id)]; sk != NULL; sk = sk->hlink) {
382 if (id == sk->keyid) {
392 * authhavekey - return TRUE and cache the key, if zero or both known
403 if (0 == id || cache_keyid == id) {
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.
413 for (sk = key_hash[KEYHASH(id)]; sk != NULL; sk = sk->hlink) {
414 if (id == sk->keyid) {
424 * If the key is not found, or if it is found but not trusted,
425 * the key is not considered found.
431 if (!(KEY_TRUSTED & sk->flags)) {
437 * The key is found and trusted. Initialize the key cache.
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;
451 * authtrust - declare a key to be trusted/untrusted
464 * Search bin for key; if it does not exist and is untrusted,
467 bucket = &key_hash[KEYHASH(id)];
468 for (sk = *bucket; sk != NULL; sk = sk->hlink) {
472 if (!trust && NULL == sk)
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
481 if (cache_keyid == id) {
484 cache_keyacclist = NULL;
488 * Key exists. If it is to be trusted, say so and
489 * update its lifetime.
492 sk->flags |= KEY_TRUSTED;
494 sk->lifetime = current_time + trust;
500 /* No longer trusted, return it to the free list. */
501 freesymkey(sk, bucket);
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.
510 lifetime = current_time + trust;
514 allocsymkey(bucket, id, KEY_TRUSTED, 0, lifetime, 0, NULL, NULL);
519 * authistrusted - determine whether a key is trusted
529 if (keyno == cache_keyid)
530 return !!(KEY_TRUSTED & cache_flags);
533 bucket = &key_hash[KEYHASH(keyno)];
534 for (sk = *bucket; sk != NULL; sk = sk->hlink) {
535 if (keyno == sk->keyid)
538 if (NULL == sk || !(KEY_TRUSTED & sk->flags)) {
547 * authistrustedip - determine if the IP is OK for the keyid
560 if (keyno == cache_keyid)
561 kal = cache_keyacclist;
564 bucket = &key_hash[KEYHASH(keyno)];
565 for (sk = *bucket; sk != NULL; sk = sk->hlink) {
566 if (keyno == sk->keyid)
569 if (NULL == sk || !(KEY_TRUSTED & sk->flags)) {
570 INSIST(!"authistrustedip: keyid not found/trusted!");
573 kal = sk->keyacclist;
579 for (k = kal; k; k = k->next) {
580 if (SOCK_EQ(&k->addr, sau))
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
613 DEBUG_ENSURE(keytype <= USHRT_MAX);
614 DEBUG_ENSURE(len < 4 * 1024);
616 * See if we already have the key. If so just stick in the
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);
627 sk->secret = emalloc(len);
628 sk->type = (u_short)keytype;
630 sk->secretsize = (u_short)secretsize;
632 #ifndef DISABLE_BUG1243_FIX
633 memcpy(sk->secret, key, secretsize);
635 /* >MUST< use 'strncpy()' here! See above! */
636 strncpy((char *)sk->secret, (const char *)key,
639 if (cache_keyid == keyno) {
642 cache_keyacclist = NULL;
649 * Need to allocate new structure. Do it.
652 secret = emalloc(secretsize);
653 #ifndef DISABLE_BUG1243_FIX
654 memcpy(secret, key, secretsize);
656 /* >MUST< use 'strncpy()' here! See above! */
657 strncpy((char *)secret, (const char *)key, secretsize);
659 allocsymkey(bucket, keyno, 0, (u_short)keytype, 0,
660 (u_short)secretsize, secret, ka);
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]);
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.
685 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
686 if (sk->keyid > NTP_MAXKEY) { /* autokey */
691 * Don't lose info as to which keys are trusted. Make
692 * sure there are no dangling pointers!
694 if (KEY_TRUSTED & sk->flags) {
695 if (sk->secret != NULL) {
696 memset(sk->secret, 0, sk->secretsize);
698 sk->secret = NULL; /* TALOS-CAN-0054 */
703 freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]);
710 * auth_agekeys - delete keys whose lifetimes have expired
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)]);
723 DPRINTF(1, ("auth_agekeys: at %lu keys %lu expired %lu\n",
724 current_time, authnumkeys, authkeyexpired));
729 * authencrypt - generate message authenticator
731 * Returns length of authenticator field, zero if key not found.
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.
746 pkt[length / 4] = htonl(keyno);
750 if (!authhavekey(keyno)) {
754 return MD5authencrypt(cache_type, cache_secret, pkt, length);
759 * authdecrypt - verify message authenticator
761 * Returns TRUE if authenticator valid, FALSE if invalid or not found.
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.
777 if (0 == keyno || !authhavekey(keyno) || size < 4) {
781 return MD5authdecrypt(cache_type, cache_secret, pkt, length,