Subject: [6lo] Address protected neighbor discovery

From: Mohit Sethi <[email-masked]>
Date: Wed, 20 Jul 2016 11:59:13 +0200

Dear Behcet and Pascal

I have previously reviewed the draft on address protected neighbor 
discovery: draft-sarikaya-6lo-ap-nd-01.

I generally like the idea but still have some questions. I wonder what 
about collisions for cryptographic IDs. The draft defines them as 
64-bits long. I assume that at a minimum 80 bits are needed to assume 
that it is collision free. Or is it the case that collisions are not an 
issue in this case?

Thanks
/--Mohit

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 20 Jul 2016 13:16:39 +0200

On 07/20/2016 11:59 AM, Mohit Sethi wrote:
> that it is collision free. Or is it the case that collisions are not 
> an issue in this case?

I just ran some numbers through for another problem with a 64bit number 
field.  It works out as follows.

The formula is:  1 - e^{-k^2/(2n)}

Where n is your maximum popluation size (2^64 here, 1.84E19) and K is 
your actual population.

A .01% probablity of a collision is  a bit less than 66M devices.

If everyone in the world has one device (7B), then you are up to a 73% 
probablity of a collision.

So your risk of a collision on a network is there, but really low.

ID author, you may want to put this formula into your draft.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Wed, 20 Jul 2016 12:27:11 +0000

Thanks Bob!

I think the bottom line here is what's the exposure. If the collision occurred on a MAC address that would effectively get packets to the wrong place and would partially cut off devices from the network.

No such thing here. The collision has no operational consequence. Both nodes will register their addresses fine and there will be no visible effect unless the IPv6 addresses are also in collision.

Is there a security opening then?

The exposure is that two devices may be capable of claiming one another's address and the 6LBR will fail to prevent this, putting us back to today's situation for these 2 particular devices. 

Even in the highly remote chance that they are on a same subnetwork, even if one is a really mean device, L2 crypto does not allow node B to see what UID is used by device A so those 2 devices will not know they are in this situation.

It's good to add words to explain all this but the chance of accident are too remote to be of consequence. Instead we need to focus on getting a CGA that is hard enough to attack....

Regards,

Pascal

> Le 20 juil. 2016 à 13:17, Robert Moskowitz <[email-masked]> a écrit :
> 
> 
> 
>> I have previously reviewed the draft on address protected neighbor discovery: draft-sarikaya-6lo-ap-nd-01.
>> 
>> I generally like the idea but still have some questions. I wonder what about collisions for cryptographic IDs. The draft defines them as 64-bits long. I assume that at a minimum 80 bits are needed to assume that it is collision free. Or is it the case that collisions are not an issue in this case?
> 
> I just ran some numbers through for another problem with a 64bit number field.  It works out as follows.
> 
> Where n is your maximum popluation size (2^64 here, 1.84E19) and K is your actual population.
> 
> If everyone in the world has one device (7B), then you are up to a 73% probablity of a collision.
> 
> _______________________________________________
> 6lo mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/6lo

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 20 Jul 2016 14:32:50 +0200

My numbers show that on a network, the probablity is so small that the 
address is statistically unique.

Even with 50,000 devices on a network, the probably would be 6.67E-9%  
Just not there.

---

From: Behcet Sarikaya <[email-masked]>
Date: Wed, 20 Jul 2016 09:54:04 -0500

Hi Bob,

On Wed, Jul 20, 2016 at 7:32 AM, Robert Moskowitz
<[email-masked]> wrote:
> Even with 50,000 devices on a network, the probably would be 6.67E-9%  Just
> not there.
>

No matter how small, there is still some chance of collision so I
think we should deal it in the draft?

Regards,

Behcet
>> I think the bottom line here is what's the exposure. If the collision
>> occurred on a MAC address that would effectively get packets to the wrong
>> place and would partially cut off devices from the network.
>>
>> No such thing here. The collision has no operational consequence. Both
>> nodes will register their addresses fine and there will be no visible effect
>> unless the IPv6 addresses are also in collision.
>>
>> The exposure is that two devices may be capable of claiming one another's
>> address and the 6LBR will fail to prevent this, putting us back to today's
>> situation for these 2 particular devices.
>>
>> Even in the highly remote chance that they are on a same subnetwork, even
>> if one is a really mean device, L2 crypto does not allow node B to see what
>> UID is used by device A so those 2 devices will not know they are in this
>> situation.
>>
>> It's good to add words to explain all this but the chance of accident are
>> too remote to be of consequence. Instead we need to focus on getting a CGA
>> that is hard enough to attack....
>>
>>
>> Regards,
>>
>> Pascal
>>
>>>> about collisions for cryptographic IDs. The draft defines them as 64-bits
>>>> long. I assume that at a minimum 80 bits are needed to assume that it is
>>>> collision free. Or is it the case that collisions are not an issue in this
>>>> case?
>>>

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 20 Jul 2016 20:02:19 +0200

Of course, this is all assuming that you really have a true random 
distribution across the 64 bit address space, not getting those bad 
random seeds that UofMich found with SSL server keys. If the resultant 
max population is only 2^32, a 50,000 device deployment has a 25% 
probablity of collision.

So you might also need to say something about the importance of random 
numbers.  Might already need that for other items...

Ya got to love ASSuMEsions.

:)

On 07/20/2016 06:43 PM, Pascal Thubert (pthubert) wrote:
> I think we can use Bob's words to show how rare and then explain that collision is inconsequential anyway, so people do not keep rising the point...
>
> Regards,
>
> Pascal
>
>> Le 20 juil. 2016 à 16:54, Behcet Sarikaya <[email-masked]> a écrit :
>>
>> Hi Bob,
>>