contrib/ldns/dnssec.c

   1 /*
   2  * dnssec.c
   3  *
   4  * contains the cryptographic function needed for DNSSEC in ldns
   5  * The crypto library used is openssl
   6  *
   7  * (c) NLnet Labs, 2004-2008
   8  *
   9  * See the file LICENSE for the license
  10  */
  11
  12 #include <ldns/config.h>
  13
  14 #include <ldns/ldns.h>
  15 #include <ldns/dnssec.h>
  16
  17 #include <strings.h>
  18 #include <time.h>
  19
  20 #ifdef HAVE_SSL
  21 #include <openssl/ssl.h>
  22 #include <openssl/evp.h>
  23 #include <openssl/rand.h>
  24 #include <openssl/err.h>
  25 #include <openssl/md5.h>
  26 #endif
  27
  28 ldns_rr *
  29 ldns_dnssec_get_rrsig_for_name_and_type(const ldns_rdf *name,
  30                                         const ldns_rr_type type,
  31                                         const ldns_rr_list *rrs)
  32 {
  33         size_t i;
  34         ldns_rr *candidate;
  35
  36         if (!name || !rrs) {
  37                 return NULL;
  38         }
  39
  40         for (i = 0; i < ldns_rr_list_rr_count(rrs); i++) {
  41                 candidate = ldns_rr_list_rr(rrs, i);
  42                 if (ldns_rr_get_type(candidate) == LDNS_RR_TYPE_RRSIG) {
  43                         if (ldns_dname_compare(ldns_rr_owner(candidate),
  44                                                name) == 0 &&
  45                             ldns_rdf2native_int8(ldns_rr_rrsig_typecovered(candidate))
  46                             == type
  47                             ) {
  48                                 return candidate;
  49                         }
  50                 }
  51         }
  52
  53         return NULL;
  54 }
  55
  56 ldns_rr *
  57 ldns_dnssec_get_dnskey_for_rrsig(const ldns_rr *rrsig,
  58                                                    const ldns_rr_list *rrs)
  59 {
  60         size_t i;
  61         ldns_rr *candidate;
  62
  63         if (!rrsig || !rrs) {
  64                 return NULL;
  65         }
  66
  67         for (i = 0; i < ldns_rr_list_rr_count(rrs); i++) {
  68                 candidate = ldns_rr_list_rr(rrs, i);
  69                 if (ldns_rr_get_type(candidate) == LDNS_RR_TYPE_DNSKEY) {
  70                         if (ldns_dname_compare(ldns_rr_owner(candidate),
  71                                                ldns_rr_rrsig_signame(rrsig)) == 0 &&
  72                             ldns_rdf2native_int16(ldns_rr_rrsig_keytag(rrsig)) ==
  73                             ldns_calc_keytag(candidate)
  74                             ) {
  75                                 return candidate;
  76                         }
  77                 }
  78         }
  79
  80         return NULL;
  81 }
  82
  83 ldns_rdf *
  84 ldns_nsec_get_bitmap(ldns_rr *nsec) {
  85         if (ldns_rr_get_type(nsec) == LDNS_RR_TYPE_NSEC) {
  86                 return ldns_rr_rdf(nsec, 1);
  87         } else if (ldns_rr_get_type(nsec) == LDNS_RR_TYPE_NSEC3) {
  88                 return ldns_rr_rdf(nsec, 5);
  89         } else {
  90                 return NULL;
  91         }
  92 }
  93
  94 /*return the owner name of the closest encloser for name from the list of rrs */
  95 /* this is NOT the hash, but the original name! */
  96 ldns_rdf *
  97 ldns_dnssec_nsec3_closest_encloser(ldns_rdf *qname,
  98                                    ATTR_UNUSED(ldns_rr_type qtype),
  99                                    ldns_rr_list *nsec3s)
 100 {
 101         /* remember parameters, they must match */
 102         uint8_t algorithm;
 103         uint32_t iterations;
 104         uint8_t salt_length;
 105         uint8_t *salt;
 106
 107         ldns_rdf *sname, *hashed_sname, *tmp;
 108         ldns_rr *ce;
 109         bool flag;
 110
 111         bool exact_match_found;
 112         bool in_range_found;
 113
 114         ldns_status status;
 115         ldns_rdf *zone_name;
 116
 117         size_t nsec_i;
 118         ldns_rr *nsec;
 119         ldns_rdf *result = NULL;
 120         qtype = qtype;
 121
 122         if (!qname || !nsec3s || ldns_rr_list_rr_count(nsec3s) < 1) {
 123                 return NULL;
 124         }
 125
 126         nsec = ldns_rr_list_rr(nsec3s, 0);
 127         algorithm = ldns_nsec3_algorithm(nsec);
 128         salt_length = ldns_nsec3_salt_length(nsec);
 129         salt = ldns_nsec3_salt_data(nsec);
 130         iterations = ldns_nsec3_iterations(nsec);
 131
 132         sname = ldns_rdf_clone(qname);
 133
 134         ce = NULL;
 135         flag = false;
 136
 137         zone_name = ldns_dname_left_chop(ldns_rr_owner(nsec));
 138
 139         /* algorithm from nsec3-07 8.3 */
 140         while (ldns_dname_label_count(sname) > 0) {
 141                 exact_match_found = false;
 142                 in_range_found = false;
 143
 144                 hashed_sname = ldns_nsec3_hash_name(sname,
 145                                                                          algorithm,
 146                                                                          iterations,
 147                                                                          salt_length,
 148                                                                          salt);
 149
 150                 status = ldns_dname_cat(hashed_sname, zone_name);
 151
 152                 for (nsec_i = 0; nsec_i < ldns_rr_list_rr_count(nsec3s); nsec_i++) {
 153                         nsec = ldns_rr_list_rr(nsec3s, nsec_i);
 154
 155                         /* check values of iterations etc! */
 156
 157                         /* exact match? */
 158                         if (ldns_dname_compare(ldns_rr_owner(nsec), hashed_sname) == 0) {
 159                                 exact_match_found = true;
 160                         } else if (ldns_nsec_covers_name(nsec, hashed_sname)) {
 161                                 in_range_found = true;
 162                         }
 163
 164                 }
 165                 if (!exact_match_found && in_range_found) {
 166                         flag = true;
 167                 } else if (exact_match_found && flag) {
 168                         result = ldns_rdf_clone(sname);
 169                         /* RFC 5155: 8.3. 2.** "The proof is complete" */
 170                         ldns_rdf_deep_free(hashed_sname);
 171                         goto done;
 172                 } else if (exact_match_found && !flag) {
 173                         /* error! */
 174                         ldns_rdf_deep_free(hashed_sname);
 175                         goto done;
 176                 } else {
 177                         flag = false;
 178                 }
 179
 180                 ldns_rdf_deep_free(hashed_sname);
 181                 tmp = sname;
 182                 sname = ldns_dname_left_chop(sname);
 183                 ldns_rdf_deep_free(tmp);
 184         }
 185
 186         done:
 187         LDNS_FREE(salt);
 188         ldns_rdf_deep_free(zone_name);
 189         ldns_rdf_deep_free(sname);
 190
 191         return result;
 192 }
 193
 194 bool
 195 ldns_dnssec_pkt_has_rrsigs(const ldns_pkt *pkt)
 196 {
 197         size_t i;
 198         for (i = 0; i < ldns_pkt_ancount(pkt); i++) {
 199                 if (ldns_rr_get_type(ldns_rr_list_rr(ldns_pkt_answer(pkt), i)) ==
 200                     LDNS_RR_TYPE_RRSIG) {
 201                         return true;
 202                 }
 203         }
 204         for (i = 0; i < ldns_pkt_nscount(pkt); i++) {
 205                 if (ldns_rr_get_type(ldns_rr_list_rr(ldns_pkt_authority(pkt), i)) ==
 206                     LDNS_RR_TYPE_RRSIG) {
 207                         return true;
 208                 }
 209         }
 210         return false;
 211 }
 212
 213 ldns_rr_list *
 214 ldns_dnssec_pkt_get_rrsigs_for_name_and_type(const ldns_pkt *pkt,
 215                                                                         ldns_rdf *name,
 216                                                                         ldns_rr_type type)
 217 {
 218         uint16_t t_netorder;
 219         ldns_rr_list *sigs;
 220         ldns_rr_list *sigs_covered;
 221         ldns_rdf *rdf_t;
 222
 223         sigs = ldns_pkt_rr_list_by_name_and_type(pkt,
 224                                                                          name,
 225                                                                          LDNS_RR_TYPE_RRSIG,
 226                                                                          LDNS_SECTION_ANY_NOQUESTION
 227                                                                          );
 228
 229         t_netorder = htons(type); /* rdf are in network order! */
 230         rdf_t = ldns_rdf_new(LDNS_RDF_TYPE_TYPE, LDNS_RDF_SIZE_WORD, &t_netorder);
 231         sigs_covered = ldns_rr_list_subtype_by_rdf(sigs, rdf_t, 0);
 232
 233         ldns_rdf_free(rdf_t);
 234         ldns_rr_list_deep_free(sigs);
 235
 236         return sigs_covered;
 237
 238 }
 239
 240 ldns_rr_list *
 241 ldns_dnssec_pkt_get_rrsigs_for_type(const ldns_pkt *pkt, ldns_rr_type type)
 242 {
 243         uint16_t t_netorder;
 244         ldns_rr_list *sigs;
 245         ldns_rr_list *sigs_covered;
 246         ldns_rdf *rdf_t;
 247
 248         sigs = ldns_pkt_rr_list_by_type(pkt,
 249                                         LDNS_RR_TYPE_RRSIG,
 250                                         LDNS_SECTION_ANY_NOQUESTION
 251                                                           );
 252
 253         t_netorder = htons(type); /* rdf are in network order! */
 254         rdf_t = ldns_rdf_new(LDNS_RDF_TYPE_TYPE,
 255                                          2,
 256                                          &t_netorder);
 257         sigs_covered = ldns_rr_list_subtype_by_rdf(sigs, rdf_t, 0);
 258
 259         ldns_rdf_free(rdf_t);
 260         ldns_rr_list_deep_free(sigs);
 261
 262         return sigs_covered;
 263
 264 }
 265
 266 /* used only on the public key RR */
 267 uint16_t
 268 ldns_calc_keytag(const ldns_rr *key)
 269 {
 270         uint16_t ac16;
 271         ldns_buffer *keybuf;
 272         size_t keysize;
 273
 274         if (!key) {
 275                 return 0;
 276         }
 277
 278         if (ldns_rr_get_type(key) != LDNS_RR_TYPE_DNSKEY &&
 279             ldns_rr_get_type(key) != LDNS_RR_TYPE_KEY
 280             ) {
 281                 return 0;
 282         }
 283
 284         /* rdata to buf - only put the rdata in a buffer */
 285         keybuf = ldns_buffer_new(LDNS_MIN_BUFLEN); /* grows */
 286         if (!keybuf) {
 287                 return 0;
 288         }
 289         (void)ldns_rr_rdata2buffer_wire(keybuf, key);
 290         /* the current pos in the buffer is the keysize */
 291         keysize= ldns_buffer_position(keybuf);
 292
 293         ac16 = ldns_calc_keytag_raw(ldns_buffer_begin(keybuf), keysize);
 294         ldns_buffer_free(keybuf);
 295         return ac16;
 296 }
 297
 298 uint16_t ldns_calc_keytag_raw(uint8_t* key, size_t keysize)
 299 {
 300         unsigned int i;
 301         uint32_t ac32;
 302         uint16_t ac16;
 303
 304         if(keysize < 4) {
 305                 return 0;
 306         }
 307         /* look at the algorithm field, copied from 2535bis */
 308         if (key[3] == LDNS_RSAMD5) {
 309                 ac16 = 0;
 310                 if (keysize > 4) {
 311                         memmove(&ac16, key + keysize - 3, 2);
 312                 }
 313                 ac16 = ntohs(ac16);
 314                 return (uint16_t) ac16;
 315         } else {
 316                 ac32 = 0;
 317                 for (i = 0; (size_t)i < keysize; ++i) {
 318                         ac32 += (i & 1) ? key[i] : key[i] << 8;
 319                 }
 320                 ac32 += (ac32 >> 16) & 0xFFFF;
 321                 return (uint16_t) (ac32 & 0xFFFF);
 322         }
 323 }
 324
 325 #ifdef HAVE_SSL
 326 DSA *
 327 ldns_key_buf2dsa(ldns_buffer *key)
 328 {
 329         return ldns_key_buf2dsa_raw((unsigned char*)ldns_buffer_begin(key),
 330                                                    ldns_buffer_position(key));
 331 }
 332
 333 DSA *
 334 ldns_key_buf2dsa_raw(unsigned char* key, size_t len)
 335 {
 336         uint8_t T;
 337         uint16_t length;
 338         uint16_t offset;
 339         DSA *dsa;
 340         BIGNUM *Q; BIGNUM *P;
 341         BIGNUM *G; BIGNUM *Y;
 342
 343         if(len == 0)
 344                 return NULL;
 345         T = (uint8_t)key[0];
 346         length = (64 + T * 8);
 347         offset = 1;
 348
 349         if (T > 8) {
 350                 return NULL;
 351         }
 352         if(len < (size_t)1 + SHA_DIGEST_LENGTH + 3*length)
 353                 return NULL;
 354
 355         Q = BN_bin2bn(key+offset, SHA_DIGEST_LENGTH, NULL);
 356         offset += SHA_DIGEST_LENGTH;
 357
 358         P = BN_bin2bn(key+offset, (int)length, NULL);
 359         offset += length;
 360
 361         G = BN_bin2bn(key+offset, (int)length, NULL);
 362         offset += length;
 363
 364         Y = BN_bin2bn(key+offset, (int)length, NULL);
 365         offset += length;
 366
 367         /* create the key and set its properties */
 368         if(!Q || !P || !G || !Y || !(dsa = DSA_new())) {
 369                 BN_free(Q);
 370                 BN_free(P);
 371                 BN_free(G);
 372                 BN_free(Y);
 373                 return NULL;
 374         }
 375         dsa->p = P;
 376         dsa->q = Q;
 377         dsa->g = G;
 378         dsa->pub_key = Y;
 379
 380         return dsa;
 381 }
 382
 383 RSA *
 384 ldns_key_buf2rsa(ldns_buffer *key)
 385 {
 386         return ldns_key_buf2rsa_raw((unsigned char*)ldns_buffer_begin(key),
 387                                                    ldns_buffer_position(key));
 388 }
 389
 390 RSA *
 391 ldns_key_buf2rsa_raw(unsigned char* key, size_t len)
 392 {
 393         uint16_t offset;
 394         uint16_t exp;
 395         uint16_t int16;
 396         RSA *rsa;
 397         BIGNUM *modulus;
 398         BIGNUM *exponent;
 399
 400         if (len == 0)
 401                 return NULL;
 402         if (key[0] == 0) {
 403                 if(len < 3)
 404                         return NULL;
 405                 /* need some smart comment here XXX*/
 406                 /* the exponent is too large so it's places
 407                  * futher...???? */
 408                 memmove(&int16, key+1, 2);
 409                 exp = ntohs(int16);
 410                 offset = 3;
 411         } else {
 412                 exp = key[0];
 413                 offset = 1;
 414         }
 415
 416         /* key length at least one */
 417         if(len < (size_t)offset + exp + 1)
 418                 return NULL;
 419
 420         /* Exponent */
 421         exponent = BN_new();
 422         if(!exponent) return NULL;
 423         (void) BN_bin2bn(key+offset, (int)exp, exponent);
 424         offset += exp;
 425
 426         /* Modulus */
 427         modulus = BN_new();
 428         if(!modulus) {
 429                 BN_free(exponent);
 430                 return NULL;
 431         }
 432         /* length of the buffer must match the key length! */
 433         (void) BN_bin2bn(key+offset, (int)(len - offset), modulus);
 434
 435         rsa = RSA_new();
 436         if(!rsa) {
 437                 BN_free(exponent);
 438                 BN_free(modulus);
 439                 return NULL;
 440         }
 441         rsa->n = modulus;
 442         rsa->e = exponent;
 443
 444         return rsa;
 445 }
 446
 447 int
 448 ldns_digest_evp(unsigned char* data, unsigned int len, unsigned char* dest,
 449         const EVP_MD* md)
 450 {
 451         EVP_MD_CTX* ctx;
 452         ctx = EVP_MD_CTX_create();
 453         if(!ctx)
 454                 return false;
 455         if(!EVP_DigestInit_ex(ctx, md, NULL) ||
 456                 !EVP_DigestUpdate(ctx, data, len) ||
 457                 !EVP_DigestFinal_ex(ctx, dest, NULL)) {
 458                 EVP_MD_CTX_destroy(ctx);
 459                 return false;
 460         }
 461         EVP_MD_CTX_destroy(ctx);
 462         return true;
 463 }
 464 #endif /* HAVE_SSL */
 465
 466 ldns_rr *
 467 ldns_key_rr2ds(const ldns_rr *key, ldns_hash h)
 468 {
 469         ldns_rdf *tmp;
 470         ldns_rr *ds;
 471         uint16_t keytag;
 472         uint8_t  sha1hash;
 473         uint8_t *digest;
 474         ldns_buffer *data_buf;
 475 #ifdef USE_GOST
 476         const EVP_MD* md = NULL;
 477 #endif
 478
 479         if (ldns_rr_get_type(key) != LDNS_RR_TYPE_DNSKEY) {
 480                 return NULL;
 481         }
 482
 483         ds = ldns_rr_new();
 484         if (!ds) {
 485                 return NULL;
 486         }
 487         ldns_rr_set_type(ds, LDNS_RR_TYPE_DS);
 488         ldns_rr_set_owner(ds, ldns_rdf_clone(
 489                                                                   ldns_rr_owner(key)));
 490         ldns_rr_set_ttl(ds, ldns_rr_ttl(key));
 491         ldns_rr_set_class(ds, ldns_rr_get_class(key));
 492
 493         switch(h) {
 494         default:
 495         case LDNS_SHA1:
 496                 digest = LDNS_XMALLOC(uint8_t, LDNS_SHA1_DIGEST_LENGTH);
 497                 if (!digest) {
 498                         ldns_rr_free(ds);
 499                         return NULL;
 500                 }
 501                 break;
 502         case LDNS_SHA256:
 503                 digest = LDNS_XMALLOC(uint8_t, LDNS_SHA256_DIGEST_LENGTH);
 504                 if (!digest) {
 505                         ldns_rr_free(ds);
 506                         return NULL;
 507                 }
 508                 break;
 509         case LDNS_HASH_GOST94:
 510 #ifdef USE_GOST
 511                 (void)ldns_key_EVP_load_gost_id();
 512                 md = EVP_get_digestbyname("md_gost94");
 513                 if(!md) {
 514                         ldns_rr_free(ds);
 515                         return NULL;
 516                 }
 517                 digest = LDNS_XMALLOC(uint8_t, EVP_MD_size(md));
 518                 if (!digest) {
 519                         ldns_rr_free(ds);
 520                         return NULL;
 521                 }
 522 #else
 523                 /* not implemented */
 524                 ldns_rr_free(ds);
 525                 return NULL;
 526 #endif
 527                 break;
 528         }
 529
 530         data_buf = ldns_buffer_new(LDNS_MAX_PACKETLEN);
 531         if (!data_buf) {
 532                 LDNS_FREE(digest);
 533                 ldns_rr_free(ds);
 534                 return NULL;
 535         }
 536
 537         /* keytag */
 538         keytag = htons(ldns_calc_keytag((ldns_rr*)key));
 539         tmp = ldns_rdf_new_frm_data(LDNS_RDF_TYPE_INT16,
 540                                                    sizeof(uint16_t),
 541                                                    &keytag);
 542         ldns_rr_push_rdf(ds, tmp);
 543
 544         /* copy the algorithm field */
 545         ldns_rr_push_rdf(ds, ldns_rdf_clone( ldns_rr_rdf(key, 2)));
 546
 547         /* digest hash type */
 548         sha1hash = (uint8_t)h;
 549         tmp = ldns_rdf_new_frm_data(LDNS_RDF_TYPE_INT8,
 550                                                    sizeof(uint8_t),
 551                                                    &sha1hash);
 552         ldns_rr_push_rdf(ds, tmp);
 553
 554         /* digest */
 555         /* owner name */
 556         tmp = ldns_rdf_clone(ldns_rr_owner(key));
 557         ldns_dname2canonical(tmp);
 558         if (ldns_rdf2buffer_wire(data_buf, tmp) != LDNS_STATUS_OK) {
 559                 LDNS_FREE(digest);
 560                 ldns_buffer_free(data_buf);
 561                 ldns_rr_free(ds);
 562                 ldns_rdf_deep_free(tmp);
 563                 return NULL;
 564         }
 565         ldns_rdf_deep_free(tmp);
 566
 567         /* all the rdata's */
 568         if (ldns_rr_rdata2buffer_wire(data_buf,
 569                                                         (ldns_rr*)key) != LDNS_STATUS_OK) {
 570                 LDNS_FREE(digest);
 571                 ldns_buffer_free(data_buf);
 572                 ldns_rr_free(ds);
 573                 return NULL;
 574         }
 575         switch(h) {
 576         case LDNS_SHA1:
 577                 (void) ldns_sha1((unsigned char *) ldns_buffer_begin(data_buf),
 578                                  (unsigned int) ldns_buffer_position(data_buf),
 579                                  (unsigned char *) digest);
 580
 581                 tmp = ldns_rdf_new_frm_data(LDNS_RDF_TYPE_HEX,
 582                                             LDNS_SHA1_DIGEST_LENGTH,
 583                                             digest);
 584                 ldns_rr_push_rdf(ds, tmp);
 585
 586                 break;
 587         case LDNS_SHA256:
 588                 (void) ldns_sha256((unsigned char *) ldns_buffer_begin(data_buf),
 589                                    (unsigned int) ldns_buffer_position(data_buf),
 590                                    (unsigned char *) digest);
 591                 tmp = ldns_rdf_new_frm_data(LDNS_RDF_TYPE_HEX,
 592                                             LDNS_SHA256_DIGEST_LENGTH,
 593                                             digest);
 594                 ldns_rr_push_rdf(ds, tmp);
 595                 break;
 596         case LDNS_HASH_GOST94:
 597 #ifdef USE_GOST
 598                 if(!ldns_digest_evp((unsigned char *) ldns_buffer_begin(data_buf),
 599                                 (unsigned int) ldns_buffer_position(data_buf),
 600                                 (unsigned char *) digest, md)) {
 601                         LDNS_FREE(digest);
 602                         ldns_buffer_free(data_buf);
 603                         ldns_rr_free(ds);
 604                         return NULL;
 605                 }
 606                 tmp = ldns_rdf_new_frm_data(LDNS_RDF_TYPE_HEX,
 607                                             EVP_MD_size(md),
 608                                             digest);
 609                 ldns_rr_push_rdf(ds, tmp);
 610 #endif
 611                 break;
 612         }
 613
 614         LDNS_FREE(digest);
 615         ldns_buffer_free(data_buf);
 616         return ds;
 617 }
 618
 619 ldns_rdf *
 620 ldns_dnssec_create_nsec_bitmap(ldns_rr_type rr_type_list[],
 621                                size_t size,
 622                                ldns_rr_type nsec_type)
 623 {
 624         size_t i;
 625         uint8_t *bitmap;
 626         uint16_t bm_len = 0;
 627         uint16_t i_type;
 628         ldns_rdf *bitmap_rdf;
 629
 630         uint8_t *data = NULL;
 631         uint8_t cur_data[32];
 632         uint8_t cur_window = 0;
 633         uint8_t cur_window_max = 0;
 634         uint16_t cur_data_size = 0;
 635
 636         if (nsec_type != LDNS_RR_TYPE_NSEC &&
 637             nsec_type != LDNS_RR_TYPE_NSEC3) {
 638                 return NULL;
 639         }
 640
 641         i_type = 0;
 642         for (i = 0; i < size; i++) {
 643                 if (i_type < rr_type_list[i])
 644                         i_type = rr_type_list[i];
 645         }
 646         if (i_type < nsec_type) {
 647                 i_type = nsec_type;
 648         }
 649
 650         bm_len = i_type / 8 + 2;
 651         bitmap = LDNS_XMALLOC(uint8_t, bm_len);
 652         for (i = 0; i < bm_len; i++) {
 653                 bitmap[i] = 0;
 654         }
 655
 656         for (i = 0; i < size; i++) {
 657                 i_type = rr_type_list[i];
 658                 ldns_set_bit(bitmap + (int) i_type / 8,
 659                                    (int) (7 - (i_type % 8)),
 660                                    true);
 661         }
 662
 663         /* fold it into windows TODO: can this be done directly? */
 664         memset(cur_data, 0, 32);
 665         for (i = 0; i < bm_len; i++) {
 666                 if (i / 32 > cur_window) {
 667                         /* check, copy, new */
 668                         if (cur_window_max > 0) {
 669                                 /* this window has stuff, add it */
 670                                 data = LDNS_XREALLOC(data,
 671                                                                  uint8_t,
 672                                                                  cur_data_size + cur_window_max + 3);
 673                                 data[cur_data_size] = cur_window;
 674                                 data[cur_data_size + 1] = cur_window_max + 1;
 675                                 memcpy(data + cur_data_size + 2,
 676                                           cur_data,
 677                                           cur_window_max+1);
 678                                 cur_data_size += cur_window_max + 3;
 679                         }
 680                         cur_window++;
 681                         cur_window_max = 0;
 682                         memset(cur_data, 0, 32);
 683                 }
 684                 cur_data[i%32] = bitmap[i];
 685                 if (bitmap[i] > 0) {
 686                         cur_window_max = i%32;
 687                 }
 688         }
 689         if (cur_window_max > 0 || cur_data[0] != 0) {
 690                 /* this window has stuff, add it */
 691                 data = LDNS_XREALLOC(data,
 692                                                  uint8_t,
 693                                                  cur_data_size + cur_window_max + 3);
 694                 data[cur_data_size] = cur_window;
 695                 data[cur_data_size + 1] = cur_window_max + 1;
 696                 memcpy(data + cur_data_size + 2, cur_data, cur_window_max+1);
 697                 cur_data_size += cur_window_max + 3;
 698         }
 699
 700         bitmap_rdf = ldns_rdf_new_frm_data(LDNS_RDF_TYPE_NSEC,
 701                                                                 cur_data_size,
 702                                                                 data);
 703
 704         LDNS_FREE(bitmap);
 705         LDNS_FREE(data);
 706
 707         return bitmap_rdf;
 708 }
 709
 710 int
 711 ldns_dnssec_rrsets_contains_type(ldns_dnssec_rrsets *rrsets,
 712                                  ldns_rr_type type)
 713 {
 714         ldns_dnssec_rrsets *cur_rrset = rrsets;
 715         while (cur_rrset) {
 716                 if (cur_rrset->type == type) {
 717                         return 1;
 718                 }
 719                 cur_rrset = cur_rrset->next;
 720         }
 721         return 0;
 722 }
 723
 724 /* returns true if the current dnssec_rrset from the given list of rrsets
 725  * is glue */
 726 static int
 727 is_glue(ldns_dnssec_rrsets *cur_rrsets, ldns_dnssec_rrsets *orig_rrsets)
 728 {
 729         /* only glue if a or aaaa if there are no ns, unless there is soa */
 730         return (cur_rrsets->type == LDNS_RR_TYPE_A ||
 731                 cur_rrsets->type ==  LDNS_RR_TYPE_AAAA) &&
 732                 (ldns_dnssec_rrsets_contains_type(orig_rrsets,
 733                       LDNS_RR_TYPE_NS) &&
 734                 !ldns_dnssec_rrsets_contains_type(orig_rrsets,
 735                       LDNS_RR_TYPE_SOA));
 736 }
 737
 738 ldns_rr *
 739 ldns_dnssec_create_nsec(ldns_dnssec_name *from,
 740                         ldns_dnssec_name *to,
 741                         ldns_rr_type nsec_type)
 742 {
 743         ldns_rr *nsec_rr;
 744         ldns_rr_type types[65535];
 745         size_t type_count = 0;
 746         ldns_dnssec_rrsets *cur_rrsets;
 747
 748         if (!from || !to || (nsec_type != LDNS_RR_TYPE_NSEC &&
 749                                          nsec_type != LDNS_RR_TYPE_NSEC3)) {
 750                 return NULL;
 751         }
 752
 753         nsec_rr = ldns_rr_new();
 754         ldns_rr_set_type(nsec_rr, nsec_type);
 755         ldns_rr_set_owner(nsec_rr, ldns_rdf_clone(ldns_dnssec_name_name(from)));
 756         ldns_rr_push_rdf(nsec_rr, ldns_rdf_clone(ldns_dnssec_name_name(to)));
 757
 758         cur_rrsets = from->rrsets;
 759         while (cur_rrsets) {
 760                 if (is_glue(cur_rrsets, from->rrsets)) {
 761                         cur_rrsets = cur_rrsets->next;
 762                         continue;
 763                 }
 764                 types[type_count] = cur_rrsets->type;
 765                 type_count++;
 766                 cur_rrsets = cur_rrsets->next;
 767         }
 768         types[type_count] = LDNS_RR_TYPE_RRSIG;
 769         type_count++;
 770         types[type_count] = LDNS_RR_TYPE_NSEC;
 771         type_count++;
 772
 773         ldns_rr_push_rdf(nsec_rr, ldns_dnssec_create_nsec_bitmap(types,
 774                                        type_count,
 775                                        nsec_type));
 776
 777         return nsec_rr;
 778 }
 779
 780 ldns_rr *
 781 ldns_dnssec_create_nsec3(ldns_dnssec_name *from,
 782                                         ldns_dnssec_name *to,
 783                                         ldns_rdf *zone_name,
 784                                         uint8_t algorithm,
 785                                         uint8_t flags,
 786                                         uint16_t iterations,
 787                                         uint8_t salt_length,
 788                                         uint8_t *salt)
 789 {
 790         ldns_rr *nsec_rr;
 791         ldns_rr_type types[65535];
 792         size_t type_count = 0;
 793         ldns_dnssec_rrsets *cur_rrsets;
 794         ldns_status status;
 795
 796         flags = flags;
 797
 798         if (!from) {
 799                 return NULL;
 800         }
 801
 802         nsec_rr = ldns_rr_new_frm_type(LDNS_RR_TYPE_NSEC3);
 803         ldns_rr_set_owner(nsec_rr,
 804                           ldns_nsec3_hash_name(ldns_dnssec_name_name(from),
 805                           algorithm,
 806                           iterations,
 807                           salt_length,
 808                           salt));
 809         status = ldns_dname_cat(ldns_rr_owner(nsec_rr), zone_name);
 810         ldns_nsec3_add_param_rdfs(nsec_rr,
 811                                   algorithm,
 812                                   flags,
 813                                   iterations,
 814                                   salt_length,
 815                                   salt);
 816
 817         cur_rrsets = from->rrsets;
 818         while (cur_rrsets) {
 819                 if (is_glue(cur_rrsets, from->rrsets)) {
 820                         cur_rrsets = cur_rrsets->next;
 821                         continue;
 822                 }
 823                 types[type_count] = cur_rrsets->type;
 824                 type_count++;
 825                 cur_rrsets = cur_rrsets->next;
 826         }
 827         /* always add rrsig type if this is not an unsigned
 828          * delegation
 829          */
 830         if (type_count > 0 &&
 831             !(type_count == 1 && types[0] == LDNS_RR_TYPE_NS)) {
 832                 types[type_count] = LDNS_RR_TYPE_RRSIG;
 833                 type_count++;
 834         }
 835
 836         /* leave next rdata empty if they weren't precomputed yet */
 837         if (to && to->hashed_name) {
 838                 (void) ldns_rr_set_rdf(nsec_rr,
 839                                        ldns_rdf_clone(to->hashed_name),
 840                                        4);
 841         } else {
 842                 (void) ldns_rr_set_rdf(nsec_rr, NULL, 4);
 843         }
 844
 845         ldns_rr_push_rdf(nsec_rr,
 846                          ldns_dnssec_create_nsec_bitmap(types,
 847                          type_count,
 848                          LDNS_RR_TYPE_NSEC3));
 849
 850         return nsec_rr;
 851 }
 852
 853 ldns_rr *
 854 ldns_create_nsec(ldns_rdf *cur_owner, ldns_rdf *next_owner, ldns_rr_list *rrs)
 855 {
 856         /* we do not do any check here - garbage in, garbage out */
 857
 858         /* the the start and end names - get the type from the
 859          * before rrlist */
 860
 861         /* inefficient, just give it a name, a next name, and a list of rrs */
 862         /* we make 1 big uberbitmap first, then windows */
 863         /* todo: make something more efficient :) */
 864         uint16_t i;
 865         ldns_rr *i_rr;
 866         uint16_t i_type;
 867
 868         ldns_rr *nsec = NULL;
 869     ldns_rr_type i_type_list[65535];
 870         int type_count = 0;
 871
 872         nsec = ldns_rr_new();
 873         ldns_rr_set_type(nsec, LDNS_RR_TYPE_NSEC);
 874         ldns_rr_set_owner(nsec, ldns_rdf_clone(cur_owner));
 875         ldns_rr_push_rdf(nsec, ldns_rdf_clone(next_owner));
 876
 877         for (i = 0; i < ldns_rr_list_rr_count(rrs); i++) {
 878                 i_rr = ldns_rr_list_rr(rrs, i);
 879                 if (ldns_rdf_compare(cur_owner,
 880                                                  ldns_rr_owner(i_rr)) == 0) {
 881                         i_type = ldns_rr_get_type(i_rr);
 882                         if (type_count == 0 || i_type_list[type_count-1] != i_type) {
 883                                 i_type_list[type_count] = i_type;
 884                                 type_count++;
 885                         }
 886                 }
 887         }
 888
 889         i_type_list[type_count] = LDNS_RR_TYPE_RRSIG;
 890         type_count++;
 891         i_type_list[type_count] = LDNS_RR_TYPE_NSEC;
 892         type_count++;
 893
 894         ldns_rr_push_rdf(nsec,
 895                                   ldns_dnssec_create_nsec_bitmap(i_type_list,
 896                                                 type_count, LDNS_RR_TYPE_NSEC));
 897
 898         return nsec;
 899 }
 900
 901 ldns_rdf *
 902 ldns_nsec3_hash_name(ldns_rdf *name,
 903                                  uint8_t algorithm,
 904                                  uint16_t iterations,
 905                                  uint8_t salt_length,
 906                                  uint8_t *salt)
 907 {
 908         size_t hashed_owner_str_len;
 909         ldns_rdf *cann;
 910         ldns_rdf *hashed_owner;
 911         unsigned char *hashed_owner_str;
 912         char *hashed_owner_b32;
 913         size_t hashed_owner_b32_len;
 914         uint32_t cur_it;
 915         /* define to contain the largest possible hash, which is
 916          * sha1 at the moment */
 917         unsigned char hash[LDNS_SHA1_DIGEST_LENGTH];
 918         ldns_status status;
 919
 920         /* prepare the owner name according to the draft section bla */
 921         cann = ldns_rdf_clone(name);
 922         if(!cann) {
 923                 fprintf(stderr, "Memory error\n");
 924                 return NULL;
 925         }
 926         ldns_dname2canonical(cann);
 927
 928         /* TODO: mnemonic list for hash algs SHA-1, default to 1 now (sha1) */
 929         algorithm = algorithm;
 930
 931         hashed_owner_str_len = salt_length + ldns_rdf_size(cann);
 932         hashed_owner_str = LDNS_XMALLOC(unsigned char, hashed_owner_str_len);
 933         memcpy(hashed_owner_str, ldns_rdf_data(cann), ldns_rdf_size(cann));
 934         memcpy(hashed_owner_str + ldns_rdf_size(cann), salt, salt_length);
 935         ldns_rdf_deep_free(cann);
 936
 937         for (cur_it = iterations + 1; cur_it > 0; cur_it--) {
 938                 (void) ldns_sha1((unsigned char *) hashed_owner_str,
 939                                  (unsigned int) hashed_owner_str_len, hash);
 940
 941                 LDNS_FREE(hashed_owner_str);
 942                 hashed_owner_str_len = salt_length + LDNS_SHA1_DIGEST_LENGTH;
 943                 hashed_owner_str = LDNS_XMALLOC(unsigned char, hashed_owner_str_len);
 944                 if (!hashed_owner_str) {
 945                         fprintf(stderr, "Memory error\n");
 946                         return NULL;
 947                 }
 948                 memcpy(hashed_owner_str, hash, LDNS_SHA1_DIGEST_LENGTH);
 949                 memcpy(hashed_owner_str + LDNS_SHA1_DIGEST_LENGTH, salt, salt_length);
 950                 hashed_owner_str_len = LDNS_SHA1_DIGEST_LENGTH + salt_length;
 951         }
 952
 953         LDNS_FREE(hashed_owner_str);
 954         hashed_owner_str = hash;
 955         hashed_owner_str_len = LDNS_SHA1_DIGEST_LENGTH;
 956
 957         hashed_owner_b32 = LDNS_XMALLOC(char,
 958                   ldns_b32_ntop_calculate_size(hashed_owner_str_len) + 1);
 959         hashed_owner_b32_len = (size_t) ldns_b32_ntop_extended_hex(
 960                 (uint8_t *) hashed_owner_str,
 961                 hashed_owner_str_len,
 962                 hashed_owner_b32,
 963                 ldns_b32_ntop_calculate_size(hashed_owner_str_len));
 964         if (hashed_owner_b32_len < 1) {
 965                 fprintf(stderr, "Error in base32 extended hex encoding ");
 966                 fprintf(stderr, "of hashed owner name (name: ");
 967                 ldns_rdf_print(stderr, name);
 968                 fprintf(stderr, ", return code: %u)\n",
 969                         (unsigned int) hashed_owner_b32_len);
 970                 LDNS_FREE(hashed_owner_b32);
 971                 return NULL;
 972         }
 973         hashed_owner_str_len = hashed_owner_b32_len;
 974         hashed_owner_b32[hashed_owner_b32_len] = '\0';
 975
 976         status = ldns_str2rdf_dname(&hashed_owner, hashed_owner_b32);
 977         if (status != LDNS_STATUS_OK) {
 978                 fprintf(stderr, "Error creating rdf from %s\n", hashed_owner_b32);
 979                 LDNS_FREE(hashed_owner_b32);
 980                 return NULL;
 981         }
 982
 983         LDNS_FREE(hashed_owner_b32);
 984         return hashed_owner;
 985 }
 986
 987 void
 988 ldns_nsec3_add_param_rdfs(ldns_rr *rr,
 989                                          uint8_t algorithm,
 990                                          uint8_t flags,
 991                                          uint16_t iterations,
 992                                          uint8_t salt_length,
 993                                          uint8_t *salt)
 994 {
 995         ldns_rdf *salt_rdf = NULL;
 996         uint8_t *salt_data = NULL;
 997         ldns_rdf *old;
 998
 999         old = ldns_rr_set_rdf(rr,
1000                               ldns_rdf_new_frm_data(LDNS_RDF_TYPE_INT8,
1001                                                     1, (void*)&algorithm),
1002                               0);
1003         if (old) ldns_rdf_deep_free(old);
1004
1005         old = ldns_rr_set_rdf(rr,
1006                               ldns_rdf_new_frm_data(LDNS_RDF_TYPE_INT8,
1007                                                     1, (void*)&flags),
1008                               1);
1009         if (old) ldns_rdf_deep_free(old);
1010
1011         old = ldns_rr_set_rdf(rr,
1012                           ldns_native2rdf_int16(LDNS_RDF_TYPE_INT16,
1013                                                 iterations),
1014                               2);
1015         if (old) ldns_rdf_deep_free(old);
1016
1017         salt_data = LDNS_XMALLOC(uint8_t, salt_length + 1);
1018         salt_data[0] = salt_length;
1019         memcpy(salt_data + 1, salt, salt_length);
1020         salt_rdf = ldns_rdf_new_frm_data(LDNS_RDF_TYPE_NSEC3_SALT,
1021                                                            salt_length + 1,
1022                                                            salt_data);
1023
1024         old = ldns_rr_set_rdf(rr, salt_rdf, 3);
1025         if (old) ldns_rdf_deep_free(old);
1026         LDNS_FREE(salt_data);
1027 }
1028
1029 static int
1030 rr_list_delegation_only(ldns_rdf *origin, ldns_rr_list *rr_list)
1031 {
1032         size_t i;
1033         ldns_rr *cur_rr;
1034         if (!origin || !rr_list) return 0;
1035         for (i = 0; i < ldns_rr_list_rr_count(rr_list); i++) {
1036                 cur_rr = ldns_rr_list_rr(rr_list, i);
1037                 if (ldns_dname_compare(ldns_rr_owner(cur_rr), origin) == 0) {
1038                         return 0;
1039                 }
1040                 if (ldns_rr_get_type(cur_rr) != LDNS_RR_TYPE_NS) {
1041                         return 0;
1042                 }
1043         }
1044         return 1;
1045 }
1046
1047 /* this will NOT return the NSEC3  completed, you will have to run the
1048    finalize function on the rrlist later! */
1049 ldns_rr *
1050 ldns_create_nsec3(ldns_rdf *cur_owner,
1051                   ldns_rdf *cur_zone,
1052                   ldns_rr_list *rrs,
1053                   uint8_t algorithm,
1054                   uint8_t flags,
1055                   uint16_t iterations,
1056                   uint8_t salt_length,
1057                   uint8_t *salt,
1058                   bool emptynonterminal)
1059 {
1060         size_t i;
1061         ldns_rr *i_rr;
1062         uint16_t i_type;
1063
1064         ldns_rr *nsec = NULL;
1065         ldns_rdf *hashed_owner = NULL;
1066
1067         ldns_status status;
1068
1069     ldns_rr_type i_type_list[1024];
1070         int type_count = 0;
1071
1072         hashed_owner = ldns_nsec3_hash_name(cur_owner,
1073                                                                  algorithm,
1074                                                                  iterations,
1075                                                                  salt_length,
1076                                                                  salt);
1077         status = ldns_dname_cat(hashed_owner, cur_zone);
1078
1079         nsec = ldns_rr_new_frm_type(LDNS_RR_TYPE_NSEC3);
1080         ldns_rr_set_type(nsec, LDNS_RR_TYPE_NSEC3);
1081         ldns_rr_set_owner(nsec, hashed_owner);
1082
1083         ldns_nsec3_add_param_rdfs(nsec,
1084                                                  algorithm,
1085                                                  flags,
1086                                                  iterations,
1087                                                  salt_length,
1088                                                  salt);
1089         (void) ldns_rr_set_rdf(nsec, NULL, 4);
1090
1091
1092         for (i = 0; i < ldns_rr_list_rr_count(rrs); i++) {
1093                 i_rr = ldns_rr_list_rr(rrs, i);
1094                 if (ldns_rdf_compare(cur_owner,
1095                                                  ldns_rr_owner(i_rr)) == 0) {
1096                         i_type = ldns_rr_get_type(i_rr);
1097                         if (type_count == 0 || i_type_list[type_count-1] != i_type) {
1098                                 i_type_list[type_count] = i_type;
1099                                 type_count++;
1100                         }
1101                 }
1102         }
1103
1104         /* add RRSIG anyway, but only if this is not an ENT or
1105          * an unsigned delegation */
1106         if (!emptynonterminal && !rr_list_delegation_only(cur_zone, rrs)) {
1107                 i_type_list[type_count] = LDNS_RR_TYPE_RRSIG;
1108                 type_count++;
1109         }
1110
1111         /* and SOA if owner == zone */
1112         if (ldns_dname_compare(cur_zone, cur_owner) == 0) {
1113                 i_type_list[type_count] = LDNS_RR_TYPE_SOA;
1114                 type_count++;
1115         }
1116
1117         ldns_rr_push_rdf(nsec,
1118                                   ldns_dnssec_create_nsec_bitmap(i_type_list,
1119                                                 type_count, LDNS_RR_TYPE_NSEC3));
1120
1121         return nsec;
1122 }
1123
1124 uint8_t
1125 ldns_nsec3_algorithm(const ldns_rr *nsec3_rr)
1126 {
1127         if (nsec3_rr && ldns_rr_get_type(nsec3_rr) == LDNS_RR_TYPE_NSEC3 &&
1128             ldns_rdf_size(ldns_rr_rdf(nsec3_rr, 0)) > 0
1129             ) {
1130                 return ldns_rdf2native_int8(ldns_rr_rdf(nsec3_rr, 0));
1131         }
1132         return 0;
1133 }
1134
1135 uint8_t
1136 ldns_nsec3_flags(const ldns_rr *nsec3_rr)
1137 {
1138         if (nsec3_rr && ldns_rr_get_type(nsec3_rr) == LDNS_RR_TYPE_NSEC3 &&
1139             ldns_rdf_size(ldns_rr_rdf(nsec3_rr, 1)) > 0
1140             ) {
1141                 return ldns_rdf2native_int8(ldns_rr_rdf(nsec3_rr, 1));
1142         }
1143         return 0;
1144 }
1145
1146 bool
1147 ldns_nsec3_optout(const ldns_rr *nsec3_rr)
1148 {
1149         return (ldns_nsec3_flags(nsec3_rr) & LDNS_NSEC3_VARS_OPTOUT_MASK);
1150 }
1151
1152 uint16_t
1153 ldns_nsec3_iterations(const ldns_rr *nsec3_rr)
1154 {
1155         if (nsec3_rr && ldns_rr_get_type(nsec3_rr) == LDNS_RR_TYPE_NSEC3 &&
1156             ldns_rdf_size(ldns_rr_rdf(nsec3_rr, 2)) > 0
1157             ) {
1158                 return ldns_rdf2native_int16(ldns_rr_rdf(nsec3_rr, 2));
1159         }
1160         return 0;
1161
1162 }
1163
1164 ldns_rdf *
1165 ldns_nsec3_salt(const ldns_rr *nsec3_rr)
1166 {
1167         if (nsec3_rr && ldns_rr_get_type(nsec3_rr) == LDNS_RR_TYPE_NSEC3) {
1168                 return ldns_rr_rdf(nsec3_rr, 3);
1169         }
1170         return NULL;
1171 }
1172
1173 uint8_t
1174 ldns_nsec3_salt_length(const ldns_rr *nsec3_rr)
1175 {
1176         ldns_rdf *salt_rdf = ldns_nsec3_salt(nsec3_rr);
1177         if (salt_rdf && ldns_rdf_size(salt_rdf) > 0) {
1178                 return (uint8_t) ldns_rdf_data(salt_rdf)[0];
1179         }
1180         return 0;
1181 }
1182
1183 /* allocs data, free with LDNS_FREE() */
1184 uint8_t *
1185 ldns_nsec3_salt_data(const ldns_rr *nsec3_rr)
1186 {
1187         uint8_t salt_length;
1188         uint8_t *salt;
1189
1190         ldns_rdf *salt_rdf = ldns_nsec3_salt(nsec3_rr);
1191         if (salt_rdf && ldns_rdf_size(salt_rdf) > 0) {
1192                 salt_length = ldns_rdf_data(salt_rdf)[0];
1193                 salt = LDNS_XMALLOC(uint8_t, salt_length);
1194                 memcpy(salt, &ldns_rdf_data(salt_rdf)[1], salt_length);
1195                 return salt;
1196         }
1197         return NULL;
1198 }
1199
1200 ldns_rdf *
1201 ldns_nsec3_next_owner(const ldns_rr *nsec3_rr)
1202 {
1203         if (!nsec3_rr || ldns_rr_get_type(nsec3_rr) != LDNS_RR_TYPE_NSEC3) {
1204                 return NULL;
1205         } else {
1206                 return ldns_rr_rdf(nsec3_rr, 4);
1207         }
1208 }
1209
1210 ldns_rdf *
1211 ldns_nsec3_bitmap(const ldns_rr *nsec3_rr)
1212 {
1213         if (!nsec3_rr || ldns_rr_get_type(nsec3_rr) != LDNS_RR_TYPE_NSEC3) {
1214                 return NULL;
1215         } else {
1216                 return ldns_rr_rdf(nsec3_rr, 5);
1217         }
1218 }
1219
1220 ldns_rdf *
1221 ldns_nsec3_hash_name_frm_nsec3(const ldns_rr *nsec, ldns_rdf *name)
1222 {
1223         uint8_t algorithm;
1224         uint16_t iterations;
1225         uint8_t salt_length;
1226         uint8_t *salt = 0;
1227
1228         ldns_rdf *hashed_owner;
1229
1230         algorithm = ldns_nsec3_algorithm(nsec);
1231         salt_length = ldns_nsec3_salt_length(nsec);
1232         salt = ldns_nsec3_salt_data(nsec);
1233         iterations = ldns_nsec3_iterations(nsec);
1234
1235         hashed_owner = ldns_nsec3_hash_name(name,
1236                                                                  algorithm,
1237                                                                  iterations,
1238                                                                  salt_length,
1239                                                                  salt);
1240
1241         LDNS_FREE(salt);
1242         return hashed_owner;
1243 }
1244
1245 bool
1246 ldns_nsec_bitmap_covers_type(const ldns_rdf *nsec_bitmap, ldns_rr_type type)
1247 {
1248         uint8_t window_block_nr;
1249         uint8_t bitmap_length;
1250         uint16_t cur_type;
1251         uint16_t pos = 0;
1252         uint16_t bit_pos;
1253         uint8_t *data = ldns_rdf_data(nsec_bitmap);
1254
1255         while(pos < ldns_rdf_size(nsec_bitmap)) {
1256                 window_block_nr = data[pos];
1257                 bitmap_length = data[pos + 1];
1258                 pos += 2;
1259
1260                 for (bit_pos = 0; bit_pos < (bitmap_length) * 8; bit_pos++) {
1261                         if (ldns_get_bit(&data[pos], bit_pos)) {
1262                                 cur_type = 256 * (uint16_t) window_block_nr + bit_pos;
1263                                 if (cur_type == type) {
1264                                         return true;
1265                                 }
1266                         }
1267                 }
1268
1269                 pos += (uint16_t) bitmap_length;
1270         }
1271         return false;
1272 }
1273
1274 bool
1275 ldns_nsec_covers_name(const ldns_rr *nsec, const ldns_rdf *name)
1276 {
1277         ldns_rdf *nsec_owner = ldns_rr_owner(nsec);
1278         ldns_rdf *hash_next;
1279         char *next_hash_str;
1280         ldns_rdf *nsec_next = NULL;
1281         ldns_status status;
1282         ldns_rdf *chopped_dname;
1283         bool result;
1284
1285         if (ldns_rr_get_type(nsec) == LDNS_RR_TYPE_NSEC) {
1286                 nsec_next = ldns_rdf_clone(ldns_rr_rdf(nsec, 0));
1287         } else if (ldns_rr_get_type(nsec) == LDNS_RR_TYPE_NSEC3) {
1288                 hash_next = ldns_nsec3_next_owner(nsec);
1289                 next_hash_str = ldns_rdf2str(hash_next);
1290                 nsec_next = ldns_dname_new_frm_str(next_hash_str);
1291                 LDNS_FREE(next_hash_str);
1292                 chopped_dname = ldns_dname_left_chop(nsec_owner);
1293                 status = ldns_dname_cat(nsec_next, chopped_dname);
1294                 ldns_rdf_deep_free(chopped_dname);
1295                 if (status != LDNS_STATUS_OK) {
1296                         printf("error catting: %s\n", ldns_get_errorstr_by_id(status));
1297                 }
1298         } else {
1299                 ldns_rdf_deep_free(nsec_next);
1300                 return false;
1301         }
1302
1303         /* in the case of the last nsec */
1304         if(ldns_dname_compare(nsec_owner, nsec_next) > 0) {
1305                 result = (ldns_dname_compare(nsec_owner, name) <= 0 ||
1306                                 ldns_dname_compare(name, nsec_next) < 0);
1307         } else {
1308                 result = (ldns_dname_compare(nsec_owner, name) <= 0 &&
1309                           ldns_dname_compare(name, nsec_next) < 0);
1310         }
1311
1312         ldns_rdf_deep_free(nsec_next);
1313         return result;
1314 }
1315
1316 #ifdef HAVE_SSL
1317 /* sig may be null - if so look in the packet */
1318 ldns_status
1319 ldns_pkt_verify(ldns_pkt *p, ldns_rr_type t, ldns_rdf *o,
1320                          ldns_rr_list *k, ldns_rr_list *s, ldns_rr_list *good_keys)
1321 {
1322         ldns_rr_list *rrset;
1323         ldns_rr_list *sigs;
1324         ldns_rr_list *sigs_covered;
1325         ldns_rdf *rdf_t;
1326         ldns_rr_type t_netorder;
1327
1328         if (!k) {
1329                 return LDNS_STATUS_ERR;
1330                 /* return LDNS_STATUS_CRYPTO_NO_DNSKEY; */
1331         }
1332
1333         if (t == LDNS_RR_TYPE_RRSIG) {
1334                 /* we don't have RRSIG(RRSIG) (yet? ;-) ) */
1335                 return LDNS_STATUS_ERR;
1336         }
1337
1338         if (s) {
1339                 /* if s is not NULL, the sigs are given to use */
1340                 sigs = s;
1341         } else {
1342                 /* otherwise get them from the packet */
1343                 sigs = ldns_pkt_rr_list_by_name_and_type(p, o, LDNS_RR_TYPE_RRSIG,
1344                                                                           LDNS_SECTION_ANY_NOQUESTION);
1345                 if (!sigs) {
1346                         /* no sigs */
1347                         return LDNS_STATUS_ERR;
1348                         /* return LDNS_STATUS_CRYPTO_NO_RRSIG; */
1349                 }
1350         }
1351
1352         /* rrsig are subtyped, so now we need to find the correct
1353          * sigs for the type t
1354          */
1355         t_netorder = htons(t); /* rdf are in network order! */
1356         /* a type identifier is a 16-bit number, so the size is 2 bytes */
1357         rdf_t = ldns_rdf_new(LDNS_RDF_TYPE_TYPE,
1358                                          2,
1359                                          &t_netorder);
1360         sigs_covered = ldns_rr_list_subtype_by_rdf(sigs, rdf_t, 0);
1361
1362         rrset = ldns_pkt_rr_list_by_name_and_type(p,
1363                                                                           o,
1364                                                                           t,
1365                                                                           LDNS_SECTION_ANY_NOQUESTION);
1366
1367         if (!rrset) {
1368                 return LDNS_STATUS_ERR;
1369         }
1370
1371         if (!sigs_covered) {
1372                 return LDNS_STATUS_ERR;
1373         }
1374
1375         return ldns_verify(rrset, sigs, k, good_keys);
1376 }
1377 #endif /* HAVE_SSL */
1378
1379 ldns_status
1380 ldns_dnssec_chain_nsec3_list(ldns_rr_list *nsec3_rrs)
1381 {
1382         size_t i;
1383         char *next_nsec_owner_str;
1384         ldns_rdf *next_nsec_owner_label;
1385         ldns_rdf *next_nsec_rdf;
1386         ldns_status status = LDNS_STATUS_OK;
1387
1388         for (i = 0; i < ldns_rr_list_rr_count(nsec3_rrs); i++) {
1389                 if (i == ldns_rr_list_rr_count(nsec3_rrs) - 1) {
1390                         next_nsec_owner_label =
1391                                 ldns_dname_label(ldns_rr_owner(ldns_rr_list_rr(nsec3_rrs,
1392                                                                                                           0)), 0);
1393                         next_nsec_owner_str = ldns_rdf2str(next_nsec_owner_label);
1394                         if (next_nsec_owner_str[strlen(next_nsec_owner_str) - 1]
1395                             == '.') {
1396                                 next_nsec_owner_str[strlen(next_nsec_owner_str) - 1]
1397                                         = '\0';
1398                         }
1399                         status = ldns_str2rdf_b32_ext(&next_nsec_rdf,
1400                                                                         next_nsec_owner_str);
1401                         if (!ldns_rr_set_rdf(ldns_rr_list_rr(nsec3_rrs, i),
1402                                                          next_nsec_rdf, 4)) {
1403                                 /* todo: error */
1404                         }
1405
1406                         ldns_rdf_deep_free(next_nsec_owner_label);
1407                         LDNS_FREE(next_nsec_owner_str);
1408                 } else {
1409                         next_nsec_owner_label =
1410                                 ldns_dname_label(ldns_rr_owner(ldns_rr_list_rr(nsec3_rrs,
1411                                                                                                           i + 1)),
1412                                                           0);
1413                         next_nsec_owner_str = ldns_rdf2str(next_nsec_owner_label);
1414                         if (next_nsec_owner_str[strlen(next_nsec_owner_str) - 1]
1415                             == '.') {
1416                                 next_nsec_owner_str[strlen(next_nsec_owner_str) - 1]
1417                                         = '\0';
1418                         }
1419                         status = ldns_str2rdf_b32_ext(&next_nsec_rdf,
1420                                                                         next_nsec_owner_str);
1421                         ldns_rdf_deep_free(next_nsec_owner_label);
1422                         LDNS_FREE(next_nsec_owner_str);
1423                         if (!ldns_rr_set_rdf(ldns_rr_list_rr(nsec3_rrs, i),
1424                                                          next_nsec_rdf, 4)) {
1425                                 /* todo: error */
1426                         }
1427                 }
1428         }
1429         return status;
1430 }
1431
1432 int
1433 qsort_rr_compare_nsec3(const void *a, const void *b)
1434 {
1435         const ldns_rr *rr1 = * (const ldns_rr **) a;
1436         const ldns_rr *rr2 = * (const ldns_rr **) b;
1437         if (rr1 == NULL && rr2 == NULL) {
1438                 return 0;
1439         }
1440         if (rr1 == NULL) {
1441                 return -1;
1442         }
1443         if (rr2 == NULL) {
1444                 return 1;
1445         }
1446         return ldns_rdf_compare(ldns_rr_owner(rr1), ldns_rr_owner(rr2));
1447 }
1448
1449 void
1450 ldns_rr_list_sort_nsec3(ldns_rr_list *unsorted)
1451 {
1452         qsort(unsorted->_rrs,
1453               ldns_rr_list_rr_count(unsorted),
1454               sizeof(ldns_rr *),
1455               qsort_rr_compare_nsec3);
1456 }
1457
1458 int
1459 ldns_dnssec_default_add_to_signatures(ldns_rr *sig, void *n)
1460 {
1461         sig = sig;
1462         n = n;
1463         return LDNS_SIGNATURE_LEAVE_ADD_NEW;
1464 }
1465
1466 int
1467 ldns_dnssec_default_leave_signatures(ldns_rr *sig, void *n)
1468 {
1469         sig = sig;
1470         n = n;
1471         return LDNS_SIGNATURE_LEAVE_NO_ADD;
1472 }
1473
1474 int
1475 ldns_dnssec_default_delete_signatures(ldns_rr *sig, void *n)
1476 {
1477         sig = sig;
1478         n = n;
1479         return LDNS_SIGNATURE_REMOVE_NO_ADD;
1480 }
1481
1482 int
1483 ldns_dnssec_default_replace_signatures(ldns_rr *sig, void *n)
1484 {
1485         sig = sig;
1486         n = n;
1487         return LDNS_SIGNATURE_REMOVE_ADD_NEW;
1488 }
1489
1490 #ifdef HAVE_SSL
1491 ldns_rdf *
1492 ldns_convert_dsa_rrsig_asn12rdf(const ldns_buffer *sig,
1493                                                   const long sig_len)
1494 {
1495         ldns_rdf *sigdata_rdf;
1496         DSA_SIG *dsasig;
1497         unsigned char *dsasig_data = (unsigned char*)ldns_buffer_begin(sig);
1498         size_t byte_offset;
1499
1500         dsasig = d2i_DSA_SIG(NULL,
1501                                          (const unsigned char **)&dsasig_data,
1502                                          sig_len);
1503         if (!dsasig) {
1504                 return NULL;
1505         }
1506
1507         dsasig_data = LDNS_XMALLOC(unsigned char, 41);
1508         dsasig_data[0] = 0;
1509         byte_offset = (size_t) (20 - BN_num_bytes(dsasig->r));
1510         if (byte_offset > 20) {
1511                 return NULL;
1512         }
1513         memset(&dsasig_data[1], 0, byte_offset);
1514         BN_bn2bin(dsasig->r, &dsasig_data[1 + byte_offset]);
1515         byte_offset = (size_t) (20 - BN_num_bytes(dsasig->s));
1516         if (byte_offset > 20) {
1517                 return NULL;
1518         }
1519         memset(&dsasig_data[21], 0, byte_offset);
1520         BN_bn2bin(dsasig->s, &dsasig_data[21 + byte_offset]);
1521
1522         sigdata_rdf = ldns_rdf_new(LDNS_RDF_TYPE_B64, 41, dsasig_data);
1523         DSA_SIG_free(dsasig);
1524
1525         return sigdata_rdf;
1526 }
1527
1528 ldns_status
1529 ldns_convert_dsa_rrsig_rdf2asn1(ldns_buffer *target_buffer,
1530                                                   const ldns_rdf *sig_rdf)
1531 {
1532         /* the EVP api wants the DER encoding of the signature... */
1533         uint8_t t;
1534         BIGNUM *R, *S;
1535         DSA_SIG *dsasig;
1536         unsigned char *raw_sig = NULL;
1537         int raw_sig_len;
1538
1539         /* extract the R and S field from the sig buffer */
1540         t = ldns_rdf_data(sig_rdf)[0];
1541         R = BN_new();
1542         if(!R) return LDNS_STATUS_MEM_ERR;
1543         (void) BN_bin2bn((unsigned char *) ldns_rdf_data(sig_rdf) + 1,
1544                          SHA_DIGEST_LENGTH, R);
1545         S = BN_new();
1546         if(!S) {
1547                 BN_free(R);
1548                 return LDNS_STATUS_MEM_ERR;
1549         }
1550         (void) BN_bin2bn((unsigned char *) ldns_rdf_data(sig_rdf) + 21,
1551                          SHA_DIGEST_LENGTH, S);
1552
1553         dsasig = DSA_SIG_new();
1554         if (!dsasig) {
1555                 BN_free(R);
1556                 BN_free(S);
1557                 return LDNS_STATUS_MEM_ERR;
1558         }
1559
1560         dsasig->r = R;
1561         dsasig->s = S;
1562
1563         raw_sig_len = i2d_DSA_SIG(dsasig, &raw_sig);
1564         if (raw_sig_len < 0) {
1565                 DSA_SIG_free(dsasig);
1566                 free(raw_sig);
1567                 return LDNS_STATUS_SSL_ERR;
1568         }
1569         if (ldns_buffer_reserve(target_buffer, (size_t) raw_sig_len)) {
1570                 ldns_buffer_write(target_buffer, raw_sig, (size_t)raw_sig_len);
1571         }
1572
1573         DSA_SIG_free(dsasig);
1574         free(raw_sig);
1575
1576         return ldns_buffer_status(target_buffer);
1577 }
1578 #endif /* HAVE_SSL */