[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.python

Reverse engineering CRC?

Gregory Ewing

3/8/2010 3:09:00 AM

Given some known data/crc pairs, how feasible is it to
figure out the polynomial being used to generate the crc?

In the case I'm looking at, it appears that the crc
size may be at least 24 bits, so just trying all possible
polynomials probably isn't doable.

An article I found hints at the possibility of using
GCDs to make the search more efficient, but doesn't go
into any details. Anyone know of any literature about
this?

If it helps, I have the ability to generate test cases
with known message contents to some extent, although
I don't have complete control over the contents. Also
it's a manual process, so generating large numbers of
them automatically isn't an option.

--
Greg
20 Answers

Steven D'Aprano

3/8/2010 3:42:00 AM

0

On Mon, 08 Mar 2010 16:09:12 +1300, Gregory Ewing wrote:

> Given some known data/crc pairs, how feasible is it to figure out the
> polynomial being used to generate the crc?

Can you just ask the application developer what CRC is being used? Or
look at the source code? Disassemble the binary?


> In the case I'm looking at, it appears that the crc size may be at least
> 24 bits, so just trying all possible polynomials probably isn't doable.

"At least"? Can't you tell by looking at them?

A good place to start is here:

http://en.wikipedia.org/wiki/Cyclic_redund...
http://en.wikipedia.org/wiki/List_of_checksum_...

You can at least eliminate known CRCs. There doesn't appear to be any 24-
bit CRCs in common use, and very few other 24-bit checksums either, so
you're probably looking at a custom CRC.


> An article I found hints at the possibility of using GCDs to make the
> search more efficient, but doesn't go into any details. Anyone know of
> any literature about this?

If you're reduced to trying to determine the polynomial from a sample of
checksums, that's a curve fitting problem. There are various ways to fit
polynomials through a set of known points, but as far as I know none of
them are designed for reverse-engineering CRCs.

You may be able to find something about curve-fitting using discrete
maths (i.e. where all values are limited to integers) or with constraints.

You should probably take this to somewhere like sci.crypt. Here's a
thread from a few years back which might give you some hints:

http://www.derkeiler.com/Newsgroups/sci.crypt/2008-07/msg...

Or here:

http://stackoverflow.com/questions/401231/determining-crc-algor...
data-crc-embedded-application


--
Steven

Steven D'Aprano

3/8/2010 3:44:00 AM

0

On Mon, 08 Mar 2010 16:09:12 +1300, Gregory Ewing wrote:

> Given some known data/crc pairs, how feasible is it to figure out the
> polynomial being used to generate the crc?

Google is your friend:

http://www.woodmann.com/fravia/c...



--
Steven

Dave Angel

3/8/2010 10:13:00 AM

0

Steven D'Aprano wrote:
> On Mon, 08 Mar 2010 16:09:12 +1300, Gregory Ewing wrote:
>
>
>> Given some known data/crc pairs, how feasible is it to figure out the
>> polynomial being used to generate the crc?
>>
>
> Google is your friend:
>
> http://www.woodmann.com/fravia/c...
>
>
That page was interesting to read, especially since I've implemented the
three algorithms - CRC16, CRC32, and the reversed version of CRC16, all
in the long-distant past.

However, if there's anything in there about how to derive the polynomial
algorithm from (a few) samples I missed it entirely. Instead, what it
calls reverse engineering is figuring out how to modify a message to
force it to have a desired CRC value (when the CRC polynomial is already
known).

DaveA

Gregory Ewing

3/8/2010 11:07:00 AM

0

Steven D'Aprano wrote:

> Can you just ask the application developer what CRC is being used? Or
> look at the source code? Disassemble the binary?

There's no source, and the binary is enormous. I could ask,
but I wouldn't hold out much hope of them being willing to
tell me.

>>it appears that the crc size may be at least
>>24 bits, so just trying all possible polynomials probably isn't doable.
>
> "At least"? Can't you tell by looking at them?

It's not entirely clear exactly which bytes are part of the
CRC. There are 3 adjacent bytes in the header of the file
that change when I modify the contents, which led me to
think it was a 24-bit CRC. But I now believe that one of
them is not part of the CRC, and it's actually 16 bits.

Using pycrc, I've now tried all possible 16-bit polynomials,
with various combinations of bit and byte reversal, but I
haven't found one that works consistently, so I'm wondering
whether it's using some non-standard algorithm.

--
Greg

Dave Angel

3/8/2010 1:07:00 PM

0

Gregory Ewing wrote:
> Steven D'Aprano wrote:
>
>> Can you just ask the application developer what CRC is being used? Or
>> look at the source code? Disassemble the binary?
>
> There's no source, and the binary is enormous. I could ask,
> but I wouldn't hold out much hope of them being willing to
> tell me.
>
>>> it appears that the crc size may be at least
>>> 24 bits, so just trying all possible polynomials probably isn't doable.
>>
>> "At least"? Can't you tell by looking at them?
>
> It's not entirely clear exactly which bytes are part of the
> CRC. There are 3 adjacent bytes in the header of the file
> that change when I modify the contents, which led me to
> think it was a 24-bit CRC. But I now believe that one of
> them is not part of the CRC, and it's actually 16 bits.
>
> Using pycrc, I've now tried all possible 16-bit polynomials,
> with various combinations of bit and byte reversal, but I
> haven't found one that works consistently, so I'm wondering
> whether it's using some non-standard algorithm.
>
Or even some other standard algorithm. If you know so little about the
value, how do you even know it's a CRC ? Could it be a ones-complement
sum, such as used in Ethernet?

Is the problem really worth it? The possibilities are practically
unbounded. And if the developer is really determined to make it
difficult, they could be doing multiple passes over the data, in which
case probably disassembly (or subtle debug tracing) may be your best bet.

DaveA

Dave

Gregory Ewing

3/8/2010 10:16:00 PM

0

Dave Angel wrote:
> If you know so little about the
> value, how do you even know it's a CRC ? Could it be a ones-complement
> sum, such as used in Ethernet?

I'm going by the fact that the application reports a
"CRC mismatch" when it's wrong. I can't be sure that what
it calls a "CRC" is really a true CRC, but it's more than
a simple sum, because changing one bit in the file results
in a completely different value.

> Is the problem really worth it?

Probably not -- it looks like fixing the problem I'm trying
to fix by hand will be faster in the long run. I just thought
it might turn out to be a solved problem and someone could
point me to an algorithm for it, but it seems not.

--
Greg

Dave Angel

3/8/2010 11:24:00 PM

0

Gregory Ewing wrote:
> <div class="moz-text-flowed" style="font-family: -moz-fixed">Dave
> Angel wrote:
>> If you know so little about the value, how do you even know it's a
>> CRC ? Could it be a ones-complement sum, such as used in Ethernet?
>
> I'm going by the fact that the application reports a
> "CRC mismatch" when it's wrong. I can't be sure that what
> it calls a "CRC" is really a true CRC, but it's more than
> a simple sum, because changing one bit in the file results
> in a completely different value.
>
>> Is the problem really worth it?
>
> Probably not -- it looks like fixing the problem I'm trying
> to fix by hand will be faster in the long run. I just thought
> it might turn out to be a solved problem and someone could
> point me to an algorithm for it, but it seems not.
>
If you assume it's done in a single pass, and you know which byte is the
end of the buffer, I'd think you could learn a lot by just tweaking that
last byte. But I still think you'd want to automate your testing,
presumably by some keystroke-stuffer.

DaveA

Gregory Ewing

3/10/2010 12:18:00 AM

0

Dave Angel wrote:

> If you assume it's done in a single pass, and you know which byte is the
> end of the buffer, I'd think you could learn a lot by just tweaking that
> last byte.

I'm sure I would, but unfortunately I can't control the
last byte. The bytes that I can influence are some distance
back from the end of the data.

--
Greg

Steve Howell

3/10/2010 5:23:00 AM

0

On Mar 7, 7:09 pm, Gregory Ewing <greg.ew...@canterbury.ac.nz> wrote:
> Given some known data/crc pairs, how feasible is it to
> figure out the polynomial being used to generate the crc?
>
> In the case I'm looking at, it appears that the crc
> size may be at least 24 bits, so just trying all possible
> polynomials probably isn't doable.
>
> An article I found hints at the possibility of using
> GCDs to make the search more efficient, but doesn't go
> into any details. Anyone know of any literature about
> this?
>
> If it helps, I have the ability to generate test cases
> with known message contents to some extent, although
> I don't have complete control over the contents. Also
> it's a manual process, so generating large numbers of
> them automatically isn't an option.
>


Hi Greg. I would at least flip one bit at a time on the first byte of
your data to see if the transformation is bitwise.

Gregory Ewing

3/11/2010 9:41:00 PM

0

Steve Howell wrote:

> Hi Greg. I would at least flip one bit at a time on the first byte of
> your data to see if the transformation is bitwise.

I'm actually making good progress on this -- it turns out
there *is* a way of deducing the polynomial by looking at
the effect of single-bit flips. It's actually quite simple,
with no brute-force searching needed at all.

Things get a bit tricky when you don't quite know all
of the data that goes into the CRC, though, which seems
to be the case here...

I'm writing up an essay on my experiences. I'll post a
link when it's finished.

--
Greg