Преодоление барьера из двух симметричных NAT

Материал из YourcmcWiki
Версия от 15:27, 20 сентября 2009; VitaliyFilippov (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

breakNAT — как «проломить» барьер из двух симметричных NAT

NAT (от англ. Network Address Translation — «преобразование сетевых адресов») — механизм в сетях TCP/IP, позволяющий преобразовывать IP-адреса транзитных пакетов. Также имеет названия IP Masquerading, Network Masquerading и Native Address Translation.

Дано

Даны два хоста host1 и host2, подключённые к сети Internet через маршрутизаторы с публичными IP-адресами nat1 и nat2, осуществляющие трансляцию сетевых адресов (NAT). Каждому новому исходящему соединению от первого хоста (host1) сопоставляется некоторый свободный порт известного IP-адреса маршрутизатора (nat1), аналогично host2 и nat2. Присваиваемый номер порта зависит от порта источника, а также порта и IP-адреса назначения, т.е устройства nat1 и nat2 осуществляют симметричную трансляцию сетевых адресов (Symmetric NAT) типа queued resource allocation или random port allocation [1] (выбор порта из очереди свободных или выбор произвольного свободного порта).

Задача

Установить прямое IP соединение между host1 и host2 (без пересылки всех пакетов через третий хост).

Решение

Для некоторых случаев, когда возможно какое-либо «предсказание» стратегий выделения портов трансляторами адресов, описаны решения в [1], [2] и [3], мы же рассматриваем общий случай — очередь или случайное выделение.

Итак, во-первых, очевидно, что в этом случае без «сторонней помощи» хосты host1 и host2 с этой задачей справиться не смогут, т.к: (в рассуждениях (i, j) = (1,2) или (2,1))

  1. hosti не может открыть соединение с hostj напрямую, т.к из-за трансляции адресов во всех пакетах, направленных в Internet от hostj, поле «источник» подменяется на адрес natj и выбранный устройством natj порт, назовём этот порт portj;
  2. аналогично hostj не может открыть соединение с hosti;
  3. чтобы hosti и hostj могли соединиться, они должны узнать номера портов portj и porti соответственно, то есть hosti должен иметь возможность отправлять пакеты на natj:portj;
  4. однако, до того момента как hosti отправит первый пакет на hostj:portj, сопоставления с porti вообще не существует;
  5. следовательно, чтобы hosti мог отправить пакет hostj, он должен знать portj, а чтобы знать portj, ему должен прийти хотя бы один пакет от hostj (оттранслированного в natj:portj), а чтобы ему этот пакет пришёл, hostj должен знать porti, а чтобы знать porti, ему должен прийти хотя бы один пакет от hosti… круг замкнулся;
  6. то есть задача не имеет решения — без «сторонней помощи» hosti и hostj действительно не могут открыть прямое соединение друг с другом.

Итак, мы показали, что без «сторонней помощи» открыть прямое соединение друг с другом hosti и hostj не могут.

Во-вторых, с использованием некоторой сторонней помощи задача становится разрешима, пусть и не без труда: установление соединения может отнять более получаса времени. Это всё ещё не подходит для размещения за NAT’ом полноценного сервера, но для задач, предполагающих небольшое количество «долгоживущих» соединений (например, одного), это уже вполне допустимо. Примером такой задачи может служить установка VPN-соединения между двумя компьютерами, не имеющими прямого доступа к сети Internet.

Мы будем использовать третий хост, имеющий публичный IP-адрес host3 в сети Internet. Будем также использовать протокол UDP, который не гарантирует доставку пакетов, но зато и не требует постоянного отслеживания и согласования sequence number'ов.

Во-первых, мы будем предполагать, что всё время работы алгоритмы каждый хост hosti имеет открытое «управляющее» соединение с host3 и всё согласование работы алгоритма происходит именно через эти «управляющие» соединения.

Первым шагом к решению задачи будет определение «времени жизни соединения» на каждом из устройств nati.

«Время жизни соединения» lifei на устройстве nati есть максимально возможный интервал времени между двумя последовательными пакетами с хоста hosti на один и тот же IP-адрес и порт, при котором porti не меняется.

Чтобы определить «время жизни соединения» на устройстве nati:

  1. Отправляем с хоста hosti пакеты на заранее выбранный порт третьего хоста host3 с возрастающими интервалами (1 сек, 2 сек, 3 сек, …)
  2. На host3 при приходе первого пакета сохраняем номер порта источника, при приходе каждого последующего сравниваем сохранённый номер порта с портом, записанным в поле «источник» пришедшего пакета; если они не равны, значит, интервал превышен — сохраняем предыдущий интервал как lifei и выходим из цикла.

Теперь рассмотрим сам алгоритм:

  1. Отправляем с host1 пакет на заранее заданный порт хоста host3;
  2. На host3 сохраняем порт источника, с которого приходит отправленный в предыдущем пункте пакет (обозначим этот порт за port1);
  3. Ждём (life1+1) секунд;
  4. С host2 на nat1:port1 начинаем отправлять пакеты с заранее известным содержимым и временными интервалами, равными (life1-1) секунд (или меньше — всё зависит от скорости канала между host2 и nat1);
  5. Перебираем порты port2 и отправляем с host3 от имени host1:port1 на адрес nat2:port2 пакеты с номером порта port2 в теле пакета;
  6. Ровно один пакет из отправленных в предыдущем пункте придёт хосту host2, после чего сообщаем с хоста host2 хосту host3 номер порта port2, указанный в теле пришедшего пакета, по управляющему соединению;
  7. С хоста host3, также используя управляющее соединение, сообщаем хосту host1 номер порта port2;
  8. Самая долгая стадия процесса: начинаем отправлять пакеты с временным интервалом (life1+1) с хоста host1 на адрес nat2:port2, «заставляя» устройство nat1 снова выбрать порт port1;
  9. Т.к мы имеем дело с симметричным NAT, использующим либо очередь свободных портов, либо выбор случайного свободного порта, рано или поздно port1 снова будет выбран устройством, хост host2 получит пакет от хоста host1, и соединение будет установлено.

Очевидно, в таком виде алгоритм является алгоритмом сложности O(n), где n — число возможных портов для перебора (в наихудшем случае это 65536). Посмотрим, можно ли как-нибудь улучшить этот результат:

  1. Во-первых, можно делать всё то же самое, используя не один выбранный порт port1, а k > 1 одновременно, при этом в среднем мы ускорим результат в k раз (сложность снизится до O(n/k));
  2. Во-вторых, можно определить T — среднее количество новых соединений, через которое номер порта повторяется, и сразу после выполнения первого пункта алгоритма отправить m пакетов на разные IP-адреса и порты (где m — меньшее T, но сопоставимое с T число, например, T/2 или T*3/4), чтобы быстро «прокрутить» очередь или датчик случайных чисел на устройстве nat1, не обращая внимания на результат. В этом случае сложность алгоритма снизится в среднем в T/(T-m) раз.
Заключение

Задача «преодоления» барьера в виде двух симметричных NAT разрешима алгоритмом сложности O(n), и хотя в реальных условиях преодоление такого барьера займёт достаточно долгое время, оно всё же возможно. Реализации алгоритма на данный момент не существует, то есть все рассуждения в статье — чисто теоретические, надеюсь, однако, что из-за этого не менее корректные.

Ссылки
  1. 1,0 1,1 Обход некоторых типов Symmetric NAT с помощью STUN: Symmetric NAT Traversal using STUN [draft-00] (автор — Y.Takeda);
  2. wikipedia:Simple traversal of UDP over NATs
  3. Traversal Using Relay NAT (TURN) [draft-08]

(c) Виталий Филиппов aka vitalif, 2007 г.