Asignación de recurso, prueba del trabajo, y consecuencias
por David MolnarTraducido por Paulo N. Lama
En enero del 2000, los empleados de los afamados sitios en internet como Yahoo! y eBay, recibieron con sorpresa como se caian sus servidores debido al problema de la asignación de los recursos del mismo. Miles de ordenadores apuntados en la Web dejaron inmediatamente de estar en linea con los servidores de esos sitios crackeados. La razón era por la libertad de abrir una nueva conexión de manera fácil, y totalmente automatizado, sin nada ni nadie pudiera estar controlando acerca de lo que pasaba entre estos ordenadores, lo que ocasionó la falla por agotamiento completo de los recursos del servidor.
Los incidentes con la falla del servidor, condujeron a dos investigadores de seguridad de datos del RSA a proponer un sistema de defensa contra este tipo de ataques[6], de manera que ya una vez comenzado el ataque pero antes de que el servidor falle totalmente, el servidor forzaría a sus clientes a realizar una prueba del trabajo , el cual es un protocolo que garantiza al servidor de que el cliente ha pasado cierta cantidad de operaciones en una tarea determinada. Haciendolo más costoso para que el cliente abra una nueva conexión, y tambien costoso para los atacantes. Asi que cuando un ordenador intenta agotar recursos del servidor, no puede computar las "prueba del trabajo" más rápidamente que el servidor , pues este ultimo puede tomar otras rutas para las nuevas conexiones.
Las pruebas del trabajo son un ejemplo de cómo la criptografía se puede aplicar a la seguridad. La criptografía se utiliza para especificar una "prueba del trabajo" y se puede encontrar buenos ejemplos de prueba del trabajo para reducir la eficacia de la suspención o negación del servicio, causada por los ataques.
Este método de usar la prueba del trabajo sirve para crear una especie de "costo" para las operaciones y que alcanza más allá de una sola aplicación. Un mundo con extensas revisiones de trabajo es un mundo con posibilidades intrigantes. Entre estas posibilidades está una alianza entre las pruebas del trabajo y los servicios de "venta de ciclos de reposición“. Otra perspectiva más preocupante es las pruebas del trabajo hacen participar involuntariamente al cliente en ciertas operaciones de cómputo más grandes, tal como la fuerza-bruta de una clave criptográfica. Cada una de estas posibilidades conduce a una serie de preguntas relacionadas con la seguridad.
La asignación de recursos es un viejo problema que posee diversos matices y muchos tipos de configuraciones. A menudo, uno o más recursos son limitados y deben estar asignados a una o más partes.
Asi como la Economía se puede considerar como una ciencia que procura maximizar los beneficios en la búsqueda de soluciones al problema en la asignación de los recursos escasos. De hecho, hay una lección en Economía, conocida como La tragedia de los campos comunes [4], que podemos aplicarlo directamente a la asignación de recursos en el Internet.
Según la historia, había un área en las praderas, llamado los campos comunes" que no era poseído por nadie y estaba totalmente libre para que todos lo utilicen. Cada día, los granjeros y pastores de las aldeas circundantes venían con su ganado a pastar en los campos comunes. Debido a que no costaba nada que los granjeros pasten su ganado ahi, y cada uno de ellos pastaría tanto como deseaban. Con el pasar de los dias, cada granjero notó que cada vez la hierba se convertía más y más debil, como evidencia del sobrepastoreo. A veces, un granjero consideraría pastar cada vez menos sus reses en los campos comunes, entonces echó una mirada a la manada vecina. Cómo podría él parar pastar su ganado cuando él no tenía ninguna certeza de que su vecino lo haría igual? Esto continuó hasta que un día no quedaba más hierba y cada uno de los animales comenzó a morir de hambre.
Qué sucedió aquí? Aunque los granjeros no pagaron nada por utilizar los campos comunes, cada granjero sobre-explotó un recurso precioso: la hierba de los campos comunes. Sin embargo, el "costo" de usar este recurso fue compartido entre todos los granjeros. Algunos granjeros más racionales, reconocieron este costo, pero continuaron pastando su ganado porque no había garantía que los otros granjeros seguirían el juego.
La situación empeoró con los granjeros de mala fe. Por ejemplo, si uno de los granjeros comenzó a destruir los campos de hierba, frecuentados a menudo por sus vecinos, y nada se podría hacer para pararlo. La hierba no es propiedad de nadie, y por lo tanto el granjero no incurre en un costo por el hecho de usarlo. De manera análoga, los recursos en línea son compartidos por todos y se pueden perder por los usuarios malévolos.
Un método para manejar recursos en línea consiste en crear un "costo" a los clientes por usar los recursos. Introduciendo un coste, su mal uso es disuadido y la tragedia como el de los campos comunes se evita.
Una manera directa de ponerlo en práctica podría ser simplemente poner un coste monetario para cada conexión o recurso ofrecido. El dinero digital de "Micropayment" se proyecta a favor de este acercamiento. Sin embargo, al Internet le falta actualmente un esquema estructural estable y extenso de pago, con la excepción de las tarjetas de crédito; que estas tambien requieren, desafortunadamente, de infraestructura significativa. Y más encima los consumidores tienden a tener aversion para pagar por acceder y utilizar (pay-per-use access) [3].
Un acercamiento alternativo para agregar un coste, seria primero precisado por Dwork y Naor, que pide que un cliente expenda una cantidad especificada de tiempo del cómputo para utilizar un servicio [2]. El cliente produce una prueba del trabajo que es un pequeno certificado que convalida lo que pasó en su cuenta y con su tiempo en un dificil problema de cómputo. Sin una prueba del trabajo, el cliente no puede recibir el servicio. Asumiendo que limitando a un cliente su potencial de cómputo, él no puede crear suficientes pruebas del trabajo como para inundar el servidor.
Una de las prueba más conocidas del trabajo es el hashcash (hash=picadillo, cash=dinero) que fue desarrollado originalmente para la prevención de Spams o cartas del correo electrónico no deseados [1]. El Spam es un problema, porque el que lo origina puede enviar muchos E-mails al mismo tiempo con poco o nada de costo. Despues surgió la idea de hacer un " coste " o " franqueo " para el E-mail, que sería denominado en " hashcash.". El Hashcash es creado para usar efectivamente su tiempo en el ordenador en sus dificiles rutinas de cómputo. Por ejemplo, uno puede utilizar hashcash para poner un " franqueo " a cada picadillo de E-mail. La cantidad sería bastante importante que el " coste " no retrasaría al usuario que envía unos pocos E-mails al día, pero sería prohibitivo para un hacedor de spams que envía miles o millones de E-mails. El duro problema de cómputo es que el hashcash está basado en encontrar las colisiones parciales en una función colisión-resistente unidireccional del hash o picadillo, es decir las que chocan parcialmente.
Una cierta explicación está en orden aquí. La función del hash o
picadillo es cualquier función que tome una cadena cualquier
longitud y vuelve cadenas de una longitud
fija. En símbolos, una función h del hash o picadillo se denota
h : {0,1}^* --> {0,1}^k
para una cierta constante fija k que
determina la longitud del resultado o salida. En la práctica, los ejemplos de
las funciones del picadillo incluyen el MD5 de la seguridad de datos del RSA,
que tiene una salida de 128 bits, y el diseño del NSA del algoritmo Secure Hash
Algorithm SHA-1 con 160 bits. Una
colisión en la función del picadillo existe cuando hay
dos elementos x
y x'
tales que h(x) =
h(x') Si la función del picadillo es una función
colisión-resistente después es dificil encontrar cualesquiera x y x' que
choque, es decir. h(x)
= h(x'). Una colisión parcial es un par y y y' tal que
h(y)
concuerda con h(y')
en cierto número de bits consecutivos.
En palabras, si H()
es una función colisión-resistente del picadillo, entonces dada H(52) = 10001
es más dificil de encontrar cualquier otra cosa en las cuales puede ser
incorporado a H()
para dar 10001
como resultado o salida. Además, es dificil encontrar dos
entradas de información H() a las cuales tenga la
misma salida, incluso si esa salida se permite ser cualquier cosa. Una colisión
parcial puede ser algo como H(52) = 10001 y H(1923) = 11101
que concuerdan en dos bits consecutivos que sumados dan 5.
Qué tan difícil puede ser? Idealmente, la función del picadillo debe parecer
a una función al azar en el que todas las salidas se eligen al azar. La
teoría de las probabilidades nos dice que encontrando una colisión para un
punto x
y h(x)
debe tener un promedio de 2^k evaluaciones de la función. Cuando el
blanco de una colisión no está en la mira, sino que por el contrario, y no hay
riesgo de colisión para x y x', solamente las 2^(k/2)
evaluaciones se requieren. Para una colisión parcial con n bits en
común, el trabajo correspondiente para encontrar cualquiera de los dos valores y y y'es 2^(n/2)
evaluaciones de la función.
Ahora un servidor puede especificar una función determinada del picadillo, como el SHA-1 del gobierno estadounidense, por un valor n determinado, y un cierto número de colisiones parciales del picadillo que se desea considerar. Éste es el costo de usar un recurso. Por ejemplo, un servidor de e-mail (mail server) puede decir que desea considerar 4 colisiones parciales con 64 bits en común cada uno, que tomará 4 * 2^(64/2) = 2^(32) operaciones. El coste estará dada según lo que contemplan estos parámetros, que estiman cuánto potencial de cómputo tiene un cliente, o si el servidor puede establecer un "precio justo" para enviar el correo.
Por ejemplo, suponga que un mail server decida que desea considerar una colisión parcial 64-bit asociada a cada E-mail antes de aceptar el mensaje para la entrega. Esto significa que para enviar un mensaje, un cliente tendrá que realizar un promedio 2^32 operaciones de la función del picadillo SHA-1 para encontrar esas colisiones parciales. Para la biblioteca cryptografica BeeCrypt, que tiene un Pentium3 corriendo a 450MHz con Windows 98 puede hacer la funcion picadillo a 19,5 MB/sec [11], y como el SHA-1 corre en bloques de 512-bit [9], siendo que 1 MB/sec equivale a 2 * 2^20 operaciones por Segundo; por lo tanto, la ejecución de las 2^32 operaciones tomará cerca de 105 segundos para encontrar una colisión parcial. Al contrario, si con el mismo ordenador, el hacedor de spams desea enviar 100.000 mensajes al mismo tiempo, tendria que esperar 105 * 100.000 segundos, es decir cerca de 121 días.
Podría un protocolo de la “prueba del trabajo” haber detenido el ataque contra la negación distribuida del servicio Yahoo? Lamentablemente, la respuesta es probablemente no. Aunque un servidor tiene que hacer relativamente poco trabajo para verificar cada prueba del trabajo, todavía debe pasar un cierto tiempo para verificar cada una de las pruebas de trabajo de cada cliente. Una vez que muchos clientes se conecten simultaneamente, el tiempo de verificar cada una de las prueba del trabajo pueden agotar los recursos del computador principal. Un adversario que monta un ataque contra la negación distribuida del servicio, deberá tener simplemente más máquinas, especialmente con cantidades grandes de anchura de banda. No obstante , gracias a la ventaja del tiempo y con las prueba del trabajo como evidencia, pueden dar a la máquina un cierto aire de alivio, mientras sus propietarios buscan al adversario.
Qué viene después de hashcash? Cuáles son las otras clases de prueba del trabajo? Una definición formal puede ser hecha, como una explícita declaración de lo que "debería tener" toda prueba del trabajo. De hecho, Jakobsson y Juels han hecho apenas eso [5].
La función del hashcash en la prueba del trabajo tiene una desventaja. El cómputo usado para crear el hashcash es literalmente botado y se pierde, en el sentido que no hace ningún trabajo útil más allá de hacer más hashcash. Sería agradable si este cómputo hiciera algo útil mientras antes de botar ese precioso tiempo del cliente.
Jakobsson y Juels produjeron no sólo una definición formal de la prueba del trabajo, sino que volcaron su atención a este asunto de cómo "reutilizar el cómputo" también. Desarrollaron un protocolo de ejemplo que utiliza la prueba del trabajo de un cliente para ayudar a un servidor a participar en un esquema del dinero digital, desarrollada por Rivest y Shamir, llamado MicroMint [8]. Además, definieron la noción "de los protocolos del pudín del pan" Estos protocolos reutilizan el cómputo añejo que habría sido perdido de otra manera [5].
Esta sección y los siguientes son de naturaleza especulativos, delineando las dos posibles futuras aplicaciones para las prueba del trabajo.
En la columna anterior, titulada " El proyecto de Seti@Hogar " observé la existencia de lanzamientos como centrata.com que se dedican a la venta de ciclos de reposición de muchos clientes [7]. Las prueba del trabajo ofrecen una manera fácil de reclutar clientes. Uno puede preveer fácilmente una prueba del trabajo que pide que un cliente realice un cómputo en una unidad distribuida de trabajo. Imagínese si en Yahoo! los clientes que se conecten requieran realizar una unidad del trabajo antes de cada conexión.
Los jóvenes Adán y Moti Yung definieron la "kleptografía" como el "arte de usar la criptografía para crackear y robar la información". Como ejemplo, mostraron cómo en un sistema criptográfico podrían filtrarse los bits de su clave secreta de una manera que sería imperceptible por el usuario del sistema. Solamente el adversario podría ver los bits "escapados" y así robar la clave. Es en esta configuración, en donde las cosas con valor están siendo robados, porque la posesión de una clave secreta permite la lectura de todos los mensajes cifrados con esa clave [12].
En un mundo donde muchos clientes se conectan con muchos servidores, los ciclos de reposición del cómputo se convierten en disponibles, venables, y por lo tanto como objeto de valor. Por lo tanto, la "kleptografía distribuida" en esta configuración implicaría, de hecho, robar los cómputos de reposición.
Este problema existe ya? Después de todo, la mayoría de las versiones de Java, mientras ponen más límites estrictos en el uso del disco y de la red de un applet, pero no limitan explícitamente el tiempo de la CPU de un applet. Hoy, sin embargo, si un applet utiliza demásiado tiempo, es probable que sea destruido por el usuario porque los applet no estan hechos para perder tiempo. Un mundo con ubicuas prueba del trabajo es un mundo en el cual los clientes están acostumbrados a perder tiempo. Combinado con un mundo en el cual las prueba del trabajo son utilizadas por los servicios que venden ciclos de reposición, esto haría de los servidores un objetivo tentador para los virus que cambian los requerimientos de las pruebas del trabajo. Además, uno puede postular la existencia de protocolos con "pruebas subliminales del trabajo", es decir las pruebas del trabajo que aparecen al computar en los problemás más dificiles, en vez de los otros diferentes problemás. En efecto, puede ser ocultar parte de una búsqueda de la fuerza-bruta en clave criptográfica en una unidad de trabajo de SETI@Hogar?
Un caso posible de "kleptografía distribuida" fue descrito por Twyman. El adversario utiliza un virus o un Java applet para robar tiempo en muchos ordenadores y para aplicarlo para crackear una clave criptográfica [10].
Las prueba del trabajo son una idea criptográfica intrigante con aplicaciones concretas de la seguridad. Primero propuso tratar del Spamming y la negación de los ataques del servicio, prueba del trabajo está encontrando aplicaciones en lugares el sorprender. La formalización de las prueba del trabajo, combinadas con su importancia a los problemás de la asignación de recurso, les está haciendo una tecnología para permanecer encima de.
El autor agradece a Roger Dingledine y Michael Freedman por las discusiones aportadas sobre este asunto. El artículo no sería posible sin la ayuda de los revisores anónimos y los editores de Crossroads.
David Molnar (mailto:dmolnar@hcs.harvard.edu) comenzó a usar el PGP en 1993. Él esta muy interesado (obsesionado?) en indagar acerca del "porqué y cómo funcionan" y ha estado estudiando la criptografía desde entonces. Ahora es estudiante en la universidad de Harvard, y continúa con gran interes en asuntos de seguridad, atendiendo cursos, leyendo grupos de discusión, y seminaries; atendiende DEF CON en su ciudad natal de Las Vegas. David es un miembro del ACM Estudiantil y un miembro de la Asociación Internacional para la Investigación Criptografica.
Last Modified:
Location: www.acm.org/crossroads/espanol/xrds7-3/onpatrol_marzo2001.html