En criptografía , Very Smooth Hash (VSH) es una función de hash criptográfica demostrablemente segura inventada en 2005 por Scott Contini, Arjen Lenstra y Ron Steinfeld. [1] Probablemente seguro significa que encontrar colisiones es tan difícil como algún problema matemático conocido. A diferencia de otros hashes resistentes a colisiones de probada seguridad , VSH es eficiente y utilizable en la práctica. Asintóticamente , solo requiere una única multiplicación por log ( n ) mensajes-bits y usa aritmética de tipo RSA. Por lo tanto, VSH puede resultar útil en entornos integrados donde el espacio de código es limitado.
General | |
---|---|
Diseñadores | Scott Contini , Arjen K. Lenstra y Ron Steinfeld |
Publicado por primera vez | 2005 |
Sucesores | VSH * |
Detalle | |
Tamaños de resumen | 1024 bits y más |
Se propusieron dos variantes principales de VSH. Por un lado, encontrar una colisión es probablemente tan difícil como encontrar una raíz cuadrada modular no trivial de un número muy suave módulo n . El otro usa 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 usar para construir una función hash de trampilla aleatoria probadamente segura. Esta función puede reemplazar la función de trampilla utilizada en el esquema de firma de Cramer-Shoup , manteniendo su seguridad demostrable mientras acelera el tiempo de verificación en aproximadamente un 50%.
VSN y VSSR
Todas las funciones de hash criptográficas que ahora se utilizan ampliamente no se basan en problemas matemáticos difíciles. Las pocas funciones que se construyen sobre problemas matemáticos difíciles se denominan probadamente seguras . Entonces se sabe que encontrar colisiones es tan difícil como resolver el difícil problema matemático. Para la versión básica de la función Very Smooth Hash, este difícil problema 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 una constante fija c y n un número entero m es un muy suave Número (VSN) si el factor primo más grande de m es como máximo (log n ) c .
Un entero b es un módulo n de residuo cuadrático muy suave si el primo más grande en la factorización de b s es como máximo (log n ) c y existe un número entero x tal que. Se dice que el número entero x es una raíz cuadrada modular de b .
Solo nos interesan las raíces cuadradas no triviales, aquellas en las que x 2 ≥ n . Si x 2 < n , la raíz se puede calcular fácilmente utilizando algoritmos de campos de características 0, como campo real. Por tanto, no son adecuados en primitivas criptográficas.
La raíz cuadrada modular no trivial de número muy suave (VSSR) es el siguiente problema: Sea n el producto de dos números primos desconocidos de aproximadamente el mismo tamaño y sea. Dejarser la secuencia de primos. VSSR es el siguiente problema: dado n , encuentre tal que y al menos uno de e 0 , ..., e k es impar.
El supuesto de VSSR es que no hay polinomio probabilístico (en) algoritmo de tiempo que resuelve VSSR con una probabilidad no despreciable . Esto se considera una suposición inútil para la práctica porque no indica para qué tamaño de módulo VSSR es computacionalmente difícil. En su lugar, se utiliza el supuesto de VSSR computacional . Dice que se supone que resolver VSSR es tan difícil como factorizar un factor difícil de factorizar. módulo de bits, donde es algo más pequeño que el tamaño de .
Ejemplos de VSN y VSSR
Deje que los parámetros se fijen de la siguiente manera: y .
Luego es un número muy suave con respecto a estos parámetros porque es mayor que todos factores primos. Por otro lado, no es un VSN bajo y .
El entero es un módulo de residuo cuadrático muy suave porque es un número muy suave (bajo ) y tenemos tal que (modificación ). Esta es una raíz cuadrada modular trivial, porque por lo que el módulo no está involucrado cuando se eleva al cuadrado.
El entero también es un módulo de residuo cuadrático muy suave . Todos los factores primos son menores que 7.37 y la raíz cuadrada modular es desde (modificación ). Por tanto, esta es una raíz no trivial. El problema de VSSR es encontrar dado y . Y suponemos que esto es computacionalmente tan difícil como factorizar.
Algoritmo VSH, versiones básicas
Dejar ser un gran compuesto RSA y dejar la secuencia de primos. Dejar, la longitud del bloque, sea el entero más grande tal que . Dejar frijol -bit mensaje a ser hash que consta de bits y asumir que . Para calcular el hash de:
- x 0 = 1
- Dejar , el número entero más pequeño mayor o igual a , sea el número de bloques. Dejar por (relleno)
- Dejar con ser la representación binaria de la longitud del mensaje y definir por .
- para j = 0, 1, ..., L en sucesión calcular
- devuelve x L + 1 .
La función del paso 4 se denomina función de compresión.
Propiedades de VSH
- No es necesario conocer la longitud del mensaje de antemano.
- Encontrar una colisión en VSH es tan difícil como resolver VSSR. Por tanto, VSH es (fuertemente) resistente a las colisiones , lo que también implica una segunda resistencia a la preimagen. No se ha demostrado que VSH sea resistente a las preimágenes.
- La función de compresión no es resistente a colisiones. No obstante, la función hash VSH es resistente a colisiones según la suposición de VSSR. Una versión alterada de VSH, llamada VSH * , utiliza una función de compresión resistente a colisiones y es aproximadamente 5 veces más rápida cuando se procesan mensajes cortos.
- Dado que la longitud de salida de VSH es la longitud de un módulo RSA seguro, VSH parece bastante adecuado en la práctica para construir firmas RSA "hash-luego-firmar" para mensajes arbitrariamente largos. Sin embargo, dicha firma debe diseñarse cuidadosamente para garantizar su seguridad. El enfoque ingenuo podría romperse fácilmente con CPA (ataque de texto sin formato elegido) .
- Eficiencia : el costo de cada iteración es menor que el costo de 3 multiplicaciones modulares. La versión básica de VSH requiere una multiplicación simple por bits de mensaje.
Variantes de VSH
Se han propuesto varias mejoras, aceleraciones y variantes más eficientes de VSH. [1] Ninguno de ellos cambia el concepto subyacente de la función. Estas mejoras se denominan:
- Cubar VSH (en lugar de cuadrar).
- VSH con mayor número de pequeños números primos.
- VSH con productos precalculados de primos.
- VSH rápido.
- VSH rápido con mayor longitud de bloque.
Variante VSDL y VSH-DL
El VSH-DL es una variante de logaritmo discreto de VSH que no tiene trampilla , su seguridad depende de la dificultad de encontrar logaritmo discreto módulo a primo p . [1]
El logaritmo discreto de número muy suave (VSDL) es un problema en el que, dado un número muy suave, queremos encontrar su módulo de logaritmo discreto algún número n .
Del mismo modo que en la sección anterior, por denotamos el -th prime. Deja además ser una constante fija y , ser primos con y deja . VSDL es el siguiente problema: dado, encuentra enteros tal que con por y al menos uno de distinto de cero.
El supuesto de VSDL es que no hay polinomio probabilístico (en) algoritmo de tiempo que resuelve VSDL con una probabilidad no despreciable . Existe una fuerte conexión entre la dureza de VSDL y la dureza de calcular el módulo de logaritmo discreto, que recuerda, pero algo más débil, la conexión entre VSSR y factorización de enteros.
Seguridad de VSH
La fuerte resistencia a las colisiones es la única propiedad probada de VSH. Esto no implica resistencia a la preimagen u 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 dependan de ellos ( firmas RSA , algunos MAC ). [1] VSH no debe considerarse una función hash de propósito general como se suele entender en la ingeniería de seguridad .
Propiedad multiplicativa
VSH es multiplicativo: sean x , y , z tres cadenas de bits de igual longitud, donde z consta solo de cero bits y las cadenas satisfacen x AND y = z . Es fácil ver que 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 hashes multiplicativos y aditivos.
Este hecho se puede utilizar para construir un ataque de preimagen contra VSH de bits que tiene complejidad en lugar de como se esperaba.
Ataque contra la versión truncada
VSH produce un hash muy largo (normalmente 1024 bits). No hay indicios de que un hash VSH truncado ofrezca una seguridad acorde con la longitud del hash.
Existe un ataque de colisión parcial en VSH truncado a los bits l menos significativos . [2]
La complejidad de este ataque contra VSH es:
- Precalcular la tabla fuera de línea: tiempo y espacio.
- Encontrar colisiones: iteraciones.
- Costo total: aproximadamente , en vez de como se esperaba 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.
Ver también
Referencias
- ^ a b c d e 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) , doi : 10.1007 / 11941378_8