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