[2021 PBCTF] Steroid Stream

$\textsf{fake[LEN-LEN//3:LEN]} = 0$. Therefore $\textsf{key[LEN-LEN//3:LEN]}$ can be recovered(Index is ignored).

 

For $\textsf{fake[i]} \text{  for  } i < \textsf{LEN-LEN//3}$, those value is linear combination of $\textsf{key[i+1:LEN]}$. It is enough to check whether which remaining value is a linear combination of $\textsf{key[i+1:LEN]}$.

 

There might be a false positive, so I was planning to bruteforce last four or five recovered keybits but fortunately there was no false positive.

 

def keygen(ln):
    # Generate a linearly independent key
    arr = [ 1 << i for i in range(ln) ]

    for i in range(ln):
        for j in range(i):
            if random.getrandbits(1):
                arr[j] ^= arr[i]
    for i in range(ln):
        for j in range(i):
            if random.getrandbits(1):
                arr[ln - 1 - j] ^= arr[ln - 1 - i]

    return arr

def gen_keystream(key):
    ln = len(key)
    assert ln > 50
    
    # Generate some fake values based on the given key...
    fake = [0] * ln
    for i in range(ln - ln // 3):
        arr = list(range(i + 1, ln))
        random.shuffle(arr)
        for j in arr[:ln // 3]:
            fake[i] ^= key[j]

    # Generate the keystream
    res = []
    for i in range(ln):
        t = random.getrandbits(1)
        if t:
            res.append((t, [fake[i], key[i]]))
        else:
            res.append((t, [key[i], fake[i]]))

    # Shuffle!
    random.shuffle(res)

    keystream = [v[0] for v in res]
    public = [v[1] for v in res]
    return keystream, public

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

def recover_keystream(key, public):
    st = set(key)
    keystream = []
    for v0, v1 in public:
        if v0 in st:
            keystream.append(0)
        elif v1 in st:
            keystream.append(1)
        else:
            assert False, "Failed to recover the keystream"
    return keystream

def bytes_to_bits(inp):
    res = []
    for v in inp:
        res.extend(list(map(int, format(v, '08b'))))
    return res

def bits_to_bytes(inp):
    res = []
    for i in range(0, len(inp), 8):
        res.append(int(''.join(map(str, inp[i:i+8])), 2))
    return bytes(res)

def rank_check(basis, t, LEN):
    for i in range(LEN-1,-1,-1):
        if t & (1<<i):
            if basis[i] == 0:
                return False
            t ^= basis[i]
    return t == 0

def add_basis(basis,t,LEN):
    for j in range(LEN-1, -1, -1):
        if t & (1 << j):
            if basis[j] == 0:
                basis[j] = t
                return None
            else:
                t ^= basis[j]

def solve():
    f = open('output.txt')
    enc = int(f.readline(), 16)
    pub = eval(f.readline()) # len 616
    LEN = len(pub)
    keystream = [0]*LEN
    vis = [0]*LEN
    basis = [0]*LEN


    ############# BASIS
    for i in range(LEN):
        if pub[i][0] == 0:
            vis[i] = True
            keystream[i] = 1
            add_basis(basis,pub[i][1],LEN)

        if pub[i][1] == 0:
            vis[i] = True
            keystream[i] = 0
            add_basis(basis,pub[i][0],LEN)
    
    for cur in range(LEN//3, LEN):        
        for i in range(LEN):
            if vis[i]: continue
            if rank_check(basis, pub[i][0], LEN):
                vis[i] = True
                add_basis(basis, pub[i][1], LEN)
                keystream[i] = 1
                print("now ", cur, "keystream", i, keystream[i])
                break
            
            if rank_check(basis, pub[i][1], LEN):
                vis[i] = True
                add_basis(basis, pub[i][0], LEN)
                print("now ", cur, "keystream", i, keystream[i])
                break
        else:
            print("!!!!!",i)
            return None
    print(keystream)
    z = 0
    for i in range(LEN):
        if keystream[i]: z ^= (1<<(LEN-1-i))

    print(long_to_bytes(z^enc))

solve()