authkeys.c revision 293896 
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 */
22typedef struct savekey symkey;
23
24struct 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
41typedef struct symkey_alloc_tag symkey_alloc;
42
43struct symkey_alloc_tag {
44	symkey_alloc *	link;
45	void *		mem;		/* enable free() atexit */
46};
47
48symkey_alloc *	authallocs;
49#endif	/* DEBUG */
50
51static inline u_short	auth_log2(double x);
52static void		auth_resize_hashtable(void);
53static void		allocsymkey(symkey **, keyid_t,	u_short,
54				    u_short, u_long, u_short, u_char *);
55static void		freesymkey(symkey *, symkey **);
56#ifdef DEBUG
57static void		free_auth_mem(void);
58#endif
59
60symkey	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
69int	authhashdisabled;
70u_short	authhashbuckets = DEF_AUTHHASHSIZE;
71u_short authhashmask = DEF_AUTHHASHSIZE - 1;
72symkey **key_hash;
73
74u_long authkeynotfound;		/* keys not found */
75u_long authkeylookups;		/* calls to lookup keys */
76u_long authnumkeys;		/* number of active keys */
77u_long authkeyexpired;		/* key lifetime expirations */
78u_long authkeyuncached;		/* cache misses */
79u_long authnokey;		/* calls to encrypt with no key */
80u_long authencryptions;		/* calls to encrypt */
81u_long authdecryptions;		/* calls to decrypt */
82
83/*
84 * Storage for free symkey structures.  We malloc() such things but
85 * never free them.
86 */
87symkey *authfreekeys;
88int 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 */
95keyid_t	cache_keyid;		/* key identifier */
96u_char *cache_secret;		/* secret */
97u_short	cache_secretsize;	/* secret length */
98int	cache_type;		/* OpenSSL digest NID */
99u_short cache_flags;		/* flags that wave */
100
101
102/*
103 * init_auth - initialize internal data
104 */
105void
106init_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
131static void
132free_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 */
158void
159auth_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 */
197void
198auth_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
213static inline u_short
214auth_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 */
227static void
228auth_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 */
262static void
263allocsymkey(
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 */
295static void
296freesymkey(
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 */
321struct savekey *
322auth_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 */
341int
342auth_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 */
366int
367authhavekey(
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 */
423void
424authtrust(
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 */
490int
491authistrusted(
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 */
525void
526MD5auth_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 */
603void
604auth_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 */
635void
636auth_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 */
656size_t
657authencrypt(
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 */
686int
687authdecrypt(
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