Incorrect xt_iprange boundary check for IPv6

Incorrect xt_iprange boundary check for IPv6

[Thomas Jacob]

Developed for and tested on 2.6.27.57, but applies and compiles
in current mainline as well (haven't tested it there though).

See the following script for a demonstration of the problem:

#!/bin/sh
PREFIX=fc42:4242
LEFTOUT=$PREFIX:0:ffff:ffff:ffff:ffff:ffff
FROM=$PREFIX:1::0
MIDDLE=$PREFIX:1::8000:0:0:0
TILL=$PREFIX:1::ffff:ffff:ffff:ffff
RIGHTOUT=$PREFIX:2::0
SUBNET=$PREFIX:1::/64
SOURCE=fc23:2323::1
CHAIN=iprange_bug

ip6tables -S OUTPUT | fgrep -q -- '-A OUTPUT -j '"$CHAIN" \
	&& ip6tables -D OUTPUT -j $CHAIN

ip6tables -F $CHAIN 2>/dev/null
ip6tables -X $CHAIN 2>/dev/null
ip6tables -N $CHAIN

ip6tables -A $CHAIN -p icmpv6 --icmpv6-type echo-request -s $SOURCE -m iprange --dst-range $FROM-$TILL
ip6tables -A $CHAIN -p icmpv6 --icmpv6-type echo-request -s $SOURCE -d $SUBNET -j DROP

ip6tables -I OUTPUT 1 -j $CHAIN

ip addr replace $SOURCE/128 dev lo
ip addr replace $LEFTOUT/128 dev lo
ip addr replace $FROM/128 dev lo
ip addr replace $MIDDLE/128 dev lo
ip addr replace $TILL/128 dev lo
ip addr replace $RIGHTOUT/128 dev lo

for IP in $LEFTOUT $FROM $MIDDLE $TILL $RIGHTOUT
do
	ping6 -c 1 -W 1 -q -I $SOURCE $IP | grep ^PING
done

echo
ip6tables -vnL $CHAIN

ip addr del $RIGHTOUT/128 dev lo
ip addr del $TILL/128 dev lo
ip addr del $MIDDLE/128 dev lo
ip addr del $FROM/128 dev lo
ip addr del $LEFTOUT/128 dev lo
ip addr del $SOURCE/128 dev lo

ip6tables -D OUTPUT -j $CHAIN
ip6tables -F $CHAIN
ip6tables -X $CHAIN

[PATCH] Incorrect xt_iprange boundary check for IPv6

[Thomas Jacob]

iprange_ipv6_sub was substracting 2 unsigned ints and then casting
the result to int to find out whether they are lt, eq or gt each
other, this doesn't work if the full 32 bits of each part
can be used in IPv6 addresses. Patch should remedy that without
significant performance penalties.

Signed-off-by: Thomas Jacob <jacob@internet24.de>
---
 net/netfilter/xt_iprange.c |   16 +++++++---------
 1 files changed, 7 insertions(+), 9 deletions(-)

diff --git a/net/netfilter/xt_iprange.c b/net/netfilter/xt_iprange.c
index 4b5741b..3cc5d21 100644
--- a/net/netfilter/xt_iprange.c
+++ b/net/netfilter/xt_iprange.c
@@ -96,15 +96,13 @@ iprange_mt4(const struct sk_buff *skb, const struct net_device *in,
 }
 
 static inline int
-iprange_ipv6_sub(const struct in6_addr *a, const struct in6_addr *b)
+iprange_ipv6_lt(const struct in6_addr *a, const struct in6_addr *b)
 {
 	unsigned int i;
-	int r;
 
 	for (i = 0; i < 4; ++i) {
-		r = ntohl(a->s6_addr32[i]) - ntohl(b->s6_addr32[i]);
-		if (r != 0)
-			return r;
+		if(ntohl(a->s6_addr32[i]) != ntohl(b->s6_addr32[i]))
+			return ntohl(a->s6_addr32[i]) < ntohl(b->s6_addr32[i]);
 	}
 
 	return 0;
@@ -121,15 +119,15 @@ iprange_mt6(const struct sk_buff *skb, const struct net_device *in,
 	bool m;
 
 	if (info->flags & IPRANGE_SRC) {
-		m  = iprange_ipv6_sub(&iph->saddr, &info->src_min.in6) < 0;
-		m |= iprange_ipv6_sub(&iph->saddr, &info->src_max.in6) > 0;
+		m  = iprange_ipv6_lt(&iph->saddr, &info->src_min.in6);
+		m |= iprange_ipv6_lt(&info->src_max.in6, &iph->saddr);
 		m ^= !!(info->flags & IPRANGE_SRC_INV);
 		if (m)
 			return false;
 	}
 	if (info->flags & IPRANGE_DST) {
-		m  = iprange_ipv6_sub(&iph->daddr, &info->dst_min.in6) < 0;
-		m |= iprange_ipv6_sub(&iph->daddr, &info->dst_max.in6) > 0;
+		m  = iprange_ipv6_lt(&iph->daddr, &info->dst_min.in6);
+		m |= iprange_ipv6_lt(&info->dst_max.in6, &iph->daddr);
 		m ^= !!(info->flags & IPRANGE_DST_INV);
 		if (m)
 			return false;
-- 
1.5.6.5

Re: [PATCH] Incorrect xt_iprange boundary check for IPv6

[Jan Engelhardt]

On Saturday 2011-01-22 15:10, Thomas Jacob wrote:

>iprange_ipv6_sub was substracting 2 unsigned ints and then casting
>the result to int to find out whether they are lt, eq or gt each
>other, this doesn't work if the full 32 bits of each part
>can be used in IPv6 addresses. Patch should remedy that without
>significant performance penalties.

Correctness before speed ;)

The algo change looks ok to me, thanks for spotting.

> static inline int
>-iprange_ipv6_sub(const struct in6_addr *a, const struct in6_addr *b)
>+iprange_ipv6_lt(const struct in6_addr *a, const struct in6_addr *b)
> {
> 	unsigned int i;
>-	int r;
> 
> 	for (i = 0; i < 4; ++i) {
>-		r = ntohl(a->s6_addr32[i]) - ntohl(b->s6_addr32[i]);
>-		if (r != 0)
>-			return r;
>+		if(ntohl(a->s6_addr32[i]) != ntohl(b->s6_addr32[i]))
>+			return ntohl(a->s6_addr32[i]) < ntohl(b->s6_addr32[i]);
> 	}
> 
> 	return 0;

Re: [PATCH] Incorrect xt_iprange boundary check for IPv6

[Jozsef Kadlecsik]

Hi Thomas,

On Sat, 22 Jan 2011, Thomas Jacob wrote:

> iprange_ipv6_sub was substracting 2 unsigned ints and then casting
> the result to int to find out whether they are lt, eq or gt each
> other, this doesn't work if the full 32 bits of each part
> can be used in IPv6 addresses. Patch should remedy that without
> significant performance penalties.
> 
> Signed-off-by: Thomas Jacob <jacob@internet24.de>
> ---
>  net/netfilter/xt_iprange.c |   16 +++++++---------
>  1 files changed, 7 insertions(+), 9 deletions(-)
> 
> diff --git a/net/netfilter/xt_iprange.c b/net/netfilter/xt_iprange.c
> index 4b5741b..3cc5d21 100644
> --- a/net/netfilter/xt_iprange.c
> +++ b/net/netfilter/xt_iprange.c
> @@ -96,15 +96,13 @@ iprange_mt4(const struct sk_buff *skb, const struct net_device *in,
>  }
>  
>  static inline int
> -iprange_ipv6_sub(const struct in6_addr *a, const struct in6_addr *b)
> +iprange_ipv6_lt(const struct in6_addr *a, const struct in6_addr *b)
>  {
>  	unsigned int i;
> -	int r;
>  
>  	for (i = 0; i < 4; ++i) {
> -		r = ntohl(a->s6_addr32[i]) - ntohl(b->s6_addr32[i]);
> -		if (r != 0)
> -			return r;
> +		if(ntohl(a->s6_addr32[i]) != ntohl(b->s6_addr32[i]))
> +			return ntohl(a->s6_addr32[i]) < ntohl(b->s6_addr32[i]);
>  	}

Why do you convert to host order in the inequality test? It could be left 
out.

Best regards,
Jozsef
-
E-mail  : kadlec@blackhole.kfki.hu, kadlec@mail.kfki.hu
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
          H-1525 Budapest 114, POB. 49, Hungary

Re: [PATCH] Incorrect xt_iprange boundary check for IPv6

[Thomas Jacob]

On Sun, 2011-01-23 at 14:53 +0100, Jozsef Kadlecsik wrote:
> > -			return r;
> > +		if(ntohl(a->s6_addr32[i]) != ntohl(b->s6_addr32[i]))
> > +			return ntohl(a->s6_addr32[i]) < ntohl(b->s6_addr32[i]);
> >  	}
> 
> Why do you convert to host order in the inequality test? It could be left 
> out.

Yes it can be, just a left over from the old code I suppose. Didn't
really thing about that ;)

But if we are talking about performance, what about the following
part:       

if (info->flags & IPRANGE_SRC) {
  m  = iprange_ipv6_lt(&iph->saddr, &info->src_min.in6);
  m |= iprange_ipv6_lt(&info->src_max.in6, &iph->saddr);
  m ^= !!(info->flags & IPRANGE_SRC_INV);
  if (m)
    return false;
}

Shouldn't this be  m ||= .. in the second call to iprange_ipv6_lt,
to allow for some short circuit optimizations? Or in order
to reduce the rather asymmetric behaviour then, shouldn't these two
function calls be merged into something like

static inline int
iprange_ipv6_cmp(const struct in6_addr *a, const struct in6_addr *b,  
   const struct in6_addr *x )
{
        unsigned int i;

        for (i = 0; i < 4; ++i) {
                if(x->s6_addr32[i] != a->s6_addr32[i])
                  return ntohl(x->s6_addr32[i])<ntohl(a->s6_addr32[i]);
                if(x->s6_addr32[i] != b->s6_addr32[i])
                  return ntohl(b->s6_addr32[i])<ntohl(x->s6_addr32[i]);
               
        }

        return 0;
}

Or would that be bad from a 1st level caching point of view?

Re: [PATCH] Incorrect xt_iprange boundary check for IPv6

[Jan Engelhardt]

On Monday 2011-01-24 12:31, Thomas Jacob wrote:
>
>if (info->flags & IPRANGE_SRC) {
>  m  = iprange_ipv6_lt(&iph->saddr, &info->src_min.in6);
>  m |= iprange_ipv6_lt(&info->src_max.in6, &iph->saddr);
>  m ^= !!(info->flags & IPRANGE_SRC_INV);
>  if (m)
>    return false;
>}
>
>Shouldn't this be  m ||= ..

C does not have a ||= operator. This is not Perl.
Which is why either you make sure iprange_ipv6_lt returns a bool,
or force one by means of !!.

>to allow for some short circuit optimizations?

Since there is no ||=, it would be

m = iprange_ipv6_lt(&iph->saddr, &info->src_min.in6);
if (!m)
	m = iprange_ipv6_lt(&info->src_max.in6, &iph->saddr);

Re: [PATCH] Incorrect xt_iprange boundary check for IPv6

[Patrick McHardy]

Am 24.01.2011 13:13, schrieb Thomas Jacob:
> iprange_ipv6_sub was substracting 2 unsigned ints and then casting
> the result to int to find out whether they are lt, eq or gt each
> other, this doesn't work if the full 32 bits of each part
> can be used in IPv6 addresses. Patch should remedy that without
> significant performance penalties. Also number of ntohl
> calls can be reduced this way (Jozsef Kadlecsik).

This looks fine to me, applied with a minor cosmetic change
(space before opening parens after if). Thanks Thomas.

[PATCH] Incorrect xt_iprange boundary check for IPv6

[Thomas Jacob]

iprange_ipv6_sub was substracting 2 unsigned ints and then casting
the result to int to find out whether they are lt, eq or gt each
other, this doesn't work if the full 32 bits of each part
can be used in IPv6 addresses. Patch should remedy that without
significant performance penalties. Also number of ntohl
calls can be reduced this way (Jozsef Kadlecsik).

Signed-off-by: Thomas Jacob <jacob@internet24.de>
---
 net/netfilter/xt_iprange.c |   16 +++++++---------
 1 files changed, 7 insertions(+), 9 deletions(-)

diff --git a/net/netfilter/xt_iprange.c b/net/netfilter/xt_iprange.c
index 4b5741b..140e906 100644
--- a/net/netfilter/xt_iprange.c
+++ b/net/netfilter/xt_iprange.c
@@ -96,15 +96,13 @@ iprange_mt4(const struct sk_buff *skb, const struct net_device *in,
 }
 
 static inline int
-iprange_ipv6_sub(const struct in6_addr *a, const struct in6_addr *b)
+iprange_ipv6_lt(const struct in6_addr *a, const struct in6_addr *b)
 {
 	unsigned int i;
-	int r;
 
 	for (i = 0; i < 4; ++i) {
-		r = ntohl(a->s6_addr32[i]) - ntohl(b->s6_addr32[i]);
-		if (r != 0)
-			return r;
+		if(a->s6_addr32[i] != b->s6_addr32[i])
+			return ntohl(a->s6_addr32[i]) < ntohl(b->s6_addr32[i]);
 	}
 
 	return 0;
@@ -121,15 +119,15 @@ iprange_mt6(const struct sk_buff *skb, const struct net_device *in,
 	bool m;
 
 	if (info->flags & IPRANGE_SRC) {
-		m  = iprange_ipv6_sub(&iph->saddr, &info->src_min.in6) < 0;
-		m |= iprange_ipv6_sub(&iph->saddr, &info->src_max.in6) > 0;
+		m  = iprange_ipv6_lt(&iph->saddr, &info->src_min.in6);
+		m |= iprange_ipv6_lt(&info->src_max.in6, &iph->saddr);
 		m ^= !!(info->flags & IPRANGE_SRC_INV);
 		if (m)
 			return false;
 	}
 	if (info->flags & IPRANGE_DST) {
-		m  = iprange_ipv6_sub(&iph->daddr, &info->dst_min.in6) < 0;
-		m |= iprange_ipv6_sub(&iph->daddr, &info->dst_max.in6) > 0;
+		m  = iprange_ipv6_lt(&iph->daddr, &info->dst_min.in6);
+		m |= iprange_ipv6_lt(&info->dst_max.in6, &iph->daddr);
 		m ^= !!(info->flags & IPRANGE_DST_INV);
 		if (m)
 			return false;
-- 
1.5.6.5