Skip to content

Instantly share code, notes, and snippets.

@hellman
Created May 4, 2020 09:01
Show Gist options
  • Save hellman/e1531a40361fa432db64290189e0cfaa to your computer and use it in GitHub Desktop.
Save hellman/e1531a40361fa432db64290189e0cfaa to your computer and use it in GitHub Desktop.
De1CTF 2020 - NLFSR
from sage.all import *
ma, mb, mc, md = 0x505a1, 0x40f3f, 0x1f02, 0x31
maxa = maxb = 1 << 19
maxc = (1 << 13)
maxd = (1 << 6)
def hw(a):
res = 0
while a > 0:
res ^= a & 1
a >>= 1
return res
hwtab = [hw(a) for a in range(2**20)]
def lfsr(r, m):
return ((r << 1) & 0xffffff) ^ hwtab[r & m]
def lfsr_stream(a, ma, n):
res = []
for i in range(n):
a = lfsr(a, ma)
res.append(a & 1)
return res
def merge(la, lb, lc, ld):
ret = []
for ao, bo, co, do in zip(la, lb, lc, ld):
codo = co ^ do
res = bo & (ao ^ codo) ^ codo
ret.append(res)
return ret
N = 150
full = list(map(int, open("data", "r").read(500)))
s = full[:N]
print("gen sc")
ssc = []
for c in range(maxc):
sc = lfsr_stream(c, mc, N)
ssc.append(sc)
print("gen sd")
ssd = []
for d in range(maxd):
sd = lfsr_stream(d, md, N)
ssd.append(sd)
print("gen sa")
ssa = []
for a in range(maxa):
sa = lfsr_stream(a, ma, N)
ssa.append(sa)
print("gen ok")
# stage 1
cands_b = []
# uncomment to go to stage2
cands_b = [524287, 494934]
if not cands_b:
import os
from random import randint, choice
print("Step 1")
# multiprocessing for the poor
NT = 4
for ti in range(NT):
if os.fork() == 0:
break
else:
for j in range(NT):
os.wait()
quit()
for b in reversed(range(ti, maxb, NT)):
if (b-ti)//NT % 5000 == 0:
print("ti", ti, ":", b, "/", mb)
sb = lfsr_stream(b, mb, N)
m = []
for i in range(N):
sc = choice(ssc)
sd = choice(ssd)
row = [(sc[j] ^ sd[j]) & (1 ^ sb[j]) for j in range(N)]
m.append(row)
m = matrix(GF(2), m)
r1 = m.rank()
row = [s[j] & (1 ^ sb[j]) for j in range(N)]
m = m.stack(vector(GF(2), row))
r2 = m.rank()
# bad guess of b would lead to wrong choice of positions
# which would provide new independent vector
# good guess will keep the rank
if r1 == r2:
print("candidate", b)
print("ti", ti, "fini")
# step 2
print("Step 2")
for b in cands_b:
print("try b =", b)
sb = lfsr_stream(b, mb, N)
# choose c when b = 0
tabc = {}
for c, sc in enumerate(ssc):
row = [sc[i] & (sb[i] ^ 1) for i in range(N)]
tabc[tuple(row)] = c
# choose a when b = 1
taba = {}
for a, sa in enumerate(ssa):
row = [sa[i] & (sb[i] ^ 0) for i in range(N)]
taba[tuple(row)] = a
for d, sd in reversed(list(enumerate(ssd))):
row = [(s[i] ^ sd[i]) & (sb[i] ^ 1) for i in range(N)]
k = tuple(row)
if k in tabc:
c = tabc[k]
sc = ssc[c]
print("b =", b, "c =", c, "d =", d)
row = [full[i] & (sb[i] ^ 0) for i in range(N)]
k = tuple(row)
if k in taba:
a = taba[k]
sa = ssa[a]
test = merge(sa, sb, sc, sd)
if test == full[:N]:
print("match", "a =", a, "b =", b, "c =", c, "d =", d)
print("De1CTF{" + ''.join("%x" % i for i in (a, b, c, d)) + "}")
# De1CTF{58bb578d5611363f}
from flag import a, b, c, d, flag
assert flag == "De1CTF{" + ''.join([hex(i)[2:] for i in [a, b, c, d]]) + "}"
assert [len(bin(i)[2:]) for i in [a, b, c, d]] == [19, 19, 13, 6]
ma, mb, mc, md = 0x505a1, 0x40f3f, 0x1f02, 0x31
def lfsr(r, m): return ((r << 1) & 0xffffff) ^ (bin(r & m).count('1') % 2)
def combine():
global a, b, c, d
a = lfsr(a, ma)
b = lfsr(b, mb)
c = lfsr(c, mc)
d = lfsr(d, md)
[ao, bo, co, do] = [i & 1 for i in [a, b, c, d]]
return (ao*bo) ^ (bo*co) ^ (bo*do) ^ co ^ do
def genkey(nb):
s = ''
for i in range(nb*8):
s += str(combine())
open("data", "w+").write(s)
genkey(128*1024)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment