contrib/unbound/validator/autotrust.c

   1 /*
   2  * validator/autotrust.c - RFC5011 trust anchor management for unbound.
   3  *
   4  * Copyright (c) 2009, NLnet Labs. All rights reserved.
   5  *
   6  * This software is open source.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * Redistributions of source code must retain the above copyright notice,
  13  * this list of conditions and the following disclaimer.
  14  *
  15  * Redistributions in binary form must reproduce the above copyright notice,
  16  * this list of conditions and the following disclaimer in the documentation
  17  * and/or other materials provided with the distribution.
  18  *
  19  * Neither the name of the NLNET LABS nor the names of its contributors may
  20  * be used to endorse or promote products derived from this software without
  21  * specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  */
  35
  36 /**
  37  * \file
  38  *
  39  * Contains autotrust implementation. The implementation was taken from
  40  * the autotrust daemon (BSD licensed), written by Matthijs Mekking.
  41  * It was modified to fit into unbound. The state table process is the same.
  42  */
  43 #include "config.h"
  44 #include "validator/autotrust.h"
  45 #include "validator/val_anchor.h"
  46 #include "validator/val_utils.h"
  47 #include "validator/val_sigcrypt.h"
  48 #include "util/data/dname.h"
  49 #include "util/data/packed_rrset.h"
  50 #include "util/log.h"
  51 #include "util/module.h"
  52 #include "util/net_help.h"
  53 #include "util/config_file.h"
  54 #include "util/regional.h"
  55 #include "util/random.h"
  56 #include "util/data/msgparse.h"
  57 #include "services/mesh.h"
  58 #include "services/cache/rrset.h"
  59 #include "validator/val_kcache.h"
  60 #include "ldns/sbuffer.h"
  61 #include "ldns/wire2str.h"
  62 #include "ldns/str2wire.h"
  63 #include "ldns/keyraw.h"
  64 #include "ldns/rrdef.h"
  65 #include <stdarg.h>
  66 #include <ctype.h>
  67
  68 /** number of times a key must be seen before it can become valid */
  69 #define MIN_PENDINGCOUNT 2
  70
  71 /** Event: Revoked */
  72 static void do_revoked(struct module_env* env, struct autr_ta* anchor, int* c);
  73
  74 struct autr_global_data* autr_global_create(void)
  75 {
  76         struct autr_global_data* global;
  77         global = (struct autr_global_data*)malloc(sizeof(*global));
  78         if(!global)
  79                 return NULL;
  80         rbtree_init(&global->probe, &probetree_cmp);
  81         return global;
  82 }
  83
  84 void autr_global_delete(struct autr_global_data* global)
  85 {
  86         if(!global)
  87                 return;
  88         /* elements deleted by parent */
  89         memset(global, 0, sizeof(*global));
  90         free(global);
  91 }
  92
  93 int probetree_cmp(const void* x, const void* y)
  94 {
  95         struct trust_anchor* a = (struct trust_anchor*)x;
  96         struct trust_anchor* b = (struct trust_anchor*)y;
  97         log_assert(a->autr && b->autr);
  98         if(a->autr->next_probe_time < b->autr->next_probe_time)
  99                 return -1;
 100         if(a->autr->next_probe_time > b->autr->next_probe_time)
 101                 return 1;
 102         /* time is equal, sort on trust point identity */
 103         return anchor_cmp(x, y);
 104 }
 105
 106 size_t
 107 autr_get_num_anchors(struct val_anchors* anchors)
 108 {
 109         size_t res = 0;
 110         if(!anchors)
 111                 return 0;
 112         lock_basic_lock(&anchors->lock);
 113         if(anchors->autr)
 114                 res = anchors->autr->probe.count;
 115         lock_basic_unlock(&anchors->lock);
 116         return res;
 117 }
 118
 119 /** Position in string */
 120 static int
 121 position_in_string(char *str, const char* sub)
 122 {
 123         char* pos = strstr(str, sub);
 124         if(pos)
 125                 return (int)(pos-str)+(int)strlen(sub);
 126         return -1;
 127 }
 128
 129 /** Debug routine to print pretty key information */
 130 static void
 131 verbose_key(struct autr_ta* ta, enum verbosity_value level,
 132         const char* format, ...) ATTR_FORMAT(printf, 3, 4);
 133
 134 /**
 135  * Implementation of debug pretty key print
 136  * @param ta: trust anchor key with DNSKEY data.
 137  * @param level: verbosity level to print at.
 138  * @param format: printf style format string.
 139  */
 140 static void
 141 verbose_key(struct autr_ta* ta, enum verbosity_value level,
 142         const char* format, ...)
 143 {
 144         va_list args;
 145         va_start(args, format);
 146         if(verbosity >= level) {
 147                 char* str = sldns_wire2str_dname(ta->rr, ta->dname_len);
 148                 int keytag = (int)sldns_calc_keytag_raw(sldns_wirerr_get_rdata(
 149                         ta->rr, ta->rr_len, ta->dname_len),
 150                         sldns_wirerr_get_rdatalen(ta->rr, ta->rr_len,
 151                         ta->dname_len));
 152                 char msg[MAXSYSLOGMSGLEN];
 153                 vsnprintf(msg, sizeof(msg), format, args);
 154                 verbose(level, "%s key %d %s", str?str:"??", keytag, msg);
 155                 free(str);
 156         }
 157         va_end(args);
 158 }
 159
 160 /**
 161  * Parse comments
 162  * @param str: to parse
 163  * @param ta: trust key autotrust metadata
 164  * @return false on failure.
 165  */
 166 static int
 167 parse_comments(char* str, struct autr_ta* ta)
 168 {
 169         int len = (int)strlen(str), pos = 0, timestamp = 0;
 170         char* comment = (char*) malloc(sizeof(char)*len+1);
 171         char* comments = comment;
 172         if(!comment) {
 173                 log_err("malloc failure in parse");
 174                 return 0;
 175         }
 176         /* skip over whitespace and data at start of line */
 177         while (*str != '\0' && *str != ';')
 178                 str++;
 179         if (*str == ';')
 180                 str++;
 181         /* copy comments */
 182         while (*str != '\0')
 183         {
 184                 *comments = *str;
 185                 comments++;
 186                 str++;
 187         }
 188         *comments = '\0';
 189
 190         comments = comment;
 191
 192         /* read state */
 193         pos = position_in_string(comments, "state=");
 194         if (pos >= (int) strlen(comments))
 195         {
 196                 log_err("parse error");
 197                 free(comment);
 198                 return 0;
 199         }
 200         if (pos <= 0)
 201                 ta->s = AUTR_STATE_VALID;
 202         else
 203         {
 204                 int s = (int) comments[pos] - '0';
 205                 switch(s)
 206                 {
 207                         case AUTR_STATE_START:
 208                         case AUTR_STATE_ADDPEND:
 209                         case AUTR_STATE_VALID:
 210                         case AUTR_STATE_MISSING:
 211                         case AUTR_STATE_REVOKED:
 212                         case AUTR_STATE_REMOVED:
 213                                 ta->s = s;
 214                                 break;
 215                         default:
 216                                 verbose_key(ta, VERB_OPS, "has undefined "
 217                                         "state, considered NewKey");
 218                                 ta->s = AUTR_STATE_START;
 219                                 break;
 220                 }
 221         }
 222         /* read pending count */
 223         pos = position_in_string(comments, "count=");
 224         if (pos >= (int) strlen(comments))
 225         {
 226                 log_err("parse error");
 227                 free(comment);
 228                 return 0;
 229         }
 230         if (pos <= 0)
 231                 ta->pending_count = 0;
 232         else
 233         {
 234                 comments += pos;
 235                 ta->pending_count = (uint8_t)atoi(comments);
 236         }
 237
 238         /* read last change */
 239         pos = position_in_string(comments, "lastchange=");
 240         if (pos >= (int) strlen(comments))
 241         {
 242                 log_err("parse error");
 243                 free(comment);
 244                 return 0;
 245         }
 246         if (pos >= 0)
 247         {
 248                 comments += pos;
 249                 timestamp = atoi(comments);
 250         }
 251         if (pos < 0 || !timestamp)
 252                 ta->last_change = 0;
 253         else
 254                 ta->last_change = (time_t)timestamp;
 255
 256         free(comment);
 257         return 1;
 258 }
 259
 260 /** Check if a line contains data (besides comments) */
 261 static int
 262 str_contains_data(char* str, char comment)
 263 {
 264         while (*str != '\0') {
 265                 if (*str == comment || *str == '\n')
 266                         return 0;
 267                 if (*str != ' ' && *str != '\t')
 268                         return 1;
 269                 str++;
 270         }
 271         return 0;
 272 }
 273
 274 /** Get DNSKEY flags
 275  * rdata without rdatalen in front of it. */
 276 static int
 277 dnskey_flags(uint16_t t, uint8_t* rdata, size_t len)
 278 {
 279         uint16_t f;
 280         if(t != LDNS_RR_TYPE_DNSKEY)
 281                 return 0;
 282         if(len < 2)
 283                 return 0;
 284         memmove(&f, rdata, 2);
 285         f = ntohs(f);
 286         return (int)f;
 287 }
 288
 289 /** Check if KSK DNSKEY.
 290  * pass rdata without rdatalen in front of it */
 291 static int
 292 rr_is_dnskey_sep(uint16_t t, uint8_t* rdata, size_t len)
 293 {
 294         return (dnskey_flags(t, rdata, len)&DNSKEY_BIT_SEP);
 295 }
 296
 297 /** Check if TA is KSK DNSKEY */
 298 static int
 299 ta_is_dnskey_sep(struct autr_ta* ta)
 300 {
 301         return (dnskey_flags(
 302                 sldns_wirerr_get_type(ta->rr, ta->rr_len, ta->dname_len),
 303                 sldns_wirerr_get_rdata(ta->rr, ta->rr_len, ta->dname_len),
 304                 sldns_wirerr_get_rdatalen(ta->rr, ta->rr_len, ta->dname_len)
 305                 ) & DNSKEY_BIT_SEP);
 306 }
 307
 308 /** Check if REVOKED DNSKEY
 309  * pass rdata without rdatalen in front of it */
 310 static int
 311 rr_is_dnskey_revoked(uint16_t t, uint8_t* rdata, size_t len)
 312 {
 313         return (dnskey_flags(t, rdata, len)&LDNS_KEY_REVOKE_KEY);
 314 }
 315
 316 /** create ta */
 317 static struct autr_ta*
 318 autr_ta_create(uint8_t* rr, size_t rr_len, size_t dname_len)
 319 {
 320         struct autr_ta* ta = (struct autr_ta*)calloc(1, sizeof(*ta));
 321         if(!ta) {
 322                 free(rr);
 323                 return NULL;
 324         }
 325         ta->rr = rr;
 326         ta->rr_len = rr_len;
 327         ta->dname_len = dname_len;
 328         return ta;
 329 }
 330
 331 /** create tp */
 332 static struct trust_anchor*
 333 autr_tp_create(struct val_anchors* anchors, uint8_t* own, size_t own_len,
 334         uint16_t dc)
 335 {
 336         struct trust_anchor* tp = (struct trust_anchor*)calloc(1, sizeof(*tp));
 337         if(!tp) return NULL;
 338         tp->name = memdup(own, own_len);
 339         if(!tp->name) {
 340                 free(tp);
 341                 return NULL;
 342         }
 343         tp->namelen = own_len;
 344         tp->namelabs = dname_count_labels(tp->name);
 345         tp->node.key = tp;
 346         tp->dclass = dc;
 347         tp->autr = (struct autr_point_data*)calloc(1, sizeof(*tp->autr));
 348         if(!tp->autr) {
 349                 free(tp->name);
 350                 free(tp);
 351                 return NULL;
 352         }
 353         tp->autr->pnode.key = tp;
 354
 355         lock_basic_lock(&anchors->lock);
 356         if(!rbtree_insert(anchors->tree, &tp->node)) {
 357                 lock_basic_unlock(&anchors->lock);
 358                 log_err("trust anchor presented twice");
 359                 free(tp->name);
 360                 free(tp->autr);
 361                 free(tp);
 362                 return NULL;
 363         }
 364         if(!rbtree_insert(&anchors->autr->probe, &tp->autr->pnode)) {
 365                 (void)rbtree_delete(anchors->tree, tp);
 366                 lock_basic_unlock(&anchors->lock);
 367                 log_err("trust anchor in probetree twice");
 368                 free(tp->name);
 369                 free(tp->autr);
 370                 free(tp);
 371                 return NULL;
 372         }
 373         lock_basic_unlock(&anchors->lock);
 374         lock_basic_init(&tp->lock);
 375         lock_protect(&tp->lock, tp, sizeof(*tp));
 376         lock_protect(&tp->lock, tp->autr, sizeof(*tp->autr));
 377         return tp;
 378 }
 379
 380 /** delete assembled rrsets */
 381 static void
 382 autr_rrset_delete(struct ub_packed_rrset_key* r)
 383 {
 384         if(r) {
 385                 free(r->rk.dname);
 386                 free(r->entry.data);
 387                 free(r);
 388         }
 389 }
 390
 391 void autr_point_delete(struct trust_anchor* tp)
 392 {
 393         if(!tp)
 394                 return;
 395         lock_unprotect(&tp->lock, tp);
 396         lock_unprotect(&tp->lock, tp->autr);
 397         lock_basic_destroy(&tp->lock);
 398         autr_rrset_delete(tp->ds_rrset);
 399         autr_rrset_delete(tp->dnskey_rrset);
 400         if(tp->autr) {
 401                 struct autr_ta* p = tp->autr->keys, *np;
 402                 while(p) {
 403                         np = p->next;
 404                         free(p->rr);
 405                         free(p);
 406                         p = np;
 407                 }
 408                 free(tp->autr->file);
 409                 free(tp->autr);
 410         }
 411         free(tp->name);
 412         free(tp);
 413 }
 414
 415 /** find or add a new trust point for autotrust */
 416 static struct trust_anchor*
 417 find_add_tp(struct val_anchors* anchors, uint8_t* rr, size_t rr_len,
 418         size_t dname_len)
 419 {
 420         struct trust_anchor* tp;
 421         tp = anchor_find(anchors, rr, dname_count_labels(rr), dname_len,
 422                 sldns_wirerr_get_class(rr, rr_len, dname_len));
 423         if(tp) {
 424                 if(!tp->autr) {
 425                         log_err("anchor cannot be with and without autotrust");
 426                         lock_basic_unlock(&tp->lock);
 427                         return NULL;
 428                 }
 429                 return tp;
 430         }
 431         tp = autr_tp_create(anchors, rr, dname_len, sldns_wirerr_get_class(rr,
 432                 rr_len, dname_len));
 433         lock_basic_lock(&tp->lock);
 434         return tp;
 435 }
 436
 437 /** Add trust anchor from RR */
 438 static struct autr_ta*
 439 add_trustanchor_frm_rr(struct val_anchors* anchors, uint8_t* rr, size_t rr_len,
 440         size_t dname_len, struct trust_anchor** tp)
 441 {
 442         struct autr_ta* ta = autr_ta_create(rr, rr_len, dname_len);
 443         if(!ta)
 444                 return NULL;
 445         *tp = find_add_tp(anchors, rr, rr_len, dname_len);
 446         if(!*tp) {
 447                 free(ta->rr);
 448                 free(ta);
 449                 return NULL;
 450         }
 451         /* add ta to tp */
 452         ta->next = (*tp)->autr->keys;
 453         (*tp)->autr->keys = ta;
 454         lock_basic_unlock(&(*tp)->lock);
 455         return ta;
 456 }
 457
 458 /**
 459  * Add new trust anchor from a string in file.
 460  * @param anchors: all anchors
 461  * @param str: string with anchor and comments, if any comments.
 462  * @param tp: trust point returned.
 463  * @param origin: what to use for @
 464  * @param origin_len: length of origin
 465  * @param prev: previous rr name
 466  * @param prev_len: length of prev
 467  * @param skip: if true, the result is NULL, but not an error, skip it.
 468  * @return new key in trust point.
 469  */
 470 static struct autr_ta*
 471 add_trustanchor_frm_str(struct val_anchors* anchors, char* str,
 472         struct trust_anchor** tp, uint8_t* origin, size_t origin_len,
 473         uint8_t** prev, size_t* prev_len, int* skip)
 474 {
 475         uint8_t rr[LDNS_RR_BUF_SIZE];
 476         size_t rr_len = sizeof(rr), dname_len;
 477         uint8_t* drr;
 478         int lstatus;
 479         if (!str_contains_data(str, ';')) {
 480                 *skip = 1;
 481                 return NULL; /* empty line */
 482         }
 483         if(0 != (lstatus = sldns_str2wire_rr_buf(str, rr, &rr_len, &dname_len,
 484                 0, origin, origin_len, *prev, *prev_len)))
 485         {
 486                 log_err("ldns error while converting string to RR at%d: %s: %s",
 487                         LDNS_WIREPARSE_OFFSET(lstatus),
 488                         sldns_get_errorstr_parse(lstatus), str);
 489                 return NULL;
 490         }
 491         free(*prev);
 492         *prev = memdup(rr, dname_len);
 493         *prev_len = dname_len;
 494         if(!*prev) {
 495                 log_err("malloc failure in add_trustanchor");
 496                 return NULL;
 497         }
 498         if(sldns_wirerr_get_type(rr, rr_len, dname_len)!=LDNS_RR_TYPE_DNSKEY &&
 499                 sldns_wirerr_get_type(rr, rr_len, dname_len)!=LDNS_RR_TYPE_DS) {
 500                 *skip = 1;
 501                 return NULL; /* only DS and DNSKEY allowed */
 502         }
 503         drr = memdup(rr, rr_len);
 504         if(!drr) {
 505                 log_err("malloc failure in add trustanchor");
 506                 return NULL;
 507         }
 508         return add_trustanchor_frm_rr(anchors, drr, rr_len, dname_len, tp);
 509 }
 510
 511 /**
 512  * Load single anchor
 513  * @param anchors: all points.
 514  * @param str: comments line
 515  * @param fname: filename
 516  * @param origin: the $ORIGIN.
 517  * @param origin_len: length of origin
 518  * @param prev: passed to ldns.
 519  * @param prev_len: length of prev
 520  * @param skip: if true, the result is NULL, but not an error, skip it.
 521  * @return false on failure, otherwise the tp read.
 522  */
 523 static struct trust_anchor*
 524 load_trustanchor(struct val_anchors* anchors, char* str, const char* fname,
 525         uint8_t* origin, size_t origin_len, uint8_t** prev, size_t* prev_len,
 526         int* skip)
 527 {
 528         struct autr_ta* ta = NULL;
 529         struct trust_anchor* tp = NULL;
 530
 531         ta = add_trustanchor_frm_str(anchors, str, &tp, origin, origin_len,
 532                 prev, prev_len, skip);
 533         if(!ta)
 534                 return NULL;
 535         lock_basic_lock(&tp->lock);
 536         if(!parse_comments(str, ta)) {
 537                 lock_basic_unlock(&tp->lock);
 538                 return NULL;
 539         }
 540         if(!tp->autr->file) {
 541                 tp->autr->file = strdup(fname);
 542                 if(!tp->autr->file) {
 543                         lock_basic_unlock(&tp->lock);
 544                         log_err("malloc failure");
 545                         return NULL;
 546                 }
 547         }
 548         lock_basic_unlock(&tp->lock);
 549         return tp;
 550 }
 551
 552 /** iterator for DSes from keylist. return true if a next element exists */
 553 static int
 554 assemble_iterate_ds(struct autr_ta** list, uint8_t** rr, size_t* rr_len,
 555         size_t* dname_len)
 556 {
 557         while(*list) {
 558                 if(sldns_wirerr_get_type((*list)->rr, (*list)->rr_len,
 559                         (*list)->dname_len) == LDNS_RR_TYPE_DS) {
 560                         *rr = (*list)->rr;
 561                         *rr_len = (*list)->rr_len;
 562                         *dname_len = (*list)->dname_len;
 563                         *list = (*list)->next;
 564                         return 1;
 565                 }
 566                 *list = (*list)->next;
 567         }
 568         return 0;
 569 }
 570
 571 /** iterator for DNSKEYs from keylist. return true if a next element exists */
 572 static int
 573 assemble_iterate_dnskey(struct autr_ta** list, uint8_t** rr, size_t* rr_len,
 574         size_t* dname_len)
 575 {
 576         while(*list) {
 577                 if(sldns_wirerr_get_type((*list)->rr, (*list)->rr_len,
 578                    (*list)->dname_len) != LDNS_RR_TYPE_DS &&
 579                         ((*list)->s == AUTR_STATE_VALID ||
 580                          (*list)->s == AUTR_STATE_MISSING)) {
 581                         *rr = (*list)->rr;
 582                         *rr_len = (*list)->rr_len;
 583                         *dname_len = (*list)->dname_len;
 584                         *list = (*list)->next;
 585                         return 1;
 586                 }
 587                 *list = (*list)->next;
 588         }
 589         return 0;
 590 }
 591
 592 /** see if iterator-list has any elements in it, or it is empty */
 593 static int
 594 assemble_iterate_hasfirst(int iter(struct autr_ta**, uint8_t**, size_t*,
 595         size_t*), struct autr_ta* list)
 596 {
 597         uint8_t* rr = NULL;
 598         size_t rr_len = 0, dname_len = 0;
 599         return iter(&list, &rr, &rr_len, &dname_len);
 600 }
 601
 602 /** number of elements in iterator list */
 603 static size_t
 604 assemble_iterate_count(int iter(struct autr_ta**, uint8_t**, size_t*,
 605         size_t*), struct autr_ta* list)
 606 {
 607         uint8_t* rr = NULL;
 608         size_t i = 0, rr_len = 0, dname_len = 0;
 609         while(iter(&list, &rr, &rr_len, &dname_len)) {
 610                 i++;
 611         }
 612         return i;
 613 }
 614
 615 /**
 616  * Create a ub_packed_rrset_key allocated on the heap.
 617  * It therefore does not have the correct ID value, and cannot be used
 618  * inside the cache.  It can be used in storage outside of the cache.
 619  * Keys for the cache have to be obtained from alloc.h .
 620  * @param iter: iterator over the elements in the list.  It filters elements.
 621  * @param list: the list.
 622  * @return key allocated or NULL on failure.
 623  */
 624 static struct ub_packed_rrset_key*
 625 ub_packed_rrset_heap_key(int iter(struct autr_ta**, uint8_t**, size_t*,
 626         size_t*), struct autr_ta* list)
 627 {
 628         uint8_t* rr = NULL;
 629         size_t rr_len = 0, dname_len = 0;
 630         struct ub_packed_rrset_key* k;
 631         if(!iter(&list, &rr, &rr_len, &dname_len))
 632                 return NULL;
 633         k = (struct ub_packed_rrset_key*)calloc(1, sizeof(*k));
 634         if(!k)
 635                 return NULL;
 636         k->rk.type = htons(sldns_wirerr_get_type(rr, rr_len, dname_len));
 637         k->rk.rrset_class = htons(sldns_wirerr_get_class(rr, rr_len, dname_len));
 638         k->rk.dname_len = dname_len;
 639         k->rk.dname = memdup(rr, dname_len);
 640         if(!k->rk.dname) {
 641                 free(k);
 642                 return NULL;
 643         }
 644         return k;
 645 }
 646
 647 /**
 648  * Create packed_rrset data on the heap.
 649  * @param iter: iterator over the elements in the list.  It filters elements.
 650  * @param list: the list.
 651  * @return data allocated or NULL on failure.
 652  */
 653 static struct packed_rrset_data*
 654 packed_rrset_heap_data(int iter(struct autr_ta**, uint8_t**, size_t*,
 655         size_t*), struct autr_ta* list)
 656 {
 657         uint8_t* rr = NULL;
 658         size_t rr_len = 0, dname_len = 0;
 659         struct packed_rrset_data* data;
 660         size_t count=0, rrsig_count=0, len=0, i, total;
 661         uint8_t* nextrdata;
 662         struct autr_ta* list_i;
 663         time_t ttl = 0;
 664
 665         list_i = list;
 666         while(iter(&list_i, &rr, &rr_len, &dname_len)) {
 667                 if(sldns_wirerr_get_type(rr, rr_len, dname_len) ==
 668                         LDNS_RR_TYPE_RRSIG)
 669                         rrsig_count++;
 670                 else    count++;
 671                 /* sizeof the rdlength + rdatalen */
 672                 len += 2 + sldns_wirerr_get_rdatalen(rr, rr_len, dname_len);
 673                 ttl = (time_t)sldns_wirerr_get_ttl(rr, rr_len, dname_len);
 674         }
 675         if(count == 0 && rrsig_count == 0)
 676                 return NULL;
 677
 678         /* allocate */
 679         total = count + rrsig_count;
 680         len += sizeof(*data) + total*(sizeof(size_t) + sizeof(time_t) +
 681                 sizeof(uint8_t*));
 682         data = (struct packed_rrset_data*)calloc(1, len);
 683         if(!data)
 684                 return NULL;
 685
 686         /* fill it */
 687         data->ttl = ttl;
 688         data->count = count;
 689         data->rrsig_count = rrsig_count;
 690         data->rr_len = (size_t*)((uint8_t*)data +
 691                 sizeof(struct packed_rrset_data));
 692         data->rr_data = (uint8_t**)&(data->rr_len[total]);
 693         data->rr_ttl = (time_t*)&(data->rr_data[total]);
 694         nextrdata = (uint8_t*)&(data->rr_ttl[total]);
 695
 696         /* fill out len, ttl, fields */
 697         list_i = list;
 698         i = 0;
 699         while(iter(&list_i, &rr, &rr_len, &dname_len)) {
 700                 data->rr_ttl[i] = (time_t)sldns_wirerr_get_ttl(rr, rr_len,
 701                         dname_len);
 702                 if(data->rr_ttl[i] < data->ttl)
 703                         data->ttl = data->rr_ttl[i];
 704                 data->rr_len[i] = 2 /* the rdlength */ +
 705                         sldns_wirerr_get_rdatalen(rr, rr_len, dname_len);
 706                 i++;
 707         }
 708
 709         /* fixup rest of ptrs */
 710         for(i=0; i<total; i++) {
 711                 data->rr_data[i] = nextrdata;
 712                 nextrdata += data->rr_len[i];
 713         }
 714
 715         /* copy data in there */
 716         list_i = list;
 717         i = 0;
 718         while(iter(&list_i, &rr, &rr_len, &dname_len)) {
 719                 memmove(data->rr_data[i],
 720                         sldns_wirerr_get_rdatawl(rr, rr_len, dname_len),
 721                         data->rr_len[i]);
 722                 i++;
 723         }
 724
 725         if(data->rrsig_count && data->count == 0) {
 726                 data->count = data->rrsig_count; /* rrset type is RRSIG */
 727                 data->rrsig_count = 0;
 728         }
 729         return data;
 730 }
 731
 732 /**
 733  * Assemble the trust anchors into DS and DNSKEY packed rrsets.
 734  * Uses only VALID and MISSING DNSKEYs.
 735  * Read the sldns_rrs and builds packed rrsets
 736  * @param tp: the trust point. Must be locked.
 737  * @return false on malloc failure.
 738  */
 739 static int
 740 autr_assemble(struct trust_anchor* tp)
 741 {
 742         struct ub_packed_rrset_key* ubds=NULL, *ubdnskey=NULL;
 743
 744         /* make packed rrset keys - malloced with no ID number, they
 745          * are not in the cache */
 746         /* make packed rrset data (if there is a key) */
 747         if(assemble_iterate_hasfirst(assemble_iterate_ds, tp->autr->keys)) {
 748                 ubds = ub_packed_rrset_heap_key(
 749                         assemble_iterate_ds, tp->autr->keys);
 750                 if(!ubds)
 751                         goto error_cleanup;
 752                 ubds->entry.data = packed_rrset_heap_data(
 753                         assemble_iterate_ds, tp->autr->keys);
 754                 if(!ubds->entry.data)
 755                         goto error_cleanup;
 756         }
 757
 758         /* make packed DNSKEY data */
 759         if(assemble_iterate_hasfirst(assemble_iterate_dnskey, tp->autr->keys)) {
 760                 ubdnskey = ub_packed_rrset_heap_key(
 761                         assemble_iterate_dnskey, tp->autr->keys);
 762                 if(!ubdnskey)
 763                         goto error_cleanup;
 764                 ubdnskey->entry.data = packed_rrset_heap_data(
 765                         assemble_iterate_dnskey, tp->autr->keys);
 766                 if(!ubdnskey->entry.data) {
 767                 error_cleanup:
 768                         autr_rrset_delete(ubds);
 769                         autr_rrset_delete(ubdnskey);
 770                         return 0;
 771                 }
 772         }
 773
 774         /* we have prepared the new keys so nothing can go wrong any more.
 775          * And we are sure we cannot be left without trustanchor after
 776          * any errors. Put in the new keys and remove old ones. */
 777
 778         /* free the old data */
 779         autr_rrset_delete(tp->ds_rrset);
 780         autr_rrset_delete(tp->dnskey_rrset);
 781
 782         /* assign the data to replace the old */
 783         tp->ds_rrset = ubds;
 784         tp->dnskey_rrset = ubdnskey;
 785         tp->numDS = assemble_iterate_count(assemble_iterate_ds,
 786                 tp->autr->keys);
 787         tp->numDNSKEY = assemble_iterate_count(assemble_iterate_dnskey,
 788                 tp->autr->keys);
 789         return 1;
 790 }
 791
 792 /** parse integer */
 793 static unsigned int
 794 parse_int(char* line, int* ret)
 795 {
 796         char *e;
 797         unsigned int x = (unsigned int)strtol(line, &e, 10);
 798         if(line == e) {
 799                 *ret = -1; /* parse error */
 800                 return 0;
 801         }
 802         *ret = 1; /* matched */
 803         return x;
 804 }
 805
 806 /** parse id sequence for anchor */
 807 static struct trust_anchor*
 808 parse_id(struct val_anchors* anchors, char* line)
 809 {
 810         struct trust_anchor *tp;
 811         int r;
 812         uint16_t dclass;
 813         uint8_t* dname;
 814         size_t dname_len;
 815         /* read the owner name */
 816         char* next = strchr(line, ' ');
 817         if(!next)
 818                 return NULL;
 819         next[0] = 0;
 820         dname = sldns_str2wire_dname(line, &dname_len);
 821         if(!dname)
 822                 return NULL;
 823
 824         /* read the class */
 825         dclass = parse_int(next+1, &r);
 826         if(r == -1) {
 827                 free(dname);
 828                 return NULL;
 829         }
 830
 831         /* find the trust point */
 832         tp = autr_tp_create(anchors, dname, dname_len, dclass);
 833         free(dname);
 834         return tp;
 835 }
 836
 837 /**
 838  * Parse variable from trustanchor header
 839  * @param line: to parse
 840  * @param anchors: the anchor is added to this, if "id:" is seen.
 841  * @param anchor: the anchor as result value or previously returned anchor
 842  *      value to read the variable lines into.
 843  * @return: 0 no match, -1 failed syntax error, +1 success line read.
 844  *      +2 revoked trust anchor file.
 845  */
 846 static int
 847 parse_var_line(char* line, struct val_anchors* anchors,
 848         struct trust_anchor** anchor)
 849 {
 850         struct trust_anchor* tp = *anchor;
 851         int r = 0;
 852         if(strncmp(line, ";;id: ", 6) == 0) {
 853                 *anchor = parse_id(anchors, line+6);
 854                 if(!*anchor) return -1;
 855                 else return 1;
 856         } else if(strncmp(line, ";;REVOKED", 9) == 0) {
 857                 if(tp) {
 858                         log_err("REVOKED statement must be at start of file");
 859                         return -1;
 860                 }
 861                 return 2;
 862         } else if(strncmp(line, ";;last_queried: ", 16) == 0) {
 863                 if(!tp) return -1;
 864                 lock_basic_lock(&tp->lock);
 865                 tp->autr->last_queried = (time_t)parse_int(line+16, &r);
 866                 lock_basic_unlock(&tp->lock);
 867         } else if(strncmp(line, ";;last_success: ", 16) == 0) {
 868                 if(!tp) return -1;
 869                 lock_basic_lock(&tp->lock);
 870                 tp->autr->last_success = (time_t)parse_int(line+16, &r);
 871                 lock_basic_unlock(&tp->lock);
 872         } else if(strncmp(line, ";;next_probe_time: ", 19) == 0) {
 873                 if(!tp) return -1;
 874                 lock_basic_lock(&anchors->lock);
 875                 lock_basic_lock(&tp->lock);
 876                 (void)rbtree_delete(&anchors->autr->probe, tp);
 877                 tp->autr->next_probe_time = (time_t)parse_int(line+19, &r);
 878                 (void)rbtree_insert(&anchors->autr->probe, &tp->autr->pnode);
 879                 lock_basic_unlock(&tp->lock);
 880                 lock_basic_unlock(&anchors->lock);
 881         } else if(strncmp(line, ";;query_failed: ", 16) == 0) {
 882                 if(!tp) return -1;
 883                 lock_basic_lock(&tp->lock);
 884                 tp->autr->query_failed = (uint8_t)parse_int(line+16, &r);
 885                 lock_basic_unlock(&tp->lock);
 886         } else if(strncmp(line, ";;query_interval: ", 18) == 0) {
 887                 if(!tp) return -1;
 888                 lock_basic_lock(&tp->lock);
 889                 tp->autr->query_interval = (time_t)parse_int(line+18, &r);
 890                 lock_basic_unlock(&tp->lock);
 891         } else if(strncmp(line, ";;retry_time: ", 14) == 0) {
 892                 if(!tp) return -1;
 893                 lock_basic_lock(&tp->lock);
 894                 tp->autr->retry_time = (time_t)parse_int(line+14, &r);
 895                 lock_basic_unlock(&tp->lock);
 896         }
 897         return r;
 898 }
 899
 900 /** handle origin lines */
 901 static int
 902 handle_origin(char* line, uint8_t** origin, size_t* origin_len)
 903 {
 904         size_t len = 0;
 905         while(isspace((unsigned char)*line))
 906                 line++;
 907         if(strncmp(line, "$ORIGIN", 7) != 0)
 908                 return 0;
 909         free(*origin);
 910         line += 7;
 911         while(isspace((unsigned char)*line))
 912                 line++;
 913         *origin = sldns_str2wire_dname(line, &len);
 914         *origin_len = len;
 915         if(!*origin)
 916                 log_warn("malloc failure or parse error in $ORIGIN");
 917         return 1;
 918 }
 919
 920 /** Read one line and put multiline RRs onto one line string */
 921 static int
 922 read_multiline(char* buf, size_t len, FILE* in, int* linenr)
 923 {
 924         char* pos = buf;
 925         size_t left = len;
 926         int depth = 0;
 927         buf[len-1] = 0;
 928         while(left > 0 && fgets(pos, (int)left, in) != NULL) {
 929                 size_t i, poslen = strlen(pos);
 930                 (*linenr)++;
 931
 932                 /* check what the new depth is after the line */
 933                 /* this routine cannot handle braces inside quotes,
 934                    say for TXT records, but this routine only has to read keys */
 935                 for(i=0; i<poslen; i++) {
 936                         if(pos[i] == '(') {
 937                                 depth++;
 938                         } else if(pos[i] == ')') {
 939                                 if(depth == 0) {
 940                                         log_err("mismatch: too many ')'");
 941                                         return -1;
 942                                 }
 943                                 depth--;
 944                         } else if(pos[i] == ';') {
 945                                 break;
 946                         }
 947                 }
 948
 949                 /* normal oneline or last line: keeps newline and comments */
 950                 if(depth == 0) {
 951                         return 1;
 952                 }
 953
 954                 /* more lines expected, snip off comments and newline */
 955                 if(poslen>0)
 956                         pos[poslen-1] = 0; /* strip newline */
 957                 if(strchr(pos, ';'))
 958                         strchr(pos, ';')[0] = 0; /* strip comments */
 959
 960                 /* move to paste other lines behind this one */
 961                 poslen = strlen(pos);
 962                 pos += poslen;
 963                 left -= poslen;
 964                 /* the newline is changed into a space */
 965                 if(left <= 2 /* space and eos */) {
 966                         log_err("line too long");
 967                         return -1;
 968                 }
 969                 pos[0] = ' ';
 970                 pos[1] = 0;
 971                 pos += 1;
 972                 left -= 1;
 973         }
 974         if(depth != 0) {
 975                 log_err("mismatch: too many '('");
 976                 return -1;
 977         }
 978         if(pos != buf)
 979                 return 1;
 980         return 0;
 981 }
 982
 983 int autr_read_file(struct val_anchors* anchors, const char* nm)
 984 {
 985         /* the file descriptor */
 986         FILE* fd;
 987         /* keep track of line numbers */
 988         int line_nr = 0;
 989         /* single line */
 990         char line[10240];
 991         /* trust point being read */
 992         struct trust_anchor *tp = NULL, *tp2;
 993         int r;
 994         /* for $ORIGIN parsing */
 995         uint8_t *origin=NULL, *prev=NULL;
 996         size_t origin_len=0, prev_len=0;
 997
 998         if (!(fd = fopen(nm, "r"))) {
 999                 log_err("unable to open %s for reading: %s",
1000                         nm, strerror(errno));
1001                 return 0;
1002         }
1003         verbose(VERB_ALGO, "reading autotrust anchor file %s", nm);
1004         while ( (r=read_multiline(line, sizeof(line), fd, &line_nr)) != 0) {
1005                 if(r == -1 || (r = parse_var_line(line, anchors, &tp)) == -1) {
1006                         log_err("could not parse auto-trust-anchor-file "
1007                                 "%s line %d", nm, line_nr);
1008                         fclose(fd);
1009                         free(origin);
1010                         free(prev);
1011                         return 0;
1012                 } else if(r == 1) {
1013                         continue;
1014                 } else if(r == 2) {
1015                         log_warn("trust anchor %s has been revoked", nm);
1016                         fclose(fd);
1017                         free(origin);
1018                         free(prev);
1019                         return 1;
1020                 }
1021                 if (!str_contains_data(line, ';'))
1022                         continue; /* empty lines allowed */
1023                 if(handle_origin(line, &origin, &origin_len))
1024                         continue;
1025                 r = 0;
1026                 if(!(tp2=load_trustanchor(anchors, line, nm, origin,
1027                         origin_len, &prev, &prev_len, &r))) {
1028                         if(!r) log_err("failed to load trust anchor from %s "
1029                                 "at line %i, skipping", nm, line_nr);
1030                         /* try to do the rest */
1031                         continue;
1032                 }
1033                 if(tp && tp != tp2) {
1034                         log_err("file %s has mismatching data inside: "
1035                                 "the file may only contain keys for one name, "
1036                                 "remove keys for other domain names", nm);
1037                         fclose(fd);
1038                         free(origin);
1039                         free(prev);
1040                         return 0;
1041                 }
1042                 tp = tp2;
1043         }
1044         fclose(fd);
1045         free(origin);
1046         free(prev);
1047         if(!tp) {
1048                 log_err("failed to read %s", nm);
1049                 return 0;
1050         }
1051
1052         /* now assemble the data into DNSKEY and DS packed rrsets */
1053         lock_basic_lock(&tp->lock);
1054         if(!autr_assemble(tp)) {
1055                 lock_basic_unlock(&tp->lock);
1056                 log_err("malloc failure assembling %s", nm);
1057                 return 0;
1058         }
1059         lock_basic_unlock(&tp->lock);
1060         return 1;
1061 }
1062
1063 /** string for a trustanchor state */
1064 static const char*
1065 trustanchor_state2str(autr_state_t s)
1066 {
1067         switch (s) {
1068                 case AUTR_STATE_START:       return "  START  ";
1069                 case AUTR_STATE_ADDPEND:     return " ADDPEND ";
1070                 case AUTR_STATE_VALID:       return "  VALID  ";
1071                 case AUTR_STATE_MISSING:     return " MISSING ";
1072                 case AUTR_STATE_REVOKED:     return " REVOKED ";
1073                 case AUTR_STATE_REMOVED:     return " REMOVED ";
1074         }
1075         return " UNKNOWN ";
1076 }
1077
1078 /** print ID to file */
1079 static int
1080 print_id(FILE* out, char* fname, uint8_t* nm, size_t nmlen, uint16_t dclass)
1081 {
1082         char* s = sldns_wire2str_dname(nm, nmlen);
1083         if(!s) {
1084                 log_err("malloc failure in write to %s", fname);
1085                 return 0;
1086         }
1087         if(fprintf(out, ";;id: %s %d\n", s, (int)dclass) < 0) {
1088                 log_err("could not write to %s: %s", fname, strerror(errno));
1089                 free(s);
1090                 return 0;
1091         }
1092         free(s);
1093         return 1;
1094 }
1095
1096 static int
1097 autr_write_contents(FILE* out, char* fn, struct trust_anchor* tp)
1098 {
1099         char tmi[32];
1100         struct autr_ta* ta;
1101         char* str;
1102
1103         /* write pretty header */
1104         if(fprintf(out, "; autotrust trust anchor file\n") < 0) {
1105                 log_err("could not write to %s: %s", fn, strerror(errno));
1106                 return 0;
1107         }
1108         if(tp->autr->revoked) {
1109                 if(fprintf(out, ";;REVOKED\n") < 0 ||
1110                    fprintf(out, "; The zone has all keys revoked, and is\n"
1111                         "; considered as if it has no trust anchors.\n"
1112                         "; the remainder of the file is the last probe.\n"
1113                         "; to restart the trust anchor, overwrite this file.\n"
1114                         "; with one containing valid DNSKEYs or DSes.\n") < 0) {
1115                    log_err("could not write to %s: %s", fn, strerror(errno));
1116                    return 0;
1117                 }
1118         }
1119         if(!print_id(out, fn, tp->name, tp->namelen, tp->dclass)) {
1120                 return 0;
1121         }
1122         if(fprintf(out, ";;last_queried: %u ;;%s",
1123                 (unsigned int)tp->autr->last_queried,
1124                 ctime_r(&(tp->autr->last_queried), tmi)) < 0 ||
1125            fprintf(out, ";;last_success: %u ;;%s",
1126                 (unsigned int)tp->autr->last_success,
1127                 ctime_r(&(tp->autr->last_success), tmi)) < 0 ||
1128            fprintf(out, ";;next_probe_time: %u ;;%s",
1129                 (unsigned int)tp->autr->next_probe_time,
1130                 ctime_r(&(tp->autr->next_probe_time), tmi)) < 0 ||
1131            fprintf(out, ";;query_failed: %d\n", (int)tp->autr->query_failed)<0
1132            || fprintf(out, ";;query_interval: %d\n",
1133            (int)tp->autr->query_interval) < 0 ||
1134            fprintf(out, ";;retry_time: %d\n", (int)tp->autr->retry_time) < 0) {
1135                 log_err("could not write to %s: %s", fn, strerror(errno));
1136                 return 0;
1137         }
1138
1139         /* write anchors */
1140         for(ta=tp->autr->keys; ta; ta=ta->next) {
1141                 /* by default do not store START and REMOVED keys */
1142                 if(ta->s == AUTR_STATE_START)
1143                         continue;
1144                 if(ta->s == AUTR_STATE_REMOVED)
1145                         continue;
1146                 /* only store keys */
1147                 if(sldns_wirerr_get_type(ta->rr, ta->rr_len, ta->dname_len)
1148                         != LDNS_RR_TYPE_DNSKEY)
1149                         continue;
1150                 str = sldns_wire2str_rr(ta->rr, ta->rr_len);
1151                 if(!str || !str[0]) {
1152                         free(str);
1153                         log_err("malloc failure writing %s", fn);
1154                         return 0;
1155                 }
1156                 str[strlen(str)-1] = 0; /* remove newline */
1157                 if(fprintf(out, "%s ;;state=%d [%s] ;;count=%d "
1158                         ";;lastchange=%u ;;%s", str, (int)ta->s,
1159                         trustanchor_state2str(ta->s), (int)ta->pending_count,
1160                         (unsigned int)ta->last_change,
1161                         ctime_r(&(ta->last_change), tmi)) < 0) {
1162                    log_err("could not write to %s: %s", fn, strerror(errno));
1163                    free(str);
1164                    return 0;
1165                 }
1166                 free(str);
1167         }
1168         return 1;
1169 }
1170
1171 void autr_write_file(struct module_env* env, struct trust_anchor* tp)
1172 {
1173         FILE* out;
1174         char* fname = tp->autr->file;
1175         char tempf[2048];
1176         log_assert(tp->autr);
1177         if(!env) {
1178                 log_err("autr_write_file: Module environment is NULL.");
1179                 return;
1180         }
1181         /* unique name with pid number and thread number */
1182         snprintf(tempf, sizeof(tempf), "%s.%d-%d", fname, (int)getpid(),
1183                 env->worker?*(int*)env->worker:0);
1184         verbose(VERB_ALGO, "autotrust: write to disk: %s", tempf);
1185         out = fopen(tempf, "w");
1186         if(!out) {
1187                 log_err("could not open autotrust file for writing, %s: %s",
1188                         tempf, strerror(errno));
1189                 return;
1190         }
1191         if(!autr_write_contents(out, tempf, tp)) {
1192                 /* failed to write contents (completely) */
1193                 fclose(out);
1194                 unlink(tempf);
1195                 log_err("could not completely write: %s", fname);
1196                 return;
1197         }
1198         if(fclose(out) != 0) {
1199                 log_err("could not complete write: %s: %s",
1200                         fname, strerror(errno));
1201                 unlink(tempf);
1202                 return;
1203         }
1204         /* success; overwrite actual file */
1205         verbose(VERB_ALGO, "autotrust: replaced %s", fname);
1206 #ifdef UB_ON_WINDOWS
1207         (void)unlink(fname); /* windows does not replace file with rename() */
1208 #endif
1209         if(rename(tempf, fname) < 0) {
1210                 log_err("rename(%s to %s): %s", tempf, fname, strerror(errno));
1211         }
1212 }
1213
1214 /**
1215  * Verify if dnskey works for trust point
1216  * @param env: environment (with time) for verification
1217  * @param ve: validator environment (with options) for verification.
1218  * @param tp: trust point to verify with
1219  * @param rrset: DNSKEY rrset to verify.
1220  * @return false on failure, true if verification successful.
1221  */
1222 static int
1223 verify_dnskey(struct module_env* env, struct val_env* ve,
1224         struct trust_anchor* tp, struct ub_packed_rrset_key* rrset)
1225 {
1226         char* reason = NULL;
1227         uint8_t sigalg[ALGO_NEEDS_MAX+1];
1228         int downprot = 1;
1229         enum sec_status sec = val_verify_DNSKEY_with_TA(env, ve, rrset,
1230                 tp->ds_rrset, tp->dnskey_rrset, downprot?sigalg:NULL, &reason);
1231         /* sigalg is ignored, it returns algorithms signalled to exist, but
1232          * in 5011 there are no other rrsets to check.  if downprot is
1233          * enabled, then it checks that the DNSKEY is signed with all
1234          * algorithms available in the trust store. */
1235         verbose(VERB_ALGO, "autotrust: validate DNSKEY with anchor: %s",
1236                 sec_status_to_string(sec));
1237         return sec == sec_status_secure;
1238 }
1239
1240 static int32_t
1241 rrsig_get_expiry(uint8_t* d, size_t len)
1242 {
1243         /* rrsig: 2(rdlen), 2(type) 1(alg) 1(v) 4(origttl), then 4(expi), (4)incep) */
1244         if(len < 2+8+4)
1245                 return 0;
1246         return sldns_read_uint32(d+2+8);
1247 }
1248
1249 /** Find minimum expiration interval from signatures */
1250 static time_t
1251 min_expiry(struct module_env* env, struct packed_rrset_data* dd)
1252 {
1253         size_t i;
1254         int32_t t, r = 15 * 24 * 3600; /* 15 days max */
1255         for(i=dd->count; i<dd->count+dd->rrsig_count; i++) {
1256                 t = rrsig_get_expiry(dd->rr_data[i], dd->rr_len[i]);
1257                 if((int32_t)t - (int32_t)*env->now > 0) {
1258                         t -= (int32_t)*env->now;
1259                         if(t < r)
1260                                 r = t;
1261                 }
1262         }
1263         return (time_t)r;
1264 }
1265
1266 /** Is rr self-signed revoked key */
1267 static int
1268 rr_is_selfsigned_revoked(struct module_env* env, struct val_env* ve,
1269         struct ub_packed_rrset_key* dnskey_rrset, size_t i)
1270 {
1271         enum sec_status sec;
1272         char* reason = NULL;
1273         verbose(VERB_ALGO, "seen REVOKE flag, check self-signed, rr %d",
1274                 (int)i);
1275         /* no algorithm downgrade protection necessary, if it is selfsigned
1276          * revoked it can be removed. */
1277         sec = dnskey_verify_rrset(env, ve, dnskey_rrset, dnskey_rrset, i,
1278                 &reason);
1279         return (sec == sec_status_secure);
1280 }
1281
1282 /** Set fetched value */
1283 static void
1284 seen_trustanchor(struct autr_ta* ta, uint8_t seen)
1285 {
1286         ta->fetched = seen;
1287         if(ta->pending_count < 250) /* no numerical overflow, please */
1288                 ta->pending_count++;
1289 }
1290
1291 /** set revoked value */
1292 static void
1293 seen_revoked_trustanchor(struct autr_ta* ta, uint8_t revoked)
1294 {
1295         ta->revoked = revoked;
1296 }
1297
1298 /** revoke a trust anchor */
1299 static void
1300 revoke_dnskey(struct autr_ta* ta, int off)
1301 {
1302         uint16_t flags;
1303         uint8_t* data;
1304         if(sldns_wirerr_get_type(ta->rr, ta->rr_len, ta->dname_len) !=
1305                 LDNS_RR_TYPE_DNSKEY)
1306                 return;
1307         if(sldns_wirerr_get_rdatalen(ta->rr, ta->rr_len, ta->dname_len) < 2)
1308                 return;
1309         data = sldns_wirerr_get_rdata(ta->rr, ta->rr_len, ta->dname_len);
1310         flags = sldns_read_uint16(data);
1311         if (off && (flags&LDNS_KEY_REVOKE_KEY))
1312                 flags ^= LDNS_KEY_REVOKE_KEY; /* flip */
1313         else
1314                 flags |= LDNS_KEY_REVOKE_KEY;
1315         sldns_write_uint16(data, flags);
1316 }
1317
1318 /** Compare two RRs skipping the REVOKED bit. Pass rdata(no len) */
1319 static int
1320 dnskey_compare_skip_revbit(uint8_t* a, size_t a_len, uint8_t* b, size_t b_len)
1321 {
1322         size_t i;
1323         if(a_len != b_len)
1324                 return -1;
1325         /* compare RRs RDATA byte for byte. */
1326         for(i = 0; i < a_len; i++)
1327         {
1328                 uint8_t rdf1, rdf2;
1329                 rdf1 = a[i];
1330                 rdf2 = b[i];
1331                 if(i==1) {
1332                         /* this is the second part of the flags field */
1333                         rdf1 |= LDNS_KEY_REVOKE_KEY;
1334                         rdf2 |= LDNS_KEY_REVOKE_KEY;
1335                 }
1336                 if (rdf1 < rdf2)        return -1;
1337                 else if (rdf1 > rdf2)   return 1;
1338         }
1339         return 0;
1340 }
1341
1342
1343 /** compare trust anchor with rdata, 0 if equal. Pass rdata(no len) */
1344 static int
1345 ta_compare(struct autr_ta* a, uint16_t t, uint8_t* b, size_t b_len)
1346 {
1347         if(!a) return -1;
1348         else if(!b) return -1;
1349         else if(sldns_wirerr_get_type(a->rr, a->rr_len, a->dname_len) != t)
1350                 return (int)sldns_wirerr_get_type(a->rr, a->rr_len,
1351                         a->dname_len) - (int)t;
1352         else if(t == LDNS_RR_TYPE_DNSKEY) {
1353                 return dnskey_compare_skip_revbit(
1354                         sldns_wirerr_get_rdata(a->rr, a->rr_len, a->dname_len),
1355                         sldns_wirerr_get_rdatalen(a->rr, a->rr_len,
1356                         a->dname_len), b, b_len);
1357         }
1358         else if(t == LDNS_RR_TYPE_DS) {
1359                 if(sldns_wirerr_get_rdatalen(a->rr, a->rr_len, a->dname_len) !=
1360                         b_len)
1361                         return -1;
1362                 return memcmp(sldns_wirerr_get_rdata(a->rr,
1363                         a->rr_len, a->dname_len), b, b_len);
1364         }
1365         return -1;
1366 }
1367
1368 /**
1369  * Find key
1370  * @param tp: to search in
1371  * @param t: rr type of the rdata.
1372  * @param rdata: to look for  (no rdatalen in it)
1373  * @param rdata_len: length of rdata
1374  * @param result: returns NULL or the ta key looked for.
1375  * @return false on malloc failure during search. if true examine result.
1376  */
1377 static int
1378 find_key(struct trust_anchor* tp, uint16_t t, uint8_t* rdata, size_t rdata_len,
1379         struct autr_ta** result)
1380 {
1381         struct autr_ta* ta;
1382         if(!tp || !rdata) {
1383                 *result = NULL;
1384                 return 0;
1385         }
1386         for(ta=tp->autr->keys; ta; ta=ta->next) {
1387                 if(ta_compare(ta, t, rdata, rdata_len) == 0) {
1388                         *result = ta;
1389                         return 1;
1390                 }
1391         }
1392         *result = NULL;
1393         return 1;
1394 }
1395
1396 /** add key and clone RR and tp already locked. rdata without rdlen. */
1397 static struct autr_ta*
1398 add_key(struct trust_anchor* tp, uint32_t ttl, uint8_t* rdata, size_t rdata_len)
1399 {
1400         struct autr_ta* ta;
1401         uint8_t* rr;
1402         size_t rr_len, dname_len;
1403         uint16_t rrtype = htons(LDNS_RR_TYPE_DNSKEY);
1404         uint16_t rrclass = htons(LDNS_RR_CLASS_IN);
1405         uint16_t rdlen = htons(rdata_len);
1406         dname_len = tp->namelen;
1407         ttl = htonl(ttl);
1408         rr_len = dname_len + 10 /* type,class,ttl,rdatalen */ + rdata_len;
1409         rr = (uint8_t*)malloc(rr_len);
1410         if(!rr) return NULL;
1411         memmove(rr, tp->name, tp->namelen);
1412         memmove(rr+dname_len, &rrtype, 2);
1413         memmove(rr+dname_len+2, &rrclass, 2);
1414         memmove(rr+dname_len+4, &ttl, 4);
1415         memmove(rr+dname_len+8, &rdlen, 2);
1416         memmove(rr+dname_len+10, rdata, rdata_len);
1417         ta = autr_ta_create(rr, rr_len, dname_len);
1418         if(!ta) {
1419                 /* rr freed in autr_ta_create */
1420                 return NULL;
1421         }
1422         /* link in, tp already locked */
1423         ta->next = tp->autr->keys;
1424         tp->autr->keys = ta;
1425         return ta;
1426 }
1427
1428 /** get TTL from DNSKEY rrset */
1429 static time_t
1430 key_ttl(struct ub_packed_rrset_key* k)
1431 {
1432         struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
1433         return d->ttl;
1434 }
1435
1436 /** update the time values for the trustpoint */
1437 static void
1438 set_tp_times(struct trust_anchor* tp, time_t rrsig_exp_interval,
1439         time_t origttl, int* changed)
1440 {
1441         time_t x, qi = tp->autr->query_interval, rt = tp->autr->retry_time;
1442
1443         /* x = MIN(15days, ttl/2, expire/2) */
1444         x = 15 * 24 * 3600;
1445         if(origttl/2 < x)
1446                 x = origttl/2;
1447         if(rrsig_exp_interval/2 < x)
1448                 x = rrsig_exp_interval/2;
1449         /* MAX(1hr, x) */
1450         if(x < 3600)
1451                 tp->autr->query_interval = 3600;
1452         else    tp->autr->query_interval = x;
1453
1454         /* x= MIN(1day, ttl/10, expire/10) */
1455         x = 24 * 3600;
1456         if(origttl/10 < x)
1457                 x = origttl/10;
1458         if(rrsig_exp_interval/10 < x)
1459                 x = rrsig_exp_interval/10;
1460         /* MAX(1hr, x) */
1461         if(x < 3600)
1462                 tp->autr->retry_time = 3600;
1463         else    tp->autr->retry_time = x;
1464
1465         if(qi != tp->autr->query_interval || rt != tp->autr->retry_time) {
1466                 *changed = 1;
1467                 verbose(VERB_ALGO, "orig_ttl is %d", (int)origttl);
1468                 verbose(VERB_ALGO, "rrsig_exp_interval is %d",
1469                         (int)rrsig_exp_interval);
1470                 verbose(VERB_ALGO, "query_interval: %d, retry_time: %d",
1471                         (int)tp->autr->query_interval,
1472                         (int)tp->autr->retry_time);
1473         }
1474 }
1475
1476 /** init events to zero */
1477 static void
1478 init_events(struct trust_anchor* tp)
1479 {
1480         struct autr_ta* ta;
1481         for(ta=tp->autr->keys; ta; ta=ta->next) {
1482                 ta->fetched = 0;
1483         }
1484 }
1485
1486 /** check for revoked keys without trusting any other information */
1487 static void
1488 check_contains_revoked(struct module_env* env, struct val_env* ve,
1489         struct trust_anchor* tp, struct ub_packed_rrset_key* dnskey_rrset,
1490         int* changed)
1491 {
1492         struct packed_rrset_data* dd = (struct packed_rrset_data*)
1493                 dnskey_rrset->entry.data;
1494         size_t i;
1495         log_assert(ntohs(dnskey_rrset->rk.type) == LDNS_RR_TYPE_DNSKEY);
1496         for(i=0; i<dd->count; i++) {
1497                 struct autr_ta* ta = NULL;
1498                 if(!rr_is_dnskey_sep(ntohs(dnskey_rrset->rk.type),
1499                         dd->rr_data[i]+2, dd->rr_len[i]-2) ||
1500                         !rr_is_dnskey_revoked(ntohs(dnskey_rrset->rk.type),
1501                         dd->rr_data[i]+2, dd->rr_len[i]-2))
1502                         continue; /* not a revoked KSK */
1503                 if(!find_key(tp, ntohs(dnskey_rrset->rk.type),
1504                         dd->rr_data[i]+2, dd->rr_len[i]-2, &ta)) {
1505                         log_err("malloc failure");
1506                         continue; /* malloc fail in compare*/
1507                 }
1508                 if(!ta)
1509                         continue; /* key not found */
1510                 if(rr_is_selfsigned_revoked(env, ve, dnskey_rrset, i)) {
1511                         /* checked if there is an rrsig signed by this key. */
1512                         /* same keytag, but stored can be revoked already, so
1513                          * compare keytags, with +0 or +128(REVOKE flag) */
1514                         log_assert(dnskey_calc_keytag(dnskey_rrset, i)-128 ==
1515                                 sldns_calc_keytag_raw(sldns_wirerr_get_rdata(
1516                                 ta->rr, ta->rr_len, ta->dname_len),
1517                                 sldns_wirerr_get_rdatalen(ta->rr, ta->rr_len,
1518                                 ta->dname_len)) ||
1519                                 dnskey_calc_keytag(dnskey_rrset, i) ==
1520                                 sldns_calc_keytag_raw(sldns_wirerr_get_rdata(
1521                                 ta->rr, ta->rr_len, ta->dname_len),
1522                                 sldns_wirerr_get_rdatalen(ta->rr, ta->rr_len,
1523                                 ta->dname_len))); /* checks conversion*/
1524                         verbose_key(ta, VERB_ALGO, "is self-signed revoked");
1525                         if(!ta->revoked)
1526                                 *changed = 1;
1527                         seen_revoked_trustanchor(ta, 1);
1528                         do_revoked(env, ta, changed);
1529                 }
1530         }
1531 }
1532
1533 /** See if a DNSKEY is verified by one of the DSes */
1534 static int
1535 key_matches_a_ds(struct module_env* env, struct val_env* ve,
1536         struct ub_packed_rrset_key* dnskey_rrset, size_t key_idx,
1537         struct ub_packed_rrset_key* ds_rrset)
1538 {
1539         struct packed_rrset_data* dd = (struct packed_rrset_data*)
1540                         ds_rrset->entry.data;
1541         size_t ds_idx, num = dd->count;
1542         int d = val_favorite_ds_algo(ds_rrset);
1543         char* reason = "";
1544         for(ds_idx=0; ds_idx<num; ds_idx++) {
1545                 if(!ds_digest_algo_is_supported(ds_rrset, ds_idx) ||
1546                         !ds_key_algo_is_supported(ds_rrset, ds_idx) ||
1547                         ds_get_digest_algo(ds_rrset, ds_idx) != d)
1548                         continue;
1549                 if(ds_get_key_algo(ds_rrset, ds_idx)
1550                    != dnskey_get_algo(dnskey_rrset, key_idx)
1551                    || dnskey_calc_keytag(dnskey_rrset, key_idx)
1552                    != ds_get_keytag(ds_rrset, ds_idx)) {
1553                         continue;
1554                 }
1555                 if(!ds_digest_match_dnskey(env, dnskey_rrset, key_idx,
1556                         ds_rrset, ds_idx)) {
1557                         verbose(VERB_ALGO, "DS match attempt failed");
1558                         continue;
1559                 }
1560                 if(dnskey_verify_rrset(env, ve, dnskey_rrset,
1561                         dnskey_rrset, key_idx, &reason) == sec_status_secure) {
1562                         return 1;
1563                 } else {
1564                         verbose(VERB_ALGO, "DS match failed because the key "
1565                                 "does not verify the keyset: %s", reason);
1566                 }
1567         }
1568         return 0;
1569 }
1570
1571 /** Set update events */
1572 static int
1573 update_events(struct module_env* env, struct val_env* ve,
1574         struct trust_anchor* tp, struct ub_packed_rrset_key* dnskey_rrset,
1575         int* changed)
1576 {
1577         struct packed_rrset_data* dd = (struct packed_rrset_data*)
1578                 dnskey_rrset->entry.data;
1579         size_t i;
1580         log_assert(ntohs(dnskey_rrset->rk.type) == LDNS_RR_TYPE_DNSKEY);
1581         init_events(tp);
1582         for(i=0; i<dd->count; i++) {
1583                 struct autr_ta* ta = NULL;
1584                 if(!rr_is_dnskey_sep(ntohs(dnskey_rrset->rk.type),
1585                         dd->rr_data[i]+2, dd->rr_len[i]-2))
1586                         continue;
1587                 if(rr_is_dnskey_revoked(ntohs(dnskey_rrset->rk.type),
1588                         dd->rr_data[i]+2, dd->rr_len[i]-2)) {
1589                         /* self-signed revoked keys already detected before,
1590                          * other revoked keys are not 'added' again */
1591                         continue;
1592                 }
1593                 /* is a key of this type supported?. Note rr_list and
1594                  * packed_rrset are in the same order. */
1595                 if(!dnskey_algo_is_supported(dnskey_rrset, i)) {
1596                         /* skip unknown algorithm key, it is useless to us */
1597                         log_nametypeclass(VERB_DETAIL, "trust point has "
1598                                 "unsupported algorithm at",
1599                                 tp->name, LDNS_RR_TYPE_DNSKEY, tp->dclass);
1600                         continue;
1601                 }
1602
1603                 /* is it new? if revocation bit set, find the unrevoked key */
1604                 if(!find_key(tp, ntohs(dnskey_rrset->rk.type),
1605                         dd->rr_data[i]+2, dd->rr_len[i]-2, &ta)) {
1606                         return 0;
1607                 }
1608                 if(!ta) {
1609                         ta = add_key(tp, (uint32_t)dd->rr_ttl[i],
1610                                 dd->rr_data[i]+2, dd->rr_len[i]-2);
1611                         *changed = 1;
1612                         /* first time seen, do we have DSes? if match: VALID */
1613                         if(ta && tp->ds_rrset && key_matches_a_ds(env, ve,
1614                                 dnskey_rrset, i, tp->ds_rrset)) {
1615                                 verbose_key(ta, VERB_ALGO, "verified by DS");
1616                                 ta->s = AUTR_STATE_VALID;
1617                         }
1618                 }
1619                 if(!ta) {
1620                         return 0;
1621                 }
1622                 seen_trustanchor(ta, 1);
1623                 verbose_key(ta, VERB_ALGO, "in DNS response");
1624         }
1625         set_tp_times(tp, min_expiry(env, dd), key_ttl(dnskey_rrset), changed);
1626         return 1;
1627 }
1628
1629 /**
1630  * Check if the holddown time has already exceeded
1631  * setting: add-holddown: add holddown timer
1632  * setting: del-holddown: del holddown timer
1633  * @param env: environment with current time
1634  * @param ta: trust anchor to check for.
1635  * @param holddown: the timer value
1636  * @return number of seconds the holddown has passed.
1637  */
1638 static time_t
1639 check_holddown(struct module_env* env, struct autr_ta* ta,
1640         unsigned int holddown)
1641 {
1642         time_t elapsed;
1643         if(*env->now < ta->last_change) {
1644                 log_warn("time goes backwards. delaying key holddown");
1645                 return 0;
1646         }
1647         elapsed = *env->now - ta->last_change;
1648         if (elapsed > (time_t)holddown) {
1649                 return elapsed-(time_t)holddown;
1650         }
1651         verbose_key(ta, VERB_ALGO, "holddown time " ARG_LL "d seconds to go",
1652                 (long long) ((time_t)holddown-elapsed));
1653         return 0;
1654 }
1655
1656
1657 /** Set last_change to now */
1658 static void
1659 reset_holddown(struct module_env* env, struct autr_ta* ta, int* changed)
1660 {
1661         ta->last_change = *env->now;
1662         *changed = 1;
1663 }
1664
1665 /** Set the state for this trust anchor */
1666 static void
1667 set_trustanchor_state(struct module_env* env, struct autr_ta* ta, int* changed,
1668         autr_state_t s)
1669 {
1670         verbose_key(ta, VERB_ALGO, "update: %s to %s",
1671                 trustanchor_state2str(ta->s), trustanchor_state2str(s));
1672         ta->s = s;
1673         reset_holddown(env, ta, changed);
1674 }
1675
1676
1677 /** Event: NewKey */
1678 static void
1679 do_newkey(struct module_env* env, struct autr_ta* anchor, int* c)
1680 {
1681         if (anchor->s == AUTR_STATE_START)
1682                 set_trustanchor_state(env, anchor, c, AUTR_STATE_ADDPEND);
1683 }
1684
1685 /** Event: AddTime */
1686 static void
1687 do_addtime(struct module_env* env, struct autr_ta* anchor, int* c)
1688 {
1689         /* This not according to RFC, this is 30 days, but the RFC demands
1690          * MAX(30days, TTL expire time of first DNSKEY set with this key),
1691          * The value may be too small if a very large TTL was used. */
1692         time_t exceeded = check_holddown(env, anchor, env->cfg->add_holddown);
1693         if (exceeded && anchor->s == AUTR_STATE_ADDPEND) {
1694                 verbose_key(anchor, VERB_ALGO, "add-holddown time exceeded "
1695                         ARG_LL "d seconds ago, and pending-count %d",
1696                         (long long)exceeded, anchor->pending_count);
1697                 if(anchor->pending_count >= MIN_PENDINGCOUNT) {
1698                         set_trustanchor_state(env, anchor, c, AUTR_STATE_VALID);
1699                         anchor->pending_count = 0;
1700                         return;
1701                 }
1702                 verbose_key(anchor, VERB_ALGO, "add-holddown time sanity check "
1703                         "failed (pending count: %d)", anchor->pending_count);
1704         }
1705 }
1706
1707 /** Event: RemTime */
1708 static void
1709 do_remtime(struct module_env* env, struct autr_ta* anchor, int* c)
1710 {
1711         time_t exceeded = check_holddown(env, anchor, env->cfg->del_holddown);
1712         if(exceeded && anchor->s == AUTR_STATE_REVOKED) {
1713                 verbose_key(anchor, VERB_ALGO, "del-holddown time exceeded "
1714                         ARG_LL "d seconds ago", (long long)exceeded);
1715                 set_trustanchor_state(env, anchor, c, AUTR_STATE_REMOVED);
1716         }
1717 }
1718
1719 /** Event: KeyRem */
1720 static void
1721 do_keyrem(struct module_env* env, struct autr_ta* anchor, int* c)
1722 {
1723         if(anchor->s == AUTR_STATE_ADDPEND) {
1724                 set_trustanchor_state(env, anchor, c, AUTR_STATE_START);
1725                 anchor->pending_count = 0;
1726         } else if(anchor->s == AUTR_STATE_VALID)
1727                 set_trustanchor_state(env, anchor, c, AUTR_STATE_MISSING);
1728 }
1729
1730 /** Event: KeyPres */
1731 static void
1732 do_keypres(struct module_env* env, struct autr_ta* anchor, int* c)
1733 {
1734         if(anchor->s == AUTR_STATE_MISSING)
1735                 set_trustanchor_state(env, anchor, c, AUTR_STATE_VALID);
1736 }
1737
1738 /* Event: Revoked */
1739 static void
1740 do_revoked(struct module_env* env, struct autr_ta* anchor, int* c)
1741 {
1742         if(anchor->s == AUTR_STATE_VALID || anchor->s == AUTR_STATE_MISSING) {
1743                 set_trustanchor_state(env, anchor, c, AUTR_STATE_REVOKED);
1744                 verbose_key(anchor, VERB_ALGO, "old id, prior to revocation");
1745                 revoke_dnskey(anchor, 0);
1746                 verbose_key(anchor, VERB_ALGO, "new id, after revocation");
1747         }
1748 }
1749
1750 /** Do statestable transition matrix for anchor */
1751 static void
1752 anchor_state_update(struct module_env* env, struct autr_ta* anchor, int* c)
1753 {
1754         log_assert(anchor);
1755         switch(anchor->s) {
1756         /* START */
1757         case AUTR_STATE_START:
1758                 /* NewKey: ADDPEND */
1759                 if (anchor->fetched)
1760                         do_newkey(env, anchor, c);
1761                 break;
1762         /* ADDPEND */
1763         case AUTR_STATE_ADDPEND:
1764                 /* KeyRem: START */
1765                 if (!anchor->fetched)
1766                         do_keyrem(env, anchor, c);
1767                 /* AddTime: VALID */
1768                 else    do_addtime(env, anchor, c);
1769                 break;
1770         /* VALID */
1771         case AUTR_STATE_VALID:
1772                 /* RevBit: REVOKED */
1773                 if (anchor->revoked)
1774                         do_revoked(env, anchor, c);
1775                 /* KeyRem: MISSING */
1776                 else if (!anchor->fetched)
1777                         do_keyrem(env, anchor, c);
1778                 else if(!anchor->last_change) {
1779                         verbose_key(anchor, VERB_ALGO, "first seen");
1780                         reset_holddown(env, anchor, c);
1781                 }
1782                 break;
1783         /* MISSING */
1784         case AUTR_STATE_MISSING:
1785                 /* RevBit: REVOKED */
1786                 if (anchor->revoked)
1787                         do_revoked(env, anchor, c);
1788                 /* KeyPres */
1789                 else if (anchor->fetched)
1790                         do_keypres(env, anchor, c);
1791                 break;
1792         /* REVOKED */
1793         case AUTR_STATE_REVOKED:
1794                 if (anchor->fetched)
1795                         reset_holddown(env, anchor, c);
1796                 /* RemTime: REMOVED */
1797                 else    do_remtime(env, anchor, c);
1798                 break;
1799         /* REMOVED */
1800         case AUTR_STATE_REMOVED:
1801         default:
1802                 break;
1803         }
1804 }
1805
1806 /** if ZSK init then trust KSKs */
1807 static int
1808 init_zsk_to_ksk(struct module_env* env, struct trust_anchor* tp, int* changed)
1809 {
1810         /* search for VALID ZSKs */
1811         struct autr_ta* anchor;
1812         int validzsk = 0;
1813         int validksk = 0;
1814         for(anchor = tp->autr->keys; anchor; anchor = anchor->next) {
1815                 /* last_change test makes sure it was manually configured */
1816                 if(sldns_wirerr_get_type(anchor->rr, anchor->rr_len,
1817                         anchor->dname_len) == LDNS_RR_TYPE_DNSKEY &&
1818                         anchor->last_change == 0 &&
1819                         !ta_is_dnskey_sep(anchor) &&
1820                         anchor->s == AUTR_STATE_VALID)
1821                         validzsk++;
1822         }
1823         if(validzsk == 0)
1824                 return 0;
1825         for(anchor = tp->autr->keys; anchor; anchor = anchor->next) {
1826                 if (ta_is_dnskey_sep(anchor) &&
1827                         anchor->s == AUTR_STATE_ADDPEND) {
1828                         verbose_key(anchor, VERB_ALGO, "trust KSK from "
1829                                 "ZSK(config)");
1830                         set_trustanchor_state(env, anchor, changed,
1831                                 AUTR_STATE_VALID);
1832                         validksk++;
1833                 }
1834         }
1835         return validksk;
1836 }
1837
1838 /** Remove missing trustanchors so the list does not grow forever */
1839 static void
1840 remove_missing_trustanchors(struct module_env* env, struct trust_anchor* tp,
1841         int* changed)
1842 {
1843         struct autr_ta* anchor;
1844         time_t exceeded;
1845         int valid = 0;
1846         /* see if we have anchors that are valid */
1847         for(anchor = tp->autr->keys; anchor; anchor = anchor->next) {
1848                 /* Only do KSKs */
1849                 if (!ta_is_dnskey_sep(anchor))
1850                         continue;
1851                 if (anchor->s == AUTR_STATE_VALID)
1852                         valid++;
1853         }
1854         /* if there are no SEP Valid anchors, see if we started out with
1855          * a ZSK (last-change=0) anchor, which is VALID and there are KSKs
1856          * now that can be made valid.  Do this immediately because there
1857          * is no guarantee that the ZSKs get announced long enough.  Usually
1858          * this is immediately after init with a ZSK trusted, unless the domain
1859          * was not advertising any KSKs at all.  In which case we perfectly
1860          * track the zero number of KSKs. */
1861         if(valid == 0) {
1862                 valid = init_zsk_to_ksk(env, tp, changed);
1863                 if(valid == 0)
1864                         return;
1865         }
1866
1867         for(anchor = tp->autr->keys; anchor; anchor = anchor->next) {
1868                 /* ignore ZSKs if newly added */
1869                 if(anchor->s == AUTR_STATE_START)
1870                         continue;
1871                 /* remove ZSKs if a KSK is present */
1872                 if (!ta_is_dnskey_sep(anchor)) {
1873                         if(valid > 0) {
1874                                 verbose_key(anchor, VERB_ALGO, "remove ZSK "
1875                                         "[%d key(s) VALID]", valid);
1876                                 set_trustanchor_state(env, anchor, changed,
1877                                         AUTR_STATE_REMOVED);
1878                         }
1879                         continue;
1880                 }
1881                 /* Only do MISSING keys */
1882                 if (anchor->s != AUTR_STATE_MISSING)
1883                         continue;
1884                 if(env->cfg->keep_missing == 0)
1885                         continue; /* keep forever */
1886
1887                 exceeded = check_holddown(env, anchor, env->cfg->keep_missing);
1888                 /* If keep_missing has exceeded and we still have more than
1889                  * one valid KSK: remove missing trust anchor */
1890                 if (exceeded && valid > 0) {
1891                         verbose_key(anchor, VERB_ALGO, "keep-missing time "
1892                                 "exceeded " ARG_LL "d seconds ago, [%d key(s) VALID]",
1893                                 (long long)exceeded, valid);
1894                         set_trustanchor_state(env, anchor, changed,
1895                                 AUTR_STATE_REMOVED);
1896                 }
1897         }
1898 }
1899
1900 /** Do the statetable from RFC5011 transition matrix */
1901 static int
1902 do_statetable(struct module_env* env, struct trust_anchor* tp, int* changed)
1903 {
1904         struct autr_ta* anchor;
1905         for(anchor = tp->autr->keys; anchor; anchor = anchor->next) {
1906                 /* Only do KSKs */
1907                 if(!ta_is_dnskey_sep(anchor))
1908                         continue;
1909                 anchor_state_update(env, anchor, changed);
1910         }
1911         remove_missing_trustanchors(env, tp, changed);
1912         return 1;
1913 }
1914
1915 /** See if time alone makes ADDPEND to VALID transition */
1916 static void
1917 autr_holddown_exceed(struct module_env* env, struct trust_anchor* tp, int* c)
1918 {
1919         struct autr_ta* anchor;
1920         for(anchor = tp->autr->keys; anchor; anchor = anchor->next) {
1921                 if(ta_is_dnskey_sep(anchor) &&
1922                         anchor->s == AUTR_STATE_ADDPEND)
1923                         do_addtime(env, anchor, c);
1924         }
1925 }
1926
1927 /** cleanup key list */
1928 static void
1929 autr_cleanup_keys(struct trust_anchor* tp)
1930 {
1931         struct autr_ta* p, **prevp;
1932         prevp = &tp->autr->keys;
1933         p = tp->autr->keys;
1934         while(p) {
1935                 /* do we want to remove this key? */
1936                 if(p->s == AUTR_STATE_START || p->s == AUTR_STATE_REMOVED ||
1937                         sldns_wirerr_get_type(p->rr, p->rr_len, p->dname_len)
1938                         != LDNS_RR_TYPE_DNSKEY) {
1939                         struct autr_ta* np = p->next;
1940                         /* remove */
1941                         free(p->rr);
1942                         free(p);
1943                         /* snip and go to next item */
1944                         *prevp = np;
1945                         p = np;
1946                         continue;
1947                 }
1948                 /* remove pending counts if no longer pending */
1949                 if(p->s != AUTR_STATE_ADDPEND)
1950                         p->pending_count = 0;
1951                 prevp = &p->next;
1952                 p = p->next;
1953         }
1954 }
1955
1956 /** calculate next probe time */
1957 static time_t
1958 calc_next_probe(struct module_env* env, time_t wait)
1959 {
1960         /* make it random, 90-100% */
1961         time_t rnd, rest;
1962         if(wait < 3600)
1963                 wait = 3600;
1964         rnd = wait/10;
1965         rest = wait-rnd;
1966         rnd = (time_t)ub_random_max(env->rnd, (long int)rnd);
1967         return (time_t)(*env->now + rest + rnd);
1968 }
1969
1970 /** what is first probe time (anchors must be locked) */
1971 static time_t
1972 wait_probe_time(struct val_anchors* anchors)
1973 {
1974         rbnode_t* t = rbtree_first(&anchors->autr->probe);
1975         if(t != RBTREE_NULL)
1976                 return ((struct trust_anchor*)t->key)->autr->next_probe_time;
1977         return 0;
1978 }
1979
1980 /** reset worker timer */
1981 static void
1982 reset_worker_timer(struct module_env* env)
1983 {
1984         struct timeval tv;
1985 #ifndef S_SPLINT_S
1986         time_t next = (time_t)wait_probe_time(env->anchors);
1987         /* in case this is libunbound, no timer */
1988         if(!env->probe_timer)
1989                 return;
1990         if(next > *env->now)
1991                 tv.tv_sec = (time_t)(next - *env->now);
1992         else    tv.tv_sec = 0;
1993 #endif
1994         tv.tv_usec = 0;
1995         comm_timer_set(env->probe_timer, &tv);
1996         verbose(VERB_ALGO, "scheduled next probe in " ARG_LL "d sec", (long long)tv.tv_sec);
1997 }
1998
1999 /** set next probe for trust anchor */
2000 static int
2001 set_next_probe(struct module_env* env, struct trust_anchor* tp,
2002         struct ub_packed_rrset_key* dnskey_rrset)
2003 {
2004         struct trust_anchor key, *tp2;
2005         time_t mold, mnew;
2006         /* use memory allocated in rrset for temporary name storage */
2007         key.node.key = &key;
2008         key.name = dnskey_rrset->rk.dname;
2009         key.namelen = dnskey_rrset->rk.dname_len;
2010         key.namelabs = dname_count_labels(key.name);
2011         key.dclass = tp->dclass;
2012         lock_basic_unlock(&tp->lock);
2013
2014         /* fetch tp again and lock anchors, so that we can modify the trees */
2015         lock_basic_lock(&env->anchors->lock);
2016         tp2 = (struct trust_anchor*)rbtree_search(env->anchors->tree, &key);
2017         if(!tp2) {
2018                 verbose(VERB_ALGO, "trustpoint was deleted in set_next_probe");
2019                 lock_basic_unlock(&env->anchors->lock);
2020                 return 0;
2021         }
2022         log_assert(tp == tp2);
2023         lock_basic_lock(&tp->lock);
2024
2025         /* schedule */
2026         mold = wait_probe_time(env->anchors);
2027         (void)rbtree_delete(&env->anchors->autr->probe, tp);
2028         tp->autr->next_probe_time = calc_next_probe(env,
2029                 tp->autr->query_interval);
2030         (void)rbtree_insert(&env->anchors->autr->probe, &tp->autr->pnode);
2031         mnew = wait_probe_time(env->anchors);
2032
2033         lock_basic_unlock(&env->anchors->lock);
2034         verbose(VERB_ALGO, "next probe set in %d seconds",
2035                 (int)tp->autr->next_probe_time - (int)*env->now);
2036         if(mold != mnew) {
2037                 reset_worker_timer(env);
2038         }
2039         return 1;
2040 }
2041
2042 /** Revoke and Delete a trust point */
2043 static void
2044 autr_tp_remove(struct module_env* env, struct trust_anchor* tp,
2045         struct ub_packed_rrset_key* dnskey_rrset)
2046 {
2047         struct trust_anchor* del_tp;
2048         struct trust_anchor key;
2049         struct autr_point_data pd;
2050         time_t mold, mnew;
2051
2052         log_nametypeclass(VERB_OPS, "trust point was revoked",
2053                 tp->name, LDNS_RR_TYPE_DNSKEY, tp->dclass);
2054         tp->autr->revoked = 1;
2055
2056         /* use space allocated for dnskey_rrset to save name of anchor */
2057         memset(&key, 0, sizeof(key));
2058         memset(&pd, 0, sizeof(pd));
2059         key.autr = &pd;
2060         key.node.key = &key;
2061         pd.pnode.key = &key;
2062         pd.next_probe_time = tp->autr->next_probe_time;
2063         key.name = dnskey_rrset->rk.dname;
2064         key.namelen = tp->namelen;
2065         key.namelabs = tp->namelabs;
2066         key.dclass = tp->dclass;
2067
2068         /* unlock */
2069         lock_basic_unlock(&tp->lock);
2070
2071         /* take from tree. It could be deleted by someone else,hence (void). */
2072         lock_basic_lock(&env->anchors->lock);
2073         del_tp = (struct trust_anchor*)rbtree_delete(env->anchors->tree, &key);
2074         mold = wait_probe_time(env->anchors);
2075         (void)rbtree_delete(&env->anchors->autr->probe, &key);
2076         mnew = wait_probe_time(env->anchors);
2077         anchors_init_parents_locked(env->anchors);
2078         lock_basic_unlock(&env->anchors->lock);
2079
2080         /* if !del_tp then the trust point is no longer present in the tree,
2081          * it was deleted by someone else, who will write the zonefile and
2082          * clean up the structure */
2083         if(del_tp) {
2084                 /* save on disk */
2085                 del_tp->autr->next_probe_time = 0; /* no more probing for it */
2086                 autr_write_file(env, del_tp);
2087
2088                 /* delete */
2089                 autr_point_delete(del_tp);
2090         }
2091         if(mold != mnew) {
2092                 reset_worker_timer(env);
2093         }
2094 }
2095
2096 int autr_process_prime(struct module_env* env, struct val_env* ve,
2097         struct trust_anchor* tp, struct ub_packed_rrset_key* dnskey_rrset)
2098 {
2099         int changed = 0;
2100         log_assert(tp && tp->autr);
2101         /* autotrust update trust anchors */
2102         /* the tp is locked, and stays locked unless it is deleted */
2103
2104         /* we could just catch the anchor here while another thread
2105          * is busy deleting it. Just unlock and let the other do its job */
2106         if(tp->autr->revoked) {
2107                 log_nametypeclass(VERB_ALGO, "autotrust not processed, "
2108                         "trust point revoked", tp->name,
2109                         LDNS_RR_TYPE_DNSKEY, tp->dclass);
2110                 lock_basic_unlock(&tp->lock);
2111                 return 0; /* it is revoked */
2112         }
2113
2114         /* query_dnskeys(): */
2115         tp->autr->last_queried = *env->now;
2116
2117         log_nametypeclass(VERB_ALGO, "autotrust process for",
2118                 tp->name, LDNS_RR_TYPE_DNSKEY, tp->dclass);
2119         /* see if time alone makes some keys valid */
2120         autr_holddown_exceed(env, tp, &changed);
2121         if(changed) {
2122                 verbose(VERB_ALGO, "autotrust: morekeys, reassemble");
2123                 if(!autr_assemble(tp)) {
2124                         log_err("malloc failure assembling autotrust keys");
2125                         return 1; /* unchanged */
2126                 }
2127         }
2128         /* did we get any data? */
2129         if(!dnskey_rrset) {
2130                 verbose(VERB_ALGO, "autotrust: no dnskey rrset");
2131                 /* no update of query_failed, because then we would have
2132                  * to write to disk. But we cannot because we maybe are
2133                  * still 'initialising' with DS records, that we cannot write
2134                  * in the full format (which only contains KSKs). */
2135                 return 1; /* trust point exists */
2136         }
2137         /* check for revoked keys to remove immediately */
2138         check_contains_revoked(env, ve, tp, dnskey_rrset, &changed);
2139         if(changed) {
2140                 verbose(VERB_ALGO, "autotrust: revokedkeys, reassemble");
2141                 if(!autr_assemble(tp)) {
2142                         log_err("malloc failure assembling autotrust keys");
2143                         return 1; /* unchanged */
2144                 }
2145                 if(!tp->ds_rrset && !tp->dnskey_rrset) {
2146                         /* no more keys, all are revoked */
2147                         /* this is a success for this probe attempt */
2148                         tp->autr->last_success = *env->now;
2149                         autr_tp_remove(env, tp, dnskey_rrset);
2150                         return 0; /* trust point removed */
2151                 }
2152         }
2153         /* verify the dnskey rrset and see if it is valid. */
2154         if(!verify_dnskey(env, ve, tp, dnskey_rrset)) {
2155                 verbose(VERB_ALGO, "autotrust: dnskey did not verify.");
2156                 /* only increase failure count if this is not the first prime,
2157                  * this means there was a previous succesful probe */
2158                 if(tp->autr->last_success) {
2159                         tp->autr->query_failed += 1;
2160                         autr_write_file(env, tp);
2161                 }
2162                 return 1; /* trust point exists */
2163         }
2164
2165         tp->autr->last_success = *env->now;
2166         tp->autr->query_failed = 0;
2167
2168         /* Add new trust anchors to the data structure
2169          * - note which trust anchors are seen this probe.
2170          * Set trustpoint query_interval and retry_time.
2171          * - find minimum rrsig expiration interval
2172          */
2173         if(!update_events(env, ve, tp, dnskey_rrset, &changed)) {
2174                 log_err("malloc failure in autotrust update_events. "
2175                         "trust point unchanged.");
2176                 return 1; /* trust point unchanged, so exists */
2177         }
2178
2179         /* - for every SEP key do the 5011 statetable.
2180          * - remove missing trustanchors (if veryold and we have new anchors).
2181          */
2182         if(!do_statetable(env, tp, &changed)) {
2183                 log_err("malloc failure in autotrust do_statetable. "
2184                         "trust point unchanged.");
2185                 return 1; /* trust point unchanged, so exists */
2186         }
2187
2188         autr_cleanup_keys(tp);
2189         if(!set_next_probe(env, tp, dnskey_rrset))
2190                 return 0; /* trust point does not exist */
2191         autr_write_file(env, tp);
2192         if(changed) {
2193                 verbose(VERB_ALGO, "autotrust: changed, reassemble");
2194                 if(!autr_assemble(tp)) {
2195                         log_err("malloc failure assembling autotrust keys");
2196                         return 1; /* unchanged */
2197                 }
2198                 if(!tp->ds_rrset && !tp->dnskey_rrset) {
2199                         /* no more keys, all are revoked */
2200                         autr_tp_remove(env, tp, dnskey_rrset);
2201                         return 0; /* trust point removed */
2202                 }
2203         } else verbose(VERB_ALGO, "autotrust: no changes");
2204
2205         return 1; /* trust point exists */
2206 }
2207
2208 /** debug print a trust anchor key */
2209 static void
2210 autr_debug_print_ta(struct autr_ta* ta)
2211 {
2212         char buf[32];
2213         char* str = sldns_wire2str_rr(ta->rr, ta->rr_len);
2214         if(!str) {
2215                 log_info("out of memory in debug_print_ta");
2216                 return;
2217         }
2218         if(str && str[0]) str[strlen(str)-1]=0; /* remove newline */
2219         ctime_r(&ta->last_change, buf);
2220         if(buf[0]) buf[strlen(buf)-1]=0; /* remove newline */
2221         log_info("[%s] %s ;;state:%d ;;pending_count:%d%s%s last:%s",
2222                 trustanchor_state2str(ta->s), str, ta->s, ta->pending_count,
2223                 ta->fetched?" fetched":"", ta->revoked?" revoked":"", buf);
2224         free(str);
2225 }
2226
2227 /** debug print a trust point */
2228 static void
2229 autr_debug_print_tp(struct trust_anchor* tp)
2230 {
2231         struct autr_ta* ta;
2232         char buf[257];
2233         if(!tp->autr)
2234                 return;
2235         dname_str(tp->name, buf);
2236         log_info("trust point %s : %d", buf, (int)tp->dclass);
2237         log_info("assembled %d DS and %d DNSKEYs",
2238                 (int)tp->numDS, (int)tp->numDNSKEY);
2239         if(tp->ds_rrset) {
2240                 log_packed_rrset(0, "DS:", tp->ds_rrset);
2241         }
2242         if(tp->dnskey_rrset) {
2243                 log_packed_rrset(0, "DNSKEY:", tp->dnskey_rrset);
2244         }
2245         log_info("file %s", tp->autr->file);
2246         ctime_r(&tp->autr->last_queried, buf);
2247         if(buf[0]) buf[strlen(buf)-1]=0; /* remove newline */
2248         log_info("last_queried: %u %s", (unsigned)tp->autr->last_queried, buf);
2249         ctime_r(&tp->autr->last_success, buf);
2250         if(buf[0]) buf[strlen(buf)-1]=0; /* remove newline */
2251         log_info("last_success: %u %s", (unsigned)tp->autr->last_success, buf);
2252         ctime_r(&tp->autr->next_probe_time, buf);
2253         if(buf[0]) buf[strlen(buf)-1]=0; /* remove newline */
2254         log_info("next_probe_time: %u %s", (unsigned)tp->autr->next_probe_time,
2255                 buf);
2256         log_info("query_interval: %u", (unsigned)tp->autr->query_interval);
2257         log_info("retry_time: %u", (unsigned)tp->autr->retry_time);
2258         log_info("query_failed: %u", (unsigned)tp->autr->query_failed);
2259
2260         for(ta=tp->autr->keys; ta; ta=ta->next) {
2261                 autr_debug_print_ta(ta);
2262         }
2263 }
2264
2265 void
2266 autr_debug_print(struct val_anchors* anchors)
2267 {
2268         struct trust_anchor* tp;
2269         lock_basic_lock(&anchors->lock);
2270         RBTREE_FOR(tp, struct trust_anchor*, anchors->tree) {
2271                 lock_basic_lock(&tp->lock);
2272                 autr_debug_print_tp(tp);
2273                 lock_basic_unlock(&tp->lock);
2274         }
2275         lock_basic_unlock(&anchors->lock);
2276 }
2277
2278 void probe_answer_cb(void* arg, int ATTR_UNUSED(rcode),
2279         sldns_buffer* ATTR_UNUSED(buf), enum sec_status ATTR_UNUSED(sec),
2280         char* ATTR_UNUSED(why_bogus))
2281 {
2282         /* retry was set before the query was done,
2283          * re-querytime is set when query succeeded, but that may not
2284          * have reset this timer because the query could have been
2285          * handled by another thread. In that case, this callback would
2286          * get called after the original timeout is done.
2287          * By not resetting the timer, it may probe more often, but not
2288          * less often.
2289          * Unless the new lookup resulted in smaller TTLs and thus smaller
2290          * timeout values. In that case one old TTL could be mistakenly done.
2291          */
2292         struct module_env* env = (struct module_env*)arg;
2293         verbose(VERB_ALGO, "autotrust probe answer cb");
2294         reset_worker_timer(env);
2295 }
2296
2297 /** probe a trust anchor DNSKEY and unlocks tp */
2298 static void
2299 probe_anchor(struct module_env* env, struct trust_anchor* tp)
2300 {
2301         struct query_info qinfo;
2302         uint16_t qflags = BIT_RD;
2303         struct edns_data edns;
2304         sldns_buffer* buf = env->scratch_buffer;
2305         qinfo.qname = regional_alloc_init(env->scratch, tp->name, tp->namelen);
2306         if(!qinfo.qname) {
2307                 log_err("out of memory making 5011 probe");
2308                 return;
2309         }
2310         qinfo.qname_len = tp->namelen;
2311         qinfo.qtype = LDNS_RR_TYPE_DNSKEY;
2312         qinfo.qclass = tp->dclass;
2313         log_query_info(VERB_ALGO, "autotrust probe", &qinfo);
2314         verbose(VERB_ALGO, "retry probe set in %d seconds",
2315                 (int)tp->autr->next_probe_time - (int)*env->now);
2316         edns.edns_present = 1;
2317         edns.ext_rcode = 0;
2318         edns.edns_version = 0;
2319         edns.bits = EDNS_DO;
2320         if(sldns_buffer_capacity(buf) < 65535)
2321                 edns.udp_size = (uint16_t)sldns_buffer_capacity(buf);
2322         else    edns.udp_size = 65535;
2323
2324         /* can't hold the lock while mesh_run is processing */
2325         lock_basic_unlock(&tp->lock);
2326
2327         /* delete the DNSKEY from rrset and key cache so an active probe
2328          * is done. First the rrset so another thread does not use it
2329          * to recreate the key entry in a race condition. */
2330         rrset_cache_remove(env->rrset_cache, qinfo.qname, qinfo.qname_len,
2331                 qinfo.qtype, qinfo.qclass, 0);
2332         key_cache_remove(env->key_cache, qinfo.qname, qinfo.qname_len,
2333                 qinfo.qclass);
2334
2335         if(!mesh_new_callback(env->mesh, &qinfo, qflags, &edns, buf, 0,
2336                 &probe_answer_cb, env)) {
2337                 log_err("out of memory making 5011 probe");
2338         }
2339 }
2340
2341 /** fetch first to-probe trust-anchor and lock it and set retrytime */
2342 static struct trust_anchor*
2343 todo_probe(struct module_env* env, time_t* next)
2344 {
2345         struct trust_anchor* tp;
2346         rbnode_t* el;
2347         /* get first one */
2348         lock_basic_lock(&env->anchors->lock);
2349         if( (el=rbtree_first(&env->anchors->autr->probe)) == RBTREE_NULL) {
2350                 /* in case of revoked anchors */
2351                 lock_basic_unlock(&env->anchors->lock);
2352                 return NULL;
2353         }
2354         tp = (struct trust_anchor*)el->key;
2355         lock_basic_lock(&tp->lock);
2356
2357         /* is it eligible? */
2358         if((time_t)tp->autr->next_probe_time > *env->now) {
2359                 /* no more to probe */
2360                 *next = (time_t)tp->autr->next_probe_time - *env->now;
2361                 lock_basic_unlock(&tp->lock);
2362                 lock_basic_unlock(&env->anchors->lock);
2363                 return NULL;
2364         }
2365
2366         /* reset its next probe time */
2367         (void)rbtree_delete(&env->anchors->autr->probe, tp);
2368         tp->autr->next_probe_time = calc_next_probe(env, tp->autr->retry_time);
2369         (void)rbtree_insert(&env->anchors->autr->probe, &tp->autr->pnode);
2370         lock_basic_unlock(&env->anchors->lock);
2371
2372         return tp;
2373 }
2374
2375 time_t
2376 autr_probe_timer(struct module_env* env)
2377 {
2378         struct trust_anchor* tp;
2379         time_t next_probe = 3600;
2380         int num = 0;
2381         verbose(VERB_ALGO, "autotrust probe timer callback");
2382         /* while there are still anchors to probe */
2383         while( (tp = todo_probe(env, &next_probe)) ) {
2384                 /* make a probe for this anchor */
2385                 probe_anchor(env, tp);
2386                 num++;
2387         }
2388         regional_free_all(env->scratch);
2389         if(num == 0)
2390                 return 0; /* no trust points to probe */
2391         verbose(VERB_ALGO, "autotrust probe timer %d callbacks done", num);
2392         return next_probe;
2393 }