Tavoli Arcobaleno: A cosa serve la riduzione?

La funzione di riduzione aiuta a memorizzare più candidati in testo semplice all'interno degli hash stessi. L'articolo fornisce un esempio di riduzione davvero semplice: prendere i primi sei numeri del tuo hash "222f00dc4b7f9131c89cff641d1a8c50". Il risultato della riduzione è un'altra possibile password a sei cifre (222004) che viene sottoposta a hash. Quindi, viene estratta un'altra password in chiaro in chiaro da quel hash e così via, creando una lunga catena. La tabella arcobaleno memorizza solo la fine di quella lunga catena. Non è necessario memorizzare tutti gli hash perché è in grado di estrarre ciascun hash dalla funzione di riduzione mentre si sposta indietro sulla catena.

quando gli dai un hash che vuoi incrinato, prima guarda nel primo set di hash che ha immagazzinato (che sono il risultato finale di questa lunga catena). Se per caso l'hash è lì, restituisce il testo in chiaro ed esce. Altrimenti, sale di un passo nella catena e controlla l'hash rispetto a quello che hai fornito. e così via.

All'inizio pensavo che funzionasse una sorta di operazione con il bucket, che riduceva il numero di posti necessari per cercare l'hash, ma non credo che la catena dia qualche indicazione su dove iniziare sulla base dell'hash originale . Semplicemente è il trading di lavoro intuitivo in memoria per una riduzione dei requisiti di storage.

Come dice l'articolo, non c'è alcuna garanzia che ogni testo in chiaro abbia un hash corrispondente in questo schema. Le tabelle arcobaleno ottengono il maggior numero possibile modificando la funzione di riduzione in ogni colonna (ecco perché sono chiamate tabelle arcobaleno, ogni colonna è immaginata di avere un colore diverso ...)

È un modo di compromettere lo spazio di archiviazione e i requisiti di calcolo.

È un'implementazione di una tabella hash : invece di memorizzare tutti i possibili valori univoci nella tabella (che si tradurrà in problema reale per l'archiviazione dell'indicizzazione e la ricerca del risultato), è sufficiente ridurre il numero di calcoli necessari per trovare un hash valido.

Fondamentalmente, quando costruisci la tabella arcobaleno, crei un hash (qui chiamato una funzione di riduzione perché riduce la dimensione dello spazio chiave) del risultato per ogni voce che provi. Quindi memorizzi il valore originale in un secchio etichettato con il risultato della funzione di riduzione.

Quando usi la tabella arcobaleno, fai quanto segue: prendi il valore di hash che vuoi invertire, passa attraverso la funzione di riduzione e guarda cosa c'è all'interno del bucket che ha quel tag: quindi prova ad hash ognuno dei elementi in quel bucket e vedere se corrisponde al tuo valore originale.

Per quanto riguarda il modo in cui scegliere una funzione di riduzione adeguata, ne vorrai una che ti consenta di raggruppare tutti i dati che vedi in blocchi gestibili: non vuoi avere solo alcuni grandi bucket o troppi piccoli. Ecco dove deve essere trovato un equilibrio. Oltre a questo, esattamente come selezioni che ridurre la funzione non è molto importante: dovresti provare a usare qualcosa di facile da calcolare, che dividerà i tuoi dati in bucket statisticamente uguali e che sarà facile da gestire per il tuo ambiente quindi, se tu? piuttosto preferisco scegliere gli ultimi 6 numeri invece del 6, non importa alla fine.

C'è un ottimo tutorial che illustra come funziona la tavola arcobaleno qui: link

Una tabella di riduzione è una tabella che esegue il mapping da hashcode a testo in chiaro. Un esempio potrebbe prendere le prime 6 cifre di hashcode (ad es. 134503 da hashcode abcd13450d3 ...).

La funzione di riduzione proverà a distribuire ugualmente il testo in chiaro, e non proverai a portare molte mappe di hash in un testo in chiaro. Ciò provocherà collisioni come descritto nel video.

Quando una funzione di riduzione e hash si intreccia, consente di formare una lunga catena che esegue ripetutamente mapping tra il dominio di hashcode e testo in chiaro.