Re: [STDS-802-Privacy] using only 24 bits of random MAC
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
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.
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.
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.
>>>
>>>
>>