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