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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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:
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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.
1
2
3
4
5
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.
1
2
3
4
5
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.
1
2
3
4
5
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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:
1
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.