Subject: Randomness and uniqueness

From: Alexandru Petrescu <[email-masked]>
Date: 05 Feb 2002 14:14:09 +0100

Hi, there's currently a stream of proposals that put random bits on
the Interface ID of an IPv6 address.  A background assumption is that
the length of the Interface ID is 64 bits.  Another assumption is that
since those ID's are generated from random sources, then their
uniqueness is guaranteed for practical purposes.

May I point out the following:

-mathematical uniqueness is not guaranteed, there's already an
 acknowledged collision probability.
-to this probability one should add "administrative probability" where
 same prefixes are accidentally assigned to two entities.
-add implementation error probabilities, where a widespread
 implementation uses a weak algorithm to generate that random numbers,
 for example use as input time of day or the birth date, or short
 passphrases, etc.
-add the p in prf.

The last three factors are very hard to quantify, and as such the
overall probability of collision events also seems to me very hard to
quantify.

Just a thought, born out of contemplating randomness.  What do you
think?

Alex

--------------------------------------------------------------------
IETF IPng Working Group Mailing List
IPng Home Page:                      http://playground.sun.com/ipng
FTP archive:                      ftp://playground.sun.com/pub/ipng
Direct all administrative requests to [email-masked]
--------------------------------------------------------------------

---

From: "Tony Hain" <[email-masked]>
Date: Tue, 5 Feb 2002 10:01:06 -0800

As you point out uniqueness is not guaranteed, even for administrative
assignments. That is why RFC 2462 specifically states:
   The Duplicate Address Detection algorithm is
   performed on all addresses, independent of whether
   they are obtained via stateless or stateful
   autoconfiguration.

In a quick scan of 3041 I didn't see a reference to that, but it was a
fundemental assumption. If 3041 is updated it would probably help to
have a clear pointer back to 2462.

Tony

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Alexandru Petrescu
> Sent: Tuesday, February 05, 2002 5:14 AM
> To: [email-masked]
> Subject: Randomness and uniqueness
>
>

---

From: Alexandru Petrescu <[email-masked]>
Date: 05 Feb 2002 19:31:07 +0100

> have a clear pointer back to 2462.

Sure, thanks for pointing this.  I wasn't referring to rfc3041
though.

My remark was rather generic.

For example, let's say I design DHCP2 where the 65th bit of all
addresses has particular meaning to DHCP2 servers: helps in better
authenticating clients.  Also, the 66th bit up to 128th contain a
random number that is used to securely communicate between DHCP2
servers and relays.

Of course, this would have huge advantages for the DHCP2 protocol,
since it allows combining trust properties into addressing and routing
properties.  But would this work with other things?

Thanks for any feedback,

Alex

PS: with respect to uniqueness there's a draft on random Interface
    ID's without DAD: draft-soto-mobileip-random-iids-00.txt
PPS: with respect to security there's ongoing discussion on Mobile IP,
     around a novel method to generate addresses (Computationally
     Generated Addresses).

---

From: "Tony Hain" <[email-masked]>
Date: Tue, 5 Feb 2002 11:19:31 -0800

A single bit for authentication seems like weak authentication... ;)

At any rate, you can't use truly random values in addressing and expect
to establish a trust based on that. At best you could have a
pseudo-random table that both ends are working from, but either that
table is well-known, or establishing it and maintaining synchronization
will be an operational nightmare.

As for using an address without performing DAD, this is a *bad idea* in
general and fast-handoff is no excuse to avoid verifying that someone
else is not already using an address on the link (assigned or random).
If mip is that far off in the weeds we may need an AD to ask them to
revisit their charter.

Tony

> From: [email-masked] [mailto:[email-masked]]
> Sent: Tuesday, February 05, 2002 10:31 AM
> To: Tony Hain
> Cc: [email-masked]
> Subject: Re: Randomness and uniqueness
>
>

---

From: Vijay Devarapalli <[email-masked]>
Date: Tue, 05 Feb 2002 11:31:16 -0800

> If mip is that far off in the weeds we may need an AD to ask them to

two comments. 

These are individual proposals in the Mobile IP WG. and these
people are being "encouraged" to take them up in the IPv6 WG
rather than the Mobile IP WG.

and Fast Handoffs for Mobile IPv6 does not say "dont do DAD".

Vijay

---

From: "Tony Hain" <[email-masked]>
Date: Tue, 5 Feb 2002 11:51:07 -0800

> rather than the Mobile IP WG.

I understand the role of cross WG sanity checking, but usually that is
only done when the origin WG believes in the work but want verification,
or that the work really belongs in the other group.

> and Fast Handoffs for Mobile IPv6 does not say "dont do DAD".

The document referenced specifically tries to justify avoiding DAD
because it takes too long for fast handoffs.

Tony

---

From: Alexandru Petrescu <[email-masked]>
Date: 05 Feb 2002 20:59:44 +0100

> or that the work really belongs in the other group.

Hi, the remark was born out mainly from my personal oppinions and
views on certain issues.  I do not intend to boil any ocean.  I'm
trying to find out some guidance on how one could put bits into
addresses.

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: 05 Feb 2002 20:48:32 +0100

> If mip is that far off in the weeds we may need an AD to ask them to

Sorry, my remark was generally about how to put bits in addresses.

The DAD thing is another topic, not discussed in Mobile IP, not a WG
item.  But your remark is valuable advice, helps for better
understanding where things go.

Alex

---

From: "Tony Hain" <[email-masked]>
Date: Tue, 5 Feb 2002 12:09:19 -0800

> trying to find out some guidance on how one could put bits into

Even though your purpose is different, a good place to start would be
the discussion in RFC 3041 since the technical details will be similar.

Tony

---

From: Peter Bieringer <[email-masked]>
Date: Tue, 05 Feb 2002 22:40:55 +0100

--On Tuesday, February 05, 2002 10:01:06 AM -0800 Tony Hain
<[email-masked]> wrote:

> As you point out uniqueness is not guaranteed, even for
> administrative assignments. That is why RFC 2462 specifically
> states:
> In a quick scan of 3041 I didn't see a reference to that, but it
> was a fundemental assumption. If 3041 is updated it would probably
> help to have a clear pointer back to 2462.

During developing my tool "ipv6calc" last summer and implementing a
RFC 3041 simulation (for demonstrations) I already detect such
problem   , too.

I've noticed both authors and got response from both that they will
update the draft based on RFC 3041 

http://www.ietf.org/internet-drafts/draft-ietf-ipngwg-temp-addresses-
v2-00.txt

See 3.2.1 (4), they already add a note now.

        Peter

---

From: Francis Dupont <[email-masked]>
Date: Thu, 07 Feb 2002 22:41:00 +0100

In your previous mail you wrote:

   Hi, there's currently a stream of proposals that put random bits on
   the Interface ID of an IPv6 address.  A background assumption is that
   the length of the Interface ID is 64 bits.

=> this is a strong assumption and all past threads about it concluded
this assumption should *not* be done.

   Another assumption is that
   since those ID's are generated from random sources, then their
   uniqueness is guaranteed for practical purposes.
   
=> if this argument is used in order to avoid (or to perform after) DAD
we have to define "practical". I agree with the probability argument
(i.e. modulo implementation errors, collisions should be almost impossible)
but I'd not like to get this in a life support system.

=> this is why DAD should be always performed. According to my
"please don't play Russion roulette with my network" argument,
the control over to perform or not DAD should be in the hands of
the network manager (not in the hands of the node manager because
an address collision usually does *two* victims).

=> this is like link-layer address collision (for instance two Ethernet
boards with the same MAC address in ROMs), the damage is done
independently/before DAD, i.e. or we consider it can't happen,
or we consider it is the business of someone else...

=> this is a real concern (even there is a RFC about randomness).

   -add the p in prf.
   
=> ???

   
=> if it is not too late (I'm afraid it is), replace DAD by Duplicate
Interface ID Detection. And, of course, perform DAD each time DAD can
be useful (I know only one good exception: PPP, because PPP manages
itself IIDs and guarantees against collisions).

Regards

[email-masked]

PS: I don't believe in RFC 3041: it doesn't provide privacy when
the first 64 bits can be used to trace you. But it does provide
near 2^63 different IIDs to the bad guy for source address spoofing!
If you don't want to be traced by your IID, use ::1, ::2, ... as your
IID and, of course, perform DAD. RFC 3041 is at the same level as
the associated privacy concern...
--------------------------------------------------------------------
IETF IPng Working Group Mailing List
IPng Home Page:                      http://playground.sun.com/ipng
FTP archive:                      ftp://playground.sun.com/pub/ipng
Direct all administrative requests to [email-masked]
--------------------------------------------------------------------

---

From: Francis Dupont <[email-masked]>
Date: Thu, 07 Feb 2002 22:47:52 +0100

=> this draft is about the probability argument.

=> there is no reason to avoid DAD on CGAs: CGAs and RFC 3041 are
not different.

Regards

---

From: Francis Dupont <[email-masked]>
Date: Thu, 07 Feb 2002 22:58:07 +0100

general

=> I agree, at least using an address without performing DAD before
should be explicitely allowed by the network manager (this can be
easily added in fast-handoff).

   and fast-handoff is no excuse

=> I am afraid that fast-handoff is an excuse for mainly tendentious
things... (:-)

   to avoid verifying that someone
   else is not already using an address on the link (assigned or random).
   If mip is that far off in the weeds we may need an AD to ask them to
   revisit their charter.
   
=> hum, what about this (from MIPv6 I-D 15):

   After forming a new care-of address, a mobile node MAY perform
   Duplicate Address Detection [27] on that new address to confirm its
   uniqueness.  However, doing so represents a tradeoff between safety
   (ensuring that the new address is not used if it is a duplicate
   address) and overhead (performing Duplicate Address Detection
   requires the sending of one or more additional packets over what
   may be, for example, a slow wireless link through which the mobile
   node is connected).  Performing Duplicate Address Detection also in
   general would cause a delay before the mobile node could use the
   new care-of address, possibly causing the mobile node to be unable
   to continue communication with correspondent nodes for some period
   of time.  For these reasons, a mobile node, after forming a new
   care-of address, MAY begin using the new care-of address without
   performing Duplicate Address Detection.  Furthermore, the mobile node
   MAY continue using the address without performing Duplicate Address
   Detection, although it SHOULD in most cases (e.g., unless network
   bandwidth or battery consumption for communication is of primary
   concern) begin Duplicate Address Detection asynchronously when it
   begins use of the address, allowing the Duplicate Address Detection
   procedure to complete in parallel with normal communication using the
   address.

Regards

---

From: Francis Dupont <[email-masked]>
Date: Thu, 07 Feb 2002 22:43:35 +0100

=> I agree, the only valid exception is PPP.

   fundemental assumption.

=> agree!

---

From: Alexandru Petrescu <[email-masked]>
Date: 08 Feb 2002 10:09:08 +0100

Hi Francis, thanks for following up on this.

> or we consider it is the business of someone else...

Exactly.  What I was trying to stress is that we're already subject to
"collisions" due to a human factor: administrative errors.  I know
this is known, just felt like I wanted to see it here.

>    -add the p in prf.

Sorry, not trying to be mysterious. Prf is short for pseudo-random
function generators.  The "pseudo" is sometimes "apparent".  For the
fun, two lines of a famous quote by von Neumann: "Any one who
considers arithmetical methods of producing random digits is, of
course, in a state of sin".  Just for the fun of it :-)

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: 08 Feb 2002 11:39:59 +0100

Francis Dupont <[email-masked]> writes:
> => I believe you've mixed in a confusing way the uniqueness of an
> address/IID on a link (guaranteed by DAD) and the uniqueness of
> a CGA from the security point of view. They are very different
> questions.

Ok, I didn't want to generate any confusion.  If that was the case,
I'm retiring my argumentation, sorry.

Alex

---

From: Francis Dupont <[email-masked]>
Date: Fri, 08 Feb 2002 11:21:57 +0100

> => there is no reason to avoid DAD on CGAs: CGAs and RFC 3041 are
   
   First, I find CGA (Computationally Generated Addresses) mechanisms to
   have valuable IP security properties and are probably exploitable in
   some contexts.
   
=> I agree, CGA have only two drawbacks: IPR (grrr!) and they are not
for free (i.e. they involve some crypto operations).

   Is it reasonable to ask two distanced MN's to verify they haven't
   generated same CGA Interface ID?
   
=> DAD is a link operation.

   For clarification, I was suggesting that since IPv6 as is doesn't rely
   on mathematical uniqueness of random bits in Interface ID's, but
   enforces it with DAD, then it would seem natural that CGA mechanisms
   don't rely on that uniqueness either and should test it somehow.  If I
   understand CGA mechanisms correctly, there's a low probability (ok,
   extremely low) for CGA'ed Interface ID's to collide.  Those Interface
   ID's are not on the same subnet, different prefixes, DAD won't find
   collisions.  The security verification of those CGA'ed Interface ID's
   happens at the Correspondent Node, against attacker MN's.
   
=> I believe you've mixed in a confusing way the uniqueness of an
address/IID on a link (guaranteed by DAD) and the uniqueness of
a CGA from the security point of view. They are very different questions.

Regards

---

From: Alexandru Petrescu <[email-masked]>
Date: 08 Feb 2002 11:01:48 +0100

Again, I'm no CGA expert and as Jari and Vijay said, nothing in CGA'ed
addresses stops them from being DAD'ed on the subnet.

Alex

---

From: Francis Dupont <[email-masked]>
Date: Fri, 08 Feb 2002 11:11:01 +0100

Exactly.  What I was trying to stress is that we're already subject to
   "collisions" due to a human factor: administrative errors.

=> administrators are *responsible* of administrative errors: this makes
the difference.

   
=> I agree that an algorithm cannot give a random number by definition
of what are an algorithme and a random number. But some hardware devices
(available on i810 chipset serie for instance) give good quality random
numbers... (obviously an overkilling in this case :-).

Regards

---

From: "marcelo bagnulo" <[email-masked]>
Date: Fri, 8 Feb 2002 12:24:17 +0100

-----Mensaje original-----
De: [email-masked]
[mailto:[email-masked]]En nombre de Francis Dupont
Enviado el: jueves, 07 de febrero de 2002 22:41
Para: Alexandru Petrescu
CC: [email-masked]
Asunto: Re: Randomness and uniqueness

> but I'd not like to get this in a life support system.

if you do agree with the probablity argument
but you do not like to implement it, because you do not like it, what are
the reasons for this dislike?

regards, m

---

From: Francis Dupont <[email-masked]>
Date: Fri, 08 Feb 2002 19:24:39 +0100

In your previous mail you wrote:

   > => the probability argument gives no guarantee.
   
   Nothing can give you full guarantees

=> globally unique IIDs give a full guarantee as I explained
in a previous mail (with what is this guarantee).

   There is no option that always work,
   all the options work fine with a certain probability, The real question is
   if the probability that it fails is low enough.

=> no, the real question is who has to cleanup the mess when it fails.
I prefer this guy has the control over the acceptable options too.

   And what does low enough
   means basically depends on the probablility of failure of the others
   elements related. So the question to be answered is if the probability of
   colision with random generated address identiers is low enough compared with
   the probability of failure of the other devices and protocols in the net.
   This is what we are trying to quantify.

=> there always is a difference between zero and not zero.

   It is also important to consider the cost, i.e. most of the times you can
   improve a solution (meaning that you can get a lower probability of failure)
   but this usually implies aditional costs, the question is if this is worthy.
   
=> worthy for who? If you takes the benefits and I have to take the problem
in the case that should never happen but has just happened, my answer is
a clear *no*.

   I mean whether you like it or not you are playing russian roulette :-),
   DAD can fail as well as all the other elements in your network
   
=> DAD is not perfect but my life is better with DAD than it would be
without DAD. And I'd like to decide what is good for my network.
This is the point I don't like at all in the MIPv6 I-D proposal,
the MN user is not the person who may decide if he can avoid or defer DAD.

Regards

---

From: "marcelo bagnulo" <[email-masked]>
Date: Fri, 8 Feb 2002 19:04:50 +0100

> De: [email-masked]
> [mailto:[email-masked]]
> Enviado el: viernes, 08 de febrero de 2002 18:29
> Para: marcelo bagnulo
> CC: Alexandru Petrescu; [email-masked]
>    but you do not like to implement it, because you do not like it,
>    what are the reasons for this dislike?
>

Nothing can give you full guarantees There is no option that always work,
if the probability that it fails is low enough. And what does low enough

I mean whether you like it or not you are playing russian roulette :-),  DAD
can fail as well as all the other elements in your network

regards, m

---

From: "marcelo bagnulo" <[email-masked]>
Date: Fri, 8 Feb 2002 20:03:23 +0100

> in a previous mail (with what is this guarantee).

globally unique IIDs can give you full guarantees, right, but the
implementation of globally unique IIDs can not. In any case, I do agree with
you that globally unique IIDs is a good solution but today it is not
available and it don´t seems to be in a short time
(i would like to see one)

> I prefer this guy has the control over the acceptable options too.

This is also an important aspect but if the probability of that mess is very
low and the "solution" to avoid the mess is expensive (for example for
handovers), what is better?

> => there always is a difference between zero and not zero.

zero is not real

> in the case that should never happen but has just happened, my answer is

Every mobile user gets the benefits avoiding the time needed for DAD, and a
very small percentage of all users pay the price. This is the tradoff that
we would like to quantify
> the MN user is not the person who may decide if he can avoid or defer DAD.
Life is not better with DAD for mobile users

Regards, m

---

From: Francis Dupont <[email-masked]>
Date: Fri, 08 Feb 2002 18:29:12 +0100

---

From: Francis Dupont <[email-masked]>
Date: Sat, 09 Feb 2002 15:27:29 +0100

globally unique IIDs can give you full guarantees, right, but the
   implementation of globally unique IIDs can not.

=> if I understand your argument, your concern is for instance we can't
guarantee uniqueness of MAC addresses. I agree but MAC address collisions
make impressive damage independently (in fact before) of IID stuff so
I consider uniqueness is guaranteed by my sledgehammer (to shutdown
definitively the device) and my legal department (for the NIC seller).

   In any case, I do agree with
   you that globally unique IIDs is a good solution but today it is not
   available and it don´t seems to be in a short time

=> they are available...
   
   > I prefer this guy has the control over the acceptable options too.
   
   This is also an important aspect but if the probability of that
   mess is very low

=> very low but not zero.

   and the "solution" to avoid the mess is expensive (for example for
   handovers), what is better?
   
=> if I am in the charge of the network and the price of the solution
is not for me I may answer I'd like to get the solution.
I believe we have exchanged enough messages to see our opinions are
not different about the probability argument validity but are
different about who should decide to apply it of not. For me
the network manager should get the control of this choice, not
the mobile user.

Regards

---

From: Alexandru Petrescu <[email-masked]>
Date: 11 Feb 2002 10:06:45 +0100

"marcelo bagnulo" <[email-masked]> writes:
> if the probability that it fails is low enough. And what does low
> enough means basically depends on the probablility of failure of the
> others elements related.

Hi, just a quick note here: physicists build systems as probability
products, but that only because laws are different in small
worlds. :-)

Alex

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 11 Feb 2002 23:37:31 +0100 (CET)

> have valuable IP security properties and are probably exploitable in

CGA = Cryptographically Generated Addresses

  Erik

---

From: Alexandru Petrescu <[email-masked]>
Date: 12 Feb 2002 10:17:40 +0100

> CGA = Cryptographically Generated Addresses

Right.

EGA = Expensively Generated Addresses :-)

Alex