Search for a command to run...
Santa is running out of elves to build gifts... So we decided to launch a community project. With enough help, we should be able to build today's flag for everyone!
Join the Community Gift Project and help us build this formidable gift! =D
https://cgp.challenges.xmas.root-me.org/
LFSR (Linear Feedback Shift Register) challenge. We need to click a button exactly 1,337,133,713,371,337,133,713,371,337,133,713,371,337 times to build a gift. Impossible to brute force so we use matrix exponentiation to fast forward the state.
The web app shows:
1337133713371337133713371337133713371337 elf-hoursLooking at the source code dist/app.py and dist/factory.py:
# When you reach the exact required work:
if counter == REQUIRED_WORK:
gift_state = 'Gift complete: ' + int(''.join(str(b) for b in flag_room.gift_state), 2).to_bytes(24, 'little').decode()
The flag is hidden in flag_room.gift_state, which is a 192 bit array that gets transformed on each click.
Each click runs this function:
def work(self):
s = 0
for t in self.instructions:
s ^= self.gift_state[t-1]
self.gift_state = [s] + self.gift_state[:-1]
It:
instructions arrayThis is a classic Linear Feedback Shift Register (LFSR).
We can't click the button that many times. But LFSR are linear systems and they can be represented as matrix operations:
new_state = Matrix × old_state
After N iterations:
final_state = Matrix^N × initial_state
Matrix exponentiation (using binary exponentiation) lets us compute Matrix^N in O(log N) time, even for huge N!
Created solve.py that:
Matrix^1337133713371337133713371337133713371337Binary Exponentiation:
def matrix_power_mod2(matrix, n):
result = identity_matrix
base = matrix
while n > 0:
if n % 2 == 1:
result = result × base (mod 2)
base = base × base (mod 2)
n //= 2
return result
This reduces the problem from ~10^40 operations to ~130 matrix multiplications!
Output:
[*] Initial state length: 192
[*] Number of taps: 98
[*] Required iterations: 1337133713371337133713371337133713371337
[*] Creating LFSR transition matrix...
[*] Computing matrix^1337133713371337133713371337133713371337 mod 2...
[*] Applying transformation to initial state...
[*] Decoding flag...
[+] Flag: RM{ThX_4_th3_h3lP_;)_:)}