aclaración sobre cómo las tablas de arco iris utilizan múltiples funciones de reducción para evitar colisiones

Question

aclaración sobre cómo las tablas de arco iris utilizan múltiples funciones de reducción para evitar colisiones

#1 de Joaquin Brandan (1 votos)

2

Comprendo cómo funcionan las tablas de compensación de tiempo-memoria de Hellman al crear cadenas de resultados de función de reducción y hash y al almacenar el último resultado después de varias operaciones. ya que la función de reducción asigna desde el espacio hash (crapton de caracteres) al espacio de contraseña (digamos hasta 10 caracteres), es obvio que vamos a tener un montón de colisiones.

Las tablas arco iris intentan resolver esto mediante el uso de múltiples funciones de reducción. No entiendo cómo o por qué eso ayuda.

Este artículo de wikipedia parece intentar ponerle algo de luz, pero simplemente no puedo entender lo que está tratando de decir.

Las tablas arco iris resuelven efectivamente el problema de las colisiones con cadenas de hash ordinarias reemplazando la función de reducción simple R con una secuencia de funciones de reducción relacionadas R ₁ a R _k. De esta manera, para que dos cadenas colisionen y se fusionen, deben alcanzar el mismo valor en la misma iteración.

rainbow-table

pregunta Joaquin Brandan 19.03.2018 - 18:44

fuente

1 respuesta

Lea otras preguntas en las etiquetas rainbow-table

El uso de hashes de archivos SHA1 y MD5 ayudaría a reducir el riesgo de eliminar no duplicados Política de caché HSTS para el dominio raíz

score 1 · Answer 1

Está bien, creo que lo descubrí.

Hice una ilustración ya que parece ser la mejor manera de explicar lo que está pasando.

Las tablas de arco iris utilizan una función de reducción diferente en cada enlace de la cadena (esto puede verse como una función diferente en cada columna, donde las cadenas son filas)

En la siguiente ilustración

H () es la función de hash
R () es una función de reducción común que se usa en todos los enlaces (no en una tabla de arco iris)
R1 () a R3 () son funciones de reducción diferentes en cada enlace (tabla Rainbow)
A-Z se obtienen mediante una función de reducción
Hash1-5 son hashes obtenidos por la función Hashing

En la ilustración que encontrarás:

¿Qué sucede durante una colisión en una tabla de Hellmans (el predecesor de la tabla Rainbow, utiliza una función de reducción única R ())
¿Qué sucede durante una colisión en una tabla Rainbow (idéntica a la tabla de Hellmans, pero utiliza diferentes funciones de reducción en cada enlace de cadena)
¿Qué sucede durante una Colisión que se produce en el mismo lugar en una tabla Arcoíris (es estadísticamente improbable, pero si esto sucede, las cadenas terminan siendo idénticas, pero ya que esto no sucede a menudo, no es una gran preocupación)