Reversing simple message + checksum pairs (32 bytes)

Question

I am trying to determine the algorithm behind a 32-byte protected section of memory on a big-endian system. It will render invalid if even a single bit is changed, but I can generate any number of valid 32-byte messages.

Here shows a variety of example data. I believe the last 4 bytes are the checksum. All of them are accepted by the algorithm.

00000000000000000000000000000000000000000007478A000101004892B760
F0000000000000000000000000000000000000000002D8DF00010100C9E23610
3065C0000000000000000000000000000000000000006F850001010060EB9F07
FFFFFFFF03FC6BBD000000000000000000000000000000000001010070B88F3A
FFFFFFFF0397E33D340C804138458C5006060968570C214B0001017AE8F416FE

I was able to create a bunch of custom messages with very little differences. Doesn't seem like it could be a CRC-32.

FFFFFFFF01671F7E000000000000000000000000000000000001010021E4DE0E (00)
FFFFFFFF01671F84000000000000000000000000000000000001010021EADE08 (01)
FFFFFFFF01671F88000000000000000000000000000000000001010021EEDE04 (02)
FFFFFFFF01671F86000000000000000000000000000000000001010021ECDE06 (03)
FFFFFFFF01671F8C000000000000000000000000000000000001010021F2DE00 (04)
FFFFFFFF01671F8A000000000000000000000000000000000001010021F0DE02 (05)
FFFFFFFF01671F86000000000000000000000000000000000001010021ECDE06 (06)
FFFFFFFF01671F8C000000000000000000000000000000000001010021F2DE00 (07)
FFFFFFFF01671F90000000000000000000000000000000000001010021F6DDFC (08)

All of the input bytes are the same, except one byte that increases by 1 in each message.

Here is a list of 50 or so pairs.

Basically, are there any analysis methods that can be applied to a set of data to determine some properties of the algorithm? I can generate any number of these messages, and verify that they are accepted.

Edit: By shifting a single bit, I noticed that 0x04 was added to two bytes, but subtracted to another (F84 -> F88, 1EA -> 1EE, E08 -> E04). After some experimentation (Mainly adding and subtracting different values and testing them) I was lucky that it turned out to be a summation of the fourteen preceding 16-bit words. AND-masking the sum by 0xFFFF, this value equals 15th word (e.g. 21EA in the first message). This value is then subtracted from 0xFFF2 to produce the 16th word in the message.

FFFFFFFF01671F84000000000000000000000000000000000001010021EADE08
FFFFFFFF01671F88000000000000000000000000000000000001010021EEDE04

Answer 1

Some of the samples inputs shown differ only in the value of the sixteenth nibble; let 's(X)' stand for such an input with value X at that nibble:

s(4): FFFFFFFF01671F840000000000000000000000000000000000010100 21EADE08
s(6): FFFFFFFF01671F860000000000000000000000000000000000010100 21ECDE06
s(8): FFFFFFFF01671F880000000000000000000000000000000000010100 21EEDE04
s(A): FFFFFFFF01671F8A0000000000000000000000000000000000010100 21F0DE02
s(C): FFFFFFFF01671F8C0000000000000000000000000000000000010100 21F2DE00

In a similar vein, let 'o(Y)' stand for the bit string consisting entirely of zeroes except for value Y at the sixteenth nibble.

Now, let's confront the XOR (bit difference) of certain inputs and the XOR of the corresponding checksums as MSB-first bitstrings:

s(4) ^ s(6) = o(2), cksum delta: .............**.............***.
s(8) ^ s(A) = o(2), cksum delta: ...........****..............**.
s(8) ^ s(C) = o(4), cksum delta: ...........***...............*..
s(4) ^ s(C) = o(8), cksum delta: ...........**...............*...

The lowest set bit of the checksum differences is equal to the bit where the inputs differ, and there is a matching difference exactly sixteen bits higher. The bursts of set bits could be due to bubbling carries.

For comparison, here are the XOR differences between the corresponding CRC32 values:

s(4) ^ s(6) = o(2), crc32 delta: .*****.*.......***...*..***..*..
s(8) ^ s(A) = o(2), crc32 delta: .*****.*.......***...*..***..*..
s(8) ^ s(C) = o(4), crc32 delta: *.***.**.....*..*****..*...*..*.
s(4) ^ s(C) = o(8), crc32 delta: .***.**.....*..*****..*...*..*.*

The structure of the changes is completely different and much more complicated. Note the CRC difference for inputs that differ in the same bit (first two lines), and the density of the differences which approaches the theoretical 50%. This is because CRCs have much better diffusion (avalance effect) than simple, empirical checksums.

And now the picture for a hash with near-perfect diffusion (the murmur hash mixer function):

s(4) ^ s(6) = o(2), murmur delta: ..*..*.....**.**..*..*....**..**
s(8) ^ s(A) = o(2), murmur delta: .*.*.*.*.*..*..*.*.*.*.**.*.*.*.
s(8) ^ s(C) = o(4), murmur delta: ..****.*****.******.**.**.******
s(4) ^ s(C) = o(8), murmur delta: .***...***.**...*.*....**.*.**.*

It is easy to get a feel for the structure of a checksum by observing these differentials for increasingly complex functions: sum, xor, xorshift, some classical hashes.

Then turn the spotlight on your target function. Observe output differences for some fixed inputs, letting single bit flip wander through the string. Observe output differences for single-bit differences at certain fixed positions for a series of different inputs. Let the difference position hop in increments of 8 bits, observe the behaviour. Then try 32-bit hops, observe. If possible, focus initial investigation on the last 32 bits of the input, since their relation to the output is bound to be a lot simpler than that for bits that went through more iterations... The structure of the hash function cannot hide itself from you for long.

That was a look at xor differentials. Depending on the hypothesised structure of the checksum, other experiments are possible. As a real-life example, a few years back I had to deduce various check digit algorithms (similar in nature to the ISBN check digit algorithm) based on sample batches of (mostly) correct specimens. Since these algorithms are based on multiplying digits with certain position-dependent weights, I searched for pairs of numbers that differed only in one single digit apart from the checksum. By fixing certain hypotheses regarding how the sum is turned into a check digit, this allowed my to deduce the weight (1, 2, 3, 4...) for each digit and to identify the correct hypothesis for the sum.

In the case under consideration it is certainly suggestive that the sixteenth nibble and the final nibble of the checksum sum to 12 (0x0C), for the five samples that I used here.

So, the basic idea is to confront input differences with output differences, modulated by one's suspicion regarding the structure of the function that needs to be inferred. Things can get very tricky if sample pairs with minimal differences are scarce. Conversely, if you can produce samples at will (chosen-plaintext attack) then things are looking very good indeed...