En criptografía , Very Smooth Hash (VSH) es una función hash criptográfica demostrablemente segura inventada en 2005 por Scott Contini, Arjen Lenstra y Ron Steinfeld. [1] Probablemente segura significa que encontrar colisiones es tan difícil como algún problema matemático difícil conocido. A diferencia de otros hashes resistentes a colisiones demostrablemente seguros , VSH es eficiente y utilizable en la práctica. Asintóticamente , solo requiere una única multiplicación por log( n ) bits de mensaje y utiliza aritmética de tipo RSA. Por lo tanto, VSH puede ser útil en entornos integrados donde el espacio de código es limitado.
Se propusieron dos variantes principales de VSH. En una, encontrar una colisión es demostrablemente tan difícil como encontrar una raíz cuadrada modular no trivial de un número muy suave módulo n . La otra utiliza un módulo primo p (sin trampilla ) y su prueba de seguridad se basa en la dificultad de encontrar logaritmos discretos de números muy suaves módulo p . Ambas versiones tienen una eficiencia similar.
VSH no es adecuado como sustituto de un oráculo aleatorio , pero se puede utilizar para crear una función hash de puerta trampa aleatoria y demostrablemente segura. Esta función puede reemplazar la función de puerta trampa utilizada en el esquema de firma Cramer-Shoup , manteniendo su seguridad demostrable y acelerando el tiempo de verificación en aproximadamente un 50%.
Todas las funciones hash criptográficas que ahora [ ¿cuándo? ] se usan ampliamente no se basan en problemas matemáticos difíciles. Las pocas funciones que se construyen sobre problemas matemáticos difíciles se denominan demostrablemente seguras . Se sabe entonces que encontrar colisiones es tan difícil como resolver el problema matemático difícil. Para la versión básica de Very Smooth Hash, este problema difícil es encontrar raíces cuadradas modulares (VSSR) de ciertos números especiales (VSN). [1] Se supone que esto es tan difícil como factorizar números enteros .
Para constantes fijas c y n , un entero m es un número muy suave (VSN) si el factor primo más grande de m es como máximo log( n ) c .
Un entero b es un residuo cuadrático muy uniforme módulo n si el primo más grande en la factorización de b es como máximo log( n ) c y existe un entero x tal que b ≡ x 2 (mod n ) . Entonces se dice que el entero x es una raíz cuadrada modular de b .
Nos interesan únicamente las raíces cuadradas no triviales, aquellas en las que x 2 ≥ n . Si x 2 < n , entonces la raíz se puede calcular fácilmente utilizando algoritmos a partir de campos de característica 0, como el campo real . Por lo tanto, no son adecuadas en primitivas criptográficas.
La raíz cuadrada modular no trivial de números muy suaves (VSSR) es el siguiente problema: Sea n el producto de dos primos desconocidos de aproximadamente el mismo tamaño, sea k ≤ (log( n )) c , y sea ( p 1 , p 2 , p 3 ,…) = (2,3,5,…) la secuencia de primos. Dado n , encuentre un entero x coprimo con n tal que y al menos uno de e 0 ,…, e k sea impar.
El supuesto VSSR es que no existe un algoritmo polinomial probabilístico (en tiempo log( n ) ) que resuelva VSSR con una probabilidad no despreciable . Esto se considera un supuesto inútil en la práctica porque no indica para qué tamaño de módulos es difícil computacionalmente VSSR. En su lugar, se utiliza el supuesto computacional VSSR . Dice que se supone que resolver VSSR es tan difícil como factorizar un módulo de s bits difícil de factorizar , donde s es algo más pequeño que el tamaño de n .
Sean los parámetros fijos c = 5 y n = 31 .
Entonces m 1 = 35 = 5 · 7 es un Número Muy Suave con respecto a estos parámetros porque log(31) 5 ≈ 7.37 es mayor que todos los factores primos de m 1. Por otro lado, m 2 = 55 = 5 · 11 no es un VSN bajo estos parámetros.
El entero 9 es un residuo cuadrático muy uniforme módulo n porque es un número muy uniforme (bajo c , n ) y 3 2 ≡ 9 (mod n ) . Esta es una raíz cuadrada modular trivial, porque 9 < n y, por lo tanto, el módulo no interviene al elevar al cuadrado.
El entero es también un residuo cuadrático muy uniforme módulo . Todos los factores primos son menores que 7,37 y la raíz cuadrada modular es porque (mod ). Por lo tanto, se trata de una raíz no trivial. El problema de la VSSR consiste en encontrar dados y . Y suponemos que esto es tan difícil computacionalmente como factorizar .
El entero b = 15 es también un residuo cuadrático muy uniforme módulo n . Todos sus factores primos son menores que 7,37 y la raíz cuadrada modular es x = 20 , ya que 20 2 = 400 ≡ 15 (mod n ) . Por lo tanto, se trata de una raíz cuadrada no trivial. El problema de la VSSR consiste en hallar x dados b y n . Se cree que esto es tan difícil computacionalmente como factorizar n .
Sea n un compuesto RSA grande y sea ( p 1 , p 2 , p 3 ,…) = (2,3,5,…) la secuencia de primos. Sea k , la longitud del bloque, el entero más grande tal que . Sea m un mensaje de ℓ bits que se va a codificar y que consta de bits ( m 1 ,…, m ℓ ) y supongamos que ℓ < 2 k . Para calcular el hash de m :
La función del paso 5 se llama función de compresión.
Se han propuesto varias mejoras, aceleraciones y variantes más eficientes de VSH. [1] Ninguna de ellas cambia el concepto subyacente de la función. Estas mejoras se denominan:
El VSH-DL es una variante de logaritmo discreto de VSH que no tiene trampa ; su seguridad depende de la dificultad de encontrar logaritmos discretos módulo un primo p . [1]
El logaritmo discreto de números muy suaves (VSDL) es un problema en el que, dado un número muy suave, la tarea es encontrar su logaritmo discreto módulo algún número n .
Como en la sección anterior, p i denota el i ésimo primo. Sea además c una constante fija y p , q primos con p = 2 q + 1 y sea k ≤ (log p ) c . VSDL es el siguiente problema: dado p , encuentre enteros e 1 ,…, e k tales que con | e i | < q para i = 1, …, k y al menos uno de e 1 ,…, e k no sea cero.
El supuesto de VSDL es que no existe un algoritmo polinomial probabilístico (en tiempo log( p ) ) que resuelva VSDL con una probabilidad no despreciable . Existe una fuerte conexión entre la dificultad de VSDL y la dificultad de calcular logaritmos discretos módulo p , que recuerda, pero es algo más débil, a la conexión entre VSSR y la factorización de números enteros.
La única propiedad demostrada para VSH es la resistencia a colisiones fuertes . Esto no implica resistencia a preimagen u otras propiedades importantes de la función hash, y los autores afirman que "VSH no debería usarse para modelar oráculos aleatorios " y no puede sustituirse en construcciones que dependan de ellos ( firmas RSA , algunas MAC ). [1] VSH no debería considerarse una función hash de propósito general como se entiende habitualmente en ingeniería de seguridad .
VSH es multiplicativo: sean x , y y z tres cadenas de bits de igual longitud, donde z consta solo de cero bits y las cadenas satisfacen x AND y = z . Entonces H ( z ) H ( x OR y ) ≡ H ( x ) H ( y ) (mod n ) . Como resultado, VSH sucumbe a un ataque clásico de compensación de tiempo-memoria que se aplica a los hashes multiplicativos y aditivos.
Este hecho se puede utilizar para construir un ataque de preimagen contra VSH de ℓ bits que tiene una complejidad de 2 ℓ/2 en lugar de 2 ℓ como se esperaba.
VSH produce un hash muy largo (normalmente 1024 bits). No hay indicios de que un hash VSH truncado ofrezca una seguridad proporcional a la longitud del hash.
Existe un ataque de colisión parcial en VSH truncado a ℓ bits menos significativos. [2]
La complejidad de este ataque contra VSH es:
Esto probablemente [ ¿según quién? ] descarta la aplicabilidad de VSH en esquemas de firma digital que producen firmas más cortas que el resultado hash de VSH, como los esquemas de firma de curva elíptica.
