affine.group home writeups about

Dragon CTF 2021 - CRC Recursive Challenge

Published on 28 Nov 2021
Writeups

Writeups by other teams:


The challenge is pretty minimalistic (the code is running on the server):

In [1]:
def crc128(buf, crc=0xffffffffffffffffffffffffffffffff):
    for val in buf:
        crc ^= val << 120
        for _ in range(8):
            crc <<= 1
            if crc & 2**128:
                crc ^= 0x14caa61b0d7fe5fa54189d46709eaba2d
    return crc

inp = input().strip().encode()
crc = crc128(inp)
if inp == f'My crc128 is 0x{crc:032x}! Cool, isn\'t it?'.encode():
    with open('flag.txt', 'r') as f:
        print(f.read().strip())
else:
    print('Nope!')

Here we have a 128-bit CRC and we need to find a 128-bit value $C$ such that the CRC of the string "My crc128 is 0x<C in hexadecimal>! Cool, isn't it?" is equal to $C$! A sort of hashquine.

The beginning

In [2]:
# setup
from sage.all import *  # python mode
from binteger import Bin
N = 128
def run(crc):
    if isinstance(crc, int):
        crc = "%032x" % crc
    crc = "".join(crc)
    assert len(crc) == 32
    inp = f'My crc128 is 0x{crc}! Cool, isn\'t it?'.encode()
    return Bin(crc128(inp), N).vector

CRC is linear, so should be solvable as a simple linear system, right?..

That would be the case! If $C$ was plugged in the raw representation in the string (or any other linear function of that). Hexdigits however do not form a 4-dimensional linear space:

In [3]:
alpha = "0123456789abcdef"
matrix(GF(2), [
    Bin(ord(v), 8).list
    for v in alpha
]).rank()
Out [3]:
6

Finding preimages (optional)

In fact, 5 dimensions would work since 1 dimension can be chopped for a constant (a non-trivial coset of a 4-dimensional affine space lies in a 5-dimensional linear space). This can be achieved by excluding 8 and 9:

In [4]:
matrix(GF(2), [
    Bin(ord(v), 8).list
    for v in alpha if v not in "89"
]).rank()
Out [4]:
5

This means that we can find preimages not having 8 or 9 in hex by solving the linear system (prob. ~1.3%) (or by guessing their positions, which has low entropy). To do this, we introduce 4 variables per input digit, and define the linear map from them to the set 0-7a-f. The map can be seen clearly by aligning 3 LSBs between 0-7 and a-f, and letting the MSB to switch 00110 to 01100:

0 ascii:0110 000
8 ascii:0111 000 (BAD)

1 ascii:0110 001
a ascii:1100 001

2 ascii:0110 010
b ascii:1100 010

3 ascii:0110 011
c ascii:1100 011

4 ascii:0110 100
d ascii:1100 100

5 ascii:0110 101
e ascii:1100 101

6 ascii:0110 110
f ascii:1100 110

7 ascii:0110 111
9 ascii:0111 001 (BAD)

An implementation:

In [5]:
mat = []

zero = run("0" * (N//4))
for i in range(N//4):
    test = list("0" * (N//4))
    for j in range(4):
        if j == 0:
            test[i] = chr(0b1100_000)
        else:
            test[i] = chr(0b110_000 + 2**(2-(j-1)))
        mat.append(run(test) + zero)

mat = matrix(GF(2), mat)
mat.nrows(), mat.ncols(), mat.rank()
# crc = mat * x + zero
Out [5]:
(128, 128, 128)

In [6]:
for i in range(32):
    crc = Bin(os.urandom(N//8)).vector
    print("target:", Bin(crc).hex)

    sol = mat.solve_left(zero + crc)  
    msg = ""
    for c in Bin(sol).split(n=4):
        v = 0b1100_000 if c[0] else 0b110_000
        v += c[1:4].int
        msg += chr(v)
    good = "GOOD" if set(msg) <= set("0123456789abcdef") else ""
    assert Bin(run(msg)).vector == crc
    print("   sol:", msg, good)
target: 3d542f7fa173707f64794456315e1e37
   sol: 4g60`30`13g6`c415`0150`65f`b5`4g 
target: 2c0394bc954d6f46dccfd2fc66e70fca
   sol: g5`4c3e20af`50`gb0f04450bb60`1`g 
target: 081185140d5309872e2c9152b5684b56
   sol: 0c616e70f67a67db12f0dfbfce22d`3a 
target: 6cc706b713fe4412eb03ad9fdfef5ee1
   sol: c4`ae6af4f54ab0bff777c1dd101`055 
target: 8edd0e72ca3465b1e6bcd4fb646ac16d
   sol: fe7624b4fc566c42fc7e646d70e`7gf5 
target: d5e61c463501574c59cf3ef18a15a1c7
   sol: 51c2g0fb5ff56a`cc0f7cb5`66fc012e 
target: c8ae9ae4af12fe0052ab80a2ad2aa37c
   sol: 4b52520ca4`10c4afc21233ca5b1fbd1 
target: afb79f7147a4783a33a81b41811e0a25
   sol: 250a6`4d0dgd3g7`44664f55a4c`34a2 
target: d66b7418c733e5175d16cca9d1681c51
   sol: 035`2352003cf0b11gc4g1cdd77c0047 
target: 8a343f23b6fb5c3620c3d350da93f1d7
   sol: 01c2bb2a7a5e03a4gacc07d623be0deg 
target: 0d79bf96a038037a09fd7ed5ad0505bf
   sol: `fg13c63`a6cdg1`0d3fe0f4cb606501 
target: 59c2a566369fe6f42d4ec62643cd873d
   sol: be56g2452603da3gd44d153fg6gc7ggb 
target: 6ff772c9099f332d4f46a57353d87ba0
   sol: gdbf`3abebee1d`ca0d4552adf26647e 
target: 69f9fec82326e2c20e4e920d8f052454
   sol: a`5a1cfc35f6527330f2fdba3g7eeca0 
target: 25662a3d12cbe2c2cf0d00e89a7a8b50
   sol: a302fce2c64gaffeec40c5f51a2cbc43 
target: 1f1d2c64edb9895001eebe2f1e97df7d
   sol: 3``0a33acb7`4cde0f6bgcg4g0f1fdc5 
target: f311a6e46b59ce2afdd51435e5ccf011
   sol: 41d5`d`76`723b0722c77bc752e`aag` 
target: d93b9d70621fecf07aa3a22ab4d406d7
   sol: 1`a5b5`fgf`464bg5`bafb5`d0b20`ba 
target: f1eb48f661dc50806cd800bc3ee84ab4
   sol: gc0g4fdg2d5af62eca6`465c11bb`4`g 
target: 746ede465381378a27db5a0176cd6f08
   sol: 2cecff36f77g66661dd63`0a7b6bd55f 
target: 245f094fc9e38de2ea9b0d39ce9fb6be
   sol: g2e7egf614fg6e00f0261dab`133bcd4 
target: a94bd44e369a514cfb03aa07b6c175c0
   sol: 3fd31g2adede65`dd36b1d6a`gcbgaa4 
target: 2303b5cc906177dfe11b8cd7d8d2c19b
   sol: 4fbbf4051c176bf2c467d7ge`d62f336 
target: b83968606caf28d673d58dab4211bd7c
   sol: fg660gf640g0c61`7c5c`60f0feffcba 
target: c7e2fc4c1933982cf3bbfca0f34cf774
   sol: 507g26d765eee21`5e41c3c34b304a64 
target: c3248a16f8d46815cb2c8e382a8c1e59
   sol: e`ba6a23cbdbeg7541ce24c``f7d222c 
target: 0ac77e399bba7e406fba18d656eb68ac
   sol: ba4aa67bfce3cd5fd0e3ce00d1b0eeb6 GOOD
target: 32d1b4f5a1f603fd98e80c4e29083948
   sol: efe30fd016df421`f7`c467a7361d61` 
target: 409e8c361f7f41e0594b59ab7e9de4ba
   sol: dee7d4cbc44f3g322d6ff01f52600b`g 
target: cd8f2dac4894d73fd42543eded294808
   sol: e7e`f`fce``0fd``ga245431a57d37ed 
target: 70dfdc2585bb38a9efc4221410be092b
   sol: 22a3ggef5dbf7cfd02gd5`67ad`7`43c 
target: f30c082c3aacee570f11225fe6e991fd
   sol: 00e4cc552dfbf03b013gc3b1gg570c27 

Back to quine

Unfortunately, this method does not work for the challenge: our 4 variables map well to binary representation of the ASCII code, but does not relate linearly to the binary representation of the digit itself:

In [7]:
def ext(v):
    return Bin.concat(
        Bin(v, 4),
        Bin(ord("%01x" % v), 8)
    ).vector

matrix(GF(2), [
    ext(v)
    for v in [0,1,2,3,4,5,6,7,10,11,12,13,14,15]
]).rank()
Out [7]:
7

What to do?

It is rather obvious that the hex digits split nicely into two groups (by their ASCII codes): 0123456789 and abcdef. If we know the group for each digit in the answer, the problem becomes linear:

In [8]:
(
matrix(GF(2), [ext(v) for v in [0,1,2,3,4,5,6,7,8,9]]).rank(),
matrix(GF(2), [ext(v) for v in [10,11,12,13,14,15]]).rank(),
)
Out [8]:
(5, 5)

The natural solution is to bruteforce all possible group patterns : $2^{32}$ possible, solve the linear system for each of them, and check that the solution works.

This is the intended solution by the author (@dsredford), who implemented it in C++ with Gaussian elimination written from scratch using 128-bit integers.

In SageMath however, this solution would take quite long, as generic linear algebra is not as fast. Let's try to improve it.

Smart enumeration

It can be noted that the split 0-9 a-f has less entropy than 1 bit: the group 0-9 has higher chances. Here we assume that the final solution is like uniformly random.

Therefore, we can first enumerate patterns which have more group 0-9 than a-f. Let's look at our chances (assuming there is 1 "random" solution):

In [9]:
p = 10/16
for l in range(33):
    success = sum(binomial(32,i) * p**(32-i) * (1-p)**i for i in range(l+1))
    nvecs = sum(binomial(32,i) for i in range(l+1))
    print(f"up to length {l:2d}: success {success*100:5.1f}% vectors 2^{math.log(nvecs, 2):.1f}")
up to length  0: success   0.0% vectors 2^0.0
up to length  1: success   0.0% vectors 2^5.0
up to length  2: success   0.0% vectors 2^9.0
up to length  3: success   0.0% vectors 2^12.4
up to length  4: success   0.2% vectors 2^15.3
up to length  5: success   0.6% vectors 2^17.9
up to length  6: success   1.9% vectors 2^20.1
up to length  7: success   4.6% vectors 2^22.1
up to length  8: success   9.8% vectors 2^23.8
up to length  9: success  18.1% vectors 2^25.4
up to length 10: success  29.6% vectors 2^26.7
up to length 11: success  43.4% vectors 2^27.8
up to length 12: success  57.8% vectors 2^28.8
up to length 13: success  71.1% vectors 2^29.6
up to length 14: success  82.0% vectors 2^30.3
up to length 15: success  89.8% vectors 2^30.8
up to length 16: success  94.8% vectors 2^31.2
up to length 17: success  97.6% vectors 2^31.5
up to length 18: success  99.0% vectors 2^31.7
up to length 19: success  99.6% vectors 2^31.8
up to length 20: success  99.9% vectors 2^31.9
up to length 21: success 100.0% vectors 2^32.0
up to length 22: success 100.0% vectors 2^32.0
up to length 23: success 100.0% vectors 2^32.0
up to length 24: success 100.0% vectors 2^32.0
up to length 25: success 100.0% vectors 2^32.0
up to length 26: success 100.0% vectors 2^32.0
up to length 27: success 100.0% vectors 2^32.0
up to length 28: success 100.0% vectors 2^32.0
up to length 29: success 100.0% vectors 2^32.0
up to length 30: success 100.0% vectors 2^32.0
up to length 31: success 100.0% vectors 2^32.0
up to length 32: success 100.0% vectors 2^32.0

So, we have a 58% chance to solve it with "only" $2^{28}$ (one/16th of the full search!).

But can we improve it further? Let's check maximum-sized subset of digits having rank 5:

In [10]:
for l in range(10, 15):
    for digits in Combinations(range(16), l):
        rk = matrix(GF(2), [ext(v) for v in digits]).rank()
        if rk <= 5:
            print(l, digits, rk)
10 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 5
10 [0, 1, 2, 3, 4, 5, 6, 7, 10, 14] 5
10 [0, 1, 2, 3, 4, 5, 6, 7, 11, 13] 5
10 [0, 1, 2, 3, 4, 5, 6, 7, 11, 15] 5
10 [0, 1, 2, 3, 4, 5, 6, 7, 13, 15] 5
10 [0, 1, 2, 3, 4, 5, 6, 11, 13, 15] 5
10 [0, 1, 2, 3, 4, 5, 7, 11, 13, 15] 5
10 [0, 1, 2, 3, 4, 6, 7, 11, 13, 15] 5
10 [0, 1, 2, 3, 5, 6, 7, 11, 13, 15] 5
10 [0, 1, 2, 4, 5, 6, 7, 11, 13, 15] 5
10 [0, 1, 3, 4, 5, 6, 7, 11, 13, 15] 5
10 [0, 2, 3, 4, 5, 6, 7, 11, 13, 15] 5
10 [1, 2, 3, 4, 5, 6, 7, 11, 13, 15] 5
11 [0, 1, 2, 3, 4, 5, 6, 7, 11, 13, 15] 5

We can slightly improve the chances, by using the (unique) split 11-5!

In [11]:
p = 11/16
for l in range(33):
    success = sum(binomial(32,i) * p**(32-i) * (1-p)**i for i in range(l+1))
    nvecs = sum(binomial(32,i) for i in range(l+1))
    print(f"up to length {l:2d}: success {success*100:5.1f}% vectors 2^{math.log(nvecs, 2):.1f}")
up to length  0: success   0.0% vectors 2^0.0
up to length  1: success   0.0% vectors 2^5.0
up to length  2: success   0.1% vectors 2^9.0
up to length  3: success   0.4% vectors 2^12.4
up to length  4: success   1.3% vectors 2^15.3
up to length  5: success   3.7% vectors 2^17.9
up to length  6: success   8.7% vectors 2^20.1
up to length  7: success  17.1% vectors 2^22.1
up to length  8: success  29.0% vectors 2^23.8
up to length  9: success  43.4% vectors 2^25.4
up to length 10: success  58.5% vectors 2^26.7
up to length 11: success  72.2% vectors 2^27.8
up to length 12: success  83.1% vectors 2^28.8
up to length 13: success  90.7% vectors 2^29.6
up to length 14: success  95.4% vectors 2^30.3
up to length 15: success  97.9% vectors 2^30.8
up to length 16: success  99.2% vectors 2^31.2
up to length 17: success  99.7% vectors 2^31.5
up to length 18: success  99.9% vectors 2^31.7
up to length 19: success 100.0% vectors 2^31.8
up to length 20: success 100.0% vectors 2^31.9
up to length 21: success 100.0% vectors 2^32.0
up to length 22: success 100.0% vectors 2^32.0
up to length 23: success 100.0% vectors 2^32.0
up to length 24: success 100.0% vectors 2^32.0
up to length 25: success 100.0% vectors 2^32.0
up to length 26: success 100.0% vectors 2^32.0
up to length 27: success 100.0% vectors 2^32.0
up to length 28: success 100.0% vectors 2^32.0
up to length 29: success 100.0% vectors 2^32.0
up to length 30: success 100.0% vectors 2^32.0
up to length 31: success 100.0% vectors 2^32.0
up to length 32: success 100.0% vectors 2^32.0

Now, we may succeed with 58% after $2^{26.7}$ patterns (less than 1/32th of the full search). Still, this amount of checks would take core-days using SageMath's linear algebra...

Feeling lucky

After implementing it and starting the search... the answer popped up just in 2 minutes! The number of patterns of the "bad" group of size 5 is ... just 4! This corresponds to the success rate 1.3%!

Who is lucky today?

DrgnS{I_b3t_hellman_wi11_juST_LLL_ThiS...}

Of course, Lucky Linear aLgebra here ;)

Feeling not lucky

This should definitely work well for the 64-bit version, right?

In [12]:
p = 11/16
for l in range(17):
    success = sum(binomial(16,i) * p**(16-i) * (1-p)**i for i in range(l+1))
    nvecs = sum(binomial(16,i) for i in range(l+1))
    print(f"up to length {l:2d}: success {success*100:5.1f}% vectors 2^{math.log(nvecs, 2):.1f}")
up to length  0: success   0.2% vectors 2^0.0
up to length  1: success   2.1% vectors 2^4.1
up to length  2: success   8.2% vectors 2^7.1
up to length  3: success  21.3% vectors 2^9.4
up to length  4: success  40.7% vectors 2^11.3
up to length  5: success  61.8% vectors 2^12.7
up to length  6: success  79.4% vectors 2^13.9
up to length  7: success  90.8% vectors 2^14.7
up to length  8: success  96.7% vectors 2^15.3
up to length  9: success  99.0% vectors 2^15.6
up to length 10: success  99.8% vectors 2^15.8
up to length 11: success 100.0% vectors 2^15.9
up to length 12: success 100.0% vectors 2^16.0
up to length 13: success 100.0% vectors 2^16.0
up to length 14: success 100.0% vectors 2^16.0
up to length 15: success 100.0% vectors 2^16.0
up to length 16: success 100.0% vectors 2^16.0

Well, the answer is 7a8abd9a85eed3b9, which has 9 out of 16 digits in the "bad" group (89ace)! This means that checking length up to 8 is not enough, although it has the success rate of 96.7%! The attack fails with fail rate 3.3%...

Who is unlucky today?

Luckily, for N=64 we can also use a meet-in-the-middle style attack by computing crc-self-difference for all possible values of the left half and of the right half ($2^{32}$ values each) and finding the intersection (32 GiB data each), e.g. through sorting and merging. But this is another story...

(Well, the attack does not really fail for N=64, enumerating the full space of $2^{16}$ patterns takes just a few minutes even in SageMath)

Implementation

Preparing the two bases:

In [13]:
# digits
inds0 = 0, 1, 2, 3, 4, 5, 6, 7, 11, 13, 15
inds1 = 8, 9, 10, 12, 14

# pivots
piv0 = 1, 2, 4, 11
piv1 = 9, 10, 12, 14

mat = matrix(GF(2), [
    ext(i) + ext(inds0[0])
    for i in piv0
])
expr0 = {inds0[0]: (0, 0, 0, 0)}
for v in inds0[1:]:
    t = ext(v) + ext(inds0[0])
    expr0[v] = tuple(map(int, mat.solve_left(t)))
    print("%2d" % v, expr0[v], t)
print()

mat = matrix(GF(2), [
    ext(i) + ext(inds1[0])
    for i in piv1
])
expr1 = {inds1[0]: (0, 0, 0, 0)}
for v in inds1[1:]:
    t = ext(v) + ext(inds1[0])
    expr1[v] = tuple(map(int, mat.solve_left(t)))
    print("%2d" % v, expr1[v], t)
print()

expr0set = set(map(tuple, expr0.values()))
expr1set = set(map(tuple, expr1.values()))
expr0inv = {v: k for k, v in expr0.items()}
expr1inv = {v: k for k, v in expr1.items()}
 1 (1, 0, 0, 0) (0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1)
 2 (0, 1, 0, 0) (0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0)
 3 (1, 1, 0, 0) (0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1)
 4 (0, 0, 1, 0) (0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0)
 5 (1, 0, 1, 0) (0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1)
 6 (0, 1, 1, 0) (0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0)
 7 (1, 1, 1, 0) (0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1)
11 (0, 0, 0, 1) (1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0)
13 (0, 1, 1, 1) (1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0)
15 (0, 0, 1, 1) (1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0)

 9 (1, 0, 0, 0) (0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1)
10 (0, 1, 0, 0) (0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1)
12 (0, 0, 1, 0) (0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1)
14 (0, 0, 0, 1) (0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1)

Preparing matrices and zeros (compute CRC(x) + x, we'll aim to match 0):

In [14]:
mat0 = []
mat1 = []

zero = run(0)
zeros0 = []
zeros1 = []
for i in range(N//4):
    test = [0] * N
    test[i*4:i*4+4] = Bin(inds0[0], 4).list
    vec = run(Bin(test, N).int) + zero + vector(GF(2), Bin(test, N).tuple)
    zeros0.append(vec)
    zerotest0 = test
    assert not vec

    test = [0] * N
    test[i*4:i*4+4] = Bin(inds1[0], 4).list
    vec = run(Bin(test, N).int) + zero + vector(GF(2), Bin(test, N).tuple)
    zeros1.append(vec)
    zerotest1 = test

    for j in range(4):
        test = [0] * N
        test[i*4:i*4+4] = Bin(piv0[j], 4).list
        vec = run(Bin(test, N).int) + zeros0[-1] + zero + vector(GF(2), Bin(test, N).tuple)
        mat0.append(vec)

        test = [0] * N
        test[i*4:i*4+4] = Bin(piv1[j], 4).list
        vec = run(Bin(test, N).int) + zeros1[-1] + zero + vector(GF(2), Bin(test, N).tuple)
        mat1.append(vec)

mat0 = matrix(GF(2), mat0)
mat1 = matrix(GF(2), mat1)

Example computation of CRC self-difference using matrices:

In [15]:
msg = int(os.urandom(N // 8).hex(), 16)

crc_selfdiff = run(msg) + vector(GF(2), Bin(msg, N).tuple)

test = zero
x = []
mixmat = []
for i, c in enumerate(Bin(msg, N).split(n=4)):
    if c.int in inds0:
        test += zeros0[i]  # actually zero
        x += list(expr0[c.int])
        mixmat.extend(list(mat0[i*4:i*4+4]))
    else:
        test += zeros1[i]
        x += list(expr1[c.int])
        mixmat.extend(list(mat1[i*4:i*4+4]))

test += vector(GF(2), x) * matrix(GF(2), mixmat)

print("crc     ", Bin(crc_selfdiff).hex)
print("test    ", Bin(test).hex)
crc      23f060cf4d695d5a572add4d6b24bde6
test     23f060cf4d695d5a572add4d6b24bde6

In [16]:
# optimized matrix construction through addition of matrices
# faster than operating on columns...
mat_base = mat0.transpose()
mat_diff = (mat1 - mat0).transpose()
diff_cols = []
for i in range(0, N, 4):
    tmp = copy(mat_diff)
    for j in range(N):
        if j not in range(i, i+4):
            tmp.rescale_col(j, 0)
    diff_cols.append(tmp)

Run!

In [17]:
itr = 0
for l in range(N//4+1):
    print("checked", itr, "starting length", l)

    # inds : indices of 5-sized groups
    for inds in Combinations(range(N//4), l):
        itr += 1

        target = zero
        mat = mat_base
        for i in inds:
            target += zeros1[i]
            mat += diff_cols[i]

        try:
            base_sol = mat.solve_right(target)
        except:
            continue

        for z in mat.right_kernel():
            sol = base_sol + z

            tsol = tuple(sol)
            for i in range(0, len(tsol), 4):
                t = tsol[i:i+4]
                if (i//4) in inds:
                    if t not in expr1set:
                        break
                else:
                    if t not in expr0set:
                        break
            else:
                print("solved!", l, inds, "checked", itr)
                print(sol)
                ans = ""
                for i in range(0, len(sol), 4):
                    v = Bin(sol[i:i+4])
                    if (i//4) in inds:
                        ans += "%01x" % expr1inv[v.tuple]
                    else:
                        ans += "%01x" % expr0inv[v.tuple]
                print("ans", ans)
                inp = f'My crc128 is 0x{ans}! Cool, isn\'t it?'
                print(inp)
                print("crc:", Bin(crc128(inp.encode())).hex)
                done
checked 0 starting length 0
checked 1 starting length 1
checked 33 starting length 2
checked 529 starting length 3
checked 5489 starting length 4
solved! 4 [15, 21, 23, 30] checked 39480
(0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0)
ans bdff2602f344773ef23fd85a545253c3
My crc128 is 0xbdff2602f344773ef23fd85a545253c3! Cool, isn't it?
crc: bdff2602f344773ef23fd85a545253c3
NameError: name 'done' is not defined

Aftermath

@dsredford shared all the 3 solutions to the 128-bit challenge:

My crc128 is 0xab3c66f8aa682e07c2828cff7aef5e65! Cool, isn't it?
My crc128 is 0xbf7040487b3ec44d7cb94a1e01873a4c! Cool, isn't it?
My crc128 is 0xbdff2602f344773ef23fd85a545253c3! Cool, isn't it?

We can see that they have 14, 10 and 4 "bad" chars respectively. Extrapolating the time to solve (39480 iterations in 2m 16s), we get timings to find each of the answers:

up to length  4: success   1.3% vectors 2^15.3  estimated time: 2m 16s
...
up to length 10: success  58.5% vectors 2^26.7  estimated time: 104 hours
...
up to length 14: success  95.4% vectors 2^30.3  estimated time: 53 days
...
up to length 32: success 100.0% vectors 2^32.0  estimated time: 171 days

With a few threads the 10-bad solution could be doable during the CTF (58.5% success), but to go beyond that an optimized linear algebra implementation (e.g. in C++) is clearly necessary (or, perhaps, a GPU?).

Site version #146 from 2023-11-26 21:16:45 (CET)