Va bene troncare un hash SHA256 a 128 bit?

Question

Gli hash MD5 e SHA-1 hanno punti deboli contro gli attacchi di collisione. SHA256 non fa ma emette 256 bit. Posso prendere tranquillamente il primo o l'ultimo 128 bit e usarlo come hash? So che sarà più debole (perché ha meno bit) ma funzionerà altrimenti?

In pratica, desidero utilizzarlo per identificare in modo univoco i file in un file system che potrebbe un giorno contenere un trilione di file. Sono a conoscenza del problema del compleanno e un hash a 128 bit dovrebbe produrre circa 1 su una trilione di possibilità su un trilione di file che ci sarebbero due file diversi con lo stesso hash. Posso vivere con quelle probabilità.

Quello con cui non posso convivere è se qualcuno possa facilmente, deliberatamente, inserire un nuovo file con lo stesso hash e gli stessi caratteri iniziali del file. Credo in MD5 e SHA1 questo è possibile.

Answer 1

Sì, funzionerà.

Per la cronaca, sono noti attacchi di collisione in uso contro MD5, ma gli attacchi SHA-1 sono a questo punto completamente teorici (nessuna collisione SHA-1 è mai stata trovata ... ancora).

Answer 2

Ma ne vale la pena? Se si dispone di un hash per ogni file, in sostanza si ha un sovraccarico per ciascun file. Supponiamo che ogni file debba occupare lo almeno 512 byte (un tipico settore del disco) e che stiate conservando questi hash in modo sufficientemente compatto in modo da evitare che ciascun hash occupi molto più della dimensione hash.

Quindi, anche se tutti i file sono 512 byte, il più piccolo, stai parlando sia 16/512 = 3.1% o 32/512 = 6.3%. In realtà, scommetto che la dimensione media del file è più alta (a meno che tutti i tuoi file non siano 1 settore ...), in modo che l'overhead sia inferiore.

Ora, la quantità di spazio necessaria per gli hash si riduce in modo lineare con il numero di file che hai. Lo spazio extra vale lo del? Anche se hai i tuoi file di trilione menzionati - questo è 1 000 000 000 000 * 16 = ~29 TiB, che è molto spazio, ma tieni a mente: i tuoi dati saranno 1 000 000 000 000 * 512 = 465 TiB. I numeri sono inutili, in realtà, dal momento che è ancora 3% o 6% overhead. Ma a questo livello, dove hai mezzo petabyte di spazio, contano 15 terabyte? A qualsiasi livello, un risparmio di 3% significa qualcosa? E ricorda, se sono più grandi, risparmi di meno. (Che, probabilmente sono: buona fortuna ottenere una dimensione del settore 512 byte a quella dimensione del disco rigido.)

Quindi, è questo 3% o meno risparmi sul disco vale il rischio potenziale in sicurezza. (Che lascerò senza risposta, poiché non è la mia tazza di tè.)

In alternativa, potresti, ad esempio, raggruppare i file insieme in modo logico, in modo da avere meno file? (Voglio dire, se hai trilioni di file da 512 byte, vuoi veramente hash ogni byte su disco?)

Answer 3

Sì, funzionerà. In teoria, è meglio XOR le due metà insieme, ma anche lo SHA256 troncato è più forte di MD5. Dovresti comunque considerare il risultato come un hash a 128 bit piuttosto che un hash a 256 bit.

La mia particolare raccomandazione in questo caso particolare è quella di memorizzare e fare riferimento usando HASH + unqualificatore dove univocatore è il numero di quanti file distinti hai visto con questo hash in precedenza. In questo modo non cadi assolutamente piatta se qualcuno cerca di memorizzare i futuri vettori di collisione scoperti per SHA256.