Post tecnico
Come calcolare il checksum
I checksum di vario tipo sono comunemente utilizzati nei protocolli di comunicazione dati per consentire al destinatario di un messaggio di stabilire, 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, quindi si aggiunge questo valore al messaggio prima di inviarlo, il destinatario può ripetere la stessa somma sui primi N – 1 byte del messaggio e confrontare il risultato con l'ultimo byte per verificare se corrisponde a 96. In caso affermativo, il destinatario può dedurre che il messaggio probabilmente non è stato alterato durante la trasmissione.
Esistono numerose tecniche di checksum in uso comune. Tra le più diffuse vi 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 unidirezionale appartenente alla famiglia dei "generatori lineari congruenziali".
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 decisamente più affidabili di altre.
Vediamo come calcolare LRC, checksum e CRC utilizzando JavaScript.
Come calcolare il checksum con il metodo tradizionale
Il checksum convenzionale a 8 bit è esattamente ciò che suggerisce il nome: la somma di tutti i valori dei byte nell'input, con eventuale overflow (derivante dalle operazioni di riporto) scartato. In JavaScript:
L'input di questa funzione deve essere una stringa esadecimale nel formato "48656C6C6F20776F726C6421" (che in questo caso corrisponde alla versione esadecimale della stringa ASCII "Hello world!"). Utilizzando "48656C6C6F20776F726C6421" come input per la funzione sopra indicata, il risultato sarà "5d", ovvero il valore esadecimale della somma finale a 8 bit.
Il codice è molto semplice. Si comincia (alla riga 3) analizzando l'input esadecimale suddividendolo in blocchi di due nibble tramite l'espressione regolare /../g — che significa: trovare le sottostringhe che corrispondono al pattern "qualsiasi carattere seguito da qualsiasi carattere" (questo è il significato dei due punti), in modo globale (questo è il significato della 'g')". Il risultato è un array, s, di valori esadecimali a due cifre.
Alla riga 5, entriamo in un ciclo (utilizzando il costrutto di iterazione forEach ) in cui convertiamo la versione stringa di un valore esadecimale a due nibble in un numero effettivo su cui possiamo operare. Alla riga 7, eseguiamo la vera e propria somma. Si noti che il numero sum è essenzialmente un intero a 32 bit, in background, 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. Questo viene fatto alla riga 9, tramite l'AND logico con 255. Allo stesso tempo, eseguiamo la conversione in esadecimale utilizzando il metodo toString() , con un argomento pari a 16 (che indica che vogliamo utilizzare la base 16 nella rappresentazione finale del numero).
Alle righe 10 e 11, è necessario verificare che il valore esadecimale finale sia lungo 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.
Se si desidera provare il codice, copiare e incollare il codice sopra riportato nella console JS (in Chrome, utilizzare Shift-Cmd-J per aprire la console), quindi aggiungere una riga in fondo (all'esterno della funzione) con CHECKSUM("48656C6C6F20776F726C6421"). Premendo Invio, la console dovrebbe mostrare '5d' come valore restituito.
Come calcolare il checksum con LRC
Il controllo di ridondanza longitudinale (LRC) è una variante del checksum a 8 bit, che si differenzia unicamente per il fatto che la "somma" viene eseguita tramite XOR anziché con l'addizione numerica.
Nella riga 6 è possibile osservare l'operatore XOR in-place (^=).
Poiché lo XOR non genera mai overflow, non è necessario limitare 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, il risultato ottenuto dovrebbe essere '21'.
Limiti del Checksum e dell'LRC
Né il checksum né l'LRC possono essere considerati strumenti affidabili contro la corruzione dei messaggi. Si consideri, ad esempio, il messaggio originale ("48656C6C6F20776F726C6421"): supponendo di modificare gli ultimi due byte del messaggio da 6421 a 6520, sia l'LRC che il checksum rimarrebbero invariati. In pratica, si è attivato un bit in un byte a monte e disattivato lo stesso bit in posizione corrispondente a valle, generando due modifiche che si annullano reciprocamente al momento del calcolo del checksum.
Analogamente, si consideri cosa accade invertendo il messaggio, ovvero invertendone l'ordine dei byte in modo che inizi con 21 e termini con 48. Anche in questo caso, LRC e checksum restano identici a quelli del messaggio originale. Ciò è dovuto al fatto che tanto lo XOR quanto l'addizione sono operazioni commutative: A + B sarà sempre uguale a B + A.
Si consideri inoltre che, poiché un LRC o checksum a 8 bit può assumere solo 256 valori distinti, esiste una probabilità di 1 su 256 che un messaggio produca lo stesso LRC (o checksum) di un altro messaggio scelto casualmente.
In generale, gli algoritmi di checksum e LRC sono facilmente "aggirabili" e non risultano particolarmente affidabili per la verifica dell'integrità dei messaggi.
Fortunatamente, esistono algoritmi più efficaci dell'LRC o del checksum per la verifica dell'integrità, sebbene comportino un maggiore onere computazionale.
Come calcolare il Checksum con CRC
Quando la verifica dell'integrità riveste un'importanza critica, è generalmente necessario ricorrere a un hash non commutativo. Spesso si tratta di un hash crittografico, come SHA-1 o MD5, che tuttavia sono computazionalmente intensivi e possono risultare eccessivi in molti contesti applicativi.
Un buon compromesso tra overhead computazionale e affidabilità è rappresentato dal Cyclic Redundancy Check, disponibile in varie versioni; il CRC a 16 bit descritto di seguito è tuttavia adeguato (e molto diffuso) per messaggi brevi (fino a circa 4 kilobyte).
Il CRC è un argomento interessante, ma lo spazio non consente di trattarlo in modo esaustivo in questa sede. (Si rimanda a Google.) Basti dire, da un punto di vista pratico, che un CRC a due byte offre un'elevata sensibilità ai bit invertiti casualmente nei dati ed è improbabile che generi falsi positivi in presenza di dati con inversioni multiple di bit. Per questo motivo, e perché è semplice da implementare in hardware o software, ed eseguito molto rapidamente con un utilizzo minimo di memoria, lo si trova impiegato in numerosi ambienti di comunicazione dati, tra cui i driver per dischi di archiviazione (dove gli errori su disco vengono spesso rilevati tramite CRC), i modem e i piccoli dispositivi elettronici (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 formato hex-ASCII).
Il CRC implementa un algoritmo di hash che può essere descritto come segue:
- Impostare il valore iniziale di crc a 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 di tabella per recuperare un "byte di sostituzione" dalla tabella nota come crcTable — Riga 15
- Scorrere il valore crc a SINISTRA di 8 bit 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 tutto l'input in questo modo, applicare uno XOR del risultato con zero e conservare i 16 bit meno significativi del CRC — Riga 17
Utilizziamo una piccola routine di utilità per convertire il numero finale da intero a stringa esadecimale:
Se si caricano entrambe queste funzioni (numToHex e CRC) nella console JS del browser e si esegue CRC( "48656C6C6F20776F726C6421" ), si dovrebbe ottenere un CRC pari a 'BD22' per il dato di input "Hello world!".
Come 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 del dato da 21 a 20, il CRC cambia in 'AD03', che non ha alcuna relazione con 'BD22'. Modificando invece gli ultimi due byte in '6520' si ottiene un CRC di '9E32'. (Si ricordi che questa stessa modifica non ha alterato né LRC né il checksum.)
Si consideri una stringa che rappresenta dieci byte zero (null). Il valore LRC di tale stringa sarebbe zero. Il checksum sarebbe ovviamente zero. Il CRC, invece, sarebbe E139.
È abbastanza semplice convincersi che invertire l'input produrrebbe un CRC completamente diverso rispetto all'utilizzo dell'input nella direzione originale. (Cosa che non valeva per LRC o checksum.) Il CRC non è commutativo, a causa del modo in cui gli 8 bit più significativi del CRC vengono sottoposti a XOR con il byte di input prima di traslare tutto verso sinistra (in modo simile a come funziona il cipher block chaining , con la differenza che in questo caso la dimensione del "cipher block" è di 8 bit).
Va notato che, sebbene il CRC sia un hash unidirezionale, non si tratta di un hash crittografico in senso stretto, poiché è in realtà piuttosto semplice calcolare un "valore di correzione" che, se aggiunto in coda ai dati, farebbe sì che una determinata alterazione dei dati produca il CRC finale desiderato. (Ciò non vale per i cosiddetti hash crittografici, per i quali è difficile calcolare un "fattore di correzione" in grado di ricondurre un blocco di dati alterato all'hash desiderato.) Il CRC è quindi adatto al rilevamento di corruzione involontaria dei dati.
Conclusione
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. Ma nelle situazioni che coinvolgono quantità di dati non trascurabili e requisiti stringenti di integrità dei dati, è quasi inevitabile ricorrere a un hash di tipo "generatore congruenziale lineare" . La famiglia di algoritmi CRC è stata ottimizzata e perfezionata nel tempo per offrire un'ottima capacità di discriminazione dell'integrità, unita a semplicità di implementazione, esecuzione rapida e requisiti di memoria ridotti. Queste caratteristiche rendono il CRC una soluzione attraente per un'ampia varietà di scenari di verifica dei dati, che spaziano dagli hard disk ai lettori di carte di credito.