6

I have a device at work with no documentation about it's checksum calculation. I know that the last byte in each message is the checksum, and most of the messages to the device requires a correct checksum.

I thought it was easy to figure out, probably some CRC or something, but i really can't figure this out.

I have some messages (from the device) with only one of the bytes changing to make it easier to find a pattern.

The last byte in each message is the Checksum.

The second last byte increments in theese messages:

00h 5Ch A2h 00h 04h D2h 38h
00h 5Ch A2h 00h 04h 57h BDh
00h 5Ch A2h 00h 08h AEh 1Ch
00h 5Ch A2h 00h 00h 01h 7Fh
00h 5Ch A2h 00h 00h 02h 80h
00h 5Ch A2h 00h 00h 03h 81h
00h 5Ch A2h 00h 00h 04h 82h
00h 5Ch A2h 00h 27h 0Fh BCh

The 4th byte increments in those:

00h 5Ch A2h 00h 00h 01h 7Fh
00h 5Ch A2h 01h 00h 01h 63h
00h 5Ch A2h 02h 00h 01h 67h
00h 5Ch A2h 03h 00h 01h 6Bh 
00h 5Ch A2h 04h 00h 01h 6Fh

I hope someone out there can help, its really a showstopper for me.

EDIT - added some more examples

00h 5Ch A2h 01h 01h 01h 65h
00h 5Ch A2h 01h 01h 02h 66h
00h 5Ch A2h 01h 01h 03h 67h
00h 5Ch A2h 01h 01h 04h 68h

00h 5Ch A2h 01h 01h 01h 65h
00h 5Ch A2h 01h 01h 02h 66h
00h 5Ch A2h 01h 01h 03h 67h
00h 5Ch A2h 01h 01h 04h 68h
00h 5Ch A2h 02h 01h 01h 69h
00h 5Ch A2h 02h 01h 02h 6Ah
00h 5Ch A2h 02h 01h 03h 6Bh

One more example of the same message where the last 3 bytes are 00h:

00h 5Ch A2h 00h 00h 00h 7Eh

2nd EDIT- Added a Pastebin link to a ton of other samples, all of the same message type

Its a different message but there is a lot of samples: Lots of sample messages in Pastebin

  • Do you have more samples? – cimarron Jan 20 '16 at 16:30
  • Hey @cimarron i just added some more examples. – Jesper R Jan 21 '16 at 7:12
  • This expression works for all samples except one: 0x7e + d[5] + 2*d[4] + 4*d[3] - (d[3] + d[4] == 0 ? 0 : 0x20) (d[0..5] being the data). If you can get more samples like the failing one, or samples that vary the first three bytes, you can probably refine it further. – hemflit Jan 21 '16 at 22:34
  • @hemflit , interesting, thanks for your time! Im looking at it right now, and i will post more samples of another message later. – Jesper R Jan 22 '16 at 8:44
7

The key is getting getting a megaton of samples, so that the analysis has something to feed on. It really helps if you can stick the samples in a database table or dictionary that can be queried interactively, e.g. from some sort of script shell. Python should work admirably but I don't have much experience with it, as I've been using Visual FoxPro for interactive spelunking these last two decades.

Once you have your samples ready to be queried you can test various simple hypotheses and disprove them by finding counterexamples. For example, the following samples seem to suggest that a difference in the fourth byte causes a quadruple difference in the checksum:

00h 5Ch A2h 00h 00h 01h 7Fh
00h 5Ch A2h 01h 00h 01h 63h
00h 5Ch A2h 02h 00h 01h 67h
00h 5Ch A2h 03h 00h 01h 6Bh 
00h 5Ch A2h 04h 00h 01h 6Fh

The key is finding samples that differ only in the current 'working' column and the checksum, to study the effect which a change in the working column has on the checksum. For example, given the input above we could note down 4 * b[3] as preliminary term for the fourth byte, and then query the sample database for counterexamples were this doesn't work. That is to say, you select pairs of samples that differ only in the fourth byte and the checksum and count the number of successes and failures for

delta(checksum) mod 256 == 4 * delta(byte[3]) mod 256.

That's the idea, anyway. What a thing like delta(checksum) mod 256 actually looks like depends on your script shell, obviously. With VFP it would be

mod(256 + asc(substr(right, 7, 1)) - asc(substr(left, 7, 1)), 256)

The complete expression for the test above would be rather long, so you'd normally write little helper functions. With a helper named byte_delta() that normalises its result to the range [0, 255] you might have

select le.sample as left, ri.sample as right ;
   from all_samples le, all_samples ri ;
   where stuff(left(ri.sample, 6), 4, 1, "") == stuff(left(le.sample, 6), 4, 1, "") ;
      and le.sample <> ri.sample ;
   into cursor byte_3_pairs

select byte_delta(right, left, 7) == mod(4 * byte_delta(right, left, 4), 256) as ok, count(*) ;
   from byte_3_pairs ;
   group by 1

In the case under consideration you'd get a mixed picture for this query (see difference between first and second sample above, which is E4 instead of 4). Normally you'd do a fair bit of selecting differences first, just to get a feel for things. 'Difference' could be arithmetic difference, bitwise xor, whatever.

That's why you need an interactive shell like Python or VFP; with the edit-compile-run cycles of a compiled language this would be rather cumbersome. I've given the VFP examples because scripting languages with database support can make things a lot easier here.

For simple weighted sums like the usual 'human-computable' checksums in things like ISBNs this gives fairly quick results. I've used this approach to determine all the check digit schemes used in German health insurance numbers - which are mostly undocumented (or at least were, at the time) - from varying amounts of samples. Of course, in that case I had the advantage that the basic type of scheme - a weighted sum of digits - was known, and the samples were already residing in database tables...

The case under discussion is more difficult because the basic scheme is not yet known. That's why it is important to look at the bit patterns to get a feel for things. For example, bubbling carries indicate an additive function. This is explained in more detail in the topic Reversing simple message + checksum pairs (32 bytes), which also shows a few change pattern examples.

P.S.: besides trying to tease out checksum differences for changes in specific bits or bytes, there are lots of other things that can be done when the samples have been stuffed into some sort of queryable table/dictionary/map. The first thing is usually to run a battery of tests with existing standard functions, like straight byte sum, straight byte xor, various CRCs and so on, to observe the difference (arithmetic and xor) to the checksum. Displaying results as bit patterns - as shown in the linked article - can often be helpful for discerning regularities that are not so obvious in hexadecimal or decimal format.

UPDATE At the moment the samples are too similar (no differences in the first three bytes) and there's too few of them for discarding hypotheses quickly. In other words, there are just too many potential functions that would fit the existing data...

For example, the following simple Fox function correctly predicts the checksum for the original handful of samples, except for a few cases where it is off by 0x20:

function f (s)

   local x, i

   x = 0
   for i = 1 to len(m.s) - 1
      x = bitand(bitlshift(m.x, 1) + asc(substr(m.s, m.i, 1)), 0xFF)
   next i

   return bitand(m.x + 0x8E, 0xFF)

That could be because it's a rotation instead of a shift, or some xor is involved, or some other shift (relatively prime to 8) that overlaps with the bitcount per byte to create a distance of two bits between the fourth byte and the checksum. A rotation by 5 would do that. However, there are a lot of other possibilities... That's why we need lots more samples. ;-)

Analysing the samples on PasteBin shows that a difference in the last byte position before the checksum is always equal to the difference in the checksum. This means that the last byte and its effect on the checksum can be removed from the sample base. This increases the number of samples that differ in just one byte position, which means there's more low-hanging fruit for analysis...

E.g. the samples

00 5C A0 00 00 00 00 00 06 00:69
00 5C A0 00 00 00 00 00 06 01:6A
...
00 5C A0 00 00 00 00 00 06 FF:68

all map to the new sample (the dot indicates a removed byte, just for the sake of exposition here):

00 5C A0 00 00 00 00 00 06 . 69

The shortened sample base immediately shows cases where the 'power of two' rule does not work (the last byte here is originally the second last):

00 5C A0 00 00 00 00 00 00 . 7D
00 5C A0 00 00 00 00 00 01 . 7F
00 5C A0 00 00 00 00 00 02 . 61  <- difference -0x20 to predicted delta 2
00 5C A0 00 00 00 00 00 03 . 63
00 5C A0 00 00 00 00 00 04 . 65
...
00 5C A0 00 00 00 07 00 00 . B5 
00 5C A0 00 00 00 08 00 00 . BD
00 5C A0 00 00 00 09 00 00 . A5  <- difference -0x20 to predicted delta 8
00 5C A0 00 00 00 0A 00 00 . AD
00 5C A0 00 00 00 0B 00 00 . D5  <- back on track with the earlier sequence
  • Hey @DarthGizka, first and foremost i want to say I appreciate your detailed answer. Have you had any success reverese engineering a checksum with the approach you are describing above? I think i will give it a try tomorrow with your approach - Im good at Python so that might be me choice then. I guess i need much more samples which varies in length as well. I leave the question open for a few more days, but if i get the checksum right tommorow i will accept your answer though - Thanks again!! – Jesper R Jan 21 '16 at 19:50
  • @Jesper: I'd love to get cracking on this myself, but unfortunately I have to use my spare time for reverse-engineering a stinking heap of legacy code at the moment (VFP; it's so bad that is easier to understand after compiling it and decompiling the object code). However, if you have difficulty getting into things and somehow a link to a nice fat bunch of samples on a place like PasteBin should appear tomorrow, then I'm sure that I - and quite a few others here - would be unable to resist. ;-) Also, it would be nice if a Python guru could chip in with helpful hints... – DarthGizka Jan 21 '16 at 20:53
  • That sounds cool, or not :).. I haven't used VFP, in fact I haven't even heard about it before. Im trying to solve it now, but i will post a link to a bunch of samples later at PasteBin as you suggested. I really appreciate your input! Feel free to ever ask me Python stuff, I will do my best to answer,. Though i haven't any experience in reverse engineering with Python. – Jesper R Jan 22 '16 at 9:01
  • 1
    I edited the question to now include a Pastebin link as you suggested with a long list of samples. It is a different message. I think the 00 in the beginning of the message can be omitted, but bear in mind that it maybe have be in front of the samples provided in the Pastebin – Jesper R Jan 22 '16 at 11:49
  • 1
    Thanks, thats a lot better already! This confirms that - for the most part - the difference in a certain byte position is equal to the power of two that corresponds to the distance to the end, which is indicative of summing with left shift by one bit (as shown in the sample Fox function in my article). The important thing now is to find out the gory details, which requires mining the samples for pairs where the difference is not equal to the expected power of two (the famous 0x20 difference from my example or hemflit's formula). And mining for gold dust requires huge heaps of ore... ;-) – DarthGizka Jan 22 '16 at 13:29
0

I am wondering if you had made more progress on your checksum decoding. I have a very similar problem and i think your method may also works for my case. These are my data that I want to figure out the checksum method, which was long lost in earlier development:

00 8a 51 0b a0 b8 a1 00 8a 51 0b a1 b8 a3 00 8a 51 0b a2 b8 23 00 8a 51 0b a3 b8 25 00 8a 51 0b a4 b8 a3 00 8a 51 0b a5 b8 a5 00 8a 51 0b a6 b8 25 00 8a 51 0b a7 b8 27

Greatly appreciate if you can discuss more on your progress which may contribute to solving this one. Also, I found out I can swap nibble and it has the same checksum as well. thank you in advanced.

  • Sorry the data is all messed up: [00 8a 51 0b a0 b8 a1] [00 8a 51 0b a1 b8 a3] [00 8a 51 0b a2 b8 23] [00 8a 51 0b a3 b8 25] [00 8a 51 0b a4 b8 a3] [ 00 8a 51 0b a5 b8 a5] [00 8a 51 0b a6 b8 25] [00 8a 51 0b a7 b8 27] In general, on bit difference in the 5th bytes affect the last byte of checksum. – user14656 Feb 11 '16 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.