contrib/unbound/validator/val_sigcrypt.c

   1 /*
   2  * validator/val_sigcrypt.c - validator signature crypto functions.
   3  *
   4  * Copyright (c) 2007, 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  * This file contains helper functions for the validator module.
  40  * The functions help with signature verification and checking, the
  41  * bridging between RR wireformat data and crypto calls.
  42  */
  43 #include "config.h"
  44 #include "validator/val_sigcrypt.h"
  45 #include "validator/val_secalgo.h"
  46 #include "validator/validator.h"
  47 #include "util/data/msgreply.h"
  48 #include "util/data/msgparse.h"
  49 #include "util/data/dname.h"
  50 #include "util/rbtree.h"
  51 #include "util/module.h"
  52 #include "util/net_help.h"
  53 #include "util/regional.h"
  54 #include "util/config_file.h"
  55 #include "sldns/keyraw.h"
  56 #include "sldns/sbuffer.h"
  57 #include "sldns/parseutil.h"
  58 #include "sldns/wire2str.h"
  59
  60 #include <ctype.h>
  61 #if !defined(HAVE_SSL) && !defined(HAVE_NSS) && !defined(HAVE_NETTLE)
  62 #error "Need crypto library to do digital signature cryptography"
  63 #endif
  64
  65 #ifdef HAVE_OPENSSL_ERR_H
  66 #include <openssl/err.h>
  67 #endif
  68
  69 #ifdef HAVE_OPENSSL_RAND_H
  70 #include <openssl/rand.h>
  71 #endif
  72
  73 #ifdef HAVE_OPENSSL_CONF_H
  74 #include <openssl/conf.h>
  75 #endif
  76
  77 #ifdef HAVE_OPENSSL_ENGINE_H
  78 #include <openssl/engine.h>
  79 #endif
  80
  81 /** return number of rrs in an rrset */
  82 static size_t
  83 rrset_get_count(struct ub_packed_rrset_key* rrset)
  84 {
  85         struct packed_rrset_data* d = (struct packed_rrset_data*)
  86         rrset->entry.data;
  87         if(!d) return 0;
  88         return d->count;
  89 }
  90
  91 /**
  92  * Get RR signature count
  93  */
  94 static size_t
  95 rrset_get_sigcount(struct ub_packed_rrset_key* k)
  96 {
  97         struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
  98         return d->rrsig_count;
  99 }
 100
 101 /**
 102  * Get signature keytag value
 103  * @param k: rrset (with signatures)
 104  * @param sig_idx: signature index.
 105  * @return keytag or 0 if malformed rrsig.
 106  */
 107 static uint16_t
 108 rrset_get_sig_keytag(struct ub_packed_rrset_key* k, size_t sig_idx)
 109 {
 110         uint16_t t;
 111         struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
 112         log_assert(sig_idx < d->rrsig_count);
 113         if(d->rr_len[d->count + sig_idx] < 2+18)
 114                 return 0;
 115         memmove(&t, d->rr_data[d->count + sig_idx]+2+16, 2);
 116         return ntohs(t);
 117 }
 118
 119 /**
 120  * Get signature signing algorithm value
 121  * @param k: rrset (with signatures)
 122  * @param sig_idx: signature index.
 123  * @return algo or 0 if malformed rrsig.
 124  */
 125 static int
 126 rrset_get_sig_algo(struct ub_packed_rrset_key* k, size_t sig_idx)
 127 {
 128         struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
 129         log_assert(sig_idx < d->rrsig_count);
 130         if(d->rr_len[d->count + sig_idx] < 2+3)
 131                 return 0;
 132         return (int)d->rr_data[d->count + sig_idx][2+2];
 133 }
 134
 135 /** get rdata pointer and size */
 136 static void
 137 rrset_get_rdata(struct ub_packed_rrset_key* k, size_t idx, uint8_t** rdata,
 138         size_t* len)
 139 {
 140         struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
 141         log_assert(d && idx < (d->count + d->rrsig_count));
 142         *rdata = d->rr_data[idx];
 143         *len = d->rr_len[idx];
 144 }
 145
 146 uint16_t
 147 dnskey_get_flags(struct ub_packed_rrset_key* k, size_t idx)
 148 {
 149         uint8_t* rdata;
 150         size_t len;
 151         uint16_t f;
 152         rrset_get_rdata(k, idx, &rdata, &len);
 153         if(len < 2+2)
 154                 return 0;
 155         memmove(&f, rdata+2, 2);
 156         f = ntohs(f);
 157         return f;
 158 }
 159
 160 /**
 161  * Get DNSKEY protocol value from rdata
 162  * @param k: DNSKEY rrset.
 163  * @param idx: which key.
 164  * @return protocol octet value
 165  */
 166 static int
 167 dnskey_get_protocol(struct ub_packed_rrset_key* k, size_t idx)
 168 {
 169         uint8_t* rdata;
 170         size_t len;
 171         rrset_get_rdata(k, idx, &rdata, &len);
 172         if(len < 2+4)
 173                 return 0;
 174         return (int)rdata[2+2];
 175 }
 176
 177 int
 178 dnskey_get_algo(struct ub_packed_rrset_key* k, size_t idx)
 179 {
 180         uint8_t* rdata;
 181         size_t len;
 182         rrset_get_rdata(k, idx, &rdata, &len);
 183         if(len < 2+4)
 184                 return 0;
 185         return (int)rdata[2+3];
 186 }
 187
 188 /** get public key rdata field from a dnskey RR and do some checks */
 189 static void
 190 dnskey_get_pubkey(struct ub_packed_rrset_key* k, size_t idx,
 191         unsigned char** pk, unsigned int* pklen)
 192 {
 193         uint8_t* rdata;
 194         size_t len;
 195         rrset_get_rdata(k, idx, &rdata, &len);
 196         if(len < 2+5) {
 197                 *pk = NULL;
 198                 *pklen = 0;
 199                 return;
 200         }
 201         *pk = (unsigned char*)rdata+2+4;
 202         *pklen = (unsigned)len-2-4;
 203 }
 204
 205 int
 206 ds_get_key_algo(struct ub_packed_rrset_key* k, size_t idx)
 207 {
 208         uint8_t* rdata;
 209         size_t len;
 210         rrset_get_rdata(k, idx, &rdata, &len);
 211         if(len < 2+3)
 212                 return 0;
 213         return (int)rdata[2+2];
 214 }
 215
 216 int
 217 ds_get_digest_algo(struct ub_packed_rrset_key* k, size_t idx)
 218 {
 219         uint8_t* rdata;
 220         size_t len;
 221         rrset_get_rdata(k, idx, &rdata, &len);
 222         if(len < 2+4)
 223                 return 0;
 224         return (int)rdata[2+3];
 225 }
 226
 227 uint16_t
 228 ds_get_keytag(struct ub_packed_rrset_key* ds_rrset, size_t ds_idx)
 229 {
 230         uint16_t t;
 231         uint8_t* rdata;
 232         size_t len;
 233         rrset_get_rdata(ds_rrset, ds_idx, &rdata, &len);
 234         if(len < 2+2)
 235                 return 0;
 236         memmove(&t, rdata+2, 2);
 237         return ntohs(t);
 238 }
 239
 240 /**
 241  * Return pointer to the digest in a DS RR.
 242  * @param k: DS rrset.
 243  * @param idx: which DS.
 244  * @param digest: digest data is returned.
 245  *      on error, this is NULL.
 246  * @param len: length of digest is returned.
 247  *      on error, the length is 0.
 248  */
 249 static void
 250 ds_get_sigdata(struct ub_packed_rrset_key* k, size_t idx, uint8_t** digest,
 251         size_t* len)
 252 {
 253         uint8_t* rdata;
 254         size_t rdlen;
 255         rrset_get_rdata(k, idx, &rdata, &rdlen);
 256         if(rdlen < 2+5) {
 257                 *digest = NULL;
 258                 *len = 0;
 259                 return;
 260         }
 261         *digest = rdata + 2 + 4;
 262         *len = rdlen - 2 - 4;
 263 }
 264
 265 /**
 266  * Return size of DS digest according to its hash algorithm.
 267  * @param k: DS rrset.
 268  * @param idx: which DS.
 269  * @return size in bytes of digest, or 0 if not supported.
 270  */
 271 static size_t
 272 ds_digest_size_algo(struct ub_packed_rrset_key* k, size_t idx)
 273 {
 274         return ds_digest_size_supported(ds_get_digest_algo(k, idx));
 275 }
 276
 277 /**
 278  * Create a DS digest for a DNSKEY entry.
 279  *
 280  * @param env: module environment. Uses scratch space.
 281  * @param dnskey_rrset: DNSKEY rrset.
 282  * @param dnskey_idx: index of RR in rrset.
 283  * @param ds_rrset: DS rrset
 284  * @param ds_idx: index of RR in DS rrset.
 285  * @param digest: digest is returned in here (must be correctly sized).
 286  * @return false on error.
 287  */
 288 static int
 289 ds_create_dnskey_digest(struct module_env* env,
 290         struct ub_packed_rrset_key* dnskey_rrset, size_t dnskey_idx,
 291         struct ub_packed_rrset_key* ds_rrset, size_t ds_idx,
 292         uint8_t* digest)
 293 {
 294         sldns_buffer* b = env->scratch_buffer;
 295         uint8_t* dnskey_rdata;
 296         size_t dnskey_len;
 297         rrset_get_rdata(dnskey_rrset, dnskey_idx, &dnskey_rdata, &dnskey_len);
 298
 299         /* create digest source material in buffer
 300          * digest = digest_algorithm( DNSKEY owner name | DNSKEY RDATA);
 301          *      DNSKEY RDATA = Flags | Protocol | Algorithm | Public Key. */
 302         sldns_buffer_clear(b);
 303         sldns_buffer_write(b, dnskey_rrset->rk.dname,
 304                 dnskey_rrset->rk.dname_len);
 305         query_dname_tolower(sldns_buffer_begin(b));
 306         sldns_buffer_write(b, dnskey_rdata+2, dnskey_len-2); /* skip rdatalen*/
 307         sldns_buffer_flip(b);
 308
 309         return secalgo_ds_digest(ds_get_digest_algo(ds_rrset, ds_idx),
 310                 (unsigned char*)sldns_buffer_begin(b), sldns_buffer_limit(b),
 311                 (unsigned char*)digest);
 312 }
 313
 314 int ds_digest_match_dnskey(struct module_env* env,
 315         struct ub_packed_rrset_key* dnskey_rrset, size_t dnskey_idx,
 316         struct ub_packed_rrset_key* ds_rrset, size_t ds_idx)
 317 {
 318         uint8_t* ds;    /* DS digest */
 319         size_t dslen;
 320         uint8_t* digest; /* generated digest */
 321         size_t digestlen = ds_digest_size_algo(ds_rrset, ds_idx);
 322
 323         if(digestlen == 0) {
 324                 verbose(VERB_QUERY, "DS fail: not supported, or DS RR "
 325                         "format error");
 326                 return 0; /* not supported, or DS RR format error */
 327         }
 328 #ifndef USE_SHA1
 329         if(fake_sha1 && ds_get_digest_algo(ds_rrset, ds_idx)==LDNS_SHA1)
 330                 return 1;
 331 #endif
 332
 333         /* check digest length in DS with length from hash function */
 334         ds_get_sigdata(ds_rrset, ds_idx, &ds, &dslen);
 335         if(!ds || dslen != digestlen) {
 336                 verbose(VERB_QUERY, "DS fail: DS RR algo and digest do not "
 337                         "match each other");
 338                 return 0; /* DS algorithm and digest do not match */
 339         }
 340
 341         digest = regional_alloc(env->scratch, digestlen);
 342         if(!digest) {
 343                 verbose(VERB_QUERY, "DS fail: out of memory");
 344                 return 0; /* mem error */
 345         }
 346         if(!ds_create_dnskey_digest(env, dnskey_rrset, dnskey_idx, ds_rrset,
 347                 ds_idx, digest)) {
 348                 verbose(VERB_QUERY, "DS fail: could not calc key digest");
 349                 return 0; /* digest algo failed */
 350         }
 351         if(memcmp(digest, ds, dslen) != 0) {
 352                 verbose(VERB_QUERY, "DS fail: digest is different");
 353                 return 0; /* digest different */
 354         }
 355         return 1;
 356 }
 357
 358 int
 359 ds_digest_algo_is_supported(struct ub_packed_rrset_key* ds_rrset,
 360         size_t ds_idx)
 361 {
 362         return (ds_digest_size_algo(ds_rrset, ds_idx) != 0);
 363 }
 364
 365 int
 366 ds_key_algo_is_supported(struct ub_packed_rrset_key* ds_rrset,
 367         size_t ds_idx)
 368 {
 369         return dnskey_algo_id_is_supported(ds_get_key_algo(ds_rrset, ds_idx));
 370 }
 371
 372 uint16_t
 373 dnskey_calc_keytag(struct ub_packed_rrset_key* dnskey_rrset, size_t dnskey_idx)
 374 {
 375         uint8_t* data;
 376         size_t len;
 377         rrset_get_rdata(dnskey_rrset, dnskey_idx, &data, &len);
 378         /* do not pass rdatalen to ldns */
 379         return sldns_calc_keytag_raw(data+2, len-2);
 380 }
 381
 382 int dnskey_algo_is_supported(struct ub_packed_rrset_key* dnskey_rrset,
 383         size_t dnskey_idx)
 384 {
 385         return dnskey_algo_id_is_supported(dnskey_get_algo(dnskey_rrset,
 386                 dnskey_idx));
 387 }
 388
 389 void algo_needs_init_dnskey_add(struct algo_needs* n,
 390         struct ub_packed_rrset_key* dnskey, uint8_t* sigalg)
 391 {
 392         uint8_t algo;
 393         size_t i, total = n->num;
 394         size_t num = rrset_get_count(dnskey);
 395
 396         for(i=0; i<num; i++) {
 397                 algo = (uint8_t)dnskey_get_algo(dnskey, i);
 398                 if(!dnskey_algo_id_is_supported((int)algo))
 399                         continue;
 400                 if(n->needs[algo] == 0) {
 401                         n->needs[algo] = 1;
 402                         sigalg[total] = algo;
 403                         total++;
 404                 }
 405         }
 406         sigalg[total] = 0;
 407         n->num = total;
 408 }
 409
 410 void algo_needs_init_list(struct algo_needs* n, uint8_t* sigalg)
 411 {
 412         uint8_t algo;
 413         size_t total = 0;
 414
 415         memset(n->needs, 0, sizeof(uint8_t)*ALGO_NEEDS_MAX);
 416         while( (algo=*sigalg++) != 0) {
 417                 log_assert(dnskey_algo_id_is_supported((int)algo));
 418                 log_assert(n->needs[algo] == 0);
 419                 n->needs[algo] = 1;
 420                 total++;
 421         }
 422         n->num = total;
 423 }
 424
 425 void algo_needs_init_ds(struct algo_needs* n, struct ub_packed_rrset_key* ds,
 426         int fav_ds_algo, uint8_t* sigalg)
 427 {
 428         uint8_t algo;
 429         size_t i, total = 0;
 430         size_t num = rrset_get_count(ds);
 431
 432         memset(n->needs, 0, sizeof(uint8_t)*ALGO_NEEDS_MAX);
 433         for(i=0; i<num; i++) {
 434                 if(ds_get_digest_algo(ds, i) != fav_ds_algo)
 435                         continue;
 436                 algo = (uint8_t)ds_get_key_algo(ds, i);
 437                 if(!dnskey_algo_id_is_supported((int)algo))
 438                         continue;
 439                 log_assert(algo != 0); /* we do not support 0 and is EOS */
 440                 if(n->needs[algo] == 0) {
 441                         n->needs[algo] = 1;
 442                         sigalg[total] = algo;
 443                         total++;
 444                 }
 445         }
 446         sigalg[total] = 0;
 447         n->num = total;
 448 }
 449
 450 int algo_needs_set_secure(struct algo_needs* n, uint8_t algo)
 451 {
 452         if(n->needs[algo]) {
 453                 n->needs[algo] = 0;
 454                 n->num --;
 455                 if(n->num == 0) /* done! */
 456                         return 1;
 457         }
 458         return 0;
 459 }
 460
 461 void algo_needs_set_bogus(struct algo_needs* n, uint8_t algo)
 462 {
 463         if(n->needs[algo]) n->needs[algo] = 2; /* need it, but bogus */
 464 }
 465
 466 size_t algo_needs_num_missing(struct algo_needs* n)
 467 {
 468         return n->num;
 469 }
 470
 471 int algo_needs_missing(struct algo_needs* n)
 472 {
 473         int i;
 474         /* first check if a needed algo was bogus - report that */
 475         for(i=0; i<ALGO_NEEDS_MAX; i++)
 476                 if(n->needs[i] == 2)
 477                         return 0;
 478         /* now check which algo is missing */
 479         for(i=0; i<ALGO_NEEDS_MAX; i++)
 480                 if(n->needs[i] == 1)
 481                         return i;
 482         return 0;
 483 }
 484
 485 enum sec_status
 486 dnskeyset_verify_rrset(struct module_env* env, struct val_env* ve,
 487         struct ub_packed_rrset_key* rrset, struct ub_packed_rrset_key* dnskey,
 488         uint8_t* sigalg, char** reason, sldns_pkt_section section,
 489         struct module_qstate* qstate)
 490 {
 491         enum sec_status sec;
 492         size_t i, num;
 493         rbtree_type* sortree = NULL;
 494         /* make sure that for all DNSKEY algorithms there are valid sigs */
 495         struct algo_needs needs;
 496         int alg;
 497
 498         num = rrset_get_sigcount(rrset);
 499         if(num == 0) {
 500                 verbose(VERB_QUERY, "rrset failed to verify due to a lack of "
 501                         "signatures");
 502                 *reason = "no signatures";
 503                 return sec_status_bogus;
 504         }
 505
 506         if(sigalg) {
 507                 algo_needs_init_list(&needs, sigalg);
 508                 if(algo_needs_num_missing(&needs) == 0) {
 509                         verbose(VERB_QUERY, "zone has no known algorithms");
 510                         *reason = "zone has no known algorithms";
 511                         return sec_status_insecure;
 512                 }
 513         }
 514         for(i=0; i<num; i++) {
 515                 sec = dnskeyset_verify_rrset_sig(env, ve, *env->now, rrset,
 516                         dnskey, i, &sortree, reason, section, qstate);
 517                 /* see which algorithm has been fixed up */
 518                 if(sec == sec_status_secure) {
 519                         if(!sigalg)
 520                                 return sec; /* done! */
 521                         else if(algo_needs_set_secure(&needs,
 522                                 (uint8_t)rrset_get_sig_algo(rrset, i)))
 523                                 return sec; /* done! */
 524                 } else if(sigalg && sec == sec_status_bogus) {
 525                         algo_needs_set_bogus(&needs,
 526                                 (uint8_t)rrset_get_sig_algo(rrset, i));
 527                 }
 528         }
 529         if(sigalg && (alg=algo_needs_missing(&needs)) != 0) {
 530                 verbose(VERB_ALGO, "rrset failed to verify: "
 531                         "no valid signatures for %d algorithms",
 532                         (int)algo_needs_num_missing(&needs));
 533                 algo_needs_reason(env, alg, reason, "no signatures");
 534         } else {
 535                 verbose(VERB_ALGO, "rrset failed to verify: "
 536                         "no valid signatures");
 537         }
 538         return sec_status_bogus;
 539 }
 540
 541 void algo_needs_reason(struct module_env* env, int alg, char** reason, char* s)
 542 {
 543         char buf[256];
 544         sldns_lookup_table *t = sldns_lookup_by_id(sldns_algorithms, alg);
 545         if(t&&t->name)
 546                 snprintf(buf, sizeof(buf), "%s with algorithm %s", s, t->name);
 547         else    snprintf(buf, sizeof(buf), "%s with algorithm ALG%u", s,
 548                         (unsigned)alg);
 549         *reason = regional_strdup(env->scratch, buf);
 550         if(!*reason)
 551                 *reason = s;
 552 }
 553
 554 enum sec_status
 555 dnskey_verify_rrset(struct module_env* env, struct val_env* ve,
 556         struct ub_packed_rrset_key* rrset, struct ub_packed_rrset_key* dnskey,
 557         size_t dnskey_idx, char** reason, sldns_pkt_section section,
 558         struct module_qstate* qstate)
 559 {
 560         enum sec_status sec;
 561         size_t i, num, numchecked = 0;
 562         rbtree_type* sortree = NULL;
 563         int buf_canon = 0;
 564         uint16_t tag = dnskey_calc_keytag(dnskey, dnskey_idx);
 565         int algo = dnskey_get_algo(dnskey, dnskey_idx);
 566
 567         num = rrset_get_sigcount(rrset);
 568         if(num == 0) {
 569                 verbose(VERB_QUERY, "rrset failed to verify due to a lack of "
 570                         "signatures");
 571                 *reason = "no signatures";
 572                 return sec_status_bogus;
 573         }
 574         for(i=0; i<num; i++) {
 575                 /* see if sig matches keytag and algo */
 576                 if(algo != rrset_get_sig_algo(rrset, i) ||
 577                         tag != rrset_get_sig_keytag(rrset, i))
 578                         continue;
 579                 buf_canon = 0;
 580                 sec = dnskey_verify_rrset_sig(env->scratch,
 581                         env->scratch_buffer, ve, *env->now, rrset,
 582                         dnskey, dnskey_idx, i, &sortree, &buf_canon, reason,
 583                         section, qstate);
 584                 if(sec == sec_status_secure)
 585                         return sec;
 586                 numchecked ++;
 587         }
 588         verbose(VERB_ALGO, "rrset failed to verify: all signatures are bogus");
 589         if(!numchecked) *reason = "signature missing";
 590         return sec_status_bogus;
 591 }
 592
 593 enum sec_status
 594 dnskeyset_verify_rrset_sig(struct module_env* env, struct val_env* ve,
 595         time_t now, struct ub_packed_rrset_key* rrset,
 596         struct ub_packed_rrset_key* dnskey, size_t sig_idx,
 597         struct rbtree_type** sortree, char** reason, sldns_pkt_section section,
 598         struct module_qstate* qstate)
 599 {
 600         /* find matching keys and check them */
 601         enum sec_status sec = sec_status_bogus;
 602         uint16_t tag = rrset_get_sig_keytag(rrset, sig_idx);
 603         int algo = rrset_get_sig_algo(rrset, sig_idx);
 604         size_t i, num = rrset_get_count(dnskey);
 605         size_t numchecked = 0;
 606         int buf_canon = 0;
 607         verbose(VERB_ALGO, "verify sig %d %d", (int)tag, algo);
 608         if(!dnskey_algo_id_is_supported(algo)) {
 609                 verbose(VERB_QUERY, "verify sig: unknown algorithm");
 610                 return sec_status_insecure;
 611         }
 612
 613         for(i=0; i<num; i++) {
 614                 /* see if key matches keytag and algo */
 615                 if(algo != dnskey_get_algo(dnskey, i) ||
 616                         tag != dnskey_calc_keytag(dnskey, i))
 617                         continue;
 618                 numchecked ++;
 619
 620                 /* see if key verifies */
 621                 sec = dnskey_verify_rrset_sig(env->scratch,
 622                         env->scratch_buffer, ve, now, rrset, dnskey, i,
 623                         sig_idx, sortree, &buf_canon, reason, section, qstate);
 624                 if(sec == sec_status_secure)
 625                         return sec;
 626         }
 627         if(numchecked == 0) {
 628                 *reason = "signatures from unknown keys";
 629                 verbose(VERB_QUERY, "verify: could not find appropriate key");
 630                 return sec_status_bogus;
 631         }
 632         return sec_status_bogus;
 633 }
 634
 635 /**
 636  * RR entries in a canonical sorted tree of RRs
 637  */
 638 struct canon_rr {
 639         /** rbtree node, key is this structure */
 640         rbnode_type node;
 641         /** rrset the RR is in */
 642         struct ub_packed_rrset_key* rrset;
 643         /** which RR in the rrset */
 644         size_t rr_idx;
 645 };
 646
 647 /**
 648  * Compare two RR for canonical order, in a field-style sweep.
 649  * @param d: rrset data
 650  * @param desc: ldns wireformat descriptor.
 651  * @param i: first RR to compare
 652  * @param j: first RR to compare
 653  * @return comparison code.
 654  */
 655 static int
 656 canonical_compare_byfield(struct packed_rrset_data* d,
 657         const sldns_rr_descriptor* desc, size_t i, size_t j)
 658 {
 659         /* sweep across rdata, keep track of some state:
 660          *      which rr field, and bytes left in field.
 661          *      current position in rdata, length left.
 662          *      are we in a dname, length left in a label.
 663          */
 664         int wfi = -1;   /* current wireformat rdata field (rdf) */
 665         int wfj = -1;
 666         uint8_t* di = d->rr_data[i]+2; /* ptr to current rdata byte */
 667         uint8_t* dj = d->rr_data[j]+2;
 668         size_t ilen = d->rr_len[i]-2; /* length left in rdata */
 669         size_t jlen = d->rr_len[j]-2;
 670         int dname_i = 0;  /* true if these bytes are part of a name */
 671         int dname_j = 0;
 672         size_t lablen_i = 0; /* 0 for label length byte,for first byte of rdf*/
 673         size_t lablen_j = 0; /* otherwise remaining length of rdf or label */
 674         int dname_num_i = (int)desc->_dname_count; /* decreased at root label */
 675         int dname_num_j = (int)desc->_dname_count;
 676
 677         /* loop while there are rdata bytes available for both rrs,
 678          * and still some lowercasing needs to be done; either the dnames
 679          * have not been reached yet, or they are currently being processed */
 680         while(ilen > 0 && jlen > 0 && (dname_num_i > 0 || dname_num_j > 0)) {
 681                 /* compare these two bytes */
 682                 /* lowercase if in a dname and not a label length byte */
 683                 if( ((dname_i && lablen_i)?(uint8_t)tolower((int)*di):*di)
 684                  != ((dname_j && lablen_j)?(uint8_t)tolower((int)*dj):*dj)
 685                  ) {
 686                   if(((dname_i && lablen_i)?(uint8_t)tolower((int)*di):*di)
 687                   < ((dname_j && lablen_j)?(uint8_t)tolower((int)*dj):*dj))
 688                         return -1;
 689                     return 1;
 690                 }
 691                 ilen--;
 692                 jlen--;
 693                 /* bytes are equal */
 694
 695                 /* advance field i */
 696                 /* lablen 0 means that this byte is the first byte of the
 697                  * next rdata field; inspect this rdata field and setup
 698                  * to process the rest of this rdata field.
 699                  * The reason to first read the byte, then setup the rdf,
 700                  * is that we are then sure the byte is available and short
 701                  * rdata is handled gracefully (even if it is a formerr). */
 702                 if(lablen_i == 0) {
 703                         if(dname_i) {
 704                                 /* scan this dname label */
 705                                 /* capture length to lowercase */
 706                                 lablen_i = (size_t)*di;
 707                                 if(lablen_i == 0) {
 708                                         /* end root label */
 709                                         dname_i = 0;
 710                                         dname_num_i--;
 711                                         /* if dname num is 0, then the
 712                                          * remainder is binary only */
 713                                         if(dname_num_i == 0)
 714                                                 lablen_i = ilen;
 715                                 }
 716                         } else {
 717                                 /* scan this rdata field */
 718                                 wfi++;
 719                                 if(desc->_wireformat[wfi]
 720                                         == LDNS_RDF_TYPE_DNAME) {
 721                                         dname_i = 1;
 722                                         lablen_i = (size_t)*di;
 723                                         if(lablen_i == 0) {
 724                                                 dname_i = 0;
 725                                                 dname_num_i--;
 726                                                 if(dname_num_i == 0)
 727                                                         lablen_i = ilen;
 728                                         }
 729                                 } else if(desc->_wireformat[wfi]
 730                                         == LDNS_RDF_TYPE_STR)
 731                                         lablen_i = (size_t)*di;
 732                                 else    lablen_i = get_rdf_size(
 733                                         desc->_wireformat[wfi]) - 1;
 734                         }
 735                 } else  lablen_i--;
 736
 737                 /* advance field j; same as for i */
 738                 if(lablen_j == 0) {
 739                         if(dname_j) {
 740                                 lablen_j = (size_t)*dj;
 741                                 if(lablen_j == 0) {
 742                                         dname_j = 0;
 743                                         dname_num_j--;
 744                                         if(dname_num_j == 0)
 745                                                 lablen_j = jlen;
 746                                 }
 747                         } else {
 748                                 wfj++;
 749                                 if(desc->_wireformat[wfj]
 750                                         == LDNS_RDF_TYPE_DNAME) {
 751                                         dname_j = 1;
 752                                         lablen_j = (size_t)*dj;
 753                                         if(lablen_j == 0) {
 754                                                 dname_j = 0;
 755                                                 dname_num_j--;
 756                                                 if(dname_num_j == 0)
 757                                                         lablen_j = jlen;
 758                                         }
 759                                 } else if(desc->_wireformat[wfj]
 760                                         == LDNS_RDF_TYPE_STR)
 761                                         lablen_j = (size_t)*dj;
 762                                 else    lablen_j = get_rdf_size(
 763                                         desc->_wireformat[wfj]) - 1;
 764                         }
 765                 } else  lablen_j--;
 766                 di++;
 767                 dj++;
 768         }
 769         /* end of the loop; because we advanced byte by byte; now we have
 770          * that the rdata has ended, or that there is a binary remainder */
 771         /* shortest first */
 772         if(ilen == 0 && jlen == 0)
 773                 return 0;
 774         if(ilen == 0)
 775                 return -1;
 776         if(jlen == 0)
 777                 return 1;
 778         /* binary remainder, capture comparison in wfi variable */
 779         if((wfi = memcmp(di, dj, (ilen<jlen)?ilen:jlen)) != 0)
 780                 return wfi;
 781         if(ilen < jlen)
 782                 return -1;
 783         if(jlen < ilen)
 784                 return 1;
 785         return 0;
 786 }
 787
 788 /**
 789  * Compare two RRs in the same RRset and determine their relative
 790  * canonical order.
 791  * @param rrset: the rrset in which to perform compares.
 792  * @param i: first RR to compare
 793  * @param j: first RR to compare
 794  * @return 0 if RR i== RR j, -1 if <, +1 if >.
 795  */
 796 static int
 797 canonical_compare(struct ub_packed_rrset_key* rrset, size_t i, size_t j)
 798 {
 799         struct packed_rrset_data* d = (struct packed_rrset_data*)
 800                 rrset->entry.data;
 801         const sldns_rr_descriptor* desc;
 802         uint16_t type = ntohs(rrset->rk.type);
 803         size_t minlen;
 804         int c;
 805
 806         if(i==j)
 807                 return 0;
 808
 809         switch(type) {
 810                 /* These RR types have only a name as RDATA.
 811                  * This name has to be canonicalized.*/
 812                 case LDNS_RR_TYPE_NS:
 813                 case LDNS_RR_TYPE_MD:
 814                 case LDNS_RR_TYPE_MF:
 815                 case LDNS_RR_TYPE_CNAME:
 816                 case LDNS_RR_TYPE_MB:
 817                 case LDNS_RR_TYPE_MG:
 818                 case LDNS_RR_TYPE_MR:
 819                 case LDNS_RR_TYPE_PTR:
 820                 case LDNS_RR_TYPE_DNAME:
 821                         /* the wireread function has already checked these
 822                          * dname's for correctness, and this double checks */
 823                         if(!dname_valid(d->rr_data[i]+2, d->rr_len[i]-2) ||
 824                                 !dname_valid(d->rr_data[j]+2, d->rr_len[j]-2))
 825                                 return 0;
 826                         return query_dname_compare(d->rr_data[i]+2,
 827                                 d->rr_data[j]+2);
 828
 829                 /* These RR types have STR and fixed size rdata fields
 830                  * before one or more name fields that need canonicalizing,
 831                  * and after that a byte-for byte remainder can be compared.
 832                  */
 833                 /* type starts with the name; remainder is binary compared */
 834                 case LDNS_RR_TYPE_NXT:
 835                 /* use rdata field formats */
 836                 case LDNS_RR_TYPE_MINFO:
 837                 case LDNS_RR_TYPE_RP:
 838                 case LDNS_RR_TYPE_SOA:
 839                 case LDNS_RR_TYPE_RT:
 840                 case LDNS_RR_TYPE_AFSDB:
 841                 case LDNS_RR_TYPE_KX:
 842                 case LDNS_RR_TYPE_MX:
 843                 case LDNS_RR_TYPE_SIG:
 844                 /* RRSIG signer name has to be downcased */
 845                 case LDNS_RR_TYPE_RRSIG:
 846                 case LDNS_RR_TYPE_PX:
 847                 case LDNS_RR_TYPE_NAPTR:
 848                 case LDNS_RR_TYPE_SRV:
 849                         desc = sldns_rr_descript(type);
 850                         log_assert(desc);
 851                         /* this holds for the types that need canonicalizing */
 852                         log_assert(desc->_minimum == desc->_maximum);
 853                         return canonical_compare_byfield(d, desc, i, j);
 854
 855                 case LDNS_RR_TYPE_HINFO: /* no longer downcased */
 856                 case LDNS_RR_TYPE_NSEC:
 857         default:
 858                 /* For unknown RR types, or types not listed above,
 859                  * no canonicalization is needed, do binary compare */
 860                 /* byte for byte compare, equal means shortest first*/
 861                 minlen = d->rr_len[i]-2;
 862                 if(minlen > d->rr_len[j]-2)
 863                         minlen = d->rr_len[j]-2;
 864                 c = memcmp(d->rr_data[i]+2, d->rr_data[j]+2, minlen);
 865                 if(c!=0)
 866                         return c;
 867                 /* rdata equal, shortest is first */
 868                 if(d->rr_len[i] < d->rr_len[j])
 869                         return -1;
 870                 if(d->rr_len[i] > d->rr_len[j])
 871                         return 1;
 872                 /* rdata equal, length equal */
 873                 break;
 874         }
 875         return 0;
 876 }
 877
 878 int
 879 canonical_tree_compare(const void* k1, const void* k2)
 880 {
 881         struct canon_rr* r1 = (struct canon_rr*)k1;
 882         struct canon_rr* r2 = (struct canon_rr*)k2;
 883         log_assert(r1->rrset == r2->rrset);
 884         return canonical_compare(r1->rrset, r1->rr_idx, r2->rr_idx);
 885 }
 886
 887 /**
 888  * Sort RRs for rrset in canonical order.
 889  * Does not actually canonicalize the RR rdatas.
 890  * Does not touch rrsigs.
 891  * @param rrset: to sort.
 892  * @param d: rrset data.
 893  * @param sortree: tree to sort into.
 894  * @param rrs: rr storage.
 895  */
 896 static void
 897 canonical_sort(struct ub_packed_rrset_key* rrset, struct packed_rrset_data* d,
 898         rbtree_type* sortree, struct canon_rr* rrs)
 899 {
 900         size_t i;
 901         /* insert into rbtree to sort and detect duplicates */
 902         for(i=0; i<d->count; i++) {
 903                 rrs[i].node.key = &rrs[i];
 904                 rrs[i].rrset = rrset;
 905                 rrs[i].rr_idx = i;
 906                 if(!rbtree_insert(sortree, &rrs[i].node)) {
 907                         /* this was a duplicate */
 908                 }
 909         }
 910 }
 911
 912 /**
 913  * Insert canonical owner name into buffer.
 914  * @param buf: buffer to insert into at current position.
 915  * @param k: rrset with its owner name.
 916  * @param sig: signature with signer name and label count.
 917  *      must be length checked, at least 18 bytes long.
 918  * @param can_owner: position in buffer returned for future use.
 919  * @param can_owner_len: length of canonical owner name.
 920  */
 921 static void
 922 insert_can_owner(sldns_buffer* buf, struct ub_packed_rrset_key* k,
 923         uint8_t* sig, uint8_t** can_owner, size_t* can_owner_len)
 924 {
 925         int rrsig_labels = (int)sig[3];
 926         int fqdn_labels = dname_signame_label_count(k->rk.dname);
 927         *can_owner = sldns_buffer_current(buf);
 928         if(rrsig_labels == fqdn_labels) {
 929                 /* no change */
 930                 sldns_buffer_write(buf, k->rk.dname, k->rk.dname_len);
 931                 query_dname_tolower(*can_owner);
 932                 *can_owner_len = k->rk.dname_len;
 933                 return;
 934         }
 935         log_assert(rrsig_labels < fqdn_labels);
 936         /* *. | fqdn(rightmost rrsig_labels) */
 937         if(rrsig_labels < fqdn_labels) {
 938                 int i;
 939                 uint8_t* nm = k->rk.dname;
 940                 size_t len = k->rk.dname_len;
 941                 /* so skip fqdn_labels-rrsig_labels */
 942                 for(i=0; i<fqdn_labels-rrsig_labels; i++) {
 943                         dname_remove_label(&nm, &len);
 944                 }
 945                 *can_owner_len = len+2;
 946                 sldns_buffer_write(buf, (uint8_t*)"\001*", 2);
 947                 sldns_buffer_write(buf, nm, len);
 948                 query_dname_tolower(*can_owner);
 949         }
 950 }
 951
 952 /**
 953  * Canonicalize Rdata in buffer.
 954  * @param buf: buffer at position just after the rdata.
 955  * @param rrset: rrset with type.
 956  * @param len: length of the rdata (including rdatalen uint16).
 957  */
 958 static void
 959 canonicalize_rdata(sldns_buffer* buf, struct ub_packed_rrset_key* rrset,
 960         size_t len)
 961 {
 962         uint8_t* datstart = sldns_buffer_current(buf)-len+2;
 963         switch(ntohs(rrset->rk.type)) {
 964                 case LDNS_RR_TYPE_NXT:
 965                 case LDNS_RR_TYPE_NS:
 966                 case LDNS_RR_TYPE_MD:
 967                 case LDNS_RR_TYPE_MF:
 968                 case LDNS_RR_TYPE_CNAME:
 969                 case LDNS_RR_TYPE_MB:
 970                 case LDNS_RR_TYPE_MG:
 971                 case LDNS_RR_TYPE_MR:
 972                 case LDNS_RR_TYPE_PTR:
 973                 case LDNS_RR_TYPE_DNAME:
 974                         /* type only has a single argument, the name */
 975                         query_dname_tolower(datstart);
 976                         return;
 977                 case LDNS_RR_TYPE_MINFO:
 978                 case LDNS_RR_TYPE_RP:
 979                 case LDNS_RR_TYPE_SOA:
 980                         /* two names after another */
 981                         query_dname_tolower(datstart);
 982                         query_dname_tolower(datstart +
 983                                 dname_valid(datstart, len-2));
 984                         return;
 985                 case LDNS_RR_TYPE_RT:
 986                 case LDNS_RR_TYPE_AFSDB:
 987                 case LDNS_RR_TYPE_KX:
 988                 case LDNS_RR_TYPE_MX:
 989                         /* skip fixed part */
 990                         if(len < 2+2+1) /* rdlen, skiplen, 1byteroot */
 991                                 return;
 992                         datstart += 2;
 993                         query_dname_tolower(datstart);
 994                         return;
 995                 case LDNS_RR_TYPE_SIG:
 996                 /* downcase the RRSIG, compat with BIND (kept it from SIG) */
 997                 case LDNS_RR_TYPE_RRSIG:
 998                         /* skip fixed part */
 999                         if(len < 2+18+1)
1000                                 return;
1001                         datstart += 18;
1002                         query_dname_tolower(datstart);
1003                         return;
1004                 case LDNS_RR_TYPE_PX:
1005                         /* skip, then two names after another */
1006                         if(len < 2+2+1)
1007                                 return;
1008                         datstart += 2;
1009                         query_dname_tolower(datstart);
1010                         query_dname_tolower(datstart +
1011                                 dname_valid(datstart, len-2-2));
1012                         return;
1013                 case LDNS_RR_TYPE_NAPTR:
1014                         if(len < 2+4)
1015                                 return;
1016                         len -= 2+4;
1017                         datstart += 4;
1018                         if(len < (size_t)datstart[0]+1) /* skip text field */
1019                                 return;
1020                         len -= (size_t)datstart[0]+1;
1021                         datstart += (size_t)datstart[0]+1;
1022                         if(len < (size_t)datstart[0]+1) /* skip text field */
1023                                 return;
1024                         len -= (size_t)datstart[0]+1;
1025                         datstart += (size_t)datstart[0]+1;
1026                         if(len < (size_t)datstart[0]+1) /* skip text field */
1027                                 return;
1028                         len -= (size_t)datstart[0]+1;
1029                         datstart += (size_t)datstart[0]+1;
1030                         if(len < 1)     /* check name is at least 1 byte*/
1031                                 return;
1032                         query_dname_tolower(datstart);
1033                         return;
1034                 case LDNS_RR_TYPE_SRV:
1035                         /* skip fixed part */
1036                         if(len < 2+6+1)
1037                                 return;
1038                         datstart += 6;
1039                         query_dname_tolower(datstart);
1040                         return;
1041
1042                 /* do not canonicalize NSEC rdata name, compat with
1043                  * from bind 9.4 signer, where it does not do so */
1044                 case LDNS_RR_TYPE_NSEC: /* type starts with the name */
1045                 case LDNS_RR_TYPE_HINFO: /* not downcased */
1046                 /* A6 not supported */
1047                 default:
1048                         /* nothing to do for unknown types */
1049                         return;
1050         }
1051 }
1052
1053 int rrset_canonical_equal(struct regional* region,
1054         struct ub_packed_rrset_key* k1, struct ub_packed_rrset_key* k2)
1055 {
1056         struct rbtree_type sortree1, sortree2;
1057         struct canon_rr *rrs1, *rrs2, *p1, *p2;
1058         struct packed_rrset_data* d1=(struct packed_rrset_data*)k1->entry.data;
1059         struct packed_rrset_data* d2=(struct packed_rrset_data*)k2->entry.data;
1060         struct ub_packed_rrset_key fk;
1061         struct packed_rrset_data fd;
1062         size_t flen[2];
1063         uint8_t* fdata[2];
1064
1065         /* basic compare */
1066         if(k1->rk.dname_len != k2->rk.dname_len ||
1067                 k1->rk.flags != k2->rk.flags ||
1068                 k1->rk.type != k2->rk.type ||
1069                 k1->rk.rrset_class != k2->rk.rrset_class ||
1070                 query_dname_compare(k1->rk.dname, k2->rk.dname) != 0)
1071                 return 0;
1072         if(d1->ttl != d2->ttl ||
1073                 d1->count != d2->count ||
1074                 d1->rrsig_count != d2->rrsig_count ||
1075                 d1->trust != d2->trust ||
1076                 d1->security != d2->security)
1077                 return 0;
1078
1079         /* init */
1080         memset(&fk, 0, sizeof(fk));
1081         memset(&fd, 0, sizeof(fd));
1082         fk.entry.data = &fd;
1083         fd.count = 2;
1084         fd.rr_len = flen;
1085         fd.rr_data = fdata;
1086         rbtree_init(&sortree1, &canonical_tree_compare);
1087         rbtree_init(&sortree2, &canonical_tree_compare);
1088         if(d1->count > RR_COUNT_MAX || d2->count > RR_COUNT_MAX)
1089                 return 1; /* protection against integer overflow */
1090         rrs1 = regional_alloc(region, sizeof(struct canon_rr)*d1->count);
1091         rrs2 = regional_alloc(region, sizeof(struct canon_rr)*d2->count);
1092         if(!rrs1 || !rrs2) return 1; /* alloc failure */
1093
1094         /* sort */
1095         canonical_sort(k1, d1, &sortree1, rrs1);
1096         canonical_sort(k2, d2, &sortree2, rrs2);
1097
1098         /* compare canonical-sorted RRs for canonical-equality */
1099         if(sortree1.count != sortree2.count)
1100                 return 0;
1101         p1 = (struct canon_rr*)rbtree_first(&sortree1);
1102         p2 = (struct canon_rr*)rbtree_first(&sortree2);
1103         while(p1 != (struct canon_rr*)RBTREE_NULL &&
1104                 p2 != (struct canon_rr*)RBTREE_NULL) {
1105                 flen[0] = d1->rr_len[p1->rr_idx];
1106                 flen[1] = d2->rr_len[p2->rr_idx];
1107                 fdata[0] = d1->rr_data[p1->rr_idx];
1108                 fdata[1] = d2->rr_data[p2->rr_idx];
1109
1110                 if(canonical_compare(&fk, 0, 1) != 0)
1111                         return 0;
1112                 p1 = (struct canon_rr*)rbtree_next(&p1->node);
1113                 p2 = (struct canon_rr*)rbtree_next(&p2->node);
1114         }
1115         return 1;
1116 }
1117
1118 /**
1119  * Create canonical form of rrset in the scratch buffer.
1120  * @param region: temporary region.
1121  * @param buf: the buffer to use.
1122  * @param k: the rrset to insert.
1123  * @param sig: RRSIG rdata to include.
1124  * @param siglen: RRSIG rdata len excluding signature field, but inclusive
1125  *      signer name length.
1126  * @param sortree: if NULL is passed a new sorted rrset tree is built.
1127  *      Otherwise it is reused.
1128  * @param section: section of packet where this rrset comes from.
1129  * @param qstate: qstate with region.
1130  * @return false on alloc error.
1131  */
1132 static int
1133 rrset_canonical(struct regional* region, sldns_buffer* buf,
1134         struct ub_packed_rrset_key* k, uint8_t* sig, size_t siglen,
1135         struct rbtree_type** sortree, sldns_pkt_section section,
1136         struct module_qstate* qstate)
1137 {
1138         struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
1139         uint8_t* can_owner = NULL;
1140         size_t can_owner_len = 0;
1141         struct canon_rr* walk;
1142         struct canon_rr* rrs;
1143
1144         if(!*sortree) {
1145                 *sortree = (struct rbtree_type*)regional_alloc(region,
1146                         sizeof(rbtree_type));
1147                 if(!*sortree)
1148                         return 0;
1149                 if(d->count > RR_COUNT_MAX)
1150                         return 0; /* integer overflow protection */
1151                 rrs = regional_alloc(region, sizeof(struct canon_rr)*d->count);
1152                 if(!rrs) {
1153                         *sortree = NULL;
1154                         return 0;
1155                 }
1156                 rbtree_init(*sortree, &canonical_tree_compare);
1157                 canonical_sort(k, d, *sortree, rrs);
1158         }
1159
1160         sldns_buffer_clear(buf);
1161         sldns_buffer_write(buf, sig, siglen);
1162         /* canonicalize signer name */
1163         query_dname_tolower(sldns_buffer_begin(buf)+18);
1164         RBTREE_FOR(walk, struct canon_rr*, (*sortree)) {
1165                 /* see if there is enough space left in the buffer */
1166                 if(sldns_buffer_remaining(buf) < can_owner_len + 2 + 2 + 4
1167                         + d->rr_len[walk->rr_idx]) {
1168                         log_err("verify: failed to canonicalize, "
1169                                 "rrset too big");
1170                         return 0;
1171                 }
1172                 /* determine canonical owner name */
1173                 if(can_owner)
1174                         sldns_buffer_write(buf, can_owner, can_owner_len);
1175                 else    insert_can_owner(buf, k, sig, &can_owner,
1176                                 &can_owner_len);
1177                 sldns_buffer_write(buf, &k->rk.type, 2);
1178                 sldns_buffer_write(buf, &k->rk.rrset_class, 2);
1179                 sldns_buffer_write(buf, sig+4, 4);
1180                 sldns_buffer_write(buf, d->rr_data[walk->rr_idx],
1181                         d->rr_len[walk->rr_idx]);
1182                 canonicalize_rdata(buf, k, d->rr_len[walk->rr_idx]);
1183         }
1184         sldns_buffer_flip(buf);
1185
1186         /* Replace RR owner with canonical owner for NSEC records in authority
1187          * section, to prevent that a wildcard synthesized NSEC can be used in
1188          * the non-existence proves. */
1189         if(ntohs(k->rk.type) == LDNS_RR_TYPE_NSEC &&
1190                 section == LDNS_SECTION_AUTHORITY) {
1191                 k->rk.dname = regional_alloc_init(qstate->region, can_owner,
1192                         can_owner_len);
1193                 if(!k->rk.dname)
1194                         return 0;
1195                 k->rk.dname_len = can_owner_len;
1196         }
1197
1198
1199         return 1;
1200 }
1201
1202 /** pretty print rrsig error with dates */
1203 static void
1204 sigdate_error(const char* str, int32_t expi, int32_t incep, int32_t now)
1205 {
1206         struct tm tm;
1207         char expi_buf[16];
1208         char incep_buf[16];
1209         char now_buf[16];
1210         time_t te, ti, tn;
1211
1212         if(verbosity < VERB_QUERY)
1213                 return;
1214         te = (time_t)expi;
1215         ti = (time_t)incep;
1216         tn = (time_t)now;
1217         memset(&tm, 0, sizeof(tm));
1218         if(gmtime_r(&te, &tm) && strftime(expi_buf, 15, "%Y%m%d%H%M%S", &tm)
1219          &&gmtime_r(&ti, &tm) && strftime(incep_buf, 15, "%Y%m%d%H%M%S", &tm)
1220          &&gmtime_r(&tn, &tm) && strftime(now_buf, 15, "%Y%m%d%H%M%S", &tm)) {
1221                 log_info("%s expi=%s incep=%s now=%s", str, expi_buf,
1222                         incep_buf, now_buf);
1223         } else
1224                 log_info("%s expi=%u incep=%u now=%u", str, (unsigned)expi,
1225                         (unsigned)incep, (unsigned)now);
1226 }
1227
1228 /** RFC 1982 comparison, uses unsigned integers, and tries to avoid
1229  * compiler optimization (eg. by avoiding a-b<0 comparisons),
1230  * this routine matches compare_serial(), for SOA serial number checks */
1231 static int
1232 compare_1982(uint32_t a, uint32_t b)
1233 {
1234         /* for 32 bit values */
1235         const uint32_t cutoff = ((uint32_t) 1 << (32 - 1));
1236
1237         if (a == b) {
1238                 return 0;
1239         } else if ((a < b && b - a < cutoff) || (a > b && a - b > cutoff)) {
1240                 return -1;
1241         } else {
1242                 return 1;
1243         }
1244 }
1245
1246 /** if we know that b is larger than a, return the difference between them,
1247  * that is the distance between them. in RFC1982 arith */
1248 static uint32_t
1249 subtract_1982(uint32_t a, uint32_t b)
1250 {
1251         /* for 32 bit values */
1252         const uint32_t cutoff = ((uint32_t) 1 << (32 - 1));
1253
1254         if(a == b)
1255                 return 0;
1256         if(a < b && b - a < cutoff) {
1257                 return b-a;
1258         }
1259         if(a > b && a - b > cutoff) {
1260                 return ((uint32_t)0xffffffff) - (a-b-1);
1261         }
1262         /* wrong case, b smaller than a */
1263         return 0;
1264 }
1265
1266 /** check rrsig dates */
1267 static int
1268 check_dates(struct val_env* ve, uint32_t unow,
1269         uint8_t* expi_p, uint8_t* incep_p, char** reason)
1270 {
1271         /* read out the dates */
1272         uint32_t expi, incep, now;
1273         memmove(&expi, expi_p, sizeof(expi));
1274         memmove(&incep, incep_p, sizeof(incep));
1275         expi = ntohl(expi);
1276         incep = ntohl(incep);
1277
1278         /* get current date */
1279         if(ve->date_override) {
1280                 if(ve->date_override == -1) {
1281                         verbose(VERB_ALGO, "date override: ignore date");
1282                         return 1;
1283                 }
1284                 now = ve->date_override;
1285                 verbose(VERB_ALGO, "date override option %d", (int)now);
1286         } else  now = unow;
1287
1288         /* check them */
1289         if(compare_1982(incep, expi) > 0) {
1290                 sigdate_error("verify: inception after expiration, "
1291                         "signature bad", expi, incep, now);
1292                 *reason = "signature inception after expiration";
1293                 return 0;
1294         }
1295         if(compare_1982(incep, now) > 0) {
1296                 /* within skew ? (calc here to avoid calculation normally) */
1297                 uint32_t skew = subtract_1982(incep, expi)/10;
1298                 if(skew < (uint32_t)ve->skew_min) skew = ve->skew_min;
1299                 if(skew > (uint32_t)ve->skew_max) skew = ve->skew_max;
1300                 if(subtract_1982(now, incep) > skew) {
1301                         sigdate_error("verify: signature bad, current time is"
1302                                 " before inception date", expi, incep, now);
1303                         *reason = "signature before inception date";
1304                         return 0;
1305                 }
1306                 sigdate_error("verify warning suspicious signature inception "
1307                         " or bad local clock", expi, incep, now);
1308         }
1309         if(compare_1982(now, expi) > 0) {
1310                 uint32_t skew = subtract_1982(incep, expi)/10;
1311                 if(skew < (uint32_t)ve->skew_min) skew = ve->skew_min;
1312                 if(skew > (uint32_t)ve->skew_max) skew = ve->skew_max;
1313                 if(subtract_1982(expi, now) > skew) {
1314                         sigdate_error("verify: signature expired", expi,
1315                                 incep, now);
1316                         *reason = "signature expired";
1317                         return 0;
1318                 }
1319                 sigdate_error("verify warning suspicious signature expiration "
1320                         " or bad local clock", expi, incep, now);
1321         }
1322         return 1;
1323 }
1324
1325 /** adjust rrset TTL for verified rrset, compare to original TTL and expi */
1326 static void
1327 adjust_ttl(struct val_env* ve, uint32_t unow,
1328         struct ub_packed_rrset_key* rrset, uint8_t* orig_p,
1329         uint8_t* expi_p, uint8_t* incep_p)
1330 {
1331         struct packed_rrset_data* d =
1332                 (struct packed_rrset_data*)rrset->entry.data;
1333         /* read out the dates */
1334         int32_t origttl, expittl, expi, incep, now;
1335         memmove(&origttl, orig_p, sizeof(origttl));
1336         memmove(&expi, expi_p, sizeof(expi));
1337         memmove(&incep, incep_p, sizeof(incep));
1338         expi = ntohl(expi);
1339         incep = ntohl(incep);
1340         origttl = ntohl(origttl);
1341
1342         /* get current date */
1343         if(ve->date_override) {
1344                 now = ve->date_override;
1345         } else  now = (int32_t)unow;
1346         expittl = expi - now;
1347
1348         /* so now:
1349          * d->ttl: rrset ttl read from message or cache. May be reduced
1350          * origttl: original TTL from signature, authoritative TTL max.
1351          * MIN_TTL: minimum TTL from config.
1352          * expittl: TTL until the signature expires.
1353          *
1354          * Use the smallest of these, but don't let origttl set the TTL
1355          * below the minimum.
1356          */
1357         if(MIN_TTL > (time_t)origttl && d->ttl > MIN_TTL) {
1358                 verbose(VERB_QUERY, "rrset TTL larger than original and minimum"
1359                         " TTL, adjusting TTL downwards to minimum ttl");
1360                 d->ttl = MIN_TTL;
1361         }
1362         else if(MIN_TTL <= origttl && d->ttl > (time_t)origttl) {
1363                 verbose(VERB_QUERY, "rrset TTL larger than original TTL, "
1364                 "adjusting TTL downwards to original ttl");
1365                 d->ttl = origttl;
1366         }
1367
1368         if(expittl > 0 && d->ttl > (time_t)expittl) {
1369                 verbose(VERB_ALGO, "rrset TTL larger than sig expiration ttl,"
1370                         " adjusting TTL downwards");
1371                 d->ttl = expittl;
1372         }
1373 }
1374
1375 enum sec_status
1376 dnskey_verify_rrset_sig(struct regional* region, sldns_buffer* buf,
1377         struct val_env* ve, time_t now,
1378         struct ub_packed_rrset_key* rrset, struct ub_packed_rrset_key* dnskey,
1379         size_t dnskey_idx, size_t sig_idx,
1380         struct rbtree_type** sortree, int* buf_canon, char** reason,
1381         sldns_pkt_section section, struct module_qstate* qstate)
1382 {
1383         enum sec_status sec;
1384         uint8_t* sig;           /* RRSIG rdata */
1385         size_t siglen;
1386         size_t rrnum = rrset_get_count(rrset);
1387         uint8_t* signer;        /* rrsig signer name */
1388         size_t signer_len;
1389         unsigned char* sigblock; /* signature rdata field */
1390         unsigned int sigblock_len;
1391         uint16_t ktag;          /* DNSKEY key tag */
1392         unsigned char* key;     /* public key rdata field */
1393         unsigned int keylen;
1394         rrset_get_rdata(rrset, rrnum + sig_idx, &sig, &siglen);
1395         /* min length of rdatalen, fixed rrsig, root signer, 1 byte sig */
1396         if(siglen < 2+20) {
1397                 verbose(VERB_QUERY, "verify: signature too short");
1398                 *reason = "signature too short";
1399                 return sec_status_bogus;
1400         }
1401
1402         if(!(dnskey_get_flags(dnskey, dnskey_idx) & DNSKEY_BIT_ZSK)) {
1403                 verbose(VERB_QUERY, "verify: dnskey without ZSK flag");
1404                 *reason = "dnskey without ZSK flag";
1405                 return sec_status_bogus;
1406         }
1407
1408         if(dnskey_get_protocol(dnskey, dnskey_idx) != LDNS_DNSSEC_KEYPROTO) {
1409                 /* RFC 4034 says DNSKEY PROTOCOL MUST be 3 */
1410                 verbose(VERB_QUERY, "verify: dnskey has wrong key protocol");
1411                 *reason = "dnskey has wrong protocolnumber";
1412                 return sec_status_bogus;
1413         }
1414
1415         /* verify as many fields in rrsig as possible */
1416         signer = sig+2+18;
1417         signer_len = dname_valid(signer, siglen-2-18);
1418         if(!signer_len) {
1419                 verbose(VERB_QUERY, "verify: malformed signer name");
1420                 *reason = "signer name malformed";
1421                 return sec_status_bogus; /* signer name invalid */
1422         }
1423         if(!dname_subdomain_c(rrset->rk.dname, signer)) {
1424                 verbose(VERB_QUERY, "verify: signer name is off-tree");
1425                 *reason = "signer name off-tree";
1426                 return sec_status_bogus; /* signer name offtree */
1427         }
1428         sigblock = (unsigned char*)signer+signer_len;
1429         if(siglen < 2+18+signer_len+1) {
1430                 verbose(VERB_QUERY, "verify: too short, no signature data");
1431                 *reason = "signature too short, no signature data";
1432                 return sec_status_bogus; /* sig rdf is < 1 byte */
1433         }
1434         sigblock_len = (unsigned int)(siglen - 2 - 18 - signer_len);
1435
1436         /* verify key dname == sig signer name */
1437         if(query_dname_compare(signer, dnskey->rk.dname) != 0) {
1438                 verbose(VERB_QUERY, "verify: wrong key for rrsig");
1439                 log_nametypeclass(VERB_QUERY, "RRSIG signername is",
1440                         signer, 0, 0);
1441                 log_nametypeclass(VERB_QUERY, "the key name is",
1442                         dnskey->rk.dname, 0, 0);
1443                 *reason = "signer name mismatches key name";
1444                 return sec_status_bogus;
1445         }
1446
1447         /* verify covered type */
1448         /* memcmp works because type is in network format for rrset */
1449         if(memcmp(sig+2, &rrset->rk.type, 2) != 0) {
1450                 verbose(VERB_QUERY, "verify: wrong type covered");
1451                 *reason = "signature covers wrong type";
1452                 return sec_status_bogus;
1453         }
1454         /* verify keytag and sig algo (possibly again) */
1455         if((int)sig[2+2] != dnskey_get_algo(dnskey, dnskey_idx)) {
1456                 verbose(VERB_QUERY, "verify: wrong algorithm");
1457                 *reason = "signature has wrong algorithm";
1458                 return sec_status_bogus;
1459         }
1460         ktag = htons(dnskey_calc_keytag(dnskey, dnskey_idx));
1461         if(memcmp(sig+2+16, &ktag, 2) != 0) {
1462                 verbose(VERB_QUERY, "verify: wrong keytag");
1463                 *reason = "signature has wrong keytag";
1464                 return sec_status_bogus;
1465         }
1466
1467         /* verify labels is in a valid range */
1468         if((int)sig[2+3] > dname_signame_label_count(rrset->rk.dname)) {
1469                 verbose(VERB_QUERY, "verify: labelcount out of range");
1470                 *reason = "signature labelcount out of range";
1471                 return sec_status_bogus;
1472         }
1473
1474         /* original ttl, always ok */
1475
1476         if(!*buf_canon) {
1477                 /* create rrset canonical format in buffer, ready for
1478                  * signature */
1479                 if(!rrset_canonical(region, buf, rrset, sig+2,
1480                         18 + signer_len, sortree, section, qstate)) {
1481                         log_err("verify: failed due to alloc error");
1482                         return sec_status_unchecked;
1483                 }
1484                 *buf_canon = 1;
1485         }
1486
1487         /* check that dnskey is available */
1488         dnskey_get_pubkey(dnskey, dnskey_idx, &key, &keylen);
1489         if(!key) {
1490                 verbose(VERB_QUERY, "verify: short DNSKEY RR");
1491                 return sec_status_unchecked;
1492         }
1493
1494         /* verify */
1495         sec = verify_canonrrset(buf, (int)sig[2+2],
1496                 sigblock, sigblock_len, key, keylen, reason);
1497
1498         if(sec == sec_status_secure) {
1499                 /* check if TTL is too high - reduce if so */
1500                 adjust_ttl(ve, now, rrset, sig+2+4, sig+2+8, sig+2+12);
1501
1502                 /* verify inception, expiration dates
1503                  * Do this last so that if you ignore expired-sigs the
1504                  * rest is sure to be OK. */
1505                 if(!check_dates(ve, now, sig+2+8, sig+2+12, reason)) {
1506                         return sec_status_bogus;
1507                 }
1508         }
1509
1510         return sec;
1511 }