Post tecnico
Come calcolare il checksum
I checksum di vario tipo sono ampiamente utilizzati nei protocolli di comunicazione dati per consentire al destinatario di un messaggio di verificare, in modo rapido e semplice, se i dati abbiano subito alterazioni durante la trasmissione. Se si sommano tutti i byte di un messaggio e si ottiene (trascurando l'overflow) un totale di 96, è sufficiente aggiungere quel valore in coda al messaggio prima di inviarlo. Il destinatario potrà ripetere la somma sui primi N – 1 byte del messaggio e confrontare il risultato con l'ultimo byte per verificare che sia 96. In caso affermativo, potrà concludere che il messaggio non è stato probabilmente alterato durante la trasmissione.
Esistono numerose tecniche di checksum in uso comune. Tre tra le più diffuse sono il checksum convenzionale, l'LRC (longitudinal redundancy check) e il CRC (cyclic redundancy check). Quest'ultimo non è propriamente un checksum nel senso tradizionale del termine, ma rappresenta un esempio di funzione hash a senso unico appartenente alla famiglia dei "generatori congruenziali lineari".
Come accennato in precedenza, queste tecniche di verifica dell'integrità dei dati consentono di stabilire se i dati "abbiano probabilmente subito alterazioni". Nessuna tecnica di checksum è infallibile al 100% nel caso generale, per dati di lunghezza arbitraria. Tuttavia, alcune tecniche sono indubbiamente più affidabili di altre.
Vediamo come calcolare LRC, checksum e CRC utilizzando JavaScript.
Come calcolare il checksum nel modo tradizionale
Il checksum convenzionale a 8 bit è esattamente ciò che suggerisce il nome: la somma di tutti i valori dei byte in ingresso, scartando qualsiasi overflow derivante dalle operazioni di riporto. In JavaScript:
L'input di questa funzione deve essere una stringa esadecimale del tipo "48656C6C6F20776F726C6421" (che in questo caso corrisponde alla rappresentazione esadecimale della stringa ASCII "Hello world!"). Utilizzando "48656C6C6F20776F726C6421" come input per la funzione sopra indicata, l'output sarà "5d", ovvero il valore esadecimale della somma finale a 8 bit.
Il codice è molto semplice. Si inizia (alla riga 3) analizzando l'input esadecimale in blocchi di due nibble tramite l'espressione regolare /../g — che significa: trova le sottostringhe che corrispondono al pattern "qualsiasi carattere seguito da qualsiasi carattere" (questo è il significato dei due punti), e fallo globalmente (questo è il significato della 'g'). Il risultato è un array, s, di valori esadecimali a due cifre.
Alla riga 5 si entra in un ciclo (utilizzando il costrutto di iterazione forEach ) nel quale si converte la rappresentazione stringa di un valore esadecimale a due nibble in un numero effettivo su cui poter operare. Alla riga 7 si esegue la somma vera e propria. Si noti che il numero sum è essenzialmente un intero a 32 bit a livello interno, il che significa che il valore finale potrebbe essere molto superiore a 255. Al termine del ciclo, è necessario assicurarsi di limitare la somma a un valore a 8 bit. Ciò avviene alla riga 9, tramite l'AND logico con 255. Contestualmente, si converte nuovamente in esadecimale usando il metodo toString() con argomento 16 (che indica l'utilizzo della base 16 nella rappresentazione finale del numero).
Alle righe 10 e 11 occorre verificare che il valore esadecimale finale sia composto da due nibble. L'operazione toString(16) di JavaScript restituisce un valore a singola cifra per valori inferiori a 10. In tal caso, è necessario anteporre '0' al risultato.
Per provare il codice, copiare e incollare il codice sopra riportato nella console JS (in Chrome, usare Shift-Cmd-J per aprire la console), quindi aggiungere una riga in fondo (fuori dalla funzione) con CHECKSUM("48656C6C6F20776F726C6421"). Premendo Invio, la console dovrebbe restituire '5d' come valore di ritorno.
Come calcolare il checksum con LRC
Il controllo di ridondanza longitudinale (LRC) è una variante del checksum a 8 bit; l'unica differenza è che la "somma" viene eseguita tramite XOR anziché con l'addizione numerica.
Alla riga 6 è possibile osservare l'operatore XOR in-place (^=).
Poiché XOR non genera mai overflow, non è necessario vincolare il risultato finale a 8 bit tramite un'operazione AND. È sufficiente verificare una lunghezza di due nibble e restituire il valore finale.
Se si esegue il codice nella console utilizzando la stringa indicata in precedenza, si dovrebbe ottenere il risultato '21'.
Analisi critica del checksum e di LRC
Né il checksum né LRC possono essere considerati strumenti affidabili contro la corruzione dei messaggi. Si consideri, ad esempio, il messaggio originale ("48656C6C6F20776F726C6421"): se si modificano gli ultimi due byte del messaggio da 6421 a 6520, sia LRC che il checksum rimangono invariati. In pratica, si attiva un bit in un byte a monte e si disattiva lo stesso bit in posizione corrispondente a valle, generando due modifiche che si annullano reciprocamente al momento del calcolo del checksum.
Allo stesso modo, si consideri cosa accade invertendo il messaggio byte per byte (in modo che inizi con 21 e termini con 48): anche in questo caso, LRC e checksum rimangono identici a quelli del messaggio originale. Ciò dipende dal fatto che XOR e l'addizione sono operazioni commutative: A + B sarà sempre uguale a B + A.
Si tenga inoltre presente che, poiché un LRC o un checksum a 8 bit può assumere solo 256 valori distinti, vi è una probabilità di 1 su 256 che un messaggio produca lo stesso LRC (o checksum) di un altro messaggio scelto casualmente.
In generale, è molto facile "ingannare" gli algoritmi di checksum e LRC, motivo per cui non risultano particolarmente affidabili per la verifica dell'integrità dei messaggi.
Fortunatamente, esistono algoritmi più efficaci di LRC o checksum per il controllo dell'integrità, sebbene comportino un maggiore onere computazionale.
Come calcolare il checksum con CRC
Quando il controllo dell'integrità è davvero critico, in linea di massima è necessario utilizzare un hash non commutativo. Spesso questo significa ricorrere a un hash crittografico, come SHA-1 o MD5, ma questi sono computazionalmente intensivi e possono risultare "eccessivi" in molte situazioni.
Un buon compromesso tra overhead computazionale e affidabilità si trova nel Cyclic Redundancy Check, disponibile in varie versioni; il CRC a 16 bit descritto di seguito è adeguato (e piuttosto diffuso) per messaggi brevi (fino a circa 4 kilobyte).
Il CRC è un argomento interessante, ma lo spazio non consente un trattamento esaustivo in questa sede. (Si rimanda a Google per approfondimenti.) È sufficiente dire che, da un punto di vista pratico, un CRC a due byte offre un'ottima sensibilità ai bit-flip casuali nei dati ed è improbabile che generi falsi positivi con dati che contengono più bit-flip. Per questo motivo, e perché è facile da implementare in hardware o software, funziona molto rapidamente e richiede pochissima memoria, lo si trova impiegato in svariati ambienti di comunicazione dati, tra cui i driver dei dischi di archiviazione (dove gli errori sul disco vengono spesso rilevati tramite CRC), i modem e i dispositivi elettronici di piccole dimensioni (inclusi tutti i lettori di carte di credito della serie ViVOpay di ID TECH).
Il seguente codice JavaScript mostra come calcolare un valore CRC a 16 bit (restituito come quattro nibble in esadecimale ASCII).
Il CRC implementa un algoritmo di hash che può essere descritto in italiano come:
- Impostare il valore iniziale di crc come 0xFFFF — Riga 10
- Leggere un byte di dati in ingresso (come numero a 8 bit) — Riga 13
- Scorrere a destra il valore crc esistente di 8 bit — Riga 14
- Eseguire lo XOR tra il crc traslato a destra e il byte in ingresso — Riga 14
- Utilizzare il valore risultante j (solo gli 8 bit inferiori) come offset nella tabella per ricercare un "byte di sostituzione" dalla tabella nota come crcTable — Riga 15
- Scorrere il valore crc di 8 bit a SINISTRA e applicare uno XOR con il "byte di sostituzione" — Riga 15
- Ripetere queste operazioni, a partire dalla Riga 13, utilizzando il byte successivo dell'input
- Dopo aver elaborato tutti i dati di input in questo modo, applicare uno XOR del risultato con zero e conservare i 16 bit inferiori del CRC — Riga 17
Utilizziamo una piccola routine di utilità per convertire il numero finale da intero a stringa esadecimale:
Se si caricano entrambe le funzioni (numToHex e CRC) nella console JS del browser e si esegue CRC( "48656C6C6F20776F726C6421" ), si dovrebbe ottenere un CRC per i dati di input "Hello world!" pari a 'BD22'.
A titolo di esercizio, si potrebbe provare a invertire un bit nell'input per osservare l'effetto sull'output. Ad esempio, utilizzando la stringa "Hello world!" come input e modificando l'ultimo byte dei dati da 21 a 20, il CRC cambia in 'AD03', che non ha alcuna relazione con 'BD22'. Modificando gli ultimi due byte in '6520' si ottiene un CRC di '9E32'. (Si ricorda che questa stessa modifica non ha alterato né LRC né il checksum.)
Consideriamo una stringa che rappresenta dieci byte zero (nulli). Il valore LRC di tale stringa sarebbe zero. Il checksum sarebbe ovviamente zero. Ma il CRC sarebbe E139.
È abbastanza semplice convincersi che invertire l'ordine dell'input produrrebbe un CRC completamente diverso rispetto all'input nella direzione originale. (Il che non era vero per LRC o checksum.) Il CRC non è commutativo, per via del modo in cui gli 8 bit più significativi del CRC vengono sottoposti a XOR con il byte di input prima di scorrere tutto verso sinistra (simile al funzionamento del cipher block chaining , con la differenza che in questo caso la dimensione del "blocco cifrato" è di 8 bit).
Si noti che, pur essendo il CRC un hash unidirezionale, non si tratta propriamente di un hash crittografico, poiché è in realtà piuttosto semplice calcolare un "valore correttivo" che, se aggiunto in coda ai dati, farebbe sì che una determinata modifica dei dati produca il CRC finale desiderato. (Ciò non vale per i cosiddetti hash crittografici, per i quali è difficile calcolare un "fattore correttivo" in grado di ricondurre un blocco di dati alterato all'hash desiderato.) Il CRC è quindi adatto al rilevamento di corruzione accidentale dei dati.
Conclusioni
Non mancano gli algoritmi di "verifica dell'integrità" utilizzabili per monitorare la corruzione dei pacchetti di dati. In alcuni casi è sufficiente un semplice checksum o LRC. Tuttavia, per situazioni che coinvolgono quantità non trascurabili di dati e requisiti stringenti di integrità, è quasi obbligatorio ricorrere a un hash di tipo "linear congruential generator" . La famiglia di algoritmi CRC è stata messa a punto e ottimizzata per garantire un'efficace discriminazione dell'integrità, unita a semplicità di implementazione, esecuzione rapida e ridotto consumo di memoria, rendendo il CRC una soluzione interessante per un'ampia varietà di scenari di verifica dei dati, che spaziano dagli hard disk ai lettori di carte di credito.