/*
 * validator/val_nsec.c - validator NSEC denial of existence functions.
 *
 * Copyright (c) 2007, NLnet Labs. All rights reserved.
 *
 * This software is open source.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 * 
 * Neither the name of the NLNET LABS nor the names of its contributors may
 * be used to endorse or promote products derived from this software without
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/**
 * \file
 *
 * This file contains helper functions for the validator module.
 * The functions help with NSEC checking, the different NSEC proofs
 * for denial of existence, and proofs for presence of types.
 */
#include "config.h"
#include "validator/val_nsec.h"
#include "validator/val_utils.h"
#include "util/data/msgreply.h"
#include "util/data/dname.h"
#include "util/net_help.h"
#include "util/module.h"
#include "services/cache/rrset.h"

/** get ttl of rrset */
static uint32_t 
rrset_get_ttl(struct ub_packed_rrset_key* k)
{
	struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
	return d->ttl;
}

int
nsecbitmap_has_type_rdata(uint8_t* bitmap, size_t len, uint16_t type)
{
	/* Check type present in NSEC typemap with bitmap arg */
	/* bitmasks for determining type-lowerbits presence */
	uint8_t masks[8] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
	uint8_t type_window = type>>8;
	uint8_t type_low = type&0xff;
	uint8_t win, winlen;
	/* read each of the type bitmap windows and see if the searched
	 * type is amongst it */
	while(len > 0) {
		if(len < 3) /* bad window, at least window# winlen bitmap */
			return 0;
		win = *bitmap++;
		winlen = *bitmap++;
		len -= 2;
		if(len < winlen || winlen < 1 || winlen > 32) 
			return 0;	/* bad window length */
		if(win == type_window) {
			/* search window bitmap for the correct byte */
			/* mybyte is 0 if we need the first byte */
			size_t mybyte = type_low>>3;
			if(winlen <= mybyte)
				return 0; /* window too short */
			return (int)(bitmap[mybyte] & masks[type_low&0x7]);
		} else {
			/* not the window we are looking for */
			bitmap += winlen;
			len -= winlen;
		}
	}
	/* end of bitmap reached, no type found */
	return 0;
}

int
nsec_has_type(struct ub_packed_rrset_key* nsec, uint16_t type)
{
	struct packed_rrset_data* d = (struct packed_rrset_data*)nsec->
		entry.data;
	size_t len;
	if(!d || d->count == 0 || d->rr_len[0] < 2+1)
		return 0;
	len = dname_valid(d->rr_data[0]+2, d->rr_len[0]-2);
	if(!len)
		return 0;
	return nsecbitmap_has_type_rdata(d->rr_data[0]+2+len, 
		d->rr_len[0]-2-len, type);
}

/**
 * Get next owner name from nsec record
 * @param nsec: the nsec RRset.
 *	If there are multiple RRs, then this will only return one of them.
 * @param nm: the next name is returned.
 * @param ln: length of nm is returned.
 * @return false on a bad NSEC RR (too short, malformed dname).
 */
static int 
nsec_get_next(struct ub_packed_rrset_key* nsec, uint8_t** nm, size_t* ln)
{
	struct packed_rrset_data* d = (struct packed_rrset_data*)nsec->
		entry.data;
	if(!d || d->count == 0 || d->rr_len[0] < 2+1) {
		*nm = 0;
		*ln = 0;
		return 0;
	}
	*nm = d->rr_data[0]+2;
	*ln = dname_valid(*nm, d->rr_len[0]-2);
	if(!*ln) {
		*nm = 0;
		*ln = 0;
		return 0;
	}
	return 1;
}

/**
 * For an NSEC that matches the DS queried for, check absence of DS type.
 *
 * @param nsec: NSEC for proof, must be trusted.
 * @param qinfo: what is queried for.
 * @return if secure the nsec proves that no DS is present, or 
 *	insecure if it proves it is not a delegation point.
 *	or bogus if something was wrong.
 */
static enum sec_status 
val_nsec_proves_no_ds(struct ub_packed_rrset_key* nsec, 
	struct query_info* qinfo)
{
	log_assert(qinfo->qtype == LDNS_RR_TYPE_DS);
	log_assert(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC);

	if(nsec_has_type(nsec, LDNS_RR_TYPE_SOA) && qinfo->qname_len != 1) {
		/* SOA present means that this is the NSEC from the child, 
		 * not the parent (so it is the wrong one). */
		return sec_status_bogus;
	}
	if(nsec_has_type(nsec, LDNS_RR_TYPE_DS)) {
		/* DS present means that there should have been a positive 
		 * response to the DS query, so there is something wrong. */
		return sec_status_bogus;
	}

	if(!nsec_has_type(nsec, LDNS_RR_TYPE_NS)) {
		/* If there is no NS at this point at all, then this 
		 * doesn't prove anything one way or the other. */
		return sec_status_insecure;
	}
	/* Otherwise, this proves no DS. */
	return sec_status_secure;
}

/** check security status from cache or verify rrset, returns true if secure */
static int
nsec_verify_rrset(struct module_env* env, struct val_env* ve, 
	struct ub_packed_rrset_key* nsec, struct key_entry_key* kkey, 
	char** reason)
{
	struct packed_rrset_data* d = (struct packed_rrset_data*)
		nsec->entry.data;
	if(d->security == sec_status_secure)
		return 1;
	rrset_check_sec_status(env->rrset_cache, nsec, *env->now);
	if(d->security == sec_status_secure)
		return 1;
	d->security = val_verify_rrset_entry(env, ve, nsec, kkey, reason);
	if(d->security == sec_status_secure) {
		rrset_update_sec_status(env->rrset_cache, nsec, *env->now);
		return 1;
	}
	return 0;
}

enum sec_status 
val_nsec_prove_nodata_dsreply(struct module_env* env, struct val_env* ve, 
	struct query_info* qinfo, struct reply_info* rep, 
	struct key_entry_key* kkey, time_t* proof_ttl, char** reason)
{
	struct ub_packed_rrset_key* nsec = reply_find_rrset_section_ns(
		rep, qinfo->qname, qinfo->qname_len, LDNS_RR_TYPE_NSEC, 
		qinfo->qclass);
	enum sec_status sec;
	size_t i;
	uint8_t* wc = NULL, *ce = NULL;
	int valid_nsec = 0;
	struct ub_packed_rrset_key* wc_nsec = NULL;

	/* If we have a NSEC at the same name, it must prove one 
	 * of two things
	 * --
	 * 1) this is a delegation point and there is no DS
	 * 2) this is not a delegation point */
	if(nsec) {
		if(!nsec_verify_rrset(env, ve, nsec, kkey, reason)) {
			verbose(VERB_ALGO, "NSEC RRset for the "
				"referral did not verify.");
			return sec_status_bogus;
		}
		sec = val_nsec_proves_no_ds(nsec, qinfo);
		if(sec == sec_status_bogus) {
			/* something was wrong. */
			*reason = "NSEC does not prove absence of DS";
			return sec;
		} else if(sec == sec_status_insecure) {
			/* this wasn't a delegation point. */
			return sec;
		} else if(sec == sec_status_secure) {
			/* this proved no DS. */
			*proof_ttl = ub_packed_rrset_ttl(nsec);
			return sec;
		}
		/* if unchecked, fall through to next proof */
	}

	/* Otherwise, there is no NSEC at qname. This could be an ENT. 
	 * (ENT=empty non terminal). If not, this is broken. */
	
	/* verify NSEC rrsets in auth section */
	for(i=rep->an_numrrsets; i < rep->an_numrrsets+rep->ns_numrrsets; 
		i++) {
		if(rep->rrsets[i]->rk.type != htons(LDNS_RR_TYPE_NSEC))
			continue;
		if(!nsec_verify_rrset(env, ve, rep->rrsets[i], kkey, reason)) {
			verbose(VERB_ALGO, "NSEC for empty non-terminal "
				"did not verify.");
			return sec_status_bogus;
		}
		if(nsec_proves_nodata(rep->rrsets[i], qinfo, &wc)) {
			verbose(VERB_ALGO, "NSEC for empty non-terminal "
				"proved no DS.");
			*proof_ttl = rrset_get_ttl(rep->rrsets[i]);
			if(wc && dname_is_wild(rep->rrsets[i]->rk.dname)) 
				wc_nsec = rep->rrsets[i];
			valid_nsec = 1;
		}
		if(val_nsec_proves_name_error(rep->rrsets[i], qinfo->qname)) {
			ce = nsec_closest_encloser(qinfo->qname, 
				rep->rrsets[i]);
		}
	}
	if(wc && !ce)
		valid_nsec = 0;
	else if(wc && ce) {
		/* ce and wc must match */
		if(query_dname_compare(wc, ce) != 0) 
			valid_nsec = 0;
		else if(!wc_nsec)
			valid_nsec = 0;
	}
	if(valid_nsec) {
		if(wc) {
			/* check if this is a delegation */
			*reason = "NSEC for wildcard does not prove absence of DS";
			return val_nsec_proves_no_ds(wc_nsec, qinfo);
		}
		/* valid nsec proves empty nonterminal */
		return sec_status_insecure;
	}

	/* NSEC proof did not conclusively point to DS or no DS */
	return sec_status_unchecked;
}

int nsec_proves_nodata(struct ub_packed_rrset_key* nsec, 
	struct query_info* qinfo, uint8_t** wc)
{
	log_assert(wc);
	if(query_dname_compare(nsec->rk.dname, qinfo->qname) != 0) {
		uint8_t* nm;
		size_t ln;

		/* empty-non-terminal checking. 
		 * Done before wildcard, because this is an exact match,
		 * and would prevent a wildcard from matching. */

		/* If the nsec is proving that qname is an ENT, the nsec owner 
		 * will be less than qname, and the next name will be a child 
		 * domain of the qname. */
		if(!nsec_get_next(nsec, &nm, &ln))
			return 0; /* bad nsec */
		if(dname_strict_subdomain_c(nm, qinfo->qname) &&
			dname_canonical_compare(nsec->rk.dname, 
				qinfo->qname) < 0) {
			return 1; /* proves ENT */
		}

		/* wildcard checking. */

		/* If this is a wildcard NSEC, make sure that a) it was 
		 * possible to have generated qname from the wildcard and 
		 * b) the type map does not contain qtype. Note that this 
		 * does NOT prove that this wildcard was the applicable 
		 * wildcard. */
		if(dname_is_wild(nsec->rk.dname)) {
			/* the purported closest encloser. */
			uint8_t* ce = nsec->rk.dname;
			size_t ce_len = nsec->rk.dname_len;
			dname_remove_label(&ce, &ce_len);

			/* The qname must be a strict subdomain of the 
			 * closest encloser, for the wildcard to apply 
			 */
			if(dname_strict_subdomain_c(qinfo->qname, ce)) {
				/* here we have a matching NSEC for the qname,
				 * perform matching NSEC checks */
				if(nsec_has_type(nsec, LDNS_RR_TYPE_CNAME)) {
				   /* should have gotten the wildcard CNAME */
					return 0;
				}
				if(nsec_has_type(nsec, LDNS_RR_TYPE_NS) && 
				   !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) {
				   /* wrong parentside (wildcard) NSEC used */
					return 0;
				}
				if(nsec_has_type(nsec, qinfo->qtype)) {
					return 0;
				}
				*wc = ce;
				return 1;
			}
		} else {
			/* See if the next owner name covers a wildcard
			 * empty non-terminal. */
			while (dname_canonical_compare(nsec->rk.dname, nm) < 0) {
				/* wildcard does not apply if qname below
				 * the name that exists under the '*' */
				if (dname_subdomain_c(qinfo->qname, nm))
					break;
				/* but if it is a wildcard and qname is below
				 * it, then the wildcard applies. The wildcard
				 * is an empty nonterminal. nodata proven. */
				if (dname_is_wild(nm)) {
					size_t ce_len = ln;
					uint8_t* ce = nm;
					dname_remove_label(&ce, &ce_len);
					if(dname_strict_subdomain_c(qinfo->qname, ce)) {
						*wc = ce;
						return 1;
					}
				}
				dname_remove_label(&nm, &ln);
			}
		}

		/* Otherwise, this NSEC does not prove ENT and is not a 
		 * wildcard, so it does not prove NODATA. */
		return 0;
	}

	/* If the qtype exists, then we should have gotten it. */
	if(nsec_has_type(nsec, qinfo->qtype)) {
		return 0;
	}

	/* if the name is a CNAME node, then we should have gotten the CNAME*/
	if(nsec_has_type(nsec, LDNS_RR_TYPE_CNAME)) {
		return 0;
	}

	/* If an NS set exists at this name, and NOT a SOA (so this is a 
	 * zone cut, not a zone apex), then we should have gotten a 
	 * referral (or we just got the wrong NSEC). 
	 * The reverse of this check is used when qtype is DS, since that
	 * must use the NSEC from above the zone cut. */
	if(qinfo->qtype != LDNS_RR_TYPE_DS &&
		nsec_has_type(nsec, LDNS_RR_TYPE_NS) && 
		!nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) {
		return 0;
	} else if(qinfo->qtype == LDNS_RR_TYPE_DS &&
		nsec_has_type(nsec, LDNS_RR_TYPE_SOA) &&
		!dname_is_root(qinfo->qname)) {
		return 0;
	}

	return 1;
}

int 
val_nsec_proves_name_error(struct ub_packed_rrset_key* nsec, uint8_t* qname)
{
	uint8_t* owner = nsec->rk.dname;
	uint8_t* next;
	size_t nlen;
	if(!nsec_get_next(nsec, &next, &nlen))
		return 0;

	/* If NSEC owner == qname, then this NSEC proves that qname exists. */
	if(query_dname_compare(qname, owner) == 0) {
		return 0;
	}

	/* If NSEC is a parent of qname, we need to check the type map
	 * If the parent name has a DNAME or is a delegation point, then 
	 * this NSEC is being misused. */
	if(dname_subdomain_c(qname, owner) && 
		(nsec_has_type(nsec, LDNS_RR_TYPE_DNAME) ||
		(nsec_has_type(nsec, LDNS_RR_TYPE_NS) 
			&& !nsec_has_type(nsec, LDNS_RR_TYPE_SOA))
		)) {
		return 0;
	}

	if(query_dname_compare(owner, next) == 0) {
		/* this nsec is the only nsec */
		/* zone.name NSEC zone.name, disproves everything else */
		/* but only for subdomains of that zone */
		if(dname_strict_subdomain_c(qname, next))
			return 1;
	}
	else if(dname_canonical_compare(owner, next) > 0) {
		/* this is the last nsec, ....(bigger) NSEC zonename(smaller) */
		/* the names after the last (owner) name do not exist 
		 * there are no names before the zone name in the zone 
		 * but the qname must be a subdomain of the zone name(next). */
		if(dname_canonical_compare(owner, qname) < 0 &&
			dname_strict_subdomain_c(qname, next))
			return 1;
	} else {
		/* regular NSEC, (smaller) NSEC (larger) */
		if(dname_canonical_compare(owner, qname) < 0 &&
		   dname_canonical_compare(qname, next) < 0) {
			return 1;
		}
	}
	return 0;
}

int val_nsec_proves_insecuredelegation(struct ub_packed_rrset_key* nsec, 
	struct query_info* qinfo)
{
	if(nsec_has_type(nsec, LDNS_RR_TYPE_NS) &&
		!nsec_has_type(nsec, LDNS_RR_TYPE_DS) &&
		!nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) {
		/* see if nsec signals an insecure delegation */
		if(qinfo->qtype == LDNS_RR_TYPE_DS) {
			/* if type is DS and qname is equal to nsec, then it
			 * is an exact match nsec, result not insecure */
			if(dname_strict_subdomain_c(qinfo->qname,
				nsec->rk.dname))
				return 1;
		} else {
			if(dname_subdomain_c(qinfo->qname, nsec->rk.dname))
				return 1;
		}
	}
	return 0;
}

uint8_t* 
nsec_closest_encloser(uint8_t* qname, struct ub_packed_rrset_key* nsec)
{
	uint8_t* next;
	size_t nlen;
	uint8_t* common1, *common2;
	if(!nsec_get_next(nsec, &next, &nlen))
		return NULL;
	/* longest common with owner or next name */
	common1 = dname_get_shared_topdomain(nsec->rk.dname, qname);
	common2 = dname_get_shared_topdomain(next, qname);
	if(dname_count_labels(common1) > dname_count_labels(common2))
		return common1;
	return common2;
}

int val_nsec_proves_positive_wildcard(struct ub_packed_rrset_key* nsec, 
	struct query_info* qinf, uint8_t* wc)
{
	uint8_t* ce;
	/*  1) prove that qname doesn't exist and 
	 *  2) that the correct wildcard was used
	 *  nsec has been verified already. */
	if(!val_nsec_proves_name_error(nsec, qinf->qname))
		return 0;
	/* check wildcard name */
	ce = nsec_closest_encloser(qinf->qname, nsec);
	if(!ce)
		return 0;
	if(query_dname_compare(wc, ce) != 0) {
		return 0;
	}
	return 1;
}

int 
val_nsec_proves_no_wc(struct ub_packed_rrset_key* nsec, uint8_t* qname, 
	size_t qnamelen)
{
	/* Determine if a NSEC record proves the non-existence of a 
	 * wildcard that could have produced qname. */
	int labs;
	int i;
	uint8_t* ce = nsec_closest_encloser(qname, nsec);
	uint8_t* strip;
	size_t striplen;
	uint8_t buf[LDNS_MAX_DOMAINLEN+3];
	if(!ce)
		return 0;
	/* we can subtract the closest encloser count - since that is the
	 * largest shared topdomain with owner and next NSEC name,
	 * because the NSEC is no proof for names shorter than the owner 
	 * and next names. */
	labs = dname_count_labels(qname) - dname_count_labels(ce);

	for(i=labs; i>0; i--) {
		/* i is number of labels to strip off qname, prepend * wild */
		strip = qname;
		striplen = qnamelen;
		dname_remove_labels(&strip, &striplen, i);
		if(striplen > LDNS_MAX_DOMAINLEN-2)
			continue; /* too long to prepend wildcard */
		buf[0] = 1;
		buf[1] = (uint8_t)'*';
		memmove(buf+2, strip, striplen);
		if(val_nsec_proves_name_error(nsec, buf)) {
			return 1;
		}
	}
	return 0;
}

/**
 * Find shared topdomain that exists
 */
static void
dlv_topdomain(struct ub_packed_rrset_key* nsec, uint8_t* qname,
	uint8_t** nm, size_t* nm_len)
{
	/* make sure reply is part of nm */
	/* take shared topdomain with left of NSEC. */

	/* because, if empty nonterminal, then right is subdomain of qname.
	 * and any shared topdomain would be empty nonterminals.
	 * 
	 * If nxdomain, then the right is bigger, and could have an 
	 * interesting shared topdomain, but if it does have one, it is
	 * an empty nonterminal. An empty nonterminal shared with the left
	 * one. */
	int n;
	uint8_t* common = dname_get_shared_topdomain(qname, nsec->rk.dname);
	n = dname_count_labels(*nm) - dname_count_labels(common);
	dname_remove_labels(nm, nm_len, n);
}

int val_nsec_check_dlv(struct query_info* qinfo,
        struct reply_info* rep, uint8_t** nm, size_t* nm_len)
{
	uint8_t* next;
	size_t i, nlen;
	int c;
	/* we should now have a NOERROR/NODATA or NXDOMAIN message */
	if(rep->an_numrrsets != 0) {
		return 0;
	}
	/* is this NOERROR ? */
	if(FLAGS_GET_RCODE(rep->flags) == LDNS_RCODE_NOERROR) {
		/* it can be a plain NSEC match - go up one more level. */
		/* or its an empty nonterminal - go up to nonempty level */
		for(i=0; i<rep->ns_numrrsets; i++) {
			if(htons(rep->rrsets[i]->rk.type)!=LDNS_RR_TYPE_NSEC ||
				!nsec_get_next(rep->rrsets[i], &next, &nlen))
				continue;
			c = dname_canonical_compare(
				rep->rrsets[i]->rk.dname, qinfo->qname);
			if(c == 0) {
				/* plain match */
				if(nsec_has_type(rep->rrsets[i],
					LDNS_RR_TYPE_DLV))
					return 0;
				dname_remove_label(nm, nm_len);
				return 1;
			} else if(c < 0 && 
				dname_strict_subdomain_c(next, qinfo->qname)) {
				/* ENT */
				dlv_topdomain(rep->rrsets[i], qinfo->qname,
					nm, nm_len);
				return 1;
			}
		}
		return 0;
	}

	/* is this NXDOMAIN ? */
	if(FLAGS_GET_RCODE(rep->flags) == LDNS_RCODE_NXDOMAIN) {
		/* find the qname denial NSEC record. It can tell us
		 * a closest encloser name; or that we not need bother */
		for(i=0; i<rep->ns_numrrsets; i++) {
			if(htons(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC)
				continue;
			if(val_nsec_proves_name_error(rep->rrsets[i], 
				qinfo->qname)) {
				log_nametypeclass(VERB_ALGO, "topdomain on",
					rep->rrsets[i]->rk.dname, 
					ntohs(rep->rrsets[i]->rk.type), 0);
				dlv_topdomain(rep->rrsets[i], qinfo->qname,
					nm, nm_len);
				return 1;
			}
		}
		return 0;
	}
	return 0;
}