Prev: Call for papers: SETP-10, USA, July 2010
Next: [ANNC] pynguin-0.2 (python turtle graphics application)
From: Albert van der Horst on 13 Mar 2010 10:29
In article <7vj7fdFnnjU1(a)mid.individual.net>,
Gregory Ewing <greg.ewing(a)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.

If it is really a CRC, it is doable.

You can have an indication, if the intention is to detect
machine errors (transmission or disk errors) or they want
you to prevent tampering with the file.
In the latter case it may be a one-way hash. Then it is near
impossible, as this is the design criterion for a one-way hash.

>--
>Greg

Groetjes Albert

--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert(a)spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

From: Gregory Ewing on 15 Mar 2010 06:29
I've solved the problem now.

It turned out to be a very standard CRC algorithm, complicated
by the presence of a few extra bytes of data being checked that
didn't appear explicitly in the file anywhere.

In the process I developed some very general techniques for
solving this kind of problem, which I've written about here
if anyone's interested:

http://www.cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.html

Thanks for everyone's help,
Greg
From: jkn on 15 Mar 2010 16:52
Hi Greg
Just to say thanks for taking the time to write up your work on
this interesting topic.

Cheers
J^n

From: geremy condra on 15 Mar 2010 16:57
On Mon, Mar 15, 2010 at 6:29 AM, Gregory Ewing
<greg.ewing(a)canterbury.ac.nz> wrote:
> I've solved the problem now.
>
> It turned out to be a very standard CRC algorithm, complicated
> by the presence of a few extra bytes of data being checked that
> didn't appear explicitly in the file anywhere.
>
> In the process I developed some very general techniques for
> solving this kind of problem, which I've written about here
> if anyone's interested:
>
> http://www.cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.html
>
> Thanks for everyone's help,
> Greg

Nice writeup, thanks.

Geremy Condra
From: Gabriel Genellina on 16 Mar 2010 02:16
En Mon, 15 Mar 2010 07:29:51 -0300, Gregory Ewing
<greg.ewing(a)canterbury.ac.nz> escribi�:

> I've solved the problem now.
>
> It turned out to be a very standard CRC algorithm, complicated
> by the presence of a few extra bytes of data being checked that
> didn't appear explicitly in the file anywhere.
>
> In the process I developed some very general techniques for
> solving this kind of problem, which I've written about here
> if anyone's interested:
>
> http://www.cosc.canterbury.ac.nz/greg.ewing/essays/CRC-Reverse-Engineering.html

A good solution to an interesting problem - and very nicely explained too!

--
Gabriel Genellina

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Call for papers: SETP-10, USA, July 2010
Next: [ANNC] pynguin-0.2 (python turtle graphics application)