Las colisiones son el único problema con Rainbow Tables. Irónicamente, las colisiones se consideran algo malo para los algoritmos de hash, pero en el caso de Rainbow Tables, un algoritmo de hashing que genere colisiones con bastante regularidad será más seguro.
Se dice que las tablas arco iris resuelven colisiones, pero ¿por qué son tan importantes las colisiones para empezar?
Un hash dado puede ser generado por múltiples puntos de vista (esto se llama colisión), lo cual es un gran problema para las cadenas porque hace que las cadenas que comienzan de manera diferente converjan en una. También obtienes bucles, que son causados cuando un hash se reduce a un texto plano que fue hash en un punto anterior de la cadena.
Se dice que las tablas del arco iris resuelven colisiones usando una función de reducción diferente para cada columna en la cadena, pero ¿cómo evita esto las colisiones? ¿Las funciones de reducción no son solo caracteres aleatorios que tomas del hash? Entonces, ¿qué diferencia hay si tomas los primeros 8 caracteres en lugar de los últimos 8?
La forma en que se manejan las colisiones es lo que diferencia a Rainbow Tables de su predecesor, que se desarrolló en 1980.
El predecesor resolvió el problema de ciertos plaintexts que nunca se redujeron al usar muchas tablas pequeñas. Cada mesa pequeña utiliza una función de reducción diferente. Esto no resuelve el problema completamente, pero ayuda.
Para resolver las combinaciones de cadenas y bucles, cada cadena finalizó en un "punto distinto"; un hash que era único de alguna manera, por ejemplo, hashes donde los primeros 4 caracteres son 0. Las cadenas continúan hasta que llega a un punto distinto. Si dos cadenas terminan en el mismo punto distinto, entonces se ha producido una colisión en algún lugar de la cadena y se descarta una de las cadenas. Si se genera una cadena durante un tiempo inusualmente largo sin llegar a un punto distinto, se sospecha que un bucle (donde una cadena de hashes termina reduciéndose y haciendo hashing a un hash anterior en la cadena). El problema con esto es que si hay una colisión, potencialmente hay una rama entera que debe ser cortada y no lo hará en las cadenas, y un bucle causará que todos los hashes que vinieron antes del bucle en la cadena ser descartado.
Además, todo el tiempo dedicado a generar esa cadena se desperdiciará, y al terminar solo en puntos distintos, tiene cadenas de longitud variable. Esto significa que es posible que tenga que seguir revisando un hash dentro de cadenas especialmente largas mucho después de que las otras cadenas hayan terminado.
Obtuve la inspiración adecuada desde aquí: enlace