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"
20 * Structure to store keys in in the hash table.
22 typedef struct savekey symkey;
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 */
35 /* define the payload region of symkey beyond the list pointers */
36 #define symkey_payload secret
38 #define KEY_TRUSTED 0x001 /* this key is trusted */
41 typedef struct symkey_alloc_tag symkey_alloc;
43 struct symkey_alloc_tag {
45 void * mem; /* enable free() atexit */
48 symkey_alloc * authallocs;
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 **);
57 static void free_auth_mem(void);
60 symkey key_listhead; /* list of all in-use keys */;
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.
65 #define DEF_AUTHHASHSIZE 64
66 /*#define HASHMASK ((HASHSIZE)-1)*/
67 #define KEYHASH(keyid) ((keyid) & authhashmask)
70 u_short authhashbuckets = DEF_AUTHHASHSIZE;
71 u_short authhashmask = DEF_AUTHHASHSIZE - 1;
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 */
84 * Storage for free symkey structures. We malloc() such things but
90 #define MEMINC 16 /* number of new free ones to get */
93 * The key cache. We cache the last key we looked at here.
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 */
103 * init_auth - initialize internal data
111 * Initialize hash table and free list
113 newalloc = authhashbuckets * sizeof(key_hash[0]);
115 key_hash = erealloc(key_hash, newalloc);
116 memset(key_hash, '\0', newalloc);
118 INIT_DLIST(key_listhead, llink);
121 atexit(&free_auth_mem);
127 * free_auth_mem - assist in leak detection by freeing all dynamic
128 * allocations from this module.
135 symkey_alloc * alloc;
136 symkey_alloc * next_alloc;
138 while (NULL != (sk = HEAD_DLIST(key_listhead, llink))) {
139 freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]);
145 for (alloc = authallocs; alloc != NULL; alloc = next_alloc) {
146 next_alloc = alloc->link;
156 * auth_moremem - get some more free key structures
167 symkey_alloc * allocrec;
168 # define MOREMEM_EXTRA_ALLOC (sizeof(*allocrec))
170 # define MOREMEM_EXTRA_ALLOC (0)
176 sk = emalloc_zero(i * sizeof(*sk) + MOREMEM_EXTRA_ALLOC);
180 authnumfreekeys += i;
182 for (; i > 0; i--, sk++) {
183 LINK_SLIST(authfreekeys, sk, llink.f);
187 allocrec = (void *)sk;
188 allocrec->mem = base;
189 LINK_SLIST(authallocs, allocrec, link);
195 * auth_prealloc_symkeys
198 auth_prealloc_symkeys(
205 allocated = authnumkeys + authnumfreekeys;
206 additional = keycount - allocated;
208 auth_moremem(additional);
209 auth_resize_hashtable();
213 static inline u_short
216 return (u_short)(log10(x) / log10(2));
221 * auth_resize_hashtable
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.
228 auth_resize_hashtable(void)
236 totalkeys = authnumkeys + authnumfreekeys;
237 hashbits = auth_log2(totalkeys / 4.0) + 1;
238 hashbits = max(4, hashbits);
239 hashbits = min(15, hashbits);
241 authhashbuckets = 1 << hashbits;
242 authhashmask = authhashbuckets - 1;
243 newalloc = authhashbuckets * sizeof(key_hash[0]);
245 key_hash = erealloc(key_hash, newalloc);
246 memset(key_hash, '\0', newalloc);
248 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
249 hash = KEYHASH(sk->keyid);
250 LINK_SLIST(key_hash[hash], sk, hlink);
256 * allocsymkey - common code to allocate and link in symkey
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
275 if (authnumfreekeys < 1)
277 UNLINK_HEAD_SLIST(sk, authfreekeys, llink.f);
278 DEBUG_ENSURE(sk != NULL);
282 sk->secretsize = secretsize;
284 sk->lifetime = lifetime;
285 LINK_SLIST(*bucket, sk, hlink);
286 LINK_TAIL_DLIST(key_listhead, sk, llink);
293 * freesymkey - common code to remove a symkey and recycle its entry.
303 if (sk->secret != NULL) {
304 memset(sk->secret, '\0', sk->secretsize);
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);
319 * auth_findkey - find a key in the hash table
328 for (sk = key_hash[KEYHASH(id)]; sk != NULL; sk = sk->hlink) {
329 if (id == sk->keyid) {
339 * auth_havekey - return TRUE if the key id is zero or known
348 if (0 == id || cache_keyid == id) {
352 for (sk = key_hash[KEYHASH(id)]; sk != NULL; sk = sk->hlink) {
353 if (id == sk->keyid) {
363 * authhavekey - return TRUE and cache the key, if zero or both known
374 if (0 == id || cache_keyid == id) {
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.
384 for (sk = key_hash[KEYHASH(id)]; sk != NULL; sk = sk->hlink) {
385 if (id == sk->keyid) {
395 * If the key is not found, or if it is found but not trusted,
396 * the key is not considered found.
402 if (!(KEY_TRUSTED & sk->flags)) {
408 * The key is found and trusted. Initialize the key cache.
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;
421 * authtrust - declare a key to be trusted/untrusted
434 * Search bin for key; if it does not exist and is untrusted,
437 bucket = &key_hash[KEYHASH(id)];
438 for (sk = *bucket; sk != NULL; sk = sk->hlink) {
442 if (!trust && NULL == sk)
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
451 if (cache_keyid == id) {
457 * Key exists. If it is to be trusted, say so and
458 * update its lifetime.
461 sk->flags |= KEY_TRUSTED;
463 sk->lifetime = current_time + trust;
469 /* No longer trusted, return it to the free list. */
470 freesymkey(sk, bucket);
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.
479 lifetime = current_time + trust;
483 allocsymkey(bucket, id, KEY_TRUSTED, 0, lifetime, 0, NULL);
488 * authistrusted - determine whether a key is trusted
498 if (keyno == cache_keyid)
499 return !!(KEY_TRUSTED & cache_flags);
502 bucket = &key_hash[KEYHASH(keyno)];
503 for (sk = *bucket; sk != NULL; sk = sk->hlink) {
504 if (keyno == sk->keyid)
507 if (NULL == sk || !(KEY_TRUSTED & sk->flags)) {
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
538 DEBUG_ENSURE(keytype <= USHRT_MAX);
539 DEBUG_ENSURE(len < 4 * 1024);
541 * See if we already have the key. If so just stick in the
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);
552 sk->secret = emalloc(len);
553 sk->type = (u_short)keytype;
555 sk->secretsize = (u_short)secretsize;
556 #ifndef DISABLE_BUG1243_FIX
557 memcpy(sk->secret, key, secretsize);
559 /* >MUST< use 'strncpy()' here! See above! */
560 strncpy((char *)sk->secret, (const char *)key,
563 if (cache_keyid == keyno) {
572 * Need to allocate new structure. Do it.
575 secret = emalloc(secretsize);
576 #ifndef DISABLE_BUG1243_FIX
577 memcpy(secret, key, secretsize);
579 /* >MUST< use 'strncpy()' here! See above! */
580 strncpy((char *)secret, (const char *)key, secretsize);
582 allocsymkey(bucket, keyno, 0, (u_short)keytype, 0,
583 (u_short)secretsize, secret);
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]);
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.
608 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
609 if (sk->keyid > NTP_MAXKEY) { /* autokey */
614 * Don't lose info as to which keys are trusted. Make
615 * sure there are no dangling pointers!
617 if (KEY_TRUSTED & sk->flags) {
618 if (sk->secret != NULL) {
619 memset(sk->secret, 0, sk->secretsize);
621 sk->secret = NULL; /* TALOS-CAN-0054 */
626 freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]);
633 * auth_agekeys - delete keys whose lifetimes have expired
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)]);
646 DPRINTF(1, ("auth_agekeys: at %lu keys %lu expired %lu\n",
647 current_time, authnumkeys, authkeyexpired));
652 * authencrypt - generate message authenticator
654 * Returns length of authenticator field, zero if key not found.
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.
669 pkt[length / 4] = htonl(keyno);
673 if (!authhavekey(keyno)) {
677 return MD5authencrypt(cache_type, cache_secret, pkt, length);
682 * authdecrypt - verify message authenticator
684 * Returns TRUE if authenticator valid, FALSE if invalid or not found.
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.
700 if (0 == keyno || !authhavekey(keyno) || size < 4) {
704 return MD5authdecrypt(cache_type, cache_secret, pkt, length,