Hash basado en el síndrome rápido

Familia de funciones hash criptográficas

En criptografía , las funciones hash basadas en síndromes rápidos (FSB) son una familia de funciones hash criptográficas introducidas en 2003 por Daniel Augot, Matthieu Finiasz y Nicolas Sendrier. ^[1] A diferencia de la mayoría de las demás funciones hash criptográficas que se utilizan hoy en día, se puede demostrar que FSB es segura hasta cierto punto. Más exactamente, se puede demostrar que romper FSB es al menos tan difícil como resolver un cierto problema NP-completo conocido como decodificación de síndromes regulares , por lo que FSB es demostrablemente seguro . Aunque no se sabe si los problemas NP-completos se pueden resolver en tiempo polinomial , a menudo se supone que no lo son.

Se han propuesto varias versiones de FSB, la última de las cuales se presentó a la competición de criptografía SHA-3 , pero fue rechazada en la primera ronda. Aunque todas las versiones de FSB afirman tener una seguridad demostrable, algunas versiones preliminares acabaron siendo violadas. ^[2] Sin embargo, el diseño de la última versión de FSB ha tenido en cuenta este ataque y sigue siendo segura frente a todos los ataques conocidos hasta el momento.

Como es habitual, la seguridad demostrable tiene un coste. FSB es más lento que las funciones hash tradicionales y utiliza bastante memoria, lo que lo hace poco práctico en entornos con limitaciones de memoria. Además, la función de compresión utilizada en FSB necesita un tamaño de salida grande para garantizar la seguridad. Este último problema se ha solucionado en versiones recientes simplemente comprimiendo la salida mediante otra función de compresión llamada Whirlpool . Sin embargo, aunque los autores argumentan que añadir esta última compresión no reduce la seguridad, hace imposible una prueba de seguridad formal. ^[3]

Descripción de la función hash

Comenzamos con una función de compresión con parámetros tales que y . Esta función solo funcionará en mensajes con una longitud ; será el tamaño de la salida. Además, queremos que y sean números naturales, donde denota el logaritmo binario . La razón es que queremos que sea una función de compresión, por lo que la entrada debe ser mayor que la salida. Más adelante utilizaremos la construcción de Merkle–Damgård para extender el dominio a entradas de longitudes arbitrarias. ${\displaystyle \phi }$ ${\displaystyle {n,r,w}}$ ${\displaystyle n>w}$ ${\displaystyle w\log(n/w)>r}$ ${\displaystyle s=w\log(n/w)}$ ${\displaystyle r}$ ${\displaystyle n,r,w,s}$ ${\displaystyle \log(n/w)}$ ${\displaystyle \log }$ ${\displaystyle w\cdot \log(n/w)>r}$ ${\displaystyle \phi }$

La base de esta función consiste en una matriz binaria (elegida aleatoriamente) que actúa sobre un mensaje de bits mediante la multiplicación de matrices . Aquí codificamos el mensaje de bits como un vector en , el espacio vectorial de dimensiones sobre el campo de dos elementos, por lo que la salida será un mensaje de bits. ${\displaystyle r\times n}$ ${\displaystyle H}$ ${\displaystyle n}$ ${\displaystyle w\log(n/w)}$ ${\displaystyle (\mathbf {F} _{2})^{n}}$ ${\displaystyle n}$ ${\displaystyle r}$

Por motivos de seguridad y para obtener una velocidad de hash más rápida, queremos utilizar únicamente “palabras regulares de peso ” como entrada para nuestra matriz. ${\displaystyle w}$

Definiciones

• Un mensaje se denomina palabra de peso y longitud ${\displaystyle w}$ ${\displaystyle n}$ si está formado por bits y exactamente esos bits son unos. ${\displaystyle n}$ ${\displaystyle w}$
• Una palabra de peso y longitud se denomina regular si en cada intervalo contiene exactamente una entrada distinta de cero para todos los . De manera más intuitiva, esto significa que si dividimos el mensaje en w partes iguales, entonces cada parte contiene exactamente una entrada distinta de cero. ${\displaystyle w}$ ${\displaystyle n}$ ${\displaystyle [(i-1)(n/w),i(n/w))}$ ${\displaystyle 0<i<w+1}$

La función de compresión

Existen exactamente diferentes palabras regulares de peso y longitud , por lo que necesitamos exactamente bits de datos para codificar estas palabras regulares. Fijamos una biyección del conjunto de cadenas de bits de longitud al conjunto de palabras regulares de peso y longitud y luego la función de compresión FSB se define de la siguiente manera: ${\displaystyle (n/w)^{w}}$ ${\displaystyle w}$ ${\displaystyle n}$ ${\displaystyle \log((n/w)^{w})=w\log(n/w)=s}$ ${\displaystyle s}$ ${\displaystyle w}$ ${\displaystyle n}$

1. entrada: un mensaje de tamaño ${\displaystyle s}$
2. convertir a palabra regular de longitud y peso ${\displaystyle n}$ ${\displaystyle w}$
3. multiplicar por la matriz ${\displaystyle H}$
4. salida: hash de tamaño ${\displaystyle r}$

Esta versión se suele llamar compresión basada en síndromes . Es muy lenta y, en la práctica, se realiza de una manera diferente y más rápida, lo que da como resultado una compresión basada en síndromes rápida . Dividimos en submatrices de tamaño y fijamos una biyección de las cadenas de bits de longitud al conjunto de secuencias de números entre 1 y . Esto es equivalente a una biyección al conjunto de palabras regulares de longitud y peso , ya que podemos ver una palabra de este tipo como una secuencia de números entre 1 y . La función de compresión se ve así: ${\displaystyle H}$ ${\displaystyle H_{i}}$ ${\displaystyle r\times n/w}$ ${\displaystyle w\log(n/w)}$ ${\displaystyle w}$ ${\displaystyle n/w}$ ${\displaystyle n}$ ${\displaystyle w}$ ${\displaystyle n/w}$

1. Entrada: mensaje de tamaño ${\displaystyle s}$
2. Convertir a una secuencia de números entre 1 y ${\displaystyle s}$ ${\displaystyle w}$ ${\displaystyle s_{1},\dots ,s_{w}}$ ${\displaystyle n/w}$
3. Sume las columnas correspondientes de las matrices para obtener una cadena binaria de longitud ${\displaystyle H_{i}}$ ${\displaystyle r}$
4. Salida: hash de tamaño ${\displaystyle r}$

Ahora podemos utilizar la construcción de Merkle–Damgård para generalizar la función de compresión para aceptar entradas de longitudes arbitrarias.

Ejemplo de la compresión

Situación e inicialización : Generar un hash de un mensaje utilizando la matriz H que está separada en subbloques , , . ${\displaystyle s=010011}$ ${\displaystyle 4\times 12}$
${\displaystyle H=\left({\begin{array}{llllcllllcllll}1&0&1&1&~&0&1&0&0&~&1&0&1&1\\0&1&0&0&~&0&1&1&1&~&0&1&0&0\\0&1&1&1&~&0&1&0&0&~&1&0&1&0\\1&1&0&0&~&1&0&1&1&~&0&0&0&1\end{array}}\right)}$
${\displaystyle w=3}$ ${\displaystyle H_{1}}$ ${\displaystyle H_{2}}$ ${\displaystyle H_{3}}$

Algoritmo :

1. Dividimos la entrada en partes de longitud y obtenemos , , . ${\displaystyle s}$ ${\displaystyle w=3}$ ${\displaystyle \log _{2}(12/3)=2}$ ${\displaystyle s_{1}=01}$ ${\displaystyle s_{2}=00}$ ${\displaystyle s_{3}=11}$
2. Convertimos cada uno en un entero y obtenemos , , . ${\displaystyle s_{i}}$ ${\displaystyle s_{1}=1}$ ${\displaystyle s_{2}=0}$ ${\displaystyle s_{3}=3}$
3. De la primera submatriz elegimos la columna 2, de la segunda submatriz la columna 1 y de la tercera submatriz la columna 4. ${\displaystyle H_{1}}$ ${\displaystyle H_{2}}$
4. Sumamos las columnas elegidas y obtenemos el resultado . ${\displaystyle r=0111\oplus 0001\oplus 1001=1111}$

Prueba de seguridad del FSB

Se ha demostrado que la construcción de Merkle–Damgård basa su seguridad únicamente en la seguridad de la función de compresión utilizada. Por lo tanto, solo necesitamos demostrar que la función de compresión es segura. ${\displaystyle \phi }$

Una función hash criptográfica debe ser segura en tres aspectos diferentes:

1. Resistencia de preimagen: Dado un Hash h debería ser difícil encontrar un mensaje m tal que Hash( m )= h
2. Segunda resistencia de preimagen: Dado un mensaje m ₁ debería ser difícil encontrar un mensaje m ₂ tal que Hash( m ₁ ) = Hash( m ₂ )
3. Resistencia a colisiones: Debería ser difícil encontrar dos mensajes diferentes m ₁ y m ₂ tales que Hash( m ₁ )=Hash( m ₂ )

Tenga en cuenta que si un adversario puede encontrar una segunda preimagen, entonces seguramente podrá encontrar una colisión. Esto significa que si podemos demostrar que nuestro sistema es resistente a las colisiones, seguramente será resistente a una segunda preimagen.

En criptografía, por lo general, duro significa algo como “casi con toda seguridad fuera del alcance de cualquier adversario al que se le debe impedir que rompa el sistema”. Sin embargo, necesitaremos un significado más exacto de la palabra duro. Entendemos que duro significa “el tiempo de ejecución de cualquier algoritmo que encuentre una colisión o una preimagen dependerá exponencialmente del tamaño del valor hash”. Esto significa que, con adiciones relativamente pequeñas al tamaño del hash, podemos alcanzar rápidamente una alta seguridad.

Resistencia a la preimagen y decodificación del síndrome regular (RSD)

Como se dijo antes, la seguridad de FSB depende de un problema llamado decodificación de síndrome regular (RSD) . La decodificación de síndrome es originalmente un problema de la teoría de codificación , pero su NP-completitud la convierte en una buena aplicación para la criptografía. La decodificación de síndrome regular es un caso especial de decodificación de síndrome y se define de la siguiente manera:

Definición de RSD: dadas matrices de dimensión y una cadena de bits de longitud tales que existe un conjunto de columnas, una en cada , que suman . Encuentre dicho conjunto de columnas. ${\displaystyle w}$ ${\displaystyle H_{i}}$ ${\displaystyle r\times (n/w)}$ ${\displaystyle S}$ ${\displaystyle r}$ ${\displaystyle w}$ ${\displaystyle H_{i}}$ ${\displaystyle S}$

Se ha demostrado que este problema es NP-completo mediante una reducción a partir de una correspondencia tridimensional . Nuevamente, aunque no se sabe si existen algoritmos de tiempo polinomial para resolver problemas NP-completos, no se conoce ninguno y encontrar uno sería un gran descubrimiento.

Es fácil ver que encontrar una preimagen de un hash dado es exactamente equivalente a este problema, por lo que el problema de encontrar preimágenes en FSB también debe ser NP-completo. ${\displaystyle S}$

Todavía tenemos que demostrar la resistencia a las colisiones. Para ello necesitamos otra variante NP-completa de RSD: la decodificación del síndrome nulo 2-regular .

Resistencia a colisiones y decodificación del síndrome nulo 2-regular (2-RNSD)

Definición de 2-RNSD: Dadas matrices de dimensión y una cadena de bits de longitud tales que existe un conjunto de columnas, dos o cero en cada una , que suman cero. Encuentre dicho conjunto de columnas. ${\displaystyle w}$ ${\displaystyle H_{i}}$ ${\displaystyle r\times (n/w)}$ ${\displaystyle S}$ ${\displaystyle r}$ ${\displaystyle w'}$ ${\displaystyle H_{i}}$ ${\displaystyle (0<w'<2w)}$

También se ha demostrado que 2-RNSD es NP-completo mediante una reducción a partir de la correspondencia tridimensional .

Así como RSD es en esencia equivalente a encontrar una palabra regular tal que , 2-RNSD es equivalente a encontrar una palabra 2-regular tal que . Una palabra 2-regular de longitud y peso es una cadena de bits de longitud tal que en cada intervalo exactamente dos o cero entradas son iguales a 1. Tenga en cuenta que una palabra 2-regular es simplemente una suma de dos palabras regulares. ${\displaystyle w}$ ${\displaystyle Hw=S}$ ${\displaystyle w'}$ ${\displaystyle Hw'=0}$ ${\displaystyle n}$ ${\displaystyle w}$ ${\displaystyle n}$ ${\displaystyle [(i-1)w,iw)}$

Supongamos que hemos encontrado una colisión, por lo que tenemos Hash( m ₁ ) = Hash( m ₂ ) con . Entonces podemos encontrar dos palabras regulares y tales que . Entonces tenemos ; es una suma de dos palabras regulares diferentes y, por lo tanto, debe ser una palabra 2-regular cuyo hash es cero, por lo que hemos resuelto una instancia de 2-RNSD. Concluimos que encontrar colisiones en FSB es al menos tan difícil como resolver 2-RNSD y, por lo tanto, debe ser NP-completo. ${\displaystyle m_{1}\neq m_{2}}$ ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$ ${\displaystyle Hw_{1}=Hw_{2}}$ ${\displaystyle H(w_{1}+w_{2})=Hw_{1}+Hw_{2}=2Hw_{1}=0}$ ${\displaystyle (w_{1}+w_{2})}$

Las últimas versiones de FSB utilizan la función de compresión Whirlpool para comprimir aún más la salida hash. Aunque esto no se puede demostrar, los autores sostienen que esta última compresión no reduce la seguridad. Tenga en cuenta que incluso si uno fuera capaz de encontrar colisiones en Whirlpool, todavía necesitaría encontrar las imágenes previas de las colisiones en la función de compresión FSB original para encontrar una colisión en FSB.

Ejemplos

Al resolver RSD, nos encontramos en la situación opuesta a la del hash. Utilizando los mismos valores que en el ejemplo anterior, se nos proporcionan separados en subbloques y una cadena . Se nos pide que encontremos en cada subbloque exactamente una columna tal que todas sumen . La respuesta esperada es, por tanto , , . Se sabe que esto es difícil de calcular para matrices grandes. ${\displaystyle H}$ ${\displaystyle w=3}$ ${\displaystyle r=1111}$ ${\displaystyle r}$ ${\displaystyle s_{1}=1}$ ${\displaystyle s_{2}=0}$ ${\displaystyle s_{3}=3}$

En 2-RNSD queremos encontrar en cada subbloque no una columna, sino dos o cero de modo que sumen 0000 (y no ). En el ejemplo, podríamos usar la columna (contando desde 0) 2 y 3 de , ninguna columna de la columna 0 y 2 de . Son posibles más soluciones, por ejemplo, podríamos no usar columnas de . ${\displaystyle r}$ ${\displaystyle H_{1}}$ ${\displaystyle H_{2}}$ ${\displaystyle H_{3}}$ ${\displaystyle H_{3}}$

Criptoanálisis lineal

La seguridad demostrable de FSB significa que encontrar colisiones es NP-completo. Pero la prueba es una reducción a un problema con una complejidad asintóticamente difícil en el peor de los casos . Esto ofrece solo una garantía de seguridad limitada, ya que todavía puede haber un algoritmo que resuelva fácilmente el problema para un subconjunto del espacio del problema. Por ejemplo, existe un método de linealización que se puede utilizar para producir colisiones de en cuestión de segundos en una PC de escritorio para las primeras variantes de FSB con una seguridad declarada de 2^128. Se muestra que la función hash ofrece una resistencia mínima a la preimagen o a la colisión cuando el espacio del mensaje se elige de una manera específica.

Resultados prácticos de seguridad

La siguiente tabla muestra la complejidad de los ataques más conocidos contra FSB.

Génesis

FSB es una versión acelerada de la función hash basada en síndromes (SB). En el caso de SB, la función de compresión es muy similar a la función de codificación de la versión de Niederreiter del criptosistema McEliece . En lugar de utilizar la matriz de comprobación de paridad de un código Goppa permutado , SB utiliza una matriz aleatoria . Desde el punto de vista de la seguridad, esto solo puede fortalecer el sistema. ${\displaystyle H}$

Otras propiedades

• Tanto el tamaño del bloque de la función hash como el tamaño de salida son completamente escalables.
• La velocidad se puede ajustar ajustando el número de operaciones bit a bit utilizadas por FSB por bit de entrada.
• La seguridad se puede ajustar ajustando el tamaño de salida.
• Existen casos malos y hay que tener cuidado al elegir la matriz . ${\displaystyle H}$
• La matriz utilizada en la función de compresión puede aumentar de tamaño en determinadas situaciones. Esto puede ser una limitación al intentar utilizar FSB en dispositivos con limitaciones de memoria. Este problema se resolvió en la función hash relacionada denominada FSB mejorado, que sigue siendo demostrablemente segura , pero se basa en suposiciones ligeramente más sólidas.

Variantes

En 2007 se publicó el IFSB. ^[3] En 2010 se publicó el S-FSB, que es un 30% más rápido que el original. ^[4]

En 2011, DJ Bernstein y Tanja Lange publicaron RFSB, que es 10 veces más rápido que el FSB-256 original. ^[5] Se demostró que RFSB funcionaba muy rápido en el FPGA Spartan 6 , alcanzando rendimientos de alrededor de 5 Gbit/s. ^[6]

Referencias

1. Augot, D.; Finiasz, M.; Sendrier, N. (2003), Una función hash criptográfica rápida y demostrablemente segura
2. Saarinen, Markku-Juhani O. (2007), "Ataques de linealización contra hashes basados ​​en síndromes", Progress in Cryptology – INDOCRYPT 2007 (PDF) , Lecture Notes in Computer Science, vol. 4859, págs. 1–9, doi :10.1007/978-3-540-77026-8_1, ISBN 978-3-540-77025-1, consultado el 12 de noviembre de 2022
3. Finiasz, M.; Gaborit, P.; Sendrier, N. (2007), Funciones hash criptográficas mejoradas basadas en el síndrome Fast (PDF) , Taller de hash ECRYPT 2007, archivado desde el original (PDF) el 2016-03-03 , consultado el 2010-01-04
4. Meziani, Mohammed; Dagdelen, Özgür; Cayrel, Pierre-Louis; El Yousfi Alaoui, Sidi Mohamed (2011). "S-FSB: una variante mejorada de la familia de hash FSB" (PDF) . Seguridad y aseguramiento de la información . Comunicaciones en informática y ciencias de la información. Vol. 200. págs. 132–145. doi :10.1007/978-3-642-23141-4_13. ISBN 978-3-642-23140-7Archivado desde el original (PDF) el 22 de diciembre de 2015. Consultado el 10 de diciembre de 2014 .
5. Bernstein, Daniel J.; Lange, Tanja; Peters, Christiane; Schwabe, Peter (2011), "Really Fast Syndrome-Based Hashing", Progreso en criptología - AFRICACRYPT 2011 (PDF) , Lecture Notes in Computer Science, vol. 6737, págs. 134-152, doi :10.1007/978-3-642-21969-6_9, ISBN 978-3-642-21968-9, consultado el 12 de noviembre de 2022
6. von Maurich, Ingo; Güneysu, Tim (2012), "Hash basado en síndrome integrado", Progreso en criptología - INDOCRYPT 2012 (PDF) , Apuntes de clase en informática, vol. 7668, págs. 339–357, doi :10.1007/978-3-642-34931-7_20, ISBN 978-3-642-34930-0, archivado desde el original (PDF) el 2 de mayo de 2015 , consultado el 10 de diciembre de 2014

Enlaces externos

• Sitio web del FSB para la competición SHA-3