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