Google CTF 2017 Quals - Introspective CRC

0solve.py

'''
CRC is affine.
CRC(x) = L(x) + C, where L is linear.
We want CRC(x) = L(x) + C = x.
Write as L(x)+x = C.
Solve matrix equation.
'''

from sage.all import *

res = [None] * 82

CONST = 1021102219365466010738322
res[0] = 4402329568053044357841518
res[1] = 652462650701865447562368
res[2] = 4369145759738886008595303
res[3] = 2480322725602030768875470
res[4] = 3504337364566901180287596
res[5] = 4492055947069970831288629
res[6] = 3089508555006000235210244
res[7] = 1531125389201339528551566
res[8] = 1176648019828191878602387
res[9] = 4533670916488644166065306
res[10] = 3183955374751928179076504
res[11] = 4303124591420953202645797
res[12] = 1219458672930521212879946
res[13] = 3521677260187149121494147
res[14] = 1021102219365466010738326
res[15] = 1021102219365466010737298
res[16] = 1021102219365466010476178
res[17] = 1021102219365466077847186
res[18] = 1021102219365483190607506
res[19] = 1021102219369864057249426
res[20] = 1021102218239566103895698
res[21] = 1021101931135089859026578
res[22] = 1021176006341760848944786
res[23] = 1039991685296944591593106
res[24] = 723612442736140615112435
res[25] = 1852317898417064568664547
res[26] = 969155808624207308437923
res[27] = 742482596032282848806519
res[28] = 2154197729079946044161410
res[29] = 648036100669268898076370
res[30] = 666934752783312987730279
res[31] = 966794639034359563652102
res[32] = 1346953540247252200842103
res[33] = 218302412844807103027364
res[34] = 1691684737928954304794860
res[35] = 1139012733091695709028251
res[36] = 4052941992792522312156248
res[37] = 2052942769961202012537404
res[38] = 2149530574831885440521453
res[39] = 4000931163639271155048817
res[40] = 2357535689749561895600857
res[41] = 104965772635601781260188
res[42] = 3514374087227427657767586
res[43] = 1606239676235867280703382
res[44] = 2291422308517462666340119
res[45] = 4019839449630599976032377
res[46] = 251363856455415866684414
res[47] = 4686815195412971855444906
res[48] = 1021102219365466010738320
res[49] = 1021102219365466010737810
res[50] = 1021102219365466010607250
res[51] = 1021102219365465977183890
res[52] = 1021102219365474600672914
res[53] = 1021102219367665033993874
res[54] = 1021102218802516057317010
res[55] = 1021102075250277934882450
res[56] = 1021065325877318591635090
res[57] = 1030546952331205301165714
res[58] = 3438953858594724360150674
res[59] = 2799047788572004106284314
res[60] = 3561743988569803951188282
res[61] = 3448407093760358505404112
res[62] = 378724150034108489592602
res[63] = 1136799457497020025428658
res[64] = 3410633455859351564430680
res[65] = 993948433704610785294296
res[66] = 2541716746266957902021712
res[67] = 770816895700360977415561
res[68] = 34130868528435514685869
res[69] = 3533483238466385943087654
res[70] = 1328022495564497406784503
res[71] = 516991334942417818521797
res[72] = 2980710693000113191747485
res[73] = 3868705842258174243202387
res[74] = 2933671034983430374102151
res[75] = 903043225902278644682261
res[76] = 2116768851942252770139274
res[77] = 142671634563984641084944
res[78] = 2900614627552098051212896
res[79] = 3915920186082480366598615
res[80] = 825126553326313425012772
res[81] = 1530552403008155235290126

def tobin(x, n):
    return map(int, bin(x).lstrip("0b").rjust(n, "0"))

m = matrix(GF(2), 82, 82)
for i, v in enumerate(res):
    m.set_column(i, tobin(v ^ CONST, 82))
    m[i,i] -= 1
target = vector(GF(2), tobin(CONST, 82))

sol = m.solve_right(target)
print "".join(map(str, sol))

'''
$ nc -v selfhash.ctfcompetition.com 1337
selfhash.ctfcompetition.com [130.211.78.216] 1337 (?) open
Give me some data: 1010010010111000110111101011101001101011011000010000100001011100101001001100000000

CTF{i-hope-you-like-linear-algebra}
'''

1collect.py

from sock import Sock

for i in xrange(-1, 82):
    f = Sock("selfhash.ctfcompetition.com 1337")
    s = ["0"] * 82
    if i >= 0:
        s[i] = "1"
    s = "".join(s)
    f.send_line(s)
    f.read_until("Was:")
    f.read_line()
    v = f.read_line().strip().strip("L")
    v = int(v)
    if i >= 0:
        print "res[%d] = %d" % (i, v)
    else:
        print "CONST = %d" % v

2log.sh

$ time sage solve.py 
1010010010111000110111101011101001101011011000010000100001011100101001001100000000

real	0m1.205s
user	0m1.048s
sys	0m0.144s

$ nc -v selfhash.ctfcompetition.com 1337
selfhash.ctfcompetition.com [130.211.78.216] 1337 (?) open
Give me some data: 1010010010111000110111101011101001101011011000010000100001011100101001001100000000

CTF{i-hope-you-like-linear-algebra}