In che modo le tabelle arcobaleno risolvono le collisioni?

6

Ne ho il succo. È come una via di mezzo tra l'attacco di forza bruta e la tabella di ricerca, memorizza il testo in chiaro iniziale e l'hash finale per ogni catena in cui una catena è composta da riduzione e hash.

Quello che non capisco è:

  1. Si dice che i tavoli arcobaleno risolvono le collisioni, ma perché le collisioni sono un grosso problema per cominciare?
  2. Si dice che le tabelle arcobaleno risolvono le collisioni utilizzando una funzione di riduzione diversa per ogni colonna della catena, ma come evitare le collisioni? Le funzioni di riduzione non sono solo caratteri casuali che prendi dall'hash? Quindi, che differenza fa se prendi i primi 8 caratteri invece degli ultimi 8?
posta User104163 24.03.2016 - 16:48
fonte

1 risposta

1

Le collisioni sono l'unico problema con Rainbow Tables. Ironicamente le collisioni sono viste come una brutta cosa per gli algoritmi di hashing, ma nel caso di Rainbow Tables un algoritmo di hashing che genera collisioni abbastanza regolarmente sarà più sicuro.

It's said that rainbow tables solve collisions, but why are collisions such a big deal to begin with?

Un determinato hash può essere generato da più testi in chiaro (questo è chiamato collisione), che è un grosso problema per le catene perché causa catene che iniziano a convergere in una diversa. Inoltre ottieni loop, che si verificano quando un hash viene ridotto a un testo in chiaro che è stato sottoposto a hash in un punto precedente della catena.

It's said that rainbow tables solve collisions by using a different reduction function for each column in the chain, but how does this prevent collisions? Aren't reduction functions just random characters you take from the hash? So what difference does it make if you take the first 8 characters instead of the last 8? The way collisions are handled is what sets Rainbow Tables apart from its predecessor which was developed in 1980.

Il predecessore ha risolto il problema di certi testi in chiaro che non venivano mai ridotti usando molti piccoli tavoli. Ogni tavolino utilizza una funzione di riduzione diversa. Questo non risolve completamente il problema, ma aiuta.

Per risolvere la catena, si fondono e si chiudono ciascuna catena terminata in un "punto distinto"; un hash che era in qualche modo univoco, per esempio hash dove i primi 4 caratteri sono 0. Le catene continuano ad andare finché non raggiunge un punto distinto. Se due catene finiscono nello stesso punto, allora c'è stata una collisione da qualche parte nella catena, e una delle catene viene scartata. Se una catena viene generata per un tempo insolitamente lungo senza raggiungere un punto distinto, si sospetta un loop (dove una catena di hash finisce per ridurre e tritare un hash precedente nella catena). Il problema con questo è che se c'è una collisione c'è potenzialmente un intero ramo che deve essere tagliato e non lo farà nelle catene, e un ciclo causerà tutti gli hash che sono venuti prima del ciclo nella catena per essere scartato Anche tutto il tempo speso a generare quella catena sarà sprecato, e terminando solo in punti distinti avete catene di lunghezza variabile. Ciò significa che potresti dover continuare a cercare un hash all'interno di catene particolarmente lunghe molto tempo dopo che le altre catene sono terminate.

Ho ricevuto l'ispirazione giusta da qui: link

    
risposta data 24.03.2016 - 17:15
fonte

Leggi altre domande sui tag