Questa modifica SHA-256 è ancora valida?
Tipicamente modelliamo una funzione hash (in particolare $\mathrm{SHA}$-$256$) come una funzione $H:\{0,1\}^{2^{64}-1} \to \{0,1\}^{256}$con alcune proprietà speciali che li rendono utili nella pratica. In questo caso, la probabilità di una collisione è intorno$2^{-256}$ che si presume non sia fattibile nella pratica.
Adesso (perché $256$bit sembrano troppo lunghi da gestire per me), voglio tagliarne alcuni e mantenere una probabilità (quasi) impossibile di avere una collisione. In altre parole, qual è la quantità corretta di bit che devo troncare in modo da avere ancora una buona resistenza alle collisioni? È solo$2^{-m}$, dove $m$ denota i bit che tieni dall'inizio?
Per illustrare cosa intendo, immagina che l'inizio di due uscite di $H$ siamo $1011100...$ e $1011000...$. Se solo decido di interrompere$4$ morde poi ho una collisione ($1011$), altrimenti no.
Dove posso trovare quando (e perché) una probabilità è "abbastanza bassa" in pratica? Presumo sia qualcosa legato ai limiti del computer ...
L'idea alla base di questa domanda è l'utilizzo di hash di tracciamento facili da gestire dagli utenti. Un limite superiore per il numero di utenti è$2$milioni. Da$256$ bit è troppo grande (è ancora grande se usi base-$16$ o base$64$), abbiamo pensato di eliminare una certa quantità di bit se è sicuro farlo. Due utenti con lo stesso hash tagliato significherebbero un disastro.
Risposte
Tipicamente modelliamo una funzione hash (in particolare $\mathrm{SHA}$-$256$) come una funzione $H:\{0,1\}^{2^{64}-1} \to \{0,1\}^{256}$ con alcune proprietà speciali che li rendono utili nella pratica.
Ebbene, quella definizione è davvero piuttosto particolare per SHA-256. La dimensione dell'output dipende ovviamente dalla funzione hash e, ad esempio, SHA-3-256 ha uno spazio di input infinito.
In questo caso, la probabilità di una collisione è intorno $2^{-256}$ che si presume non sia fattibile nella pratica.
No, per la funzione la probabilità di creare una collisione utilizzando molti tentativi è più vicina a $2^{-128}$a causa del compleanno legato. Stai mostrando la possibilità che si verifichi una pre-immagine, e questo solo per un singolo tentativo. Discutere la resistenza alle collisioni per gli hash su due messaggi distinti non ha molto senso.
Dove posso trovare quando (e perché) una probabilità è "abbastanza bassa" in pratica? Presumo sia qualcosa legato ai limiti del computer ...
Dipende da come viene utilizzata la funzione hash e dal modello di minaccia del caso d'uso specifico. Se mi chiedessi un limite di sicurezza minimo generico, sceglierei 128 bit (presumendo solo attacchi che utilizzano computer classici). Ciò significherebbe un hash a 256 bit quando si tratta di resistenza alle collisioni e non eliminare alcun bit.
Ora per casi d'uso particolari puoi andare più in basso. Tieni presente che la generazione di$2^{128}$hash non è pratico; il limite del compleanno presuppone che si confrontino molti hash dopo tutto. Quindi c'è probabilmente un margine di manovra quando si tratta di requisiti di memoria per qualsiasi attacco.
Gli hash con chiave (HMAC) sono una questione completamente diversa. Lì avrai solo bisogno di 128 bit per ottenere una sicurezza a 128 bit.