authkeys.c revision 285612
1205194Sdelphij/* 2205194Sdelphij * authkeys.c - routines to manage the storage of authentication keys 3205194Sdelphij */ 4205194Sdelphij#ifdef HAVE_CONFIG_H 5205194Sdelphij# include <config.h> 6205194Sdelphij#endif 7205194Sdelphij 8205194Sdelphij#include <math.h> 9205194Sdelphij#include <stdio.h> 10205194Sdelphij 11205194Sdelphij#include "ntp.h" 12205194Sdelphij#include "ntp_fp.h" 13205194Sdelphij#include "ntpd.h" 14205194Sdelphij#include "ntp_lists.h" 15205194Sdelphij#include "ntp_string.h" 16205194Sdelphij#include "ntp_malloc.h" 17205194Sdelphij#include "ntp_stdlib.h" 18205194Sdelphij 19205194Sdelphij/* 20205194Sdelphij * Structure to store keys in in the hash table. 21205194Sdelphij */ 22205194Sdelphijtypedef struct savekey symkey; 23205194Sdelphij 24205194Sdelphijstruct savekey { 25205194Sdelphij symkey * hlink; /* next in hash bucket */ 26205194Sdelphij DECL_DLIST_LINK(symkey, llink); /* for overall & free lists */ 27205194Sdelphij u_char * secret; /* shared secret */ 28205194Sdelphij u_long lifetime; /* remaining lifetime */ 29205194Sdelphij keyid_t keyid; /* key identifier */ 30205194Sdelphij u_short type; /* OpenSSL digest NID */ 31205194Sdelphij u_short secretsize; /* secret octets */ 32205194Sdelphij u_short flags; /* KEY_ flags that wave */ 33205194Sdelphij}; 34205194Sdelphij 35205194Sdelphij/* define the payload region of symkey beyond the list pointers */ 36205194Sdelphij#define symkey_payload secret 37205194Sdelphij 38205194Sdelphij#define KEY_TRUSTED 0x001 /* this key is trusted */ 39205194Sdelphij 40205194Sdelphij#ifdef DEBUG 41205194Sdelphijtypedef struct symkey_alloc_tag symkey_alloc; 42205194Sdelphij 43205194Sdelphijstruct symkey_alloc_tag { 44205194Sdelphij symkey_alloc * link; 45205194Sdelphij void * mem; /* enable free() atexit */ 46205194Sdelphij}; 47205194Sdelphij 48205194Sdelphijsymkey_alloc * authallocs; 49205194Sdelphij#endif /* DEBUG */ 50205194Sdelphij 51205194Sdelphijstatic inline u_short auth_log2(double x); 52205194Sdelphijstatic void auth_resize_hashtable(void); 53205194Sdelphijstatic void allocsymkey(symkey **, keyid_t, u_short, 54205194Sdelphij u_short, u_long, u_short, u_char *); 55205194Sdelphijstatic void freesymkey(symkey *, symkey **); 56205194Sdelphij#ifdef DEBUG 57205194Sdelphijstatic void free_auth_mem(void); 58205194Sdelphij#endif 59205194Sdelphij 60205194Sdelphijsymkey key_listhead; /* list of all in-use keys */; 61205194Sdelphij/* 62205194Sdelphij * The hash table. This is indexed by the low order bits of the 63205194Sdelphij * keyid. We make this fairly big for potentially busy servers. 64205194Sdelphij */ 65205194Sdelphij#define DEF_AUTHHASHSIZE 64 66205194Sdelphij//#define HASHMASK ((HASHSIZE)-1) 67205194Sdelphij#define KEYHASH(keyid) ((keyid) & authhashmask) 68205194Sdelphij 69205194Sdelphijint authhashdisabled; 70205194Sdelphiju_short authhashbuckets = DEF_AUTHHASHSIZE; 71205194Sdelphiju_short authhashmask = DEF_AUTHHASHSIZE - 1; 72205194Sdelphijsymkey **key_hash; 73205194Sdelphij 74205194Sdelphiju_long authkeynotfound; /* keys not found */ 75205194Sdelphiju_long authkeylookups; /* calls to lookup keys */ 76205194Sdelphiju_long authnumkeys; /* number of active keys */ 77205194Sdelphiju_long authkeyexpired; /* key lifetime expirations */ 78205194Sdelphiju_long authkeyuncached; /* cache misses */ 79205194Sdelphiju_long authnokey; /* calls to encrypt with no key */ 80205194Sdelphiju_long authencryptions; /* calls to encrypt */ 81205194Sdelphiju_long authdecryptions; /* calls to decrypt */ 82205194Sdelphij 83205194Sdelphij/* 84205194Sdelphij * Storage for free symkey structures. We malloc() such things but 85205194Sdelphij * never free them. 86205194Sdelphij */ 87205194Sdelphijsymkey *authfreekeys; 88205194Sdelphijint authnumfreekeys; 89205194Sdelphij 90205194Sdelphij#define MEMINC 16 /* number of new free ones to get */ 91205194Sdelphij 92205194Sdelphij/* 93205194Sdelphij * The key cache. We cache the last key we looked at here. 94205194Sdelphij */ 95205194Sdelphijkeyid_t cache_keyid; /* key identifier */ 96205194Sdelphiju_char *cache_secret; /* secret */ 97205194Sdelphiju_short cache_secretsize; /* secret length */ 98205194Sdelphijint cache_type; /* OpenSSL digest NID */ 99205194Sdelphiju_short cache_flags; /* flags that wave */ 100205194Sdelphij 101205194Sdelphij 102205194Sdelphij/* 103205194Sdelphij * init_auth - initialize internal data 104205194Sdelphij */ 105205194Sdelphijvoid 106205194Sdelphijinit_auth(void) 107205194Sdelphij{ 108205194Sdelphij size_t newalloc; 109205194Sdelphij 110205194Sdelphij /* 111205194Sdelphij * Initialize hash table and free list 112205194Sdelphij */ 113205194Sdelphij newalloc = authhashbuckets * sizeof(key_hash[0]); 114205194Sdelphij 115205194Sdelphij key_hash = erealloc(key_hash, newalloc); 116205194Sdelphij memset(key_hash, '\0', newalloc); 117205194Sdelphij 118205194Sdelphij INIT_DLIST(key_listhead, llink); 119205194Sdelphij 120205194Sdelphij#ifdef DEBUG 121205194Sdelphij atexit(&free_auth_mem); 122205194Sdelphij#endif 123205194Sdelphij} 124205194Sdelphij 125205194Sdelphij 126205194Sdelphij/* 127205194Sdelphij * free_auth_mem - assist in leak detection by freeing all dynamic 128205194Sdelphij * allocations from this module. 129205194Sdelphij */ 130205194Sdelphij#ifdef DEBUG 131205194Sdelphijstatic void 132205194Sdelphijfree_auth_mem(void) 133205194Sdelphij{ 134205194Sdelphij symkey * sk; 135205194Sdelphij symkey_alloc * alloc; 136205194Sdelphij symkey_alloc * next_alloc; 137205194Sdelphij 138205194Sdelphij while (NULL != (sk = HEAD_DLIST(key_listhead, llink))) { 139205194Sdelphij freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]); 140205194Sdelphij } 141205194Sdelphij free(key_hash); 142205194Sdelphij key_hash = NULL; 143205194Sdelphij cache_keyid = 0; 144205194Sdelphij cache_flags = 0; 145205194Sdelphij for (alloc = authallocs; alloc != NULL; alloc = next_alloc) { 146205194Sdelphij next_alloc = alloc->link; 147205194Sdelphij free(alloc->mem); 148205194Sdelphij } 149205194Sdelphij authfreekeys = NULL; 150205194Sdelphij authnumfreekeys = 0; 151205194Sdelphij} 152205194Sdelphij#endif /* DEBUG */ 153205194Sdelphij 154205194Sdelphij 155205194Sdelphij/* 156205194Sdelphij * auth_moremem - get some more free key structures 157205194Sdelphij */ 158205194Sdelphijvoid 159205194Sdelphijauth_moremem( 160205194Sdelphij int keycount 161205194Sdelphij ) 162205194Sdelphij{ 163205194Sdelphij symkey * sk; 164205194Sdelphij int i; 165205194Sdelphij#ifdef DEBUG 166205194Sdelphij void * base; 167205194Sdelphij symkey_alloc * allocrec; 168205194Sdelphij# define MOREMEM_EXTRA_ALLOC (sizeof(*allocrec)) 169205194Sdelphij#else 170205194Sdelphij# define MOREMEM_EXTRA_ALLOC (0) 171205194Sdelphij#endif 172205194Sdelphij 173205194Sdelphij i = (keycount > 0) 174205194Sdelphij ? keycount 175205194Sdelphij : MEMINC; 176205194Sdelphij sk = emalloc_zero(i * sizeof(*sk) + MOREMEM_EXTRA_ALLOC); 177205194Sdelphij#ifdef DEBUG 178205194Sdelphij base = sk; 179205194Sdelphij#endif 180205194Sdelphij authnumfreekeys += i; 181205194Sdelphij 182205194Sdelphij for (; i > 0; i--, sk++) { 183205194Sdelphij LINK_SLIST(authfreekeys, sk, llink.f); 184205194Sdelphij } 185205194Sdelphij 186205194Sdelphij#ifdef DEBUG 187205194Sdelphij allocrec = (void *)sk; 188205194Sdelphij allocrec->mem = base; 189205194Sdelphij LINK_SLIST(authallocs, allocrec, link); 190205194Sdelphij#endif 191205194Sdelphij} 192205194Sdelphij 193205194Sdelphij 194205194Sdelphij/* 195205194Sdelphij * auth_prealloc_symkeys 196205194Sdelphij */ 197205194Sdelphijvoid 198205194Sdelphijauth_prealloc_symkeys( 199205194Sdelphij int keycount 200205194Sdelphij ) 201205194Sdelphij{ 202205194Sdelphij int allocated; 203205194Sdelphij int additional; 204205194Sdelphij 205205194Sdelphij allocated = authnumkeys + authnumfreekeys; 206205194Sdelphij additional = keycount - allocated; 207205194Sdelphij if (additional > 0) 208205194Sdelphij auth_moremem(additional); 209230837Sdelphij 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 sk->type = (u_short)keytype; 538 secretsize = len; 539 sk->secretsize = (u_short)secretsize; 540#ifndef DISABLE_BUG1243_FIX 541 memcpy(sk->secret, key, secretsize); 542#else 543 strlcpy((char *)sk->secret, (const char *)key, 544 secretsize); 545#endif 546 if (cache_keyid == keyno) { 547 cache_flags = 0; 548 cache_keyid = 0; 549 } 550 return; 551 } 552 } 553 554 /* 555 * Need to allocate new structure. Do it. 556 */ 557 secretsize = len; 558 secret = emalloc(secretsize); 559#ifndef DISABLE_BUG1243_FIX 560 memcpy(secret, key, secretsize); 561#else 562 strlcpy((char *)secret, (const char *)key, secretsize); 563#endif 564 allocsymkey(bucket, keyno, 0, (u_short)keytype, 0, 565 (u_short)secretsize, secret); 566#ifdef DEBUG 567 if (debug >= 4) { 568 size_t j; 569 570 printf("auth_setkey: key %d type %d len %d ", (int)keyno, 571 keytype, (int)secretsize); 572 for (j = 0; j < secretsize; j++) 573 printf("%02x", secret[j]); 574 printf("\n"); 575 } 576#endif 577} 578 579 580/* 581 * auth_delkeys - delete non-autokey untrusted keys, and clear all info 582 * except the trusted bit of non-autokey trusted keys, in 583 * preparation for rereading the keys file. 584 */ 585void 586auth_delkeys(void) 587{ 588 symkey * sk; 589 590 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey) 591 if (sk->keyid > NTP_MAXKEY) { /* autokey */ 592 continue; 593 } 594 595 /* 596 * Don't lose info as to which keys are trusted. 597 */ 598 if (KEY_TRUSTED & sk->flags) { 599 if (sk->secret != NULL) { 600 memset(sk->secret, '\0', sk->secretsize); 601 free(sk->secret); 602 } 603 sk->secretsize = 0; 604 sk->lifetime = 0; 605 } else { 606 freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]); 607 } 608 ITER_DLIST_END() 609} 610 611 612/* 613 * auth_agekeys - delete keys whose lifetimes have expired 614 */ 615void 616auth_agekeys(void) 617{ 618 symkey * sk; 619 620 ITER_DLIST_BEGIN(key_listhead, sk, llink, symkey) 621 if (sk->lifetime > 0 && current_time > sk->lifetime) { 622 freesymkey(sk, &key_hash[KEYHASH(sk->keyid)]); 623 authkeyexpired++; 624 } 625 ITER_DLIST_END() 626 DPRINTF(1, ("auth_agekeys: at %lu keys %lu expired %lu\n", 627 current_time, authnumkeys, authkeyexpired)); 628} 629 630 631/* 632 * authencrypt - generate message authenticator 633 * 634 * Returns length of authenticator field, zero if key not found. 635 */ 636int 637authencrypt( 638 keyid_t keyno, 639 u_int32 * pkt, 640 int length 641 ) 642{\ 643 /* 644 * A zero key identifier means the sender has not verified 645 * the last message was correctly authenticated. The MAC 646 * consists of a single word with value zero. 647 */ 648 authencryptions++; 649 pkt[length / 4] = htonl(keyno); 650 if (0 == keyno) { 651 return 4; 652 } 653 if (!authhavekey(keyno)) { 654 return 0; 655 } 656 657 return MD5authencrypt(cache_type, cache_secret, pkt, length); 658} 659 660 661/* 662 * authdecrypt - verify message authenticator 663 * 664 * Returns TRUE if authenticator valid, FALSE if invalid or not found. 665 */ 666int 667authdecrypt( 668 keyid_t keyno, 669 u_int32 * pkt, 670 int length, 671 int size 672 ) 673{ 674 /* 675 * A zero key identifier means the sender has not verified 676 * the last message was correctly authenticated. For our 677 * purpose this is an invalid authenticator. 678 */ 679 authdecryptions++; 680 if (0 == keyno || !authhavekey(keyno) || size < 4) { 681 return FALSE; 682 } 683 684 return MD5authdecrypt(cache_type, cache_secret, pkt, length, 685 size); 686} 687