resilar/crchack

Reversing CRC for fun and profit

crchack's Issues

Lazy `-b` evaluation

Currently -b 4: for a long input (e.g., 1GB) is handled non-lazily by allocating a huge array to store all the input bits following the 4th byte. This is stupid. Be smarter.

`forge()` does not write the modified message to `out`

The docs state that out is populated with the modified message but it is not:

crchack/forge.h

Line 31 in 7902c05

* Output buffer `out` receives a modified message with the desired checksum.

The out argument is currently unused. I might be being overly pedantic since the docs are admitted to be incorrect, but still.

Thank you for this tool, by the way, it is quite helpful!

Split into a dynamic lib and a CLI interface to it

Usually it is beneficial to split CLI software into 2 layers:
* a shared lib doing the stuff
* a CLI to it

The benefit is that the lib can be used in other software, of course.

Doesn't work with my specific case

I tried, without success, to use custom parameters to force CRC on a file that is verified with something that looks like the crc32-alder algorithm.

Here is the crc calculation code (that use a table):

uint32_t crc32_init(void)
{
return 0xffffffff;
}

uint32_t crc32_byte(uint32_t accum, uint8_t delta)
{
return table[(accum ^ delta) & 0xff] ^ (accum >> 8);
}

uint32_t get_crc(unsigned char *buffer, size_t buffer_size) {
uint32_t crc = crc32_init();
for (int i = 0; i < buffer_size; i++) {
crc = crc32_byte(crc, buffer[i]);
}
return crc;
}

Here is the code that has been used to generate the table (we can read that the polynomial is 0xedb88320):

Here are the parameters I tried and the message generated:

-w32 -pedb88320
FAIL! try giving 32 mutable bits more (got 32)

-w32 -pedb88320 -iffffffff
FAIL! try giving 32 mutable bits more (got 32)

-w32 -pedb88320 -iffffffff -xff -rR
FAIL! try giving 5 mutable bits more (got 32)

-w32 -pedb88320 -iffffffff -rR
FAIL! try giving 4 mutable bits more (got 32)

-w32 -pedb88320 -iffffffff -xff
FAIL! try giving 28 mutable bits more (got 32)

-w32 -pedb88320 -iffffffff -xff -r
FAIL! try giving 28 mutable bits more (got 32)

-w32 -pedb88320 -iffffffff -xff -R
FAIL! try giving 5 mutable bits more (got 32)

-w32 -pedb88320 -iffffffff -R
FAIL! try giving 4 mutable bits more (got 32)

-w32 -pedb88320 -iffffffff -r
FAIL! try giving 32 mutable bits more (got 32)

What am I doing wrong ?

Deprecate -o/-O offset switches in favor of -b switches

Quoting myself from comment thread of issue #9 "Lazy -b evaluation"

I think we should consider deprecating offset switches -o/-O at some point because -b switches are now expressive and user-friendly enough to offer the same functionality: -o 42 and -b 42: are essentially identical. Similarly, -O 42 and -b -42: are equivalent to each other. The only disadvantage of -b command-line options is that appending to the input is unsupported when forging CRC checksums, whereas -o and -O do support appending to the end of the input message. However, the current append mechanism should probably be rewritten anyway to support prepending also (as discussed in issue #11).

Replace make with CMake

CMake supports multiple toolchains.

Handle underdetermined matrices

Currently crchack works with determined and overdetermined systems of equations. In some cases an underdetermined system may have solutions which can be used to get the desired checksum value.

Unable to compile, bigint.h:7:10: fatal error: bittypes.h: No such file or directory

Commit 0c877a2 introduced the bittypes.h file but it seem that it's not part of the repository.

Streaming version of crchack

crchack currently reads the whole input message into a memory buffer before starting the CRC calculation/forging process. Ideally, we would like to read the input message in chunks and perform the CRC calculation or CRC forging operation in one pass over the input. This, unfortunately, would require major changes to the code at the time being.

Improve speed

The CRC computation is too slow for files >100MB. This can be improved a lot.

Quines

Implement a feature to calculate CRC quines. For example:

$ printf "\xcc\x4f\xbb\x6a" | ./crchack -
cc4fbb6a
$ printf "\xff\xff\xff\xff" | ./crchack -
ffffffff
$ printf 'foo\x81\xc8\x73\xa7bar' | ./crchack -
81c873a7
$ printf 'foo\xe0\x2d\x7a\x0bbar' | ./crchack -
e02d7a0b

sagemath proof of concept:

def binvec(x, w=32): return vector(GF(2), x.digits(2, padto=w))

def crc32(msg):
    crc = 0xffffffff
    for c in msg.encode() if isinstance(msg, str) else msg:
        crc ^^= c & 0xff
        for _ in range(8):
            crc = (crc >> 1) ^^ 0xedb88320 if crc & 1 else crc >> 1
    return crc ^^ 0xffffffff

def h(x): return crc32(int(x).to_bytes(4, 'big'))
h0 = h(0) # crc32(b'\x00\x00\x00\x00')
diff = [h0 ^^ h(2^x) for x in range(32)]
A = matrix(GF(2), 32, [x.digits(2, padto=32) for x in diff]).transpose()

# Find a quine
sol = (A - identity_matrix(GF(2), 32)).solve_right(binvec(h0, 32))
quine = Integer(sol.list(), base=2)
print(hex(quine), quine == h(quine))
# 0xcc4fbb6a True

# Calculate all quines
def quines(h, w=32):
    def gf2vec(x): return vector(GF(2), x.digits(2, padto=w))
    h0 = h(0)
    diff = [h0 ^^ h(2^x) for x in range(w)]
    A = matrix(GF(2), w, [x.digits(2, padto=w) for x in diff]).transpose()
    Id = identity_matrix(GF(2), w)
    try: sol = (A - Id).solve_right(gf2vec(h0))
    except: return # No solutions
    for kernel in (A - Id).right_kernel():
        yield Integer((sol + kernel).list(), base=2)

def h(x, prefix=b'', suffix=b''):
    return crc32(prefix + int(x).to_bytes(4, 'big') + suffix)
for quine in quines(h, 32): print(hex(quine), quine == h(quine))
# 0xcc4fbb6a True
# 0xffffffff True

H = lambda x: h(x, b'foo', b'bar')
for quine in quines(H, 32):
    print(hex(quine), quine == H(quine))
# 0x81c873a7 True
# 0xe02d7a0b True

User-friendlier way to specify mutable bits for alphanumerical output

Proposed behavior:

• -b 03FFFFC0@1024 selects 20 bits at position 1024
• -b 80@30:40 selects 10 MSBs between positions 30 and 40
• -b 2@0:-1:1 selects all bits except the first (apply at every bit position)

After implementing this, bit numbering could be changed to MSB -> LSB which is more intuitive IMO.

Read positions of mutable bits from the command line

The current bits-file thing sucks.

Clarification: prepending instead of appending, using -O option with negative values?

I'm trying to calculate a 4 byte value to PREPEND to a 8192 byte data file so as to get a specified CRC32 value 0x224E16C3 . My reading of the manual made me think I needed to use the option -O -8192 or maybe even -O -8196. But that does not work. Can you please clarify how to get a value to prepend? Test case below.

## create test file with hex AB repeated the entire file
perl -e '$x="AB" x 8192; print pack("H*", $x);' > fileAB.8192
hexdump fileAB.8192

## test regular append-mode
crchack fileAB.8192 224E16C3 > test-append
crchack test-append
# observe that the padding value is appended
hexdump test-append

##trying to create a value to PREPEND
crchack  -O -8192  fileAB.8192 224E16C3 > test-prepend
crchack test-prepend
# observe that the padding value is appended but I thought it would prepended?
hexdump test-prepend

crchack  -O -8196 fileAB.8192 224E16C3 > test-prepend
leads to error message: bits[0]=65568 exceeds message length (65567 bits)