Jeg skjønte det! Noen av kommentarene på dette nettstedet fikk meg til å tenke hardere - faktisk å tenke annerledes.

Jeg tenkte at jeg skulle legge ut analysen jeg gjorde på disse meldingene for å prøve å bestemme CRC-algoritmen.

Analysen min er basert på et papir skrevet av Greg Ewing http://www.cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.html. Han presenterte mye innsikt i papiret. Jeg vil ikke gjenta det han skrev, bortsett fra å oppsummere og forklare resultatene mine ved hjelp av hans metode. Så følg med papiret hans mens jeg presenterer dataene mine.

Han viste at CRCs "adlyder et slags superposisjonsprinsipp. Du kan tenke på CRC som består av det eksklusive eller et sett med komponent CRC-er, som hver avhenger av bare en bit i meldingen.

Han viste hvor, for XorIn = XorOut = 0x0000, at:

C1 xor C2 = M1 xor M2where: Cx = CRC Mx = meldinger av samme lengde

Han kalte "M1 xor M2" en forskjellmelding.

Greg skrev: "Så kom jeg inn i en samtale med Patrick Maupin, som foreslo en test som kan bidra til å avklare om det var en ekte CRC eller ikke. På grunn av superposisjonsprinsippet, hvis endring av en melding ved å xore den med et bitmønster B1 får CRC til å endre seg med C1, og et annet bitmønster B2 får CRC til å endre seg med C2, bør xoring av meldingen med (B1 xeller B2) endre CRC med (C1 xeller C2). Hvis dette ikke skjer, kan ikke algoritmen være en vanlig CRC-algoritme. "

Ved å bruke disse 4-meldingene fra sender til mottakerbitstrøm:

  CRC LSB MSB ---- ---- ---- ---- ---- ---- ---- ---- M0 0x00 0x09 0x69 0x31 0x00 0x03 0xBA 0xDEM1 0x00 0x09 0x69 0x31 0x01 0x03 0x01 0xC2M2 0x00 0x09 0x69 0x31 0x02 0x03 0xCC 0xE7M3 0x00 0x09 0x69 0x31 0x03 0x03 0x77 0xFB ---- ---- ---- ---- ---- ---- ---- ---- ----  kode> 

Deretter,

  CRC
LSB MSB ---- ---- ---- ---- ---- ---- ---- M0 0x00 0x09 0x69 0x31 0x00 0x03 0xBA 0xDEB1 0x00 0x00 0x00 0x00 0x01 0x00 - ----------- XOR ------------ M1 0x00 0x09 0x69 0x31 0x01 0x03 0x01 0xC2 C1 = 0xDEBA xor 0xC201 = 0x1CBB  

og et annet bitmønster B2 får CRC til å endres med C2,

  CRC LSB MSB ---- ---- ---- ---- ---- --- --- - ---- ---- M0 0x00 0x09 0x69 0x31 0x00 0x03 0xBA 0xDEB2 0x00 0x00 0x00 0x00 0x02 0x00 ------------ XOR ------------ M2 0x00 0x09 0x69 0x31 0x02 0x03 0xCC 0xE7C2 = 0xDEBA xor 0xE7CC = 0x3976C1 xor C2 = 0x1CBB xor 0x3976 = 0x25CD  

deretter xoring pakken med B3 = (B1 x C3 = (C1 xor C2). Hvis det ikke skjer, kan ikke algoritmen være en vanlig CRC-algoritme.

  CRC LSB MSB ---- ---- --- - ---- ---- ---- ---- ---- B1 0x00 0x00 0x00 0x00 0x 01 0x00B2 0x00 0x00 0x00 0x00 0x02 0x00 ------------ XOR ------------ B3 0x00 0x00 0x00 0x00 0x03 0x00M0 0x00 0x09 0x69 0x31 0x00 0x03 0xBA 0xDEB3 0x00 0x00 0x00 0x00 0x03 0x00 ------------ XOR ------------ M3 0x00 0x09 0x69 0x31 0x03 0x03 0x77 0xFBC3 = 0xDEBA xor 0xFB77 = 0x25CD Gjør C3 = 0x25CD == C1 XOR C2 = 0x25CD? Ja  

Når det gjelder denne serielle strømmen, skjer det så det må være en vanlig CRC-algoritme.

Greg skrev: "Vurder nå to CRC-verdier hentet fra to 1-bit-meldinger, der de 1 bitene er i tilstøtende posisjoner. De resulterende CRC-ene vil variere med bare en skift-xor-syklus. For å være presis, hvis C1 tilsvarer meldingen med en 1 i posisjon i, og C2 tilsvarer melding med en 1 i posisjon i + 1, da er C1 avledet fra å bruke en shift-xor-syklus på C2. (Hvis dette virker bakover, er det fordi jo lenger 1-biten er fra slutten av meldingen, jo mer shift-xor sykluser blir brukt på CRC.)

Det er to muligheter. Hvis den fremre biten av C2 (den som skal skiftes ut) er 0, vil C1 være lik C2 forskjøvet med ett sted. Hvis det er 1, vil C2 være lik C1 forskjøvet ett sted og xored med polynomet. "

Jeg konstruerte flere forskjellmeldinger som bare skilte seg fra en bit ved hjelp av dataene fra mitt første innlegg her.

  CRC LSB MSB ---- ---- ---- ---- ---- ---- ---- ---- M0 0x00 0x09 0x69 0x31 0x00 0x03 0xBA 0xDEM1 0x00 0x09 0x69 0x31 0x01 0x03 0x01 0xC2 ---- ---- ---- ---- ---- ---- ---- ---- D01 0 0 0 0 0x01 0 0xBB 0x1C ---- ---- ---- ---- ---- ---- ---- ---- M0 0x00 0x09 0x69 0x31 0x00 0x03 0xBA 0xDEM2 0x00 0x09 0x69 0x31 0x02 0x03 0xCC 0xE7 ---- ---- ---- ---- ---- ---- ---- ---- D02 0 0 0 0 0x02 0 0x76 0x39 ---- ---- ---- ---- ---- ---- ---- ---- M0 0x00 0x09 0x69 0x31 0x00 0x03 0xBA 0xDEM3 0x00 0x09 0x69 0x31 0x04 0x03 0x56 0xAC ---- ---- - --- ---- ---- ---- ---- ---- D04 0 0 0 0 0x04 0 0xEC 0x72 ---- ---- ---- ---- - - ---- ---- --- -M0 0x00 0x09 0x69 0x31 0x00 0x03 0xBA 0xDEm8 0x00 0x09 0x69 0x31 0x08 0x03 0x62 0x3B ---- ---- ---- ---- ---- ---- ---- ---- ---- D08 0 0 0 0 0x08 0 0xD8 0xE5 ---- ---- ---- ---- ---- ---- ---- ---- M0 0x00 0x09 0x69 0x31 0x00 0x03 0xBA 0xDEM10 0x00 0x09 0x69 0x31 0x10 0x03 0x1B 0x1D ---- ---- ---- ---- ---- ---- ---- ---- D10 0 0 0 0 0x10 0 0xA1 0xC3 - --- ---- ---- ---- ---- ---- ---- ---- M0 0x00 0x09 0x69 0x31 0x00 0x03 0xBA 0xDEM20 0x00 0x09 0x69 0x31 0x20 0x03 0xE9 0x51 - - ---- ---- ---- ---- ---- ---- ---- D20 0 0 0 0 0x20 0 0x53 0x8f ---- ---- --- - ---- ---- ---- ---- ---- M0 0x00 0x09 0x69 0x31 0x00 0x03 0xBA 0xDEM40 0x00 0x09 0x69 0x31 0x40 0x03 0x0D 0xC8 ---- ---- ---- ---- ---- ---- ---- ---- ---- D40 0 0 0 0 0x40 0 0xB7 0x16
---- ---- ---- ---- ---- ---- ---- ---- M0 0x00 0x09 0x69 0x31 0x00 0x03 0xBA 0xDEM80 0x00 0x09 0x69 0x31 0x80 0x03 0xD4 0xF3 - --- ---- ---- ---- ---- ---- ---- ---- D80 0 0 0 0 0x80 0 0x6e 0x2d  

Jeg kom opp med disse CRC-verdiene for differansemeldingene med vist byte:

  Byte CRC (med bytebytte til MSB-LSB-rekkefølge) ----- ---- 01 1CBB 02 3976 LSB av CRC = 004 72EC LSB av CRC = 008 E5D8 LSB av CRC = 010 C3A1 LSB av CRC = 120 8F53 LSB av CRC = 140 16b7 LSB av CRC = 180 2d6e Lsb av CRC = 0  

Greg forklarte at når LSB er en 0, er den foregående CRC en bit riktig forskyvning av denne CRC. Hvis LSB er en 1, er den forrige CRC den gjeldende CRC xor'ed med polynomet og deretter skiftet til høyre.

  Byte CRC shift xor Previous CRC ----- ---- ---- ---- ---- 01 1CBB 02 3976 1CBB 0000 1CBB04 72EC 3976 0000 397608 E5D8 72EC 0000 72EC10 C3A1 61D0 8408 E5D820 8F53 47A9 8408 C3A140 16b7 0B5B 8408 8F5380 2d6e 16B7 0000 16b7  
 Dette fortalte meg at polynomet var 0x8408. 
 
 Neste setning omskriver det Greg skrev: "Skiftende retning indikerer at ReflectOut-parameteren skal være sann, siden skifting til høyre tilsvarer bruk av den kanoniske venstreskiftende versjonen av algoritmen med polynomet 0x1021 og deretter reflekterer den resulterende CRC. Det er bemerkelsesverdig at 0x1021 er en av standard 16-biters polynomene - den som kalte "CRC-16-CCITT" og også kjent som "KERMIT". "
 
 Så Greg har hjulpet meg å komme ganske langt sammen med anaen min lysis. Det ser sikkert ut som om det er en CRC og den mest sannsynlige CRC-16-CCITT eller Kermit (i det minste hvis init = XorOut = 0x0000). 
 Men selvfølgelig, da jeg prøvde å kjøre meldingene mine gjennom RevEng og ba den bruke KERMIT-algoritmen, stemte ikke de faktiske CRC-ene fra meldingene med det RevEng genererte. 
 
 For eksempel ved bruk av D01 melding: 
 
 d:> reveng -c -m kermit 000000000100 returnerer d819 
 
 Gregs analyse av problemet hans indikerte at det kan være noen byte inkludert i CRC-beregningen som ikke er synlige. I Gregs tilfelle skrev han: "Jeg kom på følgende ide. Begynn med å initialisere registeret med polynomet - dette tilsvarer tilstanden like etter å ha møtt 1 i en 1-bit forskjellsmelding. Kjør deretter algoritmen og tell antall trinn som kreves før den kjente CRC-verdien er nådd. Forutsatt at den til slutt ble nådd, ville det fortalt meg hvor mange 0 bits som fulgte 1 var inkludert i CRC. "
 
 Så jeg sa kanskje dette ville fungere for meg. Så jeg la til 00 byte på slutten av meldingen D01: 
 
 d:> reveng -c -m kermit 00000000010000 returnerer dc5a 
 
 d:> reveng -c -m kermit 0000000001000000 returnerer bb1c 
 
 WOW, 0xbb1c er CRC-verdien som jeg får når jeg xeller de to faktiske CRC-ene fra M0 og M1. (Jeg kan legge til 0x00 byte i differansemeldingen hvis de faktiske bytene i de faktiske meldingene er de samme og er 0x00 etter at de er xorert i differansemeldingen. Og jeg må huske at denne analysen fortsatt krever at init og XorOut er null, og det er kanskje ikke tilfelle i den faktiske algoritmen. 
 
 Så jeg brukte omtrent et år (nei, ikke heltid) på å finne verdien av ekstra byte. Jeg skrev et program som prøvde alle kombinasjoner av ekstra byte men jeg verdiene deres hoppet over alt. Jeg kommer til å utelate alt jeg gjorde for å finne de ekstra byte. Det var en blindvei. 
 
 ** Dette var jeg var da jeg la min problembeskrivelse på denne nettsiden. ** 
 
 Kanskje jeg fremdeles ikke hadde de riktige databytes i riktig posisjon eller kanskje antagelsen om at init = XorOut = 0x0000 ikke var sant. 
 Så jeg bestemte meg for å prøve flere meldinger. Jeg laget en haug med meldinger der jeg kunne kontrollere verdien av 2. byte. Her er meldingene jeg klarte å generere: 
 
  CRC LSB MSB ---- ---- ---- ---- ---- ---- ---- - - ---- ---- ---- ---- 0x00 0x02 0x77 0x32 0x97 0x13 0x22 0x8D 0x00 0x04 0x77 0x32 0x97 0x13 0x14 0xE8 0x00 0x08 0x77 0x32 0x97 0x13 0x78 0x22 0x00 0x10 0x77 0x32 0x 0x 0x 0x 0x 0x 0x 0x 0x 0x 0x00 0x20 0x77 0x32 0x97 0x13 0x32 0x8F 0x00 0x40 0x77 0x32 0x97 0x13 0x34 0xEC 0x00 0x06 0x77 0x32 0x97 0x13 0x06 0xCB 0x00 0x0A 0x77 0x32 0x97 0x13 0x6A 0x01 0x00 0x12 0x77 0x32 0x97 0x13 0xA3 0x9D 0x00 0x22 0x77 0x32 0x97 0x13 0x20 0xAC 0x00 0x42 0x77 0x32 0x97 0x13 0x26 0xCF  
 
 Og her er forskjellsmeldingene: 
 
  CRC LSB MSB ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- M02a 0x00 0x02 0x77 0x32 0x97 0x13 0x22 0x8DM03a 0x00 0x03 0x77 0x32 0x97 0x13 0xAB 0x9C ---- ---- ---- ---- ---- ---- ---- ---- ---- - --- ---- D01a 0x00 0x01 0x00 0x00 0x00 0x00 0x89 0x11 LSB MSB ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- 0x00 0x04 0x77 0x32 0x97 0x13 0x14 0xE8 0x00 0x06 0x77 0x32 0x97 0x13 0x06 0xCB ---- ---- ---- ---- ---- - - ---- ---- ---- ---- ---- 0x00 0x02 0x00 0x00 0x00 0x00 0x12 0x23 LSB MSB ---- ---- ---- ---- - - ---- ---- ---- ---- ---- ---- 0x00 0x02 0x77 0x32 0x97 0x13 0x22 0x8D
0x00 0x06 0x77 0x32 0x97 0x13 0x06 0xCB ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- - - 0x00 0x04 0x00 0x00 0x00 0x00 0x24 0x46 LSB MSB ---- ---- ---- ---- ---- ---- ---- ---- ---- - - ---- 0x00 0x02 0x77 0x32 0x97 0x13 0x22 0x8D 0x00 0x0A 0x77 0x32 0x97 0x13 0x6A 0x01 ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- 0x00 0x08 0x00 0x00 0x00 0x00 0x48 0x8C LSB MSB ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- 0x00 0x02 0x77 0x32 0x97 0x13 0x22 0x8D 0x00 0x12 0x77 0x32 0x97 0x13 0xA3 0x9D ---- ---- ---- - - ---- ---- ---- ---- ---- ---- ---- 0x00 0x10 0x00 0x00 0x00 0x00 0x81 0x10 LSB MSB ---- ---- - - ---- ---- ---- ---- ---- ---- ---- ---- 0x00 0x02 0x77 0x32 0x97 0x13 0x22 0x8D 0x00 0x22 0x77 0x32 0x97 0x13 0x20 0xAC ---- ---- ---- ---- ---- ---- ---- ---- ---- - - ---- 0x00 0x20 0x00 0x00 0x00 0x00 0x02 0x21 LSB MSB ---- ---- ---- ---- ---- ---- ---- ---- - - ---- ---- 0x00 0x02 0x77 0x32 0x97 0x13 0x22 0x8D 0x00 0x42 0x77 0x32 0x97 0x13 0x26 0xCF ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- 0x00 0x40 0x00 0x00 0x00 0x00 0x04 0x42  
 
 Så gjorde jeg den samme analysen på CRC-ordene og kom opp med samme polynominal som før: 0x8408 eller når forskjøvet den andre retningen, 0x1021 
 
  Byte CRC (med bytebytte til MSB-LSB-rekkefølge) ----- ---- 0x01 11890x02 2312 LSB av CRC = 00x04 4624 LSB av CRC = 00x08 8C48 LSB av CRC = 00x10 1081 LSB av CRC = 10x20 2102 LSB av CRC = 00x40 4204 LSB av CRC = 0Byte CRC skift xeller tidligere CRC
----- ---- ---- ---- ---- 0x01 11890x02 2312 1189 0000 11890x04 4624 2312 0000 23120x08 8C48 4624 0000 46240x10 1081 0840 8408 8C48 0x20 2102 1081 0000 10810x40 4204 2102 0000 2102  kode> 
 
 Her er alle RockSoft CRC-modellene med denne polyen, jeg må tenke forbi Kermit: 
 
  width = 16 poly = 0x1021 init = 0x0000 refin = false refout = false xorout = 0x0000 check = 0x31c3 name = "XMODEM" width = 16 poly = 0x1021 init = 0x0000 refin = true refout = true xorout = 0x0000 check = 0x2189 name = "KERMIT" width = 16 poly = 0x1021 init = 0x1d0f refin = false refout = false xorout = 0x0000 check = 0xe5cc name = "CRC-16 / AUG-CCITT" width = 16 poly = 0x1021 init = 0x89ec refin = true refout = true xorout = 0x0000 check = 0x26b1 name = "CRC-16 / TMS37157 "width = 16 poly = 0x1021 init = 0xb2aa refin = true refout = true xorout = 0x0000 check = 0x63d0 name =" CRC-16 / RIELLO "width = 16 poly = 0x1021 init = 0xc6c6 refin = true refout = true xorout = 0x00 00 check = 0xbf05 name = "CRC-A" width = 16 poly = 0x1021 init = 0xffff refin = false refout = false xorout = 0x0000 check = 0x29b1 name = "CRC-16 / CCITT-FALSE" width = 16 poly = 0x1021 init = 0xffff refin = false refout = false xorout = 0xffff check = 0xd64e name = "CRC-16 / GENIBUS" width = 16 poly = 0x1021 init = 0xffff refin = true refout = true xorout = 0x0000 check = 0x6f91 name = "CRC-16 / MCRF4XX "width = 16 poly = 0x1021 init = 0xffff refin = true refout = true xorout = 0xffff check = 0x906e name =" X-25 " 
 
 Jeg la merke til noe med dette nyeste settet med meldinger. De to ekstra bytene var ikke nødvendig for å få riktig CRC for differansemeldingene hvis jeg bare brukte den første byten og slapp de andre 0x00 byte. Bruker RevEng på melding D01a: 
 
 D:> reveng -s -w 16 018911width = 16 poly = 0x1021 init = 0x0000 refin = true refout = true xorout = 0x0000 check = 0x2189 name = "KERMIT" 
 
 Da skjønte jeg at hvis jeg mater meldingen inn i CRC-generatoren i omvendt byte-rekkefølge, min opprinnelige D01-melding
genererte riktig CRC. 
 
 D:> reveng -c -m kermit 01000000bb1c 
 
 Så disse bytene som jeg trodde var ekstra byte var egentlig bare byte av meldingen, men meldingen var å behandles i omvendt byte-rekkefølge. 
 
 Kan dette være sant? 
 
 Jeg tok M02a og M03a, og matet dem inn i RevEng i omvendt byte-rekkefølge: 
 
 D :> reveng -s -w 16 1397327702228dwidth = 16 poly = 0x1021 init = 0xffff refin = true refout = true xorout = 0x0000 check = 0x6f91 name = "CRC-16 / MCRF4XX" 
 
 D:> reveng - s -w 16 1397327703ab9cwidth = 16 poly = 0x1021 init = 0xffff refin = true refout = true xorout = 0x0000 check = 0x6f91 name = "CRC-16 / MCRF4XX" 
 
 Og det som falt ut overrasket meg, init var alle og algoritmen hadde den samme polyen som jeg tidligere fant. Algoritmen var fra MCRF4xx-kommunikasjon (som nå ser jeg fornuftig fordi RS-232-linjen som jeg sporer erstattet en RF-forbindelse). 
 
 MCRF4xx er en RFID-protokoll. 
 
 Meldingen blir tatt som et langt sett med bits slik at den siste byten behandles først og den første byten behandles sist. 0x00 byte i begynnelsen av meldingen brukes ikke. Med init = 0xffff vil MCRF4xx-algoritmen oppdage ekstra eller manglende ledende nuller. 
 
 Jeg prøvde denne algoritmen på et par dusin av meldingene, og den får riktig CRC hver gang. 
 
 Her er en kodebit som jeg fant på  http://www.snip2code.com/Snippet/86260/Simple-CRC-16-MCRF4XX-C-implementation- 
 
  #include #include uint16_t crc16_mcrf4xx (uint16_t crc, uint8_t * data, size_t len) {if (! data || len> 1) ^ 0x8408; annet crc = (crc >> 1); }} returner crc; }  
 
 En webside på RevEng-nettstedet, peker på noen dokumenter om MCRF4xx:  http://reveng.sourceforge.net/crc-catalogue/16.htm. 
 
 Takk til alle som sendte positiv energi min vei. 

Jeg skrev mitt eget CRC brute-forcing-program i 2004, men det er ganske spesialisert for et bestemt problem. Det er en mye bedre generell bruk tilgjengelig som åpen kildekode på https://github.com/sitsec/bruteforce-crc

Du bør kunne samle noen forskjellige eksempler overførte pakker og mate dem gjennom dette programmet. For en 16-biters CRC er det ganske raskt. Jeg har ikke prøvd det på lengre CRC-er.