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

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

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

Дано

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

Задача

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

Решение

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

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

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

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

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

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

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

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

«Время жизни соединения» life_i на устройстве nat_i есть максимально возможный интервал времени между двумя последовательными пакетами с хоста host_i на один и тот же IP-адрес и порт, при котором port_i не меняется.

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

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

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

1. Отправляем с host₁ пакет на заранее заданный порт хоста host₃;
2. На host₃ сохраняем порт источника, с которого приходит отправленный в предыдущем пункте пакет (обозначим этот порт за port₁);
3. Ждём (life₁+1) секунд;
4. С host₂ на nat₁:port₁ начинаем отправлять пакеты с заранее известным содержимым и временными интервалами, равными (life₁-1) секунд (или меньше — всё зависит от скорости канала между host₂ и nat₁);
5. Перебираем порты port₂ и отправляем с host₃ от имени host₁:port₁ на адрес nat₂:port₂ пакеты с номером порта port₂ в теле пакета;
6. Ровно один пакет из отправленных в предыдущем пункте придёт хосту host₂, после чего сообщаем с хоста host₂ хосту host₃ номер порта port₂, указанный в теле пришедшего пакета, по управляющему соединению;
7. С хоста host₃, также используя управляющее соединение, сообщаем хосту host₁ номер порта port₂;
8. Самая долгая стадия процесса: начинаем отправлять пакеты с временным интервалом (life₁+1) с хоста host₁ на адрес nat₂:port₂, «заставляя» устройство nat₁ снова выбрать порт port₁;
9. Т.к мы имеем дело с симметричным NAT, использующим либо очередь свободных портов, либо выбор случайного свободного порта, рано или поздно port₁ снова будет выбран устройством, хост host₂ получит пакет от хоста host₁, и соединение будет установлено.

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

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

Заключение

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

Ссылки

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