contrib/ntp/libntp/authkeys.c

   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  */
  22 typedef struct savekey symkey;
  23
  24 struct 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
  41 typedef struct symkey_alloc_tag symkey_alloc;
  42
  43 struct symkey_alloc_tag {
  44         symkey_alloc *  link;
  45         void *          mem;            /* enable free() atexit */
  46 };
  47
  48 symkey_alloc *  authallocs;
  49 #endif  /* DEBUG */
  50
  51 static inline u_short   auth_log2(double x);
  52 static void             auth_resize_hashtable(void);
  53 static void             allocsymkey(symkey **, keyid_t, u_short,
  54                                     u_short, u_long, u_short, u_char *);
  55 static void             freesymkey(symkey *, symkey **);
  56 #ifdef DEBUG
  57 static void             free_auth_mem(void);
  58 #endif
  59
  60 symkey  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
  69 int     authhashdisabled;
  70 u_short authhashbuckets = DEF_AUTHHASHSIZE;
  71 u_short authhashmask = DEF_AUTHHASHSIZE - 1;
  72 symkey **key_hash;
  73
  74 u_long authkeynotfound;         /* keys not found */
  75 u_long authkeylookups;          /* calls to lookup keys */
  76 u_long authnumkeys;             /* number of active keys */
  77 u_long authkeyexpired;          /* key lifetime expirations */
  78 u_long authkeyuncached;         /* cache misses */
  79 u_long authnokey;               /* calls to encrypt with no key */
  80 u_long authencryptions;         /* calls to encrypt */
  81 u_long authdecryptions;         /* calls to decrypt */
  82
  83 /*
  84  * Storage for free symkey structures.  We malloc() such things but
  85  * never free them.
  86  */
  87 symkey *authfreekeys;
  88 int 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  */
  95 keyid_t cache_keyid;            /* key identifier */
  96 u_char *cache_secret;           /* secret */
  97 u_short cache_secretsize;       /* secret length */
  98 int     cache_type;             /* OpenSSL digest NID */
  99 u_short cache_flags;            /* flags that wave */
 100
 101
 102 /*
 103  * init_auth - initialize internal data
 104  */
 105 void
 106 init_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
 131 static void
 132 free_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  */
 158 void
 159 auth_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  */
 197 void
 198 auth_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
 213 static inline u_short
 214 auth_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  */
 227 static void
 228 auth_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  */
 262 static void
 263 allocsymkey(
 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  */
 295 static void
 296 freesymkey(
 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  */
 321 struct savekey *
 322 auth_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  */
 341 int
 342 auth_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  */
 366 int
 367 authhavekey(
 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  */
 423 void
 424 authtrust(
 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  */
 490 int
 491 authistrusted(
 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  */
 525 void
 526 MD5auth_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  */
 603 void
 604 auth_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  */
 635 void
 636 auth_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  */
 656 size_t
 657 authencrypt(
 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  */
 686 int
 687 authdecrypt(
 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 }