Коллизия хэш-функции MAC-адреса

Доброго времени суток, коллеги.

Как говорит народная мудрость, век живи — век учись.
Довелось недавно столкнуться вживую с явлением, описанным в заголовке, о чем и пойдет речь ниже.

Дома у меня, как ни банально это звучит, есть интернет. Проводной, безлимитный, возможно даже скоростной. Я не «качок», поэтому не отслеживаю, что там на моем тарифе, по которому я когда-то давно подключался (и который меня до сих пор устраивает своей скромной абонплатой), происходит. Способ доступа — pptp vpn (к чести провайдера, это исключительно по моей лени, т. к. достаточно простого обращения, что бы перейти на давно внедряемую схему vlan на пользователя и белый IP). В сегменте народа мало, один-два человека. И вот однажды понадобилось «покачать», при этом скорость была явно не на должном уровне, и, как оказалось, с локальных ресурсов в том числе. Пропуская простые телодвижения по диагностике, сразу перейду к сути. Запущенный на интерфейсе снифер показал, что в мой 100мбит линк на хорошей такой скорости льется чей-то входящий трафик. Как оказалось — соседа по Vlan. Стало интересно, ведь это было не моих рук дело, боевой софт я не расчехлял, честно-честно. Снифер показывал, что DST MAC в пакетах был соседский, однако они приходили на мой интерфейс в том числе.
Подумалось: «Свич зафлудили, FDB переполнилась». Но это было не так. Разговор с админом провайдера (весьма опытным и грамотным товарищем) прояснил ситуацию. Это было как раз оно самое — коллизия хэш-функции MAC-адреса.

Я попробовал разобраться в сути явления. Как известно, если свич работает в режиме Store and forward, он обучается SRC MAC и в дальнейшем трафик для данных MAC будет форвардиться только через нужные порты. Хорошо известна атака, которая приводит к переполнению forwarding database. Часто в таких случаях можно услышать фразу: «свич превращается в тупой хаб». На самом деле это не совсем точно. MAC-адреса, которым устройство уже обучилось, будут жить в таблице и теоретически, если админ настроил время жизни достаточно большим — жить долго. Трафик на такие MAC-адреса не будет продвигаться через все порты. Новые же MAC-адреса в таблицу поиска попадать не будут, обучение не произойдет и для данных MAC как раз будет flooding.
Но, как оказывается, обучение (learning) может НЕ произойти еще по одной причине.

Позволю себе процитировать известный ресурс nag.ru, а именно довольно старую, но от этого не менее интересную статью

nag.ru/articles/reviews/15587/raz-tablitsa-dva-tablitsa.html

"Во-вторых, таблица, например Adress Resolve LookUp, хранит не сам мак, а хэш (bitmap). Хэш можно сделать только из мака (целиком), а можно — из мака + vlan id. Если разрядность хеша была при проектировании коммутатора заложена с расчетом только на мак-адрес, то можно добавить в свитч поддержку vlan-ов, если делать хэш не из 48 бит, а, например, из 40 битов мак-адреса и 8 битов vlan id. При некотором допущении все работает. "

Cитуация немного проясняется. Если для нескольких разных MAC (или MAC+vlan) хеши (bitmap) совпадут (коллизия) то…? А что собственно будет? Там, где должно было появиться две записи в FDB будет только одна. Я не знаю, если честно, будет ли перезапись, или сохранится старая строка, но в любом случае эфекта широковещания не будет. Трафик для одного из MAC (которому не повезло) пойдет через другой, не относящийся к нему порт.

Вопрошение гугля дало много тем на forum.nag.ru с жалобами на необучение некоторым MAC-ам при НЕпереполненной 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

Там же звучали и термины «слабая хеш функция», «коллизия». Но что же все таки происходит, почему необучение и flooding как результат?

Ответ подсказала документация циско, а именно

www.cisco.com/en/US/prod/collateral/switches/ps5718/ps708/white_paper_c11-663636.html#wp9000182

Память, используемая для хранения физических адресов и последующего поиска разбивается на страницы. Хэш функция, в которую сворачивается MAC определяет номер этой страницы и строку в ней для хранения адреса, проще говоря — индекс в этой таблице. Идеальная хэш функция дает для входного аргумента уникальное значение. Но приближенная к идеальной функция будет иметь на выходе число высокой разрядности, что заставляет таблицу быть весьма большой, и функция будет достаточно сложной и (возможно?) относительно медленной. Т. е. нужен разумный компромисс. Циска утверждает:

"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)."

И далее:

«If 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.»

Кажется оно. «floods in hardware».

Как-то примерно так я объяснил для себя свой случай в локалке (в смысле технических подробностей).

По методике, описанной на nag.ru, тестил свои девайсы уровня доступа (с2960, at8326, at8550) — проблема не наблюдалась, таблица забивалась ровно на 100%, кол-во «нафлуженных» MAC точно совпадало при этом с числом обученных.

Если кто-то знает больше по данной теме, прошу, коллеги, делитесь в комментариях.