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