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 #include "ntp_keyacc.h" 19 20 /* 21 * Structure to store keys in in the hash table. 22 */ 23 typedef struct savekey symkey; 24 25 struct savekey { 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 */ 35 }; 36 37 /* define the payload region of symkey beyond the list pointers */ 38 #define symkey_payload secret 39 40 #define KEY_TRUSTED 0x001 /* this key is trusted */ 41 42 #ifdef DEBUG 43 typedef struct symkey_alloc_tag symkey_alloc; 44 45 struct symkey_alloc_tag { 46 symkey_alloc * link; 47 void * mem; /* enable free() atexit */ 48 }; 49 50 symkey_alloc * authallocs; 51 #endif /* DEBUG */ 52 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 *); 58 #ifdef DEBUG 59 static void free_auth_mem(void); 60 #endif 61 62 symkey key_listhead; /* list of all in-use keys */; 63 /* 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. 66 */ 67 #define DEF_AUTHHASHSIZE 64 68 /*#define HASHMASK ((HASHSIZE)-1)*/ 69 #define KEYHASH(keyid) ((keyid) & authhashmask) 70 71 int authhashdisabled; 72 u_short authhashbuckets = DEF_AUTHHASHSIZE; 73 u_short authhashmask = DEF_AUTHHASHSIZE - 1; 74 symkey **key_hash; 75 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 */ 84 85 /* 86 * Storage for free symkey structures. We malloc() such things but 87 * never free them. 88 */ 89 symkey *authfreekeys; 90 int authnumfreekeys; 91 92 #define MEMINC 16 /* number of new free ones to get */ 93 94 /* 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 98 * is valid. 99 */ 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 */ 106 107 /* -------------------------------------------------------------------- 108 * manage key access lists 109 * -------------------------------------------------------------------- 110 */ 111 /* allocate and populate new access node and pushes it on the list. 112 * Returns the new head. 113 */ 114 KeyAccT* 115 keyacc_new_push( 116 KeyAccT * head, 117 const sockaddr_u * addr 118 ) 119 { 120 KeyAccT * node = emalloc(sizeof(KeyAccT)); 121 122 memcpy(&node->addr, addr, sizeof(sockaddr_u)); 123 node->next = head; 124 return node; 125 } 126 127 /* ----------------------------------------------------------------- */ 128 /* pop and deallocate the first node of a list of access nodes, if 129 * the list is not empty. Returns the tail of the list. 130 */ 131 KeyAccT* 132 keyacc_pop_free( 133 KeyAccT *head 134 ) 135 { 136 KeyAccT * next = NULL; 137 if (head) { 138 next = head->next; 139 free(head); 140 } 141 return next; 142 } 143 144 /* ----------------------------------------------------------------- */ 145 /* deallocate the list; returns an empty list. */ 146 KeyAccT* 147 keyacc_all_free( 148 KeyAccT * head 149 ) 150 { 151 while (head) 152 head = keyacc_pop_free(head); 153 return head; 154 } 155 156 /* ----------------------------------------------------------------- */ 157 /* scan a list to see if it contains a given address. Return the 158 * default result value in case of an empty list. 159 */ 160 int /*BOOL*/ 161 keyacc_contains( 162 const KeyAccT *head, 163 const sockaddr_u *addr, 164 int defv) 165 { 166 if (head) { 167 do { 168 if (SOCK_EQ(&head->addr, addr)) 169 return TRUE; 170 } while (NULL != (head = head->next)); 171 return FALSE; 172 } else { 173 return !!defv; 174 } 175 } 176 177 178 /* 179 * init_auth - initialize internal data 180 */ 181 void 182 init_auth(void) 183 { 184 size_t newalloc; 185 186 /* 187 * Initialize hash table and free list 188 */ 189 newalloc = authhashbuckets * sizeof(key_hash[0]); 190 191 key_hash = erealloc(key_hash, newalloc); 192 memset(key_hash, '\0', newalloc); 193 194 INIT_DLIST(key_listhead, llink); 195 196 #ifdef DEBUG 197 atexit(&free_auth_mem); 198 #endif 199 } 200 201 202 /* 203 * free_auth_mem - assist in leak detection by freeing all dynamic 204 * allocations from this module. 205 */ 206 #ifdef DEBUG 207 static void 208 free_auth_mem(void) 209 { 210 symkey * sk; 211 symkey_alloc * alloc; 212 symkey_alloc * next_alloc; 213 214 while (NULL != (sk = HEAD_DLIST(key_listhead, llink))) { 215 freesymkey(sk); 216 } 217 free(key_hash); 218 key_hash = NULL; 219 cache_keyid = 0; 220 cache_flags = 0; 221 cache_keyacclist = NULL; 222 for (alloc = authallocs; alloc != NULL; alloc = next_alloc) { 223 next_alloc = alloc->link; 224 free(alloc->mem); 225 } 226 authfreekeys = NULL; 227 authnumfreekeys = 0; 228 } 229 #endif /* DEBUG */ 230 231 232 /* 233 * auth_moremem - get some more free key structures 234 */ 235 void 236 auth_moremem( 237 int keycount 238 ) 239 { 240 symkey * sk; 241 int i; 242 #ifdef DEBUG 243 void * base; 244 symkey_alloc * allocrec; 245 # define MOREMEM_EXTRA_ALLOC (sizeof(*allocrec)) 246 #else 247 # define MOREMEM_EXTRA_ALLOC (0) 248 #endif 249 250 i = (keycount > 0) 251 ? keycount 252 : MEMINC; 253 sk = emalloc_zero(i * sizeof(*sk) + MOREMEM_EXTRA_ALLOC); 254 #ifdef DEBUG 255 base = sk; 256 #endif 257 authnumfreekeys += i; 258 259 for (; i > 0; i--, sk++) { 260 LINK_SLIST(authfreekeys, sk, llink.f); 261 } 262 263 #ifdef DEBUG 264 allocrec = (void *)sk; 265 allocrec->mem = base; 266 LINK_SLIST(authallocs, allocrec, link); 267 #endif 268 } 269 270 271 /* 272 * auth_prealloc_symkeys 273 */ 274 void 275 auth_prealloc_symkeys( 276 int keycount 277 ) 278 { 279 int allocated; 280 int additional; 281 282 allocated = authnumkeys + authnumfreekeys; 283 additional = keycount - allocated; 284 if (additional > 0) 285 auth_moremem(additional); 286 auth_resize_hashtable(); 287 } 288 289 290 static u_short 291 auth_log2(size_t x) 292 { 293 /* 294 ** bithack to calculate floor(log2(x)) 295 ** 296 ** This assumes 297 ** - (sizeof(size_t) is a power of two 298 ** - CHAR_BITS is a power of two 299 ** - returning zero for arguments <= 0 is OK. 300 ** 301 ** Does only shifts, masks and sums in integer arithmetic in 302 ** log2(CHAR_BIT*sizeof(size_t)) steps. (that is, 5/6 steps for 303 ** 32bit/64bit size_t) 304 */ 305 int s; 306 int r = 0; 307 size_t m = ~(size_t)0; 308 309 for (s = sizeof(size_t) / 2 * CHAR_BIT; s != 0; s >>= 1) { 310 m <<= s; 311 if (x & m) 312 r += s; 313 else 314 x <<= s; 315 } 316 return (u_short)r; 317 } 318 319 static void 320 authcache_flush_id( 321 keyid_t id 322 ) 323 { 324 if (cache_keyid == id) { 325 cache_keyid = 0; 326 cache_type = 0; 327 cache_flags = 0; 328 cache_secret = NULL; 329 cache_secretsize = 0; 330 cache_keyacclist = NULL; 331 } 332 } 333 334 335 /* 336 * auth_resize_hashtable 337 * 338 * Size hash table to average 4 or fewer entries per bucket initially, 339 * within the bounds of at least 4 and no more than 15 bits for the hash 340 * table index. Populate the hash table. 341 */ 342 static void 343 auth_resize_hashtable(void) 344 { 345 u_long totalkeys; 346 u_short hashbits; 347 u_short hash; 348 size_t newalloc; 349 symkey * sk; 350 351 totalkeys = authnumkeys + authnumfreekeys; 352 hashbits = auth_log2(totalkeys / 4) + 1; 353 hashbits = max(4, hashbits); 354 hashbits = min(15, hashbits); 355 356 authhashbuckets = 1 << hashbits; 357 authhashmask = authhashbuckets - 1; 358 newalloc = authhashbuckets * sizeof(key_hash[0]); 359 360 key_hash = erealloc(key_hash, newalloc); 361 memset(key_hash, '\0', newalloc); 362 363 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey) 364 hash = KEYHASH(sk->keyid); 365 LINK_SLIST(key_hash[hash], sk, hlink); 366 ITER_DLIST_END() 367 } 368 369 370 /* 371 * allocsymkey - common code to allocate and link in symkey 372 * 373 * secret must be allocated with a free-compatible allocator. It is 374 * owned by the referring symkey structure, and will be free()d by 375 * freesymkey(). 376 */ 377 static void 378 allocsymkey( 379 keyid_t id, 380 u_short flags, 381 u_short type, 382 u_long lifetime, 383 size_t secretsize, 384 u_char * secret, 385 KeyAccT * ka 386 ) 387 { 388 symkey * sk; 389 symkey ** bucket; 390 391 bucket = &key_hash[KEYHASH(id)]; 392 393 394 if (authnumfreekeys < 1) 395 auth_moremem(-1); 396 UNLINK_HEAD_SLIST(sk, authfreekeys, llink.f); 397 DEBUG_ENSURE(sk != NULL); 398 sk->keyid = id; 399 sk->flags = flags; 400 sk->type = type; 401 sk->secretsize = secretsize; 402 sk->secret = secret; 403 sk->keyacclist = ka; 404 sk->lifetime = lifetime; 405 LINK_SLIST(*bucket, sk, hlink); 406 LINK_TAIL_DLIST(key_listhead, sk, llink); 407 authnumfreekeys--; 408 authnumkeys++; 409 } 410 411 412 /* 413 * freesymkey - common code to remove a symkey and recycle its entry. 414 */ 415 static void 416 freesymkey( 417 symkey * sk 418 ) 419 { 420 symkey ** bucket; 421 symkey * unlinked; 422 423 if (NULL == sk) 424 return; 425 426 authcache_flush_id(sk->keyid); 427 keyacc_all_free(sk->keyacclist); 428 429 bucket = &key_hash[KEYHASH(sk->keyid)]; 430 if (sk->secret != NULL) { 431 memset(sk->secret, '\0', sk->secretsize); 432 free(sk->secret); 433 } 434 UNLINK_SLIST(unlinked, *bucket, sk, hlink, symkey); 435 DEBUG_ENSURE(sk == unlinked); 436 UNLINK_DLIST(sk, llink); 437 memset((char *)sk + offsetof(symkey, symkey_payload), '\0', 438 sizeof(*sk) - offsetof(symkey, symkey_payload)); 439 LINK_SLIST(authfreekeys, sk, llink.f); 440 authnumkeys--; 441 authnumfreekeys++; 442 } 443 444 445 /* 446 * auth_findkey - find a key in the hash table 447 */ 448 struct savekey * 449 auth_findkey( 450 keyid_t id 451 ) 452 { 453 symkey * sk; 454 455 for (sk = key_hash[KEYHASH(id)]; sk != NULL; sk = sk->hlink) 456 if (id == sk->keyid) 457 return sk; 458 return NULL; 459 } 460 461 462 /* 463 * auth_havekey - return TRUE if the key id is zero or known. The 464 * key needs not to be trusted. 465 */ 466 int 467 auth_havekey( 468 keyid_t id 469 ) 470 { 471 return 472 (0 == id) || 473 (cache_keyid == id) || 474 (NULL != auth_findkey(id)); 475 } 476 477 478 /* 479 * authhavekey - return TRUE and cache the key, if zero or both known 480 * and trusted. 481 */ 482 int 483 authhavekey( 484 keyid_t id 485 ) 486 { 487 symkey * sk; 488 489 authkeylookups++; 490 if (0 == id || cache_keyid == id) 491 return !!(KEY_TRUSTED & cache_flags); 492 493 /* 494 * Search the bin for the key. If not found, or found but the key 495 * type is zero, somebody marked it trusted without specifying a 496 * key or key type. In this case consider the key missing. 497 */ 498 authkeyuncached++; 499 sk = auth_findkey(id); 500 if ((sk == NULL) || (sk->type == 0)) { 501 authkeynotfound++; 502 return FALSE; 503 } 504 505 /* 506 * If the key is not trusted, the key is not considered found. 507 */ 508 if ( ! (KEY_TRUSTED & sk->flags)) { 509 authnokey++; 510 return FALSE; 511 } 512 513 /* 514 * The key is found and trusted. Initialize the key cache. 515 */ 516 cache_keyid = sk->keyid; 517 cache_type = sk->type; 518 cache_flags = sk->flags; 519 cache_secret = sk->secret; 520 cache_secretsize = sk->secretsize; 521 cache_keyacclist = sk->keyacclist; 522 523 return TRUE; 524 } 525 526 527 /* 528 * authtrust - declare a key to be trusted/untrusted 529 */ 530 void 531 authtrust( 532 keyid_t id, 533 u_long trust 534 ) 535 { 536 symkey * sk; 537 u_long lifetime; 538 539 /* 540 * Search bin for key; if it does not exist and is untrusted, 541 * forget it. 542 */ 543 544 sk = auth_findkey(id); 545 if (!trust && sk == NULL) 546 return; 547 548 /* 549 * There are two conditions remaining. Either it does not 550 * exist and is to be trusted or it does exist and is or is 551 * not to be trusted. 552 */ 553 if (sk != NULL) { 554 /* 555 * Key exists. If it is to be trusted, say so and update 556 * its lifetime. If no longer trusted, return it to the 557 * free list. Flush the cache first to be sure there are 558 * no discrepancies. 559 */ 560 authcache_flush_id(id); 561 if (trust > 0) { 562 sk->flags |= KEY_TRUSTED; 563 if (trust > 1) 564 sk->lifetime = current_time + trust; 565 else 566 sk->lifetime = 0; 567 } else { 568 freesymkey(sk); 569 } 570 return; 571 } 572 573 /* 574 * keyid is not present, but the is to be trusted. We allocate 575 * a new key, but do not specify a key type or secret. 576 */ 577 if (trust > 1) { 578 lifetime = current_time + trust; 579 } else { 580 lifetime = 0; 581 } 582 allocsymkey(id, KEY_TRUSTED, 0, lifetime, 0, NULL, NULL); 583 } 584 585 586 /* 587 * authistrusted - determine whether a key is trusted 588 */ 589 int 590 authistrusted( 591 keyid_t id 592 ) 593 { 594 symkey * sk; 595 596 if (id == cache_keyid) 597 return !!(KEY_TRUSTED & cache_flags); 598 599 authkeyuncached++; 600 sk = auth_findkey(id); 601 if (sk == NULL || !(KEY_TRUSTED & sk->flags)) { 602 authkeynotfound++; 603 return FALSE; 604 } 605 return TRUE; 606 } 607 608 609 /* 610 * authistrustedip - determine if the IP is OK for the keyid 611 */ 612 int 613 authistrustedip( 614 keyid_t keyno, 615 sockaddr_u * sau 616 ) 617 { 618 symkey * sk; 619 620 /* That specific key was already used to authenticate the 621 * packet. Therefore, the key *must* exist... There's a chance 622 * that is not trusted, though. 623 */ 624 if (keyno == cache_keyid) { 625 return (KEY_TRUSTED & cache_flags) && 626 keyacc_contains(cache_keyacclist, sau, TRUE); 627 } else { 628 authkeyuncached++; 629 sk = auth_findkey(keyno); 630 INSIST(NULL != sk); 631 return (KEY_TRUSTED & sk->flags) && 632 keyacc_contains(sk->keyacclist, sau, TRUE); 633 } 634 } 635 636 /* Note: There are two locations below where 'strncpy()' is used. While 637 * this function is a hazard by itself, it's essential that it is used 638 * here. Bug 1243 involved that the secret was filled with NUL bytes 639 * after the first NUL encountered, and 'strlcpy()' simply does NOT have 640 * this behaviour. So disabling the fix and reverting to the buggy 641 * behaviour due to compatibility issues MUST also fill with NUL and 642 * this needs 'strncpy'. Also, the secret is managed as a byte blob of a 643 * given size, and eventually truncating it and replacing the last byte 644 * with a NUL would be a bug. 645 * perlinger@ntp.org 2015-10-10 646 */ 647 void 648 MD5auth_setkey( 649 keyid_t keyno, 650 int keytype, 651 const u_char *key, 652 size_t secretsize, 653 KeyAccT *ka 654 ) 655 { 656 symkey * sk; 657 u_char * secret; 658 659 DEBUG_ENSURE(keytype <= USHRT_MAX); 660 DEBUG_ENSURE(secretsize < 4 * 1024); 661 /* 662 * See if we already have the key. If so just stick in the 663 * new value. 664 */ 665 sk = auth_findkey(keyno); 666 if (sk != NULL && keyno == sk->keyid) { 667 /* TALOS-CAN-0054: make sure we have a new buffer! */ 668 if (NULL != sk->secret) { 669 memset(sk->secret, 0, sk->secretsize); 670 free(sk->secret); 671 } 672 sk->secret = emalloc(secretsize + 1); 673 sk->type = (u_short)keytype; 674 sk->secretsize = secretsize; 675 /* make sure access lists don't leak here! */ 676 if (ka != sk->keyacclist) { 677 keyacc_all_free(sk->keyacclist); 678 sk->keyacclist = ka; 679 } 680 #ifndef DISABLE_BUG1243_FIX 681 memcpy(sk->secret, key, secretsize); 682 #else 683 /* >MUST< use 'strncpy()' here! See above! */ 684 strncpy((char *)sk->secret, (const char *)key, 685 secretsize); 686 #endif 687 authcache_flush_id(keyno); 688 return; 689 } 690 691 /* 692 * Need to allocate new structure. Do it. 693 */ 694 secret = emalloc(secretsize + 1); 695 #ifndef DISABLE_BUG1243_FIX 696 memcpy(secret, key, secretsize); 697 #else 698 /* >MUST< use 'strncpy()' here! See above! */ 699 strncpy((char *)secret, (const char *)key, secretsize); 700 #endif 701 allocsymkey(keyno, 0, (u_short)keytype, 0, 702 secretsize, secret, ka); 703 #ifdef DEBUG 704 if (debug >= 4) { 705 size_t j; 706 707 printf("auth_setkey: key %d type %d len %d ", (int)keyno, 708 keytype, (int)secretsize); 709 for (j = 0; j < secretsize; j++) { 710 printf("%02x", secret[j]); 711 } 712 printf("\n"); 713 } 714 #endif 715 } 716 717 718 /* 719 * auth_delkeys - delete non-autokey untrusted keys, and clear all info 720 * except the trusted bit of non-autokey trusted keys, in 721 * preparation for rereading the keys file. 722 */ 723 void 724 auth_delkeys(void) 725 { 726 symkey * sk; 727 728 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey) 729 if (sk->keyid > NTP_MAXKEY) { /* autokey */ 730 continue; 731 } 732 733 /* 734 * Don't lose info as to which keys are trusted. Make 735 * sure there are no dangling pointers! 736 */ 737 if (KEY_TRUSTED & sk->flags) { 738 if (sk->secret != NULL) { 739 memset(sk->secret, 0, sk->secretsize); 740 free(sk->secret); 741 sk->secret = NULL; /* TALOS-CAN-0054 */ 742 } 743 sk->keyacclist = keyacc_all_free(sk->keyacclist); 744 sk->secretsize = 0; 745 sk->lifetime = 0; 746 } else { 747 freesymkey(sk); 748 } 749 ITER_DLIST_END() 750 } 751 752 753 /* 754 * auth_agekeys - delete keys whose lifetimes have expired 755 */ 756 void 757 auth_agekeys(void) 758 { 759 symkey * sk; 760 761 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey) 762 if (sk->lifetime > 0 && current_time > sk->lifetime) { 763 freesymkey(sk); 764 authkeyexpired++; 765 } 766 ITER_DLIST_END() 767 DPRINTF(1, ("auth_agekeys: at %lu keys %lu expired %lu\n", 768 current_time, authnumkeys, authkeyexpired)); 769 } 770 771 772 /* 773 * authencrypt - generate message authenticator 774 * 775 * Returns length of authenticator field, zero if key not found. 776 */ 777 size_t 778 authencrypt( 779 keyid_t keyno, 780 u_int32 * pkt, 781 size_t length 782 ) 783 { 784 /* 785 * A zero key identifier means the sender has not verified 786 * the last message was correctly authenticated. The MAC 787 * consists of a single word with value zero. 788 */ 789 authencryptions++; 790 pkt[length / 4] = htonl(keyno); 791 if (0 == keyno) { 792 return 4; 793 } 794 if (!authhavekey(keyno)) { 795 return 0; 796 } 797 798 return MD5authencrypt(cache_type, cache_secret, pkt, length); 799 } 800 801 802 /* 803 * authdecrypt - verify message authenticator 804 * 805 * Returns TRUE if authenticator valid, FALSE if invalid or not found. 806 */ 807 int 808 authdecrypt( 809 keyid_t keyno, 810 u_int32 * pkt, 811 size_t length, 812 size_t size 813 ) 814 { 815 /* 816 * A zero key identifier means the sender has not verified 817 * the last message was correctly authenticated. For our 818 * purpose this is an invalid authenticator. 819 */ 820 authdecryptions++; 821 if (0 == keyno || !authhavekey(keyno) || size < 4) { 822 return FALSE; 823 } 824 825 return MD5authdecrypt(cache_type, cache_secret, pkt, length, 826 size); 827 } 828