Knobelei: CRC Polynom / Checksummen-Algorithmus gesucht

[Lutz B. (Gast)]

Hi!

Ich habe hier ein kniffliges Problem: Ich habe eine (drahtgebundene) 
Übertragung, bei der ich die Nachrichten einwandfrei mitlesen kann. Die 
Nachrichten sind über eine Checksumme/CRC/irgendwas geschützt.

Leider bekomme ich das Polynom/XOR-Maske/Init-States für die CRC nicht 
heraus. Mittlerweile habe ich in MATLAB es per "Brute-Force" auf alle 
Polynome zwischen 0x100 und 0x1FF getestet, zusätzlich jeweils noch mit 
allen XOR-Masken am Ende und allen Init-States von 0x00 bis 0xFF. Kein 
Treffer.

Eine Checksumme im Sinne von XOR oder Summe/Differenz scheint es auch 
nicht zu sein, denn "gerade" Summen führen sowohl zu ungeraden wie auch 
geraden Checksummen.

Hat jemand noch eine Idee?

verschiedene Nachrichten:

0x00 0x01 0x00 0xC4
0x00 0x01 0x01 0xC3
0x00 0x01 0x02 0xCA
(unterscheiden sich nur minimal - die ersten beiden würden als Differenz 
passen - die dritte dann aber schon nicht mehr?)

0x77 0x02 0x01 0x80 0x23
0x76 0x02 0x01 0x80 0x35
0x75 0x02 0x01 0x80 0x0F
0x74 0x02 0x01 0x80 0x19
0x73 0x02 0x01 0x80 0x7B
0x72 0x02 0x01 0x80 0x6D
0x71 0x02 0x01 0x80 0x57
0x70 0x02 0x01 0x80 0x41
0x6F 0x02 0x01 0x80 0xF4
…
0x1D 0x02 0x01 0x80 0xEA
0x1C 0x02 0x01 0x80 0xFC
…
0x12 0x02 0x01 0x80 0x38
0x11 0x02 0x01 0x80 0x02
0x10 0x02 0x01 0x80 0x14
0x90 0x02 0x01 0x80 0x25
0x8F 0x02 0x01 0x80 0x90
0x8E 0x02 0x01 0x80 0xCA
(hier könnte ich alle Nachrichten die mit 0x90 bis 0x10 anfangen 
extrahieren. Es variiert nur in einem Byte - kann man hier evtl. auf die 
Tabelle zurückrechnen? Also "0x23 ist der Tabellenwert, der durch x^0x80 
indiziert wurde. x wurde durch y^0x01 indiziert, y durch z^0x02 und z 
durch 0x77^Init-Wert")

Vielen Dank!

Grüße
Lutz

[Thomas (kosmos)]

Lutz B. schrieb:
> Ich habe eine (drahtgebundene)
> Übertragung, bei der ich die Nachrichten einwandfrei mitlesen kann.

und um welches Gerät handelt es sich genau?

[Weingut P. (weinbauer)]

hatte neulich so ne Nummer ... da wurde für jedes Byte in der Message n 
anderes Polynom verwendet.
Habs schlussendlich Byte für Byte, Bit für Bit aufgedröselt. Da war 
zusätzlich zum wechselnden Polynom nochmal die Nibbles übereinander xor 
und vertauscht. Ätzend.

[Kan a. (Firma: Basta) (kanasta)]

Weshalb sind die Nachrichten mal 4, mal 5 Byte lang?

[Achim M. (minifloat)]

Kan asta schrieb:
> Weshalb sind die Nachrichten mal 4, mal 5 Byte lang?

Zur Verwirrung, soll ja schließlich ein Rätsel sein ;)
mfg mf

[Lutz B. (Gast)]

Nein, ganz banal: es handelt sich um verschiedene Nachrichten. Daher 
auch die räumliche Trennung per Textzeile.

In habe in der Zwischenzeit ALLE "zählenden" Nachrichten extrahiert und 
Dezimal konvertiert:

16  2  1  128  20
17  2  1  128  2
18  2  1  128  56
19  2  1  128  46
20  2  1  128  76
21  2  1  128  90
22  2  1  128  96
23  2  1  128  118
24  2  1  128  164
25  2  1  128  178
26  2  1  128  136
27  2  1  128  158
28  2  1  128  252
29  2  1  128  234
30  2  1  128  208
31  2  1  128  198
32  2  1  128  189
33  2  1  128  171
34  2  1  128  145
35  2  1  128  135
36  2  1  128  229
37  2  1  128  243
38  2  1  128  201
39  2  1  128  223
40  2  1  128  13
41  2  1  128  27
42  2  1  128  33
43  2  1  128  55
44  2  1  128  85
45  2  1  128  67
46  2  1  128  121
47  2  1  128  111
101  2  1  128  104
102  2  1  128  82
103  2  1  128  68
104  2  1  128  150
105  2  1  128  128
106  2  1  128  186
107  2  1  128  172
108  2  1  128  206
109  2  1  128  216
110  2  1  128  226
111  2  1  128  244
112  2  1  128  65
113  2  1  128  87
114  2  1  128  109
115  2  1  128  123
116  2  1  128  25
117  2  1  128  15
118  2  1  128  53
119  2  1  128  35
120  2  1  128  241
121  2  1  128  231
122  2  1  128  221
123  2  1  128  203
124  2  1  128  169
125  2  1  128  191
126  2  1  128  133
127  2  1  128  147
128  2  1  128  66
129  2  1  128  84
130  2  1  128  110
131  2  1  128  120
132  2  1  128  26
133  2  1  128  12
134  2  1  128  54
135  2  1  128  32
136  2  1  128  242
137  2  1  128  228
138  2  1  128  222
139  2  1  128  200
140  2  1  128  170
141  2  1  128  188
142  2  1  128  134
143  2  1  128  144
144  2  1  128  37

Eine kurze Prüfung ergab: Die CRC-Bytes sind eindeutig, also es teilt 
sich keine "Sequenznummer" das gleiche CRC-Ergebnis. Spricht ja 
eigentlich für eine ordnungsgemäß implmentierte CRC... Oder?

Die (256!) verschiedenen Permutationen der CRC-Tabelle auszuprobieren 
ist nicht möglich... Man müsste es "von hinten aufzäumen"...

[Kan a. (Firma: Basta) (kanasta)]

Lutz B. schrieb:
> es handelt sich um verschiedene Nachrichten.

Aber hoffentlich um die gleiche Checksummenfunktion.
Wie kommst du auf die Idee, dezimal der hexadezimalen Darstellung 
vorzuziehen???

[Karlo (Gast)]

Um welches Gerät handelt es sich?

[Tom M. (Gast)]

Lutz B. schrieb:
> 0x00 0x01 0x02 0xCA
> 0x8E 0x02 0x01 0x80 0xCA

Hast du noch mehr solcher Übereinstimmungen im letzten Byte bei 4 und 5 
Byte Nachrichten?

[Lutz B. (Gast)]

Hi!

So kann ich es per C&P direkt in MATLAB verwursten. Sonst muss ich immer 
die entsprechenden Konvertierfunktionen quälen, bei '0x...' sogar in 
Gänsefüsschen als String etc. so geht es per
"test = [ <paste> ];", evtl. noch mit nem reshape. Egal.

Gut, gleiche Checksummenfunktion kann ich nicht sicher sein. Hatte aber 
zuerst versucht, die Checksumme nur über die kurzen Nachrichten zu 
finden - zumindest da sollte sie hoffentlich gleich sein. Jetzt rechne 
ich noch mal (nur) auf den Nachrichten mit Sequenznummern.

[Lutz B. (Gast)]

Tom M. schrieb:
> Lutz B. schrieb:
>> 0x00 0x01 0x02 0xCA
>> 0x8E 0x02 0x01 0x80 0xCA
>
> Hast du noch mehr solcher Übereinstimmungen im letzten Byte bei 4 und 5
> Byte Nachrichten?

Hi!

Nein, leider eben nicht. Die "196/C4 und 195/C3" fehlen in den 
"Sequenznachrichten" leider... Habe nur noch "0x80 0x13 0x29 0x08 0x10 
0xC4", was aber die Antwort vom Gerät ist - die hatte ich bewusst 
weggelassen weil man da evtl. wirklich nicht weiß ob die Polynome etc. 
gleich sind...

[Harry (Gast)]

Hallöle,


also ich habe den Algorithmus gefunden, noch jemand?


Grüße.

[Mathias K. (Gast)]

Hier die "Auflösung". Um welches Gerät handelt es sich denn nun? ;-)


Ausgabe:

FOUND: C4 == C4
FOUND: C3 == C3
FOUND: CA == CA
FOUND: 23 == 23
FOUND: 35 == 35
FOUND: 0F == 0F
FOUND: 19 == 19
FOUND: 7B == 7B
FOUND: 6D == 6D
FOUND: 57 == 57
FOUND: 41 == 41
FOUND: F4 == F4
FOUND: EA == EA
FOUND: FC == FC
FOUND: 38 == 38
FOUND: 02 == 02
FOUND: 14 == 14
FOUND: 25 == 25
FOUND: 90 == 90
ERROR: 86 == CA

#!/usr/bin/python
#
# crc8_custom.py
#
# custom crc8 calculation
#
# (C) 2012 by Mathias K.
#
# This programm is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; version 2 of the License.
#
CRC8_POLY = 0x07
CRC8_INIT = 0xf3
#
# calculate crc table
#
def crc_rev_table():
  table=[]
  for i in range(0,256):
    table.append(0)
  for i in range(0,256):
    d = [i,0]
    table[i] = crc8_algo(i)
  x=0
  print "crc8_table = ["
  for i in range(0,256):
    print "0x%02X," % table[i],
    x += 1
    if x == 8:
      print ""
      x = 0
  print "]"
#
# crc table
#
crc8_table = [
0x00, 0x07, 0x0E, 0x09, 0x1C, 0x1B, 0x12, 0x15, 
0x38, 0x3F, 0x36, 0x31, 0x24, 0x23, 0x2A, 0x2D, 
0x70, 0x77, 0x7E, 0x79, 0x6C, 0x6B, 0x62, 0x65, 
0x48, 0x4F, 0x46, 0x41, 0x54, 0x53, 0x5A, 0x5D, 
0xE0, 0xE7, 0xEE, 0xE9, 0xFC, 0xFB, 0xF2, 0xF5, 
0xD8, 0xDF, 0xD6, 0xD1, 0xC4, 0xC3, 0xCA, 0xCD, 
0x90, 0x97, 0x9E, 0x99, 0x8C, 0x8B, 0x82, 0x85, 
0xA8, 0xAF, 0xA6, 0xA1, 0xB4, 0xB3, 0xBA, 0xBD, 
0xC7, 0xC0, 0xC9, 0xCE, 0xDB, 0xDC, 0xD5, 0xD2, 
0xFF, 0xF8, 0xF1, 0xF6, 0xE3, 0xE4, 0xED, 0xEA, 
0xB7, 0xB0, 0xB9, 0xBE, 0xAB, 0xAC, 0xA5, 0xA2, 
0x8F, 0x88, 0x81, 0x86, 0x93, 0x94, 0x9D, 0x9A, 
0x27, 0x20, 0x29, 0x2E, 0x3B, 0x3C, 0x35, 0x32, 
0x1F, 0x18, 0x11, 0x16, 0x03, 0x04, 0x0D, 0x0A, 
0x57, 0x50, 0x59, 0x5E, 0x4B, 0x4C, 0x45, 0x42, 
0x6F, 0x68, 0x61, 0x66, 0x73, 0x74, 0x7D, 0x7A, 
0x89, 0x8E, 0x87, 0x80, 0x95, 0x92, 0x9B, 0x9C, 
0xB1, 0xB6, 0xBF, 0xB8, 0xAD, 0xAA, 0xA3, 0xA4, 
0xF9, 0xFE, 0xF7, 0xF0, 0xE5, 0xE2, 0xEB, 0xEC, 
0xC1, 0xC6, 0xCF, 0xC8, 0xDD, 0xDA, 0xD3, 0xD4, 
0x69, 0x6E, 0x67, 0x60, 0x75, 0x72, 0x7B, 0x7C, 
0x51, 0x56, 0x5F, 0x58, 0x4D, 0x4A, 0x43, 0x44, 
0x19, 0x1E, 0x17, 0x10, 0x05, 0x02, 0x0B, 0x0C, 
0x21, 0x26, 0x2F, 0x28, 0x3D, 0x3A, 0x33, 0x34, 
0x4E, 0x49, 0x40, 0x47, 0x52, 0x55, 0x5C, 0x5B, 
0x76, 0x71, 0x78, 0x7F, 0x6A, 0x6D, 0x64, 0x63, 
0x3E, 0x39, 0x30, 0x37, 0x22, 0x25, 0x2C, 0x2B, 
0x06, 0x01, 0x08, 0x0F, 0x1A, 0x1D, 0x14, 0x13, 
0xAE, 0xA9, 0xA0, 0xA7, 0xB2, 0xB5, 0xBC, 0xBB, 
0x96, 0x91, 0x98, 0x9F, 0x8A, 0x8D, 0x84, 0x83, 
0xDE, 0xD9, 0xD0, 0xD7, 0xC2, 0xC5, 0xCC, 0xCB, 
0xE6, 0xE1, 0xE8, 0xEF, 0xFA, 0xFD, 0xF4, 0xF3, 
]
#
# update with table
#
def crc8_update_table(d,crc):
  return crc8_table[d^crc];
#
# crc8 algorithm
#
def crc8_algo(crc):
  for x in range(0,8):
    if crc & 0x80:
      crc = (crc << 1)&0xfe;
      crc ^= CRC8_POLY
    else:
      crc = (crc << 1)&0xfe;
  return crc
#
# update with algorithm
#
def crc8_update_algo(d,crc):
  crc ^= d
  return crc8_algo(crc)
#
# calculate crc from buffer
#
def crc8_calc(buf,l):
  crc = CRC8_INIT
  for i in range(0,l):
    crc = crc8_update_algo(buf[i],crc)
  return crc
#
# generate table
#
#crc_rev_table()
#
# test data
#
data = [
[0x00, 0x01, 0x00, 0xC4],
[0x00, 0x01, 0x01, 0xC3],
[0x00, 0x01, 0x02, 0xCA],
[0x77, 0x02, 0x01, 0x80, 0x23],
[0x76, 0x02, 0x01, 0x80, 0x35],
[0x75, 0x02, 0x01, 0x80, 0x0F],
[0x74, 0x02, 0x01, 0x80, 0x19],
[0x73, 0x02, 0x01, 0x80, 0x7B],
[0x72, 0x02, 0x01, 0x80, 0x6D],
[0x71, 0x02, 0x01, 0x80, 0x57],
[0x70, 0x02, 0x01, 0x80, 0x41],
[0x6F, 0x02, 0x01, 0x80, 0xF4],
[0x1D, 0x02, 0x01, 0x80, 0xEA],
[0x1C, 0x02, 0x01, 0x80, 0xFC],
[0x12, 0x02, 0x01, 0x80, 0x38],
[0x11, 0x02, 0x01, 0x80, 0x02],
[0x10, 0x02, 0x01, 0x80, 0x14],
[0x90, 0x02, 0x01, 0x80, 0x25],
[0x8F, 0x02, 0x01, 0x80, 0x90],
[0x8E, 0x02, 0x01, 0x80, 0xCA]
]

for i in range(0,len(data)):
  d = data[i]
  crc = crc8_calc(d,len(d)-1)
  if crc != d[len(d)-1]: print "ERROR:",
  else: print "FOUND:",
  print "%02X == %02X" % (crc,d[len(d)-1])

[Lutz B. (Gast)]

Super! Vielen Dank Mathias!

Ich hatte derweil mit den neu extrahierten Daten noch mal versucht die 
Sache zu knacken und hatte, da ich glücklicherweise nur die ersten 4 
Nachrichten testete, auch Glück:

Sequenznummern  Polynom  XOR / Init
16-23  0x07  0 / 0xff
24-39  0x07  0x80 / 0xff
40-47  0x07  0 / 0xff

usw.

Ist das bei dir implizit berücksichtigt? Bin nicht genug bewandert um zu 
erkenne, ob dies bei dir in "crc8_algo" drin steckt? Ist das 
standardmäßig so? Weil mit dem Init von 0xf3 bekomme ich bei mir keine 
korrekten Werte?

Grüße
Lutz

[Kan a. (Firma: Basta) (kanasta)]

Lutz will einfach nicht mit der Info raus, wo die Daten herkommen.

[Mathias K. (Gast)]

Kan asta schrieb:
> Lutz will einfach nicht mit der Info raus, wo die Daten herkommen.

Es handelt sich wohl um eine geheime AKW Anlage die jetzt mit AVR & Co. 
erweitert wird, so eine Art Blinkenlights für unsere Nachbarn im All.

[Mathias K. (Gast)]

Lutz B. schrieb:
> Ich hatte derweil mit den neu extrahierten Daten noch mal versucht die
> Sache zu knacken und hatte, da ich glücklicherweise nur die ersten 4
> Nachrichten testete, auch Glück:
> ...
> Ist das bei dir implizit berücksichtigt? Bin nicht genug bewandert um zu
> erkenne, ob dies bei dir in "crc8_algo" drin steckt? Ist das
> standardmäßig so? Weil mit dem Init von 0xf3 bekomme ich bei mir keine
> korrekten Werte?

K.A..

Welche Daten?
Welche Routine?
Welche Hardware?

Mit der Handvoll Daten die du gütiger weise hier eingestellt hast kann 
das eigentlich nur Chuck Norris 100%ig verifizieren.

[Lutz B. (Gast)]

Nein, völlig langweilig: Abbrandsteuerung für einen 
Spartherm-Brenneinsatz (Kamin). Da aber teilweise hier viele 
Bedenkenträger rumlaufen wollte ich das Thema Kohlenmonoxidvergiftung 
oder sonstwas hier erstmal raushalten, bis eine Lösung gefunden wird.

Mittlerweile habe ich es dank Mathias Code-Beispiel (nochmals vielen 
Dank!) auch ohne "if-Orgie" hinbekommen - interessant, dass sich das 
Ergebnis dann so "regelmäßig" ändert.

Ist das "Auslassen" der "Division" bei gesetzten MSB irgendwas häufiger 
verwendetes? Außer Verwirrung des Betrachters erkenne ich keinen 
Vorteil...

Mathias, kannst du beschreiben, wie du auf die Lösung gekommen bist?

Grüße
Lutz

[Kan a. (Firma: Basta) (kanasta)]

Lutz B. schrieb:
> Da aber teilweise hier viele  Bedenkenträger rumlaufen

Da hast du Recht. Der Thread wäre 3x so groß, und vor deiner
Türe würde schon die Feuerwehr stehen.

[Mathias K. (Gast)]

Lutz B. schrieb:
> Ist das "Auslassen" der "Division" bei gesetzten MSB irgendwas häufiger
> verwendetes? Außer Verwirrung des Betrachters erkenne ich keinen
> Vorteil...

Das ist die Mathematik hinter der CRC-Berechnung und soll keine 
Verwirrung stiften ;-). Die genaue mathematische Beschreibung hat sich 
bisher meines Interessendunstkreises entzogen.

> Mathias, kannst du beschreiben, wie du auf die Lösung gekommen bist?

Mit dem Standard CRC-8 Algorithmus ausprobiert. Als Startwert ist 
eigentlich 0xff üblich, was die Sache hier "etwas" verlängert hat. Bei 
der guten alten CRC-8 sind eigentlich alle Schweinereien bei der 
Implementierung in "The Wild" und es gibt z.B. auch 8-Bit Prüfsummen die 
aus den unteren 8-Bit einer 16-Bit CRC bestehen.

Stimmt die CRC jetzt für alle Pakete? Bei deinen Beispieldaten war die 
letzte CRC nicht richtig.

[eProfi (Gast)]

Beitrag "Anbindung SHT71 an STM32F4Discovery"

[eProfi (Gast)]

tschuldigung, falscher Thread.

[Holger (Gast)]

@Mathias K. (Gast):

Ist zwar schon 'ne Weile her, aber magst Du erzählen was Du gebaut hast?
Hab auch so'ne Steuerung die nun kaputt ist (bevor ich Hand angelegt 
habe).
War das eine S-Thermatik Pro?

Gruß

[Holger (Gast)]

Gut, nun ist die Steuerung wieder heile:

Nachdem mir Spartherm gestern telefonisch mitgeteilt hat, ich müsse die 
Steuerung über einen Fachhändler einschicken: Platinentausch 400-500 
EUR.
Ich glaube es hackt! Da ist neben Stromversorgung ein bisschen PIC, ein 
RS485-Wandler und ein billiges QVGA-Display mit Touch drauf. Selbst als 
komplettes Development-Kit vom ungarischen Hersteller kostet das keine 
100 EUR...

Also habe ich zunächst selbst mein Glück probiert und ein bißchen 
rumgemessen. Fazit: Der Li-Ion-Akku war kaputt und deswegen ist die 
Spannungsversorgung zusammengebrochen. Akku ausgelötet -> läuft wieder. 
Habe jetzt eine AA-Halterung eingebaut und bei *eichelt einen neuen Akku 
bestellt. Falls ich den noch öfter tauschen muss... :-(

Trotzdem würde mich interessieren was Mathias K. sich da gebaut hat. 
Eigentlich ist das Terminal ja nur eine Anzeige/Bedienung der 
abgesetzten Steuerung (verbunden über RS485). Da die Steuerung ja auch 
autark arbeitet, schwebt mir vor, die Messwerte und Register in meine 
Haussteuerung zu übernehmen und an der Stelle ein Android-Tablet meiner 
Haussteuerung zu montieren...

[Wegstaben V. (wegstabenverbuchsler)]

Holger schrieb:
> und bei *eichelt einen neuen Akku bestellt.

Möge der Blitz dich treffen, wenn du das Unwort REICHELT aussprichst!

[Holger (Gast)]

oh, natürlich interessiert mich was Lutz B. gebaut hat...
Asche auf mein Haupt

[kla (Gast)]

Hallo,

habe auch so eine Steuerung und das Protokoll würde mich auch 
interessieren.
Möchte diese Messwerte dann mit openHAB anzeigen lassen.

Was gibt es bereits an bekannten Infos dazu ?