Linear-feedback Shift Register Writeup - CTFlearn

This challenge is a cryptography challenge from CTFlearn. It’s a hard level challenge based on Linear-feedback Shift Register (LFSR).

Challenge Description

Hello!

I have just implemented a super-cool PRNG!

I've used every next generated by it number to XOR every next character in my super-secret message with.

Are you able to retrieve it?

Btw. Biggest possibly generated number by my PRNG is 255.

Psst. The retrieved message would be your flag!

As always, starting with: CTFlearn{...

I'm giving you the PRNG scheme with a brief description (description.png) and a "secretMessage.hex" file with every byte being the corresponding message char inside PRNG.zip file. (https://ctflearn.com/challenge/download/1059)

Solution

To kick off the challenge, I started by inspecting the provided files. description.png contains the scheme of the Linear-feedback Shift Register (LFSR) and secretMessage.hex contains the encrypted message.

The LFSR scheme is depicted in the image below:

LFSR Scheme

The LFSR scheme is a 8-bit LFSR. Briefly, values of closed circles are XORed, the most right value is removed and the result is inserted to the leftmost position. This is the most important part of the challenge.

So first of all, I wrote a Python script to implement the LFSR scheme. The script is as follows:

class LFSR:
    def __init__(self, bit_array:  'list[int]', xor_indices: 'list[int]'):
        self.bit_array : list[int] = bit_array
        self.xor_indices : list[int] = xor_indices

    def shift(self):
        temp = 0
        for i in range(0, len(self.bit_array)):
            if i in self.xor_indices:
                temp ^= self.bit_array[i]
        self.bit_array.pop()
        self.bit_array.insert(0, temp)

    def getValue(self):
        return int(''.join(map(str, self.bit_array)), 2)
    
    def getArray(self):
        return self.bit_array

Also, since I am given first few bytes of the secret message, I can use them to find the initial state of the LFSR.


first_byte_of_encrypted_flag = open('/secretMessage.hex', 'rb').readline()[0]

first_byte_of_flag = ord('C') ^ first_byte_of_encrypted_flag
# first_byte_of_flag = 5

Five means that the second state of the LFSR is 5. I can use this information to find the initial state of the LFSR. Of course 5 in bitarray representation.

def int_to_bin(number: int) -> list:
    binary_str = bin(number)[2:]
    padded_binary_str = binary_str.zfill(8)
    bit_array = [int(bit) for bit in padded_binary_str]
    return bit_array

This function converts an integer to a bit array. Pretty straightforward.

So, I have the state of the LFSR. However, I need to find the XOR indices (closed circles in the scheme). I can do this by brute-forcing. I can try all possible XOR indices and check if the first byte of the flag is correct.

def get_combinations(lst):
   combination = []
   for r in range(1, len(lst) + 1):
      combination.extend(itertools.combinations(lst, r))
   return combination

Now, I can try all possible combinations of XOR indices and find the correct one. Here’s all the code together:

import itertools

class LFSR:
    def __init__(self, bit_array:  'list[int]', xor_indices: 'list[int]'):
        self.bit_array : list[int] = bit_array
        self.xor_indices : list[int] = xor_indices

    def shift(self):
        temp = 0
        for i in range(0, len(self.bit_array)):
            if i in self.xor_indices:
                temp ^= self.bit_array[i]
        self.bit_array.pop()
        self.bit_array.insert(0, temp)

    def getValue(self):
        return int(''.join(map(str, self.bit_array)), 2)
    
    def getArray(self):
        return self.bit_array
 
def int_to_bin(number: int) -> list:
    binary_str = bin(number)[2:]
    padded_binary_str = binary_str.zfill(8)
    bit_array = [int(bit) for bit in padded_binary_str]
    return bit_array
   
def get_combinations(lst):
   combination = []
   for r in range(1, len(lst) + 1):
      combination.extend(itertools.combinations(lst, r))
   return combination

possible_gates_indices = [0,1,2,3,4,5,6,7] 
all_gate_combinations = get_combinations(possible_gates_indices) 

encrypted_flag = bytes.fromhex("465647ec25c1a2868fb694904c8b2d705138366663b423cb8fbb9ccb9baa20ed6c482678713173fd")  # open('secretMessage.hex', 'rb').readline()

for gate in all_gate_combinations:
    initialState = int_to_bin(5)
    gate = list(gate)   
    lfsr = LFSR(initialState, gate)

    values = []
    enc= encrypted_flag[1:]
    flag= "C"
    for i in range(0, len(enc)):
        lfsr.shift()
        flag += chr(enc[i ] ^ lfsr.getValue())
        if flag[-1] == "}":
            break
    
    if "CTFlearn{" in flag:
        print(flag)
        break

That’s it! When I run the script, I get the flag:

CTFlearn{xxxxxxxxxxxxxxxx}

Conclusion

This challenge was a good exercise to brush up on LFSR.

I hope you enjoyed the writeup. If you have any questions, feel free to ask.