[PATCH net] ip: make IP identifiers less predictable

[PATCH net] ip: make IP identifiers less predictable

[Eric Dumazet]

From: Eric Dumazet <edumazet@google.com>

In "Counting Packets Sent Between Arbitrary Internet Hosts", Jeffrey and
Jedidiah describe ways exploiting linux IP identifier generation to
infer whether two machines are exchanging packets.

With commit 73f156a6e8c1 ("inetpeer: get rid of ip_id_count"), we
changed IP id generation, but this does not really prevent this
side-channel technique.

This patch adds a random amount of perturbation so that IP identifiers
for a given destination [1] are no longer monotonically increasing after
an idle period.

Note that prandom_u32_max(1) returns 0, so if generator is used at most
once per jiffy, this patch inserts no hole in the ID suite and do not
increase collision probability.

This is jiffies based, so in the worst case (HZ=1000), the id can
rollover after ~65 seconds of idle time, which should be fine.

If I ping the patched target, we can see ID are now hard to predict.

21:57:11.008086 IP (...)
    A > target: ICMP echo request, seq 1, length 64
21:57:11.010752 IP (... id 2081 ...)
    target > A: ICMP echo reply, seq 1, length 64

21:57:12.013133 IP (...)
    A > target: ICMP echo request, seq 2, length 64
21:57:12.015737 IP (... id 3039 ...)
    target > A: ICMP echo reply, seq 2, length 64

21:57:13.016580 IP (...)
    A > target: ICMP echo request, seq 3, length 64
21:57:13.019251 IP (... id 3437 ...)
    target > A: ICMP echo reply, seq 3, length 64

[1] TCP sessions uses a per flow ID generator not changed by this patch.

Signed-off-by: Eric Dumazet <edumazet@google.com>
Reported-by: Jeffrey Knockel <jeffk@cs.unm.edu>
Reported-by: Jedidiah R. Crandall <crandall@cs.unm.edu>
Cc: Willy Tarreau <w@1wt.eu>
---
 include/net/ip.h |   11 +----------
 net/ipv4/route.c |   27 +++++++++++++++++++++++++--
 2 files changed, 26 insertions(+), 12 deletions(-)

diff --git a/include/net/ip.h b/include/net/ip.h
index 0e795df05ec9..7596eb22e1ce 100644
--- a/include/net/ip.h
+++ b/include/net/ip.h
@@ -309,16 +309,7 @@ static inline unsigned int ip_skb_dst_mtu(const struct sk_buff *skb)
 	}
 }
 
-#define IP_IDENTS_SZ 2048u
-extern atomic_t *ip_idents;
-
-static inline u32 ip_idents_reserve(u32 hash, int segs)
-{
-	atomic_t *id_ptr = ip_idents + hash % IP_IDENTS_SZ;
-
-	return atomic_add_return(segs, id_ptr) - segs;
-}
-
+u32 ip_idents_reserve(u32 hash, int segs);
 void __ip_select_ident(struct iphdr *iph, int segs);
 
 static inline void ip_select_ident_segs(struct sk_buff *skb, struct sock *sk, int segs)
diff --git a/net/ipv4/route.c b/net/ipv4/route.c
index 3162ea923ded..2e9713a8966f 100644
--- a/net/ipv4/route.c
+++ b/net/ipv4/route.c
@@ -457,8 +457,31 @@ static struct neighbour *ipv4_neigh_lookup(const struct dst_entry *dst,
 	return neigh_create(&arp_tbl, pkey, dev);
 }
 
-atomic_t *ip_idents __read_mostly;
-EXPORT_SYMBOL(ip_idents);
+#define IP_IDENTS_SZ 2048u
+struct ip_ident_bucket {
+	atomic_t	id;
+	u32		stamp32;
+};
+
+static struct ip_ident_bucket *ip_idents __read_mostly;
+
+/* In order to protect privacy, we add a perturbation to identifiers
+ * if one generator is seldom used. This makes hard for an attacker
+ * to infer how many packets were sent between two hosts.
+ */
+u32 ip_idents_reserve(u32 hash, int segs)
+{
+	struct ip_ident_bucket *bucket = ip_idents + hash % IP_IDENTS_SZ;
+	u32 old = ACCESS_ONCE(bucket->stamp32);
+	u32 now = (u32)jiffies;
+	u32 delta = 0;
+
+	if (old != now && cmpxchg(&bucket->stamp32, old, now) == old)
+		delta = prandom_u32_max(now - old);
+
+	return atomic_add_return(segs + delta, &bucket->id) - segs;
+}
+EXPORT_SYMBOL(ip_idents_reserve);
 
 void __ip_select_ident(struct iphdr *iph, int segs)
 {

Re: [PATCH net] ip: make IP identifiers less predictable

[Linus Torvalds]

On Thu, Jul 24, 2014 at 1:07 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
>
> This patch adds a random amount of perturbation so that IP identifiers
> for a given destination [1] are no longer monotonically increasing after
> an idle period.

This certainly looks good to me. It would be good to have actual
testing by Jeffrey &al, but this seems simple and complete.

            Linus

Re: [PATCH net] ip: make IP identifiers less predictable

[Jeffrey Knockel]

On 07/24/2014 12:21 PM, Linus Torvalds wrote:
> On Thu, Jul 24, 2014 at 1:07 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
>>
>> This patch adds a random amount of perturbation so that IP identifiers
>> for a given destination [1] are no longer monotonically increasing after
>> an idle period.
> 
> This certainly looks good to me. It would be good to have actual
> testing by Jeffrey &al, but this seems simple and complete.

I've just tested it, and this easily defeats our implementation of the
side-channel attack, as our implementation assumes we're trying to infer
the value of a per-destination counter that isn't moving on its own.

I've let my thoughts on this problem percolate some more overnight.

Commit 73f156a6e8c1 ("inetpeer: get rid of ip_id_count") really does
change the problem of inferring the existence of traffic between
machines, both for better and for worse.  It helps the problem in one
way in that the IP id counter corresponding to any destination is now
noisier, particularly for high traffic servers, although for servers
with a small population of users this isn't so helpful.  It actually
hurts the problem though in that we don't even need to use our
side-channel if we control enough addresses (or at least an address that
hashes to the same counter as an address whose traffic to the server we
want to measure).  So for an attacker controlling a large number of
addresses trying to measure which of a server's small population of
users are accessing it, the problem actually seems worse since this commit.

So now about how this proposed patch changes things.  It breaks our use
of a side-channel to infer the value of counters, since our
binary-search-like approach which we rely on to efficiently find the
value of the counter just doesn't handle a randomly moving counter.
Moreover, it would seem very difficult to make it robust to that.  I
suspect that the best someone could ever do is infer a rough idea of the
counter at any one time.  And then trying to use our side-channel to
meaningfully infer anything but the largest of differences to the
counter over time would be even more difficult.  So I believe that this
patch adequately addresses the side-channel attack in our paper.

On the other hand, in the post-73f156a6e8c1 world, we also have this new
problem of where an attacker doesn't even need to use our side-channel
if he controls a large number of addresses and can measure the values of
the counters directly.  The proposed patch actually helps with this case
too.  However, the existence of traffic between the server and some
other address could probably still be inferred by a sufficiently
determined attacker.  Certainly it could be if the server is sending the
address a very large number packets, as the signal would just overcome
the noise.  But even if the number of packets being sent is very small,
surprisingly, this may still be inferable under this patch, as, e.g.,

randint(25) + randint(25) + randint(25) + randint(25)

has a much different probability distribution than randint(100), and a
determined attacker may be able to determine if he is sampling from
randint(100) or not with enough samples.

So my thoughts in a nutshell:  I believe that this proposed patch solves
the original problem of attackers being able to infer the value of
counters via a side-channel.  However, in the post-73f156a6e8c1 world,
there's also a new problem which we might care about too where we have
an attacker who controls a large number of addresses.  This patch also
happens to help with this problem too, but maybe not enough, depending
on how sophisticated of an attacker we want to protect against.

Jeff

Re: [PATCH net] ip: make IP identifiers less predictable

[Eric Dumazet]

On Fri, 2014-07-25 at 09:55 -0600, Jeffrey Knockel wrote:

> So my thoughts in a nutshell:  I believe that this proposed patch solves
> the original problem of attackers being able to infer the value of
> counters via a side-channel.  However, in the post-73f156a6e8c1 world,
> there's also a new problem which we might care about too where we have
> an attacker who controls a large number of addresses.  This patch also
> happens to help with this problem too, but maybe not enough, depending
> on how sophisticated of an attacker we want to protect against.

What do you mean by "an attacker who controls a large number of
addresses" ?

The hash(daddr) -> slot function is not known, as we use a Jenkin hash
with a secret ( ip_idents_hashrnd & ip6_idents_hashrnd )

We might change the hash to use both daddr & saddr to increase
protection.

pre-73f156a6e8c1 was horrible, because it was easy to fill inetpeer
table to force a garbage collection. Then when an ID was needed for a
peer that had been evicted, we started again from a fixed base ID
( secure_ip_id() )

Thanks.

Re: [PATCH net] ip: make IP identifiers less predictable

[Linus Torvalds]

On Fri, Jul 25, 2014 at 11:09 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
>
> We might change the hash to use both daddr & saddr to increase
> protection.

.. and maybe protocol too, so that you can't easily use icmp echo
packets to do it for udp packets etc. The underlying jhash is
jhash_3words(), so that would actually be fairly natural for at least
ipv4 (the ipv6 case I didn't look at).

               Linus

Re: [PATCH net] ip: make IP identifiers less predictable

[Eric Dumazet]

On Fri, 2014-07-25 at 11:35 -0700, Linus Torvalds wrote:
> On Fri, Jul 25, 2014 at 11:09 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> >
> > We might change the hash to use both daddr & saddr to increase
> > protection.
> 
> .. and maybe protocol too, so that you can't easily use icmp echo
> packets to do it for udp packets etc. The underlying jhash is
> jhash_3words(), so that would actually be fairly natural for at least
> ipv4 (the ipv6 case I didn't look at).

Right, in fact saddr is probably not worth it.

Its not like servers have dozen of IPv4 addresses anyway...

Re: [PATCH net] ip: make IP identifiers less predictable

[Willy Tarreau]

On Fri, Jul 25, 2014 at 08:38:17PM +0200, Eric Dumazet wrote:
> On Fri, 2014-07-25 at 11:35 -0700, Linus Torvalds wrote:
> > On Fri, Jul 25, 2014 at 11:09 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> > >
> > > We might change the hash to use both daddr & saddr to increase
> > > protection.
> > 
> > .. and maybe protocol too, so that you can't easily use icmp echo
> > packets to do it for udp packets etc. The underlying jhash is
> > jhash_3words(), so that would actually be fairly natural for at least
> > ipv4 (the ipv6 case I didn't look at).
> 
> Right, in fact saddr is probably not worth it.

Yes it is, at least to isolate public and private networks.

> Its not like servers have dozen of IPv4 addresses anyway...

Actually some have many more, even hundreds sometimes (until people
realize they can bind networks to the loopback or do transparent
proxy, where the principle is still true). It's especially true with
front equipments such as reverse proxies and load balancers. SSL
deployed all over the web has made that much worse despite the
introduction of SNI which is not supported by all clients, because
while hosting providers used to assign just a few IPs on which they
bound their servers using virtual hosting, with SSL they tend to
offer one IP address per customer.

Regards,
Willy

Re: [PATCH net] ip: make IP identifiers less predictable

[Hannes Frederic Sowa]

Hi,

On Fr, 2014-07-25 at 20:38 +0200, Eric Dumazet wrote:
> On Fri, 2014-07-25 at 11:35 -0700, Linus Torvalds wrote:
> > On Fri, Jul 25, 2014 at 11:09 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> > >
> > > We might change the hash to use both daddr & saddr to increase
> > > protection.
> > 
> > .. and maybe protocol too, so that you can't easily use icmp echo
> > packets to do it for udp packets etc. The underlying jhash is
> > jhash_3words(), so that would actually be fairly natural for at least
> > ipv4 (the ipv6 case I didn't look at).
> 
> Right, in fact saddr is probably not worth it.
> 
> Its not like servers have dozen of IPv4 addresses anyway...

Another idea, maybe worth looking at:

Since commit 703133de331a7a ("ip: generate unique IP identificator if
local fragmentation is allowed") we started to generate fragmentation
ids in the output path for every packet that has ignore_df set, which
nearly is every packet.

We could try to push that down the stack and only insert the
fragmentation id in ip_fragment. We still need to generate the frag_id
directly from the socket layer, but we can reuse the ip6_frag_id field
in skb_shinfo for IPv4, too.

Then we actually only need to generate fragmentation ids for the VJ
compression workaround, generated from the socket->inet_id. Do we still
need this (I guess, yes)?

Does this sound worth a try or are there any unseen protocol specific
consequences I am not yet aware of? We would stop leaking too many
fragmentation ids with this change.

Thanks,
Hannes

Re: [PATCH net] ip: make IP identifiers less predictable

[Jeffrey Knockel]

On 07/25/2014 12:09 PM, Eric Dumazet wrote:
> What do you mean by "an attacker who controls a large number of
> addresses" ?

In general, I mean any attacker who can read the packets sent to a large
number of different Internet addresses.  Even an attacker who has one
address but can cycle through different assignments may be a problem.

> The hash(daddr) -> slot function is not known, as we use a Jenkin hash
> with a secret ( ip_idents_hashrnd & ip6_idents_hashrnd )

That's true, but the secret never changes, right?  I may not be able to
identify the slot number that any address is hashed to, but I can
identify when some victim address hashes to the same slot as one of my
addresses whose packets I can read.  For instance, if I in short succession

1. Probe value of the IP id counter for each of my addresses
2. Spoof a large number of (e.g.) echo requests from victim address (or
something else to the distribution that I can measure)
3. Again probe value of the IP id counter for each of my addresses

Then I can tell which of my addresses hash to the same slot as the
victim address by whose value of the IP id counter has jumped as a
result of the linux machine sending echo replies to the victim.

Jeff

[PATCH v2 net] ip: make IP identifiers less predictable

[Eric Dumazet]

From: Eric Dumazet <edumazet@google.com>

In "Counting Packets Sent Between Arbitrary Internet Hosts", Jeffrey and
Jedidiah describe ways exploiting linux IP identifier generation to
infer whether two machines are exchanging packets.

With commit 73f156a6e8c1 ("inetpeer: get rid of ip_id_count"), we
changed IP id generation, but this does not really prevent this
side-channel technique.

This patch adds a random amount of perturbation so that IP identifiers
for a given destination [1] are no longer monotonically increasing after
an idle period.

Note that prandom_u32_max(1) returns 0, so if generator is used at most
once per jiffy, this patch inserts no hole in the ID suite and do not
increase collision probability.

This is jiffies based, so in the worst case (HZ=1000), the id can
rollover after ~65 seconds of idle time, which should be fine.

We also change the hash used in __ip_select_ident() to not only hash
on daddr, but also saddr and protocol, so that ICMP probes can not be
used to infer information for other protocols.

If I ping the patched target, we can see ID are now hard to predict.

21:57:11.008086 IP (...)
    A > target: ICMP echo request, seq 1, length 64
21:57:11.010752 IP (... id 2081 ...)
    target > A: ICMP echo reply, seq 1, length 64

21:57:12.013133 IP (...)
    A > target: ICMP echo request, seq 2, length 64
21:57:12.015737 IP (... id 3039 ...)
    target > A: ICMP echo reply, seq 2, length 64

21:57:13.016580 IP (...)
    A > target: ICMP echo request, seq 3, length 64
21:57:13.019251 IP (... id 3437 ...)
    target > A: ICMP echo reply, seq 3, length 64

[1] TCP sessions uses a per flow ID generator not changed by this patch.

Signed-off-by: Eric Dumazet <edumazet@google.com>
Reported-by: Jeffrey Knockel <jeffk@cs.unm.edu>
Reported-by: Jedidiah R. Crandall <crandall@cs.unm.edu>
Cc: Willy Tarreau <w@1wt.eu>
---
v2: add saddr & protocol to hash used in __ip_select_ident()
    add saddr & nexthdr to ipv6_select_ident()

 include/net/ip.h      |   11 +----------
 net/ipv4/route.c      |   32 +++++++++++++++++++++++++++++---
 net/ipv6/ip6_output.c |    4 +++-
 3 files changed, 33 insertions(+), 14 deletions(-)

diff --git a/include/net/ip.h b/include/net/ip.h
index 0e795df05ec9..7596eb22e1ce 100644
--- a/include/net/ip.h
+++ b/include/net/ip.h
@@ -309,16 +309,7 @@ static inline unsigned int ip_skb_dst_mtu(const struct sk_buff *skb)
 	}
 }
 
-#define IP_IDENTS_SZ 2048u
-extern atomic_t *ip_idents;
-
-static inline u32 ip_idents_reserve(u32 hash, int segs)
-{
-	atomic_t *id_ptr = ip_idents + hash % IP_IDENTS_SZ;
-
-	return atomic_add_return(segs, id_ptr) - segs;
-}
-
+u32 ip_idents_reserve(u32 hash, int segs);
 void __ip_select_ident(struct iphdr *iph, int segs);
 
 static inline void ip_select_ident_segs(struct sk_buff *skb, struct sock *sk, int segs)
diff --git a/net/ipv4/route.c b/net/ipv4/route.c
index 3162ea923ded..190199851c9a 100644
--- a/net/ipv4/route.c
+++ b/net/ipv4/route.c
@@ -457,8 +457,31 @@ static struct neighbour *ipv4_neigh_lookup(const struct dst_entry *dst,
 	return neigh_create(&arp_tbl, pkey, dev);
 }
 
-atomic_t *ip_idents __read_mostly;
-EXPORT_SYMBOL(ip_idents);
+#define IP_IDENTS_SZ 2048u
+struct ip_ident_bucket {
+	atomic_t	id;
+	u32		stamp32;
+};
+
+static struct ip_ident_bucket *ip_idents __read_mostly;
+
+/* In order to protect privacy, we add a perturbation to identifiers
+ * if one generator is seldom used. This makes hard for an attacker
+ * to infer how many packets were sent between two points in time.
+ */
+u32 ip_idents_reserve(u32 hash, int segs)
+{
+	struct ip_ident_bucket *bucket = ip_idents + hash % IP_IDENTS_SZ;
+	u32 old = ACCESS_ONCE(bucket->stamp32);
+	u32 now = (u32)jiffies;
+	u32 delta = 0;
+
+	if (old != now && cmpxchg(&bucket->stamp32, old, now) == old)
+		delta = prandom_u32_max(now - old);
+
+	return atomic_add_return(segs + delta, &bucket->id) - segs;
+}
+EXPORT_SYMBOL(ip_idents_reserve);
 
 void __ip_select_ident(struct iphdr *iph, int segs)
 {
@@ -467,7 +490,10 @@ void __ip_select_ident(struct iphdr *iph, int segs)
 
 	net_get_random_once(&ip_idents_hashrnd, sizeof(ip_idents_hashrnd));
 
-	hash = jhash_1word((__force u32)iph->daddr, ip_idents_hashrnd);
+	hash = jhash_3words((__force u32)iph->daddr,
+			    (__force u32)iph->saddr,
+			    iph->protocol,
+			    ip_idents_hashrnd);
 	id = ip_idents_reserve(hash, segs);
 	iph->id = htons(id);
 }
diff --git a/net/ipv6/ip6_output.c b/net/ipv6/ip6_output.c
index cb9df0eb4023..73372e8016b9 100644
--- a/net/ipv6/ip6_output.c
+++ b/net/ipv6/ip6_output.c
@@ -545,6 +545,7 @@ static void ipv6_select_ident(struct frag_hdr *fhdr, struct rt6_info *rt)
 	net_get_random_once(&ip6_idents_hashrnd, sizeof(ip6_idents_hashrnd));
 
 	hash = __ipv6_addr_jhash(&rt->rt6i_dst.addr, ip6_idents_hashrnd);
+	hash ^= __ipv6_addr_jhash(&rt->rt6i_src.addr, fhdr->nexthdr);
 	id = ip_idents_reserve(hash, 1);
 	fhdr->identification = htonl(id);
 }
@@ -639,10 +640,10 @@ int ip6_fragment(struct sk_buff *skb, int (*output)(struct sk_buff *))
 		skb_reset_network_header(skb);
 		memcpy(skb_network_header(skb), tmp_hdr, hlen);
 
-		ipv6_select_ident(fh, rt);
 		fh->nexthdr = nexthdr;
 		fh->reserved = 0;
 		fh->frag_off = htons(IP6_MF);
+		ipv6_select_ident(fh, rt);
 		frag_id = fh->identification;
 
 		first_len = skb_pagelen(skb);
@@ -1092,6 +1093,7 @@ static inline int ip6_ufo_append_data(struct sock *sk,
 	skb_shinfo(skb)->gso_size = (mtu - fragheaderlen -
 				     sizeof(struct frag_hdr)) & ~7;
 	skb_shinfo(skb)->gso_type = SKB_GSO_UDP;
+	fhdr.nexthdr = IPPROTO_UDP;
 	ipv6_select_ident(&fhdr, rt);
 	skb_shinfo(skb)->ip6_frag_id = fhdr.identification;
 

Re: [PATCH v2 net] ip: make IP identifiers less predictable

[Eric Dumazet]

On Fri, 2014-07-25 at 21:50 +0200, Eric Dumazet wrote:

> @@ -1092,6 +1093,7 @@ static inline int ip6_ufo_append_data(struct sock *sk,
>  	skb_shinfo(skb)->gso_size = (mtu - fragheaderlen -
>  				     sizeof(struct frag_hdr)) & ~7;
>  	skb_shinfo(skb)->gso_type = SKB_GSO_UDP;
> +	fhdr.nexthdr = IPPROTO_UDP;
>  	ipv6_select_ident(&fhdr, rt);
>  	skb_shinfo(skb)->ip6_frag_id = fhdr.identification;
>  
> 
> 

Arg, please ignore this version, this part is buggy.

I think I wont hash on ipv6 saddr, we might add this later.

Re: [PATCH v2 net] ip: make IP identifiers less predictable

[Eric Dumazet]

On Fri, 2014-07-25 at 21:54 +0200, Eric Dumazet wrote:
> On Fri, 2014-07-25 at 21:50 +0200, Eric Dumazet wrote:
> 
> > @@ -1092,6 +1093,7 @@ static inline int ip6_ufo_append_data(struct sock *sk,
> >  	skb_shinfo(skb)->gso_size = (mtu - fragheaderlen -
> >  				     sizeof(struct frag_hdr)) & ~7;
> >  	skb_shinfo(skb)->gso_type = SKB_GSO_UDP;
> > +	fhdr.nexthdr = IPPROTO_UDP;
> >  	ipv6_select_ident(&fhdr, rt);
> >  	skb_shinfo(skb)->ip6_frag_id = fhdr.identification;
> >  
> > 
> > 
> 
> Arg, please ignore this version, this part is buggy.
> 
> I think I wont hash on ipv6 saddr, we might add this later.
> 

Hmpff... false alarm. this is fine. I guess I need to sleep now ;)

Re: [PATCH v2 net] ip: make IP identifiers less predictable

[Hannes Frederic Sowa]

On Fr, 2014-07-25 at 21:50 +0200, Eric Dumazet wrote:
> diff --git a/net/ipv6/ip6_output.c b/net/ipv6/ip6_output.c
> index cb9df0eb4023..73372e8016b9 100644
> --- a/net/ipv6/ip6_output.c
> +++ b/net/ipv6/ip6_output.c
> @@ -545,6 +545,7 @@ static void ipv6_select_ident(struct frag_hdr *fhdr, struct rt6_info *rt)
>  	net_get_random_once(&ip6_idents_hashrnd, sizeof(ip6_idents_hashrnd));
>  
>  	hash = __ipv6_addr_jhash(&rt->rt6i_dst.addr, ip6_idents_hashrnd);
> +	hash ^= __ipv6_addr_jhash(&rt->rt6i_src.addr, fhdr->nexthdr);

I am not sure if we should hash fhdr->nexthdr for IPv6.

If you look at the reassembly engine, we compare protocol value for IPv4
but not for IPv6 (we even don't save it).

Even if we only transmit packets with UDP protocol type we might end up
having an extension header right after the fragmentation header of
another type later in the flow. We can end up using a different bucket
and thus reusing a fragmentation id wich has been seen before in this
flow possibly resulting in reassembly issues.

I don't see such a problem for IPv4.

Otherwise very nice patch, thanks,
Hannes

Re: [PATCH v2 net] ip: make IP identifiers less predictable

[Eric Dumazet]

On Sat, 2014-07-26 at 00:35 +0200, Hannes Frederic Sowa wrote:
> On Fr, 2014-07-25 at 21:50 +0200, Eric Dumazet wrote:
> > diff --git a/net/ipv6/ip6_output.c b/net/ipv6/ip6_output.c
> > index cb9df0eb4023..73372e8016b9 100644
> > --- a/net/ipv6/ip6_output.c
> > +++ b/net/ipv6/ip6_output.c
> > @@ -545,6 +545,7 @@ static void ipv6_select_ident(struct frag_hdr *fhdr, struct rt6_info *rt)
> >  	net_get_random_once(&ip6_idents_hashrnd, sizeof(ip6_idents_hashrnd));
> >  
> >  	hash = __ipv6_addr_jhash(&rt->rt6i_dst.addr, ip6_idents_hashrnd);
> > +	hash ^= __ipv6_addr_jhash(&rt->rt6i_src.addr, fhdr->nexthdr);
> 
> I am not sure if we should hash fhdr->nexthdr for IPv6.
> 

It seemed a reasonable idea to me ;)

> If you look at the reassembly engine, we compare protocol value for IPv4
> but not for IPv6 (we even don't save it).

That is linux, what about other reassembly engines ?

> 
> Even if we only transmit packets with UDP protocol type we might end up
> having an extension header right after the fragmentation header of
> another type later in the flow. We can end up using a different bucket
> and thus reusing a fragmentation id wich has been seen before in this
> flow possibly resulting in reassembly issues.

This seems to point a bug in our reassembly unit then ? It seems to rely
on senders being linux based or something.

Anyway, I'll send a v3 without netxdhr, ipv6 guys will make net-next
patches if needed.

Re: [PATCH v2 net] ip: make IP identifiers less predictable

[Hannes Frederic Sowa]

Hi,

On Sa, 2014-07-26 at 08:51 +0200, Eric Dumazet wrote:
> On Sat, 2014-07-26 at 00:35 +0200, Hannes Frederic Sowa wrote:
> > On Fr, 2014-07-25 at 21:50 +0200, Eric Dumazet wrote:
> > > diff --git a/net/ipv6/ip6_output.c b/net/ipv6/ip6_output.c
> > > index cb9df0eb4023..73372e8016b9 100644
> > > --- a/net/ipv6/ip6_output.c
> > > +++ b/net/ipv6/ip6_output.c
> > > @@ -545,6 +545,7 @@ static void ipv6_select_ident(struct frag_hdr *fhdr, struct rt6_info *rt)
> > >  	net_get_random_once(&ip6_idents_hashrnd, sizeof(ip6_idents_hashrnd));
> > >  
> > >  	hash = __ipv6_addr_jhash(&rt->rt6i_dst.addr, ip6_idents_hashrnd);
> > > +	hash ^= __ipv6_addr_jhash(&rt->rt6i_src.addr, fhdr->nexthdr);
> > 
> > I am not sure if we should hash fhdr->nexthdr for IPv6.
> > 
> 
> It seemed a reasonable idea to me ;)

To me, too. ;)

> > If you look at the reassembly engine, we compare protocol value for IPv4
> > but not for IPv6 (we even don't save it).
> 
> That is linux, what about other reassembly engines ?

The protocol id should be used in the reassembly process for ipv4, but
not for ipv6. Linux is completely rfc compliant in this regard (RFC 815
and others).

> > Even if we only transmit packets with UDP protocol type we might end up
> > having an extension header right after the fragmentation header of
> > another type later in the flow. We can end up using a different bucket
> > and thus reusing a fragmentation id wich has been seen before in this
> > flow possibly resulting in reassembly issues.
> 
> This seems to point a bug in our reassembly unit then ? It seems to rely
> on senders being linux based or something.

I don't think so.

The buckets aren't synchronized in any way. If we fragment an IPv6-UDP
stream towards a destination and some of those packets have extension
headers behind the fragment header we end up using a different bucket
which might contain an already used fragmentation id in this flow. The
reassembly engine does not match on protocol id, so it is possible that
we reassemble not matching fragments. This cannot happen with ipv4,
protocol id will always stay the same and should always be used during
reassembly.

Btw., does someone see a problem if we nuke out the ip ids before
attaching the headers to an icmp error message? We might also prevent
leaking IP ids to wrong hosts.

> Anyway, I'll send a v3 without netxdhr, ipv6 guys will make net-next
> patches if needed.

I'll have a look.

I played around with an idea of my own. These are just some snippets
from a user space implementation, comments inline:

Basically the idea is to use a symmetric block cipher with very small
block size to encrypt fragmentation ids.

We put a linear increasing counter (per host) into a symmetric block
cipher of a very small block size, for IPv6 (32 bit block size) I found
RC5 (warning: patent encumbered) to be reasonable albeit it normally
does not get used with 32 bit block sizes in real world. It may also be
possible to use it with 16 bit block sizes for IPv4. I can do so if
people like it.

The result is a perfect permutation to use for fragmentation ids (no
repeating values until the bucket counter wraps around) without the
possibility that someone can guess the next fragment id or infer
anything from it.

I only wonder if this has a too high impact performance wise.

I tried to clean up the code from the original RC5 paper and make it
undefined free and easy to integrate into the kernel.

static u32 frag_id_encrypt(u32 counter)
{
	int i;
	u16 A = counter >> 16;
	u16 B = counter & 0xffffU;

	A += S[0];
	B += S[1];

	for (i = 1; i <= ROUNDS; i++) {
		A = roll_l16(A ^ B, B);
		A += S[2 * i];
		B = roll_l16(B ^ A, A);
		B += S[2 * i + 1];
	}
	return (u32)A << 16 | B;
}

/* done once during boot up */
static void rc5_setup(void)
{
	int cnt;
	unsigned char key[KEY_BYTES] = {0};

	int  i, j;
	u16 A, B;

	u16 expanded_key[KEY_WORDS] = {0};

	srand(time(NULL));

	for (cnt = 0; cnt < KEY_BYTES; cnt++)
		key[cnt] = 0;

	for (cnt = KEY_BYTES - 1; cnt >= 0; cnt--)
		expanded_key[cnt/WORD_BYTES] =
			roll_l16(expanded_key[cnt/WORD_BYTES], 8) + key[cnt];

	S[0] = P16;
	for (cnt = 1; cnt < S_SIZE; cnt++)
		S[cnt] = S[cnt - 1] + Q16;

	i = 0;
	j = 0;
	A = 0;
	B = 0;

	for (cnt = 0; cnt < 3 * MAX(S_SIZE, KEY_WORDS); cnt++) {
		A = roll_l16(S[i] + (u16)(A + B), 3);
		S[i] = A;

		B = roll_l16(expanded_key[j] + (u16)(A + B), A + B);
		expanded_key[j] = B;

		i = (i+1) % S_SIZE;
		j = (j+1) % KEY_WORDS;
	}
}


Additional helpers so the code does compile (hmm, gcc does not see that
in can use roll instructions :( ):

static u16 roll_l16(u16 x, u16 roll)
{
	u16 l,r;
	roll &= WORD_BITS - 1;

	if (roll == 0)
		return x;

	assert(roll > 0);
	assert(roll < 16);

	l = x << roll;
	r = x >> (WORD_BITS - roll);
	return l | r;
}

static u16 roll_r16(u16 x, u16 roll)
{
	u16 l, r;
	roll &= WORD_BITS - 1;

	if (roll == 0)
		return x;

	assert(roll > 0);
	assert(roll < 16);

	l = x << (WORD_BITS - roll);
	r = x >> roll;
	return l | r;
}


<<< constants; should be at the top >>>
#define WORD_BYTES (sizeof(u16))
#define WORD_BITS (WORD_BYTES * CHAR_BIT)

#define ROUNDS 12
#define S_SIZE (2 * (ROUNDS + 1))

#define KEY_BYTES 16
#define KEY_WORDS (((KEY_BYTES-1)/WORD_BYTES) + 1)

static const u16 P16 = 0xb7e1;
static const u16 Q16 = 0x9e37;

/* constant after initialization __read_mostly */
static u16 S[S_SIZE] = {0};

<<< stuff end >>>

Bye,
Hannes
a

[PATCH v3 net] ip: make IP identifiers less predictable

[Eric Dumazet]

From: Eric Dumazet <edumazet@google.com>

In "Counting Packets Sent Between Arbitrary Internet Hosts", Jeffrey and
Jedidiah describe ways exploiting linux IP identifier generation to
infer whether two machines are exchanging packets.

With commit 73f156a6e8c1 ("inetpeer: get rid of ip_id_count"), we
changed IP id generation, but this does not really prevent this
side-channel technique.

This patch adds a random amount of perturbation so that IP identifiers
for a given destination [1] are no longer monotonically increasing after
an idle period.

Note that prandom_u32_max(1) returns 0, so if generator is used at most
once per jiffy, this patch inserts no hole in the ID suite and do not
increase collision probability.

This is jiffies based, so in the worst case (HZ=1000), the id can
rollover after ~65 seconds of idle time, which should be fine.

We also change the hash used in __ip_select_ident() to not only hash
on daddr, but also saddr and protocol, so that ICMP probes can not be
used to infer information for other protocols.

For IPv6, adds saddr into the hash as well, but not nexthdr.

If I ping the patched target, we can see ID are now hard to predict.

21:57:11.008086 IP (...)
    A > target: ICMP echo request, seq 1, length 64
21:57:11.010752 IP (... id 2081 ...)
    target > A: ICMP echo reply, seq 1, length 64

21:57:12.013133 IP (...)
    A > target: ICMP echo request, seq 2, length 64
21:57:12.015737 IP (... id 3039 ...)
    target > A: ICMP echo reply, seq 2, length 64

21:57:13.016580 IP (...)
    A > target: ICMP echo request, seq 3, length 64
21:57:13.019251 IP (... id 3437 ...)
    target > A: ICMP echo reply, seq 3, length 64

[1] TCP sessions uses a per flow ID generator not changed by this patch.

Signed-off-by: Eric Dumazet <edumazet@google.com>
Reported-by: Jeffrey Knockel <jeffk@cs.unm.edu>
Reported-by: Jedidiah R. Crandall <crandall@cs.unm.edu>
Cc: Willy Tarreau <w@1wt.eu>
Cc: Hannes Frederic Sowa <hannes@redhat.com>
---
v3: add saddr & protocol to hash used in __ip_select_ident()
    add saddr to hash used in ipv6_select_ident()

 include/net/ip.h      |   11 +----------
 net/ipv4/route.c      |   32 +++++++++++++++++++++++++++++---
 net/ipv6/ip6_output.c |    2 ++
 3 files changed, 32 insertions(+), 13 deletions(-)

diff --git a/include/net/ip.h b/include/net/ip.h
index 0e795df05ec9..7596eb22e1ce 100644
--- a/include/net/ip.h
+++ b/include/net/ip.h
@@ -309,16 +309,7 @@ static inline unsigned int ip_skb_dst_mtu(const struct sk_buff *skb)
 	}
 }
 
-#define IP_IDENTS_SZ 2048u
-extern atomic_t *ip_idents;
-
-static inline u32 ip_idents_reserve(u32 hash, int segs)
-{
-	atomic_t *id_ptr = ip_idents + hash % IP_IDENTS_SZ;
-
-	return atomic_add_return(segs, id_ptr) - segs;
-}
-
+u32 ip_idents_reserve(u32 hash, int segs);
 void __ip_select_ident(struct iphdr *iph, int segs);
 
 static inline void ip_select_ident_segs(struct sk_buff *skb, struct sock *sk, int segs)
diff --git a/net/ipv4/route.c b/net/ipv4/route.c
index 3162ea923ded..190199851c9a 100644
--- a/net/ipv4/route.c
+++ b/net/ipv4/route.c
@@ -457,8 +457,31 @@ static struct neighbour *ipv4_neigh_lookup(const struct dst_entry *dst,
 	return neigh_create(&arp_tbl, pkey, dev);
 }
 
-atomic_t *ip_idents __read_mostly;
-EXPORT_SYMBOL(ip_idents);
+#define IP_IDENTS_SZ 2048u
+struct ip_ident_bucket {
+	atomic_t	id;
+	u32		stamp32;
+};
+
+static struct ip_ident_bucket *ip_idents __read_mostly;
+
+/* In order to protect privacy, we add a perturbation to identifiers
+ * if one generator is seldom used. This makes hard for an attacker
+ * to infer how many packets were sent between two points in time.
+ */
+u32 ip_idents_reserve(u32 hash, int segs)
+{
+	struct ip_ident_bucket *bucket = ip_idents + hash % IP_IDENTS_SZ;
+	u32 old = ACCESS_ONCE(bucket->stamp32);
+	u32 now = (u32)jiffies;
+	u32 delta = 0;
+
+	if (old != now && cmpxchg(&bucket->stamp32, old, now) == old)
+		delta = prandom_u32_max(now - old);
+
+	return atomic_add_return(segs + delta, &bucket->id) - segs;
+}
+EXPORT_SYMBOL(ip_idents_reserve);
 
 void __ip_select_ident(struct iphdr *iph, int segs)
 {
@@ -467,7 +490,10 @@ void __ip_select_ident(struct iphdr *iph, int segs)
 
 	net_get_random_once(&ip_idents_hashrnd, sizeof(ip_idents_hashrnd));
 
-	hash = jhash_1word((__force u32)iph->daddr, ip_idents_hashrnd);
+	hash = jhash_3words((__force u32)iph->daddr,
+			    (__force u32)iph->saddr,
+			    iph->protocol,
+			    ip_idents_hashrnd);
 	id = ip_idents_reserve(hash, segs);
 	iph->id = htons(id);
 }
diff --git a/net/ipv6/ip6_output.c b/net/ipv6/ip6_output.c
index cb9df0eb4023..45702b8cd141 100644
--- a/net/ipv6/ip6_output.c
+++ b/net/ipv6/ip6_output.c
@@ -545,6 +545,8 @@ static void ipv6_select_ident(struct frag_hdr *fhdr, struct rt6_info *rt)
 	net_get_random_once(&ip6_idents_hashrnd, sizeof(ip6_idents_hashrnd));
 
 	hash = __ipv6_addr_jhash(&rt->rt6i_dst.addr, ip6_idents_hashrnd);
+	hash = __ipv6_addr_jhash(&rt->rt6i_src.addr, hash);
+
 	id = ip_idents_reserve(hash, 1);
 	fhdr->identification = htonl(id);
 }

Re: [PATCH v3 net] ip: make IP identifiers less predictable

[David Miller]

From: Eric Dumazet <eric.dumazet@gmail.com>
Date: Sat, 26 Jul 2014 08:58:10 +0200

> From: Eric Dumazet <edumazet@google.com>
> 
> In "Counting Packets Sent Between Arbitrary Internet Hosts", Jeffrey and
> Jedidiah describe ways exploiting linux IP identifier generation to
> infer whether two machines are exchanging packets.
> 
> With commit 73f156a6e8c1 ("inetpeer: get rid of ip_id_count"), we
> changed IP id generation, but this does not really prevent this
> side-channel technique.
> 
> This patch adds a random amount of perturbation so that IP identifiers
> for a given destination [1] are no longer monotonically increasing after
> an idle period.
> 
> Note that prandom_u32_max(1) returns 0, so if generator is used at most
> once per jiffy, this patch inserts no hole in the ID suite and do not
> increase collision probability.
> 
> This is jiffies based, so in the worst case (HZ=1000), the id can
> rollover after ~65 seconds of idle time, which should be fine.
> 
> We also change the hash used in __ip_select_ident() to not only hash
> on daddr, but also saddr and protocol, so that ICMP probes can not be
> used to infer information for other protocols.
> 
> For IPv6, adds saddr into the hash as well, but not nexthdr.
> 
> If I ping the patched target, we can see ID are now hard to predict.
 ...
> [1] TCP sessions uses a per flow ID generator not changed by this patch.
> 
> Signed-off-by: Eric Dumazet <edumazet@google.com>
> Reported-by: Jeffrey Knockel <jeffk@cs.unm.edu>
> Reported-by: Jedidiah R. Crandall <crandall@cs.unm.edu>

Applied and queued up for -stable, thanks everyone.