[Cryptography] Trying to crack a CRC

[Henry Baker]

-----Original Message-----
From: 
Sent: Apr 23, 2022 10:57 PM
To: 
Subject: [Cryptography] Trying to crack a CRC
 
Hi all:
 
This problem should be trivial, but I'm still having trouble.
 
I'm trying to crack what appears to be a 32-bit CRC algorithm.
 
I can gather a large number of samples, and I can 'correct' the
CRC (at some cost) in order to run chosen plaintext experiments.
 
Here are the parameters:
 
* Messages are 28 bytes; CRC is 4 bytes; total size is 32 bytes.
* I've gathered enough messages & done Gaussian elimination to prove that:
a) the CRC calculation is linear, and all bits participate.
b) I've been able to determine the CRC's for almost 100 out of the 224 'singleton' (1 non-zero, non-CRC bit) vectors.
c) I'm able to get singletons for upwards of 16 or more adjacent bits, which should be able to provide enough data to completely solve the CRC algorithm.
 
Although the CRC is 32 bits long, I can't verify that it is a single CRC-32 algorithm (rather than, e.g., 2 16-bit CRC-16's).
 
I suspect that the CRC is 'little-endian', but I haven't been able to prove it.
 
Unfortunately, I haven't had any success with open source CRC crackers that I found on the web: 'crc-beagle' and 'reveng'.
 
'crc-beagle' apparently checks a bunch of standard CRC algorithms, while 'reveng' supposedly searches the space mathematically.
 
'reveng' should be capable of solving this problem, but the documentation is so sparse that I haven't been able to figure out how to use it.
 
Has anyone here had any success utilizing the 'reveng' tool?

 
------------
 
Well, trying to utilize 'crc-beagle' and 'reveng' to crack my crc was a complete waste
of time.
 
I finally determined that the CRC I was trying to crack is perhaps the most common
CRC in existence -- so-called 'CRC-32' -- as used in
 
"ISO 3309 (HDLC), ANSI X3.66 (ADCCP), FIPS PUB 71, FED-STD-1003,
ITU-T V.42, ISO/IEC/IEEE 802-3 (Ethernet), SATA, MPEG-2, PKZIP, Gzip,
Bzip2, POSIX cksum,[53] PNG,[54] ZMODEM, many others"
 
https://en.wikipedia.org/wiki/Cyclic_redundancy_check
 
The fact that 'crc-beagle' and 'reveng' couldn't crack these means that
either their code has rotted (entirely possible, given how old these codes
are), or their documentation is so hopelessly confused that their tools are
useless.
 
BTW, having a contiguous sequence of 'singleton' bits makes it
relatively trivial to compute the polynomial, and one can then easily
brute force 32 bits to compute the value for any other bit position.
 
Apparently, the CRC I was trying to crack had a non-standard
initial value, which shouldn't have been a problem for a mathematical
tool.
 
I guessed right that the CRC was little-endian.
 
I found it very easy to use Lisp bignums to represent & manipulate
the various bitvectors, so my code won't be of much help to
C/C++/etc. folk.