authkeys.c revision 289764
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 515void 516MD5auth_setkey( 517 keyid_t keyno, 518 int keytype, 519 const u_char *key, 520 size_t len 521 ) 522{ 523 symkey * sk; 524 symkey ** bucket; 525 u_char * secret; 526 size_t secretsize; 527 528 DEBUG_ENSURE(keytype <= USHRT_MAX); 529 DEBUG_ENSURE(len < 4 * 1024); 530 /* 531 * See if we already have the key. If so just stick in the 532 * new value. 533 */ 534 bucket = &key_hash[KEYHASH(keyno)]; 535 for (sk = *bucket; sk != NULL; sk = sk->hlink) { 536 if (keyno == sk->keyid) { 537 /* TALOS-CAN-0054: make sure we have a new buffer! */ 538 if (NULL != sk->secret) { 539 memset(sk->secret, 0, sk->secretsize); 540 free(sk->secret); 541 } 542 sk->secret = emalloc(len); 543 sk->type = (u_short)keytype; 544 secretsize = len; 545 sk->secretsize = (u_short)secretsize; 546#ifndef DISABLE_BUG1243_FIX 547 memcpy(sk->secret, key, secretsize); 548#else 549 strlcpy((char *)sk->secret, (const char *)key, 550 secretsize); 551#endif 552 if (cache_keyid == keyno) { 553 cache_flags = 0; 554 cache_keyid = 0; 555 } 556 return; 557 } 558 } 559 560 /* 561 * Need to allocate new structure. Do it. 562 */ 563 secretsize = len; 564 secret = emalloc(secretsize); 565#ifndef DISABLE_BUG1243_FIX 566 memcpy(secret, key, secretsize); 567#else 568 strlcpy((char *)secret, (const char *)key, secretsize); 569#endif 570 allocsymkey(bucket, keyno, 0, (u_short)keytype, 0, 571 (u_short)secretsize, secret); 572#ifdef DEBUG 573 if (debug >= 4) { 574 size_t j; 575 576 printf("auth_setkey: key %d type %d len %d ", (int)keyno, 577 keytype, (int)secretsize); 578 for (j = 0; j < secretsize; j++) 579 printf("%02x", secret[j]); 580 printf("\n"); 581 } 582#endif 583} 584 585 586/* 587 * auth_delkeys - delete non-autokey untrusted keys, and clear all info 588 * except the trusted bit of non-autokey trusted keys, in 589 * preparation for rereading the keys file. 590 */ 591void 592auth_delkeys(void) 593{ 594 symkey * sk; 595 596 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey) 597 if (sk->keyid > NTP_MAXKEY) { /* autokey */ 598 continue; 599 } 600 601 /* 602 * Don't lose info as to which keys are trusted. Make 603 * sure there are no dangling pointers! 604 */ 605 if (KEY_TRUSTED & sk->flags) { 606 if (sk->secret != NULL) { 607 memset(sk->secret, 0, sk->secretsize); 608 free(sk->secret); 609 sk->secret = NULL; /* TALOS-CAN-0054 */ 610 } 611 sk->secretsize = 0; 612 sk->lifetime = 0; 613 } else { 614 freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]); 615 } 616 ITER_DLIST_END() 617} 618 619 620/* 621 * auth_agekeys - delete keys whose lifetimes have expired 622 */ 623void 624auth_agekeys(void) 625{ 626 symkey * sk; 627 628 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey) 629 if (sk->lifetime > 0 && current_time > sk->lifetime) { 630 freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]); 631 authkeyexpired++; 632 } 633 ITER_DLIST_END() 634 DPRINTF(1, ("auth_agekeys: at %lu keys %lu expired %lu\n", 635 current_time, authnumkeys, authkeyexpired)); 636} 637 638 639/* 640 * authencrypt - generate message authenticator 641 * 642 * Returns length of authenticator field, zero if key not found. 643 */ 644int 645authencrypt( 646 keyid_t keyno, 647 u_int32 * pkt, 648 int length 649 ) 650{\ 651 /* 652 * A zero key identifier means the sender has not verified 653 * the last message was correctly authenticated. The MAC 654 * consists of a single word with value zero. 655 */ 656 authencryptions++; 657 pkt[length / 4] = htonl(keyno); 658 if (0 == keyno) { 659 return 4; 660 } 661 if (!authhavekey(keyno)) { 662 return 0; 663 } 664 665 return MD5authencrypt(cache_type, cache_secret, pkt, length); 666} 667 668 669/* 670 * authdecrypt - verify message authenticator 671 * 672 * Returns TRUE if authenticator valid, FALSE if invalid or not found. 673 */ 674int 675authdecrypt( 676 keyid_t keyno, 677 u_int32 * pkt, 678 int length, 679 int size 680 ) 681{ 682 /* 683 * A zero key identifier means the sender has not verified 684 * the last message was correctly authenticated. For our 685 * purpose this is an invalid authenticator. 686 */ 687 authdecryptions++; 688 if (0 == keyno || !authhavekey(keyno) || size < 4) { 689 return FALSE; 690 } 691 692 return MD5authdecrypt(cache_type, cache_secret, pkt, length, 693 size); 694} 695