" Time-Memory Trade-off " es la terminología genérica de un algoritmo que mejora (acorta) el tiempo de ejecución al usar más espacio (memoria); o, de manera similar, eso mejora el uso de la memoria (es decir, usar menos RAM o disco, o usarlo "mejor", por ejemplo, con acceso secuencial en lugar de acceso aleatorio) a expensas de más tiempo de computación.
En el caso del hashing de contraseña , el algoritmo principal de TMTO se debe a Hellman en 1980; posteriormente se descubrieron una serie de mejoras locales, que dieron como resultado lo que se conoce coloquialmente como tablas de arco iris . Podemos obtener una vista conceptual de las tablas del arco iris considerando los dos puntos finales del espectro:
La búsqueda exhaustiva se trata de probar todas las contraseñas potenciales, hacerlas todas y comparar el valor con la que se debe descifrar. Esto tiene el costo computacional más alto (hash promedio de N / 2 para calcular las contraseñas potenciales de N con probabilidad uniforme) pero utiliza solo RAM insignificante.
-
Una tabla precomputada contiene los hashes de N contraseñas potenciales, y se debe realizar una única búsqueda. No contamos el esfuerzo de construir la tabla porque, presumiblemente, puede ser reutilizada para múltiples ataques, posiblemente por varios atacantes. El tamaño de la tabla es proporcional a N , pero el esfuerzo computacional es insignificante (bueno, sobre O ( log N) , que es pequeño ).
Las tablas del arco iris cabrán en el medio. Cuando se construye la tabla, elige un parámetro t denominado "longitud de cadena promedio". El tamaño de la tabla será proporcional a N / t : se reduce en un factor de t , en comparación con la tabla precomputada. Por otro lado, cada ataque implicará un esfuerzo de cálculo proporcional a los cálculos de hash t2 y a las búsquedas de t . Dependiendo de las condiciones operativas, las búsquedas o los cálculos serán el cuello de botella (por ejemplo, depende mucho de si la tabla está en la RAM, en un SSD o en un conjunto de discos duros mecánicos).
Las sales desbaratan completamente las tablas precalculadas, incluidas las tablas de arco iris . La construcción de una tabla precomputada para las contraseñas de N ha costado N ; la construcción de una tabla de arco iris para las mismas contraseñas de N tiene un costo aún mayor (aproximadamente 1.7 * N ). Esto vale la pena solo si la tabla se puede usar al menos dos veces, para atacar dos valores hash distintos; una mesa de un disparo (arco iris o no) no compite con una búsqueda exhaustiva. Pero el punto de las sales es que no hay una función una ; de hecho, hay una gran familia de funciones, y el valor de sal le indica cuál se usa realmente. Una tabla creada para una sal específica no tiene absolutamente ningún valor en romper un valor de hash para cualquier otra sal.
Bcrypt usa sales, por lo que no hay tablas, ni TMTO. Los atacantes han vuelto a la búsqueda exhaustiva. Bcrypt también tiene armas contra búsquedas exhaustivas, es decir, una lentitud configurable, obtenida a través de una gran cantidad de iteraciones internas: desde el punto de vista del usuario, no hay mucha diferencia entre un cálculo de hash que toma 1 microsegundo y uno que toma 100 milisegundos. ; pero para el atacante, este último significa 100000 veces el esfuerzo por su búsqueda exhaustiva.
Consulte esta respuesta para obtener más información sobre el hashing de contraseña seguro. . Breve resumen: si su contraseña es fuerte (es decir, tiene una alta entropía), incluso las agencias poderosas no podrán obtenerla rompiendo el hash bcrypt por adelantado (lo obtendrán rompiendo las rótulas, pero esa es otra historia).