ldns/drill: Update vendor branch to 1.6.9
[dragonfly.git] / contrib / ldns / dnssec_verify.c
1 #include <ldns/config.h>
2
3 #include <ldns/ldns.h>
4
5 #include <strings.h>
6 #include <time.h>
7
8 #ifdef HAVE_SSL
9 /* this entire file is rather useless when you don't have
10  * crypto...
11  */
12 #include <openssl/ssl.h>
13 #include <openssl/evp.h>
14 #include <openssl/rand.h>
15 #include <openssl/err.h>
16 #include <openssl/md5.h>
17
18 ldns_dnssec_data_chain *
19 ldns_dnssec_data_chain_new()
20 {
21         ldns_dnssec_data_chain *nc = LDNS_XMALLOC(ldns_dnssec_data_chain, 1);
22         if(!nc) return NULL;
23         nc->rrset = NULL;
24         nc->parent_type = 0;
25         nc->parent = NULL;
26         nc->signatures = NULL;
27         nc->packet_rcode = 0;
28         nc->packet_qtype = 0;
29         nc->packet_nodata = false;
30         return nc;
31 }
32
33 void
34 ldns_dnssec_data_chain_free(ldns_dnssec_data_chain *chain)
35 {
36         LDNS_FREE(chain);
37 }
38
39 void
40 ldns_dnssec_data_chain_deep_free(ldns_dnssec_data_chain *chain)
41 {
42         ldns_rr_list_deep_free(chain->rrset);
43         ldns_rr_list_deep_free(chain->signatures);
44         if (chain->parent) {
45                 ldns_dnssec_data_chain_deep_free(chain->parent);
46         }
47         LDNS_FREE(chain);
48 }
49
50 void
51 ldns_dnssec_data_chain_print(FILE *out, const ldns_dnssec_data_chain *chain)
52 {
53         ldns_lookup_table *rcode;
54         const ldns_rr_descriptor *rr_descriptor;
55         if (chain) {
56                 ldns_dnssec_data_chain_print(out, chain->parent);
57                 if (ldns_rr_list_rr_count(chain->rrset) > 0) {
58                         rcode = ldns_lookup_by_id(ldns_rcodes,
59                                                                  (int) chain->packet_rcode);
60                         if (rcode) {
61                                 fprintf(out, ";; rcode: %s\n", rcode->name);
62                         }
63
64                         rr_descriptor = ldns_rr_descript(chain->packet_qtype);
65                         if (rr_descriptor && rr_descriptor->_name) {
66                                 fprintf(out, ";; qtype: %s\n", rr_descriptor->_name);
67                         } else if (chain->packet_qtype != 0) {
68                                 fprintf(out, "TYPE%u", 
69                                            chain->packet_qtype);
70                         }
71                         if (chain->packet_nodata) {
72                                 fprintf(out, ";; NODATA response\n");
73                         }
74                         fprintf(out, "rrset:\n");
75                         ldns_rr_list_print(out, chain->rrset);
76                         fprintf(out, "sigs:\n");
77                         ldns_rr_list_print(out, chain->signatures);
78                         fprintf(out, "---\n");
79                 } else {
80                         fprintf(out, "<no data>\n");
81                 }
82         }
83 }
84
85 static void
86 ldns_dnssec_build_data_chain_dnskey(ldns_resolver *res,
87                                             uint16_t qflags,
88                                             const ldns_pkt *pkt,
89                                             ldns_rr_list *signatures,
90                                                 ldns_dnssec_data_chain *new_chain,
91                                                 ldns_rdf *key_name,
92                                                 ldns_rr_class c) {
93         ldns_rr_list *keys;
94         ldns_pkt *my_pkt;
95         if (signatures && ldns_rr_list_rr_count(signatures) > 0) {
96                 new_chain->signatures = ldns_rr_list_clone(signatures);
97                 new_chain->parent_type = 0;
98
99                 keys = ldns_pkt_rr_list_by_name_and_type(
100                                   pkt,
101                                  key_name,
102                                  LDNS_RR_TYPE_DNSKEY,
103                                  LDNS_SECTION_ANY_NOQUESTION
104                           );
105                 if (!keys) {
106                         my_pkt = ldns_resolver_query(res,
107                                                                         key_name,
108                                                                         LDNS_RR_TYPE_DNSKEY,
109                                                                         c,
110                                                                         qflags);
111                         if (my_pkt) {
112                         keys = ldns_pkt_rr_list_by_name_and_type(
113                                           my_pkt,
114                                          key_name,
115                                          LDNS_RR_TYPE_DNSKEY,
116                                          LDNS_SECTION_ANY_NOQUESTION
117                                   );
118                         new_chain->parent = ldns_dnssec_build_data_chain(res,
119                                                                                                         qflags,
120                                                                                                         keys,
121                                                                                                         my_pkt,
122                                                                                                         NULL);
123                         new_chain->parent->packet_qtype = LDNS_RR_TYPE_DNSKEY;
124                         ldns_pkt_free(my_pkt);
125                         }
126                 } else {
127                         new_chain->parent = ldns_dnssec_build_data_chain(res,
128                                                                                                         qflags,
129                                                                                                         keys,
130                                                                                                         pkt,
131                                                                                                         NULL);
132                         new_chain->parent->packet_qtype = LDNS_RR_TYPE_DNSKEY;
133                 }
134                 ldns_rr_list_deep_free(keys);
135         }
136 }
137
138 static void
139 ldns_dnssec_build_data_chain_other(ldns_resolver *res,
140                                             uint16_t qflags,
141                                                 ldns_dnssec_data_chain *new_chain,
142                                                 ldns_rdf *key_name,
143                                                 ldns_rr_class c,
144                                                 ldns_rr_list *dss)
145 {
146         /* 'self-signed', parent is a DS */
147         
148         /* okay, either we have other keys signing the current one,
149          * or the current
150          * one should have a DS record in the parent zone.
151          * How do we find this out? Try both?
152          *
153          * request DNSKEYS for current zone,
154          * add all signatures to current level
155          */
156         ldns_pkt *my_pkt;
157         ldns_rr_list *signatures2;
158         
159         new_chain->parent_type = 1;
160
161         my_pkt = ldns_resolver_query(res,
162                                                         key_name,
163                                                         LDNS_RR_TYPE_DS,
164                                                         c,
165                                                         qflags);
166         if (my_pkt) {
167         dss = ldns_pkt_rr_list_by_name_and_type(my_pkt,
168                                                                         key_name,
169                                                                         LDNS_RR_TYPE_DS,
170                                                                         LDNS_SECTION_ANY_NOQUESTION
171                                                                         );
172         if (dss) {
173                 new_chain->parent = ldns_dnssec_build_data_chain(res,
174                                                                                                 qflags,
175                                                                                                 dss,
176                                                                                                 my_pkt,
177                                                                                                 NULL);
178                 new_chain->parent->packet_qtype = LDNS_RR_TYPE_DS;
179                 ldns_rr_list_deep_free(dss);
180         }
181         ldns_pkt_free(my_pkt);
182         }
183
184         my_pkt = ldns_resolver_query(res,
185                                                         key_name,
186                                                         LDNS_RR_TYPE_DNSKEY,
187                                                         c,
188                                                         qflags);
189         if (my_pkt) {
190         signatures2 = ldns_pkt_rr_list_by_name_and_type(my_pkt,
191                                                                                    key_name,
192                                                                                    LDNS_RR_TYPE_RRSIG,
193                                                                                    LDNS_SECTION_ANSWER);
194         if (signatures2) {
195                 if (new_chain->signatures) {
196                         printf("There were already sigs!\n");
197                         ldns_rr_list_deep_free(new_chain->signatures);
198                         printf("replacing the old sigs\n");
199                 }
200                 new_chain->signatures = signatures2;
201         }
202         ldns_pkt_free(my_pkt);
203         }
204 }
205
206 ldns_dnssec_data_chain *
207 ldns_dnssec_build_data_chain_nokeyname(ldns_resolver *res,
208                                        uint16_t qflags,
209                                        ldns_rr *orig_rr,
210                                        const ldns_rr_list *rrset,
211                                        ldns_dnssec_data_chain *new_chain)
212 {
213         ldns_rdf *possible_parent_name;
214         ldns_pkt *my_pkt;
215         /* apparently we were not able to find a signing key, so
216            we assume the chain ends here
217         */
218         /* try parents for auth denial of DS */
219         if (orig_rr) {
220                 possible_parent_name = ldns_rr_owner(orig_rr);
221         } else if (rrset && ldns_rr_list_rr_count(rrset) > 0) {
222                 possible_parent_name = ldns_rr_owner(ldns_rr_list_rr(rrset, 0));
223         } else {
224                 /* no information to go on, give up */
225                 return new_chain;
226         }
227
228         my_pkt = ldns_resolver_query(res,
229                       possible_parent_name,
230                       LDNS_RR_TYPE_DS,
231                       LDNS_RR_CLASS_IN,
232                       qflags);
233         if (!my_pkt) {
234                 return new_chain;
235         }
236
237         if (ldns_pkt_ancount(my_pkt) > 0) {
238                 /* add error, no sigs but DS in parent */
239                 /*ldns_pkt_print(stdout, my_pkt);*/
240                 ldns_pkt_free(my_pkt);
241         } else {
242                 /* are there signatures? */
243                 new_chain->parent =  ldns_dnssec_build_data_chain(res, 
244                                           qflags, 
245                                           NULL,
246                                           my_pkt,
247                                           NULL);
248
249                 new_chain->parent->packet_qtype = LDNS_RR_TYPE_DS;
250                 
251         }
252         return new_chain;
253 }
254
255
256 ldns_dnssec_data_chain *
257 ldns_dnssec_build_data_chain(ldns_resolver *res,
258                                             uint16_t qflags,
259                                             const ldns_rr_list *rrset,
260                                             const ldns_pkt *pkt,
261                                             ldns_rr *orig_rr)
262 {
263         ldns_rr_list *signatures = NULL;
264         ldns_rr_list *dss = NULL;
265         
266         ldns_rr_list *my_rrset;
267
268         ldns_pkt *my_pkt;
269
270         ldns_rdf *name = NULL, *key_name = NULL;
271         ldns_rr_type type = 0;
272         ldns_rr_class c = 0;
273
274         bool other_rrset = false;
275         
276         ldns_dnssec_data_chain *new_chain = ldns_dnssec_data_chain_new();
277
278         if (!ldns_dnssec_pkt_has_rrsigs(pkt)) {
279                 /* hmm. no dnssec data in the packet. go up to try and deny
280                  * DS? */
281                 return new_chain;
282         }
283
284         if (orig_rr) {
285                 new_chain->rrset = ldns_rr_list_new();
286                 ldns_rr_list_push_rr(new_chain->rrset, orig_rr);
287                 new_chain->parent = ldns_dnssec_build_data_chain(res,
288                                                                                             qflags,
289                                                                                             rrset,
290                                                                                             pkt,
291                                                                                             NULL);
292                 new_chain->packet_rcode = ldns_pkt_get_rcode(pkt);
293                 new_chain->packet_qtype = ldns_rr_get_type(orig_rr);
294                 if (ldns_pkt_ancount(pkt) == 0) {
295                         new_chain->packet_nodata = true;
296                 }
297                 return new_chain;
298         }
299         
300         if (!rrset || ldns_rr_list_rr_count(rrset) < 1) {
301                 /* hmm, no data, do we have denial? only works if pkt was given,
302                    otherwise caller has to do the check himself */
303                 new_chain->packet_nodata = true;
304                 if (pkt) {
305                         my_rrset = ldns_pkt_rr_list_by_type(pkt,
306                                                                                  LDNS_RR_TYPE_NSEC,
307                                                                                  LDNS_SECTION_ANY_NOQUESTION
308                                                                                  );
309                         if (my_rrset) {
310                                 if (ldns_rr_list_rr_count(my_rrset) > 0) {
311                                         type = LDNS_RR_TYPE_NSEC;
312                                         other_rrset = true;
313                                 } else {
314                                         ldns_rr_list_deep_free(my_rrset);
315                                         my_rrset = NULL;
316                                 }
317                         } else {
318                                 /* nothing, try nsec3 */
319                                 my_rrset = ldns_pkt_rr_list_by_type(pkt,
320                                                      LDNS_RR_TYPE_NSEC3,
321                                                         LDNS_SECTION_ANY_NOQUESTION);
322                                 if (my_rrset) {
323                                         if (ldns_rr_list_rr_count(my_rrset) > 0) {
324                                                 type = LDNS_RR_TYPE_NSEC3;
325                                                 other_rrset = true;
326                                         } else {
327                                                 ldns_rr_list_deep_free(my_rrset);
328                                                 my_rrset = NULL;
329                                         }
330                                 } else {
331                                         /* nothing, stop */
332                                         /* try parent zone? for denied insecure? */
333                                         return new_chain;
334                                 }
335                         }
336                 } else {
337                         return new_chain;
338                 }
339         } else {
340                 my_rrset = (ldns_rr_list *) rrset;
341         }
342         
343         if (my_rrset && ldns_rr_list_rr_count(my_rrset) > 0) {
344                 new_chain->rrset = ldns_rr_list_clone(my_rrset);
345                 name = ldns_rr_owner(ldns_rr_list_rr(my_rrset, 0));
346                 type = ldns_rr_get_type(ldns_rr_list_rr(my_rrset, 0));
347                 c = ldns_rr_get_class(ldns_rr_list_rr(my_rrset, 0));
348         }
349         
350         if (other_rrset) {
351                 ldns_rr_list_deep_free(my_rrset);
352         }
353         
354         /* normally there will only be 1 signature 'set'
355            but there can be more than 1 denial (wildcards)
356            so check for NSEC
357         */
358         if (type == LDNS_RR_TYPE_NSEC || type == LDNS_RR_TYPE_NSEC3) {
359                 /* just throw in all signatures, the tree builder must sort
360                    this out */
361                 if (pkt) {
362                         signatures = ldns_dnssec_pkt_get_rrsigs_for_type(pkt, type);
363                 } else {
364                         my_pkt = ldns_resolver_query(res, name, type, c, qflags);
365                         if (my_pkt) {
366                         signatures = ldns_dnssec_pkt_get_rrsigs_for_type(pkt, type);
367                         ldns_pkt_free(my_pkt);
368                         }
369                 }
370         } else {
371                 if (pkt) {
372                         signatures =
373                                 ldns_dnssec_pkt_get_rrsigs_for_name_and_type(pkt,
374                                                                                                         name,
375                                                                                                         type);
376                 }
377                 if (!signatures) {
378                         my_pkt = ldns_resolver_query(res, name, type, c, qflags);
379                         if (my_pkt) {
380                         signatures =
381                                 ldns_dnssec_pkt_get_rrsigs_for_name_and_type(my_pkt,
382                                                                                                         name,
383                                                                                                         type);
384                         ldns_pkt_free(my_pkt);
385                         }
386                 }
387         }
388
389         if (signatures && ldns_rr_list_rr_count(signatures) > 0) {
390                 key_name = ldns_rr_rdf(ldns_rr_list_rr(signatures, 0), 7);
391         }
392
393         if (!key_name) {
394                 return ldns_dnssec_build_data_chain_nokeyname(res,
395                                                               qflags,
396                                                               orig_rr,
397                                                               rrset,
398                                                               new_chain);
399         }
400
401         if (type != LDNS_RR_TYPE_DNSKEY) {
402                 ldns_dnssec_build_data_chain_dnskey(res,
403                                                     qflags,
404                                                     pkt,
405                                                     signatures,
406                                                     new_chain,
407                                                     key_name,
408                                                     c
409                                                     );
410         } else {
411                 ldns_dnssec_build_data_chain_other(res,
412                                                    qflags,
413                                                    new_chain,
414                                                    key_name,
415                                                    c,
416                                                    dss
417                                                     
418                                                     );
419         }
420         if (signatures) {
421                 ldns_rr_list_deep_free(signatures);
422         }
423
424         return new_chain;
425 }
426
427 ldns_dnssec_trust_tree *
428 ldns_dnssec_trust_tree_new()
429 {
430         ldns_dnssec_trust_tree *new_tree = LDNS_XMALLOC(ldns_dnssec_trust_tree,
431                                                                                    1);
432         if(!new_tree) return NULL;
433         new_tree->rr = NULL;
434         new_tree->rrset = NULL;
435         new_tree->parent_count = 0;
436
437         return new_tree;
438 }
439
440 void
441 ldns_dnssec_trust_tree_free(ldns_dnssec_trust_tree *tree)
442 {
443         size_t i;
444         if (tree) {
445                 for (i = 0; i < tree->parent_count; i++) {
446                         ldns_dnssec_trust_tree_free(tree->parents[i]);
447                 }
448         }
449         LDNS_FREE(tree);
450 }
451
452 size_t
453 ldns_dnssec_trust_tree_depth(ldns_dnssec_trust_tree *tree)
454 {
455         size_t result = 0;
456         size_t parent = 0;
457         size_t i;
458         
459         for (i = 0; i < tree->parent_count; i++) {
460                 parent = ldns_dnssec_trust_tree_depth(tree->parents[i]);
461                 if (parent > result) {
462                         result = parent;
463                 }
464         }
465         return 1 + result;
466 }
467
468 /* TODO ldns_ */
469 static void
470 print_tabs(FILE *out, size_t nr, uint8_t *map, size_t treedepth)
471 {
472         size_t i;
473         for (i = 0; i < nr; i++) {
474                 if (i == nr - 1) {
475                         fprintf(out, "|---");
476                 } else if (map && i < treedepth && map[i] == 1) {
477                         fprintf(out, "|   ");
478                 } else {
479                         fprintf(out, "    ");
480                 }
481         }
482 }
483
484 void
485 ldns_dnssec_trust_tree_print_sm(FILE *out,
486                                                   ldns_dnssec_trust_tree *tree,
487                                                   size_t tabs,
488                                                   bool extended,
489                                                   uint8_t *sibmap,
490                                                   size_t treedepth)
491 {
492         size_t i;
493         const ldns_rr_descriptor *descriptor;
494         bool mapset = false;
495         
496         if (!sibmap) {
497                 treedepth = ldns_dnssec_trust_tree_depth(tree);
498                 sibmap = malloc(treedepth);
499                 if(!sibmap)
500                         return; /* mem err */
501                 memset(sibmap, 0, treedepth);
502                 mapset = true;
503         }
504         
505         if (tree) {
506                 if (tree->rr) {
507                         print_tabs(out, tabs, sibmap, treedepth);
508                         ldns_rdf_print(out, ldns_rr_owner(tree->rr));
509                         descriptor = ldns_rr_descript(ldns_rr_get_type(tree->rr));
510
511                         if (descriptor->_name) {
512                                 fprintf(out, " (%s", descriptor->_name);
513                         } else {
514                                 fprintf(out, " (TYPE%d", 
515                                            ldns_rr_get_type(tree->rr));
516                         }
517                         if (tabs > 0) {
518                                 if (ldns_rr_get_type(tree->rr) == LDNS_RR_TYPE_DNSKEY) {
519                                         fprintf(out, " keytag: %u",
520                                                 (unsigned int) ldns_calc_keytag(tree->rr));
521                                         fprintf(out, " alg: ");
522                                         ldns_rdf_print(out, ldns_rr_rdf(tree->rr, 2));
523                                         fprintf(out, " flags: ");
524                                         ldns_rdf_print(out, ldns_rr_rdf(tree->rr, 0));
525                                 } else if (ldns_rr_get_type(tree->rr) == LDNS_RR_TYPE_DS) {
526                                         fprintf(out, " keytag: ");
527                                         ldns_rdf_print(out, ldns_rr_rdf(tree->rr, 0));
528                                         fprintf(out, " digest type: ");
529                                         ldns_rdf_print(out, ldns_rr_rdf(tree->rr, 2));
530                                 }
531                                 if (ldns_rr_get_type(tree->rr) == LDNS_RR_TYPE_NSEC) {
532                                         fprintf(out, " ");
533                                         ldns_rdf_print(out, ldns_rr_rdf(tree->rr, 0));
534                                         fprintf(out, " ");
535                                         ldns_rdf_print(out, ldns_rr_rdf(tree->rr, 1));
536                                 }
537                         }
538                         
539                         fprintf(out, ")\n");
540                         for (i = 0; i < tree->parent_count; i++) {
541                                 if (tree->parent_count > 1 && i < tree->parent_count - 1) {
542                                         sibmap[tabs] = 1;
543                                 } else {
544                                         sibmap[tabs] = 0;
545                                 }
546                                 /* only print errors */
547                                 if (ldns_rr_get_type(tree->parents[i]->rr) == 
548                                     LDNS_RR_TYPE_NSEC ||
549                                     ldns_rr_get_type(tree->parents[i]->rr) ==
550                                     LDNS_RR_TYPE_NSEC3) {
551                                         if (tree->parent_status[i] == LDNS_STATUS_OK) {
552                                                 print_tabs(out, tabs + 1, sibmap, treedepth);
553                                                 if (tabs == 0 &&
554                                                     ldns_rr_get_type(tree->rr) == LDNS_RR_TYPE_NS &&
555                                                         ldns_rr_rd_count(tree->rr) > 0) {
556                                                         fprintf(out, "Existence of DS is denied by:\n");
557                                                 } else {
558                                                         fprintf(out, "Existence is denied by:\n");
559                                                 }
560                                         } else {
561                                                 /* NS records aren't signed */
562                                                 if (ldns_rr_get_type(tree->rr) == LDNS_RR_TYPE_NS) {
563                                                         fprintf(out, "Existence of DS is denied by:\n");
564                                                 } else {
565                                                         print_tabs(out, tabs + 1, sibmap, treedepth);
566                                                         fprintf(out,
567                                                                    "Error in denial of existence: %s\n",
568                                                                    ldns_get_errorstr_by_id(
569                                                                            tree->parent_status[i]));
570                                                 }
571                                         }
572                                 } else
573                                         if (tree->parent_status[i] != LDNS_STATUS_OK) {
574                                                 print_tabs(out, tabs + 1, sibmap, treedepth);
575                                                 fprintf(out,
576                                                            "%s:\n",
577                                                            ldns_get_errorstr_by_id(
578                                                                tree->parent_status[i]));
579                                                 if (tree->parent_status[i]
580                                                     == LDNS_STATUS_SSL_ERR) {
581                                                         printf("; SSL Error: ");
582                                                         ERR_load_crypto_strings();
583                                                         ERR_print_errors_fp(stdout);
584                                                         printf("\n");
585                                                 }
586                                                 ldns_rr_print(out, tree->parent_signature[i]);
587                                                 printf("For RRset:\n");
588                                                 ldns_rr_list_print(out, tree->rrset);
589                                                 printf("With key:\n");
590                                                 ldns_rr_print(out, tree->parents[i]->rr);
591                                         }
592                                 ldns_dnssec_trust_tree_print_sm(out,
593                                                                                   tree->parents[i],
594                                                                                   tabs+1,
595                                                                                   extended,
596                                                                                   sibmap,
597                                                                                   treedepth);
598                         }
599                 } else {
600                         print_tabs(out, tabs, sibmap, treedepth);
601                         fprintf(out, "<no data>\n");
602                 }
603         } else {
604                 fprintf(out, "<null pointer>\n");
605         }
606         
607         if (mapset) {
608                 free(sibmap);
609         }
610 }
611
612 void
613 ldns_dnssec_trust_tree_print(FILE *out,
614                                             ldns_dnssec_trust_tree *tree,
615                                             size_t tabs,
616                                             bool extended)
617 {
618         ldns_dnssec_trust_tree_print_sm(out, tree, tabs, extended, NULL, 0);
619 }
620
621 ldns_status
622 ldns_dnssec_trust_tree_add_parent(ldns_dnssec_trust_tree *tree,
623                                   const ldns_dnssec_trust_tree *parent,
624                                   const ldns_rr *signature,
625                                   const ldns_status parent_status)
626 {
627         if (tree
628             && parent
629             && tree->parent_count < LDNS_DNSSEC_TRUST_TREE_MAX_PARENTS) {
630                 /*
631                   printf("Add parent for: ");
632                   ldns_rr_print(stdout, tree->rr);
633                   printf("parent: ");
634                   ldns_rr_print(stdout, parent->rr);
635                 */
636                 tree->parents[tree->parent_count] =
637                         (ldns_dnssec_trust_tree *) parent;
638                 tree->parent_status[tree->parent_count] = parent_status;
639                 tree->parent_signature[tree->parent_count] = (ldns_rr *) signature;
640                 tree->parent_count++;
641                 return LDNS_STATUS_OK;
642         } else {
643                 return LDNS_STATUS_ERR;
644         }
645 }
646
647 /* if rr is null, take the first from the rrset */
648 ldns_dnssec_trust_tree *
649 ldns_dnssec_derive_trust_tree(ldns_dnssec_data_chain *data_chain, ldns_rr *rr)
650 {
651         ldns_rr_list *cur_rrset;
652         ldns_rr_list *cur_sigs;
653         ldns_rr *cur_rr = NULL;
654         ldns_rr *cur_sig_rr;
655         size_t i, j;
656
657         ldns_dnssec_trust_tree *new_tree = ldns_dnssec_trust_tree_new();
658         if(!new_tree)
659                 return NULL;
660         
661         if (data_chain && data_chain->rrset) {
662                 cur_rrset = data_chain->rrset;
663         
664                 cur_sigs = data_chain->signatures;
665
666                 if (rr) {
667                         cur_rr = rr;
668                 }
669
670                 if (!cur_rr && ldns_rr_list_rr_count(cur_rrset) > 0) {
671                         cur_rr = ldns_rr_list_rr(cur_rrset, 0);
672                 }
673
674                 if (cur_rr) {
675                         new_tree->rr = cur_rr;
676                         new_tree->rrset = cur_rrset;
677                         /* there are three possibilities:
678                            1 - 'normal' rrset, signed by a key
679                            2 - dnskey signed by other dnskey
680                            3 - dnskey proven by higher level DS
681                            (data denied by nsec is a special case that can
682                            occur in multiple places)
683                                    
684                         */
685                         if (cur_sigs) {
686                                 for (i = 0; i < ldns_rr_list_rr_count(cur_sigs); i++) {
687                                         /* find the appropriate key in the parent list */
688                                         cur_sig_rr = ldns_rr_list_rr(cur_sigs, i);
689
690                                         if (ldns_rr_get_type(cur_rr) == LDNS_RR_TYPE_NSEC) {
691                                                 if (ldns_dname_compare(ldns_rr_owner(cur_sig_rr),
692                                                                                    ldns_rr_owner(cur_rr)))
693                                                         {
694                                                                 /* find first that does match */
695
696                                                                 for (j = 0;
697                                                                      j < ldns_rr_list_rr_count(cur_rrset) && 
698                                                                                 ldns_dname_compare(ldns_rr_owner(cur_sig_rr),ldns_rr_owner(cur_rr)) != 0;
699                                                                      j++) {
700                                                                         cur_rr = ldns_rr_list_rr(cur_rrset, j);
701                                                                         
702                                                                 }
703                                                                 if (ldns_dname_compare(ldns_rr_owner(cur_sig_rr), 
704                                                                                                    ldns_rr_owner(cur_rr)))
705                                                                         {
706                                                                                 break;
707                                                                         }
708                                                         }
709                                                         
710                                         }
711                                         /* option 1 */
712                                         if (data_chain->parent) {
713                                                 ldns_dnssec_derive_trust_tree_normal_rrset(
714                                                     new_tree,
715                                                     data_chain,
716                                                     cur_sig_rr);
717                                         }
718
719                                         /* option 2 */
720                                         ldns_dnssec_derive_trust_tree_dnskey_rrset(
721                                             new_tree,
722                                             data_chain,
723                                             cur_rr,
724                                             cur_sig_rr);
725                                 }
726                                         
727                                 ldns_dnssec_derive_trust_tree_ds_rrset(new_tree,
728                                                                                             data_chain,
729                                                                                             cur_rr);
730                         } else {
731                                 /* no signatures? maybe it's nsec data */
732                                         
733                                 /* just add every rr from parent as new parent */
734                                 ldns_dnssec_derive_trust_tree_no_sig(new_tree, data_chain);
735                         }
736                 }
737         }
738
739         return new_tree;
740 }
741
742 void
743 ldns_dnssec_derive_trust_tree_normal_rrset(ldns_dnssec_trust_tree *new_tree,
744                                            ldns_dnssec_data_chain *data_chain,
745                                            ldns_rr *cur_sig_rr)
746 {
747         size_t i, j;
748         ldns_rr_list *cur_rrset = ldns_rr_list_clone(data_chain->rrset); 
749         ldns_dnssec_trust_tree *cur_parent_tree;
750         ldns_rr *cur_parent_rr;
751         uint16_t cur_keytag;
752         ldns_rr_list *tmp_rrset = NULL;
753         ldns_status cur_status;
754
755         cur_keytag = ldns_rdf2native_int16(ldns_rr_rrsig_keytag(cur_sig_rr));
756         
757         for (j = 0; j < ldns_rr_list_rr_count(data_chain->parent->rrset); j++) {
758                 cur_parent_rr = ldns_rr_list_rr(data_chain->parent->rrset, j);
759                 if (ldns_rr_get_type(cur_parent_rr) == LDNS_RR_TYPE_DNSKEY) {
760                         if (ldns_calc_keytag(cur_parent_rr) == cur_keytag) {
761
762                                 /* TODO: check wildcard nsec too */
763                                 if (cur_rrset && ldns_rr_list_rr_count(cur_rrset) > 0) {
764                                         tmp_rrset = cur_rrset;
765                                         if (ldns_rr_get_type(ldns_rr_list_rr(cur_rrset, 0))
766                                             == LDNS_RR_TYPE_NSEC ||
767                                             ldns_rr_get_type(ldns_rr_list_rr(cur_rrset, 0))
768                                             == LDNS_RR_TYPE_NSEC3) {
769                                                 /* might contain different names! 
770                                                    sort and split */
771                                                 ldns_rr_list_sort(cur_rrset);
772                                                 if (tmp_rrset && tmp_rrset != cur_rrset) {
773                                                         ldns_rr_list_deep_free(tmp_rrset);
774                                                         tmp_rrset = NULL;
775                                                 }
776                                                 tmp_rrset = ldns_rr_list_pop_rrset(cur_rrset);
777                                                 
778                                                 /* with nsecs, this might be the wrong one */
779                                                 while (tmp_rrset &&
780                                                        ldns_rr_list_rr_count(cur_rrset) > 0 &&
781                                                        ldns_dname_compare(
782                                                                 ldns_rr_owner(ldns_rr_list_rr(
783                                                                                         tmp_rrset, 0)),
784                                                                 ldns_rr_owner(cur_sig_rr)) != 0) {
785                                                         ldns_rr_list_deep_free(tmp_rrset);
786                                                         tmp_rrset =
787                                                                 ldns_rr_list_pop_rrset(cur_rrset);
788                                                 }
789                                         }
790                                         cur_status = ldns_verify_rrsig(tmp_rrset,
791                                                                                          cur_sig_rr,
792                                                                                          cur_parent_rr);
793                                         /* avoid dupes */
794                                         for (i = 0; i < new_tree->parent_count; i++) {
795                                                 if (cur_parent_rr == new_tree->parents[i]->rr) {
796                                                         goto done;
797                                                 }
798                                         }
799
800                                         cur_parent_tree =
801                                                 ldns_dnssec_derive_trust_tree(data_chain->parent,
802                                                                               cur_parent_rr);
803                                         (void)ldns_dnssec_trust_tree_add_parent(new_tree,
804                                                    cur_parent_tree,
805                                                    cur_sig_rr,
806                                                    cur_status);
807                                 }
808                         }
809                 }
810         }
811  done:
812         if (tmp_rrset && tmp_rrset != cur_rrset) {
813                 ldns_rr_list_deep_free(tmp_rrset);
814         }
815         ldns_rr_list_deep_free(cur_rrset);
816 }
817
818 void
819 ldns_dnssec_derive_trust_tree_dnskey_rrset(ldns_dnssec_trust_tree *new_tree,
820                                            ldns_dnssec_data_chain *data_chain,
821                                            ldns_rr *cur_rr,
822                                            ldns_rr *cur_sig_rr)
823 {
824         size_t j;
825         ldns_rr_list *cur_rrset = data_chain->rrset;
826         ldns_dnssec_trust_tree *cur_parent_tree;
827         ldns_rr *cur_parent_rr;
828         uint16_t cur_keytag;
829         ldns_status cur_status;
830
831         cur_keytag = ldns_rdf2native_int16(ldns_rr_rrsig_keytag(cur_sig_rr));
832
833         for (j = 0; j < ldns_rr_list_rr_count(cur_rrset); j++) {
834                 cur_parent_rr = ldns_rr_list_rr(cur_rrset, j);
835                 if (cur_parent_rr != cur_rr &&
836                     ldns_rr_get_type(cur_parent_rr) == LDNS_RR_TYPE_DNSKEY) {
837                         if (ldns_calc_keytag(cur_parent_rr) == cur_keytag
838                             ) {
839                                 cur_parent_tree = ldns_dnssec_trust_tree_new();
840                                 cur_parent_tree->rr = cur_parent_rr;
841                                 cur_parent_tree->rrset = cur_rrset;
842                                 cur_status = ldns_verify_rrsig(cur_rrset,
843                                                                cur_sig_rr,
844                                                                cur_parent_rr);
845                                 (void) ldns_dnssec_trust_tree_add_parent(new_tree,
846                                             cur_parent_tree, cur_sig_rr, cur_status);
847                         }
848                 }
849         }
850 }
851
852 void
853 ldns_dnssec_derive_trust_tree_ds_rrset(ldns_dnssec_trust_tree *new_tree,
854                                        ldns_dnssec_data_chain *data_chain,
855                                        ldns_rr *cur_rr)
856 {
857         size_t j, h;
858         ldns_rr_list *cur_rrset = data_chain->rrset;
859         ldns_dnssec_trust_tree *cur_parent_tree;
860         ldns_rr *cur_parent_rr;
861
862         /* try the parent to see whether there are DSs there */
863         if (ldns_rr_get_type(cur_rr) == LDNS_RR_TYPE_DNSKEY &&
864             data_chain->parent &&
865             data_chain->parent->rrset
866             ) {
867                 for (j = 0;
868                         j < ldns_rr_list_rr_count(data_chain->parent->rrset);
869                         j++) {
870                         cur_parent_rr = ldns_rr_list_rr(data_chain->parent->rrset, j);
871                         if (ldns_rr_get_type(cur_parent_rr) == LDNS_RR_TYPE_DS) {
872                                 for (h = 0; h < ldns_rr_list_rr_count(cur_rrset); h++) {
873                                         cur_rr = ldns_rr_list_rr(cur_rrset, h);
874                                         if (ldns_rr_compare_ds(cur_rr, cur_parent_rr)) {
875                                                 cur_parent_tree =
876                                                         ldns_dnssec_derive_trust_tree(
877                                                             data_chain->parent, cur_parent_rr);
878                                                 (void) ldns_dnssec_trust_tree_add_parent(
879                                                             new_tree,
880                                                             cur_parent_tree,
881                                                             NULL,
882                                                             LDNS_STATUS_OK);
883                                         } else {
884                                                 /*ldns_rr_print(stdout, cur_parent_rr);*/
885                                         }
886                                 }
887                         }
888                 }
889         }
890 }
891
892 void
893 ldns_dnssec_derive_trust_tree_no_sig(ldns_dnssec_trust_tree *new_tree,
894                                      ldns_dnssec_data_chain *data_chain)
895 {
896         size_t i;
897         ldns_rr_list *cur_rrset;
898         ldns_rr *cur_parent_rr;
899         ldns_dnssec_trust_tree *cur_parent_tree;
900         ldns_status result;
901         
902         if (data_chain->parent && data_chain->parent->rrset) {
903                 cur_rrset = data_chain->parent->rrset;
904                 /* nsec? */
905                 if (cur_rrset && ldns_rr_list_rr_count(cur_rrset) > 0) {
906                         if (ldns_rr_get_type(ldns_rr_list_rr(cur_rrset, 0)) ==
907                             LDNS_RR_TYPE_NSEC3) {
908                                 result = ldns_dnssec_verify_denial_nsec3(
909                                                 new_tree->rr,
910                                                    cur_rrset,
911                                                    data_chain->parent->signatures,
912                                                    data_chain->packet_rcode,
913                                                    data_chain->packet_qtype,
914                                                    data_chain->packet_nodata);
915                         } else if (ldns_rr_get_type(ldns_rr_list_rr(cur_rrset, 0)) ==
916                                          LDNS_RR_TYPE_NSEC3) {
917                                 result = ldns_dnssec_verify_denial(
918                                                 new_tree->rr,
919                                                    cur_rrset,
920                                                    data_chain->parent->signatures);
921                         } else {
922                                 /* unsigned zone, unsigned parent */
923                                 result = LDNS_STATUS_OK;
924                         }
925                 } else {
926                         result = LDNS_STATUS_DNSSEC_NSEC_RR_NOT_COVERED;
927                 }
928                 for (i = 0; i < ldns_rr_list_rr_count(cur_rrset); i++) {
929                         cur_parent_rr = ldns_rr_list_rr(cur_rrset, i);
930                         cur_parent_tree = 
931                                 ldns_dnssec_derive_trust_tree(data_chain->parent,
932                                                                                 cur_parent_rr);
933                         (void) ldns_dnssec_trust_tree_add_parent(new_tree,
934                                     cur_parent_tree, NULL, result);
935                 }
936         }
937 }
938
939 /*
940  * returns OK if there is a path from tree to key with only OK
941  * the (first) error in between otherwise
942  * or NOT_FOUND if the key wasn't present at all
943  */
944 ldns_status
945 ldns_dnssec_trust_tree_contains_keys(ldns_dnssec_trust_tree *tree,
946                                                           ldns_rr_list *trusted_keys)
947 {
948         size_t i;
949         ldns_status result = LDNS_STATUS_CRYPTO_NO_DNSKEY;
950         bool equal;
951         ldns_status parent_result;
952         
953         if (tree && trusted_keys && ldns_rr_list_rr_count(trusted_keys) > 0)
954                 { if (tree->rr) {
955                                 for (i = 0; i < ldns_rr_list_rr_count(trusted_keys); i++) {
956                                         equal = ldns_rr_compare_ds(
957                                                           tree->rr,
958                                                           ldns_rr_list_rr(trusted_keys, i));
959                                         if (equal) {
960                                                 result = LDNS_STATUS_OK;
961                                                 return result;
962                                         }
963                                 }
964                         }
965                         for (i = 0; i < tree->parent_count; i++) {
966                                 parent_result =
967                                         ldns_dnssec_trust_tree_contains_keys(tree->parents[i],
968                                                                                                   trusted_keys);
969                                 if (parent_result != LDNS_STATUS_CRYPTO_NO_DNSKEY) {
970                                         if (tree->parent_status[i] != LDNS_STATUS_OK) {
971                                                 result = tree->parent_status[i];
972                                         } else {
973                                                 if (ldns_rr_get_type(tree->rr)
974                                                     == LDNS_RR_TYPE_NSEC &&
975                                                     parent_result == LDNS_STATUS_OK
976                                                     ) {
977                                                         result =
978                                                                 LDNS_STATUS_DNSSEC_EXISTENCE_DENIED;
979                                                 } else {
980                                                         result = parent_result;
981                                                 }
982                                         }
983                                 }
984                         }
985                 } else {
986                 result = LDNS_STATUS_ERR;
987         }
988         
989         return result;
990 }
991
992 ldns_status
993 ldns_verify(ldns_rr_list *rrset, ldns_rr_list *rrsig, const ldns_rr_list *keys, 
994                   ldns_rr_list *good_keys)
995 {
996         uint16_t i;
997         ldns_status verify_result = LDNS_STATUS_ERR;
998
999         if (!rrset || !rrsig || !keys) {
1000                 return LDNS_STATUS_ERR;
1001         }
1002
1003         if (ldns_rr_list_rr_count(rrset) < 1) {
1004                 return LDNS_STATUS_ERR;
1005         }
1006
1007         if (ldns_rr_list_rr_count(rrsig) < 1) {
1008                 return LDNS_STATUS_CRYPTO_NO_RRSIG;
1009         }
1010         
1011         if (ldns_rr_list_rr_count(keys) < 1) {
1012                 verify_result = LDNS_STATUS_CRYPTO_NO_TRUSTED_DNSKEY;
1013         } else {
1014                 for (i = 0; i < ldns_rr_list_rr_count(rrsig); i++) {
1015                         ldns_status s = ldns_verify_rrsig_keylist(rrset, 
1016                                 ldns_rr_list_rr(rrsig, i), keys, good_keys);
1017                         /* try a little to get more descriptive error */
1018                         if(s == LDNS_STATUS_OK) {
1019                                 verify_result = LDNS_STATUS_OK;
1020                         } else if(verify_result == LDNS_STATUS_ERR)
1021                                 verify_result = s;
1022                         else if(s !=  LDNS_STATUS_ERR && verify_result ==
1023                                 LDNS_STATUS_CRYPTO_NO_MATCHING_KEYTAG_DNSKEY)
1024                                 verify_result = s;
1025                 }
1026         }
1027         return verify_result;
1028 }
1029
1030 ldns_status
1031 ldns_verify_notime(ldns_rr_list *rrset, ldns_rr_list *rrsig,
1032         const ldns_rr_list *keys, ldns_rr_list *good_keys)
1033 {
1034         uint16_t i;
1035         ldns_status verify_result = LDNS_STATUS_ERR;
1036
1037         if (!rrset || !rrsig || !keys) {
1038                 return LDNS_STATUS_ERR;
1039         }
1040
1041         if (ldns_rr_list_rr_count(rrset) < 1) {
1042                 return LDNS_STATUS_ERR;
1043         }
1044
1045         if (ldns_rr_list_rr_count(rrsig) < 1) {
1046                 return LDNS_STATUS_CRYPTO_NO_RRSIG;
1047         }
1048
1049         if (ldns_rr_list_rr_count(keys) < 1) {
1050                 verify_result = LDNS_STATUS_CRYPTO_NO_TRUSTED_DNSKEY;
1051         } else {
1052                 for (i = 0; i < ldns_rr_list_rr_count(rrsig); i++) {
1053                         ldns_status s = ldns_verify_rrsig_keylist_notime(rrset,
1054                                 ldns_rr_list_rr(rrsig, i), keys, good_keys);
1055
1056                         /* try a little to get more descriptive error */
1057                         if (s == LDNS_STATUS_OK) {
1058                                 verify_result = LDNS_STATUS_OK;
1059                         } else if (verify_result == LDNS_STATUS_ERR) {
1060                                 verify_result = s;
1061                         } else if (s !=  LDNS_STATUS_ERR && verify_result ==
1062                                 LDNS_STATUS_CRYPTO_NO_MATCHING_KEYTAG_DNSKEY) {
1063                                 verify_result = s;
1064                         }
1065                 }
1066         }
1067         return verify_result;
1068 }
1069
1070 ldns_rr_list *
1071 ldns_fetch_valid_domain_keys(const ldns_resolver *res,
1072                              const ldns_rdf *domain,
1073                              const ldns_rr_list *keys,
1074                              ldns_status *status)
1075 {
1076         ldns_rr_list * trusted_keys = NULL;
1077         ldns_rr_list * ds_keys = NULL;
1078
1079         if (res && domain && keys) {
1080
1081                 if ((trusted_keys = ldns_validate_domain_dnskey(res,
1082                                          domain,
1083                                          keys))) {
1084                         *status = LDNS_STATUS_OK;
1085                 } else {
1086                         /* No trusted keys in this domain, we'll have to find some in the parent domain */
1087                         *status = LDNS_STATUS_CRYPTO_NO_TRUSTED_DNSKEY;
1088       
1089                         if (ldns_rdf_size(domain) > 1) {
1090                                 /* Fail if we are at the root */
1091                                 ldns_rr_list * parent_keys;
1092                                 ldns_rdf * parent_domain = ldns_dname_left_chop(domain);
1093         
1094                                 if ((parent_keys = 
1095                                         ldns_fetch_valid_domain_keys(res,
1096                                              parent_domain,
1097                                              keys,
1098                                              status))) {
1099                                         /* Check DS records */
1100                                         if ((ds_keys =
1101                                                 ldns_validate_domain_ds(res,
1102                                                      domain,
1103                                                      parent_keys))) {
1104                                                 trusted_keys =
1105                                                         ldns_fetch_valid_domain_keys(res,
1106                                                              domain,
1107                                                              ds_keys,
1108                                                              status);
1109                                                 ldns_rr_list_deep_free(ds_keys);
1110                                         } else {
1111                                                 /* No valid DS at the parent -- fail */
1112                                                 *status = LDNS_STATUS_CRYPTO_NO_TRUSTED_DS ;
1113                                         }
1114                                         ldns_rr_list_deep_free(parent_keys);
1115                                 }
1116                                 ldns_rdf_deep_free(parent_domain);
1117                         }
1118                 }
1119         }
1120         return trusted_keys;
1121 }
1122
1123 ldns_rr_list *
1124 ldns_validate_domain_dnskey(const ldns_resolver * res,
1125                                            const ldns_rdf * domain,
1126                                            const ldns_rr_list * keys)
1127 {
1128         ldns_pkt * keypkt;
1129         ldns_rr * cur_key;
1130         uint16_t key_i; uint16_t key_j; uint16_t key_k;
1131         uint16_t sig_i; ldns_rr * cur_sig;
1132
1133         ldns_rr_list * domain_keys = NULL;
1134         ldns_rr_list * domain_sigs = NULL;
1135         ldns_rr_list * trusted_keys = NULL;
1136
1137         /* Fetch keys for the domain */
1138         keypkt = ldns_resolver_query(res, domain,
1139                 LDNS_RR_TYPE_DNSKEY, LDNS_RR_CLASS_IN, LDNS_RD);
1140         if (keypkt) {
1141                 domain_keys = ldns_pkt_rr_list_by_type(keypkt,
1142                                                                             LDNS_RR_TYPE_DNSKEY,
1143                                                                             LDNS_SECTION_ANSWER);
1144                 domain_sigs = ldns_pkt_rr_list_by_type(keypkt,
1145                                                                             LDNS_RR_TYPE_RRSIG,
1146                                                                             LDNS_SECTION_ANSWER);
1147
1148                 /* Try to validate the record using our keys */
1149                 for (key_i=0; key_i< ldns_rr_list_rr_count(domain_keys); key_i++) {
1150       
1151                         cur_key = ldns_rr_list_rr(domain_keys, key_i);
1152                         for (key_j=0; key_j<ldns_rr_list_rr_count(keys); key_j++) {
1153                                 if (ldns_rr_compare_ds(ldns_rr_list_rr(keys, key_j),
1154                                                                    cur_key)) {
1155           
1156                                         /* Current key is trusted -- validate */
1157                                         trusted_keys = ldns_rr_list_new();
1158           
1159                                         for (sig_i=0;
1160                                                 sig_i<ldns_rr_list_rr_count(domain_sigs);
1161                                                 sig_i++) {
1162                                                 cur_sig = ldns_rr_list_rr(domain_sigs, sig_i);
1163                                                 /* Avoid non-matching sigs */
1164                                                 if (ldns_rdf2native_int16(
1165                                                            ldns_rr_rrsig_keytag(cur_sig))
1166                                                     == ldns_calc_keytag(cur_key)) {
1167                                                         if (ldns_verify_rrsig(domain_keys,
1168                                                                                            cur_sig,
1169                                                                                            cur_key)
1170                                                             == LDNS_STATUS_OK) {
1171                 
1172                                                                 /* Push the whole rrset 
1173                                                                    -- we can't do much more */
1174                                                                 for (key_k=0;
1175                                                                         key_k<ldns_rr_list_rr_count(
1176                                                                                         domain_keys);
1177                                                                         key_k++) {
1178                                                                         ldns_rr_list_push_rr(
1179                                                                             trusted_keys,
1180                                                                             ldns_rr_clone(
1181                                                                                    ldns_rr_list_rr(
1182                                                                                           domain_keys,
1183                                                                                           key_k)));
1184                                                                 }
1185                 
1186                                                                 ldns_rr_list_deep_free(domain_keys);
1187                                                                 ldns_rr_list_deep_free(domain_sigs);
1188                                                                 ldns_pkt_free(keypkt);
1189                                                                 return trusted_keys;
1190                                                         }
1191                                                 }
1192                                         }
1193           
1194                                         /* Only push our trusted key */
1195                                         ldns_rr_list_push_rr(trusted_keys,
1196                                                                          ldns_rr_clone(cur_key));
1197                                 }
1198                         }
1199                 }
1200
1201                 ldns_rr_list_deep_free(domain_keys);
1202                 ldns_rr_list_deep_free(domain_sigs);
1203                 ldns_pkt_free(keypkt);
1204
1205         } else {
1206                 /* LDNS_STATUS_CRYPTO_NO_DNSKEY */
1207         }
1208     
1209         return trusted_keys;
1210 }
1211
1212 ldns_rr_list *
1213 ldns_validate_domain_ds(const ldns_resolver *res,
1214                                     const ldns_rdf * domain,
1215                                     const ldns_rr_list * keys)
1216 {
1217         ldns_pkt * dspkt;
1218         uint16_t key_i;
1219         ldns_rr_list * rrset = NULL;
1220         ldns_rr_list * sigs = NULL;
1221         ldns_rr_list * trusted_keys = NULL;
1222
1223         /* Fetch DS for the domain */
1224         dspkt = ldns_resolver_query(res, domain,
1225                 LDNS_RR_TYPE_DS, LDNS_RR_CLASS_IN, LDNS_RD);
1226         if (dspkt) {
1227                 rrset = ldns_pkt_rr_list_by_type(dspkt,
1228                                                                    LDNS_RR_TYPE_DS,
1229                                                                    LDNS_SECTION_ANSWER);
1230                 sigs = ldns_pkt_rr_list_by_type(dspkt,
1231                                                                   LDNS_RR_TYPE_RRSIG,
1232                                                                   LDNS_SECTION_ANSWER);
1233
1234                 /* Validate sigs */
1235                 if (ldns_verify(rrset, sigs, keys, NULL) == LDNS_STATUS_OK) {
1236                         trusted_keys = ldns_rr_list_new();
1237                         for (key_i=0; key_i<ldns_rr_list_rr_count(rrset); key_i++) {
1238                                 ldns_rr_list_push_rr(trusted_keys,
1239                                                                  ldns_rr_clone(ldns_rr_list_rr(rrset,
1240                                                                                                                  key_i)
1241                                                                                         )
1242                                                                  );
1243                         }
1244                 }
1245
1246                 ldns_rr_list_deep_free(rrset);
1247                 ldns_rr_list_deep_free(sigs);
1248                 ldns_pkt_free(dspkt);
1249
1250         } else {
1251                 /* LDNS_STATUS_CRYPTO_NO_DS */
1252         }
1253
1254         return trusted_keys;
1255 }
1256
1257 ldns_status
1258 ldns_verify_trusted(ldns_resolver *res,
1259                                 ldns_rr_list *rrset,
1260                                 ldns_rr_list * rrsigs,
1261                                 ldns_rr_list * validating_keys)
1262 {
1263         uint16_t sig_i; uint16_t key_i;
1264         ldns_rr * cur_sig; ldns_rr * cur_key;
1265         ldns_rr_list * trusted_keys = NULL;
1266         ldns_status result = LDNS_STATUS_ERR;
1267
1268         if (!res || !rrset || !rrsigs) {
1269                 return LDNS_STATUS_ERR;
1270         }
1271
1272         if (ldns_rr_list_rr_count(rrset) < 1) {
1273                 return LDNS_STATUS_ERR;
1274         }
1275
1276         if (ldns_rr_list_rr_count(rrsigs) < 1) {
1277                 return LDNS_STATUS_CRYPTO_NO_RRSIG;
1278         }
1279   
1280         /* Look at each sig */
1281         for (sig_i=0; sig_i < ldns_rr_list_rr_count(rrsigs); sig_i++) {
1282
1283                 cur_sig = ldns_rr_list_rr(rrsigs, sig_i);
1284                 /* Get a valid signer key and validate the sig */
1285                 if ((trusted_keys = ldns_fetch_valid_domain_keys(
1286                                                     res,
1287                                                     ldns_rr_rrsig_signame(cur_sig),
1288                                                     ldns_resolver_dnssec_anchors(res),
1289                                                     &result))) {
1290
1291                         for (key_i = 0;
1292                                 key_i < ldns_rr_list_rr_count(trusted_keys);
1293                                 key_i++) {
1294                                 cur_key = ldns_rr_list_rr(trusted_keys, key_i);
1295
1296                                 if ((result = ldns_verify_rrsig(rrset,
1297                                                                                   cur_sig,
1298                                                                                   cur_key))
1299                                     == LDNS_STATUS_OK) {
1300                                         if (validating_keys) {
1301                                                 ldns_rr_list_push_rr(validating_keys,
1302                                                                                  ldns_rr_clone(cur_key));
1303                                         }
1304                                         ldns_rr_list_deep_free(trusted_keys);
1305                                         return LDNS_STATUS_OK;
1306                                 } else {
1307                                         ldns_rr_list_print(stdout, rrset);
1308                                         ldns_rr_print(stdout, cur_sig);
1309                                         ldns_rr_print(stdout, cur_key);
1310                 
1311                                 }
1312                         }
1313                 }
1314         }
1315
1316         ldns_rr_list_deep_free(trusted_keys);
1317         return result;
1318 }
1319
1320 ldns_status
1321 ldns_dnssec_verify_denial(ldns_rr *rr,
1322                           ldns_rr_list *nsecs,
1323                           ldns_rr_list *rrsigs)
1324 {
1325         ldns_rdf *rr_name;
1326         ldns_rdf *wildcard_name;
1327         ldns_rdf *chopped_dname;
1328         ldns_rr *cur_nsec;
1329         size_t i;
1330         ldns_status result;
1331         /* needed for wildcard check on exact match */
1332         ldns_rr *rrsig;
1333         bool name_covered = false;
1334         bool type_covered = false;
1335         bool wildcard_covered = false;
1336         bool wildcard_type_covered = false;
1337
1338         wildcard_name = ldns_dname_new_frm_str("*");
1339         rr_name = ldns_rr_owner(rr);
1340         chopped_dname = ldns_dname_left_chop(rr_name);
1341         result = ldns_dname_cat(wildcard_name, chopped_dname);
1342         if (result != LDNS_STATUS_OK) {
1343                 return result;
1344         }
1345         
1346         ldns_rdf_deep_free(chopped_dname);
1347         
1348         for  (i = 0; i < ldns_rr_list_rr_count(nsecs); i++) {
1349                 cur_nsec = ldns_rr_list_rr(nsecs, i);
1350                 if (ldns_dname_compare(rr_name, ldns_rr_owner(cur_nsec)) == 0) {
1351                         /* see section 5.4 of RFC4035, if the label count of the NSEC's
1352                            RRSIG is equal, then it is proven that wildcard expansion 
1353                            could not have been used to match the request */
1354                         rrsig = ldns_dnssec_get_rrsig_for_name_and_type(
1355                                           ldns_rr_owner(cur_nsec),
1356                                           ldns_rr_get_type(cur_nsec),
1357                                           rrsigs);
1358                         if (rrsig && ldns_rdf2native_int8(ldns_rr_rrsig_labels(rrsig))
1359                             == ldns_dname_label_count(rr_name)) {
1360                                 wildcard_covered = true;
1361                         }
1362                         
1363                         if (ldns_nsec_bitmap_covers_type(ldns_nsec_get_bitmap(cur_nsec),
1364                                                                            ldns_rr_get_type(rr))) {
1365                                 type_covered = true;
1366                         }
1367                 }
1368                 if (ldns_nsec_covers_name(cur_nsec, rr_name)) {
1369                         name_covered = true;
1370                 }
1371                 
1372                 if (ldns_dname_compare(wildcard_name,
1373                                                    ldns_rr_owner(cur_nsec)) == 0) {
1374                         if (ldns_nsec_bitmap_covers_type(ldns_nsec_get_bitmap(cur_nsec),
1375                                                                            ldns_rr_get_type(rr))) {
1376                                 wildcard_type_covered = true;
1377                         }
1378                 }
1379                 
1380                 if (ldns_nsec_covers_name(cur_nsec, wildcard_name)) {
1381                         wildcard_covered = true;
1382                 }
1383                 
1384         }
1385         
1386         ldns_rdf_deep_free(wildcard_name);
1387         
1388         if (type_covered || !name_covered) {
1389                 return LDNS_STATUS_DNSSEC_NSEC_RR_NOT_COVERED;
1390         }
1391         
1392         if (wildcard_type_covered || !wildcard_covered) {
1393                 return LDNS_STATUS_DNSSEC_NSEC_WILDCARD_NOT_COVERED;
1394         }
1395
1396         return LDNS_STATUS_OK;
1397 }
1398
1399 #ifdef HAVE_SSL
1400 ldns_status
1401 ldns_dnssec_verify_denial_nsec3(ldns_rr *rr,
1402                                                   ldns_rr_list *nsecs,
1403                                                   ldns_rr_list *rrsigs,
1404                                                   ldns_pkt_rcode packet_rcode,
1405                                                   ldns_rr_type packet_qtype,
1406                                                   bool packet_nodata)
1407 {
1408         ldns_rdf *closest_encloser;
1409         ldns_rdf *wildcard;
1410         ldns_rdf *hashed_wildcard_name;
1411         bool wildcard_covered = false;
1412         ldns_rdf *zone_name;
1413         ldns_rdf *hashed_name;
1414         size_t i;
1415         ldns_status result = LDNS_STATUS_DNSSEC_NSEC_RR_NOT_COVERED;
1416
1417         rrsigs = rrsigs;
1418
1419         zone_name = ldns_dname_left_chop(ldns_rr_owner(ldns_rr_list_rr(nsecs,0)));
1420
1421         /* section 8.4 */
1422         if (packet_rcode == LDNS_RCODE_NXDOMAIN) {
1423                 closest_encloser = ldns_dnssec_nsec3_closest_encloser(
1424                                                    ldns_rr_owner(rr),
1425                                                    ldns_rr_get_type(rr),
1426                                                    nsecs);
1427                 if(!closest_encloser) {
1428                         result = LDNS_STATUS_NSEC3_ERR;
1429                         goto done;
1430                 }
1431
1432                 wildcard = ldns_dname_new_frm_str("*");
1433                 (void) ldns_dname_cat(wildcard, closest_encloser);
1434
1435                 for (i = 0; i < ldns_rr_list_rr_count(nsecs); i++) {
1436                         hashed_wildcard_name =
1437                                 ldns_nsec3_hash_name_frm_nsec3(ldns_rr_list_rr(nsecs, 0),
1438                                                                                  wildcard
1439                                                                                  );
1440                         (void) ldns_dname_cat(hashed_wildcard_name, zone_name);
1441
1442                         if (ldns_nsec_covers_name(ldns_rr_list_rr(nsecs, i),
1443                                                                  hashed_wildcard_name)) {
1444                                 wildcard_covered = true;
1445                         }
1446                         ldns_rdf_deep_free(hashed_wildcard_name);
1447                 }
1448
1449                 ldns_rdf_deep_free(closest_encloser);
1450                 ldns_rdf_deep_free(wildcard);
1451
1452                 if (!wildcard_covered) {
1453                         result = LDNS_STATUS_DNSSEC_NSEC_WILDCARD_NOT_COVERED;
1454                 } else if (closest_encloser && wildcard_covered) {
1455                         result = LDNS_STATUS_OK;
1456                 } else {
1457                         result = LDNS_STATUS_DNSSEC_NSEC_RR_NOT_COVERED;
1458                 }
1459         } else if (packet_nodata && packet_qtype != LDNS_RR_TYPE_DS) {
1460                 /* section 8.5 */
1461                 hashed_name = ldns_nsec3_hash_name_frm_nsec3(
1462                                    ldns_rr_list_rr(nsecs, 0),
1463                                    ldns_rr_owner(rr));
1464                 (void) ldns_dname_cat(hashed_name, zone_name);
1465                 for (i = 0; i < ldns_rr_list_rr_count(nsecs); i++) {
1466                         if (ldns_dname_compare(hashed_name,
1467                                  ldns_rr_owner(ldns_rr_list_rr(nsecs, i)))
1468                             == 0) {
1469                                 if (!ldns_nsec_bitmap_covers_type(
1470                                             ldns_nsec3_bitmap(ldns_rr_list_rr(nsecs, i)),
1471                                             packet_qtype)
1472                                     && 
1473                                     !ldns_nsec_bitmap_covers_type(
1474                                             ldns_nsec3_bitmap(ldns_rr_list_rr(nsecs, i)),
1475                                             LDNS_RR_TYPE_CNAME)) {
1476                                         result = LDNS_STATUS_OK;
1477                                         goto done;
1478                                 }
1479                         }
1480                 }
1481                 result = LDNS_STATUS_DNSSEC_NSEC_RR_NOT_COVERED;
1482         } else if (packet_nodata && packet_qtype == LDNS_RR_TYPE_DS) {
1483                 /* section 8.6 */
1484                 /* note: up to XXX this is the same as for 8.5 */
1485                 hashed_name = ldns_nsec3_hash_name_frm_nsec3(ldns_rr_list_rr(nsecs,
1486                                                                                                                  0),
1487                                                                                         ldns_rr_owner(rr)
1488                                                                                         );
1489                 (void) ldns_dname_cat(hashed_name, zone_name);
1490                 for (i = 0; i < ldns_rr_list_rr_count(nsecs); i++) {
1491                         if (ldns_dname_compare(hashed_name,
1492                                                            ldns_rr_owner(ldns_rr_list_rr(nsecs,
1493                                                                                                            i)))
1494                             == 0) {
1495                                 if (!ldns_nsec_bitmap_covers_type(
1496                                             ldns_nsec3_bitmap(ldns_rr_list_rr(nsecs, i)),
1497                                             LDNS_RR_TYPE_DS)
1498                                     && 
1499                                     !ldns_nsec_bitmap_covers_type(
1500                                             ldns_nsec3_bitmap(ldns_rr_list_rr(nsecs, i)),
1501                                             LDNS_RR_TYPE_CNAME)) {
1502                                         result = LDNS_STATUS_OK;
1503                                         goto done;
1504                                 }
1505                         }
1506                 }
1507
1508                 /* XXX see note above */
1509                 result = LDNS_STATUS_DNSSEC_NSEC_RR_NOT_COVERED;
1510         }
1511
1512  done:
1513         ldns_rdf_deep_free(zone_name);
1514         return result;
1515 }
1516 #endif /* HAVE_SSL */
1517
1518 #ifdef USE_GOST
1519 EVP_PKEY*
1520 ldns_gost2pkey_raw(unsigned char* key, size_t keylen)
1521 {
1522         /* prefix header for X509 encoding */
1523         uint8_t asn[37] = { 0x30, 0x63, 0x30, 0x1c, 0x06, 0x06, 0x2a, 0x85, 
1524                 0x03, 0x02, 0x02, 0x13, 0x30, 0x12, 0x06, 0x07, 0x2a, 0x85, 
1525                 0x03, 0x02, 0x02, 0x23, 0x01, 0x06, 0x07, 0x2a, 0x85, 0x03, 
1526                 0x02, 0x02, 0x1e, 0x01, 0x03, 0x43, 0x00, 0x04, 0x40};
1527         unsigned char encoded[37+64];
1528         const unsigned char* pp;
1529         if(keylen != 64) {
1530                 /* key wrong size */
1531                 return NULL;
1532         }
1533
1534         /* create evp_key */
1535         memmove(encoded, asn, 37);
1536         memmove(encoded+37, key, 64);
1537         pp = (unsigned char*)&encoded[0];
1538
1539         return d2i_PUBKEY(NULL, &pp, (int)sizeof(encoded));
1540 }
1541
1542 static ldns_status
1543 ldns_verify_rrsig_gost_raw(unsigned char* sig, size_t siglen, 
1544         ldns_buffer* rrset, unsigned char* key, size_t keylen)
1545 {
1546         EVP_PKEY *evp_key;
1547         ldns_status result;
1548
1549         (void) ldns_key_EVP_load_gost_id();
1550         evp_key = ldns_gost2pkey_raw(key, keylen);
1551         if(!evp_key) {
1552                 /* could not convert key */
1553                 return LDNS_STATUS_CRYPTO_BOGUS;
1554         }
1555
1556         /* verify signature */
1557         result = ldns_verify_rrsig_evp_raw(sig, siglen, rrset, 
1558                 evp_key, EVP_get_digestbyname("md_gost94"));
1559         EVP_PKEY_free(evp_key);
1560
1561         return result;
1562 }
1563 #endif
1564
1565 #ifdef USE_ECDSA
1566 EVP_PKEY*
1567 ldns_ecdsa2pkey_raw(unsigned char* key, size_t keylen, uint8_t algo)
1568 {
1569         unsigned char buf[256+2]; /* sufficient for 2*384/8+1 */
1570         const unsigned char* pp = buf;
1571         EVP_PKEY *evp_key;
1572         EC_KEY *ec;
1573         /* check length, which uncompressed must be 2 bignums */
1574         if(algo == LDNS_ECDSAP256SHA256) {
1575                 if(keylen != 2*256/8) return NULL;
1576                 ec = EC_KEY_new_by_curve_name(NID_X9_62_prime256v1);
1577         } else if(algo == LDNS_ECDSAP384SHA384) {
1578                 if(keylen != 2*384/8) return NULL;
1579                 ec = EC_KEY_new_by_curve_name(NID_secp384r1);
1580         } else    ec = NULL;
1581         if(!ec) return NULL;
1582         if(keylen+1 > sizeof(buf))
1583                 return NULL; /* sanity check */
1584         /* prepend the 0x02 (from docs) (or actually 0x04 from implementation
1585          * of openssl) for uncompressed data */
1586         buf[0] = POINT_CONVERSION_UNCOMPRESSED;
1587         memmove(buf+1, key, keylen);
1588         if(!o2i_ECPublicKey(&ec, &pp, (int)keylen+1)) {
1589                 EC_KEY_free(ec);
1590                 return NULL;
1591         }
1592         evp_key = EVP_PKEY_new();
1593         if(!evp_key) {
1594                 EC_KEY_free(ec);
1595                 return NULL;
1596         }
1597         EVP_PKEY_assign_EC_KEY(evp_key, ec);
1598         return evp_key;
1599 }
1600
1601 static ldns_status
1602 ldns_verify_rrsig_ecdsa_raw(unsigned char* sig, size_t siglen, 
1603         ldns_buffer* rrset, unsigned char* key, size_t keylen, uint8_t algo)
1604 {
1605         EVP_PKEY *evp_key;
1606         ldns_status result;
1607         const EVP_MD *d;
1608
1609         evp_key = ldns_ecdsa2pkey_raw(key, keylen, algo);
1610         if(!evp_key) {
1611                 /* could not convert key */
1612                 return LDNS_STATUS_CRYPTO_BOGUS;
1613         }
1614         if(algo == LDNS_ECDSAP256SHA256)
1615                 d = EVP_sha256();
1616         else    d = EVP_sha384(); /* LDNS_ECDSAP384SHA384 */
1617         result = ldns_verify_rrsig_evp_raw(sig, siglen, rrset, evp_key, d);
1618         EVP_PKEY_free(evp_key);
1619         return result;
1620 }
1621 #endif
1622
1623 ldns_status
1624 ldns_verify_rrsig_buffers(ldns_buffer *rawsig_buf, ldns_buffer *verify_buf, 
1625                                          ldns_buffer *key_buf, uint8_t algo)
1626 {
1627         return ldns_verify_rrsig_buffers_raw(
1628                          (unsigned char*)ldns_buffer_begin(rawsig_buf),
1629                          ldns_buffer_position(rawsig_buf),
1630                          verify_buf,
1631                          (unsigned char*)ldns_buffer_begin(key_buf), 
1632                          ldns_buffer_position(key_buf), algo);
1633 }
1634
1635 ldns_status
1636 ldns_verify_rrsig_buffers_raw(unsigned char* sig, size_t siglen,
1637                                                 ldns_buffer *verify_buf, unsigned char* key, size_t keylen, 
1638                                                 uint8_t algo)
1639 {
1640         /* check for right key */
1641         switch(algo) {
1642         case LDNS_DSA:
1643         case LDNS_DSA_NSEC3:
1644                 return ldns_verify_rrsig_dsa_raw(sig,
1645                                                                    siglen,
1646                                                                    verify_buf,
1647                                                                    key,
1648                                                                    keylen);
1649                 break;
1650         case LDNS_RSASHA1:
1651         case LDNS_RSASHA1_NSEC3:
1652                 return ldns_verify_rrsig_rsasha1_raw(sig,
1653                                                                           siglen,
1654                                                                           verify_buf,
1655                                                                           key,
1656                                                                           keylen);
1657                 break;
1658 #ifdef USE_SHA2
1659         case LDNS_RSASHA256:
1660                 return ldns_verify_rrsig_rsasha256_raw(sig,
1661                                                                             siglen,
1662                                                                             verify_buf,
1663                                                                             key,
1664                                                                             keylen);
1665                 break;
1666         case LDNS_RSASHA512:
1667                 return ldns_verify_rrsig_rsasha512_raw(sig,
1668                                                                             siglen,
1669                                                                             verify_buf,
1670                                                                             key,
1671                                                                             keylen);
1672                 break;
1673 #endif
1674 #ifdef USE_GOST
1675         case LDNS_ECC_GOST:
1676                 return ldns_verify_rrsig_gost_raw(sig, siglen, verify_buf,
1677                         key, keylen);
1678                 break;
1679 #endif
1680 #ifdef USE_ECDSA
1681         case LDNS_ECDSAP256SHA256:
1682         case LDNS_ECDSAP384SHA384:
1683                 return ldns_verify_rrsig_ecdsa_raw(sig, siglen, verify_buf,
1684                         key, keylen, algo);
1685                 break;
1686 #endif
1687         case LDNS_RSAMD5:
1688                 return ldns_verify_rrsig_rsamd5_raw(sig,
1689                                                                          siglen,
1690                                                                          verify_buf,
1691                                                                          key,
1692                                                                          keylen);
1693                 break;
1694         default:
1695                 /* do you know this alg?! */
1696                 return LDNS_STATUS_CRYPTO_UNKNOWN_ALGO;
1697         }
1698 }
1699
1700
1701 /**
1702  * Reset the ttl in the rrset with the orig_ttl from the sig 
1703  * and update owner name if it was wildcard 
1704  * Also canonicalizes the rrset.
1705  * @param rrset: rrset to modify
1706  * @param sig: signature to take TTL and wildcard values from
1707  */
1708 static void
1709 ldns_rrset_use_signature_ttl(ldns_rr_list* rrset_clone, ldns_rr* rrsig)
1710 {
1711         uint32_t orig_ttl;
1712         uint16_t i;
1713         uint8_t label_count;
1714         ldns_rdf *wildcard_name;
1715         ldns_rdf *wildcard_chopped;
1716         ldns_rdf *wildcard_chopped_tmp;
1717
1718         orig_ttl = ldns_rdf2native_int32( ldns_rr_rdf(rrsig, 3));
1719         label_count = ldns_rdf2native_int8(ldns_rr_rdf(rrsig, 2));
1720
1721         for(i = 0; i < ldns_rr_list_rr_count(rrset_clone); i++) {
1722                 if (label_count < 
1723                     ldns_dname_label_count(
1724                            ldns_rr_owner(ldns_rr_list_rr(rrset_clone, i)))) {
1725                         (void) ldns_str2rdf_dname(&wildcard_name, "*");
1726                         wildcard_chopped = ldns_rdf_clone(ldns_rr_owner(
1727                                 ldns_rr_list_rr(rrset_clone, i)));
1728                         while (label_count < ldns_dname_label_count(wildcard_chopped)) {
1729                                 wildcard_chopped_tmp = ldns_dname_left_chop(
1730                                         wildcard_chopped);
1731                                 ldns_rdf_deep_free(wildcard_chopped);
1732                                 wildcard_chopped = wildcard_chopped_tmp;
1733                         }
1734                         (void) ldns_dname_cat(wildcard_name, wildcard_chopped);
1735                         ldns_rdf_deep_free(wildcard_chopped);
1736                         ldns_rdf_deep_free(ldns_rr_owner(ldns_rr_list_rr(
1737                                 rrset_clone, i)));
1738                         ldns_rr_set_owner(ldns_rr_list_rr(rrset_clone, i), 
1739                                 wildcard_name);
1740                 }
1741                 ldns_rr_set_ttl(ldns_rr_list_rr(rrset_clone, i), orig_ttl);
1742                 /* convert to lowercase */
1743                 ldns_rr2canonical(ldns_rr_list_rr(rrset_clone, i));
1744         }
1745 }
1746
1747 /**
1748  * Make raw signature buffer out of rrsig
1749  * @param rawsig_buf: raw signature buffer for result
1750  * @param rrsig: signature to convert
1751  * @return OK or more specific error.
1752  */
1753 static ldns_status
1754 ldns_rrsig2rawsig_buffer(ldns_buffer* rawsig_buf, ldns_rr* rrsig)
1755 {
1756         uint8_t sig_algo = ldns_rdf2native_int8(ldns_rr_rdf(rrsig, 1));
1757         /* check for known and implemented algo's now (otherwise 
1758          * the function could return a wrong error
1759          */
1760         /* create a buffer with signature rdata */
1761         /* for some algorithms we need other data than for others... */
1762         /* (the DSA API wants DER encoding for instance) */
1763
1764         switch(sig_algo) {
1765         case LDNS_RSAMD5:
1766         case LDNS_RSASHA1:
1767         case LDNS_RSASHA1_NSEC3:
1768 #ifdef USE_SHA2
1769         case LDNS_RSASHA256:
1770         case LDNS_RSASHA512:
1771 #endif
1772 #ifdef USE_GOST
1773         case LDNS_ECC_GOST:
1774 #endif
1775                 if (ldns_rdf2buffer_wire(rawsig_buf, 
1776                     ldns_rr_rdf(rrsig, 8)) != LDNS_STATUS_OK) {
1777                         return LDNS_STATUS_MEM_ERR;
1778                 }
1779                 break;
1780         case LDNS_DSA:
1781         case LDNS_DSA_NSEC3:
1782                 /* EVP takes rfc2459 format, which is a tad longer than dns format */
1783                 if (ldns_convert_dsa_rrsig_rdf2asn1(rawsig_buf, 
1784                         ldns_rr_rdf(rrsig, 8)) != LDNS_STATUS_OK) {
1785                         /*
1786                           if (ldns_rdf2buffer_wire(rawsig_buf,
1787                           ldns_rr_rdf(rrsig, 8)) != LDNS_STATUS_OK) {
1788                         */
1789                         return LDNS_STATUS_MEM_ERR;
1790                 }
1791                 break;
1792 #ifdef USE_ECDSA
1793         case LDNS_ECDSAP256SHA256:
1794         case LDNS_ECDSAP384SHA384:
1795                 /* EVP produces an ASN prefix on the signature, which is
1796                  * not used in the DNS */
1797                 if (ldns_convert_ecdsa_rrsig_rdf2asn1(rawsig_buf, 
1798                         ldns_rr_rdf(rrsig, 8)) != LDNS_STATUS_OK) {
1799                         return LDNS_STATUS_MEM_ERR;
1800                 }
1801                 break;
1802 #endif
1803         case LDNS_DH:
1804         case LDNS_ECC:
1805         case LDNS_INDIRECT:
1806                 return LDNS_STATUS_CRYPTO_ALGO_NOT_IMPL;
1807         default:
1808                 return LDNS_STATUS_CRYPTO_UNKNOWN_ALGO;
1809         }
1810         return LDNS_STATUS_OK;
1811 }
1812
1813 /**
1814  * Check RRSIG timestamps against the given 'now' time.
1815  * @param rrsig: signature to check.
1816  * @param now: the current time in seconds epoch.
1817  * @return status code LDNS_STATUS_OK if all is fine.
1818  */
1819 static ldns_status
1820 ldns_rrsig_check_timestamps(ldns_rr* rrsig, int32_t now)
1821 {
1822         int32_t inception, expiration;
1823         
1824         /* check the signature time stamps */
1825         inception = (int32_t)ldns_rdf2native_time_t(
1826                 ldns_rr_rrsig_inception(rrsig));
1827         expiration = (int32_t)ldns_rdf2native_time_t(
1828                 ldns_rr_rrsig_expiration(rrsig));
1829
1830         if (expiration - inception < 0) {
1831                 /* bad sig, expiration before inception?? Tsssg */
1832                 return LDNS_STATUS_CRYPTO_EXPIRATION_BEFORE_INCEPTION;
1833         }
1834         if (now - inception < 0) {
1835                 /* bad sig, inception date has not yet come to pass */
1836                 return LDNS_STATUS_CRYPTO_SIG_NOT_INCEPTED;
1837         }
1838         if (expiration - now < 0) {
1839                 /* bad sig, expiration date has passed */
1840                 return LDNS_STATUS_CRYPTO_SIG_EXPIRED;
1841         }
1842         return LDNS_STATUS_OK;
1843 }
1844
1845 /**
1846  * Prepare for verification.
1847  * @param rawsig_buf: raw signature buffer made ready.
1848  * @param verify_buf: data for verification buffer made ready.
1849  * @param rrset_clone: made ready.
1850  * @param rrsig: signature to prepare for.
1851  * @return LDNS_STATUS_OK is all went well. Otherwise specific error.
1852  */
1853 static ldns_status
1854 ldns_prepare_for_verify(ldns_buffer* rawsig_buf, ldns_buffer* verify_buf, 
1855         ldns_rr_list* rrset_clone, ldns_rr* rrsig)
1856 {
1857         ldns_status result;
1858
1859         /* canonicalize the sig */
1860         ldns_dname2canonical(ldns_rr_owner(rrsig));
1861         
1862         /* check if the typecovered is equal to the type checked */
1863         if (ldns_rdf2rr_type(ldns_rr_rrsig_typecovered(rrsig)) !=
1864             ldns_rr_get_type(ldns_rr_list_rr(rrset_clone, 0)))
1865                 return LDNS_STATUS_CRYPTO_TYPE_COVERED_ERR;
1866         
1867         /* create a buffer with b64 signature rdata */
1868         result = ldns_rrsig2rawsig_buffer(rawsig_buf, rrsig);
1869         if(result != LDNS_STATUS_OK)
1870                 return result;
1871
1872         /* use TTL from signature. Use wildcard names for wildcards */
1873         /* also canonicalizes rrset_clone */
1874         ldns_rrset_use_signature_ttl(rrset_clone, rrsig);
1875
1876         /* sort the rrset in canonical order  */
1877         ldns_rr_list_sort(rrset_clone);
1878
1879         /* put the signature rr (without the b64) to the verify_buf */
1880         if (ldns_rrsig2buffer_wire(verify_buf, rrsig) != LDNS_STATUS_OK)
1881                 return LDNS_STATUS_MEM_ERR;
1882
1883         /* add the rrset in verify_buf */
1884         if(ldns_rr_list2buffer_wire(verify_buf, rrset_clone) 
1885                 != LDNS_STATUS_OK)
1886                 return LDNS_STATUS_MEM_ERR;
1887
1888         return LDNS_STATUS_OK;
1889 }
1890
1891 /**
1892  * Check if a key matches a signature.
1893  * Checks keytag, sigalgo and signature.
1894  * @param rawsig_buf: raw signature buffer for verify
1895  * @param verify_buf: raw data buffer for verify
1896  * @param rrsig: the rrsig
1897  * @param key: key to attempt.
1898  * @return LDNS_STATUS_OK if OK, else some specific error.
1899  */
1900 static ldns_status
1901 ldns_verify_test_sig_key(ldns_buffer* rawsig_buf, ldns_buffer* verify_buf, 
1902         ldns_rr* rrsig, ldns_rr* key)
1903 {
1904         uint8_t sig_algo = ldns_rdf2native_int8(ldns_rr_rdf(rrsig, 1));
1905
1906         /* before anything, check if the keytags match */
1907         if (ldns_calc_keytag(key)
1908             ==
1909             ldns_rdf2native_int16(ldns_rr_rrsig_keytag(rrsig))
1910             ) {
1911                 ldns_buffer* key_buf = ldns_buffer_new(LDNS_MAX_PACKETLEN);
1912                 ldns_status result = LDNS_STATUS_ERR;
1913
1914                 /* put the key-data in a buffer, that's the third rdf, with
1915                  * the base64 encoded key data */
1916                 if (ldns_rdf2buffer_wire(key_buf, ldns_rr_rdf(key, 3)) 
1917                         != LDNS_STATUS_OK) {
1918                         ldns_buffer_free(key_buf); 
1919                         /* returning is bad might screw up
1920                            good keys later in the list
1921                            what to do? */
1922                         return LDNS_STATUS_ERR;
1923                 }
1924
1925                 if (sig_algo == ldns_rdf2native_int8(ldns_rr_rdf(key, 2))) {
1926                         result = ldns_verify_rrsig_buffers(rawsig_buf, 
1927                                 verify_buf, key_buf, sig_algo);
1928                 } else {
1929                         /* No keys with the corresponding algorithm are found */
1930                         result = LDNS_STATUS_CRYPTO_NO_MATCHING_KEYTAG_DNSKEY;
1931                 }
1932
1933                 ldns_buffer_free(key_buf); 
1934                 return result;
1935         }
1936         else {
1937                 /* No keys with the corresponding keytag are found */
1938                 return LDNS_STATUS_CRYPTO_NO_MATCHING_KEYTAG_DNSKEY;
1939         }
1940 }
1941
1942 /* 
1943  * to verify:
1944  * - create the wire fmt of the b64 key rdata
1945  * - create the wire fmt of the sorted rrset
1946  * - create the wire fmt of the b64 sig rdata
1947  * - create the wire fmt of the sig without the b64 rdata
1948  * - cat the sig data (without b64 rdata) to the rrset
1949  * - verify the rrset+sig, with the b64 data and the b64 key data
1950  */
1951 ldns_status
1952 ldns_verify_rrsig_keylist(ldns_rr_list *rrset,
1953                                          ldns_rr *rrsig,
1954                                          const ldns_rr_list *keys, 
1955                                          ldns_rr_list *good_keys)
1956 {
1957         ldns_status result;
1958         ldns_rr_list *valid = ldns_rr_list_new();
1959         if (!valid)
1960                 return LDNS_STATUS_MEM_ERR;
1961
1962         result = ldns_verify_rrsig_keylist_notime(rrset, rrsig, keys, valid);
1963         if(result != LDNS_STATUS_OK) {
1964                 ldns_rr_list_free(valid); 
1965                 return result;
1966         }
1967
1968         /* check timestamps last; its OK except time */
1969         result = ldns_rrsig_check_timestamps(rrsig, (int32_t)time(NULL));
1970         if(result != LDNS_STATUS_OK) {
1971                 ldns_rr_list_free(valid); 
1972                 return result;
1973         }
1974
1975         ldns_rr_list_cat(good_keys, valid);
1976         ldns_rr_list_free(valid);
1977         return LDNS_STATUS_OK;
1978 }
1979
1980 ldns_status
1981 ldns_verify_rrsig_keylist_notime(ldns_rr_list *rrset,
1982                                          ldns_rr *rrsig,
1983                                          const ldns_rr_list *keys, 
1984                                          ldns_rr_list *good_keys)
1985 {
1986         ldns_buffer *rawsig_buf;
1987         ldns_buffer *verify_buf;
1988         uint16_t i;
1989         ldns_status result, status;
1990         ldns_rr_list *rrset_clone;
1991         ldns_rr_list *validkeys;
1992
1993         if (!rrset) {
1994                 return LDNS_STATUS_ERR;
1995         }
1996
1997         validkeys = ldns_rr_list_new();
1998         if (!validkeys) {
1999                 return LDNS_STATUS_MEM_ERR;
2000         }
2001         
2002         /* clone the rrset so that we can fiddle with it */
2003         rrset_clone = ldns_rr_list_clone(rrset);
2004
2005         /* create the buffers which will certainly hold the raw data */
2006         rawsig_buf = ldns_buffer_new(LDNS_MAX_PACKETLEN);
2007         verify_buf  = ldns_buffer_new(LDNS_MAX_PACKETLEN);
2008
2009         result = ldns_prepare_for_verify(rawsig_buf, verify_buf, 
2010                 rrset_clone, rrsig);
2011         if(result != LDNS_STATUS_OK) {
2012                 ldns_buffer_free(verify_buf);
2013                 ldns_buffer_free(rawsig_buf);
2014                 ldns_rr_list_deep_free(rrset_clone);
2015                 ldns_rr_list_free(validkeys);
2016                 return result;
2017         }
2018
2019         result = LDNS_STATUS_CRYPTO_NO_MATCHING_KEYTAG_DNSKEY;
2020         for(i = 0; i < ldns_rr_list_rr_count(keys); i++) {
2021                 status = ldns_verify_test_sig_key(rawsig_buf, verify_buf, 
2022                         rrsig, ldns_rr_list_rr(keys, i));
2023                 if (status == LDNS_STATUS_OK) {
2024                         /* one of the keys has matched, don't break
2025                          * here, instead put the 'winning' key in
2026                          * the validkey list and return the list 
2027                          * later */
2028                         if (!ldns_rr_list_push_rr(validkeys, 
2029                                 ldns_rr_list_rr(keys,i))) {
2030                                 /* couldn't push the key?? */
2031                                 ldns_buffer_free(rawsig_buf);
2032                                 ldns_buffer_free(verify_buf);
2033                                 ldns_rr_list_deep_free(rrset_clone);
2034                                 ldns_rr_list_free(validkeys);
2035                                 return LDNS_STATUS_MEM_ERR;
2036                         }
2037
2038                         result = status;
2039                 }
2040
2041                 if (result == LDNS_STATUS_CRYPTO_NO_MATCHING_KEYTAG_DNSKEY) {
2042                         result = status;
2043                 }
2044         }
2045
2046         /* no longer needed */
2047         ldns_rr_list_deep_free(rrset_clone);
2048         ldns_buffer_free(rawsig_buf);
2049         ldns_buffer_free(verify_buf);
2050
2051         if (ldns_rr_list_rr_count(validkeys) == 0) {
2052                 /* no keys were added, return last error */
2053                 ldns_rr_list_free(validkeys); 
2054                 return result;
2055         }
2056
2057         /* do not check timestamps */
2058
2059         ldns_rr_list_cat(good_keys, validkeys);
2060         ldns_rr_list_free(validkeys);
2061         return LDNS_STATUS_OK;
2062 }
2063
2064 ldns_status
2065 ldns_verify_rrsig(ldns_rr_list *rrset, ldns_rr *rrsig, ldns_rr *key)
2066 {
2067         ldns_buffer *rawsig_buf;
2068         ldns_buffer *verify_buf;
2069         ldns_status result;
2070         ldns_rr_list *rrset_clone;
2071
2072         if (!rrset) {
2073                 return LDNS_STATUS_NO_DATA;
2074         }
2075         /* clone the rrset so that we can fiddle with it */
2076         rrset_clone = ldns_rr_list_clone(rrset);
2077         /* create the buffers which will certainly hold the raw data */
2078         rawsig_buf = ldns_buffer_new(LDNS_MAX_PACKETLEN);
2079         verify_buf  = ldns_buffer_new(LDNS_MAX_PACKETLEN);
2080
2081         result = ldns_prepare_for_verify(rawsig_buf, verify_buf, 
2082                 rrset_clone, rrsig);
2083         if(result != LDNS_STATUS_OK) {
2084                 ldns_rr_list_deep_free(rrset_clone);
2085                 ldns_buffer_free(rawsig_buf);
2086                 ldns_buffer_free(verify_buf);
2087                 return result;
2088         }
2089         result = ldns_verify_test_sig_key(rawsig_buf, verify_buf, 
2090                 rrsig, key);
2091         /* no longer needed */
2092         ldns_rr_list_deep_free(rrset_clone);
2093         ldns_buffer_free(rawsig_buf);
2094         ldns_buffer_free(verify_buf);
2095
2096         /* check timestamp last, apart from time its OK */
2097         if(result == LDNS_STATUS_OK)
2098                 result = ldns_rrsig_check_timestamps(rrsig, 
2099                         (int32_t)time(NULL));
2100
2101         return result;
2102 }
2103
2104 ldns_status
2105 ldns_verify_rrsig_evp(ldns_buffer *sig,
2106                                   ldns_buffer *rrset,
2107                                   EVP_PKEY *key,
2108                                   const EVP_MD *digest_type)
2109 {
2110         return ldns_verify_rrsig_evp_raw(
2111                          (unsigned char*)ldns_buffer_begin(sig),
2112                          ldns_buffer_position(sig),
2113                          rrset,
2114                          key,
2115                          digest_type);
2116 }
2117
2118 ldns_status
2119 ldns_verify_rrsig_evp_raw(unsigned char *sig, size_t siglen, 
2120                                          ldns_buffer *rrset, EVP_PKEY *key, const EVP_MD *digest_type)
2121 {
2122         EVP_MD_CTX ctx;
2123         int res;
2124
2125         EVP_MD_CTX_init(&ctx);
2126         
2127         EVP_VerifyInit(&ctx, digest_type);
2128         EVP_VerifyUpdate(&ctx,
2129                                   ldns_buffer_begin(rrset),
2130                                   ldns_buffer_position(rrset));
2131         res = EVP_VerifyFinal(&ctx, sig, (unsigned int) siglen, key);
2132         
2133         EVP_MD_CTX_cleanup(&ctx);
2134         
2135         if (res == 1) {
2136                 return LDNS_STATUS_OK;
2137         } else if (res == 0) {
2138                 return LDNS_STATUS_CRYPTO_BOGUS;
2139         }
2140         /* TODO how to communicate internal SSL error?
2141            let caller use ssl's get_error() */
2142         return LDNS_STATUS_SSL_ERR;
2143 }
2144
2145 ldns_status
2146 ldns_verify_rrsig_dsa(ldns_buffer *sig, ldns_buffer *rrset, ldns_buffer *key)
2147 {
2148         return ldns_verify_rrsig_dsa_raw(
2149                          (unsigned char*) ldns_buffer_begin(sig),
2150                          ldns_buffer_position(sig),
2151                          rrset,
2152                          (unsigned char*) ldns_buffer_begin(key),
2153                          ldns_buffer_position(key));
2154 }
2155
2156 ldns_status
2157 ldns_verify_rrsig_rsasha1(ldns_buffer *sig, ldns_buffer *rrset, ldns_buffer *key)
2158 {
2159         return ldns_verify_rrsig_rsasha1_raw(
2160                          (unsigned char*)ldns_buffer_begin(sig),
2161                          ldns_buffer_position(sig),
2162                          rrset,
2163                          (unsigned char*) ldns_buffer_begin(key),
2164                          ldns_buffer_position(key));
2165 }
2166
2167 ldns_status
2168 ldns_verify_rrsig_rsamd5(ldns_buffer *sig, ldns_buffer *rrset, ldns_buffer *key)
2169 {
2170         return ldns_verify_rrsig_rsamd5_raw(
2171                          (unsigned char*)ldns_buffer_begin(sig),
2172                          ldns_buffer_position(sig),
2173                          rrset,
2174                          (unsigned char*) ldns_buffer_begin(key),
2175                          ldns_buffer_position(key));
2176 }
2177
2178 ldns_status
2179 ldns_verify_rrsig_dsa_raw(unsigned char* sig, size_t siglen,
2180                                          ldns_buffer* rrset, unsigned char* key, size_t keylen)
2181 {
2182         EVP_PKEY *evp_key;
2183         ldns_status result;
2184
2185         evp_key = EVP_PKEY_new();
2186         EVP_PKEY_assign_DSA(evp_key, ldns_key_buf2dsa_raw(key, keylen));
2187         result = ldns_verify_rrsig_evp_raw(sig,
2188                                                                 siglen,
2189                                                                 rrset,
2190                                                                 evp_key,
2191                                                                 EVP_dss1());
2192         EVP_PKEY_free(evp_key);
2193         return result;
2194
2195 }
2196
2197 ldns_status
2198 ldns_verify_rrsig_rsasha1_raw(unsigned char* sig, size_t siglen,
2199                                                 ldns_buffer* rrset, unsigned char* key, size_t keylen)
2200 {
2201         EVP_PKEY *evp_key;
2202         ldns_status result;
2203
2204         evp_key = EVP_PKEY_new();
2205         EVP_PKEY_assign_RSA(evp_key, ldns_key_buf2rsa_raw(key, keylen));
2206         result = ldns_verify_rrsig_evp_raw(sig,
2207                                                                 siglen,
2208                                                                 rrset,
2209                                                                 evp_key,
2210                                                                 EVP_sha1());
2211         EVP_PKEY_free(evp_key);
2212
2213         return result;
2214 }
2215
2216 ldns_status
2217 ldns_verify_rrsig_rsasha256_raw(unsigned char* sig,
2218                                                   size_t siglen,
2219                                                   ldns_buffer* rrset,
2220                                                   unsigned char* key,
2221                                                   size_t keylen)
2222 {
2223 #ifdef USE_SHA2
2224         EVP_PKEY *evp_key;
2225         ldns_status result;
2226
2227         evp_key = EVP_PKEY_new();
2228         EVP_PKEY_assign_RSA(evp_key, ldns_key_buf2rsa_raw(key, keylen));
2229         result = ldns_verify_rrsig_evp_raw(sig,
2230                                                                 siglen,
2231                                                                 rrset,
2232                                                                 evp_key,
2233                                                                 EVP_sha256());
2234         EVP_PKEY_free(evp_key);
2235
2236         return result;
2237 #else
2238         /* touch these to prevent compiler warnings */
2239         (void) sig;
2240         (void) siglen;
2241         (void) rrset;
2242         (void) key;
2243         (void) keylen;
2244         return LDNS_STATUS_CRYPTO_UNKNOWN_ALGO;
2245 #endif
2246 }
2247
2248 ldns_status
2249 ldns_verify_rrsig_rsasha512_raw(unsigned char* sig,
2250                                                   size_t siglen,
2251                                                   ldns_buffer* rrset,
2252                                                   unsigned char* key,
2253                                                   size_t keylen)
2254 {
2255 #ifdef USE_SHA2
2256         EVP_PKEY *evp_key;
2257         ldns_status result;
2258
2259         evp_key = EVP_PKEY_new();
2260         EVP_PKEY_assign_RSA(evp_key, ldns_key_buf2rsa_raw(key, keylen));
2261         result = ldns_verify_rrsig_evp_raw(sig,
2262                                                                 siglen,
2263                                                                 rrset,
2264                                                                 evp_key,
2265                                                                 EVP_sha512());
2266         EVP_PKEY_free(evp_key);
2267
2268         return result;
2269 #else
2270         /* touch these to prevent compiler warnings */
2271         (void) sig;
2272         (void) siglen;
2273         (void) rrset;
2274         (void) key;
2275         (void) keylen;
2276         return LDNS_STATUS_CRYPTO_UNKNOWN_ALGO;
2277 #endif
2278 }
2279
2280
2281 ldns_status
2282 ldns_verify_rrsig_rsamd5_raw(unsigned char* sig,
2283                                             size_t siglen,
2284                                             ldns_buffer* rrset,
2285                                             unsigned char* key,
2286                                             size_t keylen)
2287 {
2288         EVP_PKEY *evp_key;
2289         ldns_status result;
2290
2291         evp_key = EVP_PKEY_new();
2292         EVP_PKEY_assign_RSA(evp_key, ldns_key_buf2rsa_raw(key, keylen));
2293         result = ldns_verify_rrsig_evp_raw(sig,
2294                                                                 siglen,
2295                                                                 rrset,
2296                                                                 evp_key,
2297                                                                 EVP_md5());
2298         EVP_PKEY_free(evp_key);
2299
2300         return result;
2301 }
2302
2303 #endif