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