authkeys.c revision 316068
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 */ 23typedef struct savekey symkey; 24 25struct 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 43typedef struct symkey_alloc_tag symkey_alloc; 44 45struct symkey_alloc_tag { 46 symkey_alloc * link; 47 void * mem; /* enable free() atexit */ 48}; 49 50symkey_alloc * authallocs; 51#endif /* DEBUG */ 52 53static u_short auth_log2(size_t); 54static void auth_resize_hashtable(void); 55static void allocsymkey(keyid_t, u_short, 56 u_short, u_long, size_t, u_char *, KeyAccT *); 57static void freesymkey(symkey *); 58#ifdef DEBUG 59static void free_auth_mem(void); 60#endif 61 62symkey 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 71int authhashdisabled; 72u_short authhashbuckets = DEF_AUTHHASHSIZE; 73u_short authhashmask = DEF_AUTHHASHSIZE - 1; 74symkey **key_hash; 75 76u_long authkeynotfound; /* keys not found */ 77u_long authkeylookups; /* calls to lookup keys */ 78u_long authnumkeys; /* number of active keys */ 79u_long authkeyexpired; /* key lifetime expirations */ 80u_long authkeyuncached; /* cache misses */ 81u_long authnokey; /* calls to encrypt with no key */ 82u_long authencryptions; /* calls to encrypt */ 83u_long authdecryptions; /* calls to decrypt */ 84 85/* 86 * Storage for free symkey structures. We malloc() such things but 87 * never free them. 88 */ 89symkey *authfreekeys; 90int 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 */ 100keyid_t cache_keyid; /* key identifier */ 101u_char *cache_secret; /* secret */ 102size_t cache_secretsize; /* secret length */ 103int cache_type; /* OpenSSL digest NID */ 104u_short cache_flags; /* flags that wave */ 105KeyAccT *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 */ 114KeyAccT* 115keyacc_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 */ 131KeyAccT* 132keyacc_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. */ 146KeyAccT* 147keyacc_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 */ 160int /*BOOL*/ 161keyacc_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 */ 181void 182init_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 207static void 208free_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 */ 235void 236auth_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 = eallocarrayxz(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 */ 274void 275auth_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 290static u_short 291auth_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 319static void 320authcache_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 */ 342static void 343auth_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 */ 377static void 378allocsymkey( 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 */ 415static void 416freesymkey( 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 */ 448struct savekey * 449auth_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 */ 466int 467auth_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 */ 482int 483authhavekey( 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 */ 530void 531authtrust( 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 */ 589int 590authistrusted( 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 */ 647void 648MD5auth_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 */ 723void 724auth_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 */ 756void 757auth_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 */ 777size_t 778authencrypt( 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 */ 807int 808authdecrypt( 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