Hash muy suave

En criptografía , Very Smooth Hash (VSH) es una función hash criptográfica de seguridad demostrable , inventada en 2005 por Scott Contini, Arjen Lenstra y Ron Steinfeld. ^[¹^] La seguridad demostrable implica que encontrar colisiones es tan difícil como resolver algún problema matemático complejo conocido. A diferencia de otras funciones hash resistentes a colisiones de seguridad demostrable , VSH es eficiente y práctica. Asintóticamente , solo requiere una única multiplicación por $log($ $n$ $)$ bits del mensaje y utiliza aritmética de tipo RSA. Por lo tanto, VSH puede ser útil en entornos embebidos 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 puerta trasera ), 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 puede utilizarse para construir una función hash aleatoria con puerta trasera de seguridad demostrable . Esta función puede reemplazar la función de puerta trasera utilizada en el esquema de firma Cramer-Shoup , manteniendo su seguridad demostrable y acelerando el tiempo de verificación en aproximadamente un 50 %.

VSN y VSSR

Todas las funciones hash criptográficas que se utilizan ampliamente ahora no se basan en problemas matemáticos difíciles. Aquellas pocas funciones que se construyen sobre problemas matemáticos difíciles se denominan demostrablemente seguras . Encontrar colisiones se considera entonces 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 consiste en encontrar raíces cuadradas modulares (VSSR) de ciertos números especiales (VSN). ^[¹^] Se supone que esto es tan difícil como factorizar 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 suave 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 \equiv x² (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 donde $x²$ $\geq n .$ Si $x²$ $<$ $n$ , la raíz se puede calcular fácilmente utilizando algoritmos de campos de característica 0, como el campo real . Por lo tanto, no son adecuadas para primitivas criptográficas $.$

El problema de la raíz cuadrada modular no trivial de números muy suaves (VSSR) es el siguiente: Sea $n$ el producto de dos primos desconocidos de tamaño aproximadamente igual, sea $k \leq (log(n)) c$ , y sea $(p 1, p 2, p 3, \dots) = (2,3,5, \dots)$ la secuencia de primos. Dado $n$ , encontrar un entero $x$ coprimo con $n$ tal que $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}{\pmod {n}}$ y al menos uno de $e 0, \dots, e k$ es impar.

La suposición VSSR es que no existe ningún algoritmo de tiempo polinomial probabilístico (en $log(n)$ ) que resuelva VSSR con una probabilidad no despreciable . Esta suposición se considera inútil en la práctica porque no indica para qué tamaño de módulos VSSR es computacionalmente difícil. En su lugar, se utiliza la suposición computacional VSSR . Esta establece 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 menor que el tamaño de $n$ .

Ejemplos de VSN y VSSR

Sea fijos los parámetros como $c = 5$ y $n = 31$ .

Entonces, $m 1 = 35 = 5 \cdot 7$ es un número muy suave con respecto a estos parámetros porque $log(31) 5 \approx 7,37$ es mayor que todos los factores primos de $m 1.$ Por otro lado, $m 2 = 55 = 5 \cdot 11$ no es un número muy suave bajo estos parámetros.

El entero $9$ es un residuo cuadrático muy suave módulo $n$ porque es un número muy suave (bajo $c, n$ ), y $3² \equiv 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 $b_{2}=15$ También es un residuo cuadrático muy suave módulo $n$ . Todos los factores primos son menores que 7.37 y la raíz cuadrada modular es $x_{2}=20$ desde $20^{2}=400\equiv 15$ (mod $n$ ). Por lo tanto, esta es una raíz no trivial. El problema VSSR consiste en encontrar $x_{2}$ dado $b_{2}$ y $n$ . Y suponemos que esto es computacionalmente tan difícil como factorizar $n$ .

El entero $b = 15$ también es un residuo cuadrático muy suave módulo $n$ . Todos sus factores primos son menores que 7,37, y la raíz cuadrada modular es $x = 20$ , ya que $20² = 400 \equiv 15 (mod n) . Por lo tanto,$ se trata de una raíz cuadrada no trivial. El problema VSSR consiste en hallar $x$ dados $b$ y $n$ . Se cree que esto es computacionalmente tan difícil como factorizar $n$ .

Algoritmo VSH, versiones básicas

Sea $n$ un compuesto RSA grande y sea $(p 1, p 2, p 3, \dots) = (2,3,5, \dots)$ la secuencia de primos. Sea $k$ , la longitud del bloque, el entero más grande tal que $\textstyle \prod _{i=1}^{k}p_{i}<n$ Sea $m$ un mensaje de $ℓ bits que se va a hashear$ $, compuesto por$ $los$ $bits (m₁, ..., mℓ)$ y supongamos que $ℓ < 2k .$ Para calcular el hash de $m$ :

Establecer $x 0 = 1$ .
Sea $L$ , el entero más pequeño mayor o igual que $ℓ / k$ , el número de bloques.
Sea $m i = 0$ para $ℓ < i < Lk$ (relleno).
Dejar $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ donde $ℓ i \in {0,1}$ es la representación binaria de la longitud del mensaje $ℓ$ y definimos $m Lk + i = ℓ i$ para $1 \leq i \leq k$ .
Para $j = 0, 1, \dots, L$ sucesivamente, calcule $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$
Devuelve $x L +1$ .

La función del paso 5 se denomina función de compresión.

Propiedades de VSH

No es necesario conocer de antemano la longitud del mensaje.
Encontrar una colisión en VSH es tan difícil como resolver VSSR. Por lo tanto, VSH es (fuertemente) resistente a colisiones , lo que también implica resistencia a la segunda preimagen. No se ha demostrado que VSH sea resistente a la preimagen.
La función de compresión no es resistente a colisiones. Sin embargo, la función hash VSH sí lo es, según la suposición VSSR. Una versión modificada de VSH, denominada VSH*, utiliza una función de compresión resistente a colisiones y es aproximadamente cinco veces más rápida al aplicar hash a mensajes cortos.
Dado que la longitud de salida de VSH es igual a la longitud de un módulo RSA seguro, VSH parece bastante adecuado en la práctica para construir firmas RSA de tipo "hash-then-sign" para mensajes de longitud arbitraria. Sin embargo, dicha firma debe diseñarse cuidadosamente para garantizar su seguridad. El enfoque ingenuo podría ser fácilmente vulnerado mediante un ataque de texto plano elegido .
El coste de cada iteración es menor que el coste de 3 multiplicaciones modulares. La versión básica de VSH requiere en total una multiplicación por cada $Ω (log(n) / log(log(n)))$ bits de mensaje.

Variantes de VSH

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:

Elevar VSH al cubo (en lugar de al cuadrado)
VSH con mayor número de primos pequeños
VSH con productos de números primos precalculados
VSH rápido
VSH rápido con mayor longitud de bloque

Variantes VSDL y VSH-DL

El VSH-DL es una variante de logaritmo discreto del VSH que no tiene puerta trasera ; 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 consiste en encontrar su logaritmo discreto módulo algún número $n$ .

Como en la sección anterior, $p i$ denota el $i$ -ésimo primo. Además, sea $c$ una constante fija y $p, q$ primos con $p = 2 q + 1$ y sea $k \leq (log p) c$ . VSDL es el siguiente problema: dado $p$ , encontrar enteros $e 1, \dots, e k$ tales que $2^{e_{1}}\equiv \prod _{i=2}^{k}p_{i}^{e_{i}}{\pmod {p}}$ con $| e i | < q$ para $i = 1, \dots, k$ y al menos uno de $e 1, \dots, e k$ es distinto de cero.

La suposición de VSDL es que no existe ningún algoritmo probabilístico de tiempo polinomial (en $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, aunque es algo más débil, a la conexión entre VSSR y la factorización de enteros.

Seguridad de VSH

La fuerte resistencia a colisiones es la única propiedad demostrada para VSH. Esto no implica resistencia a preimágenes ni otras propiedades importantes de la función hash, y los autores afirman que "VSH no debe usarse para modelar oráculos aleatorios " y no puede sustituirse en construcciones que dependen de ellos ( firmas RSA , algunos MAC ). ^{[ 1 ]} VSH no debe considerarse una función hash de propósito general como se entiende habitualmente en ingeniería de seguridad .

Propiedad multiplicativa

VSH es multiplicativo: Sean $x$ , $y$ y $z$ tres cadenas de bits de igual longitud, donde $z$ consta únicamente de bits cero y las cadenas satisfacen $x AND y = z$ . Entonces $H (z) H (x OR y) \equiv H (x) H (y) (mod n)$ . Como resultado, VSH sucumbe a un ataque clásico de compensación tiempo-memoria que se aplica a las funciones hash multiplicativas y aditivas.

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.

Ataque contra la versión truncada

VSH genera un hash muy largo (normalmente de 1024 bits). No hay indicios de que un hash VSH truncado ofrezca una seguridad proporcional a su longitud.

Existe un ataque de colisión parcial en VSH truncado a $ℓ$ bits menos significativos. ^{[ 2 ]}

La complejidad de este ataque contra VSH es:

Precalcular la tabla sin conexión: $2 ℓ /3$ de tiempo y espacio.
Detección de colisiones: $2 ℓ /3$ iteraciones.
Coste total: aproximadamente $2 ℓ /3$ , en lugar de $2 ℓ /2$ como cabría esperar de una función hash con buenas propiedades de pseudoaleatoriedad .

Esto probablemente descarta la aplicabilidad de VSH en esquemas de firma digital que producen firmas más cortas que el resultado del hash VSH, como los esquemas de firma de curva elíptica.

Véase también

Referencias

1 2 3 4 5 Contini, S.; Lenstra, A.; Steinfeld, R. (2005-06-23), VSH, una función hash resistente a colisiones eficiente y demostrable.
↑ Saarinen, M.-JO (2006), "Seguridad de VSH en el mundo real" (PDF) , Progress in Cryptology - INDOCRYPT 2006 , Lecture Notes in Computer Science, vol. 4329, pp. 95–103 , doi : 10.1007/11941378_8 , ISBN 978-3-540-49767-7

[main-1] 1 2 3 4 5 Contini, S.; Lenstra, A.; Steinfeld, R. (2005-06-23), VSH, una función hash resistente a colisiones eficiente y demostrable.

[attack-2] Saarinen, M.-JO (2006), "Seguridad de VSH en el mundo real" (PDF) , Progress in Cryptology - INDOCRYPT 2006 , Lecture Notes in Computer Science, vol. 4329, pp. 95–103 , doi : 10.1007/11941378_8 , ISBN 978-3-540-49767-7

[

[ 2 ]