0CTF 2019 Quals - zer0lfsr (Crypto 207 pts)

1_solve.py

#!/usr/bin/env sage
'''
The third LFSR has low period: 378.
If the value in positions 0,378,2*378,... is equal to 0,
then the combine functions become AND of the first two LFSRs.
If the value in positions 0,378,2*378,... is equal to 1,
then the combine functions become OR  of the first two LFSRs.
We can distinguish both cases easily by number of 0s/1s
(should be 25% in the first case and 75% in the second case)

If AND is equal to 1, we know that both inputs are equal to 1.
Similarly for OR and 0. This gives us bits from LFSR state,
by solving a linear equation system we can recover initial states easily.

PS: it seems that this chall was trivially solvable by z3, thus many solves ;)
'''

from sage.all import *
from cryptools.env.basic import *

class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**(length+1)-1

    def next(self, itr=1):
        for ii in xrange(itr):
            nextdata = (self.init << 1) & self.lengthmask
            i = self.init & self.mask & self.lengthmask
            output = 0
            while i != 0:
                output ^= (i & 1)
                i = i >> 1
            nextdata ^= output
            self.init = nextdata
        return output

def combine(x1,x2,x3):
    return (x1*x2)^(x2*x3)^(x1*x3)


masks = [
0b100000000000000000000000010000000000000000000000,
0b100000000000000000000000000000000010000000000000,
0b100000100000000000000000000000000000000000000000,
]
MATN = 2048

# generate matrices for all states for each of the LFSRs
ms = []
for imask in xrange(3):
    print imask
    m = matrix(GF(2), MATN, 48)
    mask = masks[imask]
    for i in xrange(48):
        inp = [0] * 48
        inp[i] = 1
        l = lfsr(frombin(inp), mask, 48)
        ks = [l.next() for _ in xrange(MATN)]
        m.set_column(i, vector(GF(2), ks))
    ms.append(m)


from libnum import s2b
'''
python3:
s = open("keystream", "rb").read().decode()
open("keystreamBIN", "wb").write(bytes(map(ord, s)))
'''
keystream = open("keystreamBIN").read() # recoded keystream.. python3 encoding madness..
keystream = map(int, s2b(keystream))

mat = []
target = []
for off in xrange(1000):
    sub = keystream[off::378]
    bit = None
    if sum(sub) < 0.3 * len(sub):
        bit = 0
    elif sum(sub) > 0.7 * len(sub):
        bit = 1
    else:
        continue
    print "off", sum(sub) / float(len(sub)), len(sub)

    mat.append([0] * 48 + [0] * 48 + list(ms[2][off]))
    target.append(bit)
    for i in xrange(off, len(keystream), 378):
        if i >= MATN:
            break
        if keystream[i] != bit:
            mat.append(list(ms[0][i]) + [0] * 48 + [0] * 48)
            mat.append([0] * 48 + list(ms[1][i]) + [0] * 48)
            target.append(keystream[i])
            target.append(keystream[i])

mat = matrix(GF(2), mat)
target = vector(GF(2), target)

print "equations", mat.nrows()
print "rank", mat.rank()
sol = mat.solve_right(target)
print sol
init1 = frombin(sol[ 0: 48])
init2 = frombin(sol[48: 96])
init3 = frombin(sol[96:144])

print "%012x" % init1
print "%012x" % init2
print "%012x" % init3

import hashlib
init1 = n2s(init1).rjust(6, "\x00")
init2 = n2s(init2).rjust(6, "\x00")
init3 = n2s(init3).rjust(6, "\x00")
print "flag{" + hashlib.sha256(init1+init2+init3).hexdigest() +"}"

chall.py

from secret import init1,init2,init3,FLAG
import hashlib
assert(FLAG=="flag{"+hashlib.sha256(init1+init2+init3).hexdigest()+"}")

class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**(length+1)-1

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask 
        i = self.init & self.mask & self.lengthmask 
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output

def combine(x1,x2,x3):
    return (x1*x2)^(x2*x3)^(x1*x3)

if __name__=="__main__":
    l1 = lfsr(int.from_bytes(init1,"big"),0b100000000000000000000000010000000000000000000000,48)
    l2 = lfsr(int.from_bytes(init2,"big"),0b100000000000000000000000000000000010000000000000,48)
    l3 = lfsr(int.from_bytes(init3,"big"),0b100000100000000000000000000000000000000000000000,48)

    with open("keystream","wb") as f:
        for i in range(8192):
            b = 0
            for j in range(8):
                b = (b<<1)+combine(l1.next(),l2.next(),l3.next())
            f.write(chr(b).encode())