El nivel de seguridad en la función hash

Hay tres características principales que se buscan en una función hash:

• Resistencia a preimágenes : dado x , será difícil encontrar m de manera que h (m) = x .
• Resistencia a segundas preimágenes : dados m y h (m) , será difícil encontrar m ' (distinto de m ) tal que h (m) = h (m ') .
• Resistencia a colisiones : será difícil encontrar m y m ', diferentes entre sí, de manera que h (m) = h (m ') .

Para cualquier función hash, independientemente de su fuerza criptográfica, hay un ataque genérico que siempre funciona y se llama suerte . Para encontrar una preimagen (o una segunda preimagen), solo intente mensajes aleatorios hasta que se encuentre una coincidencia. Para encontrar una colisión, hash muchos mensajes aleatorios hasta que dos de ellos producen el mismo valor de hash. Para una salida de n -bit, la suerte funciona con un esfuerzo promedio 2ⁿ para preimágenes y segundas preimágenes, 2 ^{n / 2} para colisiones (por lo tanto, es mucho más fácil encontrar colisiones que las imágenes previas).

Lo que realmente necesita en una función hash depende del protocolo. Por ejemplo, los algoritmos de firma digital (los verdaderos, como RSA o DSA) comienzan por una invocación de la función hash, y el hash el valor se utiliza en el algoritmo propiamente dicho. Las firmas digitales funcionan con resistencia de preimagen y de segunda preimagen, a menos que esté en una configuración en la que un atacante potencial pueda elegir los datos de algunos mensajes para firmar, en cuyo caso también necesita resistencia a las colisiones.

Como regla general , apégate a n -bit salida tal que 2^n/2 invocaciones de La función hash es un esfuerzo demasiado grande. Esto significa n = 160 o menos. El uso de una función de hash con solo 128 bits de salida significa que uno puede encontrar colisiones con esfuerzo 2⁶⁴ , que es bastante costoso pero tecnológicamente viable (tal esfuerzo se realizó al menos una vez pero tomó cuatro años y miles de contribuyentes).

Para algunos protocolos es seguro descartar las colisiones (lo que no ganaría nada para el atacante) y, por lo tanto, reducir la salida a 80 bits (más o menos). Y el ejemplo es cuando la función hash se usa como parte de HMAC para verificaciones de integridad, pero solo mientras la función hash subyacente es robusta . De hecho, HMAC se basa en algunas propiedades internas de la función hash que no están directamente vinculadas con la resistencia a preimágenes o colisiones. Si la función hash es SHA-256, las cosas están bien; HMAC / SHA-256 truncado a 96 bits (usted trunca la salida de HMAC, no la función hash interna) ofrecerá seguridad hasta 2⁹⁶ , que es más que suficiente . Si la función hash es MD5 o SHA-1, entonces ... las cosas son menos claras.

Se necesita un criptógrafo capacitado para decirle qué uso de una función hash tolera el truncamiento y cuál no. Esto depende de la función hash en sí misma, cómo se usa y en qué contexto. Muchos criptógrafos entrenados responderán "no lo hagas" en la mayoría de los casos, porque una gran parte del entrenamiento en criptografía consiste en darse cuenta de que un solo ser humano nunca podrá pensar en todo. Soy criptógrafo entrenado y por eso te digo: no lo hagas .

Utilizar solo parte del resumen significa que está reduciendo el tamaño del espacio de resumen. Lo que esto significa en la práctica depende de para qué está utilizando el resumen.

Para el hashing de contraseñas basado en la web, me sentiría tentado a decir que no tendrá ningún impacto importante hasta que empiece a utilizar un subconjunto muy pequeño del resumen. Esto se debe al hecho de que incluso 16 bits es probablemente más grande que el espacio de contraseña en el que residirá el 99% de los usuarios. También se debe al hecho de que, aunque el uso de un subconjunto del resumen hace que las colisiones sean más probables en teoría, no es así. Haz que sea más fácil crear en la práctica. Si su función hash aún tiene una resistencia ininterrumpida en la preimagen, como la familia SHA2, las colisiones no serán una preocupación, de nuevo hasta que se conviertan en subconjuntos de compendios realmente pequeños en los que las colisiones se vuelvan fácilmente forzadas por la fuerza bruta.

Dicho esto, no suena como una buena idea. Y ciertamente no lo recomendaría en ningún otro lugar que no sea un entorno de comprobación de contraseñas muy lento, como la autenticación web remota.

En cuanto a una definición formal de qué tan seguro es, realmente depende de su aplicación. Si continuamos con el hash de contraseñas y asumimos que está haciendo todo lo demás correctamente: agregue sal, use un método hash lento, defienda su servidor de base de datos de manera adecuada, entonces su única preocupación comienza cuando la longitud del resumen que está utilizando se acerca (arriba) al contraseña máxima de entropía de su base de usuarios, incluida la sal. En ese momento, comienza a dañar la fortaleza de las contraseñas de los usuarios, lo que es un mal escenario.

Una función hash criptográfica tiene dos fuentes principales de seguridad:

• Si conoce H(x) , no es computacionalmente factible deducir cualquier información sobre x .
• Es computacionalmente imposible encontrar una colisión tal que H(x) = H(y) donde x y y no sean iguales.

Al reducir el tamaño de la salida de la función H , reduce la cantidad de esfuerzo requerido para encontrar una colisión. Por ejemplo, una función hash criptográfica perfecta con una salida de 8 bits tiene una probabilidad de 1 en 256 (0.391%) de colisión entre dos plaintexts seleccionados al azar. Para una salida de 32 bits, se reduce a 1 en 2 ³² , o 0.0000000233%.

Para garantizar una colisión, debe calcular 2 hashes ⁿ +1, donde n es el número de bits en la salida. El número esperado de hash antes de que se encuentre una colisión es 2 ^n-1 , ya que es cuando se ha calculado la mitad de todas las salidas de hash posibles sqrt (2 ⁿ ), lo que significaría 2 operaciones ⁶⁴ para un hash de 128 bits (gracias a Thomas por esta corrección). Las funciones hash modernas tienden a usarse en cualquier lugar entre 160 y 512 bits, lo que resulta en un hallazgo costoso de colisión por fuerza bruta.

Sin embargo, si trunca la salida de hash a un número menor de bits, perderá algo de esa resistencia a la colisión. Por cada byte que elimines, el costo del ataque se reduce en un factor de 256. Ahora, esto no es tan importante si solo cortas un par de bytes del final de un hash SHA256, pero si usas SHA1 y solo marca la mitad del hash, estás reduciendo un espacio de 2 ¹⁶⁰ a 2 ⁸⁰ , el último de los cuales se está acercando a los reinos de factibilidad en términos de fuerza bruta hallazgo de colisión.

La pregunta más importante es por qué querrías hacer esto. Solo puedo ver dos razones, una de las cuales está mal orientada:

• Desea aumentar la primera propiedad de seguridad del hash, es decir, no puede deducir ninguna información sobre x si solo conoce H(x) . Esto no es una buena idea, ya que cualquier hash criptográfico moderno ya habrá sido diseñado para ser lo más seguro posible en esta área. No hay razón para truncar esto.
• Tienes un espacio muy limitado para almacenar tus datos, por ejemplo. en un microcontrolador o SoC EEPROM. En este caso, debería estar bien si está utilizando un algoritmo hash decente y no se está truncando a menos de ~ 128 bits (16 bytes) por hash. Perderá algo de seguridad contra colisiones accidentales, pero actualmente está muy lejos de ser prácticamente vulnerable.

Las respuestas cortas a tus preguntas son "mucho" y "sí".

Muy simple, un resumen de hash teóricamente tiene una cantidad de imprevisibilidad, o entropía, igual a su longitud en dígitos binarios. Cada uno de esos bits podría ser 1 o cero, independientemente de cualquier otro sin patrón aparente. Una "función hash de 128 bits", por ejemplo, produce compendios de mensajes de 128 bits de largo y, por lo tanto, en teoría, tiene 128 bits de entropía. Para nuestros propósitos, etiquetaremos el número de bits de entropía como B .

Dada la función hash H , cualquier mensaje arbitrario M y el compendio resultante D = H (M) que es B de longitud, el hash seguro ideal (que intentan ser nuestros hash criptográficos del mundo real) tiene los siguientes comportamientos fundamentales:

• La complejidad (número promedio de operaciones) de encontrar M dado solo H y D es 2 ^B . Esto se llama encontrar una "preimagen".
• La complejidad de encontrar un segundo mensaje M₂ que difiere de M pero produce el mismo D es también 2 ^B ; esto se llama encontrar una "colisión" o "segunda preimagen".
• La complejidad de encontrar dos mensajes cualquiera M₁ y M₂ que producen el mismo D es 2 ^{B / 2} ; por el "problema del cumpleaños", a medida que aumenta el número de mensajes cuyos resúmenes se han calculado y recordado, la probabilidad de que el resumen del siguiente mensaje sea único disminuye; con un número relativamente pequeño de valores conocidos, comienza a tener una probabilidad relativamente grande de colisionar con cada mensaje nuevo.

Por ejemplo, dada una función hash de 128 bits, encontrar un mensaje que produzca un resumen de hash dado requeriría 2 ¹²⁸ = 3.4 * 10 ³⁸ cálculos de hash. Eso es un lote de trabajo; más de lo que cualquier sistema de computación coordinada disponible en la actualidad podría producir en nuestra vida. Sin embargo, encontrar cualquiera de los dos mensajes que produjeron el mismo resumen, independientemente de los mensajes o el resumen, es del orden de 2 ⁶⁴ = 1.8 * 10 ¹⁹ . Eso, créanlo o no, está bien dentro del ámbito de lo posible; el grupo de distribución.net pudo atravesar el espacio de claves de 64 bits en aproximadamente 5 años para descifrar un cifrado de 64 bits, que es equivalente en complejidad a encontrar una colisión de 128 bits.

El resultado de todo esto es que el uso de un resumen de hash más pequeño, incluido el uso de una porción de un resumen de hash más grande, reducirá el número de bits de entropía, reduciendo exponencialmente la dificultad de encontrar una colisión o una imagen previa. si tomó, por ejemplo, la mitad de este hash de 128 bits, reduce la complejidad de romperlo en una cantidad exponencial; 2 ¹²⁸ = 2 ⁶⁴ * 2 ⁶⁴ , así que al usar solo la mitad del valor hash, ha reducido la complejidad y, por lo tanto, la seguridad de el algoritmo, a aproximadamente un cuatrillionth de la seguridad que tiene el hash completo.

Tu pregunta es un poco vaga. Si está preguntando si es seguro revisar parte del resumen, entonces no. Si el hash del mensaje X es "abcdefg", y el hash (Y) es "ppppefg", y solo verificas una "parte" del mismo (los últimos 3 caracteres, "efg"), entonces tendrás el mismo valor - y tu funcionalidad hash falla.

Si quiere hacer un hash de una parte del mensaje, entonces solo puede proporcionar integridad de datos para esa parte, no el mensaje completo. Puede hacerse para el rendimiento, pero no es una buena práctica de seguridad.