En criptografía , SWIFFT es una colección de funciones hash demostrablemente seguras . Se basa en el concepto de transformada rápida de Fourier (FFT). SWIFFT no es la primera función hash basada en FFT, pero se distingue por proporcionar una prueba matemática de su seguridad. También utiliza el algoritmo de reducción de la base LLL . Se puede demostrar que encontrar colisiones en SWIFFT es al menos tan difícil como encontrar vectores cortos en redes cíclicas / ideales en el peor de los casos . Al dar una reducción de seguridad al peor de los casos de un problema matemático difícil, SWIFFT ofrece una garantía de seguridad mucho más sólida que la mayoría de los demás.Funciones hash criptográficas .
General | |
---|---|
Diseñadores | Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, Alon Rosen |
Publicado por primera vez | 2008 |
Relacionado con | Algoritmos basados en FFT |
A diferencia de muchas otras funciones hash demostrablemente seguras, el algoritmo es bastante rápido, con un rendimiento de 40 Mbit / s en un Intel Pentium 4 de 3,2 GHz. Aunque SWIFFT satisface muchas propiedades criptográficas y estadísticas deseables, no fue diseñado para ser un "multipropósito "función hash criptográfica. Por ejemplo, no es una función pseudoaleatoria y no sería una instanciación adecuada de un oráculo aleatorio . El algoritmo es menos eficiente que la mayoría de las funciones hash tradicionales que no dan una prueba de su resistencia a colisiones. Por lo tanto, su uso práctico radicaría principalmente en aplicaciones donde la prueba de resistencia a colisiones es particularmente valiosa, como las firmas digitales que deben permanecer confiables durante mucho tiempo.
Se propuso una modificación de SWIFFT llamada SWIFFTX como candidata para la función SHA-3 a la competencia de la función hash del NIST [1] y fue rechazada en la primera ronda. [2]
El algoritmo
El algoritmo es el siguiente: [3]
- Dejemos que la variable polinomial se llame
- Entrada : mensaje de longitud
- Convertir a una colección de polinomios en un cierto anillo polinomial con coeficientes binarios.
- Calcule los coeficientes de Fourier de cada utilizando SWIFFT.
- Definir los coeficientes de Fourier de , para que sean fijos y dependan de una familia de SWIFFT.
- Multiplica puntualmente los coeficientes de Fourier con los coeficientes de Fourier de para cada .
- Utilice FFT inversa para obtener polinomios de grado .
- Calcular modulo y .
- Convertir a bits y emitirlo .
- La operación FFT en el paso 4 es fácil de invertir y se realiza para lograr la difusión , es decir, mezclar los bits de entrada.
- La combinación lineal en el paso 6 logra confusión , ya que comprime la entrada.
- Esta es solo una descripción de alto nivel de lo que hace el algoritmo, se utilizan algunas optimizaciones más avanzadas para finalmente producir un algoritmo de alto rendimiento.
Ejemplo
Elegimos valores concretos para los parámetros n , m , y p de la siguiente manera: n = 64, m = 16, p = 257. Para estos parámetros, cualquier función de compresión fija en la familia toma una entrada binaria de longitud MN = 1024 bits ( 128 bytes), a una salida en el rango, que tiene tamaño . Una salida en se puede representar fácilmente utilizando 528 bits (66 bytes).
Descripción algebraica
Las funciones SWIFFT se pueden describir como una expresión algebraica simple sobre algún anillo polinomial . Una familia de estas funciones depende de tres parámetros principales: dejar ser una potencia de 2, deja ser un número entero pequeño y dejar ser un módulo (no necesariamente primo , pero conviene elegirlo primo). Definir ser el anillo , es decir, el anillo de polinomios en teniendo coeficientes enteros, módulo y . Un elemento de se puede escribir como un polinomio de grado tener coeficientes en . Una determinada función en la familia SWIFFT está especificada por elementos fijos del anillo , que se llaman multiplicadores. La función corresponde a la siguiente ecuación sobre el anillo R :
La son polinomios con coeficientes binarios, y corresponden a la entrada binaria de longitud .
Calcular el producto polinomial
Para calcular la expresión anterior, el problema principal es calcular los productos polinomiales . Una forma rápida de calcular estos productos viene dada por el teorema de convolución . Esto dice que bajo ciertas restricciones se cumple lo siguiente:
Aquí denota la transformada de Fourier ydenota el producto puntiagudo. En el caso general del teorema de convoluciónno denota multiplicación sino convolución . Sin embargo, se puede demostrar que la multiplicación de polinomios es una convolución.
Transformada rápida de Fourier
Para encontrar la transformada de Fourier usaremos FFT ( transformada rápida de Fourier ) que encuentra la transformada enhora. El algoritmo de multiplicación ahora es el siguiente: usamos FFT para calcular (todos a la vez) los coeficientes de Fourier de cada polinomio. Luego multiplicamos puntualmente los respectivos coeficientes de Fourier de los dos polinomios, y finalmente usamos una FFT inversa para devolver un polinomio de grado.
Transformada teórica de números
En lugar de la transformada de Fourier normal, SWIFFT utiliza la transformada de teoría numérica . La transformada teórica de números usa raíces de unidad enen lugar de raíces complejas de unidad. Para que esto funcione, debemos asegurarnos de quees un campo finito , y que las primitivas 2 n th raíces de existir unidad en este campo. Esto se puede hacer tomando primer tal que divide .
Elección de parámetros
Los parámetros m , p , n están sujetos a las siguientes restricciones:
- n debe ser una potencia de 2
- p debe ser primo
- p -1 debe ser un múltiplo de 2 n
- debe ser menor que m (de lo contrario, la salida no será menor que la entrada)
Una posible elección es n = 64, m = 16, p = 257. Obtenemos un rendimiento de aproximadamente 40 Mbit / s, seguridad de aproximadamente operaciones para encontrar colisiones y un tamaño de resumen de 512 bits.
Propiedades estadísticas
- (Hash universal). La familia de funciones SWIFFT es universal . Significa que para cualquier fijo distinto, la probabilidad (sobre la elección aleatoria de de la familia) que es la inversa del tamaño del rango.
- (Regularidad). La familia SWIFFT de funciones de compresión es regular. Una función se dice que es regular si, para una entrada elegido uniformemente al azar del dominio, la salida se distribuye uniformemente sobre el rango.
- (Extractor de aleatoriedad). SWIFFT es un extractor de aleatoriedad . Para tablas hash y aplicaciones relacionadas, normalmente es deseable que las salidas de la función hash se distribuyan de manera uniforme (o lo más uniformemente posible), incluso cuando las entradas no sean uniformes. Las funciones hash que brindan tales garantías se conocen como extractores de aleatoriedad , porque destilan la aleatoriedad no uniforme de la entrada hasta una salida (casi) uniformemente distribuida. Formalmente, la extracción aleatoria es en realidad una propiedad de una familia de funciones, de la cual se elige una función al azar (y sin darse cuenta de la entrada).
Propiedades criptográficas y seguridad
- SWIFFT no es pseudoaleatorio debido a la linealidad. Para cualquier función de nuestra familia y dos entradas , tal que también es una entrada válida, tenemos que . Es muy poco probable que esta relación se cumpla para una función aleatoria, por lo que un adversario puede distinguir fácilmente nuestras funciones de una función aleatoria.
- Los autores no afirman que las funciones SWIFFT se comporten como un oráculo aleatorio . Se dice que una función se comporta como un oráculo aleatorio si actúa como una función verdaderamente aleatoria. Esto se diferencia de la pseudoaleatoriedad en que la función es fija y pública.
- La familia SWIFFT es demostrablemente resistente a las colisiones (en un sentido asintótico), bajo una suposición relativamente leve sobre la dificultad del peor de los casos de encontrar vectores cortos en redes cíclicas / ideales. Esto implica que la familia también es resistente a la segunda preimagen.
Seguridad teórica
SWIFFT es un ejemplo de función hash criptográfica demostrablemente segura . Como ocurre con la mayoría de las pruebas de seguridad, la prueba de seguridad de SWIFFT se basa en una reducción a cierto problema matemático difícil de resolver. Tenga en cuenta que esto significa que la seguridad de SWIFFT depende en gran medida de la dificultad de este problema matemático.
La reducción en el caso de SWIFFT es el problema de encontrar vectores cortos en redes cíclicas / ideales . Se puede probar que se cumple lo siguiente: Supongamos que tenemos un algoritmo que para una versión aleatoria de SWIFFT dada por puede encontrar colisiones en dentro de un tiempo factible , y con probabilidad . Se permite que el algoritmo solo funcione en una fracción pequeña pero notable de la familia SWIFFT. Entonces podemos encontrar también un algoritmoque siempre puede encontrar un vector corto en cualquier celosía ideal sobre el anillo en algún tiempo factible , Dependiendo de y . Esto significa que encontrar colisiones en SWIFFT es al menos tan difícil como el peor de los casos de encontrar vectores cortos en una celosía sobre. Por el momento, los algoritmos más rápidos para encontrar vectores cortos son todos exponenciales en. Tenga en cuenta que esto asegura que no haya un conjunto significativo de "instancias débiles" donde la seguridad de SWIFFT sea débil. Esta garantía no la ofrecen la mayoría de las otras funciones hash demostrablemente seguras.
Seguridad práctica
Los ataques de trabajo conocidos son el ataque de cumpleaños generalizado , que toma 2 106 operaciones y los ataques de inversión que requieren 2 448 operaciones para una elección de parámetro estándar. Por lo general, se considera que esto es suficiente para hacer inviable el ataque de un adversario.
Referencias
- ^ Daniele Micciancio; Yuriy Arbitman; Gil Dogon; Vadim Lyubashevsky; Chris Peikert; Alon Rosen (30 de octubre de 2008). "SWIFFTX: una propuesta para el estándar SHA-3" (PDF) . Consultado el 3 de marzo de 2017 .
- ^ "Candidatos de la Segunda Ronda" . Instituto Nacional de Estándares y Tecnología . 2009-07-16. Archivado desde el original el 4 de junio de 2017 . Consultado el 3 de marzo de 2017 .CS1 maint: bot: estado de URL original desconocido ( enlace )
- ^ Vadim Lyubashevsky; Daniele Micciancio; Chris Peikert; Alon Rosen (21 de febrero de 2008). "SWIFFT: una propuesta modesta para Hashing FFT" (PDF) . Consultado el 3 de marzo de 2017 .