I checksum non sono hash: CRC-32, Adler-32 e a che cosa servono

Tre lavori che producono tutti un numero corto

La confusione comincia dall'output. CRC-32, Adler-32, FNV-1a, MurmurHash3, MD5 e SHA-256 prendono byte qualsiasi e restituiscono un numero di dimensione fissa, quindi in un'API sembrano intercambiabili. Non lo sono. Sono stati progettati contro tre modelli di minaccia del tutto diversi, e scegliere la famiglia sbagliata produce guasti silenziosi finché non diventano catastrofici.

Un checksum risponde: questi dati sono cambiati per caso lungo la strada? Il suo avversario è un raggio cosmico, un cavo al limite, una scrittura troncata, un settore di disco che cede. Quell'avversario è casuale e non si adatta. CRC-32 e Adler-32 sono checksum. Un hash crittografico risponde a una domanda più dura: qualcuno può, con tutto il tempo e l'hardware che riesce a comprare, trovare un secondo input con lo stesso output? Il suo avversario è una persona con un budget. MD5, SHA-1 e SHA-256 sono tentativi in tal senso — con successo variabile, di cui si occupa l'articolo compagno sulla scelta dell'hash.

Il terzo lavoro è quello che si dimentica. Un hash da tabella risponde: come trasformo questa chiave in un indice di bucket, in fretta e in modo uniforme? Il suo avversario è nominalmente nessuno — finché le chiavi non arrivano dai parametri di richieste HTTP, e allora l'avversario è chi le manda. FNV-1a e MurmurHash3 vivono qui. Sono eccellenti nel loro compito e non offrono alcuna protezione negli altri due.

CRC-32 è lineare, ed ecco la collisione

CRC-32 è divisione polinomiale su GF(2), e la divisione è lineare. In concreto, per tre messaggi qualsiasi di uguale lunghezza, crc(a XOR b XOR c) è uguale a crc(a) XOR crc(b) XOR crc(c). Provata su cinque terne casuali da 32 byte, l'uguaglianza è stata esatta ogni volta — una terna ha dato per esempio 8975e151 da entrambi i lati. Nessun hash crittografico possiede un'identità simile, e quel solo fatto algebrico è tutta la differenza fra le due famiglie.

La linearità significa che puoi risolvere una collisione invece di cercarla. Prendi un messaggio che un attaccante vuole alterare, dagli qualche byte di margine ovunque — riempimento, un campo commento, un'intestazione riservata, spazi finali — e il valore di margine richiesto è la soluzione di un sistema lineare a 32 incognite su GF(2). L'eliminazione di Gauss la risolve in microsecondi.

Fatto davvero: il messaggio originale era «config: mode=safe, retries=3, pad=......», con CRC-32 78aa94ad. La contraffazione doveva leggersi «config: mode=open, retries=9, pad=» seguito da sei byte di riempimento da determinare. Risolvere quei byte ha dato «config: mode=open, retries=9, pad=!9[noI» — stessa lunghezza di 40 byte, 11 byte diversi e lo stesso CRC-32 78aa94ad. Sono stati provati venticinque riempimenti candidati prima che uno risultasse interamente stampabile; l'intero programma è girato in 0,11 secondi. I digest SHA-256 dei due messaggi iniziano con d9cddeec e 6b7bdc0c, che è l'aspetto di una funzione senza identità di linearità.

Nulla di tutto ciò ha richiesto crittanalisi, GPU o dizionari. Ha richiesto di sapere che CRC-32 è un'applicazione lineare e di possedere sei byte del messaggio. Ecco perché un CRC che accompagna un file su un canale non fidato non prova nulla contro la manomissione: chi può cambiare il file può cambiare il CRC di conseguenza, e anche se il CRC arriva separatamente ed è intoccabile, si può comunque fabbricare un altro file che lo produca.

In che cosa CRC-32 è davvero eccellente

Nulla di quanto sopra rende CRC-32 una funzione cattiva. La rende una funzione che svolge un altro lavoro, e in quel lavoro è quasi ottimale. Le sue garanzie non sono statistiche, sono dimostrate: rileva ogni errore di un bit, ogni errore di due bit entro una lunghezza di messaggio enorme, ogni errore che coinvolga un numero dispari di bit e ogni errore a raffica fino a 32 bit — la lunghezza del checksum stesso.

Misurato e non asserito: su un messaggio da 200 byte, tutte le 1 600 inversioni possibili di un bit hanno cambiato il CRC, e anche tutte le 1 279 200 inversioni possibili di due bit lo hanno cambiato — nessuna è sfuggita. Su un frame da 1500 byte di taglia Ethernet, 200 000 errori a raffica casuali per ciascuna di sei larghezze (8, 16, 32, 33, 40 e 64 bit) sono stati tutti rilevati. Le raffiche oltre i 32 bit non sono garantite, solo schiaccianti probabili: la probabilità di fuga è circa 2 elevato a meno 32, una su 4,29 miliardi, ed è per questo che 200 000 prove non hanno trovato nulla.

Ecco perché CRC-32 è nei frame Ethernet, nelle code dei file gzip, nei chunk PNG, nelle voci ZIP e in SATA. Sono tutti canali il cui modo di guasto è un difetto fisico che produce una sequenza contigua di bit corrotti — esattamente la classe di errori che i polinomi CRC sono costruiti per cogliere con certezza. Un hash crittografico li coglierebbe anch'esso, ma a un costo molte volte superiore e senza garanzia dimostrata, solo probabilistica.

Adler-32: più economico da calcolare, più debole nel rilevare

Adler-32, definito nell'RFC 1950 per il formato zlib, sono due somme correnti modulo 65 521: una somma semplice dei byte e una somma di quelle somme parziali. È stato progettato per essere molto più economico di un CRC pur rilevando la maggior parte degli stessi errori — nessuna tabella, solo addizioni. In pratica l'operazione di modulo costa abbastanza da far spesso evaporare il vantaggio promesso: misurato nello stesso runtime JavaScript sullo stesso buffer da 64 MB, Adler-32 è andato a 174 MB/s contro i 262 MB/s di CRC-32. Adler-32 è stato più lento.

Ha anche un punto cieco che si dimostra invece di stimarlo. Il modulo 65 521 è il più grande primo sotto 65 536. Se aumenti un byte di d e diminuisci un altro byte di d, la prima somma non cambia, e la seconda cambia di d per la distanza fra i due — cosa che si annulla modulo 65 521 esattamente quando quella distanza è 65 521. Quindi ogni messaggio più lungo di circa 64 kilobyte ha coppie di modifiche compensative che Adler-32 non vede affatto.

Dimostrato su un buffer da 70 000 byte: alzare il byte 100 di 7 e abbassare il byte 65 621 di 7 ha lasciato Adler-32 a 3fee717c, identico byte per byte al valore pulito, mentre CRC-32 passava da abc586b8 a 43c209f4. Adler-32 è debole anche sugli input corti — 200 000 input casuali da quattro byte hanno prodotto solo 152 364 valori Adler-32 distinti, dove una funzione a 32 bit ideale ne avrebbe prodotti circa 199 995. Lo stesso RFC 1950 segnala la debolezza sui messaggi corti, ed è per questo che i flussi zlib lo applicano a flussi interi e non a record minuscoli.

FNV-1a e MurmurHash3: la terza categoria

FNV-1a e MurmurHash3 non sono né checksum né hash crittografici. Sono hash non crittografici progettati per tabelle hash, filtri di Bloom e sharding, dove il requisito è la distribuzione uniforme al minor costo possibile per byte. Mantengono la promessa. Nello stesso runtime e sullo stesso buffer, MurmurHash3 è andato a 730 MB/s e FNV-1a a 520 MB/s, contro i 262 MB/s di CRC-32.

Le collisioni sono banali da trovare, e l'esercizio richiede meno di due secondi. Enumerando stringhe di sette caratteri, FNV-1a 32 è collidito su «7yzlaaa» e «e6apaaa», entrambe con hash 15111984, dopo 700 997 candidati e 680 millisecondi. MurmurHash3 con seme 0 è collidito su «rynbaaa» e «ciaabaa», entrambe su e5407f96, dopo 1 679 907 candidati e 1,6 secondi. È atteso — 32 bit significano collisione di compleanno intorno ai 77 163 elementi — e non è un difetto. Diventa un difetto quando qualcuno sceglie le chiavi.

L'hash flooding è l'attacco che ne deriva, ed è facile da riprodurre. Raccogliere 20 000 chiavi il cui valore FNV-1a finisce nel bucket 0 di una tabella da 4 096 bucket è costato una frazione di secondo di divisione per tentativi. Inserirle ha fatto collassare la tabella in un'unica catena da 20 000 voci, dove chiavi ordinarie davano una catena massima di 12. Ventimila ricerche hanno poi richiesto 1 397,9 millisecondi invece di 11,5 — un rallentamento di 121 volte, da tempo costante a lineare. Ogni richiesta che tocchi una tabella simile diventa un amplificatore: è esattamente la classe di negazione del servizio che ha spinto i runtime dei linguaggi verso un SipHash con seme casuale per i loro dizionari integrati.

Scegliere, in una domanda

Chiediti chi ci guadagna se due input diversi producono lo stesso valore. Se la risposta è nessuno — stai cogliendo copie troncate, cavi ballerini, archivi corrotti, marciume di bit su un disco di backup — un checksum è corretto e CRC-32 è il default sensato. È piccolo, è ovunque, ha garanzie dimostrate contro esattamente le forme di errore che l'hardware produce, e le implementazioni native sono rapidissime: il CRC-32 di zlib in node ha toccato 2 248 MB/s sullo stesso buffer, tre volte i 763 MB/s di SHA-256.

Se la risposta è qualcuno — un download su una rete che non controlli, una firma, un file di licenza, un payload di aggiornamento, la deduplicazione di oggetti forniti dagli utenti, una cache indicizzata da qualcosa che un utente può influenzare — ti serve un hash crittografico, e oggi significa SHA-256. Il costo è reale ma piccolo: 763 MB/s è ancora più veloce della maggior parte dei dischi e delle reti, ed è l'unica famiglia in questo confronto in cui un secondo input con lo stesso output non è qualcosa che chiunque possa semplicemente risolvere.

E se il valore non lascia mai il tuo processo — indice di bucket, filtro di Bloom, selettore di shard — usa un hash da tabella, ma poniti una domanda successiva: un attaccante può scegliere le chiavi? Se può, ti serve una funzione con chiave e seme casuale come SipHash, non un FNV-1a a seme fisso. La maggior parte dei runtime moderni lo fa già per le proprie mappe integrate; il pericolo è una tabella fatta a mano nel codice applicativo che non lo faccia.

Domande frequenti

CRC-32 è una funzione di hash?

Nel senso più lasco sì — mappa un input qualsiasi su un output fisso da 32 bit — ma chiamarla così invita all'errore per cui questo articolo esiste. CRC-32 è una funzione lineare, calcolata come resto di una divisione polinomiale su GF(2). Quella linearità le dà l'identità crc(a XOR b XOR c) = crc(a) XOR crc(b) XOR crc(c), verificata qui su terne casuali, e da quell'identità discende una collisione ottenuta risolvendo un sistema lineare a 32 incognite anziché cercando. Un hash crittografico è progettato apposta perché nessuna scorciatoia algebrica del genere esista; è ciò che fa la parola crittografico. Quindi CRC-32 è un checksum, e il modello mentale utile è ottimo codice rilevatore di errori anziché hash debole. Se una libreria, un'API o una revisione del codice lo chiama hash, verifica su quale proprietà si stia davvero contando: l'unicità contro un avversario è quella che non può fornire, ed è quella che si dà per scontata.

Posso usare un CRC-32 per verificare un download?

Dipende interamente da che cosa stai verificando. Se stai controllando che i byte arrivati coincidano con quelli partiti — che la connessione non sia caduta a metà, che l'archivio non sia troncato, che il disco abbia scritto ciò che gli è stato dato — un CRC-32 è esattamente lo strumento giusto e coglierà qualsiasi guasto di trasporto realistico. Per questo ogni voce ZIP e ogni flusso gzip ne porta uno. Se invece chiedi se il file è quello che l'editore intendeva, un CRC-32 non risponde nulla. Un attaccante che possa sostituire il file può sostituire anche il CRC, e persino dove il CRC è pubblicato a parte ed è intoccabile, può costruire un altro file che vi corrisponda — questo articolo lo ha fatto in 0,11 secondi. Per verificare l'editore serve un digest crittografico pubblicato su un canale che l'attaccante non controlla, e idealmente una firma su quel digest anziché il digest da solo.

Perché gzip usa CRC-32 mentre zlib usa Adler-32?

Entrambi i formati avvolgono gli stessi dati compressi DEFLATE e differiscono soprattutto nel contenitore. L'RFC 1952 specifica un CRC-32 nella coda gzip; l'RFC 1950 specifica un Adler-32 in quella zlib. Il ragionamento dell'epoca era la velocità: Adler-32 richiede solo addizioni e un modulo, senza tabella da 256 voci, quindi sui processori dei primi anni Novanta era sensibilmente più economico per byte, e zlib puntava a contesti in cui il costo del checksum pesava rispetto alla compressione. Quel vantaggio è in gran parte evaporato. Le implementazioni moderne di CRC-32 usano tabelle slicing-by-8 o istruzioni dedicate, e nelle misure fatte qui il CRC-32 nativo di node ha raggiunto 2 248 MB/s mentre un Adler-32 diretto nello stesso runtime JavaScript si è fermato a 174 MB/s contro i 262 MB/s di CRC-32. I formati restano come specificati perché cambiare algoritmo rompe ogni lettore esistente, ed entrambi bastano al loro compito di cogliere corruzione accidentale in un flusso compresso.

Quanto è probabile una collisione CRC-32 accidentale?

Per un singolo messaggio corrotto la risposta è ottima: le raffiche fino a 32 bit non sfuggono mai, e oltre quella soglia la probabilità di fuga è di circa una su 4 294 967 296. Per una collezione di file è molto peggio di quanto l'intuizione suggerisca, per via dell'effetto compleanno. Due valori casuali a 32 bit collidono con probabilità di una su 4,29 miliardi, ma un insieme di n valori contiene n(n−1)/2 coppie, quindi la soglia del 50 % arriva a 77 163 elementi. Diecimila file portano già l'1,16 % di probabilità che una coppia condivida un CRC-32, e centomila ne portano il 68,8 %. Questo conta se usi CRC-32 come chiave di deduplicazione o identificatore indirizzato per contenuto su un corpus ampio, dove una collisione scarta in silenzio uno di due file diversi. Per un controllo di integrità file per file contro danni di trasporto l'effetto compleanno è irrilevante, perché confronti un valore con un valore atteso, non cerchi corrispondenze in una popolazione.

FNV-1a e MurmurHash3 sono sicuri su chiavi fornite dall'utente?

Senza un seme casuale, no. Entrambi sono privi di chiave per impostazione predefinita, quindi il loro output è una funzione pubblica che chiunque può calcolare offline. Questo consente a un attaccante di precalcolare chiavi che finiscano nello stesso bucket e inviarle tutte insieme: è l'hash flooding. Riprodotto qui su una tabella da 4 096 bucket: 20 000 chiavi fabbricate sono finite tutte nel bucket 0, trasformando una catena massima di 12 in un'unica catena da 20 000 e facendo sì che 20 000 ricerche impiegassero 1 397,9 millisecondi invece di 11,5 — 121 volte più lente, e raccogliere quelle chiavi è costato meno di un secondo di lavoro. La soluzione non è un hash senza chiave più forte; è uno con chiave e seme casuale per processo, che rende impossibile il precalcolo offline. SipHash è la scelta standard ed è ciò che oggi la maggior parte dei runtime usa internamente per i dizionari. Se le tue chiavi vengono dalla configurazione, dal tuo database o da qualsiasi luogo che un attaccante non può influenzare, FNV-1a e MurmurHash3 senza seme restano perfetti e velocissimi.

Che cosa devo usare per chiavi di cache e deduplicazione?

Decidi in base a chi fornisce il contenuto e a quanto costa una risposta sbagliata. Per una cache in memoria le cui chiavi generi tu — una forma di query, il nome di un template renderizzato, un identificatore interno — un hash non crittografico veloce è la scelta giusta, e MurmurHash3 a 730 MB/s è una buona opzione. Per la deduplicazione su un corpus che controlli, dove una collisione significa tenere in silenzio uno di due oggetti diversi, 32 bit sono troppo stretti: il punto compleanno del 50 % arriva a 77 163 elementi. Passa a un hash non crittografico da 64 o 128 bit, o a uno SHA-256 troncato. Per tutto ciò in cui l'utente fornisce il contenuto — file caricati, oggetti generati dagli utenti, un archivio indirizzato per contenuto, una cache condivisa fra più inquilini — usa SHA-256 per intero. Lì una collisione non è un incidente ma una capacità: consente di collocare un oggetto scelto sotto un identificatore già esistente, e solo un hash crittografico rende ciò impraticabile. Il costo è modesto: i 763 MB/s misurati qui superano il livello di archiviazione su cui stai scrivendo.