crcforge.py

#!/usr/bin/env python

# Useful common polynomials:
#POLY = 0x82F63B78 # CRC-32C (Castagnoli)
#POLY = 0xEB31D82E # CRC-32K (Koopman)
#POLY = 0xD5828281 # CRC-32Q


class CRCForger():
    def __init__(self, *args, **kwargs):
        # Polynomial is in "reversed" notation. See
        # [here](http://en.wikipedia.org/wiki/Cyclic_redundancy_check) for details.
        self.polynomial = 0xedb88320 # CRC-32-IEEE 802.3
        self.crc32_table = [0] * 256
        self.crc32_reverse = [0] * 256
        self._build_crc_tables()

    def _build_crc_tables(self):
        for i in range(256):
            fwd, rev = i, i << 24
            for j in range(8):
                # build normal table
                if (fwd & 1) == 1:
                    fwd = (fwd >> 1) ^ POLY
                else:
                    fwd >>= 1
                self.crc32_table[i] = fwd & 0xffffffff
                # build reverse table
                if rev & 0x80000000 == 0x80000000:
                    rev = ((rev ^ POLY) << 1) | 1
                else:
                    rev <<= 1
                rev &= 0xffffffff
                self.crc32_reverse[i] = rev

    def crc32(self, s):
        """Returns the CRC32 checksum of the byte sequence S.
        """
        checksum = 0xffffffff
        for element in s:
            index = (checksum ^ element) & 0xFF
            checksum = (checksum >> 8) ^ self.crc32_table[index]
        return checksum ^ 0xffffffff

    def forge(self, wanted_crc, data, pos=None):
        """Returns the bytes necessary to add to DATA in order to have the checksum WANTED_CRC.
        WANTED_CRC is an integer.
        DATA is a bytes object.
        """
        if pos is None:
            pos = len(data)

        # forward calculation of CRC up to pos, sets current forward CRC state
        fwd_crc = 0xffffffff
        for element in data[:pos]:
            fwd_crc = (fwd_crc >> 8) ^ self.crc32_table[(fwd_crc ^ element) & 0xff]

        # backward calculation of CRC up to pos, sets wanted backward CRC state
        bkd_crc = wanted_crc ^ 0xffffffff
        for element in data[pos:][::-1]:
            bkd_crc = ((bkd_crc << 8)&0xffffffff) ^ self.crc32_reverse[bkd_crc >> 24] ^ ord(element)

        # deduce the 4 bytes we need to insert
        for element in pack('<L', fwd_crc)[::-1]:
            bkd_crc = ((bkd_crc << 8) & 0xffffffff) ^ self.crc32_reverse[bkd_crc >> 24] ^ element

        res = data[:pos] + pack('<L', bkd_crc) + data[pos:]
        assert(self.crc32(res) == wanted_crc)
        return res


if __name__ == '__main__':
    import argparse
    from struct import pack, unpack

    parser = argparse.ArgumentParser(description='Forge a CRC32 checksum')
    parser.add_argument('checksum', metavar='CHECKSUM', type=int, help='the checksum to forge')
    parser.add_argument('data', metavar='DATA', type=lambda x: bytes(x, 'utf8'), help='the bytes to add bytes to', default='')
    parser.add_argument('--polynomial', '-p', metavar='POLYNOMIAL', type=int, help='the CRC polynomial to use', default=POLY)
    args = parser.parse_args()

    forger = CRCForger()
    output = forger.forge(args.checksum, args.data)

    print(output)