Perché utilizzare MD4 per la memorizzazione nella cache?

Gli hash non crittografici usuali come CRC-32 sono statisticamente buoni, ma qui ciò che la cache vuole evitare è falsi positivi - ricompilazioni che sono dichiarate identiche a una precedente, ma non lo sono . Un normale hash non crittografico che produce solo 32 bit ha un rischio troppo elevato di falsi positivi, semplicemente dalla sua dimensione di output e indipendentemente dalle sue qualità statistiche. Un hash crittografico ha un output molto più grande, il che rende trascurabili i rischi di falsi positivi.

Questa non è una domanda di sicurezza : tutti gli input provengono dall'utente, quindi se l'utente commette una collisione di proposito, sta solo combattendo contro se stesso. Pertanto, è possibile utilizzare una funzione di hash crittografata.

Ora per la scelta specifica di MD4 su una funzione più comune (come MD5 o SHA-1), si può solo speculare, ma la mia ipotesi è che si tratta di prestazioni; dopotutto, ccache si occupa di rendere le compilazioni più veloci. MD4 è diabolicamente veloce (anche più veloce di CRC-32 su alcune piattaforme). Ovviamente, l'hashing è più veloce di qualsiasi processo di compilazione o anche semplicemente lettura dei file, quindi è probabile che l'uso di MD5 anziché MD4 non abbia alcuna differenza significativa nelle prestazioni generali di ccache. Molte decisioni relative alle prestazioni sono in pratica prese per intuizione, senza preoccuparsi di misure effettive per vedere se c'è un problema di prestazioni che deve essere risolto.

Dal lavoro su questa libreria , ci sono pochissime funzioni di hash crittografiche che sono almeno veloci quanto MD4. BLAKE2 , una derivata recente del candidato BLAKE SHA-3, potrebbe essere la soluzione migliore per una funzione di hash crittografica sicura che si avvicina ai livelli MD4 delle prestazioni. Ma, come ho scritto sopra, è altamente probabile che le prestazioni non siano un problema reale nel caso di ccache.

Le funzioni hash crittografiche di solito hanno la proprietà che input leggermente diversi generano output molto diversi. Qualsiasi collisione dovrebbe di solito ha un input molto diverso.

Questa proprietà non si applica alla maggior parte dei checksum non crittografici. Piccole modifiche possono generare checksum simili e in alcuni casi d'angolo alcune piccole modifiche possono annullarsi a vicenda in modo da generare lo stesso checksum.

Le modifiche al codice sorgente sono spesso piuttosto piccole, quindi nel contesto del controllo delle modifiche al codice sorgente il rischio di collisioni è piuttosto elevato con checksum non crittografici. Il git dello strumento di controllo della versione, ad esempio, utilizza gli hash SHA-1 come identificatore univoco per le revisioni del codice.

Perché MD4 in particolare? Beh, devi chiedere agli sviluppatori di ccache su questo. È uno strumento abbastanza vecchio e MD5 non è stato standardizzato fino al 1992. Potrebbe essere possibile che MD4 fosse semplicemente la scelta più ovvia che era disponibile al momento in cui questa funzione è stata sviluppata, e in seguito nessuno ha sentito la necessità di sostituire l'algoritmo , perché ha fatto quello che avrebbe dovuto fare.