CRC cracking competition - first with working code wins FPGA

Hello everyone, I have been toying with a project that requires me to figure out the CRC method used by a hardware designer long ago. Their implementation is from the mid 90’s and is implemented within an ASIC. I have tried various methods using both software, and hardware to consistently come out to the same CRC values… to no avail. I am at my wits end, however I can submit several “packets” of data along with their correct CRC values. (This is an embedded system with data that is used internally therefore “packet” may not be the most accurate term.) There is little to no information about this system, however I did find one document that states all ASICs are using the CCITT polynomial. (Which I have been making the assumption is 0x1021.)

CRC-16

HINTS:

0x0011 – Begin New Frame
0x0012 – End of packet / new packet
0x0013 – CRC is next 2 bytes
0x0014 – End of Frame
0x0015 – ? used but why is unknown, when followed by 0x0013 it gives CRC 0xC7A4
0x0016 – ? used but why is unknown, when followed by 0x0013 it gives CRC 0xEDCC

From what I can gather from the data packets the above values are commands. Every other byte is a command in the data files and It seems the system only actually listens to the 4 lowest bits in the command bytes. Data is zero every time there is a command to be sent, and data is input in 8-bits parallel, therefore I have been unable to determine if the ASIC is processing the bytes in MSB or LSB order.

All files attached have the extension TXT however they are Binary files! They must be opened with a hex editor.

If there is someone on this forum that can help with this I am willing to donate a Spartan-6 LX9 FPGA as a thankyou for your assistance.

command15.txt (11 Bytes)

command16.txt (11 Bytes)

fr1.txt (78 Bytes)

fr2.txt (78 Bytes)

fr4.txt (78 Bytes)

fr5.txt (20.3 KB)

You have not really given enough information for someone else to have much hope in deducing the CRC method.

For example, over which bytes do you think the CRC is calculated? What do you mean by "end of frame" versus "end of packet"? Is there some significance to a "frame"? I don't understand your comments about data versus commands. Please provide some examples. If 0x10 is a command, what does it do?

Suggest you post a single text file with some complete example messages in ASCII hex format (the more the better). Example.

I've had good luck using the program reveng to reverse engineer CRC calculations.

The number of bytes prior to the CRC that are part of the calculation is also unknown. Assuming you use a single message such as (fr1.txt ) you would only have the previous 32 bytes. So anything between the command 0x0011 and 0x0013 would be my best guess.

I have been calling it “end of frame” but it may be more appropriate to call it “end of transmission” before a completely new sequence begins. At the bottom of this post I can upload the above files with their hex data as ASCII as well as a chart of what I think I know so far about the protocol.

I have tried reveng to reverse engineer the CRC, as well as writing several C++ programs and cant seem to find a pattern that is consistent with all the messages. Im not sure if I have to many bytes included, or if there was an issue with my implementation. I have also been using PyCRC to no avail.

I will also upload a copy of fr1.txt that is annotated (fr1-annotated.txt) so everyone can see what I am calling “commands”. As well as my complete breakdown of the “header”. (Since the beginning of every frame seems to have some permutation of this string of data.)

NOTE: fr5 is an example of multiple “packets” within a transmission, see the annotated documents for further details

command15.txt (34 Bytes)

command16.txt (34 Bytes)

fr1.txt (234 Bytes)

fr2.txt (235 Bytes)

fr4.txt (235 Bytes)

fr5.txt (61 KB)

Forgot to add fr1-annotated.txt and Frame illustrations:

fr1-annotated.txt (1.67 KB)

header.jpg

multiple.jpg

I see what you mean about command15 and command16. If we assume that 0x10 means “accept next data byte”, then only zeros for data lead to different (assumed) CRC values in those two cases.

Neither is a valid CRC from the point of view of reveng, even if you include the command byte or nibble.

I think this means that some other data must augment the message data for the CRC calculation, or that none of the polynomials assumed by reveng are appropriate.

There aren’t enough data to solve this problem at the moment. You need to collect enough messages so that pairs of messages that differ by only one bit can be examined, in order to deduce the effect of each bit on the CRC.

command15 and command16 are special cases, I am not quite sure what they signify.

As far as single bit differences, if you look at byte 9 (offset 0x8 in hex editor) in fr1.txt it is 0x05 --- 0000 0101
byte 9 in fr2.txt is 0x04 --- 0000 0100
byte 9 in fr4.txt is 0x02 --- 0000 0010 *probably not as useful

The only other change between fr1 and fr2 is the CRC value that is added to the messages. Are these single bit changes what you are looking for?

Yes, that is a start!

It is a linear problem, so if you can collect enough of those examples, for messages that are all of the same length and differ by only one bit, a brute force approach can solve it. Actually it is not necessary to have messages that differ by a single bit, but having them will make it much easier, especially if you can find a complete collection (e.g. every bit changed).

e.g. Sitsec Blog: Brute-forcing CRC parameters

Have you ever seen a message that was rejected because of incorrect CRCC? There is the possibility the CRCC is never being checked by the receiver>

Paul

excellent find jremington! however when experimenting with their program (after manually parsing several messages into the correct format) it appears that their program does not actually work any more. I will keep playing with that and see if I can get anything useful though.

hello Paul, I have confirmed that the receiver does check the crc by attempting to throw random data at the unit. (Fuzzing) I found that if the correct CRC is not part of the message the message is never processed within the ASIC by examining the changes of the on board RAM, as well as several bits on the output of the ASIC which would normally toggle with good data.

If you can automate the process of sending trial messages and checking whether they are rejected, this would be an extremely powerful way to find simple messages and their corresponding "CRC"s.

For example, you could send messages with all zero data except for a 1 bit somewhere, and cycle through all 65536 check values, testing for acceptance.

That said, I don’t understand your comment in fr1-anotated.txt about discarding values for which the resulting command is zero. How do you imagine that data on the command bus get incorporated into the CRC? Is there a hardware reason to assume that they ARE incorporated?

The lower 4 bits from the command bus go into the same ASIC that is performing all these functions. It is possible that it is using these 4 bits for the CRC calculation; however I am doubtful that it is in fact doing so..

however I am doubtful that it is in fact doing so..

Yet your somewhat confusing description of the process in "fr1-annotated.txt" appears to be leaving the "11" command byte in the data block for the CRC calculation.

Note: I tried taking the 11 out, or substituting it with 0x01, but reveng still can't come up with a solution.

I still suspect that some data are being included in the CRC, that are entirely separate from the data stream.

A couple of observations when looking at fr5.txt, it seems…
command 0011 is a 32 byte payload header
command 0012 is a 520 byte payload header
command 0013 is a 4 byte payload (CRC?) header
command 0016 is a 0 or 48 byte (fixed?) payload header

I know you mentioned command 0016 (and 0015) have special circumstances and looking at the fr5.txt I can see this. I wonder if the command 0016 (and 0015) with no data payload is a clue to the Polynomial used for the CRC calculation?

fr5a.txt (51.1 KB)

Excellent observations! I have wondered this myself with command 0015 and 0016. However if these commands are actually changing CRC values then that means the command bus is incorporated with the overall CRC data stream. Currently we have been running under the assumption that the commands essentially just tell the ASIC what to do and are not part of the data bus... If we should also include the command bus in the CRC we will have to determine what order the chip is processing both buses. I have seen weird situations where ASIC developers will use MSB on one bus, but LSB on the other! This adds significant time to the brute force calculations (which are still running on my computer, Day 2)... Tempting to just rewrite the program jremington posted to run on CUDA cores instead....

Just a little update; The bruteforce method said it was going to take over 23k hours!! (screen shot attached) Im going to have to find some way in hardware to figure this problem out it appears… Ill keep everyone posted.

ok, I've made a little headway in this project... I have found the CRC for a packet of all ones, and a packet of all zeros:

0016 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0010 0013 EB10 EE10 0010 0010

//Full packet of 0's has CRC 0xEBEE

0016 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 FF10 0013 5710 1610 0010 0010

//Full packet of 1's has CRC 0x5716