Perché un hash n bit non può essere violato eliminando ogni singolo testo in n bit?

Naviga le tue risposte
0

Mi chiedo perché sia così difficile trovare collisioni per gli hash crittografici.

Prendi ad esempio una funzione di hash che restituisce un hash 64 bit

Per trovare collisioni, se si alimenta la funzione ogni singola stringa di bit 65 possibile, non si è sicuri di trovare una collisione? La funzione hash deve girare 65 bit in 64 bit, quindi deve trovare alcune collisioni.

Non è possibile trovare una collisione in un modo piuttosto semplice usando questa tecnica?

Capisco che l'elaborazione di tutti ci vorrà molto tempo, ma sembra abbastanza ragionevole farlo e creare un indice di database per memorizzarli in modo che gli hash possano essere interrotti.

    
posta CodyBugstein 25.10.2015 - 14:31
fonte

2 risposte

6

Sì, hai ragione. Anche se ti aspetteresti (statisticamente) di trovare una collisione già dopo circa 2 ^ 32 tentativi.

Se hai un hash di 160 bit, dovresti provare 2 ^ 80 combinazioni (in media) per trovare una collisione. Ma ancora, con la potenza di calcolo di oggi che prova 2 ^ 80 combinazioni impiegheranno troppo tempo per diventare abbastanza vecchio da vedere la collisione: -)

Questo è tutto. Rendere i bit così tanti che ci vuole troppo tempo per provare tutte le combinazioni necessarie.

    
risposta data 25.10.2015 - 15:11
fonte
4

fr00tyl00p lo ha spiegato molto bene, quindi mi limiterò a scaricare alcuni numeri per chiarire quanti dati sarebbero.

Restiamo con il tuo esempio (ogni valore hash a 65 bit a 64 bit). 65 bit può contenere 2 ^ 65 valori diversi = 36.893.488.147.419.103.232. Quindi avresti bisogno di salvare almeno 2 ^ 65 * 64 bit. Potresti anche aver bisogno di una sorta di indice, ma lasciatelo ignorare per ora.

Ciò richiederebbe circa 256 pebibyte o 262144 dati di petabyte. E questo è solo per gli hash a 64 bit e senza alcuna forma di indice.

    
risposta data 25.10.2015 - 19:13
fonte

Leggi altre domande sui tag

Più porte aperte su un server, è sicuro? [chiuso] È una minaccia alla sicurezza avere cibo o bevande accanto ai computer [chiuso]