3
\$\begingroup\$

I have a corrupted png image. I checked and the crc32 checksum of the first chunk (size ~65k) does not match with the one I get. I am sure of this.

Also, I have identified the 4 bytes that have the wrong value. I am sure of this.

My question: Is there an efficient way to calculate the values of these 4 bytes, in order to match the required crc32 checksum?

I made a program in C to brute force the values, using this CRC32 function

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>

// The CRC32 function
uint32_t crc32(uint32_t crc, const void *buf, size_t SIZE_CHUNK);

// The size of the corrupted chunk (TYPE+DATA)
uint32_t SIZE_CHUNK = 65449;

// The CRC32 that has to be matched
uint32_t GOOD_CRC32 = 2784191201;

// The offset of the 4 corrupted bytes
uint32_t OFF[4] = {20121, 20467, 20742, 20893};

int main() {
        uint8_t *buf = (uint8_t *)calloc(SIZE_CHUNK, sizeof(uint8_t));
        uint32_t i, j, k, l, crc = 0;
        FILE *fp;

        fp = fopen("corrupted.png", "r+");
        // Offset to the first `IDAT` chunk of the png file
        fseek(fp, 87, SEEK_SET);
        // We fill `but` with the TYPE+DATA fields of the chunk
        fread(buf, sizeof(uint8_t), SIZE_CHUNK, fp);

        // Bruteforce...
        for (i=0; i<256; i++) {
                buf[OFF[0]] = i;
                for (j=0; j<256; j++) {
                        buf[OFF[1]] = j;
                        for (k=0; k<256; k++) {
                                buf[OFF[2]] = k;
                                for (l=0; l<256; l++) {
                                        buf[OFF[3]] = l;
                                        crc = crc32(0, buf, SIZE_CHUNK);
                                        if (crc == GOOD_CRC32)
                                                printf("Values found! i=%d j=%d k=%d l=%d\n", i,j,k,l);
                                }
                        }
                }
        }
        free(buf);
        fclose(fp);
}

However, this is very slow. If it doesn't speed up, it may take several days. It might be due to the size of the chunk (~65Kb).

I thought about pre-compute the CRC (the part from 0 to OFF[0]-1), but it would still be too long.

Info:

The exact size of the chunk is 65449. The corrupted bytes positions are between 20k-21k.

\$\endgroup\$
  • \$\begingroup\$ Yes, given all the rest, one can recompute a run of 32 consecutive bits without resorting to brute-force. CRCs just aren't for security but for safety. \$\endgroup\$ – Deduplicator Oct 14 '15 at 1:53
  • \$\begingroup\$ checksums are used in those types of systems, but they are simply used for validating a set of values to another set of values.. the value itself could be encrypted/encoded/compressed data. \$\endgroup\$ – Brett Caswell Oct 14 '15 at 2:20
  • \$\begingroup\$ this stackoverflow answer may be interesting to you @Mikalo, stackoverflow.com/a/4812571/1366179 \$\endgroup\$ – Brett Caswell Oct 14 '15 at 2:38
  • \$\begingroup\$ Conclusively, the easiest way to get a known CRC32 is to append the old CRC32 to your data which will always give you a CRC32 of 0x2144DF1C ~ stigge.org/martin/pub/SAR-PR-2006-05.pdf .. there is a reference to a magic sequence.. but, to be honest, the paper is riddle with referential terminology... haha \$\endgroup\$ – Brett Caswell Oct 14 '15 at 2:57
1
\$\begingroup\$

Disclaimer: It is not a review, and I am wild guessing.

The DrDobbs article outlines how the partial CRC could be recombined. I recommend to precompute CRCs of all fixed parts of the chunk, and let the GPU handle the rest. GPUs are notoriously good in number crunching, and you have at least 16K+ truly parallel cores on your graphics card. It is \$2^{18}\$ search space per core. Seems feasible.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Multithreading

A quick way to speed this up would be to use multiple threads and divide the problem among the threads. Give each thread its own copy of the buffer, otherwise you'll have problems.

Poor man's multithreading

An even easier way to achieve "multithreading" would be to add command line arguments to your program for the start and end values for i. Then you simply run your program multiple times with different arguments. For example, if you had 4 cores:

$ findcrc 0 63 > out1 &
$ findcrc 64 127 > out2 &
$ findcrc 128 191 > out3 &
$ findcrc 192 255 > out4 &

If you have access to multiple computers, you can extend this technique to split the work into many small pieces to be worked on in parallel.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.