655 return 1;
656}
657
658/** perform b32 encoding of hash */
659static int
660nsec3_calc_b32(struct regional* region, sldns_buffer* buf,
661 struct nsec3_cached_hash* c)
662{
663 int r;
664 sldns_buffer_clear(buf);
665 r = sldns_b32_ntop_extended_hex(c->hash, c->hash_len,
666 (char*)sldns_buffer_begin(buf), sldns_buffer_limit(buf));
667 if(r < 1) {
668 log_err("b32_ntop_extended_hex: error in encoding: %d", r);
669 return 0;
670 }
671 c->b32_len = (size_t)r;
672 c->b32 = regional_alloc_init(region, sldns_buffer_begin(buf),
673 c->b32_len);
674 if(!c->b32)
675 return 0;
676 return 1;
677}
678
679int
680nsec3_hash_name(rbtree_t* table, struct regional* region, sldns_buffer* buf,
681 struct ub_packed_rrset_key* nsec3, int rr, uint8_t* dname,
682 size_t dname_len, struct nsec3_cached_hash** hash)
683{
684 struct nsec3_cached_hash* c;
685 struct nsec3_cached_hash looki;
686#ifdef UNBOUND_DEBUG
687 rbnode_t* n;
688#endif
689 int r;
690 looki.node.key = &looki;
691 looki.nsec3 = nsec3;
692 looki.rr = rr;
693 looki.dname = dname;
694 looki.dname_len = dname_len;
695 /* lookup first in cache */
696 c = (struct nsec3_cached_hash*)rbtree_search(table, &looki);
697 if(c) {
698 *hash = c;
699 return 1;
700 }
701 /* create a new entry */
702 c = (struct nsec3_cached_hash*)regional_alloc(region, sizeof(*c));
703 if(!c) return 0;
704 c->node.key = c;
705 c->nsec3 = nsec3;
706 c->rr = rr;
707 c->dname = dname;
708 c->dname_len = dname_len;
709 r = nsec3_calc_hash(region, buf, c);
710 if(r != 1)
711 return r;
712 r = nsec3_calc_b32(region, buf, c);
713 if(r != 1)
714 return r;
715#ifdef UNBOUND_DEBUG
716 n =
717#else
718 (void)
719#endif
720 rbtree_insert(table, &c->node);
721 log_assert(n); /* cannot be duplicate, just did lookup */
722 *hash = c;
723 return 1;
724}
725
726/**
727 * compare a label lowercased
728 */
729static int
730label_compare_lower(uint8_t* lab1, uint8_t* lab2, size_t lablen)
731{
732 size_t i;
733 for(i=0; i<lablen; i++) {
734 if(tolower((unsigned char)*lab1) != tolower((unsigned char)*lab2)) {
735 if(tolower((unsigned char)*lab1) < tolower((unsigned char)*lab2))
736 return -1;
737 return 1;
738 }
739 lab1++;
740 lab2++;
741 }
742 return 0;
743}
744
745/**
746 * Compare a hashed name with the owner name of an NSEC3 RRset.
747 * @param flt: filter with zone name.
748 * @param hash: the hashed name.
749 * @param s: rrset with owner name.
750 * @return true if matches exactly, false if not.
751 */
752static int
753nsec3_hash_matches_owner(struct nsec3_filter* flt,
754 struct nsec3_cached_hash* hash, struct ub_packed_rrset_key* s)
755{
756 uint8_t* nm = s->rk.dname;
757 /* compare, does hash of name based on params in this NSEC3
758 * match the owner name of this NSEC3?
759 * name must be: <hashlength>base32 . zone name
760 * so; first label must not be root label (not zero length),
761 * and match the b32 encoded hash length,
762 * and the label content match the b32 encoded hash
763 * and the rest must be the zone name.
764 */
765 if(hash->b32_len != 0 && (size_t)nm[0] == hash->b32_len &&
766 label_compare_lower(nm+1, hash->b32, hash->b32_len) == 0 &&
767 query_dname_compare(nm+(size_t)nm[0]+1, flt->zone) == 0) {
768 return 1;
769 }
770 return 0;
771}
772
773/**
774 * Find matching NSEC3
775 * Find the NSEC3Record that matches a hash of a name.
776 * @param env: module environment with temporary region and buffer.
777 * @param flt: the NSEC3 RR filter, contains zone name and RRs.
778 * @param ct: cached hashes table.
779 * @param nm: name to look for.
780 * @param nmlen: length of name.
781 * @param rrset: nsec3 that matches is returned here.
782 * @param rr: rr number in nsec3 rrset that matches.
783 * @return true if a matching NSEC3 is found, false if not.
784 */
785static int
786find_matching_nsec3(struct module_env* env, struct nsec3_filter* flt,
787 rbtree_t* ct, uint8_t* nm, size_t nmlen,
788 struct ub_packed_rrset_key** rrset, int* rr)
789{
790 size_t i_rs;
791 int i_rr;
792 struct ub_packed_rrset_key* s;
793 struct nsec3_cached_hash* hash;
794 int r;
795
796 /* this loop skips other-zone and unknown NSEC3s, also non-NSEC3 RRs */
797 for(s=filter_first(flt, &i_rs, &i_rr); s;
798 s=filter_next(flt, &i_rs, &i_rr)) {
799 /* get name hashed for this NSEC3 RR */
800 r = nsec3_hash_name(ct, env->scratch, env->scratch_buffer,
801 s, i_rr, nm, nmlen, &hash);
802 if(r == 0) {
803 log_err("nsec3: malloc failure");
804 break; /* alloc failure */
805 } else if(r < 0)
806 continue; /* malformed NSEC3 */
807 else if(nsec3_hash_matches_owner(flt, hash, s)) {
808 *rrset = s; /* rrset with this name */
809 *rr = i_rr; /* matches hash with these parameters */
810 return 1;
811 }
812 }
813 *rrset = NULL;
814 *rr = 0;
815 return 0;
816}
817
818int
819nsec3_covers(uint8_t* zone, struct nsec3_cached_hash* hash,
820 struct ub_packed_rrset_key* rrset, int rr, sldns_buffer* buf)
821{
822 uint8_t* next, *owner;
823 size_t nextlen;
824 int len;
825 if(!nsec3_get_nextowner(rrset, rr, &next, &nextlen))
826 return 0; /* malformed RR proves nothing */
827
828 /* check the owner name is a hashed value . apex
829 * base32 encoded values must have equal length.
830 * hash_value and next hash value must have equal length. */
831 if(nextlen != hash->hash_len || hash->hash_len==0||hash->b32_len==0||
832 (size_t)*rrset->rk.dname != hash->b32_len ||
833 query_dname_compare(rrset->rk.dname+1+
834 (size_t)*rrset->rk.dname, zone) != 0)
835 return 0; /* bad lengths or owner name */
836
837 /* This is the "normal case: owner < next and owner < hash < next */
838 if(label_compare_lower(rrset->rk.dname+1, hash->b32,
839 hash->b32_len) < 0 &&
840 memcmp(hash->hash, next, nextlen) < 0)
841 return 1;
842
843 /* convert owner name from text to binary */
844 sldns_buffer_clear(buf);
845 owner = sldns_buffer_begin(buf);
846 len = sldns_b32_pton_extended_hex((char*)rrset->rk.dname+1,
847 hash->b32_len, owner, sldns_buffer_limit(buf));
848 if(len<1)
849 return 0; /* bad owner name in some way */
850 if((size_t)len != hash->hash_len || (size_t)len != nextlen)
851 return 0; /* wrong length */
852
853 /* this is the end of zone case: next <= owner &&
854 * (hash > owner || hash < next)
855 * this also covers the only-apex case of next==owner.
856 */
857 if(memcmp(next, owner, nextlen) <= 0 &&
858 ( memcmp(hash->hash, owner, nextlen) > 0 ||
859 memcmp(hash->hash, next, nextlen) < 0)) {
860 return 1;
861 }
862 return 0;
863}
864
865/**
866 * findCoveringNSEC3
867 * Given a name, find a covering NSEC3 from among a list of NSEC3s.
868 *
869 * @param env: module environment with temporary region and buffer.
870 * @param flt: the NSEC3 RR filter, contains zone name and RRs.
871 * @param ct: cached hashes table.
872 * @param nm: name to check if covered.
873 * @param nmlen: length of name.
874 * @param rrset: covering NSEC3 rrset is returned here.
875 * @param rr: rr of cover is returned here.
876 * @return true if a covering NSEC3 is found, false if not.
877 */
878static int
879find_covering_nsec3(struct module_env* env, struct nsec3_filter* flt,
880 rbtree_t* ct, uint8_t* nm, size_t nmlen,
881 struct ub_packed_rrset_key** rrset, int* rr)
882{
883 size_t i_rs;
884 int i_rr;
885 struct ub_packed_rrset_key* s;
886 struct nsec3_cached_hash* hash;
887 int r;
888
889 /* this loop skips other-zone and unknown NSEC3s, also non-NSEC3 RRs */
890 for(s=filter_first(flt, &i_rs, &i_rr); s;
891 s=filter_next(flt, &i_rs, &i_rr)) {
892 /* get name hashed for this NSEC3 RR */
893 r = nsec3_hash_name(ct, env->scratch, env->scratch_buffer,
894 s, i_rr, nm, nmlen, &hash);
895 if(r == 0) {
896 log_err("nsec3: malloc failure");
897 break; /* alloc failure */
898 } else if(r < 0)
899 continue; /* malformed NSEC3 */
900 else if(nsec3_covers(flt->zone, hash, s, i_rr,
901 env->scratch_buffer)) {
902 *rrset = s; /* rrset with this name */
903 *rr = i_rr; /* covers hash with these parameters */
904 return 1;
905 }
906 }
907 *rrset = NULL;
908 *rr = 0;
909 return 0;
910}
911
912/**
913 * findClosestEncloser
914 * Given a name and a list of NSEC3s, find the candidate closest encloser.
915 * This will be the first ancestor of 'name' (including itself) to have a
916 * matching NSEC3 RR.
917 * @param env: module environment with temporary region and buffer.
918 * @param flt: the NSEC3 RR filter, contains zone name and RRs.
919 * @param ct: cached hashes table.
920 * @param qinfo: query that is verified for.
921 * @param ce: closest encloser information is returned in here.
922 * @return true if a closest encloser candidate is found, false if not.
923 */
924static int
925nsec3_find_closest_encloser(struct module_env* env, struct nsec3_filter* flt,
926 rbtree_t* ct, struct query_info* qinfo, struct ce_response* ce)
927{
928 uint8_t* nm = qinfo->qname;
929 size_t nmlen = qinfo->qname_len;
930
931 /* This scans from longest name to shortest, so the first match
932 * we find is the only viable candidate. */
933
934 /* (David:) FIXME: modify so that the NSEC3 matching the zone apex need
935 * not be present. (Mark Andrews idea).
936 * (Wouter:) But make sure you check for DNAME bit in zone apex,
937 * if the NSEC3 you find is the only NSEC3 in the zone, then this
938 * may be the case. */
939
940 while(dname_subdomain_c(nm, flt->zone)) {
941 if(find_matching_nsec3(env, flt, ct, nm, nmlen,
942 &ce->ce_rrset, &ce->ce_rr)) {
943 ce->ce = nm;
944 ce->ce_len = nmlen;
945 return 1;
946 }
947 dname_remove_label(&nm, &nmlen);
948 }
949 return 0;
950}
951
952/**
953 * Given a qname and its proven closest encloser, calculate the "next
954 * closest" name. Basically, this is the name that is one label longer than
955 * the closest encloser that is still a subdomain of qname.
956 *
957 * @param qname: query name.
958 * @param qnamelen: length of qname.
959 * @param ce: closest encloser
960 * @param nm: result name.
961 * @param nmlen: length of nm.
962 */
963static void
964next_closer(uint8_t* qname, size_t qnamelen, uint8_t* ce,
965 uint8_t** nm, size_t* nmlen)
966{
967 int strip = dname_count_labels(qname) - dname_count_labels(ce) -1;
968 *nm = qname;
969 *nmlen = qnamelen;
970 if(strip>0)
971 dname_remove_labels(nm, nmlen, strip);
972}
973
974/**
975 * proveClosestEncloser
976 * Given a List of nsec3 RRs, find and prove the closest encloser to qname.
977 * @param env: module environment with temporary region and buffer.
978 * @param flt: the NSEC3 RR filter, contains zone name and RRs.
979 * @param ct: cached hashes table.
980 * @param qinfo: query that is verified for.
981 * @param prove_does_not_exist: If true, then if the closest encloser
982 * turns out to be qname, then null is returned.
983 * If set true, and the return value is true, then you can be
984 * certain that the ce.nc_rrset and ce.nc_rr are set properly.
985 * @param ce: closest encloser information is returned in here.
986 * @return bogus if no closest encloser could be proven.
987 * secure if a closest encloser could be proven, ce is set.
988 * insecure if the closest-encloser candidate turns out to prove
989 * that an insecure delegation exists above the qname.
990 */
991static enum sec_status
992nsec3_prove_closest_encloser(struct module_env* env, struct nsec3_filter* flt,
993 rbtree_t* ct, struct query_info* qinfo, int prove_does_not_exist,
994 struct ce_response* ce)
995{
996 uint8_t* nc;
997 size_t nc_len;
998 /* robust: clean out ce, in case it gets abused later */
999 memset(ce, 0, sizeof(*ce));
1000
1001 if(!nsec3_find_closest_encloser(env, flt, ct, qinfo, ce)) {
1002 verbose(VERB_ALGO, "nsec3 proveClosestEncloser: could "
1003 "not find a candidate for the closest encloser.");
1004 return sec_status_bogus;
1005 }
1006 log_nametypeclass(VERB_ALGO, "ce candidate", ce->ce, 0, 0);
1007
1008 if(query_dname_compare(ce->ce, qinfo->qname) == 0) {
1009 if(prove_does_not_exist) {
1010 verbose(VERB_ALGO, "nsec3 proveClosestEncloser: "
1011 "proved that qname existed, bad");
1012 return sec_status_bogus;
1013 }
1014 /* otherwise, we need to nothing else to prove that qname
1015 * is its own closest encloser. */
1016 return sec_status_secure;
1017 }
1018
1019 /* If the closest encloser is actually a delegation, then the
1020 * response should have been a referral. If it is a DNAME, then
1021 * it should have been a DNAME response. */
1022 if(nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_NS) &&
1023 !nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_SOA)) {
1024 if(!nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_DS)) {
1025 verbose(VERB_ALGO, "nsec3 proveClosestEncloser: "
1026 "closest encloser is insecure delegation");
1027 return sec_status_insecure;
1028 }
1029 verbose(VERB_ALGO, "nsec3 proveClosestEncloser: closest "
1030 "encloser was a delegation, bad");
1031 return sec_status_bogus;
1032 }
1033 if(nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_DNAME)) {
1034 verbose(VERB_ALGO, "nsec3 proveClosestEncloser: closest "
1035 "encloser was a DNAME, bad");
1036 return sec_status_bogus;
1037 }
1038
1039 /* Otherwise, we need to show that the next closer name is covered. */
1040 next_closer(qinfo->qname, qinfo->qname_len, ce->ce, &nc, &nc_len);
1041 if(!find_covering_nsec3(env, flt, ct, nc, nc_len,
1042 &ce->nc_rrset, &ce->nc_rr)) {
1043 verbose(VERB_ALGO, "nsec3: Could not find proof that the "
1044 "candidate encloser was the closest encloser");
1045 return sec_status_bogus;
1046 }
1047 return sec_status_secure;
1048}
1049
1050/** allocate a wildcard for the closest encloser */
1051static uint8_t*
1052nsec3_ce_wildcard(struct regional* region, uint8_t* ce, size_t celen,
1053 size_t* len)
1054{
1055 uint8_t* nm;
1056 if(celen > LDNS_MAX_DOMAINLEN - 2)
1057 return 0; /* too long */
1058 nm = (uint8_t*)regional_alloc(region, celen+2);
1059 if(!nm) {
1060 log_err("nsec3 wildcard: out of memory");
1061 return 0; /* alloc failure */
1062 }
1063 nm[0] = 1;
1064 nm[1] = (uint8_t)'*'; /* wildcard label */
1065 memmove(nm+2, ce, celen);
1066 *len = celen+2;
1067 return nm;
1068}
1069
1070/** Do the name error proof */
1071static enum sec_status
1072nsec3_do_prove_nameerror(struct module_env* env, struct nsec3_filter* flt,
1073 rbtree_t* ct, struct query_info* qinfo)
1074{
1075 struct ce_response ce;
1076 uint8_t* wc;
1077 size_t wclen;
1078 struct ub_packed_rrset_key* wc_rrset;
1079 int wc_rr;
1080 enum sec_status sec;
1081
1082 /* First locate and prove the closest encloser to qname. We will
1083 * use the variant that fails if the closest encloser turns out
1084 * to be qname. */
1085 sec = nsec3_prove_closest_encloser(env, flt, ct, qinfo, 1, &ce);
1086 if(sec != sec_status_secure) {
1087 if(sec == sec_status_bogus)
1088 verbose(VERB_ALGO, "nsec3 nameerror proof: failed "
1089 "to prove a closest encloser");
1090 else verbose(VERB_ALGO, "nsec3 nameerror proof: closest "
1091 "nsec3 is an insecure delegation");
1092 return sec;
1093 }
1094 log_nametypeclass(VERB_ALGO, "nsec3 namerror: proven ce=", ce.ce,0,0);
1095
1096 /* At this point, we know that qname does not exist. Now we need
1097 * to prove that the wildcard does not exist. */
1098 log_assert(ce.ce);
1099 wc = nsec3_ce_wildcard(env->scratch, ce.ce, ce.ce_len, &wclen);
1100 if(!wc || !find_covering_nsec3(env, flt, ct, wc, wclen,
1101 &wc_rrset, &wc_rr)) {
1102 verbose(VERB_ALGO, "nsec3 nameerror proof: could not prove "
1103 "that the applicable wildcard did not exist.");
1104 return sec_status_bogus;
1105 }
1106
1107 if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1108 verbose(VERB_ALGO, "nsec3 nameerror proof: nc has optout");
1109 return sec_status_insecure;
1110 }
1111 return sec_status_secure;
1112}
1113
1114enum sec_status
1115nsec3_prove_nameerror(struct module_env* env, struct val_env* ve,
1116 struct ub_packed_rrset_key** list, size_t num,
1117 struct query_info* qinfo, struct key_entry_key* kkey)
1118{
1119 rbtree_t ct;
1120 struct nsec3_filter flt;
1121
1122 if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1123 return sec_status_bogus; /* no valid NSEC3s, bogus */
1124 rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1125 filter_init(&flt, list, num, qinfo); /* init RR iterator */
1126 if(!flt.zone)
1127 return sec_status_bogus; /* no RRs */
1128 if(nsec3_iteration_count_high(ve, &flt, kkey))
1129 return sec_status_insecure; /* iteration count too high */
1130 log_nametypeclass(VERB_ALGO, "start nsec3 nameerror proof, zone",
1131 flt.zone, 0, 0);
1132 return nsec3_do_prove_nameerror(env, &flt, &ct, qinfo);
1133}
1134
1135/*
1136 * No code to handle qtype=NSEC3 specially.
1137 * This existed in early drafts, but was later (-05) removed.
1138 */
1139
1140/** Do the nodata proof */
1141static enum sec_status
1142nsec3_do_prove_nodata(struct module_env* env, struct nsec3_filter* flt,
1143 rbtree_t* ct, struct query_info* qinfo)
1144{
1145 struct ce_response ce;
1146 uint8_t* wc;
1147 size_t wclen;
1148 struct ub_packed_rrset_key* rrset;
1149 int rr;
1150 enum sec_status sec;
1151
1152 if(find_matching_nsec3(env, flt, ct, qinfo->qname, qinfo->qname_len,
1153 &rrset, &rr)) {
1154 /* cases 1 and 2 */
1155 if(nsec3_has_type(rrset, rr, qinfo->qtype)) {
1156 verbose(VERB_ALGO, "proveNodata: Matching NSEC3 "
1157 "proved that type existed, bogus");
1158 return sec_status_bogus;
1159 } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_CNAME)) {
1160 verbose(VERB_ALGO, "proveNodata: Matching NSEC3 "
1161 "proved that a CNAME existed, bogus");
1162 return sec_status_bogus;
1163 }
1164
1165 /*
1166 * If type DS: filter_init zone find already found a parent
1167 * zone, so this nsec3 is from a parent zone.
1168 * o can be not a delegation (unusual query for normal name,
1169 * no DS anyway, but we can verify that).
1170 * o can be a delegation (which is the usual DS check).
1171 * o may not have the SOA bit set (only the top of the
1172 * zone, which must have been above the name, has that).
1173 * Except for the root; which is checked by itself.
1174 *
1175 * If not type DS: matching nsec3 must not be a delegation.
1176 */
1177 if(qinfo->qtype == LDNS_RR_TYPE_DS && qinfo->qname_len != 1
1178 && nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA) &&
1179 !dname_is_root(qinfo->qname)) {
1180 verbose(VERB_ALGO, "proveNodata: apex NSEC3 "
1181 "abused for no DS proof, bogus");
1182 return sec_status_bogus;
1183 } else if(qinfo->qtype != LDNS_RR_TYPE_DS &&
1184 nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS) &&
1185 !nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) {
1186 if(!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_DS)) {
1187 verbose(VERB_ALGO, "proveNodata: matching "
1188 "NSEC3 is insecure delegation");
1189 return sec_status_insecure;
1190 }
1191 verbose(VERB_ALGO, "proveNodata: matching "
1192 "NSEC3 is a delegation, bogus");
1193 return sec_status_bogus;
1194 }
1195 return sec_status_secure;
1196 }
1197
1198 /* For cases 3 - 5, we need the proven closest encloser, and it
1199 * can't match qname. Although, at this point, we know that it
1200 * won't since we just checked that. */
1201 sec = nsec3_prove_closest_encloser(env, flt, ct, qinfo, 1, &ce);
1202 if(sec == sec_status_bogus) {
1203 verbose(VERB_ALGO, "proveNodata: did not match qname, "
1204 "nor found a proven closest encloser.");
1205 return sec_status_bogus;
1206 } else if(sec==sec_status_insecure && qinfo->qtype!=LDNS_RR_TYPE_DS){
1207 verbose(VERB_ALGO, "proveNodata: closest nsec3 is insecure "
1208 "delegation.");
1209 return sec_status_insecure;
1210 }
1211
1212 /* Case 3: removed */
1213
1214 /* Case 4: */
1215 log_assert(ce.ce);
1216 wc = nsec3_ce_wildcard(env->scratch, ce.ce, ce.ce_len, &wclen);
1217 if(wc && find_matching_nsec3(env, flt, ct, wc, wclen, &rrset, &rr)) {
1218 /* found wildcard */
1219 if(nsec3_has_type(rrset, rr, qinfo->qtype)) {
1220 verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1221 "wildcard had qtype, bogus");
1222 return sec_status_bogus;
1223 } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_CNAME)) {
1224 verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1225 "wildcard had a CNAME, bogus");
1226 return sec_status_bogus;
1227 }
1228 if(qinfo->qtype == LDNS_RR_TYPE_DS && qinfo->qname_len != 1
1229 && nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) {
1230 verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1231 "wildcard for no DS proof has a SOA, bogus");
1232 return sec_status_bogus;
1233 } else if(qinfo->qtype != LDNS_RR_TYPE_DS &&
1234 nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS) &&
1235 !nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) {
1236 verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1237 "wilcard is a delegation, bogus");
1238 return sec_status_bogus;
1239 }
1240 /* everything is peachy keen, except for optout spans */
1241 if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1242 verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1243 "wildcard is in optout range, insecure");
1244 return sec_status_insecure;
1245 }
1246 return sec_status_secure;
1247 }
1248
1249 /* Case 5: */
1250 /* Due to forwarders, cnames, and other collating effects, we
1251 * can see the ordinary unsigned data from a zone beneath an
1252 * insecure delegation under an optout here */
1253 if(!ce.nc_rrset) {
1254 verbose(VERB_ALGO, "nsec3 nodata proof: no next closer nsec3");
1255 return sec_status_bogus;
1256 }
1257
1258 /* We need to make sure that the covering NSEC3 is opt-out. */
1259 log_assert(ce.nc_rrset);
1260 if(!nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1261 if(qinfo->qtype == LDNS_RR_TYPE_DS)
1262 verbose(VERB_ALGO, "proveNodata: covering NSEC3 was not "
1263 "opt-out in an opt-out DS NOERROR/NODATA case.");
1264 else verbose(VERB_ALGO, "proveNodata: could not find matching "
1265 "NSEC3, nor matching wildcard, nor optout NSEC3 "
1266 "-- no more options, bogus.");
1267 return sec_status_bogus;
1268 }
1269 /* RFC5155 section 9.2: if nc has optout then no AD flag set */
1270 return sec_status_insecure;
1271}
1272
1273enum sec_status
1274nsec3_prove_nodata(struct module_env* env, struct val_env* ve,
1275 struct ub_packed_rrset_key** list, size_t num,
1276 struct query_info* qinfo, struct key_entry_key* kkey)
1277{
1278 rbtree_t ct;
1279 struct nsec3_filter flt;
1280
1281 if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1282 return sec_status_bogus; /* no valid NSEC3s, bogus */
1283 rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1284 filter_init(&flt, list, num, qinfo); /* init RR iterator */
1285 if(!flt.zone)
1286 return sec_status_bogus; /* no RRs */
1287 if(nsec3_iteration_count_high(ve, &flt, kkey))
1288 return sec_status_insecure; /* iteration count too high */
1289 return nsec3_do_prove_nodata(env, &flt, &ct, qinfo);
1290}
1291
1292enum sec_status
1293nsec3_prove_wildcard(struct module_env* env, struct val_env* ve,
1294 struct ub_packed_rrset_key** list, size_t num,
1295 struct query_info* qinfo, struct key_entry_key* kkey, uint8_t* wc)
1296{
1297 rbtree_t ct;
1298 struct nsec3_filter flt;
1299 struct ce_response ce;
1300 uint8_t* nc;
1301 size_t nc_len;
1302 size_t wclen;
1303 (void)dname_count_size_labels(wc, &wclen);
1304
1305 if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1306 return sec_status_bogus; /* no valid NSEC3s, bogus */
1307 rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1308 filter_init(&flt, list, num, qinfo); /* init RR iterator */
1309 if(!flt.zone)
1310 return sec_status_bogus; /* no RRs */
1311 if(nsec3_iteration_count_high(ve, &flt, kkey))
1312 return sec_status_insecure; /* iteration count too high */
1313
1314 /* We know what the (purported) closest encloser is by just
1315 * looking at the supposed generating wildcard.
1316 * The *. has already been removed from the wc name.
1317 */
1318 memset(&ce, 0, sizeof(ce));
1319 ce.ce = wc;
1320 ce.ce_len = wclen;
1321
1322 /* Now we still need to prove that the original data did not exist.
1323 * Otherwise, we need to show that the next closer name is covered. */
1324 next_closer(qinfo->qname, qinfo->qname_len, ce.ce, &nc, &nc_len);
1325 if(!find_covering_nsec3(env, &flt, &ct, nc, nc_len,
1326 &ce.nc_rrset, &ce.nc_rr)) {
1327 verbose(VERB_ALGO, "proveWildcard: did not find a covering "
1328 "NSEC3 that covered the next closer name.");
1329 return sec_status_bogus;
1330 }
1331 if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1332 verbose(VERB_ALGO, "proveWildcard: NSEC3 optout");
1333 return sec_status_insecure;
1334 }
1335 return sec_status_secure;
1336}
1337
1338/** test if list is all secure */
1339static int
1340list_is_secure(struct module_env* env, struct val_env* ve,
1341 struct ub_packed_rrset_key** list, size_t num,
1342 struct key_entry_key* kkey, char** reason)
1343{
1344 struct packed_rrset_data* d;
1345 size_t i;
1346 for(i=0; i<num; i++) {
1347 d = (struct packed_rrset_data*)list[i]->entry.data;
1348 if(list[i]->rk.type != htons(LDNS_RR_TYPE_NSEC3))
1349 continue;
1350 if(d->security == sec_status_secure)
1351 continue;
1352 rrset_check_sec_status(env->rrset_cache, list[i], *env->now);
1353 if(d->security == sec_status_secure)
1354 continue;
1355 d->security = val_verify_rrset_entry(env, ve, list[i], kkey,
1356 reason);
1357 if(d->security != sec_status_secure) {
1358 verbose(VERB_ALGO, "NSEC3 did not verify");
1359 return 0;
1360 }
1361 rrset_update_sec_status(env->rrset_cache, list[i], *env->now);
1362 }
1363 return 1;
1364}
1365
1366enum sec_status
1367nsec3_prove_nods(struct module_env* env, struct val_env* ve,
1368 struct ub_packed_rrset_key** list, size_t num,
1369 struct query_info* qinfo, struct key_entry_key* kkey, char** reason)
1370{
1371 rbtree_t ct;
1372 struct nsec3_filter flt;
1373 struct ce_response ce;
1374 struct ub_packed_rrset_key* rrset;
1375 int rr;
1376 log_assert(qinfo->qtype == LDNS_RR_TYPE_DS);
1377
1378 if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) {
1379 *reason = "no valid NSEC3s";
1380 return sec_status_bogus; /* no valid NSEC3s, bogus */
1381 }
1382 if(!list_is_secure(env, ve, list, num, kkey, reason))
1383 return sec_status_bogus; /* not all NSEC3 records secure */
1384 rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1385 filter_init(&flt, list, num, qinfo); /* init RR iterator */
1386 if(!flt.zone) {
1387 *reason = "no NSEC3 records";
1388 return sec_status_bogus; /* no RRs */
1389 }
1390 if(nsec3_iteration_count_high(ve, &flt, kkey))
1391 return sec_status_insecure; /* iteration count too high */
1392
1393 /* Look for a matching NSEC3 to qname -- this is the normal
1394 * NODATA case. */
1395 if(find_matching_nsec3(env, &flt, &ct, qinfo->qname, qinfo->qname_len,
1396 &rrset, &rr)) {
1397 /* If the matching NSEC3 has the SOA bit set, it is from
1398 * the wrong zone (the child instead of the parent). If
1399 * it has the DS bit set, then we were lied to. */
1400 if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA) &&
1401 qinfo->qname_len != 1) {
1402 verbose(VERB_ALGO, "nsec3 provenods: NSEC3 is from"
1403 " child zone, bogus");
1404 *reason = "NSEC3 from child zone";
1405 return sec_status_bogus;
1406 } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_DS)) {
1407 verbose(VERB_ALGO, "nsec3 provenods: NSEC3 has qtype"
1408 " DS, bogus");
1409 *reason = "NSEC3 has DS in bitmap";
1410 return sec_status_bogus;
1411 }
1412 /* If the NSEC3 RR doesn't have the NS bit set, then
1413 * this wasn't a delegation point. */
1414 if(!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS))
1415 return sec_status_indeterminate;
1416 /* Otherwise, this proves no DS. */
1417 return sec_status_secure;
1418 }
1419
1420 /* Otherwise, we are probably in the opt-out case. */
1421 if(nsec3_prove_closest_encloser(env, &flt, &ct, qinfo, 1, &ce)
1422 != sec_status_secure) {
1423 /* an insecure delegation *above* the qname does not prove
1424 * anything about this qname exactly, and bogus is bogus */
1425 verbose(VERB_ALGO, "nsec3 provenods: did not match qname, "
1426 "nor found a proven closest encloser.");
1427 *reason = "no NSEC3 closest encloser";
1428 return sec_status_bogus;
1429 }
1430
1431 /* robust extra check */
1432 if(!ce.nc_rrset) {
1433 verbose(VERB_ALGO, "nsec3 nods proof: no next closer nsec3");
1434 *reason = "no NSEC3 next closer";
1435 return sec_status_bogus;
1436 }
1437
1438 /* we had the closest encloser proof, then we need to check that the
1439 * covering NSEC3 was opt-out -- the proveClosestEncloser step already
1440 * checked to see if the closest encloser was a delegation or DNAME.
1441 */
1442 log_assert(ce.nc_rrset);
1443 if(!nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1444 verbose(VERB_ALGO, "nsec3 provenods: covering NSEC3 was not "
1445 "opt-out in an opt-out DS NOERROR/NODATA case.");
1446 *reason = "covering NSEC3 was not opt-out in an opt-out "
1447 "DS NOERROR/NODATA case";
1448 return sec_status_bogus;
1449 }
1450 /* RFC5155 section 9.2: if nc has optout then no AD flag set */
1451 return sec_status_insecure;
1452}
1453
1454enum sec_status
1455nsec3_prove_nxornodata(struct module_env* env, struct val_env* ve,
1456 struct ub_packed_rrset_key** list, size_t num,
1457 struct query_info* qinfo, struct key_entry_key* kkey, int* nodata)
1458{
1459 enum sec_status sec, secnx;
1460 rbtree_t ct;
1461 struct nsec3_filter flt;
1462 *nodata = 0;
1463
1464 if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1465 return sec_status_bogus; /* no valid NSEC3s, bogus */
1466 rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1467 filter_init(&flt, list, num, qinfo); /* init RR iterator */
1468 if(!flt.zone)
1469 return sec_status_bogus; /* no RRs */
1470 if(nsec3_iteration_count_high(ve, &flt, kkey))
1471 return sec_status_insecure; /* iteration count too high */
1472
1473 /* try nxdomain and nodata after another, while keeping the
1474 * hash cache intact */
1475
1476 secnx = nsec3_do_prove_nameerror(env, &flt, &ct, qinfo);
1477 if(secnx==sec_status_secure)
1478 return sec_status_secure;
1479 sec = nsec3_do_prove_nodata(env, &flt, &ct, qinfo);
1480 if(sec==sec_status_secure) {
1481 *nodata = 1;
1482 } else if(sec == sec_status_insecure) {
1483 *nodata = 1;
1484 } else if(secnx == sec_status_insecure) {
1485 sec = sec_status_insecure;
1486 }
1487 return sec;
1488}
| 601 return 1;
602}
603
604/** perform b32 encoding of hash */
605static int
606nsec3_calc_b32(struct regional* region, sldns_buffer* buf,
607 struct nsec3_cached_hash* c)
608{
609 int r;
610 sldns_buffer_clear(buf);
611 r = sldns_b32_ntop_extended_hex(c->hash, c->hash_len,
612 (char*)sldns_buffer_begin(buf), sldns_buffer_limit(buf));
613 if(r < 1) {
614 log_err("b32_ntop_extended_hex: error in encoding: %d", r);
615 return 0;
616 }
617 c->b32_len = (size_t)r;
618 c->b32 = regional_alloc_init(region, sldns_buffer_begin(buf),
619 c->b32_len);
620 if(!c->b32)
621 return 0;
622 return 1;
623}
624
625int
626nsec3_hash_name(rbtree_t* table, struct regional* region, sldns_buffer* buf,
627 struct ub_packed_rrset_key* nsec3, int rr, uint8_t* dname,
628 size_t dname_len, struct nsec3_cached_hash** hash)
629{
630 struct nsec3_cached_hash* c;
631 struct nsec3_cached_hash looki;
632#ifdef UNBOUND_DEBUG
633 rbnode_t* n;
634#endif
635 int r;
636 looki.node.key = &looki;
637 looki.nsec3 = nsec3;
638 looki.rr = rr;
639 looki.dname = dname;
640 looki.dname_len = dname_len;
641 /* lookup first in cache */
642 c = (struct nsec3_cached_hash*)rbtree_search(table, &looki);
643 if(c) {
644 *hash = c;
645 return 1;
646 }
647 /* create a new entry */
648 c = (struct nsec3_cached_hash*)regional_alloc(region, sizeof(*c));
649 if(!c) return 0;
650 c->node.key = c;
651 c->nsec3 = nsec3;
652 c->rr = rr;
653 c->dname = dname;
654 c->dname_len = dname_len;
655 r = nsec3_calc_hash(region, buf, c);
656 if(r != 1)
657 return r;
658 r = nsec3_calc_b32(region, buf, c);
659 if(r != 1)
660 return r;
661#ifdef UNBOUND_DEBUG
662 n =
663#else
664 (void)
665#endif
666 rbtree_insert(table, &c->node);
667 log_assert(n); /* cannot be duplicate, just did lookup */
668 *hash = c;
669 return 1;
670}
671
672/**
673 * compare a label lowercased
674 */
675static int
676label_compare_lower(uint8_t* lab1, uint8_t* lab2, size_t lablen)
677{
678 size_t i;
679 for(i=0; i<lablen; i++) {
680 if(tolower((unsigned char)*lab1) != tolower((unsigned char)*lab2)) {
681 if(tolower((unsigned char)*lab1) < tolower((unsigned char)*lab2))
682 return -1;
683 return 1;
684 }
685 lab1++;
686 lab2++;
687 }
688 return 0;
689}
690
691/**
692 * Compare a hashed name with the owner name of an NSEC3 RRset.
693 * @param flt: filter with zone name.
694 * @param hash: the hashed name.
695 * @param s: rrset with owner name.
696 * @return true if matches exactly, false if not.
697 */
698static int
699nsec3_hash_matches_owner(struct nsec3_filter* flt,
700 struct nsec3_cached_hash* hash, struct ub_packed_rrset_key* s)
701{
702 uint8_t* nm = s->rk.dname;
703 /* compare, does hash of name based on params in this NSEC3
704 * match the owner name of this NSEC3?
705 * name must be: <hashlength>base32 . zone name
706 * so; first label must not be root label (not zero length),
707 * and match the b32 encoded hash length,
708 * and the label content match the b32 encoded hash
709 * and the rest must be the zone name.
710 */
711 if(hash->b32_len != 0 && (size_t)nm[0] == hash->b32_len &&
712 label_compare_lower(nm+1, hash->b32, hash->b32_len) == 0 &&
713 query_dname_compare(nm+(size_t)nm[0]+1, flt->zone) == 0) {
714 return 1;
715 }
716 return 0;
717}
718
719/**
720 * Find matching NSEC3
721 * Find the NSEC3Record that matches a hash of a name.
722 * @param env: module environment with temporary region and buffer.
723 * @param flt: the NSEC3 RR filter, contains zone name and RRs.
724 * @param ct: cached hashes table.
725 * @param nm: name to look for.
726 * @param nmlen: length of name.
727 * @param rrset: nsec3 that matches is returned here.
728 * @param rr: rr number in nsec3 rrset that matches.
729 * @return true if a matching NSEC3 is found, false if not.
730 */
731static int
732find_matching_nsec3(struct module_env* env, struct nsec3_filter* flt,
733 rbtree_t* ct, uint8_t* nm, size_t nmlen,
734 struct ub_packed_rrset_key** rrset, int* rr)
735{
736 size_t i_rs;
737 int i_rr;
738 struct ub_packed_rrset_key* s;
739 struct nsec3_cached_hash* hash;
740 int r;
741
742 /* this loop skips other-zone and unknown NSEC3s, also non-NSEC3 RRs */
743 for(s=filter_first(flt, &i_rs, &i_rr); s;
744 s=filter_next(flt, &i_rs, &i_rr)) {
745 /* get name hashed for this NSEC3 RR */
746 r = nsec3_hash_name(ct, env->scratch, env->scratch_buffer,
747 s, i_rr, nm, nmlen, &hash);
748 if(r == 0) {
749 log_err("nsec3: malloc failure");
750 break; /* alloc failure */
751 } else if(r < 0)
752 continue; /* malformed NSEC3 */
753 else if(nsec3_hash_matches_owner(flt, hash, s)) {
754 *rrset = s; /* rrset with this name */
755 *rr = i_rr; /* matches hash with these parameters */
756 return 1;
757 }
758 }
759 *rrset = NULL;
760 *rr = 0;
761 return 0;
762}
763
764int
765nsec3_covers(uint8_t* zone, struct nsec3_cached_hash* hash,
766 struct ub_packed_rrset_key* rrset, int rr, sldns_buffer* buf)
767{
768 uint8_t* next, *owner;
769 size_t nextlen;
770 int len;
771 if(!nsec3_get_nextowner(rrset, rr, &next, &nextlen))
772 return 0; /* malformed RR proves nothing */
773
774 /* check the owner name is a hashed value . apex
775 * base32 encoded values must have equal length.
776 * hash_value and next hash value must have equal length. */
777 if(nextlen != hash->hash_len || hash->hash_len==0||hash->b32_len==0||
778 (size_t)*rrset->rk.dname != hash->b32_len ||
779 query_dname_compare(rrset->rk.dname+1+
780 (size_t)*rrset->rk.dname, zone) != 0)
781 return 0; /* bad lengths or owner name */
782
783 /* This is the "normal case: owner < next and owner < hash < next */
784 if(label_compare_lower(rrset->rk.dname+1, hash->b32,
785 hash->b32_len) < 0 &&
786 memcmp(hash->hash, next, nextlen) < 0)
787 return 1;
788
789 /* convert owner name from text to binary */
790 sldns_buffer_clear(buf);
791 owner = sldns_buffer_begin(buf);
792 len = sldns_b32_pton_extended_hex((char*)rrset->rk.dname+1,
793 hash->b32_len, owner, sldns_buffer_limit(buf));
794 if(len<1)
795 return 0; /* bad owner name in some way */
796 if((size_t)len != hash->hash_len || (size_t)len != nextlen)
797 return 0; /* wrong length */
798
799 /* this is the end of zone case: next <= owner &&
800 * (hash > owner || hash < next)
801 * this also covers the only-apex case of next==owner.
802 */
803 if(memcmp(next, owner, nextlen) <= 0 &&
804 ( memcmp(hash->hash, owner, nextlen) > 0 ||
805 memcmp(hash->hash, next, nextlen) < 0)) {
806 return 1;
807 }
808 return 0;
809}
810
811/**
812 * findCoveringNSEC3
813 * Given a name, find a covering NSEC3 from among a list of NSEC3s.
814 *
815 * @param env: module environment with temporary region and buffer.
816 * @param flt: the NSEC3 RR filter, contains zone name and RRs.
817 * @param ct: cached hashes table.
818 * @param nm: name to check if covered.
819 * @param nmlen: length of name.
820 * @param rrset: covering NSEC3 rrset is returned here.
821 * @param rr: rr of cover is returned here.
822 * @return true if a covering NSEC3 is found, false if not.
823 */
824static int
825find_covering_nsec3(struct module_env* env, struct nsec3_filter* flt,
826 rbtree_t* ct, uint8_t* nm, size_t nmlen,
827 struct ub_packed_rrset_key** rrset, int* rr)
828{
829 size_t i_rs;
830 int i_rr;
831 struct ub_packed_rrset_key* s;
832 struct nsec3_cached_hash* hash;
833 int r;
834
835 /* this loop skips other-zone and unknown NSEC3s, also non-NSEC3 RRs */
836 for(s=filter_first(flt, &i_rs, &i_rr); s;
837 s=filter_next(flt, &i_rs, &i_rr)) {
838 /* get name hashed for this NSEC3 RR */
839 r = nsec3_hash_name(ct, env->scratch, env->scratch_buffer,
840 s, i_rr, nm, nmlen, &hash);
841 if(r == 0) {
842 log_err("nsec3: malloc failure");
843 break; /* alloc failure */
844 } else if(r < 0)
845 continue; /* malformed NSEC3 */
846 else if(nsec3_covers(flt->zone, hash, s, i_rr,
847 env->scratch_buffer)) {
848 *rrset = s; /* rrset with this name */
849 *rr = i_rr; /* covers hash with these parameters */
850 return 1;
851 }
852 }
853 *rrset = NULL;
854 *rr = 0;
855 return 0;
856}
857
858/**
859 * findClosestEncloser
860 * Given a name and a list of NSEC3s, find the candidate closest encloser.
861 * This will be the first ancestor of 'name' (including itself) to have a
862 * matching NSEC3 RR.
863 * @param env: module environment with temporary region and buffer.
864 * @param flt: the NSEC3 RR filter, contains zone name and RRs.
865 * @param ct: cached hashes table.
866 * @param qinfo: query that is verified for.
867 * @param ce: closest encloser information is returned in here.
868 * @return true if a closest encloser candidate is found, false if not.
869 */
870static int
871nsec3_find_closest_encloser(struct module_env* env, struct nsec3_filter* flt,
872 rbtree_t* ct, struct query_info* qinfo, struct ce_response* ce)
873{
874 uint8_t* nm = qinfo->qname;
875 size_t nmlen = qinfo->qname_len;
876
877 /* This scans from longest name to shortest, so the first match
878 * we find is the only viable candidate. */
879
880 /* (David:) FIXME: modify so that the NSEC3 matching the zone apex need
881 * not be present. (Mark Andrews idea).
882 * (Wouter:) But make sure you check for DNAME bit in zone apex,
883 * if the NSEC3 you find is the only NSEC3 in the zone, then this
884 * may be the case. */
885
886 while(dname_subdomain_c(nm, flt->zone)) {
887 if(find_matching_nsec3(env, flt, ct, nm, nmlen,
888 &ce->ce_rrset, &ce->ce_rr)) {
889 ce->ce = nm;
890 ce->ce_len = nmlen;
891 return 1;
892 }
893 dname_remove_label(&nm, &nmlen);
894 }
895 return 0;
896}
897
898/**
899 * Given a qname and its proven closest encloser, calculate the "next
900 * closest" name. Basically, this is the name that is one label longer than
901 * the closest encloser that is still a subdomain of qname.
902 *
903 * @param qname: query name.
904 * @param qnamelen: length of qname.
905 * @param ce: closest encloser
906 * @param nm: result name.
907 * @param nmlen: length of nm.
908 */
909static void
910next_closer(uint8_t* qname, size_t qnamelen, uint8_t* ce,
911 uint8_t** nm, size_t* nmlen)
912{
913 int strip = dname_count_labels(qname) - dname_count_labels(ce) -1;
914 *nm = qname;
915 *nmlen = qnamelen;
916 if(strip>0)
917 dname_remove_labels(nm, nmlen, strip);
918}
919
920/**
921 * proveClosestEncloser
922 * Given a List of nsec3 RRs, find and prove the closest encloser to qname.
923 * @param env: module environment with temporary region and buffer.
924 * @param flt: the NSEC3 RR filter, contains zone name and RRs.
925 * @param ct: cached hashes table.
926 * @param qinfo: query that is verified for.
927 * @param prove_does_not_exist: If true, then if the closest encloser
928 * turns out to be qname, then null is returned.
929 * If set true, and the return value is true, then you can be
930 * certain that the ce.nc_rrset and ce.nc_rr are set properly.
931 * @param ce: closest encloser information is returned in here.
932 * @return bogus if no closest encloser could be proven.
933 * secure if a closest encloser could be proven, ce is set.
934 * insecure if the closest-encloser candidate turns out to prove
935 * that an insecure delegation exists above the qname.
936 */
937static enum sec_status
938nsec3_prove_closest_encloser(struct module_env* env, struct nsec3_filter* flt,
939 rbtree_t* ct, struct query_info* qinfo, int prove_does_not_exist,
940 struct ce_response* ce)
941{
942 uint8_t* nc;
943 size_t nc_len;
944 /* robust: clean out ce, in case it gets abused later */
945 memset(ce, 0, sizeof(*ce));
946
947 if(!nsec3_find_closest_encloser(env, flt, ct, qinfo, ce)) {
948 verbose(VERB_ALGO, "nsec3 proveClosestEncloser: could "
949 "not find a candidate for the closest encloser.");
950 return sec_status_bogus;
951 }
952 log_nametypeclass(VERB_ALGO, "ce candidate", ce->ce, 0, 0);
953
954 if(query_dname_compare(ce->ce, qinfo->qname) == 0) {
955 if(prove_does_not_exist) {
956 verbose(VERB_ALGO, "nsec3 proveClosestEncloser: "
957 "proved that qname existed, bad");
958 return sec_status_bogus;
959 }
960 /* otherwise, we need to nothing else to prove that qname
961 * is its own closest encloser. */
962 return sec_status_secure;
963 }
964
965 /* If the closest encloser is actually a delegation, then the
966 * response should have been a referral. If it is a DNAME, then
967 * it should have been a DNAME response. */
968 if(nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_NS) &&
969 !nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_SOA)) {
970 if(!nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_DS)) {
971 verbose(VERB_ALGO, "nsec3 proveClosestEncloser: "
972 "closest encloser is insecure delegation");
973 return sec_status_insecure;
974 }
975 verbose(VERB_ALGO, "nsec3 proveClosestEncloser: closest "
976 "encloser was a delegation, bad");
977 return sec_status_bogus;
978 }
979 if(nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_DNAME)) {
980 verbose(VERB_ALGO, "nsec3 proveClosestEncloser: closest "
981 "encloser was a DNAME, bad");
982 return sec_status_bogus;
983 }
984
985 /* Otherwise, we need to show that the next closer name is covered. */
986 next_closer(qinfo->qname, qinfo->qname_len, ce->ce, &nc, &nc_len);
987 if(!find_covering_nsec3(env, flt, ct, nc, nc_len,
988 &ce->nc_rrset, &ce->nc_rr)) {
989 verbose(VERB_ALGO, "nsec3: Could not find proof that the "
990 "candidate encloser was the closest encloser");
991 return sec_status_bogus;
992 }
993 return sec_status_secure;
994}
995
996/** allocate a wildcard for the closest encloser */
997static uint8_t*
998nsec3_ce_wildcard(struct regional* region, uint8_t* ce, size_t celen,
999 size_t* len)
1000{
1001 uint8_t* nm;
1002 if(celen > LDNS_MAX_DOMAINLEN - 2)
1003 return 0; /* too long */
1004 nm = (uint8_t*)regional_alloc(region, celen+2);
1005 if(!nm) {
1006 log_err("nsec3 wildcard: out of memory");
1007 return 0; /* alloc failure */
1008 }
1009 nm[0] = 1;
1010 nm[1] = (uint8_t)'*'; /* wildcard label */
1011 memmove(nm+2, ce, celen);
1012 *len = celen+2;
1013 return nm;
1014}
1015
1016/** Do the name error proof */
1017static enum sec_status
1018nsec3_do_prove_nameerror(struct module_env* env, struct nsec3_filter* flt,
1019 rbtree_t* ct, struct query_info* qinfo)
1020{
1021 struct ce_response ce;
1022 uint8_t* wc;
1023 size_t wclen;
1024 struct ub_packed_rrset_key* wc_rrset;
1025 int wc_rr;
1026 enum sec_status sec;
1027
1028 /* First locate and prove the closest encloser to qname. We will
1029 * use the variant that fails if the closest encloser turns out
1030 * to be qname. */
1031 sec = nsec3_prove_closest_encloser(env, flt, ct, qinfo, 1, &ce);
1032 if(sec != sec_status_secure) {
1033 if(sec == sec_status_bogus)
1034 verbose(VERB_ALGO, "nsec3 nameerror proof: failed "
1035 "to prove a closest encloser");
1036 else verbose(VERB_ALGO, "nsec3 nameerror proof: closest "
1037 "nsec3 is an insecure delegation");
1038 return sec;
1039 }
1040 log_nametypeclass(VERB_ALGO, "nsec3 namerror: proven ce=", ce.ce,0,0);
1041
1042 /* At this point, we know that qname does not exist. Now we need
1043 * to prove that the wildcard does not exist. */
1044 log_assert(ce.ce);
1045 wc = nsec3_ce_wildcard(env->scratch, ce.ce, ce.ce_len, &wclen);
1046 if(!wc || !find_covering_nsec3(env, flt, ct, wc, wclen,
1047 &wc_rrset, &wc_rr)) {
1048 verbose(VERB_ALGO, "nsec3 nameerror proof: could not prove "
1049 "that the applicable wildcard did not exist.");
1050 return sec_status_bogus;
1051 }
1052
1053 if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1054 verbose(VERB_ALGO, "nsec3 nameerror proof: nc has optout");
1055 return sec_status_insecure;
1056 }
1057 return sec_status_secure;
1058}
1059
1060enum sec_status
1061nsec3_prove_nameerror(struct module_env* env, struct val_env* ve,
1062 struct ub_packed_rrset_key** list, size_t num,
1063 struct query_info* qinfo, struct key_entry_key* kkey)
1064{
1065 rbtree_t ct;
1066 struct nsec3_filter flt;
1067
1068 if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1069 return sec_status_bogus; /* no valid NSEC3s, bogus */
1070 rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1071 filter_init(&flt, list, num, qinfo); /* init RR iterator */
1072 if(!flt.zone)
1073 return sec_status_bogus; /* no RRs */
1074 if(nsec3_iteration_count_high(ve, &flt, kkey))
1075 return sec_status_insecure; /* iteration count too high */
1076 log_nametypeclass(VERB_ALGO, "start nsec3 nameerror proof, zone",
1077 flt.zone, 0, 0);
1078 return nsec3_do_prove_nameerror(env, &flt, &ct, qinfo);
1079}
1080
1081/*
1082 * No code to handle qtype=NSEC3 specially.
1083 * This existed in early drafts, but was later (-05) removed.
1084 */
1085
1086/** Do the nodata proof */
1087static enum sec_status
1088nsec3_do_prove_nodata(struct module_env* env, struct nsec3_filter* flt,
1089 rbtree_t* ct, struct query_info* qinfo)
1090{
1091 struct ce_response ce;
1092 uint8_t* wc;
1093 size_t wclen;
1094 struct ub_packed_rrset_key* rrset;
1095 int rr;
1096 enum sec_status sec;
1097
1098 if(find_matching_nsec3(env, flt, ct, qinfo->qname, qinfo->qname_len,
1099 &rrset, &rr)) {
1100 /* cases 1 and 2 */
1101 if(nsec3_has_type(rrset, rr, qinfo->qtype)) {
1102 verbose(VERB_ALGO, "proveNodata: Matching NSEC3 "
1103 "proved that type existed, bogus");
1104 return sec_status_bogus;
1105 } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_CNAME)) {
1106 verbose(VERB_ALGO, "proveNodata: Matching NSEC3 "
1107 "proved that a CNAME existed, bogus");
1108 return sec_status_bogus;
1109 }
1110
1111 /*
1112 * If type DS: filter_init zone find already found a parent
1113 * zone, so this nsec3 is from a parent zone.
1114 * o can be not a delegation (unusual query for normal name,
1115 * no DS anyway, but we can verify that).
1116 * o can be a delegation (which is the usual DS check).
1117 * o may not have the SOA bit set (only the top of the
1118 * zone, which must have been above the name, has that).
1119 * Except for the root; which is checked by itself.
1120 *
1121 * If not type DS: matching nsec3 must not be a delegation.
1122 */
1123 if(qinfo->qtype == LDNS_RR_TYPE_DS && qinfo->qname_len != 1
1124 && nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA) &&
1125 !dname_is_root(qinfo->qname)) {
1126 verbose(VERB_ALGO, "proveNodata: apex NSEC3 "
1127 "abused for no DS proof, bogus");
1128 return sec_status_bogus;
1129 } else if(qinfo->qtype != LDNS_RR_TYPE_DS &&
1130 nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS) &&
1131 !nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) {
1132 if(!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_DS)) {
1133 verbose(VERB_ALGO, "proveNodata: matching "
1134 "NSEC3 is insecure delegation");
1135 return sec_status_insecure;
1136 }
1137 verbose(VERB_ALGO, "proveNodata: matching "
1138 "NSEC3 is a delegation, bogus");
1139 return sec_status_bogus;
1140 }
1141 return sec_status_secure;
1142 }
1143
1144 /* For cases 3 - 5, we need the proven closest encloser, and it
1145 * can't match qname. Although, at this point, we know that it
1146 * won't since we just checked that. */
1147 sec = nsec3_prove_closest_encloser(env, flt, ct, qinfo, 1, &ce);
1148 if(sec == sec_status_bogus) {
1149 verbose(VERB_ALGO, "proveNodata: did not match qname, "
1150 "nor found a proven closest encloser.");
1151 return sec_status_bogus;
1152 } else if(sec==sec_status_insecure && qinfo->qtype!=LDNS_RR_TYPE_DS){
1153 verbose(VERB_ALGO, "proveNodata: closest nsec3 is insecure "
1154 "delegation.");
1155 return sec_status_insecure;
1156 }
1157
1158 /* Case 3: removed */
1159
1160 /* Case 4: */
1161 log_assert(ce.ce);
1162 wc = nsec3_ce_wildcard(env->scratch, ce.ce, ce.ce_len, &wclen);
1163 if(wc && find_matching_nsec3(env, flt, ct, wc, wclen, &rrset, &rr)) {
1164 /* found wildcard */
1165 if(nsec3_has_type(rrset, rr, qinfo->qtype)) {
1166 verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1167 "wildcard had qtype, bogus");
1168 return sec_status_bogus;
1169 } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_CNAME)) {
1170 verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1171 "wildcard had a CNAME, bogus");
1172 return sec_status_bogus;
1173 }
1174 if(qinfo->qtype == LDNS_RR_TYPE_DS && qinfo->qname_len != 1
1175 && nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) {
1176 verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1177 "wildcard for no DS proof has a SOA, bogus");
1178 return sec_status_bogus;
1179 } else if(qinfo->qtype != LDNS_RR_TYPE_DS &&
1180 nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS) &&
1181 !nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) {
1182 verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1183 "wilcard is a delegation, bogus");
1184 return sec_status_bogus;
1185 }
1186 /* everything is peachy keen, except for optout spans */
1187 if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1188 verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1189 "wildcard is in optout range, insecure");
1190 return sec_status_insecure;
1191 }
1192 return sec_status_secure;
1193 }
1194
1195 /* Case 5: */
1196 /* Due to forwarders, cnames, and other collating effects, we
1197 * can see the ordinary unsigned data from a zone beneath an
1198 * insecure delegation under an optout here */
1199 if(!ce.nc_rrset) {
1200 verbose(VERB_ALGO, "nsec3 nodata proof: no next closer nsec3");
1201 return sec_status_bogus;
1202 }
1203
1204 /* We need to make sure that the covering NSEC3 is opt-out. */
1205 log_assert(ce.nc_rrset);
1206 if(!nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1207 if(qinfo->qtype == LDNS_RR_TYPE_DS)
1208 verbose(VERB_ALGO, "proveNodata: covering NSEC3 was not "
1209 "opt-out in an opt-out DS NOERROR/NODATA case.");
1210 else verbose(VERB_ALGO, "proveNodata: could not find matching "
1211 "NSEC3, nor matching wildcard, nor optout NSEC3 "
1212 "-- no more options, bogus.");
1213 return sec_status_bogus;
1214 }
1215 /* RFC5155 section 9.2: if nc has optout then no AD flag set */
1216 return sec_status_insecure;
1217}
1218
1219enum sec_status
1220nsec3_prove_nodata(struct module_env* env, struct val_env* ve,
1221 struct ub_packed_rrset_key** list, size_t num,
1222 struct query_info* qinfo, struct key_entry_key* kkey)
1223{
1224 rbtree_t ct;
1225 struct nsec3_filter flt;
1226
1227 if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1228 return sec_status_bogus; /* no valid NSEC3s, bogus */
1229 rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1230 filter_init(&flt, list, num, qinfo); /* init RR iterator */
1231 if(!flt.zone)
1232 return sec_status_bogus; /* no RRs */
1233 if(nsec3_iteration_count_high(ve, &flt, kkey))
1234 return sec_status_insecure; /* iteration count too high */
1235 return nsec3_do_prove_nodata(env, &flt, &ct, qinfo);
1236}
1237
1238enum sec_status
1239nsec3_prove_wildcard(struct module_env* env, struct val_env* ve,
1240 struct ub_packed_rrset_key** list, size_t num,
1241 struct query_info* qinfo, struct key_entry_key* kkey, uint8_t* wc)
1242{
1243 rbtree_t ct;
1244 struct nsec3_filter flt;
1245 struct ce_response ce;
1246 uint8_t* nc;
1247 size_t nc_len;
1248 size_t wclen;
1249 (void)dname_count_size_labels(wc, &wclen);
1250
1251 if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1252 return sec_status_bogus; /* no valid NSEC3s, bogus */
1253 rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1254 filter_init(&flt, list, num, qinfo); /* init RR iterator */
1255 if(!flt.zone)
1256 return sec_status_bogus; /* no RRs */
1257 if(nsec3_iteration_count_high(ve, &flt, kkey))
1258 return sec_status_insecure; /* iteration count too high */
1259
1260 /* We know what the (purported) closest encloser is by just
1261 * looking at the supposed generating wildcard.
1262 * The *. has already been removed from the wc name.
1263 */
1264 memset(&ce, 0, sizeof(ce));
1265 ce.ce = wc;
1266 ce.ce_len = wclen;
1267
1268 /* Now we still need to prove that the original data did not exist.
1269 * Otherwise, we need to show that the next closer name is covered. */
1270 next_closer(qinfo->qname, qinfo->qname_len, ce.ce, &nc, &nc_len);
1271 if(!find_covering_nsec3(env, &flt, &ct, nc, nc_len,
1272 &ce.nc_rrset, &ce.nc_rr)) {
1273 verbose(VERB_ALGO, "proveWildcard: did not find a covering "
1274 "NSEC3 that covered the next closer name.");
1275 return sec_status_bogus;
1276 }
1277 if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1278 verbose(VERB_ALGO, "proveWildcard: NSEC3 optout");
1279 return sec_status_insecure;
1280 }
1281 return sec_status_secure;
1282}
1283
1284/** test if list is all secure */
1285static int
1286list_is_secure(struct module_env* env, struct val_env* ve,
1287 struct ub_packed_rrset_key** list, size_t num,
1288 struct key_entry_key* kkey, char** reason)
1289{
1290 struct packed_rrset_data* d;
1291 size_t i;
1292 for(i=0; i<num; i++) {
1293 d = (struct packed_rrset_data*)list[i]->entry.data;
1294 if(list[i]->rk.type != htons(LDNS_RR_TYPE_NSEC3))
1295 continue;
1296 if(d->security == sec_status_secure)
1297 continue;
1298 rrset_check_sec_status(env->rrset_cache, list[i], *env->now);
1299 if(d->security == sec_status_secure)
1300 continue;
1301 d->security = val_verify_rrset_entry(env, ve, list[i], kkey,
1302 reason);
1303 if(d->security != sec_status_secure) {
1304 verbose(VERB_ALGO, "NSEC3 did not verify");
1305 return 0;
1306 }
1307 rrset_update_sec_status(env->rrset_cache, list[i], *env->now);
1308 }
1309 return 1;
1310}
1311
1312enum sec_status
1313nsec3_prove_nods(struct module_env* env, struct val_env* ve,
1314 struct ub_packed_rrset_key** list, size_t num,
1315 struct query_info* qinfo, struct key_entry_key* kkey, char** reason)
1316{
1317 rbtree_t ct;
1318 struct nsec3_filter flt;
1319 struct ce_response ce;
1320 struct ub_packed_rrset_key* rrset;
1321 int rr;
1322 log_assert(qinfo->qtype == LDNS_RR_TYPE_DS);
1323
1324 if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) {
1325 *reason = "no valid NSEC3s";
1326 return sec_status_bogus; /* no valid NSEC3s, bogus */
1327 }
1328 if(!list_is_secure(env, ve, list, num, kkey, reason))
1329 return sec_status_bogus; /* not all NSEC3 records secure */
1330 rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1331 filter_init(&flt, list, num, qinfo); /* init RR iterator */
1332 if(!flt.zone) {
1333 *reason = "no NSEC3 records";
1334 return sec_status_bogus; /* no RRs */
1335 }
1336 if(nsec3_iteration_count_high(ve, &flt, kkey))
1337 return sec_status_insecure; /* iteration count too high */
1338
1339 /* Look for a matching NSEC3 to qname -- this is the normal
1340 * NODATA case. */
1341 if(find_matching_nsec3(env, &flt, &ct, qinfo->qname, qinfo->qname_len,
1342 &rrset, &rr)) {
1343 /* If the matching NSEC3 has the SOA bit set, it is from
1344 * the wrong zone (the child instead of the parent). If
1345 * it has the DS bit set, then we were lied to. */
1346 if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA) &&
1347 qinfo->qname_len != 1) {
1348 verbose(VERB_ALGO, "nsec3 provenods: NSEC3 is from"
1349 " child zone, bogus");
1350 *reason = "NSEC3 from child zone";
1351 return sec_status_bogus;
1352 } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_DS)) {
1353 verbose(VERB_ALGO, "nsec3 provenods: NSEC3 has qtype"
1354 " DS, bogus");
1355 *reason = "NSEC3 has DS in bitmap";
1356 return sec_status_bogus;
1357 }
1358 /* If the NSEC3 RR doesn't have the NS bit set, then
1359 * this wasn't a delegation point. */
1360 if(!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS))
1361 return sec_status_indeterminate;
1362 /* Otherwise, this proves no DS. */
1363 return sec_status_secure;
1364 }
1365
1366 /* Otherwise, we are probably in the opt-out case. */
1367 if(nsec3_prove_closest_encloser(env, &flt, &ct, qinfo, 1, &ce)
1368 != sec_status_secure) {
1369 /* an insecure delegation *above* the qname does not prove
1370 * anything about this qname exactly, and bogus is bogus */
1371 verbose(VERB_ALGO, "nsec3 provenods: did not match qname, "
1372 "nor found a proven closest encloser.");
1373 *reason = "no NSEC3 closest encloser";
1374 return sec_status_bogus;
1375 }
1376
1377 /* robust extra check */
1378 if(!ce.nc_rrset) {
1379 verbose(VERB_ALGO, "nsec3 nods proof: no next closer nsec3");
1380 *reason = "no NSEC3 next closer";
1381 return sec_status_bogus;
1382 }
1383
1384 /* we had the closest encloser proof, then we need to check that the
1385 * covering NSEC3 was opt-out -- the proveClosestEncloser step already
1386 * checked to see if the closest encloser was a delegation or DNAME.
1387 */
1388 log_assert(ce.nc_rrset);
1389 if(!nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1390 verbose(VERB_ALGO, "nsec3 provenods: covering NSEC3 was not "
1391 "opt-out in an opt-out DS NOERROR/NODATA case.");
1392 *reason = "covering NSEC3 was not opt-out in an opt-out "
1393 "DS NOERROR/NODATA case";
1394 return sec_status_bogus;
1395 }
1396 /* RFC5155 section 9.2: if nc has optout then no AD flag set */
1397 return sec_status_insecure;
1398}
1399
1400enum sec_status
1401nsec3_prove_nxornodata(struct module_env* env, struct val_env* ve,
1402 struct ub_packed_rrset_key** list, size_t num,
1403 struct query_info* qinfo, struct key_entry_key* kkey, int* nodata)
1404{
1405 enum sec_status sec, secnx;
1406 rbtree_t ct;
1407 struct nsec3_filter flt;
1408 *nodata = 0;
1409
1410 if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1411 return sec_status_bogus; /* no valid NSEC3s, bogus */
1412 rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1413 filter_init(&flt, list, num, qinfo); /* init RR iterator */
1414 if(!flt.zone)
1415 return sec_status_bogus; /* no RRs */
1416 if(nsec3_iteration_count_high(ve, &flt, kkey))
1417 return sec_status_insecure; /* iteration count too high */
1418
1419 /* try nxdomain and nodata after another, while keeping the
1420 * hash cache intact */
1421
1422 secnx = nsec3_do_prove_nameerror(env, &flt, &ct, qinfo);
1423 if(secnx==sec_status_secure)
1424 return sec_status_secure;
1425 sec = nsec3_do_prove_nodata(env, &flt, &ct, qinfo);
1426 if(sec==sec_status_secure) {
1427 *nodata = 1;
1428 } else if(sec == sec_status_insecure) {
1429 *nodata = 1;
1430 } else if(secnx == sec_status_insecure) {
1431 sec = sec_status_insecure;
1432 }
1433 return sec;
1434}
|