Dragon CTF 2021 - CRC Recursive Challenge
Writeups by other teams:
- https://mystiz.hk/posts/2021-11-29-dragonctf-crc/
- https://gist.github.com/sasdf/78fa4f4c9dc9db93534e4742b1de92e1
The challenge is pretty minimalistic (the code is running on the server):
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
# 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:
alpha = "0123456789abcdef"
matrix(GF(2), [
Bin(ord(v), 8).list
for v in alpha
]).rank()
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:
matrix(GF(2), [
Bin(ord(v), 8).list
for v in alpha if v not in "89"
]).rank()
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:
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
(128, 128, 128)
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:
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()
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:
(
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(),
)
(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):
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:
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!
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?
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:
# 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):
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:
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
# 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!
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?).