Re: CRC question

In article <1156274464.334380.62710@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"hypermodest" <hypermodest@xxxxxxxxx> wrote:

I have a source code of very special hash-function and
I seek ways to crack it somehow. One part of this function
is CRC-function

In the real world, in front of some function that you suspect
is a CRC, but of unknown polynomial, and/or where you do not
know the details such as modulus polynomial, initial and
final message padding, order in which input bits form the
divided polynomial, and/or the order in wich outputs bit
form the rest of polynomial division (or, in your case,
fail to figure this out from code inspection),
first thing is to check that a basic property of all CRC
derivatives is verified:
for any three messages A B C of same length
H(A XOR B XOR C) = H(A) XOR H(B) XOR H(C)

By this property alone, H(X) for any X of n bits can be
trivially computed from the H(Mj) of only n+1 approriate
fixed messages, such as the n+1 distinct Mj of n bits
with at most 1 bit set.

This technique works for a class of functions much wider
than the textbook CRC, including all CRC-lookalikes
for fixed length messages, without bothering for annoying
details. I suspect this is enough for your needs.


if you figure out the order of bits in the messages and
remainder, finding the reducing polynomial is relatively
easy: independetly of initial and final message padding
value (but dependent on the numder m of bits in the final
padding, which is the order of the reducing polynomial
in the textbook CRC, and in practice some small multiple
of 8), the XOR of two distinct messages of same length,
left-shifted by m bits, then XORed with the CRC of each
two messages, must be divisible by the reducing
polynomial.

Thus, gather a few examples, fire a polynomial GCD,
and you get the reducing polynomial (or disprove your
hypothesis on m or the order of bits).


François Grieu
.

Relevant Pages

  • Re: More about MT19937 in crypto
    ... end up dealing with XOR chains complex enough that you do have to ... off-diagonal 1's that perform simply a "shift" operation. ... for updating the CRC register for "byte at a time" CRCs, ... the base of the logarithm, not the fact that it's O. ...
    (sci.crypt)
  • crc code using vhdl found , few questions on it!!!
    ... has the software to generate the vhdl code for the crc 32 polynomial. ... crc is computed on only 4 bits of data. ... I will change the variable assignment to the ... Cxor C; ...
    (comp.arch.fpga)
  • Re: Query in Parallel CRC(urgent)
    ... The serial version of the CRC is the CRC ... As you can tell all we did was shift that first initial bit all the way ... Putting it all together is Dxor Dxor ... the first serial data bit is D ...
    (comp.arch.fpga)
  • Re: Why Microsoft products using RC4 failed
    ... Since the CRC is linear, we can xor Delta into the message ... XOR chunk3 XOR chunk4), calculate CHK, ...
    (sci.crypt)