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