¿Qué tan malo es truncar un hash?

30

Me pregunto qué tan malo es truncar un SHA1 y solo comparar, por ejemplo, los primeros 10/12 bytes, etc. Estoy trabajando con una longitud fija de 8 bytes que necesito agrupar para obtener un carácter único, pero almacenar con la huella más pequeña posible (otros 8 bytes serían buenos, pero creo que no es posible).

Un poco más de información sin sacrificar secretos profesionales:

  • Algunos blackbox toman un valor de 8 bytes, lo transforman y lo transmiten a un servidor, donde se verifica su validez contra una tabla de elementos conocidos.
  • Ni la caja negra ni el servidor deben poder conocer los 8 bytes originales.

La mejor solución sería algún tipo de relación de 1 a 1, como el cifrado asimétrico. Pero no creo que ningún mecanismo de cifrado produzca tan pocos bytes.

    
pregunta Agnar 10.11.2014 - 19:02
fuente

2 respuestas

40

No hay una respuesta absoluta, ya que depende del modelo de ataque . Al truncar el hash, facilita algunas operaciones; esto es malo si el atacante quiere realizar estas operaciones, y hacerlas más fáciles en realidad las hace factibles .

Hay tres características principales que las funciones de hash criptográficas intentan cumplir:

  • Resistencia a las imágenes previas: dado x , no debería ser posible encontrar m de manera que h (m) = x .
  • Resistencia a las segundas preimágenes: dado m , no debería ser factible encontrar m '≠ m tal que h (m) = h (m ') .
  • Resistencia a las colisiones: no debería ser factible encontrar m '≠ m de modo que h (m) = h (m') .

Para una función hash perfecta que tiene una salida de bits n , los costos de encontrar preimágenes, segundas preimágenes o colisiones serán, respectivamente, 2 n , 2 n y 2 n / 2 . Al truncar la salida de hash, reduce estos costos de manera correspondiente. Como regla general, un costo de 2 64 es muy difícil (posible, pero toma más de una docena de PC) y 2 80 no es factible.

En su caso, si una colisión es interesante para el atacante, y puede elegir qué hash, entonces el atacante intentará ingresar dos elementos de datos que implica una colisión de hash (en tu hash truncado). Truncar a 12 bytes hace que el ataque sea bastante factible, fácil si bajas a 8 bytes. Por otro lado, si todo lo que el atacante puede hacer es tratar de encontrar algún elemento de datos que coincida con un hash truncado dado (segundo preimagen), entonces con 10 o 12 bytes, esto todavía es demasiado difícil para ser factible, y con 8 bytes es simplemente "muy caro" (por lo que probablemente no valga la pena el esfuerzo).

Si no hay un atacante y solo estás luchando contra la mala suerte, el truncado a 8 bytes incurre en el riesgo de colisiones falsas; debe alcanzar su primera colisión después de (en promedio) ingresar unos cuantos miles de millones de entradas. Dependiendo de su situación, esto puede o no ser tolerable.

    
respondido por el Tom Leek 10.11.2014 - 19:31
fuente
17

En cuanto al truncamiento en general, no es necesariamente malo en absoluto. De hecho, la El algoritmo SHA ‑ 384 se define como hacer un SHA ‑ 512 (ligeramente modificado) y luego Truncando el resultado a 384 bits. Me gustaría agregar a las respuestas existentes proporcionando el material relevante sobre el truncamiento del estándar SHA.

FIPS 180‑4 , el estándar SHA, explícitamente permite truncamiento de los bits más a la izquierda.

  

Algunas aplicaciones pueden requerir una función hash con un resumen de mensaje   longitud diferente a las proporcionadas por las funciones hash en este   Estándar. En tales casos, se puede usar un resumen de mensaje truncado,   mediante el cual se aplica una función hash con una longitud de resumen de mensaje más grande   a los datos que se deben cifrar, y el resumen del mensaje resultante es   truncado seleccionando un número apropiado de los bits más a la izquierda. por   Directrices para elegir la longitud del resumen del mensaje truncado y   Información sobre sus implicaciones de seguridad para la criptografía.   aplicación que lo utiliza, consulte SP 800‑107 [SP 800‑107].

SP 800-107 explica las reglas para truncamiento:

  

Que el resumen del mensaje (acortado) se llame mensaje truncado   digiere, y sea λ la longitud deseada en bits. Un mensaje truncado   se puede utilizar el resumen si se cumplen los siguientes requisitos:

     
  1. La longitud del bloque de salida de la función hash aprobada que se utilizará será mayor que λ (es decir, L > λ).

  2.   
  3. Los bits λ más a la izquierda del resumen del mensaje de longitud completa se seleccionarán como el resumen del mensaje truncado.

         

    Por ejemplo, si se desea un resumen de mensaje truncado de 96 bits,   la función hash SHA ‑ 256 podría usarse (por ejemplo, porque es   disponible para la aplicación, y proporciona una salida más grande que   96 bits). Los 96 bits más a la izquierda del resumen de mensajes de 256 bits   generados por SHA ‑ 256 se seleccionan como el mensaje truncado   digerir, y los 160 bits más a la derecha del compendio del mensaje son   descartado.

  4.   
  5. Si se requiere resistencia de colisión, λ debe ser al menos el doble de la resistencia de colisión requerida s (en bits) para el truncado   resumen del mensaje (es decir, λ ≥ 2s).

  6.   

Finaliza la sección sobre el truncamiento con esta advertencia sobre la seguridad de un hash truncado.

  

Truncar el resumen del mensaje puede afectar la seguridad de un   solicitud. Al truncar un resumen del mensaje, la colisión esperada   la resistencia de la resistencia se reduce de L / 2 a λ / 2 (en bits). Para el   ejemplo en el elemento 2 anterior, aunque SHA-256 proporciona 128 bits   de resistencia a la colisión, la resistencia a la colisión proporcionada por   El resumen del mensaje truncado de 96 bits es la mitad de la longitud del truncado   El resumen del mensaje, que es de 48 bits, en este caso.

    
respondido por el indiv 10.11.2014 - 22:05
fuente

Lea otras preguntas en las etiquetas