#$Id: NSECepsilon.pm,v 1.7 2004/11/29 18:24:12 olaf Exp $ 	-*-perl-*-


=head1 NSECepsilon library.


This library contains functions to find the closest predecessor and
closest successor to a given domain name.

In addition there are two utility functions that one can use to 
create a signed zone that contains only NSECs that point to the closest
sucsessor of the names available in the unsigned zones.

=head2 Implementation

This version implements draft-sisson-dnsext-dns-name-p-s-00.txt in its
least optimized form. 

It makes a distinction between clossest successor in the case of
NXDOMAIN answers and clossest successor in the case of NOERROR. 

One can drastically shorten the domain names by counting the
labeldepth in ones zone and by taken into account the maximum number
of characters present in the zone at each particular label depth.

=head1 Functions

=cut

package Net::DNS::SEC::NSECepsilon;

use bytes;
use strict;
use Net::DNS qw(name2labels wire2presentation);
use Net::DNS::Zone::Parser;



use vars qw(
    $VERSION
    @ISA
    @EXPORT
    @EXPORT_OK
);


use Exporter;
@ISA     = qw(Exporter);
$VERSION = '0.00_3';


@EXPORT = qw(name_plus_epsilon name_min_epsilon preproc_zone strip_zone);




my $debug=0;

my $maxnamelength=255; # This is the maximum length in wire format.
                       # In presentation format one has to add 
                       # the number of charactes in the labels add the number
                       # of dots between the labels and add 2 for the trailing
                       # NULL octet and the first size octet


my $maxlabellength=63; # maximum number of chars in a label.
my $max_sort=pack("C",0xff);
my $min_sort=pack("C",0x00);
my $junkidentifyer="Bert_Created_a_Mess_again";


=head2 name_min_epsilon

    my ($dname,$origin)=("bert.secret-wg.org","secret-wg.org");
    my $closest_predecessor=name_min_epsilon($dname,$origin);

Returns the closest_predecessor given a domain name and the originin
of the zone inwhich this domain name 

dies on errors.

=cut


sub name_min_epsilon {

    use Net::DNS::SEC::NSECepsilon;
    my $name=shift;
    my $apex=shift;



    die "two arguments needed" unless defined($apex);

    
    my $result;
    #append dot for consistency
    $apex .= "." unless $apex=~ /\.$/; 
    $name .= "." unless $name=~ /\.$/; 
    my $namelength=length(Net::DNS::RR->_name2wire($name));
    die "Namelength larger than $maxnamelength" if $namelength>$maxnamelength;
    die "Not in zone" unless ($name=~s/(.*)$apex$/$1/);
    my @alabels=name2labels($apex);
    my @nlabels=name2labels($name);

    
    if (@nlabels==0){
	# We are at the apex case 2.1
	print "Case 2.1\n" if $debug;
	my $label;
	while ($namelength<$maxnamelength){
	    my $labellength=0;
	    while ($labellength < $maxlabellength   &&
		   $namelength < $maxnamelength
		   ){
		$label.=$max_sort;
		$namelength++; 	 
		$labellength++;
	    }
	    unshift @nlabels, $label;
	    $namelength++;  # This takes into acount the length byte
	    $label="";
	}
	return (labels2name(@nlabels).".".labels2name(@alabels).".");
    }elsif($nlabels[0] eq $min_sort ){
	# case 2.2
	print "Case 2.2\n" if $debug;
	shift(@nlabels);
	return (labels2name(@nlabels).".".labels2name(@alabels).".");

    }else{
	print "Case 2.3 ($name [$namelength])\n" if $debug;
	$nlabels[0]=~/(.*)(.)$/; # least significant octet
	$nlabels[0]=defined($1)?$1:"";
	#  $nlabels[0] has its last octet stripped 
	#  append the last octed
	#  decremented by one if it is not the minimum value

	#  Note that all this has been reduced to lowercase
	my $char=$2;
	
	# We do some magic with $label;
	my $label;
	
	if ($char ne $min_sort){
	    # Hack to jump over the uppercase ASCII
	    $char="A" if $char eq "[";
	    $nlabels[0].=lc (pack("C", unpack("C",$char)-1));
	    # Store @nlabel[0] and shift it from the
	    # @labels array. Have it topped off with $max_val below
	    # and then put it back.
	    $label=$nlabels[0];
	    shift @nlabels;
	}else{
	    # $2 equaled $min_sort ... don't do nothing, $nlabels[0] is 
	    # one octed smaller.
	    $namelength-=1;
	    $label="";
	}

	# Filling up with max val.
	print "Case 2.4 (". labels2name(@nlabels).".".labels2name(@alabels).".[$namelength])\n" if $debug;

	



	while ($namelength<$maxnamelength){
	    my $labellength=length($label);
	    while ($labellength < $maxlabellength  &&
		   $namelength < $maxnamelength
		   ){
		$label.=$max_sort;
		$namelength++; 	 
		$labellength++;

	    }
	    unshift @nlabels, $label;
	    $namelength++;  # This takes into acount the length byte
	    $label="";
	}
	
	return (labels2name(@nlabels).".".labels2name(@alabels).".");
	
    }
    die "Dropped through if-then";
}


=head2 name_plus_epsilon

    use Net::DNS::SEC::NSECepsilon;
    my ($dname,$origin)=("bert.secret-wg.org","secret-wg.org");
    my $closest_successor=name_plus_epsilon($dname,$origin,$is_nxdomain);

Returns the closest_successor given a domain name and the originin
of the zone inwhich this domain name. 

If $is_nxdomain evaluates to true then care will be taken that the
closest successor does not turn "$dname" into an empty non-terminal.


This is because of the following reason. If one wants to use the
closes successor to proof an "NXDOMAIN" the presense of "$dname" with
subdomains will proof the existence of the _name_ "$dname", that sort
of proof is inconsistent with "NXDOMAIN".

For example.
if is_nxdomain==0 the clossest successor of foo.example.com. is:
    \000.foo.example.com.
in the case that  is_nxdomain==1 the clossest successor will be
    foo\000.example.com.

dies on errors.

=cut


# In the case that $nxdomain evaluates to true we will not add labels, as
# these indicate empty non terminals. 

sub name_plus_epsilon {
    my $name=shift;
    my $apex=shift;
    my $nxdomain=shift;

    die "two arguments needed" unless defined($apex);
    my $first_pass=shift;
    
    $first_pass=1 unless defined ($first_pass);
    
    my $result;

    #append dot for consistency
    $apex .= "." unless $apex=~ /\.$/; 
    $name .= "." unless $name=~ /\.$/; 

    my $namelength=length(Net::DNS::RR->_name2wire($name));

    die "Namelength larger than $maxnamelength" if $namelength>$maxnamelength;
    die "Not in zone" unless ($name=~s/(.*)$apex$/$1/);
    my @alabels=name2labels($apex);
    my @nlabels=name2labels($name);


    # Calculate the length based on wire format.
    if (  $namelength+1 < $maxnamelength && $first_pass && ! $nxdomain ){
	print "Case 3.1\n" if $debug;
	unshift (@nlabels,  $min_sort );
	return (labels2name(@nlabels).".".labels2name(@alabels).".");

    }elsif ($namelength < $maxnamelength &&
	    length($nlabels[0])<$maxlabellength && $first_pass  ){
	
	print "Case 3.2 labellength:".length($nlabels[0])."\n" if $debug;
	$nlabels[0].=$min_sort;

	return (labels2name(@nlabels).".".labels2name(@alabels).".");
	
    }elsif ($nlabels[0] !~ /^[$max_sort]*$/){

	print "Case 3.3 ($namelength)\n" if $debug;

	chop $nlabels[0] while ($nlabels[0] =~ /$max_sort$/);
	$nlabels[0]=~s/(.)$//;
	my $char=$1;
	# Hack to jump over the uppercase characters.
	$char="Z" if ($char eq "@");
        $nlabels[0].=lc (pack("C" ,unpack("C",$char)+1));
	
	return (labels2name(@nlabels).".".labels2name(@alabels).".");
    }else{
	print "Case 3.4 ($namelength)\n" if $debug;
	shift @nlabels;
	if (@nlabels){
	    name_plus_epsilon (labels2name(@nlabels).".".labels2name(@alabels).".",
			       $apex,$nxdomain,0) ;  #@nlabels equals 0 if the 
	    # name was only one level deep
	}else{
	    return (labels2name(@alabels).".");	
	}
    }
}



=head2 preproc_zone, strip_zone

These two functions are typically used in combination, in two seperate
scripts.

    use Net::DNS::SEC::NSECepsilon;
    preproc_zone($origin,$zonefile);



    use Net::DNS::SEC::NSECepsilon;
    strip_zone($origin,$zonefile);




Reads the zone for "$origin" from "$zonefile", strips any of the
available security records ( DNSKEY, RRSIG, NSEC ) and for every
domain name "dname" in the zone will add  a TXT record owned by
"dname+epsilon".

The resulting zone is returned to STDOUT.


This zone can be signed by BINDs dnssec-signzone and then "strip_zone"
can be used to remove the RRs with the owner names that were added by
prepoc_zone (removes the TXT, NSEC and RRSIGs).


The result is a signed zone with NSEC records that span to the clossest
successors of the names in the zone.

=cut


sub preproc_zone {
    my $domainname=shift;
    my $zonefile=shift;

    my $parser=Net::DNS::Zone::Parser->new();
    
    my $err=$parser->read($zonefile,
			 { ORIGIN => $domainname,
			   CREATE_RR => 1,
			   STRIP_SEC=>1,
		       });
		     
    my %seen;
    die $err if $err; 
    my $RRs= $parser->get_array();
    
    foreach my $rr (@$RRs){
	$rr->print;
	next if defined($seen{$rr->name});
	$seen{$rr->name}=1;


	# All DS RRs have been stripped. 
	# Assume there is no other RR data at the delegated name other than 
	# the NS RR
	if ($rr->name ne $domainname && $rr->type eq "NS"){
	    #Delegation
	    $seen{$rr->name}=1;
	    next;
	}

	my $name=name_plus_epsilon($rr->name,$domainname);
	chop $name;  #Net::DNS::RR does not like trailing dots.
	my $nsec=Net::DNS::RR->new(
				   name    => $name,
				   ttl     => 00,
				   class   => "IN",
				   type    => "TXT",

				   char_str_list => [$junkidentifyer],
				   );

	$nsec->print;
    }
}




sub strip_zone {
    my $domainname=shift;
    my $zonefile=shift;

    my $parser=Net::DNS::Zone::Parser->new();
    
    my $err=$parser->read($zonefile,
			 { ORIGIN => $domainname,
			   CREATE_RR => 1,
		       });
		     
    my %seen;
    die $err if $err; 
    my $RRs= $parser->get_array();
    
    #firstloop collect all ownernames 
    #for which we there is s TXT record with the junkidentifyer text

    foreach my $rr (@$RRs){
	next if ($rr->type ne "TXT");
	next if ( ($rr->char_str_list())[0] ne $junkidentifyer);
	$seen{$rr->name}=1;
    }

    # second loop... throw away RR data with "seen" names
    foreach my $rr (@$RRs){
        $rr->print if (! $seen{$rr->name});
    }
    
}



sub labels2name {
    my @names=@_;
    my $dname="";;
    foreach my $label (@names){
        my $escapedlabel= wire2presentation ($label);
        $dname = $dname . ".".$escapedlabel ;
    }
    # remove the . that lives at the start.
    return substr($dname,1);
}



=head1 TODO

There are a number of optimizations that can be used to optimize this if
the structure of the zone is known.


The  preproc_zone and strip_zone do not deal with GLUE well.

=head1 COPYRIGHT

Copyright (c) 2004  RIPE NCC.  Author Olaf M. Kolkman 
<net-dns-sec@ripe.net>

All Rights Reserved

Permission to use, copy, modify, and distribute this software and its
documentation for any purpose and without fee is hereby granted,
provided that the above copyright notice appear in all copies and that
both that copyright notice and this permission notice appear in
supporting documentation, and that the name of the author not be
used in advertising or publicity pertaining to distribution of the
software without specific, written prior permission.


THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS; IN NO EVENT SHALL
AUTHOR BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY
DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.





=cut