MAC Address Hash Collision
Good day, colleagues.
According to popular wisdom, live and learn.
Recently I had a chance to encounter live with the phenomenon described in the title, which will be discussed below.
At home, no matter how trite it sounds, there is Internet access. Wired, unlimited, maybe even high-speed. I’m not a “roll”, so I don’t keep track of what’s happening on my tariff, at which I once connected for a long time (and which still suits me with its modest monthly fee). The access method is pptp vpn (to the honor of the provider, this is only in my laziness, because a simple appeal is enough to switch to the long-implemented vlan scheme for the user and white IP). In the segment of people there are few, one or two people. And once it was necessary to "rock", while the speed was clearly not up to the mark, and, as it turned out, from local resources as well. Skipping simple gestures for diagnosis, I will immediately turn to the point. The sniffer launched on the interface showed that someone’s incoming traffic is pouring into my 100mbit link at a good speed. As it turned out - a neighbor in Vlan. It became interesting, because it was not my work, I did not uncover combat software, honestly, honestly. Sniffer showed that the DST MAC in the packets was neighbor, however, they came to my interface as well.
It was thought: "The switch is flooded, FDB is full." But that was not so. A conversation with the administrator of the provider (a very experienced and competent friend) clarified the situation. It was just the same thing - the collision of the hash function of the MAC address.
I tried to understand the essence of the phenomenon. As you know, if a switch operates in Store and forward mode, it learns the SRC MAC and in the future traffic for MAC data will be forwarded only through the necessary ports. The attack that overflows the forwarding database is well known. Often in such cases, you can hear the phrase: "the switch turns into a dumb hub." In fact, this is not entirely accurate. The MAC addresses that the device has already learned will live in the table, and theoretically, if the admin has configured the lifetime to be large enough, it will live for a long time. Traffic to such MAC addresses will not go through all ports. New MAC addresses will not get into the lookup table, training will not happen, and for the MAC data, there will just be flooding.
But, as it turns out, learning can NOT happen for another reason.
Let me quote a well-known resource nag.ru, namely a rather old, but no less interesting article
nag.ru/articles/reviews/15587/raz-tablitsa-dva-tablitsa.html
" Secondly, a table, for example Adress Resolve LookUp, it’s not the poppy itself that stores the hash (bitmap). The hash can be made only from the poppy (in its entirety), or it can be made from the poppy + vlan id. add vlan support to the switch if you have to make a hash not from 48 bits, but, for example, from 40 bits of the mac address and 8 bits of vlan id. With some assumption, everything works. "
The situation is becoming clearer. If for several different MAC (or MAC + vlan) hashes (bitmap) match (collision) then ...? And what will actually be? Where two records were to appear in FDB there will be only one. I don’t know, to be honest, whether there will be a rewrite or the old line will be saved, but in any case there will be no broadcast effect. Traffic for one of the MACs (which is unlucky) will go through another, non-related port.
Google’s implementation has yielded a lot of topics on forum.nag.ru complaining that some MACs have failed to learn when FDB is NOT full.
forum.nag.ru/forum/index.php?showtopic=52882
forum.nag.ru/forum/index.php?showtopic=58022
forum.nag.ru/forum/index.php?showtopic=58532
The terms “weak hash function” and “collision” sounded in the same place. But what is still happening, why is learning and flooding as a result?
The answer was suggested by the cisco documentation, namely
www.cisco.com/en/US/prod/collateral/switches/ps5718/ps708/white_paper_c11-663636.html#wp9000182

The memory used for storing physical addresses and subsequent searches is paginated. The hash function that the MAC collapses into determines the number of this page and the line in it to store the address, in other words, the index in this table. The ideal hash function provides a unique value for the input argument. But a function close to ideal will have a high-bit number at the output, which makes the table be very large, and the function will be quite complex and (possibly?) Relatively slow. That is, a reasonable compromise is needed. Tsiska states:
" The hash function used by the PFC4 and DFC4 is 99 percent efficient, meaning that the system can populate 99 percent of the MAC address table, at a minimum (the system can populate 100 percent of the MAC address table if there are no collisions)."
And further:
" I f a collision does occur and a MAC address cannot be learned, the system floods in hardware (see Step 3 in Figure 1). All Layer 2 operations are hardware based, so no CPU impact is realized in this case. "
It seems." Floods in hardware ".
Somehow I explained my case to myself in LAN (in the sense of technical details).
Using the method described on nag.ru, I tested my access level devices (c2960, at8326, at8550 ) - the problem is not observed, the table would shrink by exactly 100%, the number of "nafluzhennyh» MAC coincided exactly with the with the number of training.
If someone knows more on the subject, please, colleagues, share in the comments.
UPD: for memory and a reference to the discussion on the topicforum.dlink.ru/viewtopic.php?f=2&t=123334&sid=21a5f96978673427f2ac8b84fb91d045
According to popular wisdom, live and learn.
Recently I had a chance to encounter live with the phenomenon described in the title, which will be discussed below.
At home, no matter how trite it sounds, there is Internet access. Wired, unlimited, maybe even high-speed. I’m not a “roll”, so I don’t keep track of what’s happening on my tariff, at which I once connected for a long time (and which still suits me with its modest monthly fee). The access method is pptp vpn (to the honor of the provider, this is only in my laziness, because a simple appeal is enough to switch to the long-implemented vlan scheme for the user and white IP). In the segment of people there are few, one or two people. And once it was necessary to "rock", while the speed was clearly not up to the mark, and, as it turned out, from local resources as well. Skipping simple gestures for diagnosis, I will immediately turn to the point. The sniffer launched on the interface showed that someone’s incoming traffic is pouring into my 100mbit link at a good speed. As it turned out - a neighbor in Vlan. It became interesting, because it was not my work, I did not uncover combat software, honestly, honestly. Sniffer showed that the DST MAC in the packets was neighbor, however, they came to my interface as well.
It was thought: "The switch is flooded, FDB is full." But that was not so. A conversation with the administrator of the provider (a very experienced and competent friend) clarified the situation. It was just the same thing - the collision of the hash function of the MAC address.
I tried to understand the essence of the phenomenon. As you know, if a switch operates in Store and forward mode, it learns the SRC MAC and in the future traffic for MAC data will be forwarded only through the necessary ports. The attack that overflows the forwarding database is well known. Often in such cases, you can hear the phrase: "the switch turns into a dumb hub." In fact, this is not entirely accurate. The MAC addresses that the device has already learned will live in the table, and theoretically, if the admin has configured the lifetime to be large enough, it will live for a long time. Traffic to such MAC addresses will not go through all ports. New MAC addresses will not get into the lookup table, training will not happen, and for the MAC data, there will just be flooding.
But, as it turns out, learning can NOT happen for another reason.
Let me quote a well-known resource nag.ru, namely a rather old, but no less interesting article
nag.ru/articles/reviews/15587/raz-tablitsa-dva-tablitsa.html
" Secondly, a table, for example Adress Resolve LookUp, it’s not the poppy itself that stores the hash (bitmap). The hash can be made only from the poppy (in its entirety), or it can be made from the poppy + vlan id. add vlan support to the switch if you have to make a hash not from 48 bits, but, for example, from 40 bits of the mac address and 8 bits of vlan id. With some assumption, everything works. "
The situation is becoming clearer. If for several different MAC (or MAC + vlan) hashes (bitmap) match (collision) then ...? And what will actually be? Where two records were to appear in FDB there will be only one. I don’t know, to be honest, whether there will be a rewrite or the old line will be saved, but in any case there will be no broadcast effect. Traffic for one of the MACs (which is unlucky) will go through another, non-related port.
Google’s implementation has yielded a lot of topics on forum.nag.ru complaining that some MACs have failed to learn when FDB is NOT full.
forum.nag.ru/forum/index.php?showtopic=52882
forum.nag.ru/forum/index.php?showtopic=58022
forum.nag.ru/forum/index.php?showtopic=58532
The terms “weak hash function” and “collision” sounded in the same place. But what is still happening, why is learning and flooding as a result?
The answer was suggested by the cisco documentation, namely
www.cisco.com/en/US/prod/collateral/switches/ps5718/ps708/white_paper_c11-663636.html#wp9000182

The memory used for storing physical addresses and subsequent searches is paginated. The hash function that the MAC collapses into determines the number of this page and the line in it to store the address, in other words, the index in this table. The ideal hash function provides a unique value for the input argument. But a function close to ideal will have a high-bit number at the output, which makes the table be very large, and the function will be quite complex and (possibly?) Relatively slow. That is, a reasonable compromise is needed. Tsiska states:
" The hash function used by the PFC4 and DFC4 is 99 percent efficient, meaning that the system can populate 99 percent of the MAC address table, at a minimum (the system can populate 100 percent of the MAC address table if there are no collisions)."
And further:
" I f a collision does occur and a MAC address cannot be learned, the system floods in hardware (see Step 3 in Figure 1). All Layer 2 operations are hardware based, so no CPU impact is realized in this case. "
It seems." Floods in hardware ".
Somehow I explained my case to myself in LAN (in the sense of technical details).
Using the method described on nag.ru, I tested my access level devices (c2960, at8326, at8550 ) - the problem is not observed, the table would shrink by exactly 100%, the number of "nafluzhennyh» MAC coincided exactly with the with the number of training.
If someone knows more on the subject, please, colleagues, share in the comments.
UPD: for memory and a reference to the discussion on the topicforum.dlink.ru/viewtopic.php?f=2&t=123334&sid=21a5f96978673427f2ac8b84fb91d045