CRC's..Checksums.. Reverse Engineering!

[Tazzi]

Iv entered the world of CRCs, I see there not "too strong" of a data validation source from what some experts have mentioned.. but still enough to give someone a headache from messing around with them too much!

Iv readup on some good documents.. namely:
http://webcache.googleusercontent.com/s ... clnk&gl=au
http://www.woodmann.com/fravia/crctut1.htm
http://stackoverflow.com/questions/4012 ... pplication
http://www.cosc.canterbury.ac.nz/greg.e ... ering.html
http://blog.affien.com/archives/2005/07 ... rsing-crc/
http://stigge.org/martin/pub/SAR-PR-2006-05.pdf

The fourth source is quite interesting, I was trying to follow his working to optain the polynomial but I just dont understand what operations he does to what to obtain it. Looks simply but Im lost where he says "shift-xor", to which I dont kow if I only shift one of the bytes, or both and which who xor's the other.

I made a simple CRC16 bruteforcer, iv tested it on live examples on the web and works a treat! Although these are typically 2-50bytes. Whereas Im dealing with something like 10000bytes thus its taking a LOT longer. Even so, there are a few alterations to the CRC that can be done.. that I am a little confused about such as reflecting in/out.. which I assume is just flip the bits before and after the CRC calc.

bruteforcecrc.PNG (14.1 KiB) Viewed 14525 times

Anyways, why sooo much interest? Im looking at the E38 bins and am interested in working out the CRC16 checksums.

Ill chuck up a couple bins with the relevant data in a sec if anyone wants to tinker with this as well? Note that any byte changed inside this data modifies the checksums. All other bytes outside of this range do not affect them. Im 100% sure on this.

[Tazzi]

Attached two bins, which 1 byte difference causing changes to the two checksums at the beginning (all bytes before the first checksum have been discarded as there are irrelevant to this section!). A quick "bin compare" will highlight these changes.!

[Tazzi]

I think Im slowly frying my brain, but.. I understand the example to decipher the polynomial value. Sooo Say we have these two sets of values an corresponding CRCs (CRC red):

00 08 B2DF (Call this C1)

00 10 25BD (Call this C2)

There is a different of 1bits between these two messages. Thus, by definition, we should be able to shift C1 by 1 right and then XOR is with C2 to get the polynomial..

Soooo:
25BD shift 1bit right = 12DE
Then XOR with B2DF = A001

Bingo! Thats the correct polynomial for that CRC16..

To confirm this, move onto the next sequence of this test CRC
00 04 F96E

Thus:
B2DF shift 1 bit right = 596F
Then XOR with F96E = A001


Sooo now to apply this to our situation. Again, I am assuming that this is a CRC16.. but there are two of them.. and Im wondering if Im really dealing with a CRC32 but split into two 16bit bytes

[Tazzi]

Didnt have much luck here using the above. Although it could be I need to swap the bytes before/after to getting a constant polynomial happening. Might need to shift the bits the opposite direction as well.

I was thinking about why there is two CRC's.
I originally thought it was due to one of the checksums does the CRC for all the data below it, and the other does all the data below it plus the other CRC.

But after some testing, modifying the bytes between the two checksums still results in both changing. It could very well be that the 2nd checksum does do a CRC utilizing all the bytes. Then the 1st checksum does a full CRC including the 2nd checksum. But I dunno!


Alternatively, it could be a CRC32. I had a tinker with combining the two CRCs. Although didnt manage to work the CRC backwards using the same mathematics as above.


Brute forcing does look like it could work. I attempted to use some available bruteforcers.. but (Of course) they dont seem to allow for the amount of bytes we need so its a "DIY" situation and have to implement out own application.
There are only a few unknowns that need to be sorted. This is the "initial value" which is normally 0x0000 or 0xFFFF (I need to try these first), the "Polynomial" which is the value that is Xor'd with. Typcial values are 0xA001 and 0X8001, ReverseIN and ReverseOUT

Code: Select all

 Public Function CRC16CalcNormal(ByVal Data() As Byte, ByVal Polynomial As UInt16, ByVal StartValue As UInt16) As UInt16
        Dim CRC As UShort = StartValue '&HFFFF
        Dim Poly As UShort = Polynomial '&HA001
        For I As Integer = 0 To Data.Length - 1
            CRC = CRC Xor Data(I)
            For i As integer = 0 To 7
                If CRC And 1 Then
                    CRC = (CRC >> 1) Xor Poly
                Else
                    CRC >>= 1
                End If
            Next
        Next
        Return CRC
    End Function

There are some "alternatives" to the standard CRC16. Iv only coded up a working standard CRC16 algo. I still need to implement a reverseIN and reverseOUT function in the algo. Which essentially just swaps the bytes before performing the CRC and after performing the CRC.
The other algos Im a little unsure of what they are doing exactly, different polynomials? or flipping bytes?.. Will need to scout of for some pe-made functions to understand it.

[Tazzi]

Alright progress!

Looks like CRC number two validates the first one possibly? or vise versa. Either way.. I didnt think do do something as simple as this from the beginning.

In the original bin,
Checksum1 = 3114
Checksum2 = E3A6
Ck1+Ck = 3114+E3A6 = 114BA

In the next bin changed by 1 bytes,
Checksum1 = 6EAD
Checksum2 = A60C
Ck1+Ck = 6EAD+A60C = 114B9

And the difference is 114BA-114B9 = 1

Sooo.. these are linked in some way... Increasing by X amount of bytes causes a decrease in the added up sums by X amoutn. But difference between the two checksums is inconsistent.

Hmmm..

[antus]

There should not be a relationship between the two CRCs as the point of CRCs is that a 1 bit change will change the sum completely, thus any relationship along those lines cant continue to exist across differing data sets. Unless one is an inverted copy of the other. If thats the case it might help to look at it in binary.

The polynomials will more than likely be the most common standards.

http://en.wikipedia.org/wiki/Cyclic_redundancy_check

That is CRC-16-CCITT (0x1021) or CRC-32 (0x04C11DB7)

[Tazzi]

There should not be a relationship between the two CRCs as the point of CRCs is that a 1 bit change will change the sum completely, thus any relationship along those lines cant continue to exist across differing data sets. Unless one is an inverted copy of the other. If thats the case it might help to look at it in binary.

The polynomials will more than likely be the most common standards.

http://en.wikipedia.org/wiki/Cyclic_redundancy_check

That is CRC-16-CCITT (0x1021) or CRC-32 (0x04C11DB7)

Yeah I figured that as well. But the changes between all changes, even by 1, are absolutely massive with what seems to be no common pattern occuring!
So I figured it must be using CRC. And one of them must be a reflection of the other +- the change that has occured.

But then that doesnt fit with what we are observing above. The two checksums change widley, but yet they can be added together to end up "X" different on the next bin change by X amount.

It cant be CRC32 otherwise the above wouldnt occur again.

hmm.. will have to pull all the checksums out and display that as binary.. I do think that might help out

[Tazzi]

Alright bare with me here..Im gonna get this out my head before I start mixing things up.

What if Checksum1 is the "total" CRC16 checksum. And then Checksum2 is something as simple as "(FFFF - Checksum1)+ 2'scompliment"
It would make sense how the Checksums can vary so much.. but them once added they come back together.. I think Im onto something there!

Im thinking.. because the bins only increase by "1" each time I change something by "1". I believe the entire contents of that section are added up as a 16bit byte then added to checksum2.

In saying this.. this means checksum1 is calculated first before checksum2. But, it could be vise versa, and checksum2 could be the CRC and checksum1 could be the final verification

[antus]

I have been thinking about this. I think you may be looking at the CVN, rather than a CRC. The CVNs are 16 bit, but the CRCs are 32bit. Do you not see any 32 bit changes on edit?

[Tazzi]

I have been thinking about this. I think you may be looking at the CVN, rather than a CRC. The CVNs are 16 bit, but the CRCs are 32bit. Do you not see any 32 bit changes on edit?

Nope, theres only two 16bit changes.

One of which is the CVN like you said. And the other is the checksum. Although it looks like they display the CVN and Checksum together as a 32bit byte checksum.

I checked through the bins, and the CVN value only occurs once so it is definitively one of the checksums.

Iv also verified that there is only there two checksum changes for this section as the files could be successfully flashed back after changing only 1 byte.