Description
Please enjoy the classical lfsr.
zer0lfsr.tar.gz
Attachment content
chall.py
keystream
chall.py script
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())
Write-up
As Wikipedia states a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. I had never heard of LFSR before (or maybe I had and forgot about it) so I looked at this script for several hours.
At some point I started to print the b variable written to file and it was never greater than 255. So, since the range goes from 0 to 8191, why does the keystream file have more than 8192 bytes?
$ cat keystream | wc -c
11990
I found out that the encode() sometimes returned 1 and sometimes 2 bytes for each character. So the first thing was to create a decoded-keystream of 8192 bytes.
I think there are better methods, but this was the one that I came up with:
barr = b''
with open('keystream','rb') as f:
data = f.read()
i = 0
while i < len(data):
if data[i] == 194 or data[i] == 195:
barr += bytes([ord(bytes([data[i], data[i+1]]).decode())])
i += 1
else:
barr += bytes([ord(bytes([data[i]]).decode())])
i += 1
with open('decoded-keystream', 'wb') as f:
f.write(barr)
$ cat decoded-keystream | wc -c
8192
Ok. As I did not know nothing about LFSR, I studied how the b was generated:
b = (b<<1)+combine(l1.next(),l2.next(),l3.next())
The operation b<<1 multiplies b by 2. If b = 16, b<<1 = 32. Sometimes an odd number like 33 appears and I found out this was because of the combine method. b<<1 can only generate even numbers, so when b was odd in some iteration I knew combine returned 1. So, I understood I could retrieve every output of combine with this algorithm:
b = 193
iteration 8 -> 193 = 96 * 2 + 1
iteration 7 -> 96 = 48 * 2 + 0
iteration 6 -> 48 = 24 * 2 + 0
iteration 5 -> 24 = 12 * 2 + 0
iteration 4 -> 12 = 6 * 2 + 0
iteration 3 -> 6 = 3 * 2 + 0
iteration 2 -> 3 = 1 * 2 + 1
iteration 1 -> 1 = 0 * 2 + 1
If the b = 193, I know the combine method generated 1, 1, 0, 0, 0, 0, 0 and 1 as outputs. So, I came up with a method to generate all the outputs for me, for each iteration:
with open("decoded-keystream", "rb") as f:
data = f.read()
for b in data:
arr = []
tmp = b
for i in range(8):
arr += [tmp]
tmp //= 2
tmp = 0
for l in arr[::-1]:
outputs += [l - (tmp * 2)]
tmp = l
>>> print(len(outputs))
65536
Good signal: I have 65536 outputs for the 8192 * 8 interactions.
To make sure this was right, I created a method to generate a proof and compare it to the original keystream:
with open('proof', 'wb') as f:
o = 0
for i in range(8192):
b = 0
for j in range(8):
b = (b<<1) + outputs[o]
o += 1
f.write(chr(b).encode())
$ sha256sum keystream
44b4e996f4790b2940c596b006e3f0916ce589b960bb1a7c600831d42004d12b keystream
$ sha256sum proof
44b4e996f4790b2940c596b006e3f0916ce589b960bb1a7c600831d42004d12b proof
Same result, so my output is reliable!
Then I got stuck. As I knew nothing about LFSR, I can’t understand how to find the original seeds.
I asked our crypto specialist for help.
Marzano knew that with Z3 it was possible to reverse the keystream into the seeds. As the LFSR length was 48 bits, he created this script:
from z3 import *
class lfsr():
def __init__(self, init, mask, length):
self.init = init
self.mask = mask
self.lengthmask = 2**(length+1)-1
self.length = length
def next(self):
nextdata = (self.init << 1) & self.lengthmask
i = self.init & self.mask & self.lengthmask
output = 0
for j in range(self.length):
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)
init1 = BitVec('init1', 48)
init2 = BitVec('init2', 48)
init3 = BitVec('init3', 48)
l1 = lfsr(init1, 0b100000000000000000000000010000000000000000000000, 48)
l2 = lfsr(init2, 0b100000000000000000000000000000000010000000000000, 48)
l3 = lfsr(init3, 0b100000100000000000000000000000000000000000000000, 48)
s = Solver()
with open('decoded-keystream', 'rb') as f:
keystream = f.read()
outputs = []
for b in keystream:
arr = []
tmp = b
for i in range(8):
arr += [tmp]
tmp //= 2
tmp = 0
for l in arr[::-1]:
outputs += [l - (tmp * 2)]
tmp = l
for i in range(len(outputs)):
s.add(outputs[i] == combine(l1.next(), l2.next(), l3.next()))
print(i)
s.check()
print(s.model())
We tested the script with the first bits of output and everything worked. However, when we ran the script with full length, the script crashed with no memory left.
I thought for some time and I came up with the solution: let’s try to run a script with only x bits, then run again with a y greater than x and see if the result is the same.
The line
for i in range(len(outputs)):
was changed to:
for i in range(bits):
bits = 100
[init3 = 319098525903, init2 = 159339250822750, init1 = 165948368634684]
bits = 200
[init3 = 191532558614761, init2 = 181037482648735, init1 = 70989122156399]
bits = 300
[init3 = 191532558614761, init2 = 181037482648735, init1 = 70989122156399]
200 bits and 300 bits returned the same result, so it seemed like 200 bits was enough.
The flag was asserted like this:
assert(FLAG=="flag{"+hashlib.sha256(init1+init2+init3).hexdigest()+"}")
In the original script, the seeds were converted from bytes to int:
int.from_bytes(init1,"big")
Based on this I assumed that init1, init2 and init3 were in byte array format.
This was my final code to generate the flag:
from Crypto.Util.number import long_to_bytes
from hashlib import sha256
flag = 'flag{' + sha256(long_to_bytes(70989122156399) + long_to_bytes(181037482648735) + long_to_bytes(191532558614761)).hexdigest() + '}'
print(flag)
Flag
flag{b527e2621131134ec22250cfbca75e8c9f5ae4f40370871fd55910927f66a1b4}