En criptografía , las funciones hash basadas en síndrome rápido (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 otras funciones hash criptográficas que se utilizan hoy en día, se puede demostrar que FSB es seguro hasta cierto punto. Más exactamente, se puede demostrar que romper FSB es al menos tan difícil como resolver cierto problema NP-completo conocido como decodificación de síndrome regular, por lo que FSB es probadamente seguro . Aunque no se sabe si los problemas NP-completos se pueden resolver en tiempo polinomial , a menudo se supone que no lo son.
General | |
---|---|
Diseñadores | Daniel Augot , Matthieu Finiasz , Nicolas Sendrier |
Publicado por primera vez | 2003 |
Derivado de | Criptosistema McEliece y criptosistema Niederreiter |
Sucesores | Función hash basada en síndrome rápido mejorada |
Relacionado con | Función hash basada en el síndrome |
Detalle | |
Tamaños de resumen | Escalable |
Se han propuesto varias versiones de FSB, la última de las cuales se presentó al concurso 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 finalmente se rompieron. [2] Sin embargo, el diseño de la última versión de FSB ha tenido en cuenta este ataque y sigue siendo seguro para todos los ataques conocidos actualmente.
Como de costumbre, la seguridad demostrable tiene un costo. 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 resuelto en versiones recientes simplemente comprimiendo la salida mediante otra función de compresión llamada Whirlpool . Sin embargo, aunque los autores argumentan que agregar esta última compresión no reduce la seguridad, hace imposible una prueba de seguridad formal. [3]
Descripción de la función hash
Empezamos con una función de compresión. con parámetros tal que y . Esta función solo funcionará en mensajes con longitud; será el tamaño de la salida. Además, queremos y ser números naturales, donde denota el logaritmo binario . La razón por es que queremos para ser una función de compresión, por lo que la entrada debe ser mayor que la salida. Más adelante usaremos la construcción Merkle-Damgård para extender el dominio a entradas de longitudes arbitrarias.
La base de esta función consiste en un binario (elegido al azar) matriz que actúa sobre un mensaje de bits por multiplicación de matrices . Aquí codificamos el-mensaje de bits como vector en , la -espacio vectorial dimensional sobre el campo de dos elementos, por lo que la salida será un mensaje de bits.
Por motivos de seguridad, así como para obtener una velocidad de hash más rápida, queremos usar solo "palabras regulares de peso ”Como entrada para nuestra matriz.
Definiciones
- Un mensaje se llama palabra de peso. y longitud si consta de bits y exactamente de esos bits son unos.
- Una palabra de peso y longitud se llama regular si en cada intervalo contiene exactamente una entrada distinta de cero para todos . 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.
La función de compresión
Hay exactamente diferentes palabras regulares de peso y longitud , entonces necesitamos exactamente bits de datos para codificar estas palabras regulares. Arreglamos 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:
- entrada: un mensaje de tamaño
- convertir a una palabra regular de longitud y el peso
- multiplicar por la matriz
- salida: hash de tamaño
Esta versión generalmente se llama compresión basada en síndrome . Es muy lento y, en la práctica, se realiza de una manera diferente y más rápida, lo que da como resultado una compresión rápida basada en el síndrome . Nos separamos en submatrices de tamaño y arreglamos 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 el peso , ya que podemos ver una palabra como una secuencia de números entre 1 y . La función de compresión tiene el siguiente aspecto:
- Entrada: mensaje de tamaño
- Convertir a una secuencia de números entre 1 y
- Suma las columnas correspondientes de las matrices para obtener una cadena binaria de una longitud
- Salida: hash de tamaño
Ahora podemos usar la construcción 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 : hash de un mensaje utilizando matriz H
que se separa en sub-bloques , , .
Algoritmo :
- Dividimos la entrada dentro partes de longitud y obtenemos , , .
- Convertimos cada uno en un número entero y obtener , , .
- Desde la primera submatriz , elegimos la columna 2, de la segunda submatriz la columna 1 y de la tercera submatriz la columna 4.
- Sumamos las columnas elegidas y obtenemos el resultado .
Prueba de seguridad de FSB
Se ha demostrado que la construcción Merkle-Damgård basa su seguridad solo en la seguridad de la función de compresión utilizada. Entonces solo necesitamos mostrar que la función de compresión es seguro.
Una función hash criptográfica debe ser segura en tres aspectos diferentes:
- Resistencia previa a la imagen: dado un Hash h , debería ser difícil encontrar un mensaje m tal que Hash ( m ) = h
- Segunda resistencia previa a la imagen: dado un mensaje m 1 debería ser difícil encontrar un mensaje m 2 tal que Hash ( m 1 ) = Hash ( m 2 )
- Resistencia a colisiones: debería ser difícil encontrar dos mensajes diferentes m 1 y m 2 tales que Hash ( m 1 ) = Hash ( m 2 )
Tenga en cuenta que si un adversario puede encontrar una segunda imagen previa, ciertamente puede encontrar una colisión. Esto significa que si podemos demostrar que nuestro sistema es resistente a colisiones, sin duda será resistente a la segunda imagen previa.
Por lo general, en criptografía, duro significa algo así como "casi con certeza más allá del alcance de cualquier adversario al que se deba evitar que rompa el sistema". Sin embargo, necesitaremos un significado más exacto de la palabra difícil. Nos tomaremos en cuenta que "el tiempo de ejecución de cualquier algoritmo que encuentre una colisión o una imagen previa 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 previa a la imagen y decodificación de 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 del síndrome es originalmente un problema de la teoría de la codificación, pero su NP-completo lo 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: dada matrices de dimensión y un poco de cuerda de longitud tal que existe un conjunto de columnas, una en cada , sumando a . Encuentra tal conjunto de columnas.
Se ha demostrado que este problema es NP-completo mediante una reducción de la coincidencia tridimensional . Nuevamente, aunque no se sabe si existen algoritmos de tiempo polinomial para resolver problemas NP-completos, ninguno se conoce y encontrar uno sería un gran descubrimiento.
Es fácil ver que encontrar una imagen previa de un hash dado es exactamente equivalente a este problema, por lo que el problema de encontrar imágenes previas en FSB también debe ser NP-completo.
Todavía tenemos que demostrar la resistencia a las colisiones. Para esto, necesitamos otra variación NP-completa de RSD: decodificación de síndrome nulo 2-regular .
Resistencia a colisiones y decodificación del síndrome nulo 2-regular (2-RNSD)
Definición de 2-RNSD: Dado matrices de dimensión y un poco de cuerda de longitud tal que existe un conjunto de columnas, dos o cero en cada , sumando cero. . Encuentra tal conjunto de columnas.
También se ha demostrado que 2-RNSD es NP-completo mediante una reducción de la coincidencia tridimensional .
Al igual que RSD es, en esencia, equivalente a encontrar una palabra normal tal que , 2-RNSD es equivalente a encontrar una palabra regular de 2 tal que . Una palabra de longitud regular de 2 y el peso es una pequeña cadena de longitud tal que en cada intervalo exactamente dos o cero entradas son iguales a 1. Tenga en cuenta que una palabra regular 2 es solo la suma de dos palabras regulares.
Supongamos que hemos encontrado una colisión, por lo que tenemos Hash ( m 1 ) = Hash ( m 2 ) con. Entonces podemos encontrar dos palabras regulares y tal que . Entonces tenemos; es una suma de dos palabras regulares diferentes y, por lo tanto, debe ser una palabra regular de 2 cuyo hash sea 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.
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 probar, los autores argumentan que esta última compresión no reduce la seguridad. Tenga en cuenta que incluso si uno pudiera encontrar colisiones en Whirlpool, aún necesitaría encontrar las imágenes previas de colisiones en la función de compresión FSB original para encontrar una colisión en FSB.
Ejemplos de
Al resolver RSD, nos encontramos en la situación opuesta a la del hash. Usando los mismos valores que en el ejemplo anterior, se nos da separado en subbloques y una cadena . Se nos pide que busquemos en cada subbloque exactamente una columna de modo que todas sumen. La respuesta esperada es entonces, , . Se sabe que esto es difícil de calcular para matrices grandes.
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 desde, ninguna columna de columna 0 y 2 de . Son posibles más soluciones, por ejemplo, es posible que no se utilicen columnas de.
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 dura 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 seguridad 2 ^ 128 reivindicada. Se muestra que la función hash ofrece una preimagen mínima o una resistencia a la colisión cuando el espacio del mensaje se elige de una manera específica.
Resultados de seguridad prácticos
La siguiente tabla muestra la complejidad de los ataques más conocidos contra FSB.
Tamaño de salida (bits) | Complejidad de la búsqueda de colisiones | Complejidad de la inversión |
---|---|---|
160 | 2 100,3 | 2 163,6 |
224 | 2 135,3 | 2 229,0 |
256 | 2 190,0 | 2 261,0 |
384 | 2 215,5 | 2 391,5 |
512 | 2 285,6 | 2 527,4 |
Génesis
FSB es una versión acelerada de la función hash basada en síndrome (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 usar la matriz de verificación de paridad de un código Goppa permutado , SB usa una matriz aleatoria. Desde el punto de vista de la seguridad, esto solo puede fortalecer el sistema.
Otras propiedades
- Tanto el tamaño de 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 malas instancias y hay que tener cuidado al elegir la matriz. .
- La matriz utilizada en la función de compresión puede aumentar de tamaño en determinadas situaciones. Esto podría ser una limitación al intentar utilizar FSB en dispositivos con limitaciones de memoria. Este problema se resolvió en la función hash relacionada llamada FSB mejorado, que todavía es demostrablemente seguro , pero se basa en suposiciones un poco más sólidas.
Variantes
En 2007, se publicó IFSB. [4] En 2010, se publicó S-FSB, que es un 30% más rápido que el original. [5]
En 2011, DJ Bernstein y Tanja Lange publicaron RFSB, que es 10 veces más rápido que el FSB-256 original. [6] Se demostró que RFSB se ejecuta muy rápido en el FPGA Spartan 6 , alcanzando un rendimiento de alrededor de 5 Gbit / s. [7]
Referencias
- ^ Augot, D .; Finiasz, M .; Sendrier, N. (2003), una función hash criptográfica rápida y demostrablemente segura (PDF)
- ^ Saarinen, Markku-Juhani O. (2007), Ataques de linealización contra hashes basados en el síndrome , Progreso en criptología - INDOCRYPT 2007
- ^ Finiasz, M .; Gaborit, P .; Sendrier, N. (2007), Funciones hash criptográficas mejoradas basadas en el síndrome rápido (PDF) , ECRYPT Hash Workshop 2007
- ^ https://www.rocq.inria.fr/secret/Matthieu.Finiasz/research/2007/finiasz-gaborit-sendrier-ecrypt-hash-workshop07.pdf
- ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 22 de diciembre de 2015 . Consultado el 10 de diciembre de 2014 .Mantenimiento de CS1: copia archivada como título ( enlace )
- ^ http://cr.yp.to/codes/rfsb-20110214.pdf
- ^ https://www.ei.rub.de/media/sh/veroeffentlichungen/2012/12/10/embedded_syndrome-based_hashing.pdf
enlaces externos
- Sitio web del FSB para la competencia SHA-3