Le righe hanno la forma «ALGORITMO valore» seguita da una riga di parametri rientrata, così un risultato copiato e incollato indica sempre quale set di parametri lo ha prodotto.
CRC — controllo di ridondanza ciclica, spiegato da zero
In una frase: un CRC tratta i dati come un unico numero binario enorme, lo divide per un numero «generatore» fisso usando lo XOR al posto della sottrazione e riporta il resto — un'impronta compatta che cambia drasticamente anche quando si inverte un solo bit dell'input, ed è per questo che tutto, dai file PNG ai cavi Modbus, ne porta uno.
Che cos'è davvero un CRC
L'immagine della divisione. Allinei i byte come un unico lungo numero binario. Scelga un divisore — il polinomio, per es. 0x04C11DB7 per CRC-32. Esegua la divisione binaria lunga in cui la «sottrazione» è l'operazione XOR: ogni volta che il bit iniziale del resto corrente è 1, applichi XOR con il divisore, sposti a sinistra e ripeta. Dopo aver fatto passare l'intero messaggio, ciò che resta nel registro è il CRC. Nessuna chiave, nessuna tabella nella definizione — solo una divisione con resto.
I cinque parametri. Due sistemi possono entrambi dire «CRC-32» e comunque non essere d'accordo, perché il solo nome non stabilisce nulla. La ricetta completa richiede cinque valori: poly (il divisore), init (il valore iniziale del registro — lo zero fa sparire gli zeri iniziali, il tutto-uno no), refin/refout (se ogni byte in ingresso — e il registro finale — è invertito bit per bit, retaggio dell'hardware seriale che inviava i bit a partire dal meno significativo) e xorout (una maschera XOR finale, così una sequenza di zeri finali cambia comunque il risultato). Questa pagina stampa tutti e cinque accanto a ogni risultato proprio per questo motivo.
Perché rileva gli errori. Un divisore ben scelto fa sì che il resto di un messaggio e il resto dello stesso messaggio con alcuni bit alterati differiscano con probabilità schiacciante: un buon CRC-32 individua tutti gli errori di 1 e 2 bit, tutti i numeri dispari di errori di bit e ogni raffica di fino a 32 bit consecutivi corrotti — con garanzia, non in modo probabilistico. Questa garanzia riguarda la corruzione accidentale, ed è ciò che rende i CRC lo strumento giusto per cavi rumorosi e dischi difettosi.
Che cosa un CRC non è
Non è un hash crittografico. Non c'è alcun segreto né alcuna irreversibilità: chiunque conosca i parametri può falsificare un messaggio con il CRC che desidera, in millisecondi, aggiungendo quattro byte correttivi. Un CRC rileva gli incidenti, mai gli avversari. Per i download che verifica con sconosciuti contano le firme — veda invece il Generatore di hash (MD5/SHA/BLAKE2). Quella pagina spiega anche perché MD5 e SHA-1 sono ritirati in contesti ostili mentre SHA-256 resta valido.
Non è un codice correttore. Un CRC le dice che qualcosa è cambiato, non che cosa è cambiato. Riparare gli errori al volo è il compito di codici come Reed–Solomon o Hamming, che memorizzano deliberatamente una struttura ridondante che un decodificatore può invertire.
Non è compressione né cifratura. Il resto occupa pochi byte indipendentemente dalla dimensione dell'input, e da esso non è possibile recuperare l'input — ma a differenza di un hash crittografico questo accade solo perché l'informazione è stata scartata, non perché l'inversione sia difficile.
Le famiglie di questa pagina
La quaterna CRC-32. Quattro voci di questa pagina condividono il poly 0x04C11DB7 e producono comunque valori diversi: ISO-HDLC (riflesso, init e xorout tutti a uno) è «il» CRC-32 di zlib, gzip, PNG e ZIP; BZIP2 è la stessa matematica non riflessa; MPEG-2 è BZIP2 senza XOR finale; POSIX parte da zero ed è la base del comando cksum (che inoltre aggiunge la lunghezza del file alla divisione, quindi il cksum di un file e il CRC-32/POSIX degli stessi byte differiscono). CRC-32C (Castagnoli, poly 0x1EDC6F41) è il quinto fratello: un poly diverso scelto per migliori prestazioni di rilevamento degli errori, e quello che le moderne CPU x86 e ARM possono calcolare alla velocità della memoria con una sola istruzione.
La quaterna CRC-64. XZ usa il polinomio ECMA-182 in forma riflessa con init e xorout tutti a uno; ECMA-182 stesso è l'originale non riflesso con init a zero dello standard per nastri DLT-1; GO-ISO è crc64.ISO di Go, un poly minuscolo 0x1B, ancora riflesso; REDIS usa un poly scelto per una buona diffusione nell'assegnazione degli slot hash. Sessantaquattro bit è la dimensione in cui i CRC iniziano a essere usati come funzioni hash (per la suddivisione in bucket) anziché come pure somme di controllo.
Adler-32 è l'outsider: non è affatto una divisione. Somma i byte (A, partendo da 1) e somma quelle somme (B), entrambe modulo 65521, e concatena le due somme a 16 bit. È più veloce del CRC-32 nel software e zlib lo usa per i flussi deflate — ma per input brevi (sotto qualche centinaio di byte) la somma porta troppo poca informazione, ed è proprio per questo che zlib torna al CRC-32 per i blocchi piccoli.
CRC-8 e CRC-16 sopravvivono dove i byte sono costosi: CRC-8/CCITT (poly 0x07) protegge i singoli byte di intestazione in SMBus e nei protocolli delle radio cellulari; CRC-16/CCITT-FALSE protegge i blocchi delle smart card; CRC-16/MODBUS è la somma di controllo di ogni frame Modbus RTU negli stabilimenti industriali di tutto il mondo.
Dove vive ciascuno
| Set di parametri | Presente in |
|---|
| CRC-32/ISO-HDLC | zlib, gzip, PNG, ZIP, Ethernet (FCS), molti formati di archivio |
| CRC-32C | iSCSI, ext4, btrfs, ZFS, istruzione hardware CRC32C di SSE4.2/ARMv8 |
| CRC-32/BZIP2 | flusso di archivio .bz2 |
| CRC-32/MPEG-2 | flussi di trasporto MPEG-2 |
| CRC-32/POSIX & cksum | output del comando POSIX cksum (cksum file.txt) |
| CRC-16/MODBUS | frame Modbus RTU (PLC industriali, contatori, inverter) |
| CRC-16/CCITT-FALSE | smart card, collegamenti affini a X.25, alcuni protocolli GPS |
| CRC-8/CCITT | SMBus (byte PEC), intestazioni delle radio cellulari |
| CRC-64/XZ | controlli di integrità del contenitore .xz |
| CRC-64/ECMA-182 | ECMA-182 / standard per nastri DLT-1 |
| CRC-64/GO-ISO | libreria standard di Go crc64.ISO |
| CRC-64/REDIS | assegnazione degli slot hash nel cluster Redis |
| Adler-32 | flussi zlib (deflate), altri contesti di checksum veloce |
La tabella di ancoraggio — check(«123456789»)
La convenzione del catalogo CRC è pubblicare il risultato per la stringa ASCII 123456789 (9 byte). Ogni valore sotto è riproducibile su questa pagina: digiti 123456789 nella casella Testo, spunti l'algoritmo e prema Calcola.
| Set di parametri | Larghezza | Valore di controllo (esadecimale) |
|---|
| CRC-8/CCITT | 8 | 0xf4 |
| CRC-16/CCITT-FALSE | 16 | 0x29b1 |
| CRC-16/MODBUS | 16 | 0x4b37 |
| CRC-32/ISO-HDLC | 32 | 0xcbf43926 |
| CRC-32C | 32 | 0xe3069283 |
| CRC-32/BZIP2 | 32 | 0xfc891918 |
| CRC-32/MPEG-2 | 32 | 0x0376e6e7 |
| CRC-32/POSIX | 32 | 0x765e7680 |
| cksum (POSIX command) | 32 | 0x377a6011 |
| CRC-64/XZ | 64 | 0x995dc9bbdf1939fa |
| CRC-64/ECMA-182 | 64 | 0x6c40df5f0b497347 |
| CRC-64/GO-ISO | 64 | 0xb90956c775a41001 |
| CRC-64/REDIS | 64 | 0xe9c6d914c4b8d9ca |
| Adler-32 | 32 | 0x091e01de |
Fonti: ogni valore è stato verificato incrociatamente con un'implementazione di riferimento bit per bit indipendente e, dove esiste, con la libreria di sistema che include l'algoritmo (zlib per CRC-32 e Adler-32; il catalogo CRC di Greg Cook per gli altri).
Errori comuni
- «CRC-32» senza parametri. Tra ISO-HDLC, BZIP2, MPEG-2, POSIX e CRC-32C circolano cinque valori diversi con lo stesso nome. Registri sempre poly/init/refin/refout/xorout insieme al risultato — questa pagina li stampa per lei.
- Confrontare il CRC-32 di un file con l'output di
cksum. Sono algoritmi diversi: cksum aggiunge la lunghezza e usa un init diverso. I numeri non coincideranno, ed entrambi sono «corretti».
- Fidarsi del CRC contro le manomissioni. Falsificare un CRC corrispondente è un esercizio da manuale (modificare gli ultimi 4 byte). Usi un MAC con chiave (HMAC) o una firma quando l'altra parte potrebbe essere ostile.
- Aspettarsi l'effetto valanga. Un CRC è lineare: messaggi correlati producono CRC correlati. Va bene per il rumore, non per l'hashing — se le serve la suddivisione in bucket, CRC-64 o un vero hash è più sicuro del CRC-32.
- Testo esadecimale contro byte. La stringa
"123456789" (9 byte ASCII, 31 32 33 34 35 36 37 38 39) e il numero 0x123456789 sono input diversi con CRC diversi. Usi la scheda Byte esadecimali quando i dati di partenza sono davvero binari.
Domande frequenti
Perché il mio CRC-32 non coincide con quello nel file ZIP? Il CRC-32 di ZIP è ISO-HDLC sui dati non compressi. Assicuri di aver calcolato il CRC degli stessi byte (non del flusso compresso), nella stessa modalità (Testo o Esadecimale) e con lo stesso set di parametri — la riga dei parametri stampata sotto ogni risultato serve a fare questo controllo immediatamente.
Quale è migliore, CRC-32C o CRC-32? Per il rilevamento degli errori accidentali entrambi individuano tutte le raffiche fino a 32 bit; il CRC-32C funziona meglio con alcuni schemi di errore ed è quello con l'istruzione dedicata della CPU — praticamente gratuito a velocità gigabit. Il motivo per cui CRC-32/ISO-HDLC sopravvive è la compatibilità: trent'anni di archivi lo usano.
Il CRC-64 è più forte del CRC-32? Rileva raffiche più lunghe (fino a 64 bit) e produce molte meno collisioni se usato per la suddivisione in bucket, ma è ugualmente falsificabile — la larghezza dà garanzie di rilevamento, non sicurezza.
Un CRC può essere invertito per rivelare l'input? No — infiniti input condividono lo stesso CRC. Ma a differenza di un hash crittografico, un attaccante può costruire un input con il CRC che sceglie, ed è in questo senso che non è affatto unidirezionale.
