m0leCon 2021 | obscurity

#m0lecon2021

import random
from functools import reduce
import sys
from math import log2
from secret import flag

def xor(a, b):
    return bytes(x^y for x,y in zip(a,b))

class LFSR(object):
    def __init__(self, s, p):
        self.s = s
        self.p = p

    def clock(self):
        out = self.s[0]
        self.s = self.s[1:]+[self.s[0]^self.s[(self.p)[0]]^self.s[(self.p)[1]]]
        return out

def buildLFSR(l):
    return LFSR([int(x) for x in list(bin(random.randint(1,2**l-1))[2:].rjust(l,'0'))], random.sample(range(1,l), k=2))

key = b""

print("encrypt plz [in hex]")
pt = bytes.fromhex(input().strip())

if len(pt)>1000:
    print("WELL, not that much")
    exit()

pt = pt + flag
periodic = True

while periodic:
    lfsr_len = [random.randint(4,6) for _ in range(random.randint(9,12))]
    L = [buildLFSR(i) for i in lfsr_len]
    u = 0
    key = b""
    for i in range(len(pt)+65):
        ch = 0
        for j in range(8):
            outvec = [l.clock() for l in L]
            u = (u+sum(outvec))//2
            out = (reduce(lambda i, j: i^j, outvec) ^ u) & 1
            ch += out*pow(2,7-j)
        key += bytes([ch])
    kk = key.hex()
    if kk.count(kk[-6:]) == 1:
        periodic = False

res = xor(key[:-65],pt).hex()
print(res)

overview

• 実装がカスだけどLFSRは LFSR

• buildLFSR(l) は bitのstateと を返す

• • 後者はstateのどこをみて結合するか、といういわゆるmask

• 本体

• まずplaintextを渡すと、後ろにflagをくっつけてくれる

• これを暗号化する。暗号化はLFSRを用いたkeystreamとのxorで行われる

• • したがって、既知の平文を用いてkeystreamを当てるのが今回の問題

• keystreamの生成は次の通り

• 内部状態が4~6 bitのLFSRを9〜12個つくる

• 8bitずつ作っていく

• • それぞれのLFSRから1bitずつ得て outvec とする

  • と更新する

  • 

  • が1bitになる

• これで len(pt) + 65 バイトつくって、状態がループしていないことを確認できれば len(pt) バイトの鍵を返す