views:

886

answers:

3
+1  Q: 

Reversing CRC32

I'm looking for a way to reverse a CRC32 checksum. There are solutions around, but they are either badly written, extremely technical and/or in Assembly. Assembly is (currently) beyond my ken, so I'm hoping someone can piece together an implementation in a higher level language. Ruby is ideal, but I can parse PHP, Python, C, Java, etc.

Any takers?

+8  A: 

A CRC32 is only reversible if the original string is 4 bytes or less.

Cade Roux
I doubt crc will generate a unique 32-bit code for every string combo 4 bytes or less ...
Goz
If you look at the implementation, for 4 bytes it will do 3 8-bit shifts with only XOR operations, so yes, it is reversible: http://www.sanity-free.org/12/crc32_implementation_in_csharp.html
Cade Roux
This is what I'd initially thought, and then had people send the links mentioned above my way... obviously, the fact it's limited to 4 bytes was glossed over.Thanks for the clarification.
pat
If CRC is based on primitive polynomial what usualy is, that mean that it will return uniqe key for every of 2^32 imputs.
ralu
Misses the point: even though CRC32 is not always reversible, given that a certain CRC32 value is a CRC of a real string, it is necessarily reversible.
Pavel Radzivilovsky
@Pavel I think you cannot construct a 4-byte string for any given 32-bit value which would generate that value as CRC32 (it probably doesn't have perfect entropy). It probably is true that you can construct some string to produce a given value as its CRC32. There are an infinity of strings which produce the same CRC32. Hence the notion of reversibility is rather limited - you can only show A string which has the CRC32, not necessarily the CORRECT string (in the sense of error correction). I took reversibility in the sense that this would need to be a bijective function, which it is not.
Cade Roux
the question is what is meant by reverse, indeed.
Pavel Radzivilovsky
A: 

Cade Roux Is right about reversing CRC32.

The links you mentioned provide a solution to fix a CRC that has become invalide by altering the original byte stream. This fix is achieved by changing some (unimportant) bytes and so recreate the original CRC value.

Frank Bollack
Or hacking the stream so that the CRC is unchanged while important data (like anti-piracy code) is changed.
Cade Roux
+2  A: 

Read this fine document.

This is C#:

public class Crc32
{
    public const uint poly = 0xedb88320;
    public const uint startxor = 0xffffffff;

    static uint[] table = null;
    static uint[] revtable = null;

    public void FixChecksum(byte[] bytes, int length, int fixpos, uint wantcrc)
    {
        if (fixpos + 4 > length) return;

        uint crc = startxor;
        for (int i = 0; i < fixpos; i++) {
            crc = (crc >> 8) ^ table[(crc ^ bytes[i]) & 0xff];
        }

        Array.Copy(BitConverter.GetBytes(crc), 0, bytes, fixpos, 4);

        crc = wantcrc ^ startxor;
        for (int i = length - 1; i >= fixpos; i--) {
            crc = (crc << 8) ^ revtable[crc >> (3 * 8)] ^ bytes[i];
        }

        Array.Copy(BitConverter.GetBytes(crc), 0, bytes, fixpos, 4);
    }

    public Crc32()
    {
        if (Crc32.table == null) {
            uint[] table = new uint[256];
            uint[] revtable = new uint[256];

            uint fwd, rev;
            for (int i = 0; i < table.Length; i++) {
                fwd = (uint)i;
                rev = (uint)(i) << (3 * 8);
                for (int j = 8; j > 0; j--) {
                    if ((fwd & 1) == 1) {
                        fwd = (uint)((fwd >> 1) ^ poly);
                    } else {
                        fwd >>= 1;
                    }

                    if ((rev & 0x80000000) != 0) {
                        rev = ((rev ^ poly) << 1) | 1;
                    } else {
                        rev <<= 1;
                    }
                }
                table[i] = fwd;
                revtable[i] = rev;
            }

            Crc32.table = table;
            Crc32.revtable = revtable;
        }
    }
}
Fozi
OMG! It works! Thanks! :)
SLA80