Skip to content

Instantly share code, notes, and snippets.

@hellman
Last active February 28, 2017 13:20
Show Gist options
  • Save hellman/e50c9404992591c686feb18132aac94f to your computer and use it in GitHub Desktop.
Save hellman/e50c9404992591c686feb18132aac94f to your computer and use it in GitHub Desktop.
Boston Key Party CTF 2016 - Supercomputer
from sage.all import *
import re
active_bits = [
0, 3, 4, 7, 8, 9, 10, 11, 14, 20, 21, 24, 25, 26,
35, 40, 41, 43, 45, 46, 47,
]
code = """
cnot(40, 34)
cnot(45, 0)
cnot(32, 20)
cnot(44, 47)
cnot(45, 10)
cnot(45, 24)
cnot(5, 28)
cnot(41, 15)
cnot(25, 12)
cnot(43, 25)
cnot(24, 9)
cnot(10, 37)
cnot(26, 37)
cnot(35, 11)
cnot(12, 19)
cnot(24, 5)
cnot(24, 9)
cnot(0, 43)
cnot(45, 33)
cnot(11, 42)
cnot(34, 35)
cnot(3, 44)
cnot(25, 21)
cnot(4, 18)
cnot(10, 43)
cnot(21, 39)
cnot(39, 20)
cnot(24, 45)
cnot(46, 0)
cnot(47, 16)
cnot(35, 24)
cnot(19, 14)
cnot(38, 17)
cnot(13, 38)
cnot(5, 24)
cnot(19, 10)
cnot(6, 41)
cnot(3, 26)
cnot(43, 37)
cnot(45, 46)
cnot(40, 6)
cnot(10, 27)
cnot(37, 1)
cnot(18, 42)
cnot(37, 25)
cnot(20, 32)
cnot(37, 3)
cnot(34, 40)
cnot(13, 35)
cnot(7, 6)
cnot(28, 16)
cnot(40, 35)
cnot(35, 5)
cnot(14, 42)
cnot(46, 34)
cnot(7, 43)
cnot(38, 42)
cnot(32, 30)
cnot(27, 16)
cnot(1, 21)
cnot(35, 13)
cnot(33, 34)
cnot(10, 28)
cnot(23, 45)
cnot(8, 13)
cnot(21, 31)
cnot(16, 40)
cnot(37, 20)
cnot(3, 32)
cnot(28, 29)
cnot(15, 10)
cnot(19, 47)
cnot(6, 36)
cnot(4, 34)
cnot(23, 19)
cnot(19, 12)
cnot(40, 18)
cnot(38, 19)
cnot(16, 3)
cnot(22, 26)
cnot(11, 44)
cnot(6, 16)
cnot(1, 0)
cnot(0, 10)
cnot(42, 9)
cnot(21, 6)
cnot(42, 31)
cnot(32, 6)
cnot(11, 22)
cnot(36, 44)
cnot(9, 8)
cnot(45, 1)
cnot(26, 27)
cnot(16, 13)
cnot(36, 33)
cnot(42, 26)
cnot(28, 18)
cnot(27, 21)
cnot(16, 31)
cnot(1, 41)
cnot(19, 46)
cnot(34, 16)
cnot(11, 47)
cnot(9, 47)
cnot(42, 12)
cnot(46, 13)
cnot(3, 45)
cnot(3, 36)
cnot(25, 37)
cnot(0, 3)
cnot(0, 36)
cnot(22, 27)
cnot(46, 0)
cnot(32, 46)
cnot(36, 17)
cnot(20, 39)
cnot(34, 17)
cnot(2, 35)
cnot(23, 42)
cnot(29, 35)
cnot(34, 29)
cnot(41, 33)
cnot(33, 22)
cnot(15, 34)
cnot(34, 25)
cnot(20, 28)
cnot(39, 38)
cnot(10, 23)
cnot(35, 31)
cnot(41, 28)
cnot(32, 0)
cnot(47, 30)
cnot(33, 12)
cnot(2, 22)
cnot(26, 24)
cnot(44, 21)
cnot(38, 43)
cnot(46, 30)
cnot(26, 29)
cnot(19, 36)
cnot(14, 42)
cnot(41, 0)
cnot(16, 31)
cnot(27, 22)
cnot(30, 26)
cnot(11, 4)
cnot(13, 31)
cnot(16, 10)
cnot(3, 11)
cnot(20, 33)
cnot(23, 14)
cnot(30, 21)
cnot(41, 29)
cnot(43, 37)
cnot(7, 24)
cnot(13, 12)
cnot(19, 42)
cnot(34, 9)
cnot(34, 8)
cnot(40, 23)
cnot(23, 36)
cnot(6, 45)
cnot(19, 26)
cnot(13, 28)
cnot(35, 36)
cnot(19, 2)
cnot(10, 36)
cnot(3, 15)
cnot(0, 20)
cnot(32, 20)
cnot(10, 41)
cnot(6, 11)
cnot(43, 26)
cnot(23, 5)
cnot(28, 17)
cnot(4, 15)
cnot(37, 43)
cnot(37, 22)
cnot(46, 21)
cnot(47, 33)
cnot(24, 15)
cnot(27, 35)
cnot(2, 1)
cnot(39, 0)
cnot(36, 13)
cnot(0, 1)
cnot(18, 25)
cnot(11, 47)
cnot(10, 25)
cnot(13, 21)
cnot(8, 33)
cnot(30, 21)
cnot(22, 29)
cnot(35, 24)
cnot(18, 38)
cnot(6, 25)
cnot(40, 37)
cnot(10, 32)
cnot(20, 23)
cnot(4, 33)
cnot(14, 31)
cnot(3, 22)
cnot(17, 21)
cnot(4, 13)
cnot(36, 14)
cnot(45, 8)
cnot(47, 43)
cnot(14, 40)
cnot(4, 46)
cnot(47, 13)
cnot(5, 47)
cnot(39, 20)
cnot(45, 39)
cnot(31, 7)
cnot(16, 40)
cnot(3, 43)
cnot(20, 43)
cnot(24, 2)
cnot(3, 35)
cnot(21, 46)
cnot(20, 24)
cnot(24, 22)
cnot(15, 34)
cnot(26, 11)
cnot(31, 30)
cnot(2, 14)
cnot(39, 34)
cnot(35, 43)
cnot(4, 18)
cnot(15, 20)
cnot(36, 17)
cnot(16, 5)
cnot(46, 45)
cnot(5, 6)
cnot(41, 17)
cnot(20, 19)
cnot(16, 12)
cnot(30, 9)
cnot(45, 4)
cnot(22, 37)
cnot(33, 30)
cnot(12, 23)
cnot(23, 32)
cnot(32, 37)
cnot(39, 28)
cnot(3, 23)
cnot(41, 43)
cnot(15, 33)
cnot(26, 1)
cnot(19, 26)
cnot(36, 7)
cnot(31, 18)
cnot(17, 23)
cnot(26, 34)
cnot(18, 39)
cnot(35, 12)
cnot(28, 1)
cnot(10, 20)
cnot(8, 44)
cnot(19, 5)
cnot(44, 13)
cnot(4, 19)
cnot(10, 40)
cnot(22, 34)
cnot(31, 16)
cnot(13, 19)
cnot(25, 19)
cnot(12, 10)
cnot(27, 37)
cnot(44, 21)
cnot(47, 23)
cnot(9, 25)
cnot(27, 15)
cnot(9, 12)
cnot(41, 43)
cnot(21, 4)
cnot(20, 5)
cnot(15, 41)
cnot(31, 32)
cnot(35, 34)
cnot(1, 38)
cnot(16, 20)
cnot(43, 23)
cnot(27, 25)
cnot(29, 17)
cnot(8, 9)
cnot(13, 0)
cnot(16, 7)
cnot(43, 45)
cnot(6, 10)
cnot(43, 22)
cnot(1, 8)
cnot(18, 36)
cnot(30, 5)
cnot(32, 26)
cnot(34, 20)
cnot(28, 47)
cnot(46, 8)
cnot(22, 20)
cnot(16, 1)
cnot(38, 47)
cnot(5, 6)
cnot(45, 22)
cnot(40, 8)
cnot(2, 36)
cnot(27, 16)
cnot(7, 2)
cnot(46, 0)
cnot(37, 6)
cnot(36, 4)
cnot(27, 17)
cnot(19, 37)
cnot(1, 31)
cnot(4, 43)
cnot(30, 43)""".strip()
def comp(bits):
bits = list(bits)
for line in code.splitlines():
if "cnot" in line:
src, dst = map(int, re.findall(r"\d+", line))
bits[dst] ^= bits[src]
return bits
def tobin(x, n):
return tuple(map(int, bin(x).lstrip("0b").rjust(n, "0")))
def frombin(v):
return int("".join(map(str, v)), 2 )
m = matrix(GF(2), 48, 48)
vals = []
for x in xrange(48):
v = [0] * 48
if x in active_bits:
v[x] = 1
v = comp(v)
vals.append(frombin(v))
m.set_column(x, v)
if 0: # 2^21 exhaustion
mx = 0
for vs in Combinations(vals):
res = 0
for v in vs:
res ^= v
mx = max(mx, res)
print mx
else: # linear algebra solution
prefix = []
for bit in xrange(48):
mat = m[:bit+1]
vec = vector(GF(2), prefix + [1])
try:
mat.solve_right(vec)
except Exception as err:
prefix.append(0)
else:
prefix.append(1)
print frombin(prefix)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment