From: Jeffrey Knockel <jeffk@cs•unm.edu>
To: Linus Torvalds <torvalds@linux-foundation•org>,
Eric Dumazet <eric.dumazet@gmail•com>
Cc: David Miller <davem@davemloft•net>,
netdev <netdev@vger•kernel.org>,
"Jedidiah R. Crandall" <crandall@cs•unm.edu>,
Willy Tarreau <w@1wt•eu>,
"security@kernel•org" <security@kernel•org>
Subject: Re: [PATCH net] ip: make IP identifiers less predictable
Date: Fri, 25 Jul 2014 09:55:58 -0600 [thread overview]
Message-ID: <53D27E0E.40102@cs.unm.edu> (raw)
In-Reply-To: <CA+55aFyCDNq3E+bZ3aPfS33w8mA_86J+cNWR5V6fdogNihSh2Q@mail.gmail.com>
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
next prev parent reply other threads:[~2014-07-25 16:04 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-07-24 8:07 [PATCH net] ip: make IP identifiers less predictable Eric Dumazet
2014-07-24 18:21 ` Linus Torvalds
2014-07-25 15:55 ` Jeffrey Knockel [this message]
2014-07-25 18:09 ` Eric Dumazet
2014-07-25 18:35 ` Linus Torvalds
2014-07-25 18:38 ` Eric Dumazet
2014-07-25 19:03 ` Willy Tarreau
2014-07-25 23:05 ` Hannes Frederic Sowa
2014-07-25 20:28 ` Jeffrey Knockel
2014-07-25 19:50 ` [PATCH v2 " Eric Dumazet
2014-07-25 19:54 ` Eric Dumazet
2014-07-25 19:57 ` Eric Dumazet
2014-07-25 22:35 ` Hannes Frederic Sowa
2014-07-26 6:51 ` Eric Dumazet
2014-07-26 12:21 ` Hannes Frederic Sowa
2014-07-26 6:58 ` [PATCH v3 " Eric Dumazet
2014-07-29 1:47 ` David Miller
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=53D27E0E.40102@cs.unm.edu \
--to=jeffk@cs$(echo .)unm.edu \
--cc=crandall@cs$(echo .)unm.edu \
--cc=davem@davemloft$(echo .)net \
--cc=eric.dumazet@gmail$(echo .)com \
--cc=netdev@vger$(echo .)kernel.org \
--cc=security@kernel$(echo .)org \
--cc=torvalds@linux-foundation$(echo .)org \
--cc=w@1wt$(echo .)eu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox