La semana pasada, en mi clase de criptografía en la ESPE, un estudiante me preguntó por qué su ataque de fuerza bruta contra hashes MD5 estaba tomando días, cuando había oído que existían formas de hacerlo en minutos. Esa fue la oportunidad perfecta para introducir uno de los conceptos más elegantes de la criptografía moderna: las rainbow tables.
Ver la cara de asombro cuando les expliqué que podían "pre-computar" billones de hashes y almacenarlos de forma comprimida para búsquedas instantáneas fue impagable. Pero también fue el momento perfecto para enseñarles por qué los buenos criptógrafos siempre van un paso adelante.
El problema fundamental del crackeo de hashes
Antes de entender las rainbow tables, necesitas comprender el problema que resuelven. Cuando intentas crackear un hash, básicamente tienes dos opciones:
Opción 1: Fuerza bruta en tiempo real
Generas cada posible contraseña, calculas su hash, y comparas con el objetivo. Es lento pero no requiere almacenamiento. Para contraseñas de 8 caracteres alfanuméricos, hablamos de 62^8 = 218 billones de posibilidades.
Opción 2: Tabla de lookup precomputada
Pre-calculas todos los hashes posibles y los almacenas en una tabla gigante. Búsquedas instantáneas, pero el almacenamiento requerido es astronómico. Para el mismo espacio de contraseñas, necesitarías petabytes de storage.
Las rainbow tables son la solución brillante a este dilema tiempo vs. espacio.
¿Qué son las rainbow tables?
Una rainbow table es una estructura de datos precomputada que permite el crackeo rápido de hashes usando un trade-off inteligente entre tiempo de cómputo y espacio de almacenamiento. En lugar de almacenar todos los hashes posibles, almacena "cadenas" comprimidas que pueden regenerar los hashes cuando se necesiten.
La idea fundamental viene del trabajo de Martin Hellman en 1980, pero fue Philippe Oechslin quien en 2003 desarrolló el algoritmo optimizado que conocemos como rainbow tables.
Cómo funcionan: la magia de las cadenas reducidas
Concepto básico de cadenas
Imagina que tienes una función hash H() y una función de reducción R(). Una cadena se construye así:
contraseña1 → H() → hash1 → R() → contraseña2 → H() → hash2 → R() → contraseña3...
La función de reducción R() convierte un hash de vuelta en una contraseña válida del espacio de búsqueda. No es la inversa criptográfica (eso sería imposible), sino una función que mapea hashes a contraseñas de forma determinística.
Almacenamiento inteligente
En lugar de guardar toda la cadena, solo almacenas el punto inicial y final:
Inicio: "aaaa"
Final: "zx9k"
Longitud: 1000 pasos
Una cadena de 1000 pasos requiere solo dos valores almacenados, pero puede encontrar cualquiera de los 1000 hashes intermedios regenerando la cadena desde el inicio.
El problema de las colisiones
Las cadenas simples tienen un problema: cuando dos cadenas convergen, se vuelven idénticas desde ese punto (merging). Esto reduce la cobertura efectiva de la tabla.
Las rainbow tables resuelven esto usando múltiples funciones de reducción R1(), R2(), R3()... Una cadena rainbow se ve así:
pass1 → H() → hash1 → R1() → pass2 → H() → hash2 → R2() → pass3 → H() → hash3 → R3() → pass4
Esto hace que las colisiones entre cadenas sean mucho menos probables, aumentando dramáticamente la eficiencia.
Construcción práctica de rainbow tables
Usando RainbowCrack
RainbowCrack es la herramienta más popular para generar y usar rainbow tables. Para instalarla en Linux:
# Descargar RainbowCrack
wget http://project-rainbowcrack.com/rainbowcrack-1.2-linux-x86_64.zip
unzip rainbowcrack-1.2-linux-x86_64.zip
# Generar tabla para MD5, contraseñas de 6 caracteres alfanuméricos
./rtgen md5 loweralpha-numeric 1 6 0 2400 33554432 0
# Parámetros explicados:
# md5: algoritmo hash
# loweralpha-numeric: conjunto de caracteres
# 1 6: longitud mínima y máxima
# 0: índice de tabla
# 2400: longitud de cadena
# 33554432: número de cadenas
# 0: parte de tabla (para dividir en múltiples archivos)
Cálculo de parámetros óptimos
Elegir los parámetros correctos es crucial para la eficiencia:
- Longitud de cadena: Más larga = menos storage, pero más tiempo de búsqueda
- Número de cadenas: Más cadenas = mejor cobertura, pero más storage
- Número de tablas: Múltiples tablas reducen falsas alarmas
Para MD5 con contraseñas de 6 caracteres alfanuméricos, parámetros típicos:
Espacio total: 36^6 = 2,176,782,336 contraseñas
Longitud de cadena: 2,400
Número de cadenas: 33,554,432
Número de tablas: 8
Cobertura: ~99.9%
Tamaño total: ~64 GB
Tiempo de generación
En mi experiencia generando tablas para demostraciones en clase, los tiempos son considerables:
- MD5, 6 caracteres alphanum: 2-3 días en Core 2 Duo
- NTLM, 7 caracteres alphanum: 1-2 semanas
- SHA1, 6 caracteres alphanum: 4-5 días
Es una inversión de tiempo inicial significativa, pero después las búsquedas son prácticamente instantáneas.
Uso de rainbow tables para crackeo
Crackeando hashes individuales
# Crackear un hash MD5 específico
./rcrack *.rt -h 5d41402abc4b2a76b9719d911017c592
# Crackear múltiples hashes desde archivo
./rcrack *.rt -l hashlist.txt
# Resultado típico:
# 5d41402abc4b2a76b9719d911017c592 hello hex:68656c6c6f
Búsqueda en cadenas rainbow
El algoritmo de búsqueda es fascinante:
- Toma el hash objetivo
- Para cada tabla, asume que el hash está en la posición final de alguna cadena
- Aplica las funciones de reducción apropiadas para llegar al final
- Busca ese valor final en la tabla
- Si lo encuentra, regenera la cadena completa desde el inicio
- Verifica si el hash objetivo está en esa cadena
Si no encuentra nada, asume que está una posición antes del final, y repite. Continúa hasta cubrir toda la longitud de cadena.
Herramientas alternativas
Ophcrack: el especialista en Windows
Ophcrack viene con tablas precomputadas para hashes LM y NTLM de Windows:
# Instalar Ophcrack
sudo apt-get install ophcrack
# Usar con tablas descargadas
ophcrack -g -d /path/to/tables/ -f hashfile.txt
Las tablas de Ophcrack son especialmente efectivas porque se enfocan en contraseñas comunes de Windows, incluyendo variaciones con números y símbolos.
RainbowCrack para GPU
Las versiones modernas pueden usar GPU para acelerar tanto la generación como la búsqueda:
# Generar tabla usando GPU (si está disponible)
./rtgen md5 loweralpha-numeric 1 6 0 2400 33554432 0 -gpu
Matemáticas detrás del éxito
Probabilidad de éxito
La probabilidad de encontrar un hash en una rainbow table depende de la cobertura:
Cobertura = (Número de cadenas × Longitud de cadena) / Espacio total
Para nuestro ejemplo MD5:
Cobertura = (33,554,432 × 2,400) / 2,176,782,336 = ~37% por tabla
Con 8 tablas independientes:
Probabilidad total ≈ 1 - (1 - 0.37)^8 ≈ 99.9%
Trade-off tiempo vs. espacio
Las rainbow tables representan un punto específico en el espectro tiempo-espacio:
- Fuerza bruta pura: Tiempo máximo, espacio mínimo
- Tabla completa: Tiempo mínimo, espacio máximo
- Rainbow tables: Tiempo moderado, espacio moderado
Para MD5 de 6 caracteres, comparando con fuerza bruta, las rainbow tables son ~1000x más rápidas y usan ~1000x menos espacio que una tabla completa.
Defensas contra rainbow tables
Salting: la muerte de las rainbow tables
La defensa más efectiva contra rainbow tables es el salting. En lugar de almacenar:
hash = MD5(contraseña)
Se almacena:
salt = random_string()
hash = MD5(contraseña + salt)
El salt se almacena junto al hash, típicamente en texto plano. Como cada contraseña usa un salt diferente, necesitarías tablas rainbow separadas para cada salt, lo cual es computacionalmente prohibitivo.
Implementación correcta de salting
En PHP, por ejemplo:
Key stretching y funciones costosas
Algoritmos como bcrypt, scrypt, y Argon2 no solo usan salts, sino que hacen el cómputo del hash intencionalmente lento. Esto hace que tanto las rainbow tables como la fuerza bruta sean prohibitivamente costosas.
Casos de estudio reales
Demostración en clase: hashes LM
En una demostración reciente con estudiantes de la ESPE, usé Ophcrack contra hashes LM de Windows XP:
- Tiempo de preparación: 5 minutos (cargar tablas preexistentes)
- Hashes crackeados: 23 de 25 (92%)
- Tiempo promedio por hash: 15 segundos
- Contraseñas encontradas: "123456", "password", "admin", "qwerty"
Los estudiantes quedaron impactados por la velocidad, pero más impactados cuando les mostré que simplemente agregar un salt hacía las tablas completamente inútiles.
Auditoria empresarial
En una consultoría para una pequeña empresa en Quito, encontré hashes MD5 sin salt en su aplicación web casera:
- Base de datos: 200 usuarios
- Hashes crackeados: 156 (78%)
- Tiempo total: 30 minutos
- Contraseñas comunes: nombres de empleados, fechas, "empresa123"
La demostración práctica convenció a la gerencia de contratar un desarrollador para implementar salting apropiado.
Limitaciones y consideraciones
Espacio de almacenamiento
Las rainbow tables requieren storage considerable:
- MD5, 6 chars alphanum: ~64 GB
- MD5, 8 chars alphanum: ~800 GB
- SHA1, 7 chars alphanum: ~300 GB
Para espacios de contraseñas grandes, el storage requerido puede volverse prohibitivo.
Falsos positivos
Las rainbow tables pueden producir falsos positivos donde encuentran una contraseña que produce el hash correcto, pero no es la contraseña original. Esto es más común con hashes cortos o espacios de contraseñas grandes.
Tiempo de búsqueda variable
Aunque las búsquedas son generalmente rápidas, pueden variar significativamente. Un hash en el último eslabón de una cadena se encuentra instantáneamente, pero uno en el primer eslabón requiere regenerar toda la cadena.
Evolución y futuro
Rainbow tables para GPU
Las implementaciones modernas aprovechan la potencia de las GPUs tanto para generación como para búsqueda. Una GTX 480 puede generar tablas ~50x más rápido que un CPU equivalente.
Servicios en línea
Proyectos como "Free Rainbow Tables" proporcionan acceso a tablas precomputadas masivas vía internet, eliminando la necesidad de generarlas localmente.
Algoritmos post-rainbow
Investigación actual explora métodos que van más allá de las rainbow tables, incluyendo ataques probabilísticos y técnicas basadas en machine learning para predicción de contraseñas.
Impacto en la industria
Las rainbow tables transformaron la percepción de la seguridad de contraseñas. Antes de su popularización, muchos desarrolladores consideraban que hashear contraseñas era "suficientemente seguro". Las rainbow tables demostraron que el hashing simple es inadecuado.
Este cambio de paradigma forzó la adopción masiva de salting y algoritmos de hashing más seguros, mejorando la seguridad general de aplicaciones web.
Lecciones para desarrolladores
Si desarrollas aplicaciones que manejan contraseñas, las lecciones de las rainbow tables son claras:
- Nunca uses hashes simples: MD5, SHA1, etc. sin salt son vulnerables
- Usa algoritmos diseñados para contraseñas: bcrypt, scrypt, Argon2
- Genera salts únicos: Un salt diferente por contraseña
- Usa longitud de salt adecuada: Mínimo 128 bits
- Considera key stretching: Hacer el hashing intencionalmente lento
Comentarios 2
Comparte tu opinión
Pablo Jiménez
Oscar Jiménez