Reverse engineeren van checksum

Misschien een voor de hand liggende vraag...

Maar over welke apparatuur gaat dit precies? Of waarvoor wordt dit toegepast?

Sorry, dat was ik inderdaad vergeten te melden.

Het gaat om een infrarood protocol dat wordt gebruikt voor het bedienen van schakelaars.
Dit is vermoedelijk een zelfbouwproject geweest, maar ik ken de maker niet en kan helaas ook niet de firmware achterhalen...

Nu probeer ik een uitbreiding te maken op het systeem, maar om commando's te kunnen sturen moet ik natuurlijk de goede checksum meesturen

Hoe weet je dan dat de laatste 2 bytes de checksum zijn?

Ik weet niet zeker of de bytes een checksum zijn.

Maar ik kan door verschillende commando's te sturen precies achterhalen wat de eerste 7 bytes voorstellen.
Wanneer ik echter een bit in één van de eerste zeven bytes aanpas veranderden de laatste twee bytes ook.

Het kan ook CRC zijn? Dat achterhaal je niet zo makkelijk door naar de bitjes te kijken. Er zijn echter zat online CRC generators te vinden. Douw daar de data eens in en kijk of je wat zinnigs terug krijgt.

Tenslotte weet ik niet hoeveel commando's je moet sturen. Maar als je die op een andere manier kunt genereren en alleen maar na hoef te doen, ben je er natuurlijk ook...

Is het geen CRC-16?

[EDIT]
EricP was 12 seconden eerder...

[Bericht gewijzigd door Franzki op donderdag 23 oktober 2014 17:30:44 (55%)]

De laatste 4 bits lijken een counter te vormen, maar waarvan?

Een pakketteller dus.
Als je met een andere afstandbediening een pakket tussenvoegt dan wordt de data waarschijnlijk niet geaccepteerd omdat de tellerstand niet klopt.

CRC16 zal het dus niet zijn want daar zit geen teller in.

Dank jullie wel zover!
Ik ben intussen allerlei CRC-16's aan het proberen, wie weet.

Met teller bedoelde ik dat de waarde precies met één ophoogt wanneer ik in de data een waarde met één verhoog.
Het is dus geen pakettenteller, maar een teller die de totale waarde van het pakket weergeeft o.i.d.

CRC zal het niet zijn, aangezien er nog iets van een teller in te vinden is. (bij CRC zou je dat niet zien)
Wel vreemd dat er een 2 byte checksum is gebruikt om (maar) 7 databytes te beveiligen...

Met teller bedoelde ik dat de waarde precies met één ophoogt wanneer ik in de data een waarde met één verhoog.
Het is dus geen pakettenteller, maar een teller die de totale waarde van het pakket weergeeft o.i.d.

Dat doet dan toch weer meer aan checksum-achtige zaken denken...

parity van de 1e byte!

KLOPT EXACT, tel maar na!!!

[Bericht gewijzigd door High met Henk op donderdag 23 oktober 2014 20:02:16 (42%)]

Dat kan ik even niet volgen, hoe bedoel je dat precies? (wat/waar is parity van eerste byte?)

nou hij zendt 9 bytes elk pakket.
hij heeft 15 van die pakketten gedropt

de eerste byte is een 8 bits teller.

zie hieronder het lijstje
het eerste getal is het pakket nummer
het tweede getal is het aantal bits in het 1e byte
het derde getal is dat 2e bit in die checksum

1  2  1
2  3  0
3  3  0
4  4  1
5  3  0
6  4  1
7  4  1
8  5  0  
9  2  1
10 3  0
11 3  0
12 4  1
13 3  0
14 4  1
15 4  1

EDIT: bij 8e bericht waren er 5, geen 4 zoals er eerder stond

alleen nu die 9e byte nog, om die counters zou ik me niet zo druk maken eigenlijk. gewoon optellen..

hoewel het misschien handig is de test te herhalen met 15x dit pakket en 15x een ander pakket, dat geeft wellicht inzicht in de andere bytes.

[Bericht gewijzigd door High met Henk op donderdag 23 oktober 2014 20:46:59 (20%)]

Op 23 oktober 2014 18:02:29 schreef Arco:
CRC zal het niet zijn, aangezien er nog iets van een teller in te vinden is. (bij CRC zou je dat niet zien)

Een CRC is wiskundig niets anders dan de rest van het deelsommetje data/speciaal getal. Dus als je de data met stapjes van 1 ophoogt, is het niet vreemd als er in de rest ook iets met stapjes van een ophoogt.

Op 23 oktober 2014 16:45:47 schreef Douwe W:
(de LSB komt telkens als eerste)

Ik denk toch dat je de zaak van de andere kant moet bekijken. Ik heb het gros van de data even in hex getikt met de aanname dat het MSb links staat, en zowel de CRC-16 als de CRC-16 voor Modbus komen akelig dicht in de buurt. Het enige verschil tussen beide CRC's is de polynomal.

Data                                CRC16        Modbus

11 80 80 00 9A 28 C0 - 60 3D        60 21        60 3A
91 80 80 00 9A 28 C0 - A8 BD        A8 A0        A8 BB
51 80 80 00 9A 28 C0 - A4 7D        A4 60        A4 7B
D1 80 80 00 9A 28 C0 - 6C FD        6C E1        6C FA
31 80 80 00 9A 28 C0 - A2 7D        A2 00        A2 1B
B1 80 80 00 9A 28 C0 - 6A FD        6A 81        6A 9A
71 80 80 00 9A 28 C0 - 66 65        66 41        66 5A
F1 80 80 00 9A 28 C0 - AE E5
09 80 80 00 9A 28 C0 -
89 80 80 00 9A 28 C0 -
49 80 80 00 9A 28 C0 -
C9 80 80 00 9A 28 C0 -
29 80 80 00 9A 28 C0 -
A9 80 80 00 9A 28 C0 -
69 80 80 00 9A 28 C0 -

Je kan daar natuurlijk makkelijk een scripje schrijven wat alle 65536 polynomals probeert en kijkt bij welke de CRC matched.

Wow KIF, dat ziet er veelbelovend uit!

Ik ben meteen begonnen met het scriptje, maar om te check of ik het goed heb geschreven wilde ik even de CRC checken met jouw resultaten. Echter kom ik op een ander resultaat voor de CRC16. Heb jij daar ook het polynoom 0x8005 gebruikt? (ik gebrijp van google dat dit het polynoom is van de standaard CRC16)

Edit:
De polynoom was andersom, dus A001.
Verder blijken CRC16 en Modbus de zelfde polynoom te gebruiken maar een andere startwaarde.

[Bericht gewijzigd door Douwe W op donderdag 23 oktober 2014 23:47:17 (17%)]

Vandaag even een scriptje gemaakt dat alle polynomen uitprobeert. Helaas geen resultaat daaruit.

Daarna heb ik het lijstje van KIF nog wat aangevuld en alles blijkt inderdaad behoorlijk in de buurt te komen van de CRC16. De onderste 6 blijken zelfs exact overeen te komen.

Data packet			CRC-16	Modbus

11 80 80 00 9A 28 C0 - 60 3D	60 21	60 3A
91 80 80 00 9A 28 C0 - A8 BD	A8 A0	A8 BB
51 80 80 00 9A 28 C0 - A4 7D	A4 60	A4 7B
D1 80 80 00 9A 28 C0 - 6C FD	6C E1	6C FA
31 80 80 00 9A 28 C0 - A2 7D	A2 00	A2 1B
B1 80 80 00 9A 28 C0 - 6A FD	6A 81	6A 9A
71 80 80 00 9A 28 C0 - 66 65	66 41	66 5A
F1 80 80 00 9A 28 C0 - AE E5	AE C0	AE DB
09 80 80 00 9A 28 C0 - 61 BD	61 B9	61 A2
89 80 80 00 9A 28 C0 - A9 3D	A9 38	A9 23
49 80 80 00 9A 28 C0 - A7 FD	A5 F8	A5 E3
C9 80 80 00 9A 28 C0 - 6D 7D	6D 79 	6D 62
29 80 80 00 9A 28 C0 - A3 9D	A3 98	A3 83
A9 80 80 00 9A 28 C0 - 6B 1D	6B 19	6B 02
69 80 80 00 9A 28 C0 - 67 DD	67 D9	67 C2

B1 80 88 00 37 28 80 - BA FD	BA F0	BA EB
E1 80 80 00 9A 28 F8 - BD DD	BD D0	BD CB
11 80 80 00 9A 28 FE - B0 BD	B0 A0	B0 BB
80 80 D7 28 D7 28 80 - 22 4C	22 4C	22 57
80 80 37 28 37 28 80 - 02 CC	02 CC	02 D7
80 80 39 28 39 28 80 - 00 C4	00 C4	00 DF
80 80 B9 28 B9 28 80 - 36 C4 	36 C4	36 DF
80 80 D7 28 D7 28 46 - 70 CC	70 CC	70 D7
80 80 37 28 37 28 46 - 50 4C	50 4C	50 57

Ik denk dat ik nu eerst moet kijken of ik geen timing fouten heb in de ontvangende kant waardoor de laatste paar bits soms afwijken...

Op 23 oktober 2014 21:11:55 schreef klein is fijn:
Je kan daar natuurlijk makkelijk een scripje schrijven wat alle 65536 polynomals probeert en kijkt bij welke de CRC matched.

Dat kan, maar polynomials zijn niet zomaar willekeurig te kiezen. Ze moeten een deler van 10000...001 zijn of zoiets. Of juist priem. Te lang geleden, en ik heb het toch nooit goed gesnapt.

Maar goed, dus voor het zoeken naar "hebben ze soms polynomial 0x.... gebruikt"? Kan je ze wel allemaal proberen, maar om zelf een CRC te gaan gebruiken, moet je er 1 uit de boekjes plukken. Er zijn er vaak een paar die werken (dus ongeveer 1-5 van alle mogelijke!), maar de meeste dus niet.

Overweeg ook eens of misschien de laatste paar bitjes niet door de CRC gaan. Je afwijking lijkt in de laatste 4-8 bits van de CRC te zitten, en dat zou kunen komen door een paar bitjes minder door de CRC te gooien.... (dat kan bijvoorbeeld een off-by-one fout in de originele code kunnen zijn... Dus dat ie maar 55 van de 66 bitjes CRC-t!....)

Op 24 oktober 2014 11:25:49 schreef rew:
(...) dat zou kunen komen door een paar bitjes minder door de CRC te gooien.... (dat kan bijvoorbeeld een off-by-one fout in de originele code kunnen zijn... Dus dat ie maar 55 van de 66 bitjes CRC-t!....)

Wanneer ik een klein beetje verander of weglaat in de data, dan verandert de CRC compleet (wat volgens mij ook het idee is van een CRC) dus hoe bedoel je dit precies?

De manier om je CRC16 te vinden is te zoeken naar de CRC die 0xFFFF of 0x0000 geeft !. Dan zijn je twee laatste bytes voorafgaande aan je CRC namelijk je CRC polynoom !.

Dus genereer heel veel pakketen en controleer alle CRC bytes en bewaar alleen 0x0000 en 0xFFFF !.

Op 26 oktober 2014 21:04:31 schreef Douwe W:
Wanneer ik een klein beetje verander of weglaat in de data, dan verandert de CRC compleet (wat volgens mij ook het idee is van een CRC) dus hoe bedoel je dit precies?

D'r is een truuk om een CRC per 8 bits tegelijk uit te rekenen. Natuurlijk gebruikt iedereen die. Maar in origine gaat er 1 bit tegelijk in.

http://www.altera.com/literature/an/an049_01.pdf

Maar het is inderdaad raar dat de boel niet verschoven is maar wel een paar bitjes fout heeft. En de CRC16 uit het altera document hebben allemaal hoge termen (11-15), zodat de invloed niet alleen tot de laagste bitjes beperkt kan blijven.

Op 26 oktober 2014 21:25:47 schreef IoT:
De manier om je CRC16 te vinden is te zoeken naar de CRC die 0xFFFF of 0x0000 geeft !. Dan zijn je twee laatste bytes voorafgaande aan je CRC namelijk je CRC polynoom !.

Dus genereer heel veel pakketen en controleer alle CRC bytes en bewaar alleen 0x0000 en 0xFFFF !.

die kans is 1 op 32000.....
moet je het dus al snel geautomatiseerd doen.

Natuurlijk moet je dit met de computer oid doen en je moet waarschijnlijk wel meer dan 65000 packets controleren. Afhankelijk van het soort CRC dat ze gebruiken en of de init waarde 0xFFFF was of 0x0000 en of ze de CRC inverteren voordat ze deze verzenden is de oplossing een CRC van 0x0000 of 0xFFFF je moet dus allebij deze waardes bewaren.

CRC is de rest van een deling in GF(2) dus delen kun je met een XOR doen bitwise, byte wise maar ook word wise. Zolang je payload dezelfde lengte heeft als je CRC is er 100% fout detectie (kun je de CRC ook gebruiken als fout correctie) als je payload heel lang is tov je CRC neemt de kans snel af. De perfecte polynoom bestaan niet en is afhankelijk van het soort fouten dat je verwacht, daarom zijn er ook zoveel soorten CRC-16.

[Bericht gewijzigd door Henry S. op zondag 22 maart 2015 15:37:19 (11%)]

Douwe W, heb je dan uiteindelijk de oplossing gevonden? Misschien wil je je scriptje wel delen of zo? Ik heb interesse omdat ik zelf ook tegen een dergelijk probleem aanliep, maar tot op heden de tijd nog niet gevonden heb om er eens op te zoeken.