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