Cracking CRC32 with Forward Polynomial Constant

Study case Intechfest 2022 (see are see).

Preface

During the competition, my team got 1st place and i got 1st blood in this challenge. I've been facing some CRC32 challenge that required me to do cracking, but this one is not usual. It requires me to do some preprocessing before cracking using crchack.

Analyzing the Code

Given source code below

#!/usr/bin/python3

import base64

# polynomial = ????
crc_32_tab = [
    0x00000000,0xd1a61e95,0x05d75b55,0xd47145c0,0x0baeb6aa,
    0xda08a83f,0x0e79edff,0xdfdff36a,0x175d6d54,0xc6fb73c1,
    0x128a3601,0xc32c2894,0x1cf3dbfe,0xcd55c56b,0x192480ab,
    0xc8829e3e,0x2ebadaa8,0xff1cc43d,0x2b6d81fd,0xfacb9f68,
    0x25146c02,0xf4b27297,0x20c33757,0xf16529c2,0x39e7b7fc,
    0xe841a969,0x3c30eca9,0xed96f23c,0x32490156,0xe3ef1fc3,
    0x379e5a03,0xe6384496,0x5d75b550,0x8cd3abc5,0x58a2ee05,
    0x8904f090,0x56db03fa,0x877d1d6f,0x530c58af,0x82aa463a,
    0x4a28d804,0x9b8ec691,0x4fff8351,0x9e599dc4,0x41866eae,
    0x9020703b,0x445135fb,0x95f72b6e,0x73cf6ff8,0xa269716d,
    0x761834ad,0xa7be2a38,0x7861d952,0xa9c7c7c7,0x7db68207,
    0xac109c92,0x649202ac,0xb5341c39,0x614559f9,0xb0e3476c,
    0x6f3cb406,0xbe9aaa93,0x6aebef53,0xbb4df1c6,0xbaeb6aa0,
    0x6b4d7435,0xbf3c31f5,0x6e9a2f60,0xb145dc0a,0x60e3c29f,
    0xb492875f,0x653499ca,0xadb607f4,0x7c101961,0xa8615ca1,
    0x79c74234,0xa618b15e,0x77beafcb,0xa3cfea0b,0x7269f49e,
    0x9451b008,0x45f7ae9d,0x9186eb5d,0x4020f5c8,0x9fff06a2,
    0x4e591837,0x9a285df7,0x4b8e4362,0x830cdd5c,0x52aac3c9,
    0x86db8609,0x577d989c,0x88a26bf6,0x59047563,0x8d7530a3,
    0x5cd32e36,0xe79edff0,0x3638c165,0xe24984a5,0x33ef9a30,
    0xec30695a,0x3d9677cf,0xe9e7320f,0x38412c9a,0xf0c3b2a4,
    0x2165ac31,0xf514e9f1,0x24b2f764,0xfb6d040e,0x2acb1a9b,
    0xfeba5f5b,0x2f1c41ce,0xc9240558,0x18821bcd,0xccf35e0d,
    0x1d554098,0xc28ab3f2,0x132cad67,0xc75de8a7,0x16fbf632,
    0xde79680c,0x0fdf7699,0xdbae3359,0x0a082dcc,0xd5d7dea6,
    0x0471c033,0xd00085f3,0x01a69b66,0xd34db33f,0x02ebadaa,
    0xd69ae86a,0x073cf6ff,0xd8e30595,0x09451b00,0xdd345ec0,
    0x0c924055,0xc410de6b,0x15b6c0fe,0xc1c7853e,0x10619bab,
    0xcfbe68c1,0x1e187654,0xca693394,0x1bcf2d01,0xfdf76997,
    0x2c517702,0xf82032c2,0x29862c57,0xf659df3d,0x27ffc1a8,
    0xf38e8468,0x22289afd,0xeaaa04c3,0x3b0c1a56,0xef7d5f96,
    0x3edb4103,0xe104b269,0x30a2acfc,0xe4d3e93c,0x3575f7a9,
    0x8e38066f,0x5f9e18fa,0x8bef5d3a,0x5a4943af,0x8596b0c5,
    0x5430ae50,0x8041eb90,0x51e7f505,0x99656b3b,0x48c375ae,
    0x9cb2306e,0x4d142efb,0x92cbdd91,0x436dc304,0x971c86c4,
    0x46ba9851,0xa082dcc7,0x7124c252,0xa5558792,0x74f39907,
    0xab2c6a6d,0x7a8a74f8,0xaefb3138,0x7f5d2fad,0xb7dfb193,
    0x6679af06,0xb208eac6,0x63aef453,0xbc710739,0x6dd719ac,
    0xb9a65c6c,0x680042f9,0x69a6d99f,0xb800c70a,0x6c7182ca,
    0xbdd79c5f,0x62086f35,0xb3ae71a0,0x67df3460,0xb6792af5,
    0x7efbb4cb,0xaf5daa5e,0x7b2cef9e,0xaa8af10b,0x75550261,
    0xa4f31cf4,0x70825934,0xa12447a1,0x471c0337,0x96ba1da2,
    0x42cb5862,0x936d46f7,0x4cb2b59d,0x9d14ab08,0x4965eec8,
    0x98c3f05d,0x50416e63,0x81e770f6,0x55963536,0x84302ba3,
    0x5befd8c9,0x8a49c65c,0x5e38839c,0x8f9e9d09,0x34d36ccf,
    0xe575725a,0x3104379a,0xe0a2290f,0x3f7dda65,0xeedbc4f0,
    0x3aaa8130,0xeb0c9fa5,0x238e019b,0xf2281f0e,0x26595ace,
    0xf7ff445b,0x2820b731,0xf986a9a4,0x2df7ec64,0xfc51f2f1,
    0x1a69b667,0xcbcfa8f2,0x1fbeed32,0xce18f3a7,0x11c700cd,
    0xc0611e58,0x14105b98,0xc5b6450d,0x0d34db33,0xdc92c5a6,
    0x08e38066,0xd9459ef3,0x069a6d99,0xd73c730c,0x034d36cc,
    0xd2eb2859]

def crc32(data):
    crc = 0xffffffff
    for byte in data:
        crc = crc_32_tab[(crc ^ byte) & 0xff] ^ (crc >> 8)
    crc = crc ^ 0xffffffff
    return crc & 0xffffffff

FLAG = open('flag.txt', 'r').read()

if __name__ == '__main__':
    try:
        print('Enter your credential >> ', end='')
        cred = base64.b64decode(input())
        
        username, level = '', ''
        for line in str(cred, 'utf-8').splitlines():
            s = line.split(':')
            if len(s) == 2:
                if s[0] == 'username':
                    username = s[1]
                elif s[0] == 'level':
                    level = s[1]

        if username == '':
            print('Invalid credential!')
            exit(1)

        if username == 'nino':
            crc = crc32(cred)
            if crc != 0xCAFEBABE:
                print('You are not my waifu!')
                exit(1)

        print()

        print(f'hi {username}, please choose :^)')
        print('1. do nothing')
        print('2. read flag')

        print('>> ', end='')
        choice = int(input())

        if choice == 1:
            print('You just did nothing...')
        elif choice == 2:
            if username != 'nino':
                print('Only my waifu can read the flag!')
            else:
                print(FLAG)
    except Exception as e:
        print(e)
        exit(1)

It can be seen that the code above implements the crc32 hash, but the crc32 table is different from the general one. The purpose of this question is clear, the point is to find collisions/get a hash value with a predetermined prefix. We found a tool to get collisions on crc32, namely crchack . However, crchack needs several parameters to get collisions in crc32 implementations that do not use default values, for example the default value for the polynomial.

Cracking CRC32

To get the polynomial we use the naive method, namely bruteforce because 32 bits is not too much. Here's the code for bruteforce

A valid value was obtained, which is 0xd34db33f

   #include <stdio.h>

   int main ()
   {
     long i;
     int j;
     long tmp,v;
        
         for (i = 0; i < 4294967296; i++){
         v = 1;
         for (j = 8; j > 0; --j){
              v = (v & 1) ? (v >> 1) ^ i : (v >> 1);
             }
         tmp = v;
         if((tmp&0xffffffff)==0xd1a61e95){
            // 0xd34db33f
            printf("%lx %lx\n",i,tmp);
          }
        }
     return 0;
   }

After getting the polynomial value we realized that the problem implemented crc forward while crchack implemented crc reverse.

// Challenge implementation
crc = crc_32_tab[(crc ^ byte) & 0xff] ^ (crc >> 8)

// Crchack implementation
int bit = bigint_msb(checksum) ^ !!(bytes[i / 8] & bits[i % 8]);
bigint_shl_1(checksum);
if (bit) bigint_xor(checksum, &crc->poly);

So just do the reverse binary value for the seed obtained, then it can be used in CRC as reverse mode.

Because the value of the level is not checked, so just add a random value so that all values from the input are included in the utf-8 encoding.

Finally, just send the value that has a collision

import base64
from pwn import *

crc_32_tab = [
    0x00000000,0xd1a61e95,0x05d75b55,0xd47145c0,0x0baeb6aa,
    0xda08a83f,0x0e79edff,0xdfdff36a,0x175d6d54,0xc6fb73c1,
    0x128a3601,0xc32c2894,0x1cf3dbfe,0xcd55c56b,0x192480ab,
    0xc8829e3e,0x2ebadaa8,0xff1cc43d,0x2b6d81fd,0xfacb9f68,
    0x25146c02,0xf4b27297,0x20c33757,0xf16529c2,0x39e7b7fc,
    0xe841a969,0x3c30eca9,0xed96f23c,0x32490156,0xe3ef1fc3,
    0x379e5a03,0xe6384496,0x5d75b550,0x8cd3abc5,0x58a2ee05,
    0x8904f090,0x56db03fa,0x877d1d6f,0x530c58af,0x82aa463a,
    0x4a28d804,0x9b8ec691,0x4fff8351,0x9e599dc4,0x41866eae,
    0x9020703b,0x445135fb,0x95f72b6e,0x73cf6ff8,0xa269716d,
    0x761834ad,0xa7be2a38,0x7861d952,0xa9c7c7c7,0x7db68207,
    0xac109c92,0x649202ac,0xb5341c39,0x614559f9,0xb0e3476c,
    0x6f3cb406,0xbe9aaa93,0x6aebef53,0xbb4df1c6,0xbaeb6aa0,
    0x6b4d7435,0xbf3c31f5,0x6e9a2f60,0xb145dc0a,0x60e3c29f,
    0xb492875f,0x653499ca,0xadb607f4,0x7c101961,0xa8615ca1,
    0x79c74234,0xa618b15e,0x77beafcb,0xa3cfea0b,0x7269f49e,
    0x9451b008,0x45f7ae9d,0x9186eb5d,0x4020f5c8,0x9fff06a2,
    0x4e591837,0x9a285df7,0x4b8e4362,0x830cdd5c,0x52aac3c9,
    0x86db8609,0x577d989c,0x88a26bf6,0x59047563,0x8d7530a3,
    0x5cd32e36,0xe79edff0,0x3638c165,0xe24984a5,0x33ef9a30,
    0xec30695a,0x3d9677cf,0xe9e7320f,0x38412c9a,0xf0c3b2a4,
    0x2165ac31,0xf514e9f1,0x24b2f764,0xfb6d040e,0x2acb1a9b,
    0xfeba5f5b,0x2f1c41ce,0xc9240558,0x18821bcd,0xccf35e0d,
    0x1d554098,0xc28ab3f2,0x132cad67,0xc75de8a7,0x16fbf632,
    0xde79680c,0x0fdf7699,0xdbae3359,0x0a082dcc,0xd5d7dea6,
    0x0471c033,0xd00085f3,0x01a69b66,0xd34db33f,0x02ebadaa,
    0xd69ae86a,0x073cf6ff,0xd8e30595,0x09451b00,0xdd345ec0,
    0x0c924055,0xc410de6b,0x15b6c0fe,0xc1c7853e,0x10619bab,
    0xcfbe68c1,0x1e187654,0xca693394,0x1bcf2d01,0xfdf76997,
    0x2c517702,0xf82032c2,0x29862c57,0xf659df3d,0x27ffc1a8,
    0xf38e8468,0x22289afd,0xeaaa04c3,0x3b0c1a56,0xef7d5f96,
    0x3edb4103,0xe104b269,0x30a2acfc,0xe4d3e93c,0x3575f7a9,
    0x8e38066f,0x5f9e18fa,0x8bef5d3a,0x5a4943af,0x8596b0c5,
    0x5430ae50,0x8041eb90,0x51e7f505,0x99656b3b,0x48c375ae,
    0x9cb2306e,0x4d142efb,0x92cbdd91,0x436dc304,0x971c86c4,
    0x46ba9851,0xa082dcc7,0x7124c252,0xa5558792,0x74f39907,
    0xab2c6a6d,0x7a8a74f8,0xaefb3138,0x7f5d2fad,0xb7dfb193,
    0x6679af06,0xb208eac6,0x63aef453,0xbc710739,0x6dd719ac,
    0xb9a65c6c,0x680042f9,0x69a6d99f,0xb800c70a,0x6c7182ca,
    0xbdd79c5f,0x62086f35,0xb3ae71a0,0x67df3460,0xb6792af5,
    0x7efbb4cb,0xaf5daa5e,0x7b2cef9e,0xaa8af10b,0x75550261,
    0xa4f31cf4,0x70825934,0xa12447a1,0x471c0337,0x96ba1da2,
    0x42cb5862,0x936d46f7,0x4cb2b59d,0x9d14ab08,0x4965eec8,
    0x98c3f05d,0x50416e63,0x81e770f6,0x55963536,0x84302ba3,
    0x5befd8c9,0x8a49c65c,0x5e38839c,0x8f9e9d09,0x34d36ccf,
    0xe575725a,0x3104379a,0xe0a2290f,0x3f7dda65,0xeedbc4f0,
    0x3aaa8130,0xeb0c9fa5,0x238e019b,0xf2281f0e,0x26595ace,
    0xf7ff445b,0x2820b731,0xf986a9a4,0x2df7ec64,0xfc51f2f1,
    0x1a69b667,0xcbcfa8f2,0x1fbeed32,0xce18f3a7,0x11c700cd,
    0xc0611e58,0x14105b98,0xc5b6450d,0x0d34db33,0xdc92c5a6,
    0x08e38066,0xd9459ef3,0x069a6d99,0xd73c730c,0x034d36cc,
    0xd2eb2859]

def crc32(data):
    crc = 0xffffffff
    for byte in data:
        crc = crc_32_tab[(crc ^ byte) & 0xff] ^ (crc >> 8)
    crc = crc ^ 0xffffffff
    return crc & 0xffffffff

f = open("crchack/z","rb").read()
assert(crc32(f)==0xcafebabe)
payload = base64.b64encode(f)

r = remote("15.235.143.42",19206)
r.recvuntil(b">> ")
r.sendline(payload)
r.recvuntil(b">> ")
r.sendline(b"2")
r.interactive()

Flag : itf{crc_s00_w3ak_lma000000000}