Función de compresión unidireccional

En criptografía , una función de compresión unidireccional es aquella que transforma dos entradas de longitud fija en una salida de longitud fija. ^{[ 1 ]} La transformación es "unidireccional" , lo que significa que, dada una salida particular, es difícil calcular entradas que se compriman hasta alcanzar dicha salida. Las funciones de compresión unidireccional no están relacionadas con los algoritmos de compresión de datos convencionales , que pueden invertir los datos originales de forma exacta (compresión sin pérdidas) o aproximada (compresión con pérdidas).

Las funciones de compresión unidireccional se utilizan, por ejemplo, en la construcción Merkle-Damgård dentro de las funciones hash criptográficas .

Las funciones de compresión unidireccional suelen construirse a partir de cifrados de bloques . Algunos métodos para convertir cualquier cifrado de bloques convencional en una función de compresión unidireccional son Davies-Meyer , Matyas-Meyer-Oseas , Miyaguchi-Preneel (funciones de compresión de longitud de bloque simple) y MDC-2/Meyer-Schilling , MDC-4 , Hirose (funciones de compresión de longitud de bloque doble). Estos métodos se describen con detalle más adelante. ( MDC-2 es también el nombre de una función hash patentada por IBM ).

Otro método es 2BOW (o NBOW en general), que es una "función hash de alta tasa y longitud de bloque múltiple basada en cifrados de bloques" ^{[ 2 ]} y que normalmente alcanza tasas (asintóticas) entre 1 y 2, independientemente del tamaño del hash (solo con una pequeña sobrecarga constante). Este método aún no ha sido objeto de un análisis de seguridad serio, por lo que debe manejarse con precaución.

Una función de compresión combina dos entradas de longitud fija y produce una única salida de longitud fija del mismo tamaño que una de las entradas. Esto también puede interpretarse como que la función de compresión transforma una entrada grande de longitud fija en una salida más corta de longitud fija.

Por ejemplo, la entrada A podría ser de 128 bits, la entrada B también de 128 bits y ambas se comprimen juntas para obtener una única salida de 128 bits. Esto equivale a tener una única entrada de 256 bits comprimida a una única salida de 128 bits.

Algunas funciones de compresión no reducen la entrada a la mitad, sino que utilizan otro factor. Por ejemplo, la entrada A podría ser de 256 bits y la entrada B de 128 bits, las cuales se comprimen a una única salida de 128 bits. Es decir, un total de 384 bits de entrada se comprimen en 128 bits de salida.

La mezcla se realiza de tal manera que se logra un efecto de avalancha completo . Es decir, cada bit de salida depende de cada bit de entrada.

Una función unidireccional es una función fácil de calcular pero difícil de invertir. Una función de compresión unidireccional (también llamada función hash) debe tener las siguientes propiedades:

• Fácil de calcular: Si tienes alguna entrada o entradas, es fácil calcular la salida.
• Resistencia a la preimagen: Si un atacante solo conoce la salida, debería ser inviable calcular una entrada. En otras palabras, dada una salida , debería ser inviable calcular una entrada tal que .${\displaystyle h}$${\displaystyle m}$${\displaystyle \operatorname {hash} (m)=h}$
• Segunda resistencia a la preimagen: Dada una entrada cuya salida es , debería ser inviable encontrar otra entrada que tenga la misma salida , es decir .${\displaystyle m_{1}}$${\displaystyle h}$${\displaystyle m_{2}}$${\displaystyle h}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$
• Resistencia a colisiones: debería ser difícil encontrar dos entradas diferentes que se compriman en la misma salida, es decir, un atacante no debería poder encontrar un par de mensajes tales que . Debido a la paradoja del cumpleaños (véase también ataque de cumpleaños ), hay un 50 % de probabilidad de que se pueda encontrar una colisión en un tiempo de aproximadamente donde es el número de bits en la salida de la función hash. Por lo tanto, un ataque a la función hash no debería poder encontrar una colisión con menos de aproximadamente trabajo.${\displaystyle m_{1}\neq m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{n/2}}$${\displaystyle n}$${\displaystyle 2^{n/2}}$

Idealmente, uno desearía que la "inviabilidad" en la resistencia a la preimagen y la resistencia a la segunda preimagen significara un trabajo de aproximadamente donde es el número de bits en la salida de la función hash. Sin embargo, particularmente para la resistencia a la segunda preimagen, este es un problema difícil.${\displaystyle 2^{n}}$${\displaystyle n}$

Un uso común de las funciones de compresión unidireccional se encuentra en la construcción Merkle-Damgård dentro de las funciones hash criptográficas. La mayoría de las funciones hash más utilizadas, incluidas MD5 , SHA-1 (que está en desuso ^{[ 3 ]} ) y SHA-2, utilizan esta construcción.

Una función hash debe ser capaz de procesar un mensaje de longitud arbitraria y generar una salida de longitud fija. Esto se logra dividiendo la entrada en una serie de bloques de igual tamaño y procesándolos secuencialmente mediante una función de compresión unidireccional. Dicha función puede diseñarse específicamente para el hashing o construirse a partir de un cifrado de bloques. El último bloque procesado debe rellenarse con ceros , lo cual es fundamental para la seguridad de esta construcción.

Cuando se aplica el relleno de longitud (también llamado fortalecimiento MD), los ataques no pueden encontrar colisiones más rápido que la paradoja del cumpleaños ( siendo el tamaño del bloque en bits) si la función utilizada es resistente a colisiones. ^{[ 4 ] [ 5 ]} Por lo tanto, la construcción de hash Merkle-Damgård reduce el problema de encontrar una función hash adecuada a encontrar una función de compresión adecuada.${\displaystyle 2^{n/2}}$${\displaystyle n}$${\displaystyle f}$

Un segundo ataque de preimagen (dado un mensaje, un atacante encuentra otro mensaje para satisfacerlo ) se puede realizar según Kelsey y Schneier ^{[ 6 ]} para un mensaje de bloque de mensajes en tiempo . La complejidad de este ataque alcanza un mínimo de para mensajes largos cuando y se aproxima a cuando los mensajes son cortos.${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{k}}$${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$${\displaystyle 2^{3n/4+2}}$${\displaystyle k=2^{n/4}}$${\displaystyle 2^{n}}$

Las funciones de compresión unidireccional a menudo se construyen a partir de cifrados por bloques.

Los cifradores de bloques toman (al igual que las funciones de compresión unidireccional) dos entradas de tamaño fijo (la clave y el texto plano ) y devuelven una única salida (el texto cifrado ) que tiene el mismo tamaño que el texto plano de entrada.

Sin embargo, los cifrados de bloques modernos solo son parcialmente unidireccionales. Es decir, dados un texto plano y un texto cifrado, es imposible encontrar una clave que encripta el texto plano al texto cifrado. Pero, dados un texto cifrado y una clave, se puede encontrar un texto plano coincidente simplemente utilizando la función de descifrado del cifrado de bloques. Por lo tanto, para convertir un cifrado de bloques en una función de compresión unidireccional, es necesario añadir algunas operaciones adicionales.

Algunos métodos para convertir cualquier cifrado de bloques normal en una función de compresión unidireccional son Davies-Meyer, Matyas-Meyer-Oseas, Miyaguchi-Preneel (funciones de compresión de longitud de bloque única) y MDC-2, MDC-4, Hirose (funciones de compresión de longitud de bloque doble).

Las funciones de compresión de longitud de bloque simple generan la misma cantidad de bits que los procesados ​​por el cifrado de bloques subyacente. En consecuencia, las funciones de compresión de longitud de bloque doble generan el doble de bits.

Si un cifrado de bloques tiene un tamaño de bloque de, por ejemplo, 128 bits, los métodos de longitud de bloque simple crean una función hash con un tamaño de bloque de 128 bits y producen un hash de 128 bits. Los métodos de longitud de bloque doble generan hashes con el doble de tamaño que el tamaño de bloque del cifrado utilizado. Por lo tanto, un cifrado de bloques de 128 bits se puede convertir en una función hash de 256 bits.

Estos métodos se utilizan posteriormente dentro de la construcción de Merkle-Damgård para construir la función hash propiamente dicha. Estos métodos se describen con detalle más adelante.

Utilizar un cifrado de bloques para construir la función de compresión unidireccional de una función hash suele ser algo más lento que usar una función de compresión unidireccional especialmente diseñada en la función hash. Esto se debe a que todas las construcciones seguras conocidas realizan la programación de claves para cada bloque del mensaje. Black, Cochran y Shrimpton demostraron que es imposible construir una función de compresión unidireccional que realice una sola llamada a un cifrado de bloques con una clave fija. ^{[ 7 ]} En la práctica, se alcanzan velocidades razonables siempre que la programación de claves del cifrado de bloques seleccionado no sea una operación demasiado pesada.

Sin embargo, en algunos casos resulta más sencillo, ya que una única implementación de cifrado por bloques puede utilizarse tanto para el cifrado por bloques como para la función hash. Además, permite ahorrar espacio de código en sistemas embebidos muy pequeños, como por ejemplo tarjetas inteligentes o nodos en automóviles u otras máquinas.

Por lo tanto, la tasa hash o tasa permite vislumbrar la eficiencia de una función hash basada en una determinada función de compresión. La tasa de una función hash iterada describe la relación entre el número de operaciones de cifrado por bloques y la salida. Más precisamente, la tasa representa la relación entre el número de bits procesados ​​de la entrada , la longitud de bits de salida del cifrado por bloques y las operaciones de cifrado por bloques necesarias para producir estos bits de salida. Generalmente, el uso de menos operaciones de cifrado por bloques resulta en un mejor rendimiento general de toda la función hash, pero también conlleva un valor hash menor, lo cual podría ser indeseable. La tasa se expresa mediante la fórmula:${\displaystyle m}$${\displaystyle n}$${\displaystyle s}$${\displaystyle n}$

${\displaystyle R_{h}={\frac {\left|m_{i}\right|}{s\cdot n}}}$

La función hash solo puede considerarse segura si se cumplen al menos las siguientes condiciones:

• El cifrado por bloques no posee propiedades especiales que lo distingan de los cifrados ideales, como claves débiles o claves que conduzcan a cifrados idénticos o relacionados (puntos fijos o colisiones de claves).
• El tamaño del hash resultante es suficientemente grande. Según el ataque de cumpleaños, se desea un nivel de seguridad de ^2⁸⁰ (generalmente considerado inviable de calcular hoy en día), por lo que el tamaño del hash debería ser de al menos 160 bits.
• El último bloque se rellena correctamente antes de aplicar la función hash. (Véase la construcción de Merkle-Damgård ). El relleno de longitud se implementa y gestiona internamente en funciones hash especializadas como SHA-1 , etc.

Las construcciones presentadas a continuación: Davies-Meyer, Matyas-Meyer-Oseas, Miyaguchi-Preneel e Hirose han demostrado ser seguras bajo el análisis de caja negra . ^{[ 8 ] [ 9 ]} El objetivo es demostrar que cualquier ataque que se pueda encontrar es, como máximo, tan eficiente como el ataque de cumpleaños bajo ciertas suposiciones. El modelo de caja negra asume que se utiliza un cifrado de bloques elegido aleatoriamente de un conjunto que contiene todos los cifrados de bloques apropiados. En este modelo, un atacante puede cifrar y descifrar libremente cualquier bloque, pero no tiene acceso a una implementación del cifrado de bloques. La función de cifrado y descifrado está representada por oráculos que reciben un par de texto plano y clave o texto cifrado y clave. Los oráculos responden entonces con un texto plano o cifrado elegido aleatoriamente, si el par se solicitó por primera vez. Ambos comparten una tabla para estas tripletas, un par de la consulta y la respuesta correspondiente, y devuelven el registro, si la consulta se recibió por segunda vez. Para la demostración, se utiliza un algoritmo de detección de colisiones que realiza consultas aleatorias a los oráculos. El algoritmo devuelve 1 si dos respuestas resultan en una colisión que involucra la función hash construida a partir de una función de compresión que aplica este cifrado de bloques (0 en caso contrario). La probabilidad de que el algoritmo devuelva 1 depende del número de consultas, que determina el nivel de seguridad.

La función de compresión de longitud de bloque único de Davies-Meyer introduce cada bloque del mensaje ( ) como clave para un cifrado de bloques. Introduce el valor hash anterior ( ) como texto plano a cifrar. El texto cifrado de salida también se combina mediante XOR (⊕) con el valor hash anterior ( ) para producir el siguiente valor hash ( ). En la primera ronda, cuando no hay un valor hash anterior, utiliza un valor inicial constante preespecificado ( ).${\displaystyle m_{i}}$${\displaystyle H_{i-1}}$${\displaystyle H_{i-1}}$${\displaystyle H_{i}}$${\displaystyle H_{0}}$

En notación matemática, el método de Davies-Meyer se puede describir como:

${\displaystyle H_{i}=E_{m_{i}}{(H_{i-1})}\oplus {H_{i-1}}}$

El esquema tiene la siguiente tasa (k es el tamaño de la clave):

${\displaystyle R_{DM}={\frac {k}{1\cdot n}}={\frac {k}{n}}}$

Si el cifrado por bloques utiliza, por ejemplo, claves de 256 bits, entonces cada bloque de mensaje ( ) es un fragmento de 256 bits del mensaje. Si el mismo cifrado por bloques utiliza un tamaño de bloque de 128 bits, entonces los valores hash de entrada y salida en cada ronda son de 128 bits.${\displaystyle m_{i}}$

Existen variantes de este método que reemplazan la operación XOR con cualquier otra operación de grupo, como la suma de enteros sin signo de 32 bits.

Una propiedad notable de la construcción Davies-Meyer es que, incluso si el cifrado de bloques subyacente es totalmente seguro, es posible calcular puntos fijos para la construcción: para cualquier , se puede encontrar un valor de tal que : solo hay que establecer . ^{[ 10 ]} Esta es una propiedad que las funciones aleatorias ciertamente no tienen. Hasta ahora, ningún ataque práctico se ha basado en esta propiedad, pero se debe tener en cuenta esta "característica". Los puntos fijos se pueden usar en un segundo ataque de preimagen (dado un mensaje , el atacante encuentra otro mensaje que satisfaga ) de Kelsey y Schneier ^{[ 6 ]} para un mensaje de bloque de mensajes en tiempo . Si la construcción no permite la creación fácil de puntos fijos (como Matyas-Meyer-Oseas o Miyaguchi-Preneel), entonces este ataque se puede realizar en tiempo . En ambos casos, la complejidad es superior pero inferior cuando los mensajes son largos y que cuando los mensajes se acortan la complejidad del ataque se aproxima a .${\displaystyle m}$${\displaystyle h}$${\displaystyle E_{m}(h)\oplus h=h}$${\displaystyle h=E_{m}^{-1}(0)}$${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{k}}$${\displaystyle 3\times 2^{n/2+1}+2^{n-k+1}}$${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$${\displaystyle 2^{n/2}}$${\displaystyle 2^{n}}$${\displaystyle 2^{n}}$

La seguridad de la construcción Davies-Meyer en el Modelo de Cifrado Ideal fue demostrada por primera vez por R. Winternitz. ^{[ 11 ]}

La función de compresión unidireccional de longitud de bloque único de Matyas-Meyer-Oseas puede considerarse la dual (la opuesta) de la de Davies-Meyer.

Alimenta cada bloque del mensaje ( ) como el texto plano que se va a cifrar. El texto cifrado de salida también se combina mediante XOR (⊕) con el mismo bloque del mensaje ( ) para producir el siguiente valor hash ( ). El valor hash anterior ( ) se utiliza como clave para el cifrado de bloques. En la primera ronda, cuando no hay un valor hash anterior, utiliza un valor inicial constante preespecificado ( ).${\displaystyle m_{i}}$${\displaystyle m_{i}}$${\displaystyle H_{i}}$${\displaystyle H_{i-1}}$${\displaystyle H_{0}}$

Si el cifrado por bloques tiene diferentes tamaños de bloque y clave, el valor hash ( ) tendrá un tamaño incorrecto para usarlo como clave. El cifrado también podría tener otros requisitos especiales para la clave. Entonces, el valor hash se pasa primero a través de la función para convertirlo/rellenarlo y que se ajuste como clave para el cifrado.${\displaystyle H_{i-1}}$${\displaystyle g}$

En notación matemática, el método de Matyas-Meyer-Oseas se puede describir como:

${\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus m_{i}}$

El plan tiene la siguiente tasa:

${\displaystyle R_{MMO}={\frac {n}{1\cdot n}}=1}$

Un segundo ataque de preimagen (dado un mensaje, un atacante encuentra otro mensaje que lo satisfaga ) se puede realizar según Kelsey y Schneier ^{[ 6 ]} para un mensaje de bloque de mensajes en tiempo . La complejidad es superior pero inferior cuando los mensajes son largos, y que cuando los mensajes se acortan la complejidad del ataque se aproxima a .${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{k}}$${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$${\displaystyle 2^{n/2}}$${\displaystyle 2^{n}}$${\displaystyle 2^{n}}$

La función de compresión unidireccional de longitud de bloque único de Miyaguchi-Preneel es una variante extendida de Matyas-Meyer-Oseas. Fue propuesta independientemente por Shoji Miyaguchi y Bart Preneel .

Alimenta cada bloque del mensaje ( ) como el texto plano que se va a cifrar. El texto cifrado de salida se combina mediante XOR (⊕) con el mismo bloque del mensaje ( ) y luego también se combina mediante XOR con el valor hash anterior ( ) para producir el siguiente valor hash ( ). El valor hash anterior ( ) se utiliza como clave para el cifrado de bloques. En la primera ronda, cuando no hay un valor hash anterior, utiliza un valor inicial constante preespecificado ( ).${\displaystyle m_{i}}$${\displaystyle m_{i}}$${\displaystyle H_{i-1}}$${\displaystyle H_{i}}$${\displaystyle H_{i-1}}$${\displaystyle H_{0}}$

Si el cifrado por bloques tiene diferentes tamaños de bloque y clave, el valor hash ( ) tendrá un tamaño incorrecto para usarlo como clave. El cifrado también podría tener otros requisitos especiales para la clave. Entonces, el valor hash se pasa primero a través de la función para convertirlo/rellenarlo y que se ajuste como clave para el cifrado.${\displaystyle H_{i-1}}$${\displaystyle g}$

En notación matemática, el método Miyaguchi-Preneel se puede describir como:

${\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus H_{i-1}\oplus m_{i}}$

El plan tiene la siguiente tasa:

${\displaystyle R_{MP}={\frac {n}{1\cdot n}}=1}$

Los roles de y pueden intercambiarse, de modo que se cifra bajo la clave , lo que convierte a este método en una extensión de Davies-Meyer.${\displaystyle m_{i}}$${\displaystyle H_{i-1}}$${\displaystyle H_{i-1}}$${\displaystyle m_{i}}$

Un segundo ataque de preimagen (dado un mensaje, un atacante encuentra otro mensaje que lo satisfaga ) se puede realizar según Kelsey y Schneier ^{[ 6 ]} para un mensaje de bloque de mensajes en tiempo . La complejidad es superior pero inferior cuando los mensajes son largos, y que cuando los mensajes se acortan la complejidad del ataque se aproxima a .${\displaystyle m_{1}}$${\displaystyle m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{k}}$${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$${\displaystyle 2^{n/2}}$${\displaystyle 2^{n}}$${\displaystyle 2^{n}}$

La función de compresión unidireccional de doble longitud de bloque de Hirose ^{[ 9 ]} consiste en un cifrado de bloques más una permutación . Fue propuesta por Shoichi Hirose en 2006 y se basa en un trabajo ^{[ 12 ]} de Mridul Nandi .${\displaystyle p}$

Utiliza un cifrado de bloques cuya longitud de clave es mayor que la longitud del bloque y produce un hash de tamaño . Por ejemplo, cualquiera de los candidatos AES con una clave de 192 o 256 bits (y un bloque de 128 bits).${\displaystyle k}$${\displaystyle n}$${\displaystyle 2n}$

Cada ronda acepta una porción del mensaje que tiene bits de longitud y la utiliza para actualizar dos valores de estado de bits y .${\displaystyle m_{i}}$${\displaystyle kn}$${\displaystyle n}$${\displaystyle G}$${\displaystyle H}$

Primero, se concatena para producir una clave . Luego, los dos valores de retroalimentación se actualizan de acuerdo con:${\displaystyle m_{i}}$${\displaystyle H_{i-1}}$${\displaystyle K_{i}}$

• ${\displaystyle G_{i}=E_{K_{i}}(G_{i-1})\oplus G_{i-1}}$
• ${\displaystyle H_{i}=E_{K_{i}}(p(G_{i-1}))\oplus p(G_{i-1})}$

${\displaystyle p(G_{i-1})}$es una permutación arbitraria sin punto fijo en un valor de bits, típicamente definida como para una constante arbitraria distinta de cero (todos unos pueden ser una elección conveniente).${\displaystyle n}$${\displaystyle p(x)=x\oplus c}$${\displaystyle c}$

Cada cifrado se asemeja a la construcción estándar de Davies-Meyer. La ventaja de este esquema sobre otros esquemas propuestos de doble longitud de bloque es que ambos cifrados utilizan la misma clave, por lo que el esfuerzo de programación de claves puede compartirse.

El resultado final es . El esquema tiene la tasa relativa al cifrado del mensaje con el cifrado.${\displaystyle H_{t}||G_{t}}$${\textstyle R_{Hirose}={\frac {k-n}{2n}}}$

Hirose también proporciona una prueba en el Modelo de Cifrado Ideal.

La construcción de esponja se puede utilizar para construir funciones de compresión unidireccional. ^{[ 3 ]}

• Whirlpool : una función hash criptográfica construida utilizando la construcción Miyaguchi-Preneel y un cifrado de bloques similar a Square y AES .
• CBC-MAC , OMAC y PMAC : métodos para convertir cifrados de bloques en códigos de autenticación de mensajes (MAC).