MAC Address Hash Collision
Good day, colleagues.
As the proverb says, live and learn.
I recently happened to encounter live with the phenomenon described in the title, which will be discussed below.
')
At home, no matter how trite it sounds, I have Internet. Wired, unlimited, maybe even fast. I am not a “jock”, so I don’t keep track of what’s on my tariff, which I used to connect for a long time (and which still suits me with my modest subscription fee), it happens. The access method is pptp vpn (to the credit of the provider, this is solely my own laziness, since a simple call is enough to switch to the vlan scheme that has been introduced to the user and the white IP for a long time). There are few people in the segment, one or two people. And once it took to “shake”, while the speed was clearly not up to par, and, as it turned out, from local resources as well. Skipping simple gestures on diagnostics, 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 on the Vlan. It became interesting, because it was not my handiwork, I did not uncover combat software, honestly, honestly. Sniffer showed that the DST MAC in the packets was neighboring, however they came to my interface as well.
I thought: "Switch flooded, FDB overflowed." But this was not the case. Conversation with the admin of the provider (very experienced and competent comrade) clarified the situation. This was exactly the same thing - the MAC address hash function collision.
I tried to understand the essence of the phenomenon. As it is known, if the switch works in the Store and forward mode, it learns the SRC MAC and in the future the traffic for the MAC data will be forwarded only through the necessary ports. A well-known attack that leads to an overflow of the forwarding database. Often in such cases you can hear the phrase: “the switch turns into a stupid hub”. In fact, this is not entirely accurate. MAC addresses that the device has already learned will live in the table and theoretically, if the admin has configured a lifetime long enough to live long. Traffic to such MAC addresses will not go through all ports. New MAC addresses will not be included into the lookup table, training will not occur and flooding will be just for MAC data.
But as it turns out, learning can NOT happen for one more 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, the table, for example, Adress Resolve LookUp, does not store the poppy itself, but the hash (bitmap). The hash can be made only from the poppy (entirely), but it can be made from the poppy + vlan id. If the hash capacity was used when designing the switch with the calculation only on the mac address, you can add vlan-s support to the switch, if you make a hash not of 48 bits, but, for example, of 40 bits of the mac-address and 8 bits of vlan id. With some assumption everything works. "
The situation clears up a little. If for several different MAC (or MAC + vlan) hashes (bitmap) match (collision) then ...? And what actually will be? Where there should have been two entries in FDB there will be only one. I don’t know, honestly, whether there will be a rewrite, or the old line will be preserved, but in any case there will be no broadcast effect. The traffic for one of the MAC (which is unlucky) will go through the other, unrelated port.
The introduction of Google gave a lot of topics to forum.nag.ru with complaints about not learning some MACs with NOT overflowing FDB.
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” also sounded there. But what all the same happens, why not learning and flooding as a result?
The answer was suggested by the tsisko documentation, namely
www.cisco.com/en/US/prod/collateral/switches/ps5718/ps708/white_paper_c11-663636.html#wp9000182
The memory used to store the physical addresses and the subsequent search is paginated. The hash function in which the MAC is minimized determines the number of this page and the string in it to store the address, in other words, the index in this table. The ideal hash function gives the input argument a unique value. But an approximate to ideal function will have a high-resolution number at the output, which causes the table to be very large, and the function will be rather complicated and (perhaps?) Relatively slow. That is, we need a reasonable compromise. Tsisk claims:
" The hash has been used for the PFC4 and the DFC4 is 99% for the MAC address table. . "
And further:
“I’m not addressing the network address (see Step 3 in Figure 1). The impact is realized in this case. "
It seems it. "Floods in hardware".
Something like this, I explained my case in LAN (in terms of technical details).
According to the technique described on nag.ru, testing their access level devices (2960, at8326, at8550) - the problem was not observed, the table was clogged exactly 100%, the number of “flooded” MACs exactly coincided with the number of trained ones.
If someone knows more about this topic, please, colleagues, share in the comments.
UPD: for memory a reference to the discussion of the topic forum.dlink.ru/viewtopic.php?f=2&t=123334&sid=21a5f96978673427f2ac8b84fb91d045
As the proverb says, live and learn.
I recently happened to encounter live with the phenomenon described in the title, which will be discussed below.
')
At home, no matter how trite it sounds, I have Internet. Wired, unlimited, maybe even fast. I am not a “jock”, so I don’t keep track of what’s on my tariff, which I used to connect for a long time (and which still suits me with my modest subscription fee), it happens. The access method is pptp vpn (to the credit of the provider, this is solely my own laziness, since a simple call is enough to switch to the vlan scheme that has been introduced to the user and the white IP for a long time). There are few people in the segment, one or two people. And once it took to “shake”, while the speed was clearly not up to par, and, as it turned out, from local resources as well. Skipping simple gestures on diagnostics, 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 on the Vlan. It became interesting, because it was not my handiwork, I did not uncover combat software, honestly, honestly. Sniffer showed that the DST MAC in the packets was neighboring, however they came to my interface as well.
I thought: "Switch flooded, FDB overflowed." But this was not the case. Conversation with the admin of the provider (very experienced and competent comrade) clarified the situation. This was exactly the same thing - the MAC address hash function collision.
I tried to understand the essence of the phenomenon. As it is known, if the switch works in the Store and forward mode, it learns the SRC MAC and in the future the traffic for the MAC data will be forwarded only through the necessary ports. A well-known attack that leads to an overflow of the forwarding database. Often in such cases you can hear the phrase: “the switch turns into a stupid hub”. In fact, this is not entirely accurate. MAC addresses that the device has already learned will live in the table and theoretically, if the admin has configured a lifetime long enough to live long. Traffic to such MAC addresses will not go through all ports. New MAC addresses will not be included into the lookup table, training will not occur and flooding will be just for MAC data.
But as it turns out, learning can NOT happen for one more 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, the table, for example, Adress Resolve LookUp, does not store the poppy itself, but the hash (bitmap). The hash can be made only from the poppy (entirely), but it can be made from the poppy + vlan id. If the hash capacity was used when designing the switch with the calculation only on the mac address, you can add vlan-s support to the switch, if you make a hash not of 48 bits, but, for example, of 40 bits of the mac-address and 8 bits of vlan id. With some assumption everything works. "
The situation clears up a little. If for several different MAC (or MAC + vlan) hashes (bitmap) match (collision) then ...? And what actually will be? Where there should have been two entries in FDB there will be only one. I don’t know, honestly, whether there will be a rewrite, or the old line will be preserved, but in any case there will be no broadcast effect. The traffic for one of the MAC (which is unlucky) will go through the other, unrelated port.
The introduction of Google gave a lot of topics to forum.nag.ru with complaints about not learning some MACs with NOT overflowing FDB.
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” also sounded there. But what all the same happens, why not learning and flooding as a result?
The answer was suggested by the tsisko documentation, namely
www.cisco.com/en/US/prod/collateral/switches/ps5718/ps708/white_paper_c11-663636.html#wp9000182
The memory used to store the physical addresses and the subsequent search is paginated. The hash function in which the MAC is minimized determines the number of this page and the string in it to store the address, in other words, the index in this table. The ideal hash function gives the input argument a unique value. But an approximate to ideal function will have a high-resolution number at the output, which causes the table to be very large, and the function will be rather complicated and (perhaps?) Relatively slow. That is, we need a reasonable compromise. Tsisk claims:
" The hash has been used for the PFC4 and the DFC4 is 99% for the MAC address table. . "
And further:
“I’m not addressing the network address (see Step 3 in Figure 1). The impact is realized in this case. "
It seems it. "Floods in hardware".
Something like this, I explained my case in LAN (in terms of technical details).
According to the technique described on nag.ru, testing their access level devices (2960, at8326, at8550) - the problem was not observed, the table was clogged exactly 100%, the number of “flooded” MACs exactly coincided with the number of trained ones.
If someone knows more about this topic, please, colleagues, share in the comments.
UPD: for memory a reference to the discussion of the topic forum.dlink.ru/viewtopic.php?f=2&t=123334&sid=21a5f96978673427f2ac8b84fb91d045
Source: https://habr.com/ru/post/155265/
All Articles