algorithms - ¿Alguna porción de 64 bits de un hash de 128 bits es a prueba de colisiones como un hash de 64 bits?
murmur3 (3)
Debido al efecto de avalancha, un hash fuerte es aquel en el que un solo bit de cambio en la fuente da como resultado que la mitad de los hash de rotación de hash en promedio. Para un buen hash, entonces, el "hashness" se distribuye uniformemente, por lo que cada sección o segmento se ve afectado por una cantidad igual y uniformemente distribuida de bits de origen, y por lo tanto es tan fuerte como cualquier otro segmento de la misma longitud de bits. ser.
Estaría de acuerdo con el compañero de trabajo 1 siempre que el hash tenga buenas propiedades y una distribución uniforme.
Estamos tratando de resolver un debate interno en nuestro equipo de desarrollo:
Estamos buscando una función hash PHP de 64 bits. Encontramos una implementación PHP de MurmurHash3 , pero MurmurHash3 es de 32 bits o de 128 bits, no de 64 bits.
El compañero de trabajo n.º 1 cree que para producir un hash de 64 bits de MurmurHash3, simplemente podemos dividir los primeros (o últimos, o cualquiera) 64 bits del hash de 128 bits y que será tan resistente a la colisión como un nativo Función hash de 64 bits.
El compañero de trabajo n.º 2 cree que debemos encontrar una función de hash de 64 bits nativa para reducir las colisiones y que los segmentos de 64 bits de un hash de 128 bits no serán tan resistentes a las colisiones como un hash de 64 bits nativo.
¿Quién es correcto?
¿Cambia la respuesta si tomamos los primeros (o últimos, o alguno) de 64 bits de un hash criptográfico como SHA1 en lugar de Murmur3?
Esta pregunta parece incompleta sin que esto sea mencionado:
Algunos hashes son hash demostrablemente perfect para una clase específica de entradas (por ejemplo, para entradas de longitud n para un valor razonable de n ). Si trunca ese hash, es probable que destruya esa propiedad, en cuyo caso, por definición, aumenta la tasa de colisiones de cero a no cero y ha debilitado el hash en ese caso de uso.
No es el caso general, pero es un ejemplo de una preocupación legítima al truncar hashes.
Si tuviera valores aleatorios reales, distribuidos uniformemente, entonces "rebanar" arrojaría exactamente los mismos resultados que si hubiera comenzado con el valor más pequeño desde el principio. Para ver por qué, considere este ejemplo muy simple: Digamos que su generador aleatorio genera 3 bits aleatorios, pero solo necesita un bit aleatorio para trabajar. Asumamos que la salida es
b1 b2 b3
Los valores posibles son
000, 001, 010, 011, 100, 101, 110, 111
y todos deben ocurrir con igual probabilidad de 1/8. Ahora, sin importar el bit que se desprenda de esos tres para su propósito, el primero, el segundo o el tercero, la probabilidad de tener un ''1'' siempre será 1/2, independientemente de la posición - y lo mismo es cierto para un ''0 ''.
Puede escalar fácilmente este experimento al caso de 64 de 128 bits: independientemente de los bits que corte, la probabilidad de terminar con un uno o un cero en una determinada posición será de la mitad. Lo que esto significa es que si se tomara una muestra de una variable aleatoria distribuida uniformemente, el corte no haría que la probabilidad de colisiones sea más o menos probable.
Ahora, una buena pregunta es si las funciones aleatorias son realmente lo mejor que podemos hacer para evitar colisiones. Pero resulta que se puede demostrar que la probabilidad de encontrar colisiones aumenta cada vez que una función se desvía de la aleatoria.
Funciones hash criptográficas: el compañero de trabajo # 1 gana
El problema en la vida real es que las funciones hash no son aleatorias en absoluto, por el contrario, son aburridamente deterministas. Pero un objetivo de diseño de las funciones hash criptográficas es el siguiente: si no conociéramos su estado inicial, entonces su salida sería indistinguible computacionalmente de una función aleatoria real, es decir, no hay una manera computacionalmente eficiente de diferenciar entre la salida hash. y valores aleatorios reales. Esta es la razón por la que consideraría un hash como un tipo de ruptura si pudiera encontrar un "distintivo", un método para distinguir el hash de valores aleatorios reales con una probabilidad superior a la mitad. Desafortunadamente, realmente no podemos probar estas propiedades para los hash criptográficos existentes, pero a menos que alguien las rompa, podemos asumir que estas propiedades se mantienen con cierta confianza. Este es un ejemplo de un paper sobre un distintivo para una de las presentaciones SHA-3 que ilustra el proceso.
Para resumir, a menos que se encuentre un distintivo para un hash criptográfico determinado, el corte es perfectamente correcto y no aumenta la probabilidad de una colisión.
Funciones hash no criptográficas: el compañero de trabajo nº 2 podría ganar
Los hashes no criptográficos no tienen que satisfacer el mismo conjunto de requisitos que los hashes criptográficos. Por lo general, se los define como muy rápidos y satisfacen ciertas propiedades "en condiciones sanas / benevolentes", pero podrían quedarse cortos si alguien intenta manipularlos de manera maliciosa. Un buen ejemplo de lo que esto significa en la práctica es el ataque de complejidad computacional en las implementaciones de tablas hash ( hashDoS ) presentadas este año. En condiciones normales, los hashes no criptográficos funcionan perfectamente bien, pero su resistencia a la colisión puede verse seriamente socavada por algunas entradas inteligentes. Esto no puede suceder con las funciones criptográficas de hash, porque su definición misma requiere que sean inmunes a todo tipo de entradas inteligentes.
Debido a que es posible, a veces incluso bastante fácil, encontrar un distintivo como el de arriba para la salida de hashes no criptográficos, podemos decir inmediatamente que no califican como funciones de hash criptográficas. Ser capaz de notar la diferencia significa que en algún lugar hay un patrón o sesgo en la salida.
Y este hecho solo implica que se desvían más o menos de una función aleatoria, y por lo tanto (después de lo que dijimos anteriormente) las colisiones son probablemente más probables de lo que serían para las funciones aleatorias. Finalmente, dado que las colisiones se producen con mayor probabilidad para los 128 bits completos ya, esto no mejorará con salidas de datos más cortas, las colisiones probablemente sean aún más probables en ese caso.
tl; dr Estás a salvo con una función criptográfica de hash al truncarla. Pero está mejor con una función hash criptográfica "nativa" de 64 bits en comparación con el truncamiento de un hash no criptográfico con una salida mayor a 64 bits.