xref: /freebsd/contrib/ntp/libntp/authkeys.c (revision 39ee7a7a6bdd1557b1c3532abf60d139798ac88b) 
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  */
22 typedef struct savekey symkey;
23 
24 struct 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
41 typedef struct symkey_alloc_tag symkey_alloc;
42 
43 struct symkey_alloc_tag {
44 	symkey_alloc *	link;
45 	void *		mem;		/* enable free() atexit */
46 };
47 
48 symkey_alloc *	authallocs;
49 #endif	/* DEBUG */
50 
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 **);
56 #ifdef DEBUG
57 static void		free_auth_mem(void);
58 #endif
59 
60 symkey	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 
69 int	authhashdisabled;
70 u_short	authhashbuckets = DEF_AUTHHASHSIZE;
71 u_short authhashmask = DEF_AUTHHASHSIZE - 1;
72 symkey **key_hash;
73 
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 */
82 
83 /*
84  * Storage for free symkey structures.  We malloc() such things but
85  * never free them.
86  */
87 symkey *authfreekeys;
88 int 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  */
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 */
100 
101 
102 /*
103  * init_auth - initialize internal data
104  */
105 void
106 init_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
131 static void
132 free_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  */
158 void
159 auth_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  */
197 void
198 auth_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 
213 static inline u_short
214 auth_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  */
227 static void
228 auth_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  */
262 static void
263 allocsymkey(
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  */
295 static void
296 freesymkey(
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  */
321 struct savekey *
322 auth_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  */
341 int
342 auth_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  */
366 int
367 authhavekey(
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  */
423 void
424 authtrust(
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  */
490 int
491 authistrusted(
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 
515 void
516 MD5auth_setkey(
517 	keyid_t keyno,
518 	int	keytype,
519 	const u_char *key,
520 	size_t len
521 	)
522 {
523 	symkey *	sk;
524 	symkey **	bucket;
525 	u_char *	secret;
526 	size_t		secretsize;
527 
528 	DEBUG_ENSURE(keytype <= USHRT_MAX);
529 	DEBUG_ENSURE(len < 4 * 1024);
530 	/*
531 	 * See if we already have the key.  If so just stick in the
532 	 * new value.
533 	 */
534 	bucket = &key_hash[KEYHASH(keyno)];
535 	for (sk = *bucket; sk != NULL; sk = sk->hlink) {
536 		if (keyno == sk->keyid) {
537 			/* TALOS-CAN-0054: make sure we have a new buffer! */
538 			if (NULL != sk->secret) {
539 				memset(sk->secret, 0, sk->secretsize);
540 				free(sk->secret);
541 			}
542 			sk->secret = emalloc(len);
543 			sk->type = (u_short)keytype;
544 			secretsize = len;
545 			sk->secretsize = (u_short)secretsize;
546 #ifndef DISABLE_BUG1243_FIX
547 			memcpy(sk->secret, key, secretsize);
548 #else
549 			strlcpy((char *)sk->secret, (const char *)key,
550 				secretsize);
551 #endif
552 			if (cache_keyid == keyno) {
553 				cache_flags = 0;
554 				cache_keyid = 0;
555 			}
556 			return;
557 		}
558 	}
559 
560 	/*
561 	 * Need to allocate new structure.  Do it.
562 	 */
563 	secretsize = len;
564 	secret = emalloc(secretsize);
565 #ifndef DISABLE_BUG1243_FIX
566 	memcpy(secret, key, secretsize);
567 #else
568 	strlcpy((char *)secret, (const char *)key, secretsize);
569 #endif
570 	allocsymkey(bucket, keyno, 0, (u_short)keytype, 0,
571 		    (u_short)secretsize, secret);
572 #ifdef DEBUG
573 	if (debug >= 4) {
574 		size_t	j;
575 
576 		printf("auth_setkey: key %d type %d len %d ", (int)keyno,
577 		    keytype, (int)secretsize);
578 		for (j = 0; j < secretsize; j++)
579 			printf("%02x", secret[j]);
580 		printf("\n");
581 	}
582 #endif
583 }
584 
585 
586 /*
587  * auth_delkeys - delete non-autokey untrusted keys, and clear all info
588  *                except the trusted bit of non-autokey trusted keys, in
589  *		  preparation for rereading the keys file.
590  */
591 void
592 auth_delkeys(void)
593 {
594 	symkey *	sk;
595 
596 	ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
597 		if (sk->keyid > NTP_MAXKEY) {	/* autokey */
598 			continue;
599 		}
600 
601 		/*
602 		 * Don't lose info as to which keys are trusted. Make
603 		 * sure there are no dangling pointers!
604 		 */
605 		if (KEY_TRUSTED & sk->flags) {
606 			if (sk->secret != NULL) {
607 				memset(sk->secret, 0, sk->secretsize);
608 				free(sk->secret);
609 				sk->secret = NULL; /* TALOS-CAN-0054 */
610 			}
611 			sk->secretsize = 0;
612 			sk->lifetime = 0;
613 		} else {
614 			freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]);
615 		}
616 	ITER_DLIST_END()
617 }
618 
619 
620 /*
621  * auth_agekeys - delete keys whose lifetimes have expired
622  */
623 void
624 auth_agekeys(void)
625 {
626 	symkey *	sk;
627 
628 	ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey)
629 		if (sk->lifetime > 0 && current_time > sk->lifetime) {
630 			freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]);
631 			authkeyexpired++;
632 		}
633 	ITER_DLIST_END()
634 	DPRINTF(1, ("auth_agekeys: at %lu keys %lu expired %lu\n",
635 		    current_time, authnumkeys, authkeyexpired));
636 }
637 
638 
639 /*
640  * authencrypt - generate message authenticator
641  *
642  * Returns length of authenticator field, zero if key not found.
643  */
644 int
645 authencrypt(
646 	keyid_t		keyno,
647 	u_int32 *	pkt,
648 	int		length
649 	)
650 {\
651 	/*
652 	 * A zero key identifier means the sender has not verified
653 	 * the last message was correctly authenticated. The MAC
654 	 * consists of a single word with value zero.
655 	 */
656 	authencryptions++;
657 	pkt[length / 4] = htonl(keyno);
658 	if (0 == keyno) {
659 		return 4;
660 	}
661 	if (!authhavekey(keyno)) {
662 		return 0;
663 	}
664 
665 	return MD5authencrypt(cache_type, cache_secret, pkt, length);
666 }
667 
668 
669 /*
670  * authdecrypt - verify message authenticator
671  *
672  * Returns TRUE if authenticator valid, FALSE if invalid or not found.
673  */
674 int
675 authdecrypt(
676 	keyid_t		keyno,
677 	u_int32 *	pkt,
678 	int		length,
679 	int		size
680 	)
681 {
682 	/*
683 	 * A zero key identifier means the sender has not verified
684 	 * the last message was correctly authenticated.  For our
685 	 * purpose this is an invalid authenticator.
686 	 */
687 	authdecryptions++;
688 	if (0 == keyno || !authhavekey(keyno) || size < 4) {
689 		return FALSE;
690 	}
691 
692 	return MD5authdecrypt(cache_type, cache_secret, pkt, length,
693 			      size);
694 }
695