[2021 PBCTF] Alkaloid Stream

Let $\textsf{LEN}$ be a key bit length.

 

Since $\textsf{fake[LEN-1]} = 0$, we can search the value $\textsf{fake[LEN-1]}$  in pubkey. Then $\textsf{key[LEN-1]}$ is immediately recovered.

 

$\textsf{fake[LEN-2]} = \textsf{key[LEN-1]}$, also possible to find $\textsf{fake[LEN-2]}$ in pubkey. Then $\textsf{key[LEN-2]}$ is recovered.

 

By similar logic, if we know $\textsf{key[i...LEN-1]}$, then $\textsf{fake[i-1]}$ is recovered which derives to earn $\textsf{key[i-1]}$.

 

This is all.

 

from Crypto.Util.number import *
import random

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)
    
    # Generate some fake values based on the given key...
    fake = [0] * ln
    for i in range(ln):
        for j in range(ln // 3):
            if i + j + 1 >= ln:
                break
            fake[i] ^= key[i + j + 1]

    # 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 solve():
    f = open('output.txt')
    enc = int(f.readline(), 16)
    pub = eval(f.readline())

    key_recover = [0]*600
    fake_recover = [0]*600
    keystream = [0]*600
    vis = [0]*600    
    for i in range(599,-1,-1):
        vv = 0
        for j in range(i+1, min(i+201, 600)):
            vv ^= key_recover[j]
        print(vv)
        for j in range(600):
            if vis[j]: continue
            if pub[j][0] == vv:
                keystream[j] = 1
                key_recover[i] = pub[j][1]
                fake_recover[i] = pub[j][0]
                vis[j] = 1
                break
            if pub[j][1] == vv:
                keystream[j] = 0
                key_recover[i] = pub[j][0]
                fake_recover[i] = pub[j][1]
                vis[j] = 1
                break
        else:
            print("wrong",i)
            assert(0)

    z = 0
    for i in range(600):
        if keystream[i]: z ^= (1<<(599-i))
    print(hex(z))

    print(long_to_bytes(z^enc))

solve()