De1CTF 2020 - NLFSR

0_solve.sage

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}

1_quiz.py

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)