Skip to content

Instantly share code, notes, and snippets.

@hellman hellman/1_solve.py
Last active Mar 26, 2019

Embed
What would you like to do?
0CTF 2019 Quals - zer0lfsr (Crypto 207 pts)
#!/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() +"}"
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())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.