math - opciones - ¿Las funciones hash criptográficas alcanzan cada valor posible, p. Ej., Son surjective?

huella hash

Question

Tome una función hash binaria de uso común, por ejemplo, SHA-256. Como su nombre lo indica, emite un valor de 256 bit.

Deje A ser el conjunto de todos los posibles valores binarios de 256 bits. A es extremadamente grande, pero finito.

Deje B ser el conjunto de todos los valores binarios posibles. B es infinito.

Deje que C sea ​​el conjunto de valores obtenidos ejecutando SHA-256 en cada miembro de B. Obviamente, esto no se puede hacer en la práctica, pero supongo que aún podemos hacer un análisis matemático de él.

Mi pregunta: por necesidad, C ⊆ A. Pero, ¿ C = A ?

EDITAR: Como se señaló en algunas respuestas, esto es totalmente dependiente de la función tiene en cuestión. Entonces, si conoce la respuesta para cualquier función hash en particular, ¡dígalo!

Answer 1

No necesariamente. El principio del casillero declara que una vez que se ha generado un hash más allá del tamaño de A, existe una probabilidad de colisión de 1, pero no indica que se haya generado cada elemento de A.

Answer 2

No necesariamente. Eso dependería de la función hash.

Probablemente sería ideal si la función hash fuera surjective , pero hay cosas que suelen ser más importantes, como una baja probabilidad de colisiones.

Answer 3

No siempre es el caso. Sin embargo, la calidad requerida para un algoritmo hash es:

• Cardinalidad de B
• Repartición de hashes en B (cada valor en B debe tener la misma probabilidad de ser un hash)

Answer 4

Primero, señalemos que SHA-256 no acepta todas las cadenas binarias posibles como entrada. Según lo definido por FIPS 180-3 , SHA-256 acepta como entrada cualquier secuencia de bits de longitud inferior a 2 ^ 64 bits (es decir, no más de 18446744073709551615 bits). Esto es muy común; todas las funciones hash están de alguna manera limitadas en la longitud de entrada formal. Una razón es que la noción de seguridad se define con respecto al costo computacional; hay un umbral sobre el poder computacional que cualquier atacante puede reunir. Las entradas más allá de una longitud determinada requerirían más de esa potencia de cálculo máxima para evaluar simplemente la función. En resumen, los criptógrafos son muy cautelosos con los infinitos, porque los infinitos tienden a evitar que la seguridad sea definida, y mucho menos cuantificada. Por lo tanto, su conjunto de entrada C debe restringirse a secuencias de hasta 2 ^ 64-1 bits.

Dicho esto, veamos qué se sabe sobre la función surgida de la función hash.

Las funciones Hash intentan emular un oráculo aleatorio , un objeto conceptual que selecciona salidas al azar bajo la única restricción de que "recuerda" las entradas y salidas anteriores, y, si se le da una entrada ya vista, devuelve el mismo resultado que anteriormente. Por definición, un oráculo al azar puede probarse surjective solo probando entradas y agotando el espacio de salida. Si la salida tiene un tamaño n bits, entonces se espera que sean necesarias aproximadamente 2 ^ (2n) entradas distintas para agotar el espacio de salida de tamaño 2 ^ n . Para n = 256 , esto significa que hashing alrededor de 2 ^ 512 mensajes (por ejemplo, todos los mensajes de 512 bits) debería ser suficiente (en promedio). SHA-256 acepta entradas mucho más largas que 512 bits (de hecho, acepta entradas de hasta 18446744073709551615 bits), por lo que parece altamente plausible que SHA-256 sea surjective.

Sin embargo , no se ha demostrado que SHA-256 sea surjective, y eso se espera . Como se muestra arriba, una prueba de surjectivity para un oráculo al azar requiere una gran cantidad de poder de cómputo, sustancialmente más que meros ataques como preimágenes ( 2 ^ n ) y colisiones ( 2 ^ (n / 2) ). En consecuencia, una buena función hash "no debería" permitir que una propiedad como la surjectivity sea realmente probada. Sería muy sospechoso: la seguridad de la función hash proviene de la intratabilidad de su estructura interna, y esa intratabilidad debería oponerse firmemente a cualquier intento de análisis matemático.

Como consecuencia, la surjectivity no está formalmente probada para ninguna función hash decente, y ni siquiera para las funciones hash "rotas" como MD4. Solo es "altamente sospechoso" (un oráculo al azar con entradas mucho más largas que la salida debe ser surjective).

Answer 5

Realmente depende de la función hash. Si usa esta función hash válida:

Int256 Hash (string input) {
    return 0;
}

entonces es obvio que C! = A. Entonces el "por ejemplo, SHA256" es una nota bastante importante a considerar.

Para responder a su pregunta real: lo creo, pero estoy adivinando. Wikipedia no proporciona ninguna información significativa sobre esto.