Estimar el tamaño de una tabla de arco iris

RainbowCrack es probablemente lo que usarías para generar tablas de arco iris. Las tablas de arco iris se siempre generadas sobre un espacio de teclas, como el alfa-numérico de 5-9 bytes y la longitud y el recuento de la cadena que afectarán la velocidad y el tamaño de las tablas resultantes. Si tiene un archivo de entrada, entonces no es una tabla de arco iris, es otra tabla de búsqueda. Una tabla de arco iris es un tipo especial de tabla de búsqueda con propiedades nítidas. Por ejemplo, el tamaño de la función hash ( sha256 vs sha512 ) no afecta el tamaño de la tabla del arco iris.

Hay algunos scripts matlab que flotan alrededor para calcular el tamaño de la tabla del arco iris, sin embargo, este sitio es más fácil de usar .

Una tabla de arco iris se caracteriza por su longitud de cadena promedio . Es un parámetro que se elige en el momento de la construcción de la mesa. Llamémoslo t .

Si la tabla cubre aproximadamente N contraseñas provisionales, tendrá un tamaño de aproximadamente N / t "entradas", donde una entrada es un "final de cadena" . El tamaño codificado de un extremo de la cadena depende de muchos detalles, pero normalmente será tan grande o algo más grande que un campo que puede contener el valor entero N . En otras palabras, si N está cerca de 2 ⁴⁰ , cada entrada necesitará al menos 5 bytes, pero probablemente un poco más que eso, digamos 8 bytes.

Para ahorrar en el costo de almacenamiento, querrá que t sea lo más grande posible. Sin embargo, no puede hacerlo tan grande como quiera, porque eleva otros costos. Dicho brevemente:

• El costo de construcción de la tabla se trata de 1.7 * N evaluaciones de la función hash.
• El costo de almacenamiento es N / t termina la cadena.
• El costo de la CPU cuando se ataca es sobre t² evaluaciones de la función hash.
• El costo de búsqueda cuando se ataca es sobre t accesos aleatorios en las tablas.

Un disco duro moderno permite aproximadamente 100 búsquedas por segundo, por lo que si desea mantener el tiempo de ataque por debajo de un minuto, no puede tener t por encima de 6000. Puede tener valores mucho más altos para t si usa SSD (lo que permite muchos miles de accesos aleatorios por segundo), pero el costo de almacenamiento aumenta porque los SSD son bastante caros. Además, si t se vuelve demasiado alto, el costo cuadrático de la CPU puede volverse prohibitivo.

La diferencia entre una tabla rainbow , lo que existía antes (el compromiso de la memoria del tiempo de Hellman) y las variantes modernas que mezclan ideas de Hellman, Oechslin, Rivest, Biham y algunas otras. es un factor de como máximo 2 en costos de CPU y búsqueda.