¿Cuál es el riesgo del hash de puntos / ciclos fijos?

Supongamos que tiene una función pseudoaleatoria con una salida de n bits. Una buena función de hash con una sal dada debería comportarse como un PRF.

La estructura promedio general de un PRF, con respecto a la aplicación repetida, es tener un gran "ciclo": si hash y rehash repetidamente, en algún punto, ingresará un ciclo y obtendrá un valor que ya encontrado. La duración promedio del ciclo será aproximadamente 2^n/2 . La cantidad de pasos que deberá realizar antes de alcanzar el ciclo también será sobre 2^n/2 . Casi todos los valores iniciales lo llevarán, en última instancia, a este ciclo interno. Puede haber algunos valores iniciales que no lo llevarán a este ciclo; incluso podría haber algunos puntos fijos (hay una probabilidad del 63,2% de que exista al menos un punto fijo); pero el número de tales potencialmente Los puntos problemáticos no serán más, en promedio, que 2^n/2 .

Para resumir, si n es lo suficientemente grande como para que se descuide una probabilidad de 2^-n/2 , entonces las cosas están bien . En particular, si n = 256 (está usando SHA-256), entonces puede dejar de preocuparse. Incluso con MD5 ( n = 128 ), los ciclos cortos son lo suficientemente raros como para que no impliquen ningún problema de seguridad real.

Un ciclo de espacio completo significaría que su función hash no es un PRF, sino una permutación, y una permutación con un solo ciclo. Es posible construir una permutación unidireccional, pero es mucho más difícil que una función unidireccional para la que parece que puede juntar algunas operaciones y rotaciones a nivel de bits; para una permutación, necesita matemáticas (por ejemplo, con exponentiation modulo un entero no primo) y esto implicará algunos problemas adicionales (la permutación será en promedio de una sola vía, pero puede haber valores para los que no lo será).