DOWN-THE-STREAM-1

crypto 107 solves by william_etotheipi

Challenge

A synchronous stream cipher sounds like a very secure cipher!

Understanding the cipher

The keystream comes from an 8-bit Fibonacci LFSR with a fixed, fully disclosed tap set:

def next_register(register: int) -> int:
    for _ in range(8):
        feedback = (((register >> 7) & 1) ^
                    ((register >> 5) & 1) ^
                    ((register >> 4) & 1) ^
                    ((register >> 3) & 1))
        register = ((register << 1) | feedback) & 0xff
    return register

def LFSR(pt_bytes, IV):
    register = IV
    ct[0] = pt[0] ^ register
    for i in range(1, len(pt)):
        register = next_register(register)
        ct[i] = pt[i] ^ register

Every byte of keystream is register before it's clocked again, XORed straight into the plaintext byte. The taps, the round count, the whole algorithm, all given. The only unknown is the 1-byte IV, and a 1-byte register only has 256 possible starting states. This is a brute force problem, plain and simple.

Solution

XOR is its own inverse, so decryption looks identical to encryption: run the same LFSR() function against the ciphertext for every possible IV and keep whichever one decodes to readable ASCII containing the flag prefix.

ct_hex = "e944b3a55e47c5d8f3af3c93e2f7f2b1892094001e95a16b779b907bd374e2327a2dace45d222f69138b"
ct_bytes = bytes.fromhex(ct_hex)
for iv in range(256):
    pt = decrypt_LFSR(ct_bytes, iv)
    try:
        cosa = pt.decode('ascii')
        if "gaslightCTF" in cosa:
            print(cosa)
    except UnicodeDecodeError:
        pass