Протокол головоломки с гидом

Протокол головоломки с гидом (GTP) - это криптографический протокол для смягчения атак типа «отказ в обслуживании» на уровне приложений . Он направлен на преодоление недостатков протоколов головоломок, основанных на вычислениях , в которых от клиентов требуется вычисление задач, связанных с жестким процессором или привязкой к памяти, которые отдают предпочтение клиентам с обильными вычислительными ресурсами. Протокол головоломки с гидом можно рассматривать как форму протокола доказательства работы (POW).

Обзор [ править ]

Шаги протокола протокола головоломки с гидом аналогичны шагам протокола головоломки клиента. Все клиенты должны выполнить головоломку с гидом перед получением обслуживания от сервера , если сервер подозревает, что в настоящее время он подвергается атаке отказа в обслуживании или его нагрузка превышает заранее определенный порог. Проще говоря, головоломка с гидом - это тур, который необходимо завершить, совершив несколько последовательных обходов к набору специальных узлов, называемых путеводителями , в последовательном порядке. Это называется экскурсия с гидом., потому что порядок посещения гидов неизвестен клиенту, и каждый гид должен направить клиента к следующему гиду, чтобы клиент завершил тур в правильном порядке. Один гид может появляться в туре несколько раз, поэтому термин « остановка» используется для обозначения одного появления гида в туре. Клиент знает, какой гид находится на следующей остановке, только после завершения посещения текущей остановки. ^{[ необходима цитата ]}

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

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

Шаги протокола [ править ]

Пример головоломки с гидом, когда количество гидов равно 2, а длина тура равна 5. Порядок тура: G1 -> G0 -> G1 -> G1 -> G0.

Прежде чем приступить к решению головоломки с гидом, необходимо настроить гидов в системе, где . Между тем, сервер устанавливает общий секрет с каждым гидом, используя защищенный канал, где . Сервер хранит кратковременный секрет для вычисления первого значения хеш-функции, которое возвращается клиенту как часть сообщения-головоломки. Сообщение-головоломка также содержит длину тура , которая используется для управления сложностью головоломки с гидом. На рисунке показан пример экскурсии, когда и .${\ 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}$

Подробности каждого шага протокола головоломки с гидом объясняются ниже. ^[1]

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

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

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

• Решение головоломки : клиент вычисляет индекс экскурсовода на -й остановке своего тура по следующей формуле:${\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 l}$${\displaystyle k_{js}}$${\displaystyle G_{j}}$${\displaystyle x}$${\displaystyle S_{1}}$${\displaystyle S_{l}}$${\displaystyle h_{0}}$${\displaystyle 1}$${\displaystyle L}$${\displaystyle G_{S_{1}}}$${\displaystyle h_{1}}$${\displaystyle G_{S_{1}}}$${\displaystyle h_{1}}$${\displaystyle h_{l}}$${\displaystyle x}$${\displaystyle L-1}$${\displaystyle G_{S_{2}},G_{S_{3}},...,G_{S_{L}}}$. Ответное сообщение от путеводителя по последней остановке содержит последнее значение хеш-функции , а клиент отправляет ( ) на сервер в качестве ответа на головоломку.${\displaystyle G_{S_{L}}}$${\displaystyle h_{L}}$${\displaystyle x}$${\displaystyle h_{0},\;h_{L}}$

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

Сравнение с другими протоколами головоломок [ править ]

Протоколы вычислительной головоломки с привязкой к ЦП, такие как Client Puzzle Protocol , могут смягчить эффект атаки отказа в обслуживании, потому что чем больше злоумышленник хочет перегрузить сервер, тем больше головоломок он должен вычислить и тем больше он должен использовать свои собственные вычислительные ресурсы. Клиенты с высокой вычислительной мощностью могут решать головоломки с гораздо большей скоростью, чем нуждающиеся клиенты, и могут нежелательно занимать большую часть ресурсов сервера. ^{[1] [2] [3] [4]}

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

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

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

См. Также [ править ]

• Система подтверждения работы
• Клиентский протокол головоломки
• CAPTCHA

Ссылки [ править ]

Внешние ссылки [ править ]

• Программа ежегодной конференции по приложениям компьютерной безопасности 2009 г.