La reducción de espacio ocurre, pero no de esa manera.
Se supone que las funciones hash seguras se comportan como lo haría una función aleatoria en promedio (es decir, una función elegida uniformemente entre el conjunto de funciones posibles con las mismas longitudes de entrada y salida). Se sabe que MD5 y SHA-1 no son seguros en última instancia (porque podemos encontrar colisiones para ellos más eficientemente de lo que podríamos con una función aleatoria), pero todavía son aproximaciones lo suficientemente cercanas aquí (aún así, no debe usarlas excepto para la interoperabilidad con implementaciones heredadas; realmente debería usar una función más moderna y segura como SHA-256).
Entonces, asumiendo una salida de n -bit, si hash todas las 2 n cadenas de n bits , puede esperar que todas las salidas cubran aproximadamente el 63.21% del espacio de 2n valores posibles de salida (eso es 1- (1 / e )). Pierdes un poco más de un tercio del espacio. Sin embargo , si vuelve a repetir todos estos valores obtenidos, perderá mucho menos que un tercio de ellos. El factor de reducción no es constante para cada ronda. Después de algunas rondas, la reducción adicional por ronda es muy pequeña.
Cuando hash un valor dado muchas veces sucesivamente, en realidad estás recorriendo una "estructura rho", como se muestra en la siguiente figura:
Estaestructurasellamaasíporquesepareceaproximadamentealaletragriegaρ,“rho”.Cadapuntoesunvalorden-bit,ycadaflecharepresentalaaplicacióndesufunciónhash.Elpuntoazulestupuntodepartida.Entonces,laideaesquealaplicarlafunciónlosuficientevariasveces,terminasenunciclo.Unavezenelciclo,lasaplicacionessucesivasdelafunciónhashyanoreducenelespaciodevaloresposibles:simplementecaminasalrededordelciclo,indefinidamente.Laduracióndelcicloes,entonces,eltamañodeespaciomínimoquepuedesalcanzar.
Laslongitudestantodela"cola" (los valores que obtiene antes de ingresar al ciclo) como del "ciclo" son, en promedio, 2 n / 2 . Por lo tanto, para una función hash con una salida de 128 bits, las aplicaciones sucesivas no reducirán el espacio por debajo de 2 64 , un valor bastante grande; alcanzar un espacio mínimo tomará, en promedio, 2 64 evaluaciones de la función hash, lo cual es costoso.
Encontrar el ciclo recorriendo la estructura rho es en realidad la base de algoritmo de búsqueda de ciclos de Floyd , que es uno de los algoritmos genéricos que se pueden utilizar para crear colisiones para una función de hash: en la estructura rho, en el punto donde la cola está unida al ciclo, hay una colisión (dos valores distintos que tienen el mismo valor). Para una función hash criptográficamente segura, se supone que encontrar colisiones es difícil; en particular, el algoritmo de Floyd no debe ser computacionalmente factible, lo que se logra al hacer que n sea lo suficientemente grande (por ejemplo, n = 256 para SHA-256: esto aumenta el costo del algoritmo de Floyd a 2 128 , es decir, no es realista factible en la Tierra).
En otras palabras: si selecciona una función hash segura, con un resultado suficientemente amplio (un requisito previo para estar seguro), entonces no podrá alcanzar el ciclo y / o camine, y su seguridad no sufrirá ninguna "reducción de espacio". Corolario: si tiene un problema de reducción de espacio, entonces no está utilizando una función hash segura, y ese es el problema que necesita solucionar. Por lo tanto, utilice SHA-256.