Протокол головоломки с управляемым туром

Протокол головоломки с управляемым туром близок по шагам к Client Puzzle Protocol. Каждый клиент должен пройти такой тур-головоломку до получения обслуживания от сервера, если сервер подозревает атаку или его загрузка превысила предустановленный порог. В упрощённом виде, головоломка с управляемым туром представляет собой прохождение тура, требующего совершения нескольких циклов «туда-обратно» к специальным узлам — «экскурсоводам» — в определённой последовательности. Эта последовательность неизвестна клиенту заранее, и только каждый очередной экскурсовод сообщает клиенту, к какому стоит обращаться следующим, чтобы пройти все точки тура в правильном порядке. Одна и та же точка-экскурсовод может встречаться в туре несколько раз, поэтому отдельный её проход называется «остановкой». Клиент узнаёт адрес следующей точки только после взаимодействия с текущей.

Решение головоломки заключается в прохождении тура в нужном порядке. Начав с первой «остановки», клиент связывается с каждым экскурсоводом и получает ответ, включающий уникальный токен. Токен из ответа текущей точки нужен для вычисления адреса следующей; первая точка вычисляется на основе токена, полученного от сервера при начале головоломки.

Клиент должен передавать полученный токен от текущего экскурсовода следующему, который использует его для собственной функции генерации токена. После завершения тура токен от последнего экскурсовода вместе с исходным токеном сервера отправляется обратно на сервер в подтверждение прохождения. Сервер может быстро проверить их корректность и предоставляет услугу лишь после успешной валидации^[1].

Перед стартом головоломки в системе должно быть задано ${\displaystyle N}$ экскурсоводов, где ${\displaystyle N\geq 2}$. Сервер устанавливает общий секретный ключ ${\displaystyle k_{js}}$ с каждым экскурсоводом ${\displaystyle G_{j}}$ по защищённому каналу, где ${\displaystyle 0\leq j<N}$. Сервер также использует короткоживущий секрет ${\displaystyle K_{s}}$ для вычисления первого хеш-значения, которое отправляется клиенту с сообщением о начале головоломки. В этом сообщении также указывается длина тура ${\displaystyle L}$ — параметр сложности. На иллюстрации выше приведен пример для ${\displaystyle N=2}$ и ${\displaystyle L=5}$.

Детали каждого этапа протокола:

• Запрос на услугу: Клиент ${\displaystyle x}$ отправляет серверу запрос. Если нагрузка нормальная — запрос обрабатывается стандартно; если сервер перегружен — инициируется «генерация головоломки».
• Генерация головоломки: Сервер отвечает клиенту ${\displaystyle x}$ сообщением с заданием закончить управляемый тур. В сообщении содержатся длина тура ${\displaystyle L}$ и хеш ${\displaystyle h_{0}}$, вычисляемый по формуле:

${\displaystyle h_{0}=hash(A_{x}\;||\;L\;||\;ts\;||\;K_{s})}$

где ${\displaystyle ||}$ — конкатенация, ${\displaystyle A_{x}}$ — уникальный идентификатор клиента (например, IP-адрес), ${\displaystyle ts}$ — усечённая временная метка, а ${\displaystyle hash}$ — криптографическая хеш-функция (например, SHA-1).

• Решение головоломки: Клиент вычисляет индекс экскурсовода для ${\displaystyle l}$-й остановки по формуле:

${\displaystyle S_{l}=(h_{l-1}\mod N)}$

где ${\displaystyle 0<l\leq L}$. При контакте клиента ${\displaystyle x}$, экскурсовод ${\displaystyle G_{j}}$ вычисляет хеш ${\displaystyle h_{l}}$ (${\displaystyle 0<l\leq L}$) по формуле:

${\displaystyle h_{l}=hash(h_{l-1}\;||\;l\;||\;L\;||\;A_{x}\;||\;ts\;||\;k_{js})}$

где ${\displaystyle l}$ — номер остановки, ${\displaystyle k_{js}}$ — общий ключ экскурсовода ${\displaystyle G_{j}}$ и сервера. После получения ответа сервера клиент вычисляет индекс ${\displaystyle S_{1}}$ по формуле для ${\displaystyle S_{l}}$ и отправляет набор (${\displaystyle h_{0}}$, ${\displaystyle 1}$, ${\displaystyle L}$) экскурсоводу ${\displaystyle G_{S_{1}}}$, где второе значение указывает текущую остановку. В ответ он получает ${\displaystyle h_{1}}$, вычисляемый по формуле для ${\displaystyle h_{l}}$. Далее клиент повторяет процесс ${\displaystyle L-1}$ раз, обращаясь к экскурсоводам ${\displaystyle G_{S_{2}},G_{S_{3}},...,G_{S_{L}}}$. Последний ответ ${\displaystyle h_{L}}$ и исходный ${\displaystyle h_{0}}$ клиент отправляет серверу — это его решение.

• Проверка: Сервер, получив связку (${\displaystyle h'_{0}}$, ${\displaystyle h'_{L}}$), сначала сверяет ${\displaystyle h'_{0}}$ с ранее вычисленным значением по формуле для ${\displaystyle h_{0}}$. При совпадении он пересчитывает цепочку хешей по формуле для ${\displaystyle h_{l}}$ и сверяет ${\displaystyle h'_{L}}$ с финальным результатом ${\displaystyle h_{L}}$. Если оба значения корректны, ресурсы для запроса выделяются. Поскольку сервер знает все секретные ключи (${\displaystyle k_{1s},k_{2s},...,k_{Ns}}$), он может восстановить всю цепочку без взаимодействия с экскурсоводами. Сервер и экскурсоводы должны использовать близко синхронизированные часы для корректных вычислений.

Вычислительно-сложные протоколы головоломок позволяют смягчить атаки отказа в обслуживании: чем активнее атакующий, тем больше головоломок ему приходится решать за счёт собственных ресурсов. Однако клиенты с мощным оборудованием способны решать головоломки быстрее менее обеспеченных, вытесняя обычных пользователей^[1][2][3][4].

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

Протокол головоломки с управляемым туром накладывает на клиента не вычислительную, а сетевую задержку через циклы туда-обратно. Таким образом, скорость поступления запросов регулируется задержками обработки, очередей и распространения на промежуточных маршрутизаторах, находящихся вне контроля конечных клиентов. Даже злоумышленник с большими вычислительными ресурсами не может получить преимущество относительно обычных пользователей^[1].

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