Hashcash - Hashcash

Hashcash es un sistema de prueba de trabajo que se utiliza para limitar el correo no deseado y los ataques de denegación de servicio , y más recientemente se ha hecho conocido por su uso en bitcoin (y otras criptomonedas ) como parte del algoritmo de minería. El Hashcash fue propuesto en 1997 por Adam Back y descrito de manera más formal en el artículo de Back de 2002 "Hashcash - Una contramedida de denegación de servicio".

Fondo

La idea "... requerir que un usuario calcule una función moderadamente difícil, pero no intratable ..." fue propuesta por Cynthia Dwork y Moni Naor en su artículo de 1992 "Precios a través del procesamiento o la lucha contra el correo basura".

Cómo funciona

Hashcash es un algoritmo de prueba de trabajo criptográfico basado en hash que requiere una cantidad seleccionable de trabajo para calcular, pero la prueba se puede verificar de manera eficiente. Para usos de correo electrónico, se agrega una codificación textual de un sello hashcash al encabezado de un correo electrónico para demostrar que el remitente ha gastado una cantidad modesta de tiempo de CPU calculando el sello antes de enviar el correo electrónico. En otras palabras, como el remitente ha tardado una cierta cantidad de tiempo en generar el sello y enviar el correo electrónico, es poco probable que sea un spammer. El receptor puede, a un costo computacional insignificante, verificar que el sello es válido. Sin embargo, la única forma conocida de encontrar un encabezado con las propiedades necesarias es la fuerza bruta , probando valores aleatorios hasta encontrar la respuesta; Aunque probar una cadena individual es fácil, las respuestas satisfactorias son lo suficientemente raras como para requerir un número sustancial de intentos para encontrar la respuesta.

La hipótesis es que los spammers, cuyo modelo de negocio se basa en su capacidad para enviar una gran cantidad de correos electrónicos con muy poco costo por mensaje, dejarán de ser rentables si hay un costo mínimo por cada spam que envían. Los receptores pueden verificar si un remitente hizo tal inversión y usar los resultados para ayudar a filtrar el correo electrónico.

Detalles técnicos

La línea del encabezado se parece a esto: 

X-Hashcash: 1:20:1303030600:anni@cypherspace.org::McMybZIhxKXu57jd:ckvi

El encabezado contiene:

  • ver : versión en formato Hashcash, 1 (que reemplaza a la versión 0).
  • bits : número de bits de "preimagen parcial" (cero) en el código hash.
  • fecha : la hora a la que se envió el mensaje, en el formato YYMMDD[hhmm[ss]].
  • recurso : Cadena de datos del recurso que se transmite, por ejemplo, una dirección IP o una dirección de correo electrónico.
  • ext : Extensión (opcional; ignorada en la versión 1).
  • rand : Cadena de caracteres aleatorios, codificada en formato base 64 .
  • contador : Contador binario, codificado en formato base 64.

El encabezado contiene la dirección de correo electrónico del destinatario, la fecha del mensaje y la información que prueba que se ha realizado el cálculo requerido. La presencia de la dirección de correo electrónico del destinatario requiere que se calcule un encabezado diferente para cada destinatario. La fecha permite al destinatario registrar los encabezados recibidos recientemente y asegurarse de que el encabezado sea exclusivo del mensaje de correo electrónico.

Lado del remitente

El remitente prepara un encabezado y agrega un valor de contador inicializado a un número aleatorio. Luego calcula el hash SHA-1 de 160 bits del encabezado. Si los primeros 20 bits (es decir, los 5 dígitos hexadecimales más significativos) del hash son todos ceros, entonces este es un encabezado aceptable. De lo contrario, el remitente incrementa el contador y vuelve a intentar el hash. Fuera de 2 160 posibles valores de hash, hay 2 140 valores hash que satisfacen este criterio. Por lo tanto, la posibilidad de seleccionar aleatoriamente un encabezado que tendrá 20 ceros como comienzo del hash es de 1 en 2 20 (aproximadamente 10 6 , o aproximadamente uno en un millón). El número de veces que el remitente debe intentar obtener un valor hash válido se modela mediante distribución geométrica . Por lo tanto, el remitente tendrá que probar en promedio 2 20 valores para encontrar un encabezado válido. Dadas estimaciones razonables del tiempo necesario para calcular el hash, esto tomaría alrededor de un segundo para encontrarlo. No se conoce ningún método más eficiente que este enfoque de fuerza bruta para encontrar un encabezado válido.

Un usuario normal en una PC de escritorio no se vería molesto de manera significativa por el tiempo de procesamiento requerido para generar la cadena Hashcash. Sin embargo, los spammers sufrirían significativamente debido a la gran cantidad de mensajes spam enviados por ellos.

Lado del destinatario

Técnicamente el sistema se implementa con los siguientes pasos:

  • La computadora del destinatario calcula el hash SHA-1 de 160 bits de toda la cadena (por ejemplo, ). Esto lleva aproximadamente dos microsegundos en una máquina de 1 GHz, mucho menos tiempo que el tiempo que tarda en recibirse el resto del correo electrónico. Si los primeros 20 bits no son todos cero, el hash no es válido. (Las versiones posteriores pueden requerir que más bits sean cero a medida que aumentan las velocidades de procesamiento de la máquina)."1:20:060408:anni@cypherspace.org::1QTjaYd7niiQA/sc:ePa"
  • La computadora del destinatario verifica la fecha en el encabezado (por ejemplo "060408", que representa la fecha 8 de abril de 2006). Si no está dentro de los dos días posteriores a la fecha actual, no es válido. (La ventana de dos días compensa la desviación del reloj y el tiempo de enrutamiento de la red entre diferentes sistemas).
  • La computadora del destinatario verifica si la dirección de correo electrónico en la cadena de control coincide con alguna de las direcciones de correo electrónico válidas registradas por el destinatario o si coincide con alguna de las listas de correo a las que está suscrito el destinatario. Si no se encuentra una coincidencia, la cadena hash no es válida.
  • La computadora del destinatario inserta la cadena hash en una base de datos. Si la cadena ya está en la base de datos (lo que indica que se está intentando reutilizar la cadena hash), no es válida.

Si la cadena hash pasa todas estas pruebas, se considera una cadena hash válida. Todas estas pruebas toman mucho menos tiempo y espacio en disco que recibir el contenido del cuerpo del correo electrónico.

Esfuerzo requerido

El tiempo necesario para calcular tal colisión hash es exponencial con el número de bits cero. Por lo tanto, se pueden agregar bits cero adicionales (duplicando la cantidad de tiempo necesario para calcular un hash con cada bit cero adicional) hasta que sea demasiado costoso para los spammers generar líneas de encabezado válidas.

Confirmar que el encabezado es válido es mucho más rápido y siempre toma la misma cantidad de tiempo, sin importar cuántos bits cero se requieran para un encabezado válido, ya que esto requiere solo una sola operación de hash.

Ventajas y desventajas

El sistema Hashcash tiene la ventaja sobre las propuestas de micropagos que se aplican al correo electrónico legítimo de que no se trata de dinero real. Ni el remitente ni el destinatario necesitan pagar, por lo que se evitan por completo los problemas administrativos relacionados con cualquier sistema de micropagos y los problemas morales relacionados con el cobro del correo electrónico.

Por otro lado, como Hashcash requiere que se gasten recursos computacionales potencialmente significativos en cada correo electrónico que se envía, es algo difícil ajustar la cantidad ideal de tiempo promedio que uno desea que los clientes dediquen a calcular un encabezado válido. Esto puede significar sacrificar la accesibilidad de los sistemas integrados de gama baja o, de lo contrario, correr el riesgo de que los hosts hostiles no sean desafiados lo suficiente como para proporcionar un filtro eficaz contra el spam.

Hashcash también es bastante sencillo de implementar en agentes de usuario de correo y filtros de spam. No se necesita un servidor central. Hashcash se puede implementar de forma incremental: el encabezado de Hashcash adicional se ignora cuando lo reciben clientes de correo que no lo entienden.

Un análisis plausible llegó a la conclusión de que solo es probable uno de los siguientes casos: o el correo electrónico que no sea spam se atascará debido a la falta de capacidad de procesamiento del remitente, o el correo electrónico no deseado seguirá llegando. Los ejemplos de cada uno incluyen, respectivamente, una topología de correo electrónico centralizada (como una lista de correo ), en la que algún servidor debe enviar una enorme cantidad de correos electrónicos legítimos , y redes de bots o granjas de clústeres con las que los spammers pueden aumentar enormemente su poder de procesamiento. .

Es posible que se aborden la mayoría de estos problemas. Por ejemplo, las botnets pueden caducar más rápido porque los usuarios notan la alta carga de la CPU y toman contramedidas, y los servidores de listas de correo pueden registrarse en listas blancas en los hosts de los suscriptores y, por lo tanto, liberarse de los desafíos del hashcash. Pero representan serios obstáculos para el despliegue de hashcash que aún no se han abordado.

Otro problema proyectado es que las computadoras continúan siendo más rápidas de acuerdo con la ley de Moore . Por tanto, la dificultad de los cálculos necesarios debe incrementarse con el tiempo. Sin embargo, se puede esperar que los países en desarrollo utilicen hardware más antiguo, lo que significa que les resultará cada vez más difícil participar en el sistema de correo electrónico. Esto también se aplica a las personas de bajos ingresos en los países desarrollados que no pueden pagar el hardware más reciente.

Al igual que hashcash, cryptocurrencies utilizan una función hash como su sistema de prueba de trabajo. El aumento de las criptomonedas ha creado una demanda de máquinas mineras basadas en ASIC . Aunque la mayoría de las criptomonedas usan la función hash SHA-256 , la misma tecnología ASIC podría usarse para crear solucionadores de hashcash que son tres órdenes de magnitud más rápidos que una CPU de consumo, reduciendo el obstáculo computacional para los spammers.

Aplicaciones

minería Bitcoin

A diferencia del hashcash en las aplicaciones de correo que depende de que los destinatarios establezcan manualmente una cantidad de trabajo destinada a disuadir a los remitentes malintencionados, la red de criptomonedas Bitcoin emplea un desafío de prueba de trabajo basado en hash diferente para permitir la minería competitiva de Bitcoin . Un minero de Bitcoin ejecuta un programa informático que recopila transacciones no confirmadas de los usuarios de la red. Juntos, estos pueden formar un "bloque" y obtener un pago para el minero, pero la red solo acepta un bloque si su hash cumple con el objetivo de dificultad de la red. Así, como en el hashcash, los mineros deben descubrir por fuerza bruta el "nonce" que, cuando se incluye en el bloque, da como resultado un hash aceptable.

A diferencia del hashcash, el objetivo de dificultad de Bitcoin no especifica un número mínimo de ceros iniciales en el hash. En cambio, el hash se interpreta como un número entero (muy grande) y este número debe ser menor que el número entero de destino. Esto es necesario porque la red Bitcoin debe ajustar periódicamente su nivel de dificultad para mantener un tiempo promedio de 10 minutos entre bloques sucesivos. Si solo se consideraran ceros a la izquierda, entonces la dificultad solo se podría duplicar o reducir a la mitad, lo que provocaría que el ajuste se sobrepasara o no se alcanzara en gran medida en respuesta a pequeños cambios en el tiempo de bloque promedio. Aún así, el número de ceros iniciales en el objetivo sirve como una buena aproximación de la dificultad actual. En enero de 2020, el bloque # 614525 tenía 74 ceros a la izquierda.

Filtros de spam

Hashcash se utiliza como una solución potencial para falsos positivos con sistemas automatizados de filtrado de spam, ya que los usuarios legítimos rara vez se verán molestos por el tiempo adicional que lleva extraer un sello. SpamAssassin ha podido comprobar si hay sellos Hashcash desde la versión 2.70, asignando una puntuación negativa (es decir, menos probable que sea spam) para los sellos Hashcash válidos no gastados. Sin embargo, aunque el complemento hashcash no está inicialmente activado de forma predeterminada, aún debe configurarse con una lista de patrones de dirección que deben coincidir con el campo de recursos Hashcash, por lo que en realidad no funciona de forma predeterminada.

Clientes de correo electrónico

El proyecto de software Penny Post en SourceForge implementa Hashcash en el cliente de correo electrónico Mozilla Thunderbird . El proyecto se llama así por la disponibilidad histórica de servicios de correo convencionales que le cuestan al remitente solo un centavo; consulte Penny Post para obtener información sobre dichos servicios de correo en la historia.

Matasellos de correo electrónico

Microsoft también diseñó e implementó una especificación abierta ahora obsoleta, similar pero incompatible con Hashcash, Email Postmark, como parte de su Iniciativa Coordinada de Reducción de Spam (CSRI). La variante de matasellos de correo electrónico de Microsoft de Hashcash se implementa en los componentes de la infraestructura de correo de Microsoft Exchange, Outlook y Hotmail. Las diferencias de formato entre Hashcash y el matasellos de correo electrónico de Microsoft es que el matasellos tiene un hash en el cuerpo además del destinatario, y usa un SHA-1 modificado como función hash y usa múltiples sub-rompecabezas para reducir la variación de la prueba de trabajo.

Blogs

Al igual que el correo electrónico, los blogs suelen ser víctimas del spam de comentarios . Algunos propietarios de blogs han utilizado scripts hashcash escritos en lenguaje JavaScript para ralentizar a los spammers de comentarios. Algunos scripts (como wp-hashcash) afirman implementar hashcash pero en cambio dependen de la ofuscación de JavaScript para forzar al cliente a generar una clave coincidente; Si bien esto requiere algo de potencia de procesamiento, no utiliza el algoritmo hashcash ni los sellos hashcash.

Propiedad intelectual

Hashcash no está patentado y la implementación de referencia y la mayoría de las otras implementaciones son software libre. Hashcash está incluido o disponible para muchas distribuciones de Linux .

RSA ha hecho declaraciones de IPR al IETF sobre rompecabezas de clientes en el contexto de un RFC que describe los rompecabezas de clientes (no hashcash). El RFC incluía hashcash en el título y hacía referencia a hashcash, pero el mecanismo descrito en él es un desafío interactivo de solución conocida que es más parecido a Client-Puzzles; hashcash no es interactivo y, por lo tanto, no tiene una solución conocida. En cualquier caso, la declaración de derechos de propiedad intelectual de RSA no se puede aplicar al hashcash porque el hashcash es anterior (marzo de 1997) a la publicación de los rompecabezas del cliente (febrero de 1999) y la solicitud de patente de los rompecabezas del cliente US7197639 (febrero de 2000).

Ver también

Notas

Referencias

  • Adam Back, "Hashcash - Una contramedida de denegación de servicio", informe técnico, agosto de 2002 (PDF) .
  • Ben Laurie y Richard Clayton, "'Prueba de trabajo' demuestra que no funciona", WEIS 04. (PDF) .
  • Dwork, C. y Naor, M. (1992) "Fijación de precios mediante el procesamiento o la lucha contra el correo basura", Crypto '92, págs. 139-147. (PDF)

enlaces externos