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