Tags: python crypto 


The picture describes the whole process. For each step you pop the least significant bit of the shift register and
* xor it with the next bit of the flag and append the result to Y
* xor it with the 8ths place bit and add that to the most significant end of the shift register

Because of the nature of the xor operation, if we feed in Y instead of the flag, as long as the LFSR prouces the same bit sequence we'll get the flag out. The bit sequence only depends on the initial value of the register. As there are only 32 possible initial states, each one can be tried with a script such as this one:

import binascii

def generate_bit_sequence(initial_state):
state = initial_state
while True:
last_bit = state & 1
yield last_bit
middle_bit = state >> 3 & 1
state = (state >> 1) | ((last_bit ^ middle_bit) << 4)

def decrypt(message, initial_state):
lfsr = generate_bit_sequence(initial_state)
decrypted = ""
for c in message:
decrypted_bit = (ord(c) - ord('0')) ^ next(lfsr)
decrypted += chr(decrypted_bit + ord('0'))
return int(decrypted, 2)

Y = "000001000000000010001110111111111100000110101011100011100111010100011011111101001010100100110100100010000110110101101101101111010100011001111010001100000101010110000000010011001000010000100110100001111011010111000010000111101110001110001110"

for initial_state in range(32):
d = hex(decrypt(Y, initial_state))[2:-1]
if len(d) % 2 == 0:
# ignore the odd length ones
print binascii.unhexlify(d)

Among the outputs which are mostly garbage lies our flag: `SchoolCTF{3v3rY80DY_l0V3_Lf5R}`