RÁPIDO

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de febrero de 2021; las comprobaciones requieren 3 ediciones .

RÁPIDO
Desarrolladores	Vadim Lyubashevsky, Daniel Michiancio, Chris Peikert, Alon Rosen
Creado	2008
publicado	2008
Tipo de	función hash

SWIFFT es un conjunto de funciones hash criptográficas con seguridad comprobada [1] [2] [3] . Se basan en la Transformada Rápida de Fourier ( FFT ) y utilizan el algoritmo de bases reducidas LLL . La seguridad criptográfica de las funciones SWIFFT (en sentido asintótico) [4] se demuestra matemáticamente utilizando los parámetros recomendados [5] . Encontrar colisiones en SWIFFT requiere al menos tanto tiempo en el peor de los casos como encontrar vectores cortos en retículas cíclicas/ideales . La aplicación práctica de SWIFFT será valiosa precisamente en aquellos casos en los que la resistencia a las colisiones sea especialmente importante. Por ejemplo, las firmas digitales, que deben permanecer fiables durante mucho tiempo.

Este algoritmo proporciona un rendimiento de aproximadamente 40 Mb/s en un procesador Intel Pentium 4 con una frecuencia de reloj de 3,2 GHz [6] [1] . Se han realizado investigaciones para acelerar la FFT, que se utiliza en SWIFFT [7] . Como resultado, la velocidad del algoritmo aumentó más de 13 veces [6] . Esta implementación de SWIFFT resultó ser más rápida que las implementaciones de funciones hash ampliamente utilizadas [8] .

En la competencia del Instituto Nacional de Estándares y Tecnología de 2012 [2] , se propuso SWIFFTX (una modificación de SWIFFT) como SHA-3 (para reemplazar al antiguo SHA-2 y especialmente al SHA-1 [9] ), pero fue rechazado en la primera ronda [ 10] .

Descripción del trabajo

Las funciones SWIFFT se pueden describir como una simple expresión algebraica sobre algún anillo polinomial [1] [11] . La familia de funciones depende de tres parámetros principales : sea una potencia de 2, - un número entero pequeño y - no necesariamente un número primo , pero es mejor elegirlo primo. Lo definimos como un anillo de la forma . Por ejemplo, el anillo de polinomios en , cuyos coeficientes son números enteros, es el número por el cual realizamos la división de módulo, y . Un elemento de puede ser un polinomio de menor grado con coeficientes de . $R$ $norte$ $m>0$ $p>0$ $R$ $R=\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ $\alfa$ $pags$ $\alfa ^{n}+1$ $R$ $norte$ $Z_{p}$

Una función definida en la familia SWIFFT se define como elementos de anillo fijos , llamados multiplicadores. Esta función sobre el anillo se puede escribir de la siguiente forma: $metro$ $a_{1},\ldots,a_{m}\in R$ $R$ $R$

$\sum _{i=1}^{m}(a_{i}\cdot x_{i})$ ,

donde son polinomios con coeficientes binarios correspondientes a un mensaje de entrada binario de longitud . $x_{1},\ldots,x_{m}\in R$ $Minnesota$

El algoritmo de operación es el siguiente: [1] [12] [11]

Taken es un polinomio irreducible sobre $\alfa$ $\mathbb {Z} [\alfa]$
La entrada es un mensaje de longitud $METRO$ $Minnesota$
$METRO$ se convierte en un conjunto de polinomios en un cierto anillo de polinomios con coeficientes binarios $metro$ $Pi}$ $R$
Los coeficientes de Fourier se calculan para cada $Pi}$
Los coeficientes fijos de Fourier se establecen según la familia SWIFFT $ai}$
Los coeficientes de Fourier se multiplican por pares con para cada $Pi}$ $ai}$ $i$
Se utiliza la transformada inversa de Fourier para obtener polinomios de grado máximo $metro$ $f_{i}$ $2n$
Módulo calculado y . $f=\sum_{i=1}^{m}(f_{i})$ $pags$ $\alfa ^{n}+1$
$F$ convertido a bits y enviado a la salida $n\registro(p)$

La operación de transformada rápida de Fourier en el paso 4 es fácil de invertir. Se lleva a cabo para lograr confusión : mezclar bits dados a la entrada.
La combinación lineal en el paso 6 es confusa porque comprime la entrada.

Ejemplo

Los valores específicos para los parámetros n , m y p se eligen de la siguiente manera: n = 64, m = 16, p = 257 [13] . Para estos parámetros, cualquier función de compresión fija de la familia aceptará como entrada un mensaje de longitud mn = 1024 bits (128 bytes). La salida está en un rango que tiene tamaño . Los datos de salida se pueden representar utilizando 528 bits (66 bytes). $\mathbb {Z} _{p}^{n}$ $p^{n}=257^{64}$ $\mathbb {Z} _{p}^{n}$

Cálculo del resultado de la multiplicación de polinomios

La parte más difícil de calcular la expresión anterior es calcular el resultado de la multiplicación [1] [14] . Una forma rápida de calcular un producto dado es usar el teorema de convolución , que establece que bajo ciertas condiciones: $a_{i}\cdot x_{i}$

{\mathcal {F}}\{f*g\}={\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}

Aquí denota la transformada de Fourier , y la operación significa multiplicar coeficientes con el mismo índice. En general, el teorema de convolución tiene el significado de convolución , no de multiplicación. Sin embargo, se puede demostrar que la multiplicación de polinomios es una convolución. ${\ matemáticas {F}}$ $\cdot$ $*$

Transformada rápida de Fourier

Para encontrar la transformada de Fourier, usamos la transformada rápida de Fourier (FFT), que toma [1] . El algoritmo de multiplicación es el siguiente [14] : calculamos todos los coeficientes de Fourier para todos los polinomios a la vez usando la FFT. Luego multiplicamos por pares los coeficientes de Fourier correspondientes de los dos polinomios. Después usamos la FFT inversa, después de lo cual obtenemos un polinomio de grado no superior a . $O(n\log(n))$ $2n$

Transformada discreta de Fourier

En lugar de la transformada de Fourier habitual, SWIFFT utiliza la transformada discreta de Fourier (DFT) [1] [14] . Utiliza raíces de unidad en lugar de raíces complejas de unidad. Esto será cierto si es un campo finito , y sus 2 n ésimas raíces simples de la unidad existen en el campo dado. Estas condiciones se cumplirán si tomamos un número primo que sea divisible por . $\mathbb {Z} _{p}$ $\mathbb {Z} _{p}$ $pags$ $p-1$ $2n$

Elección de opciones

Los parámetros m , p , n deben cumplir los siguientes requisitos [15] :

n debe ser una potencia de dos
p debe ser un número primo
p -1 debe ser divisible por 2 n
$\registro(p)<$ metro

Puede tomar, por ejemplo, los siguientes parámetros: n =64, m =16, p =257. Tomamos el rendimiento al nivel de 40 Mb / s [6] , seguridad de la búsqueda de colisiones - operaciones. $2^{106}$

Propiedades estadísticas

Hashing universal. La familia de funciones SWIFFT es universal [1] . En otras palabras, para cualquier función diferente fija y elegida aleatoriamente de la familia, la probabilidad de que se mantenga la igualdad es inversamente proporcional al valor del rango elegido. $x,x*$ $F$ $f(x)=f(x*)$
Regularidad. Las funciones de la familia SWIFFT de funciones de reducción son regulares [1] .
generador de entropía. SWIFFT es un generador de entropía [1] . Para tablas hash y aplicaciones relacionadas, es deseable que las claves para los valores introducidos en la función se distribuyan de manera uniforme (o cerca de la distribución uniforme), incluso si los valores de entrada se distribuyen de manera desigual. Las funciones hash que se comportan de esta manera se denominan generadores de entropía porque pueden convertir parámetros distribuidos de manera desigual en una salida (casi) uniforme. Formalmente, esta propiedad suele tener una familia de funciones, de las cuales se elige una función al azar.

Propiedades criptográficas y seguridad

SWIFFT no es una función pseudoaleatoria debido a la linealidad [1] . Para una función arbitraria de la familia SWIFFT, se cumple lo siguiente: para dos parámetros de entrada , tal que también puede ser un parámetro de entrada, . El cumplimiento de esta relación no es adecuado para una función aleatoria, y un atacante puede distinguir fácilmente nuestra función de una aleatoria. $F$ $x_{1}$ $x_{2}$ $x_{1}+x_{2}$ $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$

Para la familia de funciones SWIFFT, la resistencia criptográfica a las colisiones (en el sentido asintótico) se ha probado bajo una suposición relativamente moderada sobre la complejidad del problema de encontrar vectores cortos en redes cíclicas/ideales en el peor de los casos. Esto significa que la familia de funciones SWIFFT también es resistente al segundo ataque de preimagen [4] [16] .

Estabilidad teórica

SWIFFT - Funciones criptográficas de seguridad comprobadas [1] [3] . Como en la mayoría de los casos, la prueba de la seguridad de las funciones se basa en que el problema matemático utilizado en las funciones no se puede resolver en tiempo polinomial. Esto significa que la fuerza de SWIFFT radica únicamente en el hecho de que se basa en un problema matemático complejo.

En el caso de SWIFFT, la seguridad probada radica en el problema de encontrar vectores cortos en redes cíclicas/ideales [17] . Se puede probar que la siguiente afirmación es verdadera: supongamos que tenemos un algoritmo que puede encontrar colisiones de funciones para una versión aleatoria de SWIFFT obtenida de , en algún tiempo posible con probabilidad . Esto significa que el algoritmo funciona solo en una pequeña pero notable fracción de las funciones de la familia. Entonces también podemos encontrar un algoritmo que siempre puede encontrar un vector corto en cualquier red ideal sobre un anillo en algún tiempo posible dependiendo de y . Esto significa que encontrar colisiones en SWIFFT no es menos difícil, el problema de encontrar vectores cortos en una red sobre , para los cuales solo existen algoritmos exponenciales . $F$ $F$ $T$ $pags$ $f_{2}$ $\mathbb {Z} _{p}[\alfa]/(\alfa^{n}+1)$ $T_{2}$ $T$ $pags$ $\mathbb {Z} _{p}[\alfa]/(\alfa^{n}+1)$

Práctica durabilidad

Los autores de esta función hash la examinaron en busca de vulnerabilidades a varios ataques y descubrieron que el ataque de "cumpleaños" requiere la menor cantidad de operaciones de conteo de hash (2 106 ) para encontrar colisiones. [18] [1] . Los ataques de permutación requieren 2448 conteos para parámetros estándar. Una enumeración completa de los valores posibles requeriría 2528 cálculos hash. Esto suele ser suficiente para hacer imposible un ataque enemigo.

Véase también

Transformada rápida de Fourier

Notas

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 Lyubashevsky et al., 2008 .
↑ 12 Arbitman et al., 2008 .
↑ 1 2 Györfi et al., 2012 , pág. 2.
↑ 12 Arbitman et al., 2008 , pág. una.
↑ Buchmann y Lindner 2009 , pág. 1-2.
↑ 1 2 3 Györfi et al., 2012 , pág. quince.
↑ Györfi et al., 2012 , pág. 15-16.
↑ Györfi et al., 2012 , pág. dieciséis.
↑ COMPETENCIA PRE-SHA-3 . Instituto Nacional de Normas y Tecnología (15 de abril de 2005). Archivado desde el original el 9 de agosto de 2017. (indefinido)
↑ Candidatos a la segunda ronda . Instituto Nacional de Normas y Tecnología (19 de enero de 2010). Consultado el 14 de febrero de 2010. Archivado desde el original el 10 de abril de 2012. (indefinido)
↑ 1 2 Györfi et al., 2012 , pág. 3.
↑ Arbitman et al., 2008 , pág. 4-5.
↑ Györfi et al., 2012 .
↑ 1 2 3 Györfi et al., 2012 , pág. cuatro
↑ Buchmann, Lindner, 2009 .
↑ Sarinay, 2010 , pág. 9.
↑ Arbitman et al., 2008 , pág. 10-11.
↑ Buchmann y Lindner 2009 , pág. 2.

Literatura

Libros

Schneier B. Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumph, 2002. - 816 p. - 3000 copias. - ISBN 5-89392-055-4 .

Artículos

Lyubashevsky V. , Micciancio D. , Peikert C. , Rosen A. SWIFFT: una propuesta modesta para FFT Hashing (inglés) // Cifrado rápido de software - 2008. - vol. 5086. - Pág. 54-72. doi:10.1007/ 978-3-540-71039-4_4
Arbitman Y. , Dogon G. , Lyubashevsky V. , Micciancio D. , Peikert C. , Rosen A. SWIFFTX: una propuesta para el estándar SHA-3 (inglés) - 2008.
Buchmann J. , Lindner R. Secure Parameters for SWIFFT (inglés) // Progress in Cryptology - INDOCRYPT 2009 : 10th International Conference on Cryptology in India, New Delhi, India, 13-16 de diciembre de 2009. Actas / B. Roy , N Sendrier - Springer Berlín Heidelberg , 2009. - P. 1-17. - ISBN 978-3-642-10627-9 - doi:10.1007/978-3-642-10628-6_1
Šarinay J. Interpreting Hash Function Security Proofs (inglés) // Provable Security : 4th International Conference, ProvSec 2010, Malacca, Malaysia, 13-15 de octubre de 2010. Actas / S. Heng , K. Kurosawa - Springer Berlin Heidelberg , 2010. -Pág. 119-132. — ISBN 978-3-642-16279-4 — doi:10.1007/978-3-642-16280-0_8
Győrfi T. , Cret O. , Hanrot G. , Brisebarre N. Arquitectura de hardware de alto rendimiento para las funciones hash de SWIFFT/SWIFFTX // Cryptology ePrint Archive - Asociación internacional para la investigación criptológica , 2012.

Funciones hash
propósito general	Adler-32 CDN Suma de comprobación de Fletcher FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Árbol de hachís picadillo de jenkins suma de hash
Criptográfico	Stribog GOST R 34.11-94 Cinturón BLAKE BMW CubeHash ECO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H Kupyna Hachís de LM luffa MD2 MD4 MD5 MD6 N-hachís RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD RÁPIDO Piel Snefru Tigre Torbellino
Funciones de generación de claves	cripta PBKDF2 cripta Argón2 Lyra2
Número de cheque ( comparación )	Suma de verificación Algoritmo de Verhouff Algoritmo lunar Maldito algoritmo Código de barras cuentas bancarias tarjetas bancarias ES EN SNILES OKPO ESTAÑO OKATO ISBN OGRN y OGRNIP VIN
Hachís	Comparación de números de cheque Protocolos de autenticación Comparación de códigos de barras Criptografía Enlace magnético firma Merkle ed2k URNA