Author Topic: Trying to work out a checksum in a 8 byte data stream.. (Read 22440 times)

beyondhelp · « **on:** November 10, 2015, 12:41:39 am »

This has been bugging me for a while. I have a piece of hardware that I want to control from a MCU that currently works over a simple serial connection from a piece of software (that wont work in win10!). In order for me to really do this I need to figure out how the checksum works so that I don't have to manually store tons of data when it could easily be calculated on the fly.

Data is sent as blocks of 8 bytes, the last two are checksum. If I alter those the hardware does not respond, if I alter the other 6 bytes the hardware does also not respond and in both cases an 8bit corrupt data counter is increased by 1.

So here is an example of valid data:
01 00 20 01 01 01 7b 38
01 00 20 02 02 02 1b 04
01 00 20 03 03 03 3b 10
01 00 20 04 04 04 db 7c
01 00 20 05 05 05 fb 68
01 00 20 06 06 06 9b 54
01 00 20 07 07 07 bb 40
01 00 20 08 08 08 6a be
01 00 20 09 09 09 4a aa
01 00 20 0a 0a 0a 2a 96
01 00 20 0b 0b 0b 0a 82
01 00 20 0c 0c 0c ea ee
01 00 20 0d 0d 0d ca fa
01 00 20 0e 0e 0e aa c6
01 00 20 0f 0f 0f 8a d2

Somehow the last two bytes are calculated from the first 6. I would have thought it cannot be *that* complicated as the hardware is based on a 16f871 PIC. I have tried some CRC ideas but basically, I'm looking for any ideas that may help me! I have also tried looking for patterns in binary (nothing obvious). Thing is this isn't my strong point hence I post here in the hope that someone with more experience may help me.

ataradov · « **Reply #1 on:** November 10, 2015, 12:52:05 am »

This does not appear to be a standard CRC variant.

What sort of control do you have over the data? Can you generate arbitrary payload and get CRC for it?

beyondhelp · « **Reply #2 on:** November 10, 2015, 12:55:29 am »

No, I think that's the problem. I can create valid data from the program and record it, or record responses from the hardware. But I have no way to generate a checksum for any given bit of data.

Here if it helps is another example, this time responses from the hardware rather than data sent from the software (post above)

00 01 70 01 22 01 14 d3
00 01 60 00 80 00 9f 85
00 01 b0 00 20 00 f3 16
00 01 b0 01 20 00 c3 21
00 01 b0 02 53 00 99 24
00 01 b0 03 65 00 9a bc
00 01 b0 04 71 00 bd f6
00 01 b0 05 75 00 49 0d
00 01 b0 06 65 00 6a 57
00 01 b0 07 6e 00 81 ad
00 01 b0 08 63 00 dd c5
00 01 b0 09 65 00 4b 58
00 01 b0 0a 72 00 ff 9b
00 01 b0 0b 20 00 12 c5
00 01 b0 0c 36 00 57 e9
00 01 b0 0d 34 00 05 b8
00 01 b0 0e 20 00 e2 2e
00 01 b0 0f 20 00 d2 19
00 01 30 00 58 00 3a 4f
00 01 00 00 00 00 e4 f5

ataradov · « **Reply #3 on:** November 10, 2015, 12:58:14 am »

I'm asking if you can ask the program to send any values. Can you generate this sum for 00 00 00 00 00 00 and 01 00 00 00 00 00?

beyondhelp · « **Reply #4 on:** November 10, 2015, 01:01:11 am »

No, sadly not. The best I can do is something like this:

00 01 30 00 01 00 3c eb
00 01 30 00 02 00 6f be
00 01 30 00 03 00 5e 8d
00 01 30 00 04 00 c9 14
00 01 30 00 05 00 f8 27
00 01 30 00 06 00 ab 72
00 01 30 00 07 00 9a 41

hamster_nz · « **Reply #5 on:** November 10, 2015, 01:07:20 am »

If you look at the difference that each bit makes (e.g. from 01 00 20 02 02 02 to 01 00 20 03 03 03)

It looks to always be
20 14

Likewise the difference between these two messages are

01 00 20 04 04 04 db 7c
01 00 20 06 06 06 9b 54
40 28

So a message of

00 00 00 02 02 02 has a checksum of 40 28.

So it does look to be some sort of shift and XOR checksum CRC thingy.

You could probably just analyse a few more messages to get the polynomial... really easy if you could get a message with just the last bit that differs.

ataradov · « **Reply #6 on:** November 10, 2015, 01:07:42 am »

One way to get the CRC for 00 00 00 00 00 00 is to send a bunch (65K) of requests like "00 00 00 00 00 00 AA BB", where AA and BB run from 0x00 to 0xff. Find the one your device likes. A simple script will do that in seconds.

This will also let you generate packets at will, which will help a lot.

beyondhelp · « **Reply #7 on:** November 10, 2015, 01:15:16 am »

That's a clever idea. I may write a quick arduino script to do that and see what happens... I just have to keep hitting it until the bad message counter does not increment.

This has however been so frustrating, on and off I have been trying to get this for a few years, only just occurred to me to ask here now.

hamster_nz, im going to try sending 00 00 00 02 02 02 40 28 now and see if it thinks its valid.

Will post results in a sec.

ataradov · « **Reply #8 on:** November 10, 2015, 01:19:56 am »

Quote from: beyondhelp on November 10, 2015, 01:15:16 am

That's a clever idea.

I did this many times for reverse engineering things.

If you can automate this process and can generate checksums for simple patterns with 1 bit set in different positions, I'm sure we'll find what this CS is.

beyondhelp · « **Reply #9 on:** November 10, 2015, 01:30:11 am »

Ok so:

[10/11/2015 01:25:00] Written data (COM6)
01 00 30 00 00 00 fc 37 - message status request
[10/11/2015 01:25:00] Read data (COM6)
00 01 30 01 0d 00 40 88 - message status response, 1 bad msg, 13 good.
[10/11/2015 01:26:08] Written data (COM6)
00 00 00 02 02 02 40 28 - hamster_nz data (no response as expected)
[10/11/2015 01:26:28] Written data (COM6)
01 00 30 00 00 00 fc 37 - message status request
[10/11/2015 01:26:28] Read data (COM6)
00 01 30 02 0e 00 43 84 - message status response, 2 bad msg, 14 good.

So on that basis, it didn't like that...

hamster_nz · « **Reply #10 on:** November 10, 2015, 01:39:33 am »

If you send "01 00 30 00 00 00 fc 37" ( message status request) a few times, you will get a reply back that will at some time have one bit different (the number of good messages).

Should be easy to analyse the checksum from there!

beyondhelp · « **Reply #11 on:** November 10, 2015, 01:49:22 am »

Right doing that now...

beyondhelp · « **Reply #12 on:** November 10, 2015, 01:54:49 am »

Here we go:

[10/11/2015 01:52:33] Written data (COM6)
01 00 30 00 00 00 fc 37 ..0...ü7
[10/11/2015 01:52:33] Read data (COM6)
00 01 30 00 ff 00 f2 da ..0.ÿ.òÚ

Counter rolls over:

[10/11/2015 01:52:33] Written data (COM6)
01 00 30 00 00 00 fc 37 ..0...ü7
[10/11/2015 01:52:33] Read data (COM6)
00 01 30 00 00 00 0d d8 ..0....Ø

[10/11/2015 01:52:34] Written data (COM6)
01 00 30 00 00 00 fc 37 ..0...ü7
[10/11/2015 01:52:34] Read data (COM6)
00 01 30 00 01 00 3c eb ..0...<ë

1st good message.. and so on...

[10/11/2015 01:52:34] Written data (COM6)
01 00 30 00 00 00 fc 37 ..0...ü7
[10/11/2015 01:52:34] Read data (COM6)
00 01 30 00 02 00 6f be ..0...o¾

beyondhelp · « **Reply #13 on:** November 10, 2015, 02:12:11 am »

I'm having a go now (really should be asleep) of quickly making a program in processing to send serial data to the hardware directly from the pc, rather than arduino. That way its easy for me to see the data sent/received, and to try ataradovs idea.

hamster_nz · « **Reply #14 on:** November 10, 2015, 09:45:53 am »

Prediction:

Code: [Select]

00 01 30 00 08 00  => a4 51
00 01 30 00 09 00  => 95 62
00 01 30 00 0a 00  => c6 37
00 01 30 00 0b 00  => f7 04
00 01 30 00 0c 00  => 60 9d
00 01 30 00 0d 00  => 51 ae
00 01 30 00 0e 00  => 02 fb
00 01 30 00 0f 00  => 33 c8

It looks like CRC16, but there seems to be some thing else going on. Could there be extra bytes in the message? or could the first three bytes be packed somehow?

hamster_nz · « **Reply #15 on:** November 10, 2015, 10:21:41 am »

Quote from: beyondhelp on November 10, 2015, 12:41:39 am

This has been bugging me for a while. I have a piece of hardware that I want to control from a MCU that currently works over a simple serial connection from a piece of software (that wont work in win10!). In order for me to really do this I need to figure out how the checksum works so that I don't have to manually store tons of data when it could easily be calculated on the fly.

Data is sent as blocks of 8 bytes, the last two are checksum. If I alter those the hardware does not respond, if I alter the other 6 bytes the hardware does also not respond and in both cases an 8bit corrupt data counter is increased by 1.

So here is an example of valid data:
01 00 20 01 01 01 7b 38
01 00 20 02 02 02 1b 04
01 00 20 03 03 03 3b 10
01 00 20 04 04 04 db 7c
01 00 20 05 05 05 fb 68
01 00 20 06 06 06 9b 54
01 00 20 07 07 07 bb 40
01 00 20 08 08 08 6a be
01 00 20 09 09 09 4a aa
01 00 20 0a 0a 0a 2a 96
01 00 20 0b 0b 0b 0a 82
01 00 20 0c 0c 0c ea ee
01 00 20 0d 0d 0d ca fa
01 00 20 0e 0e 0e aa c6
01 00 20 0f 0f 0f 8a d2

Somehow the last two bytes are calculated from the first 6. I would have thought it cannot be *that* complicated as the hardware is based on a 16f871 PIC. I have tried some CRC ideas but basically, I'm looking for any ideas that may help me! I have also tried looking for patterns in binary (nothing obvious). Thing is this isn't my strong point hence I post here in the hope that someone with more experience may help me.

Strange...it looks like bit 3 of byte 4 somehow gets xored with bit 1 or byte 5...

This is my code with the test vectors slightly munged by XORing with 00 00 00 00 01 00 for the last eight... I get the right checksums, but can't explain why...


01 00 20 01 01 01  => 7b 38 should be 7b 38, error 00 00
01 00 20 02 02 02  => 1b 04 should be 1b 04, error 00 00
01 00 20 03 03 03  => 3b 10 should be 3b 10, error 00 00
01 00 20 04 04 04  => db 7c should be db 7c, error 00 00
01 00 20 05 05 05  => fb 68 should be fb 68, error 00 00
01 00 20 06 06 06  => 9b 54 should be 9b 54, error 00 00
01 00 20 07 07 07  => bb 40 should be bb 40, error 00 00
01 00 20 08 09 08  => 6a be should be 6a be, error 00 00
01 00 20 09 08 09  => 4a aa should be 4a aa, error 00 00
01 00 20 0a 0b 0a  => 2a 96 should be 2a 96, error 00 00
01 00 20 0b 0a 0b  => 0a 82 should be 0a 82, error 00 00
01 00 20 0c 0d 0c  => ea ee should be ea ee, error 00 00
01 00 20 0d 0c 0d  => ca fa should be ca fa, error 00 00
01 00 20 0e 0f 0e  => aa c6 should be aa c6, error 00 00
01 00 20 0f 0e 0f  => 8a d2 should be 8a d2, error 00 00

BradC · « **Reply #16 on:** November 10, 2015, 11:17:46 am »

If it were me I'd step through the Windows app in IDA and just watch what it does.. but that's a totally different ballgame.

legacy · « **Reply #17 on:** November 10, 2015, 12:00:46 pm »

Quote from: BradC on November 10, 2015, 11:17:46 am

If it were me I'd step through the Windows app in IDA and just watch what it does.. but that's a totally different ballgame.

Is it able to reverse at the C level, or just assembly?

mikerj · « **Reply #18 on:** November 10, 2015, 03:28:13 pm »

Quote from: legacy on November 10, 2015, 12:00:46 pm

Quote from: BradC on November 10, 2015, 11:17:46 am
If it were me I'd step through the Windows app in IDA and just watch what it does.. but that's a totally different ballgame.

Is it able to reverse at the C level, or just assembly?

IDA=Interactive DisAssembler. You can only debug at the C level if you have the source code and the appropriate debug files.

nctnico · « **Reply #19 on:** November 10, 2015, 04:26:34 pm »

There are several ways to tackle this. If the software is written in .Net or Microsoft C chances are you can decompile it back to source. If not even then a decompiler can provide some insight into how a program works.

What works in many cases is using a debugger and see where the checksum gets calculated. It may be they are using a non-zero seed value. Besides IDA there is also olydbg ( http://www.ollydbg.de/ )

beyondhelp · « **Reply #20 on:** November 10, 2015, 08:29:07 pm »

Cool, I had to call it a day and get some sleep, just got home and its half 8pm, and going to have another play with it. A friend of mine who is a bit of a reverse engineering wiz is also having a look, but don't let that put you off.. I'll tease him lots if I can figure it out with help from you all here first

beyondhelp · « **Reply #21 on:** November 10, 2015, 08:35:06 pm »

Quote from: hamster_nz on November 10, 2015, 09:45:53 am

Prediction:

Code: [Select]
00 01 30 00 08 00 => a4 51 00 01 30 00 09 00 => 95 62 00 01 30 00 0a 00 => c6 37 00 01 30 00 0b 00 => f7 04 00 01 30 00 0c 00 => 60 9d 00 01 30 00 0d 00 => 51 ae 00 01 30 00 0e 00 => 02 fb 00 01 30 00 0f 00 => 33 c8
It looks like CRC16, but there seems to be some thing else going on. Could there be extra bytes in the message? or could the first three bytes be packed somehow?

Results:
00 01 30 00 08 00 85 40
00 01 30 00 09 00 b4 73
00 01 30 00 0a 00 e7 26
00 01 30 00 0b 00 d6 15

hamster_nz · « **Reply #22 on:** November 10, 2015, 08:58:17 pm »

Quote from: beyondhelp on November 10, 2015, 08:35:06 pm

Quote from: hamster_nz on November 10, 2015, 09:45:53 am
Prediction:

Code: [Select]
00 01 30 00 08 00 => a4 51 00 01 30 00 09 00 => 95 62 00 01 30 00 0a 00 => c6 37 00 01 30 00 0b 00 => f7 04 00 01 30 00 0c 00 => 60 9d 00 01 30 00 0d 00 => 51 ae 00 01 30 00 0e 00 => 02 fb 00 01 30 00 0f 00 => 33 c8
It looks like CRC16, but there seems to be some thing else going on. Could there be extra bytes in the message? or could the first three bytes be packed somehow?

Results:
00 01 30 00 08 00 85 40
00 01 30 00 09 00 b4 73
00 01 30 00 0a 00 e7 26
00 01 30 00 0b 00 d6 15

Humm all out by 21 11 ... eg a4 51 xor 21 11 = 85 40.....

nali · « **Reply #23 on:** November 10, 2015, 09:37:54 pm »

Quote from: beyondhelp on November 10, 2015, 12:41:39 am

This has been bugging me for a while. I have a piece of hardware that I want to control from a MCU that currently works over a simple serial connection from a piece of software (that wont work in win10!). In order for me to really do this I need to figure out how the checksum works so that I don't have to manually store tons of data when it could easily be calculated on the fly.

Data is sent as blocks of 8 bytes, the last two are checksum. If I alter those the hardware does not respond, if I alter the other 6 bytes the hardware does also not respond and in both cases an 8bit corrupt data counter is increased by 1.

So here is an example of valid data:
01 00 20 01 01 01 7b 38
01 00 20 02 02 02 1b 04
01 00 20 03 03 03 3b 10
01 00 20 04 04 04 db 7c
01 00 20 05 05 05 fb 68
01 00 20 06 06 06 9b 54
01 00 20 07 07 07 bb 40
01 00 20 08 08 08 6a be
01 00 20 09 09 09 4a aa
01 00 20 0a 0a 0a 2a 96
01 00 20 0b 0b 0b 0a 82
01 00 20 0c 0c 0c ea ee
01 00 20 0d 0d 0d ca fa
01 00 20 0e 0e 0e aa c6
01 00 20 0f 0f 0f 8a d2

Somehow the last two bytes are calculated from the first 6. I would have thought it cannot be *that* complicated as the hardware is based on a 16f871 PIC. I have tried some CRC ideas but basically, I'm looking for any ideas that may help me! I have also tried looking for patterns in binary (nothing obvious). Thing is this isn't my strong point hence I post here in the hope that someone with more experience may help me.

Well if you map out the checksums in binary there are definitely some bit patterns in there, you can see some of the binary counting in some of the individual bits i.e. 01010101 00110011 00001111 etc. The one exception to that is bit 4 of the checksum which changes pattern on the 4th row

01 00 20 01 01 01 7b 38 0111101100111000
01 00 20 02 02 02 1b 04 0001101100000100
01 00 20 03 03 03 3b 10 0011101100010000
01 00 20 04 04 04 db 7c 1101101101111100
01 00 20 05 05 05 fb 68 1111101101101000
01 00 20 06 06 06 9b 54 1001101101010100
01 00 20 07 07 07 bb 40 1011101101000000
01 00 20 08 08 08 6a be 0110101010111110
01 00 20 09 09 09 4a aa 0100101010101010
01 00 20 0a 0a 0a 2a 96 0010101010010110
01 00 20 0b 0b 0b 0a 82 0000101010000010
01 00 20 0c 0c 0c ea ee 1110101011101110
01 00 20 0d 0d 0d ca fa 1100101011111010
01 00 20 0e 0e 0e aa c6 1010101011000110
01 00 20 0f 0f 0f 8a d2 1000101011010010

beyondhelp · « **Reply #24 on:** November 10, 2015, 09:50:33 pm »

Quote from: hamster_nz on November 10, 2015, 08:58:17 pm

Humm all out by 21 11 ... eg a4 51 xor 21 11 = 85 40.....

On that basis do you get the same checksum with this:

00 01 70 01 22 01 14 d3

or

00 01 00 00 00 00 e4 f5

ataradov · « **Reply #25 on:** November 10, 2015, 09:54:05 pm »

Have you gotten anywhere with generating arbitrary packets? It would help a lot and will eliminate a lot of guessing. Required patterns:

00 00 00 00 00 00
00 00 00 00 00 01
01 00 00 00 00 00
80 00 00 00 00 00
00 00 00 00 00 80

beyondhelp · « **Reply #26 on:** November 10, 2015, 10:13:34 pm »

just working out how to send and receive data in processing. That way I can record the results easier than just via an arduino. I;m going to spend a couple of hours on it now and I'll let you know how I get on using those bytes.

beyondhelp · « **Reply #27 on:** November 11, 2015, 02:59:59 am »

finally its 3am and i have a test running. Should have the first checksum for 01 00 00 00 00 00 soon I hope

beyondhelp · « **Reply #28 on:** November 11, 2015, 03:32:13 am »

GOT ONE!!!

01 00 00 00 00 00 15 1a

Interestingly I get a reply as well

00 01 00 00 00 00 e4 f5

No idea what that means yet, but I have had that response from other requests.

Shall keep looking but I'll let it run as im off to bed now.

ataradov · « **Reply #29 on:** November 11, 2015, 03:34:28 am »

Quote from: beyondhelp on November 11, 2015, 03:32:13 am

GOT ONE!!!

Now run the rest of my combinations, especially all 00's.

You now have a very powerful tool in your hands.

beyondhelp · « **Reply #30 on:** November 11, 2015, 03:39:17 am »

Thanks, yes its very exciting... Its rather slow however took 20 mins to get that one. I'm sending packets of data every 300ms, so could take as long as 6 hours, but it means my serial port program on the pc (requests are being sent from the arduino) format nicely and so spotting the change in counts when it responds is easy.

Working on 00 00 00 00 00 01 now. but I have to goto bed again ,so shall update some point tomorrow!

Thanks for the help so far...

JimRemington · « **Reply #31 on:** November 11, 2015, 04:07:14 am »

I've had good luck with the CRC reverse engineering program called "reveng", download here: http://sourceforge.net/projects/reveng/

It can decode an arbitrary CRC and also reverses the bitstreams, etc. I gave reveng a couple of tries (with the presumed 16 bit CRC in both byte orders) and it works for three of the messages, but not with four messages. However, it is a bad sign if more than one polynomial is discovered, or if the byte order of the CRC checksum doesn't matter, which may mean that the input data are linearly dependent. I'll keep playing with it a bit, but here is a log of a few attempts, using the first three messages you posted, and finally adding one of the latter messages. In each attempt, the byte order of the presumed checksum is swapped.

Note: in one particularly difficult case I had to swap the NIBBLES of each byte in order to solve the problem!

Code: [Select]

C:\Users\Justme\Desktop\Current\REVENG~1.0A>reveng -s -w16  010020010101387b 010
020020202041b 010020030303103b
width=16  poly=0x1021  init=0x0a56  refin=false  refout=false  xorout=0x0000  ch
eck=0x95f4  name=(none)

C:\Users\Justme\Desktop\Current\REVENG~1.0A>reveng -s -w16  0100200101017b38 010
0200202021b04 0100200303033b10
width=16  poly=0x726f  init=0x4be1  refin=true  refout=true  xorout=0x0000  chec
k=0x99ee  name=(none)
width=16  poly=0xadd7  init=0x2e11  refin=true  refout=true  xorout=0x0000  chec
k=0x8e4c  name=(none)

C:\Users\Justme\Desktop\Current\REVENG~1.0A>reveng -s -w16  010020010101387b 010
020020202041b 010020030303103b 0100200f0f0fd28a
reveng: no models found

C:\Users\Justme\Desktop\Current\REVENG~1.0A>reveng -s -w16  0100200101017b38 010
0200202021b04 0100200303033b10 0100200f0f0f8ad2
reveng: no models found

beyondhelp · « **Reply #32 on:** November 11, 2015, 08:53:43 am »

I have another one... This took some time to recover:

00 00 00 00 00 01 94 4f

Shall leave if finding 00 00 00 00 00 00 now

Andy Watson · « **Reply #33 on:** November 11, 2015, 01:15:04 pm »

Quote from: beyondhelp on November 11, 2015, 03:32:13 am

GOT ONE!!!

01 00 00 00 00 00 15 1a

Interestingly I get a reply as well

00 01 00 00 00 00 e4 f5

Just one? I'd count that as TWO

beyondhelp · « **Reply #34 on:** November 11, 2015, 05:36:17 pm »

I have another!

00 00 00 00 00 00 b5 5f - took over 4 hours to get that one!

So far, form the list I needed above:
01 00 00 00 00 00 15 1a
00 00 00 00 00 01 94 4f
00 00 00 00 00 00 b5 5f

ataradov · « **Reply #35 on:** November 11, 2015, 05:38:29 pm »

That's great. I'll play with those numbers later today and we'll see what can be done here.

beyondhelp · « **Reply #36 on:** November 11, 2015, 05:48:25 pm »

Awesome, I have double checked and send those, they are all good. Now working on 80 00 00 00 00 00. Hopefully by the time I'm home that will be done as well.

hamster_nz · « **Reply #37 on:** November 11, 2015, 06:52:46 pm »

Sorry... long post....

For all the test vectors I have got from the thread, I've got something that is almost there..

Code: [Select]

00 01 00 00 00 00 => 00 01 00 00 00 00  => e4 f4 should be e4 f5, error 00 01
01 00 20 01 01 01 => 01 00 20 01 01 01  => 7b 38
01 00 20 02 02 02 => 01 00 20 02 02 02  => 1b 04
01 00 20 03 03 03 => 01 00 20 03 03 03  => 3b 10
01 00 20 04 04 04 => 01 00 20 04 04 04  => db 7c
01 00 20 05 05 05 => 01 00 20 05 05 05  => fb 68
01 00 20 06 06 06 => 01 00 20 06 06 06  => 9b 54
01 00 20 07 07 07 => 01 00 20 07 07 07  => bb 40
01 00 20 08 08 08 => 01 00 20 08 09 08  => 6a be
01 00 20 09 09 09 => 01 00 20 09 08 09  => 4a aa
01 00 20 0a 0a 0a => 01 00 20 0a 0b 0a  => 2a 96
01 00 20 0b 0b 0b => 01 00 20 0b 0a 0b  => 0a 82
01 00 20 0c 0c 0c => 01 00 20 0c 0d 0c  => ea ee
01 00 20 0d 0d 0d => 01 00 20 0d 0c 0d  => ca fa
01 00 20 0e 0e 0e => 01 00 20 0e 0f 0e  => aa c6
01 00 20 0f 0f 0f => 01 00 20 0f 0e 0f  => 8a d2
00 01 70 01 22 01 => 00 01 70 01 23 00  => 14 d2 should be 14 d3, error 00 01
00 01 60 00 80 00 => 00 01 60 00 81 00  => 9f 85
00 01 b0 00 20 00 => 00 01 b0 01 21 01  => f3 17 should be f3 16, error 00 01
00 01 b0 01 20 00 => 00 01 b0 00 21 01  => c3 20 should be c3 21, error 00 01
00 01 b0 02 53 00 => 00 01 b0 03 52 01  => 99 24
00 01 b0 03 65 00 => 00 01 b0 02 64 01  => 9a bc
00 01 b0 04 71 00 => 00 01 b0 05 70 01  => bd f6
00 01 b0 05 75 00 => 00 01 b0 04 74 01  => 49 0d
00 01 b0 06 65 00 => 00 01 b0 07 64 01  => 6a 57
00 01 b0 07 6e 00 => 00 01 b0 06 6f 00  => 81 ac should be 81 ad, error 00 01
00 01 b0 08 63 00 => 00 01 b0 09 63 00  => dd c5
00 01 b0 09 65 00 => 00 01 b0 08 65 00  => 4b 58
00 01 b0 0a 72 00 => 00 01 b0 0b 72 00  => ff 9b
00 01 b0 0b 20 00 => 00 01 b0 0a 20 00  => 12 c4 should be 12 c5, error 00 01
00 01 b0 0c 36 00 => 00 01 b0 0d 36 00  => 57 e8 should be 57 e9, error 00 01
00 01 b0 0d 34 00 => 00 01 b0 0c 34 00  => 05 b9 should be 05 b8, error 00 01
00 01 b0 0e 20 00 => 00 01 b0 0f 20 00  => e2 2f should be e2 2e, error 00 01
00 01 b0 0f 20 00 => 00 01 b0 0e 20 00  => d2 18 should be d2 19, error 00 01
00 01 30 00 58 00 => 00 01 30 00 58 01  => 3a 4f
00 01 30 00 01 00 => 00 01 30 00 01 00  => 3c eb
00 01 30 00 02 00 => 00 01 30 00 02 00  => 6f be
00 01 30 00 03 00 => 00 01 30 00 03 00  => 5e 8d
00 01 30 00 04 00 => 00 01 30 00 04 00  => c9 14
00 01 30 00 05 00 => 00 01 30 00 05 00  => f8 27
00 01 30 00 06 00 => 00 01 30 00 06 00  => ab 72
00 01 30 00 07 00 => 00 01 30 00 07 00  => 9a 41
00 01 30 00 08 00 => 00 01 30 00 08 01  => 85 41 should be 85 40, error 00 01
00 01 30 00 09 00 => 00 01 30 00 09 01  => b4 72 should be b4 73, error 00 01
00 01 30 00 0a 00 => 00 01 30 00 0a 01  => e7 27 should be e7 26, error 00 01
00 01 30 00 0b 00 => 00 01 30 00 0b 01  => d6 14 should be d6 15, error 00 01
01 00 00 00 00 00 => 01 00 00 00 00 00  => 15 1b should be 15 1a, error 00 01

It is some sort of obscuring transform in front of a CRC16...

Code: [Select]

short int my_crc(unsigned char *data, short unsigned length)
{
  int i;
  short unsigned crc = 0, crc_low, crc_high;
  for(i = 0; i < length; i++)
     printf("%02x ",data[i]);
  printf("=> ",data[i]);

  if((data[2] & 0x80)) {
    data[3] ^= 0x01;
    data[4] ^= 0x01;
    data[5] ^= 0x01;
  }
  if((data[2] & 0x70) == 0x70) {
    data[4] ^= 0x01;
    data[5] ^= 0x01;
  }
  if((data[3] & 0x08) ^ (data[4] & 0x80))
    data[4] ^= 0x01;
  if((data[2] & 0x08) ^ (data[3] & 0x08) ^ (data[4] & 0x08))
    data[5] ^= 0x01;

  crc = 0x0000;
  for(i = 0; i < length*8;  i++)
  {
    int mask, index,bit,wrap;
    mask = 0x80>>(i%8);
    index = i/8;
    bit = (data[index] & mask) ? 1 : 0;
    wrap = (crc & 0x8000) ? 1 : 0;
    crc <<= 1;
    if(wrap ^ bit) crc ^= 0x1021;
  }
  /* Display the data) */
  for(i = 0; i < length; i++)
     printf("%02x ",data[i]);
#if 1
  if( data[i] || data[i+1])
     crc ^=  0x1b15 ^ 0x45a0;
#endif
  crc_low  = (crc>>0)&0xFF;
  crc_high = (crc>>8)&0xFF;

  if( crc_low == data[i] && crc_high == data[i+1])
    printf(" => %02x %02x\r\n", data[i], data[i+1]);
  else
    printf(" => %02x %02x should be %02x %02x, error %02x %02x\r\n",
           crc_low, crc_high,
           data[i], data[i+1],
           crc_low^data[i], crc_high^data[i+1]);

  return 0;
}

beyondhelp · « **Reply #38 on:** November 11, 2015, 07:14:24 pm »

Absolutely top work. Honestly I'm way out of my depth with checksums etc, but so grateful for the help I'm being given here. I'm actually amazed at how much work it appears to be to crack this.

Gotta love a challenge eh!

Is there anything more I can do to help? I have a load more captured data I can share.

ataradov · « **Reply #39 on:** November 11, 2015, 07:25:09 pm »

Quote from: beyondhelp on November 11, 2015, 07:14:24 pm

Is there anything more I can do to help? I have a load more captured data I can share.

Capturing more simple cases. Like 01 and 80 in various positions may be helpful.

I don't think it is that complex, it is just something else. Why on earth anyone would do obfuscation like that?

Edit: And may be more useful:
02 00 00 00 00 00
04 00 00 00 00 00
08 00 00 00 00 00
10 00 00 00 00 00
20 00 00 00 00 00
40 00 00 00 00 00

And the same with numbers in the last byte.

This will tell us how individual bits affect the result if they are at the beginning and at the end.

beyondhelp · « **Reply #40 on:** November 11, 2015, 08:13:10 pm »

Ok well its ticking away, a few more hours potentially on this one

hamster_nz · « **Reply #41 on:** November 11, 2015, 08:19:16 pm »

Quote from: beyondhelp on November 11, 2015, 07:14:24 pm

Is there anything more I can do to help? I have a load more captured data I can share.

Yes please, the more test vectors the quicker the result (however, only if you are 100% sure that they are valid - if a bad test slips in it it can be a real bother to weed out!

It definitely has a CRC nature to it:
- You can flip bits in the input and it usually flips the same same set of bits in the checksum
- The bits that are flipped are usually the same that would be flipped in an vanilla CRC16 checksum
- So far when the CRC bits flipped they aren't the same as the simple CRC16 checksum, it can be solved by also flipping some of the following LSBs e.g:

Code: [Select]

  if((data[2] & 0x80)) {
    data[3] ^= 0x01;
    data[4] ^= 0x01;
    data[5] ^= 0x01;
  }

and

Code: [Select]

  if((data[3] & 0x08) ^ (data[4] & 0x80))
    data[4] ^= 0x01;
  ....

That transform seems just too structured to be a random coincidence - I just don't have enough data at the moment to get the insight to determine the original pattern.

So I guess the original thinking went along the line of "I want to use a CRC16, but don't want anybody to reverse engineering the protocol. I'll apply a simple 'random' transform to data before I CRC it - that way I have the benefits of a standard CRC & standard polynomial (i.e. can use a CRC library) but it isn't obvious on the wire".

beyondhelp · « **Reply #42 on:** November 11, 2015, 08:26:13 pm »

ok another one to add to the list:

80 00 00 00 00 00 71 53

beyondhelp · « **Reply #43 on:** November 11, 2015, 08:29:53 pm »

These are all valid, as they were generated by the hardware and captured.

Code: [Select]

00 01 70 01 22 01 14 d3
00 01 60 00 f3 01 b4 c9
00 01 b0 00 20 00 f3 16
00 01 b0 01 20 00 c3 21
00 01 b0 02 53 00 99 24
00 01 b0 03 65 00 9a bc
00 01 b0 04 71 00 bd f6
00 01 b0 05 75 00 49 0d
00 01 b0 06 65 00 6a 57
00 01 b0 07 6e 00 81 ad
00 01 b0 08 63 00 dd c5
00 01 b0 09 65 00 4b 58
00 01 b0 0a 72 00 ff 9b
00 01 b0 0b 20 00 12 c5
00 01 b0 0c 36 00 57 e9
00 01 b0 0d 34 00 05 b8
00 01 b0 0e 20 00 e2 2e
00 01 b0 0f 20 00 d2 19
00 01 30 00 2a 00 01 20
00 01 00 00 00 00 e4 f5
00 01 00 00 00 00 e4 f5
00 01 00 00 00 00 e4 f5
00 01 00 00 00 00 e4 f5

00 01 70 01 22 01 14 d3
00 01 60 00 d7 01 96 03
00 01 b0 00 20 00 f3 16
00 01 b0 01 20 00 c3 21
00 01 b0 02 53 00 99 24
00 01 b0 03 65 00 9a bc
00 01 b0 04 71 00 bd f6
00 01 b0 05 75 00 49 0d
00 01 b0 06 65 00 6a 57
00 01 b0 07 6e 00 81 ad
00 01 b0 08 63 00 dd c5
00 01 b0 09 65 00 4b 58
00 01 b0 0a 72 00 ff 9b
00 01 b0 0b 20 00 12 c5
00 01 b0 0c 36 00 57 e9
00 01 b0 0d 34 00 05 b8
00 01 b0 0e 20 00 e2 2e
00 01 b0 0f 20 00 d2 19
00 01 30 00 13 00 2d 8e
00 01 00 00 00 00 e4 f5
00 01 00 00 00 00 e4 f5
00 01 00 00 00 00 e4 f5
00 01 00 00 00 00 e4 f5

00 01 70 01 22 01 14 d3
00 01 60 00 80 00 9f 85
00 01 b0 00 20 00 f3 16
00 01 b0 01 20 00 c3 21
00 01 b0 02 53 00 99 24
00 01 b0 03 65 00 9a bc
00 01 b0 04 71 00 bd f6
00 01 b0 05 75 00 49 0d
00 01 b0 06 65 00 6a 57
00 01 b0 07 6e 00 81 ad
00 01 b0 08 63 00 dd c5
00 01 b0 09 65 00 4b 58
00 01 b0 0a 72 00 ff 9b
00 01 b0 0b 20 00 12 c5
00 01 b0 0c 36 00 57 e9
00 01 b0 0d 34 00 05 b8
00 01 b0 0e 20 00 e2 2e
00 01 b0 0f 20 00 d2 19
00 01 30 00 58 00 3a 4f
00 01 00 00 00 00 e4 f5
00 01 00 00 00 00 e4 f5
00 01 00 00 00 00 e4 f5
00 01 00 00 00 00 e4 f5

00 01 70 01 22 01 14 d3
00 01 60 00 7e 00 51 b4
00 01 b0 00 20 00 f3 16
00 01 b0 01 20 00 c3 21
00 01 b0 02 53 00 99 24
00 01 b0 03 65 00 9a bc
00 01 b0 04 71 00 bd f6
00 01 b0 05 75 00 49 0d
00 01 b0 06 65 00 6a 57
00 01 b0 07 6e 00 81 ad
00 01 b0 08 63 00 dd c5
00 01 b0 09 65 00 4b 58
00 01 b0 0a 72 00 ff 9b
00 01 b0 0b 20 00 12 c5
00 01 b0 0c 36 00 57 e9
00 01 b0 0d 34 00 05 b8
00 01 b0 0e 20 00 e2 2e
00 01 b0 0f 20 00 d2 19
00 01 30 00 41 00 f0 e7
00 01 00 00 00 00 e4 f5

beyondhelp · « **Reply #44 on:** November 12, 2015, 12:10:21 am »

Ok the last one on that list:

00 00 00 00 00 80 3d cf

Interestingly the bad message counter just doesn't count anything when this checksum is correct. No good or bad messages. It just totally ignores it, however change any bit on the checksum and it then flags a bad message.

So there complete list!

01 00 00 00 00 00 15 1a
00 00 00 00 00 01 94 4f
00 00 00 00 00 00 b5 5f
80 00 00 00 00 00 71 53
00 00 00 00 00 80 3d cf

I shall start it doing some of the other suggestions now.

ataradov · « **Reply #45 on:** November 12, 2015, 12:16:45 am »

Can't wait to get home and start working on this

I love practical brain teasers like that.

beyondhelp · « **Reply #46 on:** November 12, 2015, 01:17:43 am »

haha I can't wait for you to do it as well!!

I've just been looking, but don't really know where to start :s

apelly · « **Reply #47 on:** November 12, 2015, 01:26:46 am »

It's not something like check-digit + crc is it?

beyondhelp · « **Reply #48 on:** November 12, 2015, 01:39:48 am »

Quote from: hamster_nz on November 11, 2015, 08:19:16 pm

That transform seems just too structured to be a random coincidence - I just don't have enough data at the moment to get the insight to determine the original pattern.

So I guess the original thinking went along the line of "I want to use a CRC16, but don't want anybody to reverse engineering the protocol. I'll apply a simple 'random' transform to data before I CRC it - that way I have the benefits of a standard CRC & standard polynomial (i.e. can use a CRC library) but it isn't obvious on the wire".

That makes perfect sense, and is all I can really think it could be. I mean why would you want to make it even more complex?

bson · « **Reply #49 on:** November 12, 2015, 02:46:47 am »

Quote from: hamster_nz on November 11, 2015, 06:52:46 pm

It is some sort of obscuring transform in front of a CRC16...

Maybe it starts at something other than 0... like a simple mod 255 sum of the bytes in the message, or something.

JimRemington · « **Reply #50 on:** November 12, 2015, 02:57:18 am »

Quote

Maybe it starts at something other than 0

If it were a constant, reveng (post #31) would have found it. Reveng checks for both pre- and post-XOR values.

Here is an example of a rather bizarre variation on a CRC checksum that was rather laboriously decoded, and it seems to be common among several manufacturers of simple temperature sensors: https://eclecticmusingsofachaoticmind.wordpress.com/2015/01/21/home-automation-temperature-sensors/

hamster_nz · « **Reply #51 on:** November 12, 2015, 03:47:23 am »

Getting close... only got a single bit of error in the final checksum, but can't see how this is being caused.

The issue that the error is the same for all failing tests is a big clue. But why '00 00 00 00 00 00' works yet '00 00 00 00 00 80' doesn't, and then '00 01 30 00 2a 00' passes but '00 01 30 00 13 00' doesn't, but both with the same error perplexes me.

All test vectors supplied so far (sorted and de-duplicated) and my results....

Code: [Select]

Raw    => Goes into CRC16 => Checksum
00 00 00 00 00 00 => 00 00 00 00 00 00  => b5 5f
00 00 00 00 00 01 => 00 00 00 00 00 01  => 94 4f
00 00 00 00 00 80 => 00 00 00 00 00 80  => 3d ce should be 3d cf, error 00 01
00 01 00 00 00 00 => 00 01 00 00 00 00  => e4 f5
00 01 30 00 13 00 => 00 01 30 00 13 00  => 2d 8f should be 2d 8e, error 00 01
00 01 30 00 2a 00 => 00 01 30 00 2a 01  => 01 20
00 01 30 00 41 00 => 00 01 30 00 41 00  => f0 e7
00 01 30 00 58 00 => 00 01 30 00 58 01  => 3a 4e should be 3a 4f, error 00 01
00 01 60 00 7e 00 => 00 01 60 00 7f 00  => 51 b4
00 01 60 00 80 00 => 00 01 60 00 81 00  => 9f 84 should be 9f 85, error 00 01
00 01 60 00 d7 01 => 00 01 60 00 d6 01  => 96 03
00 01 60 00 f3 01 => 00 01 60 00 f2 01  => b4 c9
00 01 70 01 22 01 => 00 01 70 01 23 00  => 14 d3
00 01 b0 00 20 00 => 00 01 b0 01 21 01  => f3 16
00 01 b0 01 20 00 => 00 01 b0 00 21 01  => c3 21
00 01 b0 02 53 00 => 00 01 b0 03 52 01  => 99 25 should be 99 24, error 00 01
00 01 b0 03 65 00 => 00 01 b0 02 64 01  => 9a bd should be 9a bc, error 00 01
00 01 b0 04 71 00 => 00 01 b0 05 70 01  => bd f7 should be bd f6, error 00 01
00 01 b0 05 75 00 => 00 01 b0 04 74 01  => 49 0c should be 49 0d, error 00 01
00 01 b0 06 65 00 => 00 01 b0 07 64 01  => 6a 56 should be 6a 57, error 00 01
00 01 b0 07 6e 00 => 00 01 b0 06 6f 00  => 81 ad
00 01 b0 08 63 00 => 00 01 b0 09 63 00  => dd c4 should be dd c5, error 00 01
00 01 b0 09 65 00 => 00 01 b0 08 65 00  => 4b 59 should be 4b 58, error 00 01
00 01 b0 0a 72 00 => 00 01 b0 0b 72 00  => ff 9a should be ff 9b, error 00 01
00 01 b0 0b 20 00 => 00 01 b0 0a 20 00  => 12 c5
00 01 b0 0c 36 00 => 00 01 b0 0d 36 00  => 57 e9
00 01 b0 0d 34 00 => 00 01 b0 0c 34 00  => 05 b8
00 01 b0 0e 20 00 => 00 01 b0 0f 20 00  => e2 2e
00 01 b0 0f 20 00 => 00 01 b0 0e 20 00  => d2 19
01 00 00 00 00 00 => 01 00 00 00 00 00  => 15 1a
01 00 20 01 01 01 => 01 00 20 01 01 01  => 7b 39 should be 7b 38, error 00 01
01 00 20 02 02 02 => 01 00 20 02 02 02  => 1b 05 should be 1b 04, error 00 01
01 00 20 03 03 03 => 01 00 20 03 03 03  => 3b 11 should be 3b 10, error 00 01
01 00 20 04 04 04 => 01 00 20 04 04 04  => db 7d should be db 7c, error 00 01
01 00 20 05 05 05 => 01 00 20 05 05 05  => fb 69 should be fb 68, error 00 01
01 00 20 06 06 06 => 01 00 20 06 06 06  => 9b 55 should be 9b 54, error 00 01
01 00 20 07 07 07 => 01 00 20 07 07 07  => bb 41 should be bb 40, error 00 01
01 00 20 08 08 08 => 01 00 20 08 09 08  => 6a bf should be 6a be, error 00 01
01 00 20 09 09 09 => 01 00 20 09 08 09  => 4a ab should be 4a aa, error 00 01
01 00 20 0a 0a 0a => 01 00 20 0a 0b 0a  => 2a 97 should be 2a 96, error 00 01
01 00 20 0b 0b 0b => 01 00 20 0b 0a 0b  => 0a 83 should be 0a 82, error 00 01
01 00 20 0c 0c 0c => 01 00 20 0c 0d 0c  => ea ef should be ea ee, error 00 01
01 00 20 0d 0d 0d => 01 00 20 0d 0c 0d  => ca fb should be ca fa, error 00 01
01 00 20 0e 0e 0e => 01 00 20 0e 0f 0e  => aa c7 should be aa c6, error 00 01
01 00 20 0f 0f 0f => 01 00 20 0f 0e 0f  => 8a d3 should be 8a d2, error 00 01
80 00 00 00 00 00 => 80 01 01 01 01 00  => 71 53

ataradov · « **Reply #52 on:** November 12, 2015, 03:53:14 am »

Are you still adding new preprocessing rules to the same code or got something new?

I just can't see what should go though someone's head to do something like this.

The input data size is small, so it is possible that operations involved in CRC just happened to be useful part of the real algorithm that has nothing to do with cyclic codes. In that case having the source with hacks would help, but CRC part needs to be unrolled, and some new better algorithm will emerge in combination with your preprocessing.

ataradov · « **Reply #53 on:** November 12, 2015, 04:31:58 am »

I've got an idea for a more math-based approach, but for that you will need all checksums for all 48 single bits (80...00, 40...00, etc until 00...02, 00...01, 00...00). We have some of them already.

Basically after that any CRC will be a linear combination of the above CRCs. So for example CRC(00...05) == CRC(00...04) + CRC(00...01) - CRC(00...00).

This should work for any block code, not necessarily cyclic. There is also a way to reverse it back to a polynomial if it will turn out to be cyclic, which I doubt it will.

We really need at least blocks I've mentioned earlier. We have 00...01, 00...00, all we need is 00...05 and 00...04 to test this theory.

JimRemington · « **Reply #54 on:** November 12, 2015, 05:08:20 am »

Quote from: ataradov on November 12, 2015, 04:31:58 am

Basically after that any CRC will be a linear combination of the above CRCs. So for example CRC(00...05) == CRC(00...04) + CRC(00...01) - CRC(00...00).

That seems to work for this set (excerpted from one of the above posts by beyondhelp)

00 01 b0 00 20 00 f3 16
00 01 b0 01 20 00 c3 21
00 01 b0 0e 20 00 e2 2e
00 01 b0 0f 20 00 d2 19

d219=e22e^c321^f316

ataradov · « **Reply #55 on:** November 12, 2015, 05:17:42 am »

Quote from: JimRemington on November 12, 2015, 05:08:20 am

That seems to work for this set (excerpted from one of the above posts by beyondhelp)

Good spotting on the numbers!

I guess OP will have to collect all 48 values, after that we could test this theory against all other known values.

And if that works, it can be ether used as is, or just for fun we can try to minimize it.

beyondhelp · « **Reply #56 on:** November 12, 2015, 12:18:55 pm »

Ok, I'll keep going until I have more. I'll have more time this afternoon.
I'm amazed/fascinated how tricky it appears to be, but then I guess its a case of its easy when you know how.

I'll update more as soon as I find them.

hamster_nz · « **Reply #57 on:** November 12, 2015, 06:49:32 pm »

I'm not expecting many to be valid (and some you have already mined), but if you try these and a few new ones are correct it might save you a lot of work...

Code: [Select]

80 00 00 00 00 00 71 53
40 00 00 00 00 00 10 47
20 00 00 00 00 00 bd 6b
10 00 00 00 00 00 31 45
08 00 00 00 00 00 13 8b
04 00 00 00 00 00 14 59
02 00 00 00 00 00 f5 d4
01 00 00 00 00 00 15 1a
00 80 00 00 00 00 f1 1f
00 40 00 00 00 00 fd 5a
00 20 00 00 00 00 01 56
00 10 00 00 00 00 ef 5b
00 08 00 00 00 00 0c 3e
00 04 00 00 00 00 b3 d6
00 02 00 00 00 00 36 1b
00 01 00 00 00 00 e4 f5
00 00 80 00 00 00 ad 96
00 00 40 00 00 00 39 12
00 00 20 00 00 00 fb 69
00 00 10 00 00 00 12 44
00 00 08 00 00 00 56 cf
00 00 04 00 00 00 44 95
00 00 02 00 00 00 dd b2
00 00 01 00 00 00 01 29
00 00 00 80 00 00 ff 47
00 00 00 40 00 00 39 52
00 00 00 20 00 00 73 d8
00 00 00 10 00 00 d6 1c
00 00 00 08 00 00 04 d4
00 00 00 04 00 00 75 83
00 00 00 02 00 00 d5 31
00 00 00 01 00 00 85 68
00 00 00 00 80 00 0c 54
00 00 00 00 40 00 79 52
00 00 00 00 20 00 53 58
00 00 00 00 10 00 c6 5c
00 00 00 00 08 00 3d c7
00 00 00 00 04 00 71 93
00 00 00 00 02 00 d7 39
00 00 00 00 01 00 84 6c
00 00 00 00 00 80 3d ce
00 00 00 00 00 40 71 17
00 00 00 00 00 20 d7 7b
00 00 00 00 00 10 84 4d
00 00 00 00 00 08 bd de
00 00 00 00 00 04 31 1f
00 00 00 00 00 02 f7 7f
00 00 00 00 00 01 94 4f

ataradov · « **Reply #58 on:** November 12, 2015, 06:54:06 pm »

Quote from: hamster_nz on November 12, 2015, 06:49:32 pm

I'm not expecting many to be valid (and some you have already mined), but if you try these and a few new ones are correct it might save you a lot of work...

Excellent idea. beyondhelp,try them first and see how many work.

I'm still not entirely convinced that my method works. I did not invent it, obviously, I just heard that something like that should work, but I'm fuzzy on the details. We need a few more test cases before you go recovering the rest of them.

beyondhelp · « **Reply #59 on:** November 12, 2015, 10:28:32 pm »

Wow thats an excellent idea.

I just got home and at some point the pc had restarted (updates??!?!!) anyway, todays work 'lost' I'll try those all now, and report back shortly.

JimRemington · « **Reply #60 on:** November 12, 2015, 11:26:08 pm »

Quote from: ataradov on November 12, 2015, 06:54:06 pm

I'm still not entirely convinced that my method works. I did not invent it, obviously, I just heard that something like that should work, but I'm fuzzy on the details. We need a few more test cases before you go recovering the rest of them.

You are certainly on the right track. Here is an excellent overview on brute force/linear algebra methods for deducing such algorithms: http://www.cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.html

Following one of the protocols suggested in the above to deduce the polynomial, if there is one, gives an important clue

Code: [Select]

00 01 30 00 01 00 3c eb
00 01 30 00 02 00 6f be  53 55
00 01 30 00 04 00 c9 14  a6 aa

In the above, the data entries differ by a single bit shift. The last column is the XOR of the two checksums, which, if this were a standard CRC, would either be the polynomial or zero.

However, the result of the XOR of two CRCs is bit shifted by one to the left in successive operations. So, one possibility is that the polynomial itself is also being shifted.

ataradov · « **Reply #61 on:** November 13, 2015, 12:18:59 am »

Quote from: JimRemington on November 12, 2015, 11:26:08 pm

Here is an excellent overview on brute force/linear algebra methods for deducing such algorithms

That looks like a good confirmation that my memory serves me well. I guess it is a safe bet to collect CRC for all positions of "1"s.

Quote from: JimRemington on November 12, 2015, 11:26:08 pm

So, one possibility is that the polynomial itself is also being shifted.

It does not have to be a polynomial at all. At this point we know that it is not a CRC of any kind.

beyondhelp · « **Reply #62 on:** November 13, 2015, 12:36:30 am »

Quote from: hamster_nz on November 12, 2015, 06:49:32 pm

I'm not expecting many to be valid (and some you have already mined), but if you try these and a few new ones are correct it might save you a lot of work...

You are not kidding. MANY of those were valid, about 3/5th many several of the others were out by one bit, the end result so far is this:
The gaps are the missing ones I'm working on those now, and have now a much much faster way to mine them, so shouldn't take too long.

Code: [Select]

80 00 00 00 00 00 71 53
40 00 00 00 00 00 31 57
20 00 00 00 00 00 8c 58
10 00 00 00 00 00 10 55
08 00 00 00 00 00 33 9e
04 00 00 00 00 00 14 59
02 00 00 00 00 00 c4 e7
01 00 00 00 00 00 15 1a
00 80 00 00 00 00 f1 1f
00 40 00 00 00 00 fd 5b
00 20 00 00 00 00 20 47
00 10 00 00 00 00 ef 5a
00 08 00 00 00 00 1c 1d
00 04 00 00 00 00 b3 d6
00 02 00 00 00 00 17 0b
00 01 00 00 00 00 e4 f5
00 00 80 00 00 00 ad 97
00 00 40 00 00 00 39 13
00 00 20 00 00 00 fb 69
00 00 10 00 00 00 12 44
00 00 08 00 00 00 77 de
00 00 04 00 00 00 44 95
00 00 02 00 00 00 dd b3
00 00 01 00 00 00 01 29
00 00 00 80 00 00 ff 46
00 00 00 40 00 00 39 53
00 00 00 20 00 00 73 d9
00 00 00 10 00 00 d6 1c
00 00 00 08 00 00 04 d5
00 00 00 04 00 00 75 83
00 00 00 02 00 00 d5 31
00 00 00 01 00 00 85 68
00 00 00 00 80 00 0c 55
00 00 00 00 40 00 79 53
00 00 00 00 20 00 53 59
00 00 00 00 10 00 c6 5c
00 00 00 00 08 00 3d c7
00 00 00 00 04 00 71 93
00 00 00 00 02 00 d7 39
00 00 00 00 01 00 84 6c
00 00 00 00 00 80 3d cf
00 00 00 00 00 40 71 17
00 00 00 00 00 20 d7 7b
00 00 00 00 00 10 84 4d
00 00 00 00 00 08 bd df
00 00 00 00 00 04 31 1f
00 00 00 00 00 02 f7 7f
00 00 00 00 00 01 94 4f

ataradov · « **Reply #63 on:** November 13, 2015, 12:41:53 am »

We already had "80 00 00 00 00 00 71 53"
And this "02 00 00 00 00 80 00 00" has two bits set. "02 00 00 00 00 00" needs to be re-done.

We have plenty of bits now to do verification. I'll get to it as soon as I get home.

beyondhelp · « **Reply #64 on:** November 13, 2015, 12:46:00 am »

Err, yes I'm just copying and pasting from my code. I'll correct those, it was an old one I'd left behind.

JimRemington · « **Reply #65 on:** November 13, 2015, 01:16:22 am »

Quote

It does not have to be a polynomial at all. At this point we know that it is not a CRC of any kind.

I agree. I did not state that there is a polynomial.

However, I am convinced that the operations employed in the mystery calculation are quite closely related to those of the "familiar CRC", of which there are on the order of 100 well characterized variations. http://reveng.sourceforge.net/crc-catalogue/

ataradov · « **Reply #66 on:** November 13, 2015, 02:05:13 am »

Well, I would declare it a success. First of all, none of the missing bits ever appear in the real data (I'm working with a 94 entries set combined by hamster_nz earlier). We still need to find them, of course.

And checksum calculation algorithm works perfectly on the entire set.

Source code attached.

After all values are known, we can start looking into optimizing this and reversing it back to the original formula (if one exists).

beyondhelp · « **Reply #67 on:** November 13, 2015, 02:34:08 am »

SPEECHLESS

WOW!!!!

ataradov · « **Reply #68 on:** November 13, 2015, 02:36:43 am »

Find the missing bits first. We are missing like 10 bits for complete happiness

beyondhelp · « **Reply #69 on:** November 13, 2015, 02:39:13 am »

Sorry I was running away a bit with excitement... I've been trying to do this for a long long time now.

I shall work on the last remaining ones, and update my post asap. Its 2.40am here so I'll try a couple more now but these late nights this week is catching up fast!

beyondhelp · « **Reply #70 on:** November 13, 2015, 03:02:29 am »

Have added another one.

ataradov · « **Reply #71 on:** November 13, 2015, 03:09:23 am »

Quote from: beyondhelp on November 13, 2015, 03:02:29 am

Have added another one.

I'm counting 3 new ones compared to my table. I don't know why this happened. Anyway, 7 more left.

beyondhelp · « **Reply #72 on:** November 13, 2015, 04:04:51 am »

All done.

I'm shattered now! have fun with those (!) and I'll see how you got on in the morning! (4am here now!)

ataradov · « **Reply #73 on:** November 13, 2015, 04:14:20 am »

Here is an updated program in case anyone wants to play with it.

I'm going to try to turn that into an actual function, not just a table.

hamster_nz · « **Reply #74 on:** November 13, 2015, 05:01:39 am »

Here's the guts of the code that I have so far.

* The data goes through a 'mysterious transform'

* Then it calculates a standard CRC16, with 0x1021 for the polynomial constant (the same one used for EDID ROMs, as luck would have it...)

* Finally the CRC is XORed with 0x51A5

It gets everything but the LSB for all test vectors I have so far.

Very weird!

I guess this is as much help as I can offer - off to other projects

Mike

Code: [Select]

short int std_crc16(unsigned char *data, short unsigned length)
{
  int i;
  short unsigned crc = 0xFFFF;
  for(i = 0; i < length*8;  i++)
  {
    int mask, index,bit,wrap;
    mask = 0x80>>(i%8);
    index = i/8;
    bit = (data[index] & mask) ? 1 : 0;
    wrap = (crc & 0x8000) ? 1 : 0;
    crc <<= 1;
    if(wrap ^ bit) crc ^= 0x1021;
  }
  return crc;
}
void mystery_transform(unsigned char *data, short unsigned length)
{
  int i, j;
  unsigned char a = data[0]^data[1]^data[2]^data[3]^data[4];

/* Mystery transform */
  for(i = 0; i < 5; i++) {
    if((data[i] & 0x40)) {
      for(j=i+2; j <6 && j < i+5 ; j++)
         data[j] ^= 0x01;
    }
  }

  for(i = 0; i < 5; i++) {
    unsigned char b;
    b = data[i] >> 7;
    b ^= data[i] >> 3;
    if(b & 0x1) {
      for(j=i+1; j <6 && j < i+5; j++)
         data[j] ^= 0x01;
    }
  }

/* Double mystery transform (removes some of 00 01) */
  if(a & 0x20) {
    data[2] ^= 0x01;
    data[3] ^= 0x01;
    data[5] ^= 0x04;
  }

  if(a & 0x08) {
    data[2] ^= 0x01;
    data[3] ^= 0x01;
    data[5] ^= 0x04;
  }
}

short int my_crc(unsigned char *data, short unsigned length)
{
  int i;
  short unsigned crc = 0, crc_low, crc_high;

  for(i = 0; i < length; i++)
     printf("%02x ",data[i]);
  printf("=> ");

  mystery_transform(data,length);

  /* Display the transfomed data */
  for(i = 0; i < length; i++)
     printf("%02x ",data[i]);

  crc = std_crc16(data,length);
  crc ^=  0x51A5;
  crc_low  = (crc>>0)&0xFF;
  crc_high = (crc>>8)&0xFF;

  if( crc_low == data[i] && crc_high == data[i+1])
    printf(" => %02x %02x\r\n", data[i], data[i+1]);
  else
    printf(" => %02x %02x should be %02x %02x, error %02x %02x\r\n",
           crc_low, crc_high,
           data[i], data[i+1],
           crc_low^data[i], crc_high^data[i+1]);

  return 0;
}

ataradov · « **Reply #75 on:** November 13, 2015, 05:42:23 am »

Same code with correct endianness. It does not make much difference for a table method, but it is clearly a little endian CRC.

I'm making some progress on reversing this.

ataradov · « **Reply #76 on:** November 14, 2015, 08:06:33 am »

Just in case anyone is still interested in fully understanding this. Here is some new data.

Here is how input (47-0) bits affect output bits of the CRC (0-15). This is for a standard polynomial (0x1021).

Code: [Select]

0 :      *      * **   ***   * **      **  *   *   *   (15)
1 :     *      * **   ***   * **      **  *   *   *    (15)
2 :    *      * **   ***   * **      **  *   *   *     (15)
3 :   *      * **   ***   * **      **  *   *   *      (15)
4 :  *      * **   ***   * **      **  *   *   *       (15)
5 : *    * * ** *   *  * *** * ** **  *** **  **   *   (24)
6 :     * * ** *   *  * *** * ** **  *** **  **   *    (23)
7 :    * * ** *   *  * *** * ** **  *** **  **   *     (23)
8 :   * * ** *   *  * *** * ** **  *** **  **   *      (23)
9 :  * * ** *   *  * *** * ** **  *** **  **   *       (23)
10: * * ** *   *  * *** * ** **  *** **  **   *        (23)
11:  * ** *   *  * *** * ** **  *** **  **   *         (22)
12: * **     *      * **   ***   * **      **  *   *   (17)
13:  **     *      * **   ***   * **      **  *   *    (16)
14: **     *      * **   ***   * **      **  *   *     (16)
15: *     *      * **   ***   * **      **  *   *      (15)

Numbers at the end of the line are just count. So if intersection of the input bit and output bit has an asterisk, then presence of the input bit flips (xor operation) corresponding output bit.

And here is the same map for the algorithm in question:

Code: [Select]

0 :   ** **   * *  *   * *     **   *  *   *   *   *   (16)
1 :     *      * **   ***   * **      **  *   *   *    (15)
2 : ** **   * *  *   ***   * **      **  *   *   *     (18)
3 :   *      * **   ***   * **      **  *   *   *      (15)
4 :   *   *   **   **    * *    *  **  *   *   *       (14)
5 :   ** ***    * *    * ***   ** *** **  **  **   *   (23)
6 : *     * ** *   *  * *** * ** **  *** **  **   *    (23)
7 : ** *** *  * * *  * *** * ** **  *** **  **   *     (26)
8 :   * *  *   * *     **   *  *   *   *   *           (12)
9 :   ** *      *  *  ** * *  *** *** **  **   *       (20)
10: * *  * * * *  *  **   ** **  *** **  **   *        (21)
11: ** *  *   *  * *** * ** **  *** **  **   *         (22)
12:       *   *   *   **   **    * *    *  **  *   *   (14)
13:       *        *  *   **      **      **  *   *    (11)
14:     *  **   * * **   ***   * **      **  *   *     (17)
15:     * *      * **   ***   * **      **  *   *      (15)

As you can see they are similar, but things get complicated as you move towards highest bits (those represent first byte of the data, so they get shifted in first, so they affect the result in a most complicated way).

And here is a table with formal differences:

Code: [Select]

0 : 0cc4 ^ d420 = d8e4
1 : 0884 ^ 6a10 = 6294
2 : 0739 ^ 3508 = 3231
3 : 0aa5 ^ 1a84 = 1021
4 : c186 ^ 0d42 = ccc4
5 : 06a1 ^ 06a1 = 0000
6 : b871 ^ 8b40 = 3331
7 : 45a0 ^ 45a0 = 0000
8 : 4044 ^ 22d0 = 6294
9 : 0448 ^ 1168 = 1520
10: 1895 ^ 08b4 = 1021
11: 055a ^ 045a = 0100
12: 42a9 ^ 022d = 4084
13: 8906 ^ 8906 = 0000
14: 54a2 ^ 4483 = 1021
15: aa51 ^ aa51 = 0000
16: c818 ^ dd38 = 1520
17: 4c8c ^ 6e9c = 2210
18: 364e ^ 374e = 0100
19: 1ba7 ^ 1ba7 = 0000
20: 81c2 ^ 85c3 = 0401
21: caf1 ^ caf1 = 0000
22: ec68 ^ ed68 = 0100
23: 76b4 ^ 76b4 = 0000
24: 194a ^ 3b5a = 2210
25: 0c8c ^ 1dad = 1121
26: 86c6 ^ 86c6 = 0000
27: 4363 ^ 4363 = 0000
28: 8ab1 ^ a9a1 = 2310
29: dcc0 ^ dcc0 = 0000
30: 6e60 ^ 6e60 = 0000
31: 3730 ^ 3730 = 0000
32: 0ab9 ^ 1b98 = 1121
33: 0ccc ^ 0dcc = 0100
34: 06e6 ^ 06e6 = 0000
35: 0373 ^ 0373 = 0000
36: 9888 ^ 89a9 = 1121
37: ccc4 ^ ccc4 = 0000
38: 6662 ^ 6662 = 0000
39: 3331 ^ 3331 = 0000
40: 9088 ^ 9188 = 0100
41: 48c4 ^ 48c4 = 0000
42: 2462 ^ 2462 = 0000
43: 1231 ^ 1231 = 0000
44: 8008 ^ 8108 = 0100
45: 4084 ^ 4084 = 0000
46: 2042 ^ 2042 = 0000
47: 1021 ^ 1021 = 0000

So my conclusion is that there is no data pre-processing, but there are some minor changes in the CRC loop itself. So that data that comes in last affects the difference the least, but data that came in first, gets splattered all over the place.

So now the task is simplified. We just need to find a way to make that last list show 0's in all positions

beyondhelp · « **Reply #77 on:** November 14, 2015, 02:31:24 pm »

Quote from: hamster_nz on November 13, 2015, 05:01:39 am

I guess this is as much help as I can offer - off to other projects

Mike

Thanks for your time and input into this Mike. Much appreciated.

beyondhelp · « **Reply #78 on:** November 14, 2015, 02:33:25 pm »

Quote from: ataradov on November 14, 2015, 08:06:33 am

Just in case anyone is still interested in fully understanding this. Here is some new data.

I'm doing my best!! I'm going to read that again...

beyondhelp · « **Reply #79 on:** November 14, 2015, 02:41:40 pm »

Ok, I kind of get it!

I'm fearful of sound stupid, but am I right we now have enough information to generate the checksum via a lookup table and some code. So essentially in a non ideal way its cracked? As for calculating the exact code with which the checksum is calculated from we also know half of how the CRC may be being performed with a polynomial of 0x1021, but don't yet know how the CRC is being modified for the highest bits?

ataradov · « **Reply #80 on:** November 14, 2015, 07:10:01 pm »

Quote from: beyondhelp on November 14, 2015, 02:41:40 pm

So essentially in a non ideal way its cracked?

Yes, for any practical uses take my last code and take definitions for CS_ZERO, partial[] and calc_sum().

That's all you need. Somewhere in the beginning of your program (setup() in case of arduino) update the partials table:

Code: [Select]

  for (int i = 0; i < 6*8; i++)
    partial[i] ^= CS_ZERO;

You can precalculate this, of course.

After that you can call calc_sum() on any 6-byte array. It will return 2-byte check sum. Add those to bytes to the message and you will get 8 bytes of valid data.

Anything else is just pure fun of figuring stuff out, but you don't need to worry about that.

hamster_nz · « **Reply #81 on:** November 15, 2015, 01:53:08 am »

Based on ataradov's tables, here is the modified CRC function:

Code: [Select]

short int magic_crc16(unsigned char *data, short unsigned length, short unsigned initial)
{
  int i;
  short unsigned crc = 0xFFFF;
  for(i = 0; i < length*8;  i++)
  {
    int mask, index,bit,wrap;
    mask = 0x80>>(i%8);
    index = i/8;
    bit = (data[index] & mask) ? 1 : 0;
    wrap = (crc & 0x8000) ? 1 : 0;
    crc <<= 1;
    if((i&7)== 4) {
      if(wrap ^ bit) crc ^= 0x1001;
    } else {
      if(wrap ^ bit) crc ^= 0x1021;
    }
  }
  return crc;
}

It works for all of the 100 test cases that are in this thread...

JimRemington · « **Reply #82 on:** November 15, 2015, 02:02:14 am »

Cool! Any speculation on what the original programmer might have been thinking?

I spent some time trying to imagine a simple mistake or change in the inner loop of the standard CRC that would lead to such a pattern of bit flip differences, and decided that whatever it was, was not simple. Your exposition confirms that suspicion.

hamster_nz · « **Reply #83 on:** November 15, 2015, 02:15:12 am »

Quote from: JimRemington on November 15, 2015, 02:02:14 am

Cool! Any speculation on what the original programmer might have been thinking?

It's either a bug in an unrolled loop, or an attempt to thwart reverse engineering. Most likely the former than the latter, IMO.

ataradov · « **Reply #84 on:** November 15, 2015, 02:15:25 am »

Yep, that function yields no differences. And here is a more traditional form of CRC with this change:

Code: [Select]

uint16_t calc_crc(uint8_t *data)
{
  uint16_t crc = 0xffff;

  for (int i = 0; i < 6; i++) 
  {
    crc ^= (data[i] << 8);

    for (int j = 0; j < 8; j++)
    {
      if (crc & 0x8000)
      {
        if (4 == j)
          crc = (crc << 1) ^ 0x1001;
        else
          crc = (crc << 1) ^ 0x1021;
      }
      else
        crc = (crc << 1);
    }
  }

  return crc;
}

I don't see any benefit of doing this apart from obfuscation.

beyondhelp use this function instead.

hamster_nz · « **Reply #85 on:** November 15, 2015, 05:17:52 am »

Quote from: ataradov link=topic=58151.msg800597#msg800597 47553725

beyondhelp use this function instead.

Given that the target is a PIC 16Fsomething, it is most probably better to rewrite the code to the platform. The have limited and segmented RAM, lots of bit test operations and bit test and skip ops can be leveraged, but minimal support for anything like a pointer... they make an AVR look feature rich!

ataradov · « **Reply #86 on:** November 15, 2015, 05:20:21 am »

Quote from: hamster_nz on November 15, 2015, 05:17:52 am

Guven that the target is a PIC 16Fsomething,

The devices runs PIC, but PC part needs to be replaced from what I understand.

But yeah, optimize as needed, of course.

beyondhelp · « **Reply #87 on:** November 15, 2015, 04:06:48 pm »

It will be replaced depending on use with a software interface that will allow it to work in more recent OS,or/and with a more simple Amtel based physical hardware interface, most probably a ATMega256, because if I'm honest that's where my (limited) experience lies.

beyondhelp · « **Reply #88 on:** November 15, 2015, 05:21:13 pm »

Quote from: ataradov on November 15, 2015, 02:15:25 am

Yep, that function yields no differences. And here is a more traditional form of CRC with this change:
Code: [Select]
uint16_t calc_crc(uint8_t *data) { uint16_t crc = 0xffff; for (int i = 0; i < 6; i++) { crc ^= (data[i] << 8); for (int j = 0; j < 8; j++) { if (crc & 0x8000) { if (4 == j) crc = (crc << 1) ^ 0x1001; else crc = (crc << 1) ^ 0x1021; } else crc = (crc << 1); } } return crc; }
I don't see any benefit of doing this apart from obfuscation.

beyondhelp use this function instead.

Ok having a play now. From the code this replaces the previous code including the tables?

ataradov · « **Reply #89 on:** November 15, 2015, 07:57:27 pm »

Quote from: beyondhelp on November 15, 2015, 05:21:13 pm

From the code this replaces the previous code including the tables?

yes, that's the single function you need.

beyondhelp · « **Reply #90 on:** November 16, 2015, 04:33:13 am »

With a little help from hampster_nz, and ataradov's code, ITS WORKING

I know I'll be back with more questions, but so far for the test data I'm putting in, im getting out valid checksum data. Amazing!!

Honestly what can I say!! I'm blown away by the knowledge, skills and time put into this thread. Thanks so much!

matkar · « **Reply #91 on:** November 16, 2015, 07:57:21 am »

I followed this thread with great interest. I'm amazed by the skills you all have. I liked the way you draw conclusions and had a small epiphany at ataradov's reply #76. You can clearly see the pattern. Unbelievable!

Can you guys give us some insight on what tools are you using when dealing with such problems?
E.g. hamster_nz was half way there in reply #51 which facilitated the search of valid entries. Did you use a "plain" CRC calculation? How did you (almost) figured which polynome and seed is used?
@ataradov:How did you figured there is not some kind of pre or post processing but the CRC algorithm obfuscation instead?
How did you came to the first solution that uses tables? How did you guys derived the second solution using equations?

I really wish there were more threads like this. Thank you!

BravoV · « **Reply #92 on:** November 16, 2015, 07:59:50 am »

Quote from: matkar on November 16, 2015, 07:57:21 am

I really wish there were more threads like this. Thank you!

+1 , thanks to all who contributed.

Imo, this thread prolly one of the best thread of the month around this forum currently.

ataradov · « **Reply #93 on:** November 16, 2015, 08:07:29 am »

Quote from: matkar on November 16, 2015, 07:57:21 am

E.g. hamster_nz was half way there in reply #51 which facilitated the search of valid entries.

It is quite obvious, since first 3 (or last 3, depending on where you count from) entries are consistent with a standard 0xffff / 0x1021 CRC-16.

Quote from: matkar on November 16, 2015, 07:57:21 am

@ataradov:How did you figured there is not some kind of pre or post processing but the CRC algorithm obfuscation instead?

Same reason, if you look at the progression in the change of the value, you will see that if the bit containing "1" is shifted at the beginning, then CRC is result is barely predictable. But if the "1" bit is shifted in at the end, then changes are very predictable and for the last 3 values match with the standard CRC.

Quote from: matkar on November 16, 2015, 07:57:21 am

How did you came to the first solution that uses tables?

Just knowledge of this property for block codes. I don't know where it came from, probably some university course.

Quote from: matkar on November 16, 2015, 07:57:21 am

How did you guys derived the second solution using equations?

Trying things and looking at the results.

hamster_nz · « **Reply #94 on:** November 16, 2015, 09:50:42 am »

Quote from: matkar on November 16, 2015, 07:57:21 am

I followed this thread with great interest. I'm amazed by the skills you all have. I liked the way you draw conclusions and had a small epiphany at ataradov's reply #76. You can clearly see the pattern. Unbelievable!

Can you guys give us some insight on what tools are you using when dealing with such problems?

I've been doing a few projects that are loosely aligned to CRCs lately. They turn up quite a bit in hardware. LFSRs, CRCs, BCH codes are all somewhat related. CRC16 is used in the physical layer of SD cards for verifying block data transfers, and it is also used in SDI video where the checksum of each raster is sent following the active video data. So I had a C implementation handy, for verifying against my VHDL code. (I mistakenly said a monitor's EDID ROM. but I just checked and that is a simple checksum....).

Quote from: matkar on November 16, 2015, 07:57:21 am

E.g. hamster_nz was half way there in reply #51 which facilitated the search of valid entries. Did you use a "plain" CRC calculation? How did you (almost) figured which polynome and seed is used?

beyondhelp did an awesome job of collecting the data, and included quite a few pairs of messages that differed by one bit, especially the status message with the counters that increment by one.

The checksums for the pairs differed by a consistent amount when bits when the same bits changed, regardless of the rest of the message. On top of that when the neighboring bits changed the difference was the same pattern rotated one bit. That is expected for a CRC, where it is a rotate and then XOR by a constant amount. So I just ran some patterns through the CRC16 code, and rather than just getting unrelated numbers (which would be expected if the polynomial was different) the errors looked somehow related.

With a bit of fiddling I could get most of the changes to sort of agree, and with a bit of hacking I managed to get it close enough that I would take a guesses at what each bit's effect on the checksum would be. My 'mystery transform' was propagating the then-unknown change made to the polynomial through the input data. My bad

Quote

How did you guys derived the second solution using equations?

I had decided to move on to other things, but when I saw ataradov's tables it nagged at me . I just printed it out, turned it on it's side and highlighted the differences.

Code: [Select]

FEDCBA9876543210
 44 other lines
x......O....x...
.x......x....x..
..x......x....x.
...x......x....x

Then undid the rotation step:

Code: [Select]

FEDCBA9876543210
 44 other lines
...x...........x  0x1001
...x......x....x  0x1021
...x......x....x  0x1021
...x......x....x  0x1021

So I plugged 0x1001 as the polynomial constant used on the third-to-last bit, and everything worked out back to the 11th to last bit. I plugged 0x1001 in for the 12th-to-last bit, and that worked too.

Then I just tried the two most common initial values (all zeros or all ones), half expecting to do an exhaustive search, and 0xFFFF just worked.

Quote

I really wish there were more threads like this. Thank you!

A big thanks should go to beyondhelp giving us such a fun problem. Much more fun than doing Sudoku in the wife's Women's Day

I pinged him a message this afternoon and helped him with his Arduino/C testing code, but I still forgot to ask him/her what the end device actually does!

android · « **Reply #95 on:** November 16, 2015, 11:36:23 am »

Quote

I still forgot to ask him/her what the end device actually does!

...just some kind of missile launch control system, I think

beyondhelp · « **Reply #96 on:** November 16, 2015, 07:16:50 pm »

Quite agree, this thread has been EPIC!! So glad that others have found it as fascinating as I have

Gotta love the EE community

Quote from: android on November 16, 2015, 11:36:23 am

Quote
I still forgot to ask him/her what the end device actually does!
...just some kind of missile launch control system, I think

Incredibly close!!!! Not going to name it, but it is for the use of pyrotechnics for entertainment purposes!! It was either get this working or ultimately ditch and replace with something else!

abyrvalg · « **Reply #97 on:** November 19, 2015, 09:24:08 am »

Lots of fun here! For completeness I would like to extract the original algo and post it here for comparison. beyondhelp, would you mind sending me an original executable that talks to this hardware? IDA is my girlfriend

rs20 · « **Reply #98 on:** November 19, 2015, 09:29:16 am »

I just finished reading The Da Vinci Code; parts of this thread have a similar vibe...

beyondhelp · « **Reply #99 on:** November 23, 2015, 12:48:35 pm »

Quote from: abyrvalg on November 19, 2015, 09:24:08 am

Lots of fun here! For completeness I would like to extract the original algo and post it here for comparison. beyondhelp, would you mind sending me an original executable that talks to this hardware? IDA is my girlfriend

I'll see what I can do

Only runs on XP however. Even in a VM it crashes...


EEVblog Main Site	EEVblog on Youtube	EEVblog on Twitter	EEVblog on Facebook	EEVblog on Odysee