Protocolo de rompecabezas de la visita guiada

El protocolo Guided Tour Puzzle (GTP) es un protocolo criptográfico para mitigar los ataques de denegación de servicio en la capa de aplicación . Su objetivo es superar la deficiencia de los protocolos de rompecabezas basados ​​en computación , en los que se requiere que los clientes calculen rompecabezas que requieren un uso intensivo de la CPU o de la memoria, lo que favorece a los clientes con abundantes recursos computacionales. El protocolo Guided Tour Puzzle puede considerarse una forma de protocolo de prueba de trabajo (POW).

Descripción general

Los pasos del protocolo de rompecabezas de visitas guiadas son similares a los del Protocolo de rompecabezas de clientes . Todos los clientes deben completar un rompecabezas de visitas guiadas antes de recibir servicio del servidor , si el servidor sospecha que actualmente está bajo un ataque de denegación de servicio o su carga excede un umbral predefinido. En pocas palabras, un rompecabezas de visitas guiadas es un recorrido que debe completarse realizando múltiples viajes de ida y vuelta a un conjunto de nodos especiales, llamados guías turísticos , en un orden secuencial. Se llama visita guiada porque el orden en el que se visitan los guías turísticos es desconocido para el cliente, y cada guía turístico tiene que dirigir al cliente hacia el siguiente guía turístico para que el cliente complete el recorrido en el orden correcto. Un solo guía turístico puede aparecer varias veces en un recorrido, por lo que el término parada se usa para denotar una sola aparición de un guía turístico en un recorrido. Un cliente sabe qué guía turístico está en la siguiente parada, solo después de completar su visita a la parada actual.

Resolver un rompecabezas de una visita guiada equivale básicamente a completar una visita guiada en el orden correcto. A partir de la primera parada, el cliente se pone en contacto con cada parada y recibe una respuesta. Cada respuesta contiene un token único. El token del mensaje de respuesta de la parada actual se utiliza para calcular la dirección del guía turístico de la siguiente parada. La dirección del guía turístico de la primera parada se calcula utilizando el token contenido en el primer mensaje de respuesta del servidor que informa al cliente del inicio de un proceso de rompecabezas. ^{[ cita requerida ]}

El cliente debe enviar el token recibido del guía turístico de la parada actual al guía turístico de la siguiente parada, que lo utilizará como entrada para su función de cálculo de tokens. El token recibido del guía turístico de la última parada más el token del mensaje de rompecabezas del servidor se envían al servidor como prueba de finalización de un recorrido. El servidor puede validar de manera eficiente estos dos tokens y otorgar el servicio al cliente solo después de probar su validez. ^{[ cita requerida ]}

Pasos del protocolo

Ejemplo de un rompecabezas de visita guiada cuando el número de guías turísticos es 2 y la duración de la visita es 5. El orden de la visita es: G1 -> G0 -> G1 -> G1 -> G0.

Antes de que pueda comenzar el rompecabezas de la visita guiada, se deben configurar los guías turísticos en el sistema, donde . Mientras tanto, el servidor establece un secreto compartido con cada guía turístico mediante un canal seguro, donde . El servidor mantiene un secreto de corta duración para calcular el primer valor hash que se devuelve al cliente como parte de un mensaje de rompecabezas. Un mensaje de rompecabezas también contiene la duración del recorrido , que se utiliza para controlar la dificultad de un rompecabezas de visita guiada. La figura muestra un ejemplo de una visita guiada cuando y . ${\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}$

A continuación se explican los detalles de cada paso del protocolo del rompecabezas de la visita guiada. ^[1]

• Solicitud de servicio : un cliente envía una solicitud de servicio al servidor. Si la carga del servidor es normal, la solicitud del cliente se atiende de manera habitual; si el servidor está sobrecargado, se procede al paso inicial de generación del rompecabezas . ${\displaystyle x}$
• Generación inicial del rompecabezas : el servidor responde al cliente con un mensaje de rompecabezas que le informa que debe completar una visita guiada. El mensaje de rompecabezas contiene la duración de la visita y un valor hash . El servidor realiza el cálculo utilizando la siguiente fórmula: ${\displaystyle x}$ ${\displaystyle L}$ ${\displaystyle h_{0}}$ ${\displaystyle h_{0}}$

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

donde, significa concatenación, es la dirección (o cualquier valor único) del cliente , es una marca de tiempo aproximada y es una función hash criptográfica como SHA-1 . ${\displaystyle ||}$ ${\displaystyle A_{x}}$ ${\displaystyle x}$ ${\displaystyle ts}$ ${\displaystyle hash}$

• Resolución de problemas : un cliente calcula el índice del guía turístico en la parada -ésima de su recorrido utilizando la siguiente fórmula: ${\displaystyle l}$

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

donde, . Cuando un cliente se pone en contacto con él , un guía turístico calcula un valor hash ( ) utilizando la fórmula: ${\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})}$

donde, significa la -ésima parada del tour del cliente, es la clave compartida entre el guía turístico y el servidor. Después de que el cliente recibe el mensaje de respuesta del servidor, comienza un tour guiado calculando el índice del primer guía turístico usando la fórmula para . Luego, el cliente envía un conjunto de valores ( , , ) al guía turístico , donde el segundo valor indica en qué parada del tour se encuentra actualmente el cliente. Como respuesta, el cliente recibe un valor hash del guía turístico , donde se calcula usando la fórmula para . El cliente repite este proceso más veces y se comunica con los guías turísticos . El mensaje de respuesta del guía turístico de la última parada contiene el último valor hash , y el cliente envía ( ) al servidor como la respuesta del rompecabezas. ${\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}}$

• Verificación de acertijos : cuando el servidor recibe una solicitud del cliente con una respuesta de acertijo ( , ) adjunta, primero verifica si es igual a la que calculó utilizando la fórmula para . Si es así, el servidor realiza el cálculo utilizando repetidamente la fórmula para , y verifica que sea igual a . Si ambos valores hash son válidos, el servidor asigna recursos para procesar la solicitud del cliente. Dado que el servidor conoce las claves compartidas , puede calcular la cadena de hashes sin contactar a ningún guía turístico. Se requiere una sincronización de tiempo flexible entre el servidor y los guías turísticos para calcular el mismo valor hash en el servidor y los guías turísticos. ${\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}}$

Comparación con otros protocolos de rompecabezas

Los protocolos de resolución de problemas computacionales limitados por la CPU, como el Protocolo de resolución de problemas de cliente , pueden mitigar el efecto de un ataque de denegación de servicio, porque cuanto más quiera un atacante sobrecargar al servidor, más problemas computacionales tendrá que resolver y más deberá utilizar sus propios recursos computacionales. Los clientes con una gran capacidad computacional pueden resolver problemas a un ritmo mucho mayor que los clientes incapaces y pueden ocupar indeseablemente la mayoría de los recursos del servidor. ^{[1] [2] [3] [4]}

Otra deficiencia crucial de los protocolos de rompecabezas computacionales es que todos los clientes, incluidos todos los clientes legítimos, deben realizar cálculos que consumen muchos recursos de la CPU y que no contribuyen a ningún servicio o aplicación significativos.

El protocolo Guided Tour Puzzle impone un retraso a los clientes a través de retrasos de ida y vuelta , de modo que las solicitudes de los clientes lleguen a una velocidad que el servidor pueda mantener. La ventaja de utilizar retrasos de ida y vuelta, en contraposición a problemas computacionales complejos, es que el retraso de ida y vuelta de un paquete pequeño está determinado principalmente por los retrasos de procesamiento , los retrasos de puesta en cola y los retrasos de propagación en los enrutadores intermedios , por lo que está fuera del control de los hosts finales (clientes). Como tal, incluso un atacante con abundantes recursos computacionales no puede priorizarse sobre clientes legítimos mal provistos. ^{[ cita requerida ]}

Además, en el protocolo de rompecabezas de visitas guiadas, el cálculo requerido para el cliente es trivial. Dado que la longitud de una visita guiada suele ser un número pequeño del orden de decenas o menos, la sobrecarga de ancho de banda para completar una visita guiada también es trivial. Como resultado, los clientes no tienen que realizar cálculos pesados ​​(que suelen requerir los protocolos de rompecabezas limitados por la CPU o la memoria). ^{[ cita requerida ]}

Véase también

• Sistema de prueba de trabajo
• Protocolo de Puzzle de Cliente
• CAPTCHA

Referencias

1. Mehmud Abliz y Taieb Znati. Un rompecabezas de recorrido guiado para la prevención de denegación de servicio. En Actas de la Conferencia Anual de Aplicaciones de Seguridad Informática (ACSAC) 2009 , páginas 279-288, Honolulu, HI, diciembre de 2009.
2. "Los peligros de la ciberseguridad". Archivado desde el original el 21 de agosto de 2016 . Consultado el 2 de agosto de 2016 .
3. Martin Abadi, Mike Burrows, Mark Manasse y Ted Wobber. Funciones moderadamente difíciles y limitadas por la memoria. En Proceedings of NDSS 2003 , páginas 25-39, 2003.
4. Cynthia Dwork, Andrew Goldberg y Moni Naor. Sobre las funciones vinculadas a la memoria para combatir el spam. En Proceedings of CRYPTO 2003 , páginas 426-444, 2003.

Enlaces externos

• Programa de la Conferencia Anual sobre Aplicaciones de Seguridad Informática 2009