Es barato para validar pero costoso calcular el algoritmo de hash

Question

Es barato para validar pero costoso calcular el algoritmo de hash

#1 de David Schwartz (11 votos)

8

Estoy buscando un algoritmo de hashing similar a bcrypt, excepto que me gustaría que la validación fuera extremadamente barata.

Como medida antispam, me gustaría exigir a mis clientes que gasten, por ejemplo, medio segundo de tiempo de cálculo, antes de que envíen información. Me gustaría asignarles información al hash y luego, en mi extremo, comprobar rápidamente que la información se haya copiado correctamente. Protegerme de un DoS utilizando algo como bcrypt no sería factible.

Como es una medida antispam, no estoy buscando la perfección, el algoritmo de hash puede ser débil.

¿Hay un nombre para tal algoritmo? ¿Qué podría usar?

hash spam

pregunta Sam Saffron 29.09.2011 - 14:09

fuente

1 respuesta

Lea otras preguntas en las etiquetas hash spam

Javascript y jQuery no están seguros a través de https ¿Es esta la forma de implementar CTR en un sistema que solo implementa CBC, CFB, CTS, ECB y OFB?

score 11 · Accepted Answer

Se llama algoritmo de "prueba de trabajo". La idea básica es forzar a la persona que llama a realizar un trabajo adicional después de crear el hash. Puedes usar cualquier algoritmo de hash. Aquí hay una forma simple:

El cliente calcula el hash de los datos. (Por ejemplo, es de 160 bits).
El cliente crea un bloque que contiene el hash y el resto de los datos, todos ceros. (Supongamos que el bloque es de 512 bits).
El cliente calcula el hash de este bloque.
Si este hash final está por debajo del objetivo, el cliente envía todo el bloque que acaba de hacer hash y está listo.
El cliente incrementa los datos en el bloque que no sea el hash y salta al paso 3.

Cuando el servidor obtiene el bloque, calcula el hash del bloque. Si el hash está por debajo del destino, el servidor acepta el bloque y lee el hash desde el principio del bloque. Si el hash está por encima del destino, el servidor lo rechaza.

Entonces, si el objetivo es 0fffffff ... el cliente normalmente tendrá que realizar el paso 3 (la operación de hash) 16 veces antes de obtener un hash final por debajo del objetivo. (Existe una posibilidad de 1 en 16 de que un hash dado, en hexadecimal, comience con un cero). Si es demasiado fácil, establezca el objetivo en 00fff ... y el cliente normalmente tendrá que hacer 256 bloques de hashes.

Puede forzar al cliente a hacer, en promedio, tantos hashes como desee. El número real de hashes que el cliente deberá realizar sigue una distribución de Poisson. El inconveniente es que siempre hay una posibilidad de que el cliente tenga mala suerte y tenga que hacer una gran cantidad de trabajo.

Si necesita evitar que el cliente "reutilice" el trabajo, puede hacer que el cliente le solicite un número de secuencia. El bloque luego contiene el hash, luego el número de secuencia, luego el nonce (la parte que el cliente incrementa). Luego, puede validar el número de secuencia, por lo que el cliente no puede reutilizar un bloque que hizo antes y no puede calcular previamente los bloques.

Si no te gusta esto, también puedes elegir dos primos aleatorios y enviar el producto de esos primos. Forzar al cliente a factorizar ese número. Acepta un hash por número factorizado. Por supuesto, puede hacer que los números primos sean tan grandes o tan pequeños como desee para controlar la cantidad de trabajo que el cliente necesita hacer.