authkeys.c revision 294569
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 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 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(symkey **, keyid_t, u_short, u_short, 56 u_long, u_short, u_char *, KeyAccT *); 57static void freesymkey(symkey *, 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 */ 97keyid_t cache_keyid; /* key identifier */ 98u_char *cache_secret; /* secret */ 99u_short cache_secretsize; /* secret length */ 100int cache_type; /* OpenSSL digest NID */ 101u_short cache_flags; /* flags that wave */ 102KeyAccT *cache_keyacclist; /* key access list */ 103 104 105/* 106 * init_auth - initialize internal data 107 */ 108void 109init_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 134static void 135free_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 */ 162void 163auth_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 */ 201void 202auth_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 217static u_short 218auth_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 */ 254static void 255auth_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 */ 289static void 290allocsymkey( 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 */ 324static void 325freesymkey( 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 */ 350struct savekey * 351auth_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 */ 370int 371auth_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 */ 395int 396authhavekey( 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 */ 453void 454authtrust( 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 */ 521int 522authistrusted( 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 */ 599void 600MD5auth_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 */ 680void 681auth_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 */ 712void 713auth_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 */ 733size_t 734authencrypt( 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 */ 763int 764authdecrypt( 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