Come potrei indovinare un algoritmo di checksum?

Question

Supponiamo che alla fine abbia alcuni pacchetti con un checksum a 16 bit. Vorrei indovinare quale algoritmo di checksum viene utilizzato.

Per cominciare, dai dati di dump posso vedere che un byte cambia nel payload del pacchetto cambia totalmente il checksum, quindi posso presumere che non sia una sorta di semplice XOR o somma.

Quindi ho provato diverse varianti di CRC16 , ma senza molta fortuna.

Questa domanda potrebbe essere più distorta verso la crittografia, ma sono davvero interessato a qualsiasi strumento statistico di facile comprensione per scoprire quale CRC potrebbe essere. Potrei anche passare a disegnare diversi algoritmi CRC se tutto il resto fallisce.

Storia di Backgroud: ho un protocollo RFID seriale con una sorta di checksum. Posso riprodurre i messaggi senza problemi e interpretare i risultati (senza controllo del checksum), ma non riesco a inviare pacchetti modificati perché il dispositivo li rilascia sul pavimento.

Utilizzando il software esistente, posso modificare il payload del chip RFID. Tuttavia, il numero di serie univoco è immutabile, quindi non ho la possibilità di controllare ogni possibile combinazione. Anche se potrei generare dump di valori incrementando di uno, ma non abbastanza per rendere la ricerca esaustiva applicabile a questo problema.

file di dump con dati sono disponibili se la domanda stessa non basta :-)

Hai bisogno di documentazione di riferimento? UNA GUIDA SENZA PAIN IN CRC ALGORITMI DI RILEVAMENTO DEGLI ERRORI è un ottimo riferimento che ho trovato dopo aver posto la domanda qui.

Alla fine, dopo un suggerimento molto utile nella risposta accettata rispetto a CCITT, I ha utilizzato questo calcolatore CRC e ha generato un checksum generato da xored con checksum noto per ottenere 0xffff che mi ha portato a conclusione che xor finale è 0xffff, come indicato da 0x0000 di CCITT.

Answer 1

Esistono diverse variabili da considerare per un CRC:

Polynomial
No of bits (16 or 32)
Normal (LSB first) or Reverse (MSB first)
Initial value
How the final value is manipulated (e.g. subtracted from 0xffff), or is a constant value

CRC tipici:

LRC:    Polynomial=0x81; 8 bits; Normal; Initial=0; Final=as calculated
CRC16:  Polynomial=0xa001; 16 bits; Normal; Initial=0; Final=as calculated
CCITT:  Polynomial=0x1021; 16 bits; reverse; Initial=0xffff; Final=0x1d0f
Xmodem: Polynomial=0x1021; 16 bits; reverse; Initial=0; Final=0x1d0f
CRC32:  Polynomial=0xebd88320; 32 bits; Normal; Initial=0xffffffff; Final=inverted value
ZIP32:  Polynomial=0x04c11db7; 32 bits; Normal; Initial=0xffffffff; Final=as calculated

La prima cosa da fare è ottenere alcuni campioni cambiando diciamo l'ultimo byte. Questo ti aiuterà a capire il numero di byte nel CRC.

Questo è un "fatto in casa"? algoritmo. In questo caso potrebbe richiedere del tempo. Altrimenti prova gli algoritmi standard.

Prova a cambiare msb o lsb dell'ultimo byte e guarda come questo cambia il CRC. Ciò fornirà un'indicazione della direzione.

Per renderlo più difficile, ci sono implementazioni che manipolano il CRC in modo che non influisca sul mezzo di comunicazione (protocollo).

Dal tuo commento su RFID, implica che il CRC è legato alle comunicazioni. Di solito CRC16 viene utilizzato per le comunicazioni, sebbene CCITT sia utilizzato anche su alcuni sistemi.

D'altra parte, se si tratta di tag RFID UHF, ci sono alcuni schemi CRC - uno a 5 bit e alcuni a 16 bit. Questi sono documentati negli standard ISO e nelle schede tecniche IPX.

IPX:  Polynomial=0x8005; 16 bits; Reverse; Initial=0xffff; Final=as calculated
ISO 18000-6B: Polynomial=0x1021; 16 bits; Reverse; Initial=0xffff; Final=as calculated
ISO 18000-6C: Polynomial=0x1021; 16 bits; Reverse; Initial=0xffff; Final=as calculated
    Data must be padded with zeroes to make a multiple of 8 bits
ISO CRC5: Polynomial=custom; 5 bits; Reverse; Initial=0x9; Final=shifted left by 3 bits
    Data must be padded with zeroes to make a multiple of 8 bits
EPC class 1: Polynomial=custom 0x1021; 16 bits; Reverse; Initial=0xffff; Final=post processing of 16 zero bits

Ecco la tua risposta !!!!

Dopo aver esaminato i log, il CRC è quello CCITT. Il primo byte 0xd6 è escluso dal CRC.

Answer 2

Dovresti provare ogni possibile algoritmo di checksum e vedere quale genera lo stesso risultato. Tuttavia, non vi è alcuna garanzia su quale contenuto sia stato incluso nel checksum. Ad esempio, alcuni algoritmi saltano gli spazi bianchi, che portano a risultati diversi.

Non vedo davvero perché qualcuno dovrebbe saperlo però.

Answer 3

Potrebbe non essere un CRC, potrebbe essere un errore che corregge il codice come Reed-Solomon.

I codici ECC sono spesso una frazione sostanziale della dimensione dei dati originali che proteggono, a seconda del tasso di errore che vogliono gestire. Se la dimensione dei messaggi è superiore a circa 16 byte, 2 byte di ECC non sarebbero sufficienti per essere utili. Quindi, se il messaggio è di grandi dimensioni, è molto probabile che si tratti di una sorta di CRC.

Answer 4

Sto provando a risolvere un problema simile qui e ho trovato un sito web abbastanza pulito che prenderà il tuo file ed eseguirà checksum su di esso con 47 algoritmi diversi e mostrerà i risultati. Se l'algoritmo utilizzato per calcolare il checksum è uno di questi algoritmi, lo troveresti semplicemente nell'elenco dei checksum prodotti con una semplice ricerca di testo.

Il sito web è https://defuse.ca/checksums.htm