Re: [STDS-802-Privacy] using only 24 bits of random MAC
Hi Mathieu,
On 7 Oct 2014, at 09:58, Mathieu Cunche wrote:
> Hi Dan and Piers,
> On 10/05/2014 09:03 AM, Dan Harkins wrote:
>> Hi Mathieu,
>>
>> On 10/2/14 6:54 AM, "Mathieu Cunche" <mathieu.cunche@xxxxxxxx> wrote:
>>
>>> Hi all,
>>>
>>> Even if in the case of 46 random bits, can the eventuallity of a
>>> collision be ruled out ? The current reccord is 30,0000+ devices and
>>> it already gives a 1:156000 probability.
>>>
>>> Pushing the numbers to 60.000 and 300.000 devices, we obtain:
>>> p(60000, 2^46) = 0.000025
>>> p(300000, 2^46) = 0.00064
>>>
>>> I agree that 300.000 of device is high (unrealistic ?) and that the
>>> corresponding probabilities are small, but can we consider that
>>> collisions will never happen even with 46 bits ?
>>
>> Keep in mind that the the N used to calculate the probability is
>> the number of unique devices on the switched network. As soon a you
>> reach a router it doesn't matter if a device on the other side is
>> using your address. The size of a forwarding table on a switch just
>> doesn't go up to 300,000. They will _theoretically_ go up to 64k
>> but in practice they don't. So when people architect their network
>> they consciously make it so their switches don't melt down.
>
> Correct me if I am wrong. It seems that you are both considering the
> collision issue in routing tables, but MAC collision can have other
Not really - the ARMD WG was looking at ARP - which is used on the LAN before routing. I was mainly brining up the ARMD RFC as a reference for the number of devices that might share a network segment.
> negative effects at link layer. One can imagine a wireless
> environement with up to 300,000 interfaces even if they are not all on
> the same network.
>
I agree there are plenty of other issues.
> As for the number of distinct MAC address found in one environment, we
> should take into account potential changes at the protocol and/or
> application level. For instance, someone mentioned the possibility of
> having multiple MAC address per interface. This has the potential to
> multiply the number of MAC address even if the number of devices
> remain the same.
>
That is what I implied when I quoted from RFC6820 - "100,000 physical machines and many times that number of VMs"
Piers
> Mathieu
>
>>
>> We can never say never but 1:156,000 is very highly unlikely.
>>
>> Dan.
>>
>>> Mathieu
>>>
>>> On 10/01/2014 05:51 PM, Dan Harkins wrote:
>>>>
>>>> Hello,
>>>>
>>>> As Mathieu reported today, when randomizing only 24 bits of the MAC
>>>> a collision is basically assured. We can calculate the probability of a
>>>> collision out of a pool of c when there are n people by:
>>>>
>>>> p(n; c) = 1 - ((c-1)/c)^(n*(n-1)/2)
>>>>
>>>> If we are only randomizing 24 bits of MAC we end up with numbers
>>>> like this:
>>>>
>>>> p(500, 2^24) = 0.0074
>>>> p(1000, 2^24) = 0.029
>>>> p(5000, 2^24) = 0.525 <-- worse than a coin flip
>>>>
>>>> Even with only 500 people it's basically assured that there will be a
>>>> collision after a while. Whereas if we randomize 46 bits of MAC we end
>>>> up with numbers like this:
>>>>
>>>> p(500, 2^46) = 0.0000000018
>>>> p(1000, 2^46) = 0.0000000071
>>>> p(5000, 2^46) = 0.0000001776
>>>> p(10000, 2^46) = 0.0000007105
>>>> p(30000, 2^46) = 0.00000639
>>>>
>>>> The record for most simultaneous associations in a wi-fi network is
>>>> 30,0000+ and even in that situation, assuming everyone is randomizing
>>>> MAC addresses it's still around 1:156000. Never say never but we can say
>>>> "highly unlikely."
>>>>
>>>> Whereas if we only randomize 24 bits we can safely say "definitely
>>>> assured".
>>>> I do not think this study group wants to come up with recommendations on
>>>> how to most assuredly screw up a network.
>>>>
>>>> The critical issue is not whether someone temporarily sets his MAC
>>>> address
>>>> to that "owned" by someone somewhere (and I am still not convinced that
>>>> purchasers of OUIs get them with the "local" bit set), the critical
>>>> issue is
>>>> whether there will be collisions on the switched network. We do not
>>>> need to
>>>> assure that a randomly chosen MAC address is unique in the world, we
>>>> just
>>>> need to make it as unlikely as possible that that address is already
>>>> used on the
>>>> same switched network. We can't make that assurance with only 24 bits
>>>> but we can with 46.
>>>>
>>>> Please, let's abandon the idea of following 802.1's recommendations
>>>> for
>>>> their small, local LAN randomized MAC scheme. It won't work in wireless
>>>> in the real world.
>>>>
>>>> regards,
>>>>
>>>> Dan.
>>>>
>>>>
>>>