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:
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

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


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: 4g603013g6c415015065fb54g
target: 2c0394bc954d6f46dccfd2fc66e70fca
sol: g54c3e20af50gb0f04450bb601g
target: 081185140d5309872e2c9152b5684b56
sol: 0c616e70f67a67db12f0dfbfce22d3a
sol: c4ae6af4f54ab0bff777c1dd101055
target: 8edd0e72ca3465b1e6bcd4fb646ac16d
sol: fe7624b4fc566c42fc7e646d70e7gf5
target: d5e61c463501574c59cf3ef18a15a1c7
sol: 51c2g0fb5ff56acc0f7cb566fc012e
sol: 4b52520ca410c4afc21233ca5b1fbd1
target: afb79f7147a4783a33a81b41811e0a25
sol: 250a64d0dgd3g744664f55a4c34a2
target: d66b7418c733e5175d16cca9d1681c51
sol: 0352352003cf0b11gc4g1cdd77c0047
target: 8a343f23b6fb5c3620c3d350da93f1d7
sol: 01c2bb2a7a5e03a4gacc07d623be0deg
sol: fg13c63a6cdg10d3fe0f4cb606501
target: 59c2a566369fe6f42d4ec62643cd873d
sol: be56g2452603da3gd44d153fg6gc7ggb
target: 6ff772c9099f332d4f46a57353d87ba0
sol: gdbf3abebee1dca0d4552adf26647e
target: 69f9fec82326e2c20e4e920d8f052454
sol: a5a1cfc35f6527330f2fdba3g7eeca0
target: 25662a3d12cbe2c2cf0d00e89a7a8b50
sol: a302fce2c64gaffeec40c5f51a2cbc43
target: 1f1d2c64edb9895001eebe2f1e97df7d
sol: 30a33acb74cde0f6bgcg4g0f1fdc5
target: f311a6e46b59ce2afdd51435e5ccf011
sol: 41d5d76723b0722c77bc752eaag
target: d93b9d70621fecf07aa3a22ab4d406d7
sol: 1a5b5fgf464bg5bafb5d0b20ba
target: f1eb48f661dc50806cd800bc3ee84ab4
sol: gc0g4fdg2d5af62eca6465c11bb4g
target: 746ede465381378a27db5a0176cd6f08
sol: 2cecff36f77g66661dd630a7b6bd55f
target: 245f094fc9e38de2ea9b0d39ce9fb6be
sol: g2e7egf614fg6e00f0261dab133bcd4
target: a94bd44e369a514cfb03aa07b6c175c0
sol: 3fd31g2adede65dd36b1d6agcbgaa4
target: 2303b5cc906177dfe11b8cd7d8d2c19b
sol: 4fbbf4051c176bf2c467d7ged62f336
target: b83968606caf28d673d58dab4211bd7c
sol: fg660gf640g0c617c5c60f0feffcba
target: c7e2fc4c1933982cf3bbfca0f34cf774
sol: 507g26d765eee215e41c3c34b304a64
target: c3248a16f8d46815cb2c8e382a8c1e59
sol: eba6a23cbdbeg7541ce24cf7d222c
target: 0ac77e399bba7e406fba18d656eb68ac
sol: ba4aa67bfce3cd5fd0e3ce00d1b0eeb6 GOOD
target: 32d1b4f5a1f603fd98e80c4e29083948
sol: efe30fd016df421f7c467a7361d61
target: 409e8c361f7f41e0594b59ab7e9de4ba
sol: dee7d4cbc44f3g322d6ff01f52600bg
target: cd8f2dac4894d73fd42543eded294808
sol: e7effce0fdga245431a57d37ed
target: 70dfdc2585bb38a9efc4221410be092b
sol: 22a3ggef5dbf7cfd02gd567ad743c
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


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 #113 from 2021-12-03 17:05:54 (CET)