Una tabla de arco iris es "solo" una representación compacta de una tabla de valores hash precalculados. Durante la construcción de la tabla del arco iris, se prueban y se procesan muchas entradas posibles. Cada entrada que se haya encontrado durante la construcción de la tabla será atacada con éxito con esa tabla, y ninguna otra. La evaluación de hash concentra la mayor parte del costo de construcción de la tabla.
Entonces, básicamente, el costo de construir una tabla de arco iris que puede invertir las contraseñas de N es aproximadamente equivalente al costo de probar esas contraseñas de N a través de la función hash: el punto de la tabla del arco iris es que la construyes una vez y luego la uses para romper varias contraseñas. (Para ser precisos, debido a las colisiones de la cadena durante la construcción de la mesa, el costo es, de hecho, más cercano a 1.7 * N , pero ignoremos eso por el momento).
Una vez he hecho algunas experiencias con SHA-1. Un simple hash de contraseña con SHA-1 tiene el costo de procesar un solo "bloque" (SHA-1, como MD5, procesa datos por bloques de 64 bytes), que necesita aproximadamente 900 operaciones lógicas o aritméticas de 32 bits. Una implementación optimizada en un procesador Intel Core2 x86 puede hacer eso en aproximadamente 500 ciclos de reloj. Sin embargo, los ataques de contraseña (ya sea directamente o para la construcción de tablas de arco iris, no importa) son un trabajo altamente paralelo, por lo que uno podría usar las instrucciones SSE2 que ofrecen registros de 128 bits, y donde un solo código de operación puede realizar cuatro operaciones de 32 bits simultáneamente. SSE2 tiene menos tipos de operaciones disponibles (en particular, no ofrece rotaciones, solo cambios), por lo que el recuento de operaciones aumenta a aproximadamente 1200; pero, bajo ciertas condiciones, la unidad SSE2 ejecutará varios códigos de operación simultáneamente. Así que terminamos con 800 ciclos de reloj, para cuatro instancias de SHA-1 en paralelo. En pocas palabras: mi PC es una Intel Core2 Q6600, con cuatro núcleos que funcionan a 2.4 GHz. Cada núcleo puede ejecutar mi implementación SSE2, lo que da como resultado 48 millones de contraseñas con hash por segundo.
También tengo una tarjeta gráfica Nvidia no muy pequeña, y la GPU puede ejecutar código arbitrario a través de CUDA . Este es un 9800 GTX +, con 128 núcleos funcionando a 1.84 GHz. Cada núcleo puede ejecutar una operación de 32 bits por ciclo (hay una alta latencia, pero, gracias a la alta paralelización, se puede mantener este rendimiento de una instrucción por ciclo). Los núcleos no conocen las rotaciones, por lo que cada código utilizará 1200 ciclos de reloj por contraseña con hash. El rendimiento total es de 160 millones de contraseñas con hash por segundo.
Mi PC y la tarjeta gráfica son de principios de 2009 y no son de primera línea. Hoy en día se puede encontrar, por unos pocos cientos de dólares, una GPU que procesará las contraseñas tres veces más rápido que mi 9800 GTX +. Así que supongamos que un atacante con una PC común (que cuesta menos de $ 1000) puede hash de medio billón de contraseñas por segundo.
A esa velocidad, todas las contraseñas con 8 caracteres alfanuméricos (letras mayúsculas y minúsculas y dígitos) se pasan en aproximadamente 5 días . Con una PC de 1000 $. Si usa MD5, las cosas son aproximadamente un 30% más rápidas (MD5 usa un poco menos operaciones que SHA-1). Sin embargo, los buenos esquemas de hash de contraseñas no utilizan una invocación de hash simple: usan hash iterado con, por ejemplo, 2000 invocaciones de hash anidadas: esto multiplica el costo para el atacante por el mismo factor de 2000 (por lo que convierte los "5 días" en aproximadamente 28 años, literalmente "edades" como lo pones).