Computer Interfacing
Discussions about interfacing and electronics
 

CRC16 Reverse Engineer- Reveng: no brute force seach occurs


 

       Computer Interfacing Forum Index -> Error detection and correction
Author Message
mtsunstrum
Guest







Feb 22, 2014 7:05 am

I have several packet samples, that strongly appear to have a CRC16 on the end of the packet.
I am attempting to reverse engineer the CRC16 calculation using "reveng"

Each packet is 21 bytes (19 bytes data, 2 bytes CRC)
I have verified the following:
- all 19 bytes are involved in the CRC16 calculation
- that the packet samples observe the "superposition princple", indicating that the last 2 bytes strongly appear to be a CRC calculation
(See Section "Applying some Brute Force" in www(dot)cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.html)

I run the following "reveng" command:
reveng.exe -w 16 -s C1A71A240F57537579A889C320652C8AA925A85E22 C1A71A240F57537579A889C320652C8AA92FA80520 C1A71A240F57537579A889C320652C8AA92B288B3D

and "no models found" is returned.

I don't expect this CRC16 to be a standard model, so this returned value is not surprising.
But I would expect "reveng" to continue on and perform a "brute force" search through all possible polynomials.

See www(dot)lammertbies.nl/forum/viewtopic.php?t=1867 where "reveng" will show "reveng: searching: width=16 poly= ..." status messages.

In my case, I don't see these "reveng: searching" messages, and "reveng" appears to run/exit very quickly.
I would think that it might take several seconds to run through a full brute force test.

Anyone familiar with "reveng" enough to know if something is preventing it from proceeding with a "brute force" polynomial search ?

Any help is appreciated !

Martin
Guest








Feb 28, 2014 8:30 pm

Hello Martin, thank you for your interest in the forums and CRC RevEng.

Firstly, the "searching:" messages are coded so that they don't appear more than 1-2 times per minute on current hardware. When the whole search is not expected to take this long - i.e. the polynomial width is 28 bits or less - then the messages are not printed at all.

Secondly, to brute-force the polynomial, CRC RevEng XORs pairs of messages and discards the leading zeroes of the result, as they have no effect on the search result. Even though the messages are long, they only differ in the last 4 bytes, and so the search only operates on these bytes.

Therefore, this search problem consists of 32768 iterations of CRC-16 on a 4-byte message. On my machine it completes in less than 0.5 seconds. If a candidate polynomial divides the first superposed pair, it is tested against all others before printing. In this case there is no polynomial that satisfies all three of your sample messages.

You can see that CRC RevEng really is doing a brute force search by removing one of the messages. Be aware that these outputs are probably spurious!
Code:
$ reveng -w 16 -s C1A71A240F57537579A889C320652C8AA925A85E22 \
                  C1A71A240F57537579A889C320652C8AA92FA80520
width=16  poly=0x5299  init=0xc92b  refin=false  refout=false  xorout=0x0000  check=0xb9aa  name=(none)
width=16  poly=0x5789  init=0x9f11  refin=false  refout=false  xorout=0x0000  check=0x7d5f  name=(none)
width=16  poly=0x667b  init=0xef2a  refin=false  refout=false  xorout=0x0000  check=0xf226  name=(none)

But as for the problem itself: I will endeavour to take a look at it this weekend, if free time permits.

Regards,

Greg
regregex
Preferred Member



Joined: 30 Oct 2007
Posts: 184
Location: London, UK

Feb 28, 2014 8:32 pm

[Last post was by me - login timed out Smile]

       Computer Interfacing Forum Index -> Error detection and correction
Page 1 of 1



Running on php BB © 2001, 2009 php BB Group
   Lammert Bies     Interfacing     Sitemap     Forum