Subject: some comments/suggestions on draft-gont-6man-non-stable-iids-02

From: Dave Plonka <[email-masked]>
Date: Mon, 19 Mar 2018 14:48:37 +0000

Hi Fernando and 6man folks,

In my reading of "Recommendation on Temporary IPv6 Interface
Identifiers" https://tools.ietf.org/html/draft-gont-6man-non-stable-iids-02
, I have these comments/suggestions:

> 5.  Requirements for Temporary IPv6 Addresses
>
>    The requirements for temporary IPv6 addresses are as follows:
>
>    1.  Temporary addresses MUST have a limited lifetime, which should be
>        different for different addresses.  The lifetime of an address
>        essentially limits the extent to which network activity
>        correlation can be performed based on such address.

Stating that a temporary adddresses' lifetime must be "different for
different addresses" is ambiguous (to me). Can you clarify?

Does it mean 2 or more temporary addresses chosen by the same host
or across all hosts?

Does it mean different addresses should have different durations,
e.g., 1 hour for one address and 2 hours for another?

Or does it mean that their lifetime, during which the address
is assigned to an interface, should not begin or end at (nearly)
the same moments in time?

>    3.  The resulting Interface Identifiers MUST be different when
>        addresses are configured for different prefixes.  That is, if
>        different autoconfiguration prefixes are used to configure
>        addresses for the same network interface card, the resulting
>        Interface Identifiers must be (statistically) different.  This
>        means that, given two addresses that employ different prefixes,
>        it must be difficult for an outside entity to tell whether the
>        addresses correspond to the same network interface or even
>        whether they have been generated by the same host.

This is, then, reiterated later in the draft:

> The IIDs of addresses configured for different autoconfiguration
> prefixes must be different, such that traffic for those addresses
> cannot be correlated.

I believe it's problematic to state that a host's temporary
Interfaces Identifiers MUST be different (either across time, e.g.,
on a given interface nor across address space, e.g., on interfaces
with differing prefixes) since it is, e.g., possible, just extremely
improbable, for even the best random number generator to produce
the same result.

I suggest we say that it MUST be extremely unlikely, i.e., of
extremely low probability, that they be the same (either across
time or across address space).

If we don't change this, and maintain that they MUST be different,
it implies that a host, when [re]generating a candidate temporary
Interface Identifier, MUST check that it differs from the other
Interface Identifiers that it used previously or that it uses
in other prefixes. This seems an onerous requirement of the host
implementation and, perhaps, impossible in some implementations,
without persistent storage of Interface Identifiers.

This requirement would also conflict with these statement later in
the draft:

>    6.  The resulting Interface Identifiers MUST be semantically opaque
>        [RFC7136] and MUST NOT follow any specific patterns.
> [...]
> Any semantics or patterns in an IID might be leveraged by an attacker
> to e.g.  reduce the search space when performing address-scanning
> attacks, infer the identity of the node, etc.

It would conflict because testing IID values against previous values
(in time) or other values used (in space) to determine that they
differ and then *rejecting* some values imposes a subtle pattern
on the resulting IID.

>    5.  It must be difficult for an outside entity to predict the
>        Interface Identifiers that will be generated by the algorithm,
>        even with knowledge of the Interface Identifiers generated for
>        configuring other addresses.

Rather than saying "must be difficult" to predict the Interface
Identifiers, we should prescribe something more specific to
implementers. Also this is the only point in the draft where it
uses the word "algorithm," i.e., it is implying that there is
an algorithm by which the host is choosing an Interface Idenfier.

The method by which a host chooses its Temporary IPv6 Interface
Identifiers should result in those Interfaces Identifiers being
most unlikely to be predicted even by an outside entity with
knowledge of the host's method, e.g., pseudo-random number generation
algorithm, or the host's prior or other Interface Identifiers.

Does that make sense?

Thanks,
Dave

-- 
[email-masked]  http://www.cs.wisc.edu/~plonka/

---

From: Fernando Gont <[email-masked]>
Date: Mon, 19 Mar 2018 15:06:14 +0000

Hello, Dave,

Thanks for your feedback! Comments inline...

> different addresses" is ambiguous (to me). Can you clarify?

The idea is that an attacker cannot deterministically determine when an
address is going to change.

Otherwise, he could correlate two distinct address when one disappears
and a new one (to replace the existing one) appears.

> Does it mean 2 or more temporary addresses chosen by the same host

What we meant is "Don't use a hardcoded timer value", such that an
attacker cannot now exactly/deterministically when an address will be
phased out an a new one generated.

> e.g., 1 hour for one address and 2 hours for another?>

Aren't the two closely related?

> improbable, for even the best random number generator to produce

How about "statistically different", instead?

> implementers. 

This doc is analogous to RFC8064. Specifies the requirements, but you
are free to comply with them in any way you please. rfc4941bis proposes
to way to comply with such requirements.

> Also this is the only point in the draft where it

Will double-check and reference rfc4941bis where necessary. Would that work?

> algorithm, or the host's prior or other Interface Identifiers.

Let me try to commit your text into the doc. Will come back to you on
this one.

Thanks so much for the useful feedback!

Thanks,
-- 
Fernando Gont
SI6 Networks
e-mail: [email-masked]
PGP Fingerprint: 6666 31C6 D484 63B2 8FB1 E3C4 AE25 0D55 1D4E 7492

---

From: Dave Plonka <[email-masked]>
Date: Mon, 19 Mar 2018 15:48:17 +0000

Hi Fernando, Lorenzo, and 6man folks,

In the conversation in the WG meeting just now, we can probably agree
in spirit with Lorenzo's suggestion to say that the "Interface
Identifier" (or the value on which it is mostly based) should be
random, however there are a few complications we should handle:

1) As you know, only 63 of the 64 bits in an temporary IID are random,
b/c one is fixed, the "u" bit. This makes the whole IID, itself, less
than random.

2) I believe it is impossible to determine whether or not a short
string (of characters or bits) is random.

For instance, the NIST test for randomness (e.g., ala Shannon Entropy)
requires thousands of bits input to produce a result.

Perhaps we could say "pseudorandom," instead, but the definition of
that is (from m-w.com):

   q(: being or involving entities (such as numbers) that are selected
by a definite computational process but that satisfy one or more
standard tests for statistical randomness)

So, what standard test could we propose? That seems unnecessarily hard
for our work here.

I know of only one tool that attempts to measure something like
randomness in short strings and it does this by calculating entropy or
information content; it is called "flott."

It's an interesting tool, but, unfortunately, does not have a strong
theoretical basis in the literature, so it is an open problem to
determine what it is really measuring (despite the author(s)
suspecting it is related to Shannon Entropy.)

This is why I propose words along these lines:

   A Temporary Interface Identifier MUST be unpredictable by an
outside entity even having knowledge of the host's method of
generating the Interface Identifier, e.g., pseudo-random number
generation algorithm, or knowledge of the host's prior or other
Interface Identifiers.

This text allows high-quality pseudorandom number generators (which I
think is what Lorenzo and most of us expect) but also leaves open any
method that is unpredictable. We care that its unpredictable (to an
outside entity), not necessarily that it tests as random by any
specific standard test, although one characteristic likely coincides
with the other.

Dave

---

From: Mark Smith <[email-masked]>
Date: Tue, 20 Mar 2018 06:24:45 +1100

> b/c one is fixed, the "u" bit. This makes the whole IID, itself, less

The meaning of the U bit was dropped in RFC7136.

> --------------------------------------------------------------------
> IETF IPv6 working group mailing list
> [email-masked]
> Administrative Requests: https://www.ietf.org/mailman/listinfo/ipv6
> --------------------------------------------------------------------

---

From: Fernando Gont <[email-masked]>
Date: Mon, 19 Mar 2018 20:17:46 +0000

Hello, Dave,

Thanks for the feedback!

> b/c one is fixed, the "u" bit. This makes the whole IID, itself, less

See RFC7136.

> So, what standard test could we propose? That seems unnecessarily hard

What we say is that it must be unpredictable from the outside. That's
the same sort of terminology that we have employed in e.g. RFC7217 and
RFC7739.

> generation algorithm, or knowledge of the host's prior or other

This would be in replacement of this:

or what?

> specific standard test, although one characteristic likely coincides

Just curious: what's the text of the document that gives you the idea
that we expect the IID to comply with some sort of randommens checks?

Thanks!

Cheers,

---

From: Brian E Carpenter <[email-masked]>
Date: Tue, 20 Mar 2018 11:27:02 +1300

> On 03/19/2018 03:48 PM, Dave Plonka wrote:
...
>> generation algorithm, or knowledge of the host's prior or other

I know theoreticians who would pick holes even in that formulation.
If I know the weaknesses in your PRNG, and how it picks its seed,
I might be able to predict its output with a finite probability of
success. But that seems like an acceptable risk.

>        configuring other addresses.

It seems to cover the same ground.

    Brian

---

From: Dave Plonka <[email-masked]>
Date: Mon, 19 Mar 2018 22:58:49 +0000

Hi Brian and Fernando,

> success. But that seems like an acceptable risk.

I agree. I took the "outside entity" to mean someone that didn't know
the seed, but might know the algorithm that operates on the seed.

I mentioned PRNG as only one example ("e.g.") method of what an
implementer might do.
I'd actually prefer the draft not mention randomness, but rather that
an IID be unpredictable.

> It seems to cover the same ground.

They are close, but we could strengthen the implementer's goal from
"difficult [to predict]" to "unpredictable."

This is inline with Brian's comment that a poor PRNG's output may be
still remain difficult to predict, yet have a high probability of
success.

I certainly don't disagree with what the draft is trying to say, I
just think it can be stated better by:
(a) not mentioning IIDs differing from prior values or (b) that they
be random. In (a), requiring it to differ compromises the randomness
because it makes them, in small part, a function of the prior value.
In (b), there is no way to know that an IID is random, only plausibly
so (by testing it as a member of a set as we say here:
https://arxiv.org/pdf/1707.03900.pdf Section 2.1 "Identifying
Plausible Randomness," for instance.

Perhaps a goal of being "unpredictable" and "plausibly random" would
be a good solution.

What do you think?

Dave

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 21 Mar 2018 13:13:30 +1300

below...
> Perhaps a goal of being "unpredictable" and "plausibly random" would

If you mean me personally, saying should or must be unpredicatble is
necessary and sufficient. If we use the words 'random' or 'pseudorandom'
you tend to wake up the mathematicians to no purpose.

   Brian

---

From: Dave Plonka <[email-masked]>
Date: Fri, 23 Mar 2018 14:27:52 +0000

I totally agree.