Colisiones PBKDF2-HMAC

Question

Tratando de comprender la propiedad bien conocida de estas colisiones cuando se usa con SHA1, SHA256, etc., donde una clave dada es más grande que el tamaño de bloque de la función de resumen. En estos casos, la más pequeña de las colisiones tendrá un tamaño de 20 caracteres para SHA1 y 32 para SHA256 (la mitad de la longitud de resumen hexadecimal), por lo que ¿significa esto para fuerza bruta un PBKDF2-HMAC-SHA1 que un atacante solo debe considerar? frases de contraseña de 20 caracteres o menos? ¿Y por lo tanto 32 o menos si usa SHA256? ¿Son efectivamente inútiles las frases de contraseña más largas? Gracias.

Answer 1

"fuerza bruta a PBKDF2-HMAC-SHA1" no se trata de colisiones (al menos, si se apunta a un solo hash, o si hay sal en la entrada del hash de la contraseña). Es un ataque de preimagen .

La salida hash de SHA-1 es de 160 bits. Eso es 20 bytes (no caracteres; estas son nociones diferentes y por qué tenemos codificaciones de caracteres ). Puede tomar$2^{160}$valores. La salida de PBKDF2-HMAC-SHA-1 tiene un tamaño parametrizable que puede ser menor (por truncamiento) o mayor (esencialmente agregando resultados de 20 bytes), pero el parámetro a menudo se establece en 20 bytes, y asumiremos que .

¿Significa esto que para aplicar la fuerza bruta a un PBKDF2-HMAC-SHA-1, un atacante solo necesita considerar frases de contraseña de 20 caracteres o menos?

No se . Implica que un valor aleatorio del tamaño del hash tiene probabilidad$2^{-160}$para que coincida con un hash dado. La consecuencia práctica es que intentarlo al azar es inútil.

Las contraseñas a menudo están restringidas a un subconjunto de ASCII con aproximadamente 95 caracteres, por lo que hay aproximadamente $2^{131.714}$contraseñas de 20 caracteres de este tipo o menos (la mayoría de ellos exactamente de 20 caracteres). Si PBKDF2 está parametrizado para realizar 1000 hashes SHA-1 por PBKDF2 (que es la parametrización más baja jamás considerada por su definición, y se ha vuelto extremadamente insuficiente), el hash de la mitad de estas contraseñas requeriría más de$2^{140}$ hashes, eso se acabó $2^{40}$(un millón de millones) de veces más de lo que ha desperdiciado hasta ahora la minería de bitcoins de la humanidad. Eso no es una opción.

Por lo general, la búsqueda de contraseñas no prueba todas las contraseñas posibles con más de unos pocos caracteres; comúnmente ≈6 entre ≈70 caracteres (solo los atacantes muy poderosos podrían apuntar a todas las combinaciones de 10 caracteres cuando hay incluso un leve estiramiento de contraseña / clave ). Lo que hace la búsqueda de contraseñas es probar contraseñas que las personas podrían elegir de manera plausible, aproximadamente para disminuir la probabilidad de ser elegidas.