Author's solution: (this code can solve both 64- and 128-bit version of the challenge, but for 64-bit it was simpler to just do MitM)
```C++// Solver for CRC Recursive Challenge from Dragon CTF 2021// Author: Michał "Redford" Kowalczyk//// Could probably be much simpler, but this code was evolving for too long// without a rewrite ¯\_(ツ)_/¯
#include <iostream>#include <cstdio>#include <cstddef>#include <cstring>#include <cassert>#include <algorithm>#include <thread>
using std::swap;using std::pair;using std::make_pair;
// using representation without reversing bits: LSB is on the right (x & 1 == LSB)using poly_t = unsigned __int128;//using poly_t = uint64_t;
//constexpr poly_t MOD = 0xad93d23594c935a9; // <- picked for 64-bit chall//constexpr poly_t BITS = 64;//constexpr poly_t MOD = 0x4caa61b0d7fe5fa54189d46709eaba2d; // <- picked for 128-bit chall, C++ sucksconstexpr poly_t MOD = ((poly_t)0x4caa61b0d7fe5fa5 << 64) + 0x4189d46709eaba2d;constexpr poly_t BITS = 128;//const char prefix[] = "My crc64 is 0x";const char prefix[] = "My crc128 is 0x";const char suffix[] = "! Cool, isn\'t it?";constexpr size_t prefix_len = sizeof(prefix) - 1;constexpr size_t suffix_len = sizeof(suffix) - 1;
constexpr poly_t MASK = ((poly_t)1 << (BITS - 1) << 1) - 1; // can't do '(1 << BITS) - 1' because of the bitshift UBconstexpr size_t SETS_CNT = 2;poly_t set_fixup_left[SETS_CNT] = {    0x30, // 0 -> [0, 0, 1, 1, 0, 0, 0, 0]    0x60, // 1 -> [0, 1, 1, 0, 0, 0, 0, 0]};poly_t set_fixup_right[SETS_CNT] = {    0x0, // 0 -> [0, 0, 0, 0]    0x9, // 1 -> [1, 0, 0, 1]};poly_t set_var_coeff_left[SETS_CNT][4] = { // [set][var%4] -> bits if 1    {0x08,  // [0, 0, 0, 0, 1, 0, 0, 0]     0x04,  // [0, 0, 0, 0, 0, 1, 0, 0]     0x02,  // [0, 0, 0, 0, 0, 0, 1, 0]     0x01}, // [0, 0, 0, 0, 0, 0, 0, 1]    {0x00,  // [0, 0, 0, 0, 0, 0, 0, 0]     0x04,  // [0, 0, 0, 0, 0, 1, 0, 0]     0x02,  // [0, 0, 0, 0, 0, 0, 1, 0]     0x01}  // [0, 0, 0, 0, 0, 0, 0, 1]};
poly_t set_var_coeff_right[SETS_CNT][4] = { // [set][var%4] -> bits if 1    {0x08,  // [1, 0, 0, 0]     0x04,  // [0, 1, 0, 0]     0x02,  // [0, 0, 1, 0]     0x01}, // [0, 0, 0, 1]    {0x04,  // [0, 1, 0, 0]     0x00,  // [0, 0, 0, 0]     0x02,  // [0, 0, 1, 0]     0x03}  // [0, 0, 1, 1]};
poly_t crc(const uint8_t* buf, size_t buf_size, poly_t crc = MASK) {    for (size_t i = 0; i < buf_size; i++) {        crc ^= (poly_t)buf[i] << (BITS - 8);        for (int j = 0; j < 8; j++) {            if ((crc & ((poly_t)1 << (BITS - 1))) == 0)                crc = crc << 1;            else                crc = (crc << 1) ^ MOD;        }    }    return crc & MASK;}
bool verify(poly_t checksum) {    // slow and ugly, but this was used only for testing and debugging    char input[128] = { 0 };    strcat(input, prefix);    char fmt[16];    sprintf(fmt, "%%0%ullx", (int)BITS / 4);    sprintf(input + prefix_len, fmt, checksum);    strcpy(input + prefix_len + BITS / 4, suffix);    return crc((const uint8_t*)input, strlen(input)) == checksum;}
poly_t poly_bytes_mod(uint8_t* buf, size_t buf_size, poly_t mod) {    poly_t crc = 0;    assert(buf_size > BITS / 8);    size_t i;    for (i = 0; i < buf_size - BITS / 8; i++) {        crc ^= (poly_t)buf[i] << (BITS - 8);        for (int j = 0; j < 8; j++) {            if ((crc & ((poly_t)1 << (BITS - 1))) == 0)                crc = crc << 1;            else                crc = (crc << 1) ^ MOD;        }    }    for (size_t j = 0; j < BITS / 8; j++) {        crc ^= (poly_t)buf[i + j] << (BITS - 8 * (j + 1));    }    return crc & MASK;}
void poly_bytes_add_bit(uint8_t* buf, size_t buf_size, size_t pos) {    buf[buf_size - 1 - pos / 8] ^= (1 << (pos % 8));}
// Be careful: modifies `vars`!//__declspec(noinline)// TODO: hardcode vars count? - lol, makes the code slower...void poly_gauss(pair<poly_t, poly_t>* vars /*<weight, var_bit>*/,                size_t vars_cnt, poly_t expected_sum, size_t letters) {    size_t fixed = 0;    for (size_t col = 0; col < BITS; col++) {        bool found = false;        for (size_t row = fixed; row < vars_cnt; row++) {            if (vars[row].first & ((poly_t)1 << col)) {                swap(vars[fixed], vars[row]);                found = true;                break;            }        }        if (!found)            continue; // can't fully control this bit        pair<poly_t, poly_t> cur = vars[fixed];        for (size_t row = fixed + 1; row < vars_cnt; row++) {            if (vars[row].first & ((poly_t)1 << col)) {                vars[row].first ^= cur.first;                vars[row].second ^= cur.second;            }        }        fixed++;    }
    poly_t res_sum = 0;    poly_t res_vars = 0;    size_t row = 0;    for (size_t col = 0; col < BITS; col++) {        if ((expected_sum ^ res_sum) & ((poly_t)1 << col)) {            if (vars[row].first & ((poly_t)1 << col)) {                res_sum ^= vars[row].first;                res_vars ^= vars[row].second;            } else {                return;            }        }        if (vars[row].first & ((poly_t)1 << col)) {            row += 1;            if (row >= vars_cnt)                break;        }    }    assert(res_sum == expected_sum); // otherwise we'd have returned in the loop above
    assert(fixed > 0);    poly_t limit;    if (vars_cnt - fixed == 0)        limit = 1;    else        limit = ((poly_t)1 << (vars_cnt - fixed - 1)) << 1; // may overflow to 0, but without UB    for (poly_t i = 0;;) {        poly_t solution = res_vars;        for (poly_t bit = 0; bit < vars_cnt - fixed; bit++)            if (i & ((poly_t)1 << bit))                solution ^= vars[vars_cnt - 1 - bit].second;        // verify poly solution (it may not match the bruteforced ranges        bool ok = true;        for (poly_t nibble_pos = 0; nibble_pos < BITS / 4; nibble_pos++) {            int sol_vars = (solution >> (BITS - 4 - 4 * nibble_pos)) & 0xF;            if (letters & ((size_t)1 << nibble_pos)) {                // a-f                // the other bit endianness                // if (sol_vars != 0b1000 &&                //     sol_vars != 0b0100 &&                //     sol_vars != 0b1101 &&                //     sol_vars != 0b0011 &&                //     sol_vars != 0b1011 &&                //     sol_vars != 0b0111) {                //     ok = false;                //     break;                // }                if (sol_vars != 0b0001 &&                    sol_vars != 0b0010 &&                    sol_vars != 0b1011 &&                    sol_vars != 0b1100 &&                    sol_vars != 0b1101 &&                    sol_vars != 0b1110) {                    ok = false;                    break;                }
            } else {                // 0-9                if (sol_vars >= 10) {                    ok = false;                    break;                }                // the other bit endianness                // if (sol_vars != 0b0000 &&                //     sol_vars != 0b1000 &&                //     sol_vars != 0b0100 &&                //     sol_vars != 0b1100 &&                //     sol_vars != 0b0010 &&                //     sol_vars != 0b1010 &&                //     sol_vars != 0b0110 &&                //     sol_vars != 0b1110 &&                //     sol_vars != 0b0001 &&                //     sol_vars != 0b1001) {                //     ok = false;                //     break;                // }            }        }        if (ok) {            poly_t crc = 0;            for (poly_t nibble_pos = 0; nibble_pos < BITS / 4; nibble_pos++) {                size_t set_ind = !!(letters & ((size_t)1 << nibble_pos));                poly_t nibble = set_fixup_right[set_ind];                for (int j = 0; j < 4; j++)                    if (solution & ((poly_t)1 << (BITS - 1 - nibble_pos * 4 - j)))                        nibble ^= set_var_coeff_right[set_ind][j];                crc ^= nibble << (BITS - 4 * (nibble_pos + 1));            }            if (BITS <= 64) // otherwise ull is too small                assert(verify(crc));            if (BITS <= 64) {                char fmt[32];                sprintf(fmt, "Found: 0x%%0%ullx\n", (int)BITS / 4);                printf(fmt, crc);            } else {                char fmt[32];                sprintf(fmt, "Found: 0x%%0%ullx%%0%ullx\n", (int)BITS / 4 / 2, (int)BITS / 4 / 2);                printf(fmt, (uint64_t)(crc >> 64), uint64_t(crc));            }        }
        if (i == limit) // doing it this way to prevent UB on 1 << 64            break;        i++;    }}
poly_t set_weight[BITS / 4][SETS_CNT] = { 0 }; // [nibble_pos][let] -> coeff for Cpoly_t var_weight[BITS][SETS_CNT] = { 0 }; // [var][set] -> variable weightpoly_t C_base;
void solver(size_t start, size_t end) { // exclusive    for (size_t letters = start; letters < end; letters++) { // this bitshift won't overflow for the bitsizes we use        if (((letters - start) & 0x1FFFFF) == 0)            //printf("%zu/%zu...\n", letters, end - 1);            printf("%d%%...\n", int((letters - start) / (double)(end-start-1) * 100));
        poly_t C = C_base;        for (int i = 0; i < BITS / 4; i++)            C ^= set_weight[i][!!(letters & ((size_t)1 << i))];
        size_t vars_cnt = 0;        pair<poly_t, poly_t> vars[BITS]; // <weight, var_bit>        for (int var = 0; var < BITS; var++) {            int set = !!(letters & ((size_t)1 << var / 4));            vars[vars_cnt] = make_pair(var_weight[var][set], (poly_t)1 << (BITS - 1 - var));            vars_cnt++;        }
        poly_gauss(vars, vars_cnt, C, letters);    }}
int main(int argc, char* argv[]) {    // preprocess base C value    uint8_t tmp[prefix_len + BITS / 4 + suffix_len + BITS / 8] = { 0 };    memcpy(tmp, prefix, prefix_len);    memcpy(tmp + prefix_len + BITS / 4, suffix, suffix_len);    for (size_t i = 0; i < BITS / 8; i++)        tmp[i] ^= 0xFF;    C_base = poly_bytes_mod(tmp, sizeof(tmp), MOD);
    // preprocess set_weight    for (size_t nibble_pos = 0; nibble_pos < BITS / 4; nibble_pos++)        for (int set = 0; set < SETS_CNT; set++) {            uint8_t tmp[BITS / 4 + suffix_len + BITS / 8] = { 0 };            tmp[nibble_pos] ^= set_fixup_left[set];            if (nibble_pos % 2 == 0)                tmp[BITS / 4 + suffix_len + nibble_pos / 2] ^= (set_fixup_right[set] << 4);            else                tmp[BITS / 4 + suffix_len + nibble_pos / 2] ^= set_fixup_right[set];            set_weight[nibble_pos][set] = poly_bytes_mod(tmp, sizeof(tmp), MOD);        }
    // preprocess var_weight    for (size_t var = 0; var < BITS; var++)        for (int set = 0; set < SETS_CNT; set++) {            uint8_t tmp[BITS / 4 + suffix_len + BITS / 8] = { 0 };            tmp[var / 4] ^= set_var_coeff_left[set][var % 4];            if ((var / 4) % 2 == 0)                tmp[BITS / 4 + suffix_len + var / 4 / 2] ^= (set_var_coeff_right[set][var % 4] << 4);            else                tmp[BITS / 4 + suffix_len + var / 4 / 2] ^= set_var_coeff_right[set][var % 4];            var_weight[var][set] = poly_bytes_mod(tmp, sizeof(tmp), MOD);        }
    size_t threads_cnt;    if (argc <= 1) {        threads_cnt = 1;    } else {        threads_cnt = atoi(argv[1]);    }    printf("Running main loop with %zu threads...\n", threads_cnt);    std::vector<std::thread> threads;    size_t end = (size_t)1 << BITS / 4;    size_t step = (end + threads_cnt - 1) / threads_cnt;    for (size_t i = 0; i < threads_cnt; i++)        threads.emplace_back(solver, step * i, std::min(step * (i + 1), end));    for (auto& thread : threads)        thread.join();
    puts("Done!");}```