Happy Meal
Happy Meal
Platform: VolgaCTF 2026 | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-03-28 | Status: Solved Techniques: 2-adic_rational_approximation, fcsr_state_recovery, extended_gcd_lattice_reduction, known_plaintext_prng_attack
Summary
Task: Recover a 12-word mnemonic seed phrase generated by an FCSR, given the first 3 words and source code. Solution: Used 2-adic rational approximation (extended GCD) on 21 known output bits to recover the connection integer q=845, then generated the full phrase.
Happy Meal — VolgaCTF 2026
Description
We lost mnemonic seed phrase for our wallet. The only thing we have on hand is the first 3 of the 12 words and the source code for generating it.
REDACTED...
Can you help us to recover it?
We are given the source code for a mnemonic phrase generator that uses an FCSR (Feedback with Carry Shift Register) as its PRNG. The FCSR parameters (q, m, a) are hidden. We know the first 3 of 12 words in the generated phrase and need to recover the remaining 9.
Files provided: task.py, fcsr.py, dictionary.py
Analysis
FCSR Structure
The FCSR (Feedback with Carry Shift Register) is similar to an LFSR but operates over the 2-adic integers instead of GF(2). Key properties:
- Connection integer
q: Determines the feedback polynomial (must be odd) - Initial state
a: The register contents at startup - Carry
m: An integer carry value (unlike LFSR which has no carry) - Register length:
bit_length(q+1) - 1
The clock() method computes:
comp = m + sum(q[i] & a[i]) (feedback taps)
output_bit = comp % 2
new_carry = comp // 2
Known Information
- Dictionary size: 128 words →
idx_length = floor(log2(128)) = 7bits per word - Known words: "happy" (index 37), "meal" (index 63), "family" (index 26)
- Known output bits: 21 bits total from the first 3 word indices
Word-to-bits conversion (MSB first, 7 bits each):
"happy" = 37 = 0100101
"meal" = 63 = 0111111
"family" = 26 = 0011010
FCSR output stream (first 21 bits): 0 1 0 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 1 0
2-adic Theory
A fundamental property of FCSRs: the output sequence b_0, b_1, b_2, ... satisfies:
$$\alpha = b_0 + b_1 \cdot 2 + b_2 \cdot 4 + \cdots = \frac{p}{q} \in \mathbb{Z}_2$$
where p and q are integers determined by the FCSR parameters. This means if we can find the rational number p/q from a partial output, we can reconstruct the entire infinite output stream.
Solution
Step 1: Compute the 2-adic value from known bits
Convert the 21 known output bits to a 2-adic integer (LSB = first output bit):
python read-only • copy allowedknown_bits = [0,1,0,0,1,0,1, 0,1,1,1,1,1,1, 0,0,1,1,0,1,0] alpha = sum(known_bits[i] * (2**i) for i in range(21)) # alpha = 737106 (mod 2^21)
Step 2: 2-adic rational approximation via Extended GCD
To find small p, q such that α ≡ p/q (mod 2^21), we apply the extended Euclidean algorithm to (2^21, α). This is the 2-adic analog of continued fraction approximation:
python read-only • copy allowedr_prev, r_curr = 2**21, 737106 t_prev, t_curr = 0, 1 bound = int(math.isqrt(2**21)) # ~1448 while r_curr != 0: q_div = r_prev // r_curr r_prev, r_curr = r_curr, r_prev - q_div * r_curr t_prev, t_curr = t_curr, t_prev - q_div * t_curr if abs(r_curr) < bound and t_curr % 2 != 0: # Found: p = r_curr, q = t_curr break
Result: p = 426, q = 845 (both small integers, q is odd ✓)
Step 3: Generate the full output stream
With p/q known, compute the full 2-adic expansion to get all 84 bits (12 words × 7 bits):
python read-only • copy allowedN = 7 * 12 + 10 # 94 bits, with margin modN = 2**N q_inv = pow(845, -1, modN) # modular inverse (q is odd, so it exists mod 2^N) full_alpha = (426 * q_inv) % modN # Extract bits and convert to word indices all_bits = [(full_alpha >> i) & 1 for i in range(84)]
Step 4: Verify with brute-force
As confirmation, brute-forced all odd q < 2048 with all valid initial states:
python read-only • copy allowedfor q_try in range(3, 2048, 2): coefficients = int_to_bit_seq(q_try + 1)[::-1] reg_len = len(coefficients) - 1 max_m = bin(q_try + 1).count('1') - 1 for m_try in range(max_m + 2): for a_try in range(1, 2**reg_len): fcsr = FCSR(q_try, m_try, a_try) if all(fcsr.get_idx(7) == known_indices[i] for i in range(3)): # Found: q=845, m=0, a=338, register length=9
Unique solution: q = 845, m = 0, a = 338
Full Solve Script
python read-only • copy allowed#!/usr/bin/env python3 import math MNEMONIC_DICT_EN = [ "apple", "actor", "animal", "airport", "answer", "ball", "banana", "beach", "bedroom", "bird", "cable", "camera", "candle", "carpet", "castle", "damage", "dance", "desert", "diamond", "doctor", "eagle", "earth", "economy", "editor", "engine", "factory", "family", "farmer", "feather", "festival", "galaxy", "garden", "gas", "gate", "guitar", "hair", "hammer", "happy", "helmet", "holiday", "ice", "idea", "income", "insect", "island", "jacket", "jelly", "jewel", "journey", "judge", "kangaroo", "kayak", "kernel", "kettle", "king", "ladder", "lake", "language", "lawyer", "library", "machine", "magazine", "market", "meal", "museum", "nail", "nation", "necklace", "needle", "notebook", "oasis", "ocean", "office", "onion", "orange", "package", "painting", "palace", "parent", "planet", "quarry", "queen", "question", "queue", "rabbit", "radio", "rainbow", "river", "robot", "salary", "sandwich", "school", "screen", "sister", "table", "teacher", "temple", "theory", "ticket", "umbrella", "uncle", "unicorn", "uniform", "university", "vacation", "valley", "vessel", "victory", "village", "wallet", "warrior", "weather", "window", "writer", "xenon", "xylophone", "xylem", "xenophobia", "yacht", "yak", "yard", "year", "youth", "zebra", "zenith", "zinc", "zoo", "zone", ] class FCSR: def __init__(self, q, m, a): coefficients = self.int_to_bit_seq(q + 1)[::-1] state = self.int_to_bit_seq(a)[:len(coefficients)-1] state = [0] * (len(coefficients) - len(state) - 1) + state state = state[::-1] self.m = m self.q = coefficients self.a = state @staticmethod def int_to_bit_seq(number): return list(map(int, list(bin(number)[2:]))) def clock(self): comp = self.m + sum([x & y for (x, y) in zip(self.q[1:], self.a[::-1])]) self.a.append(comp % 2) self.m = comp // 2 return self.a.pop(0) def get_idx(self, idx_length): ret = 0 for _ in range(idx_length): bit = self.clock() ret = (ret << 1) | bit return ret # === Method 1: 2-adic rational approximation === known_words = ["happy", "meal", "family"] known_indices = [MNEMONIC_DICT_EN.index(w) for w in known_words] idx_length = 7 # Extract known output bits (MSB first per word) known_bits = [] for idx in known_indices: for j in range(idx_length - 1, -1, -1): known_bits.append((idx >> j) & 1) # Compute 2-adic value: alpha = sum(b_i * 2^i) n = len(known_bits) # 21 alpha = sum(known_bits[i] * (2**i) for i in range(n)) # Extended GCD to find small p, q with alpha = p/q (mod 2^n) r_prev, r_curr = 2**n, alpha t_prev, t_curr = 0, 1 bound = int(math.isqrt(2**n)) while r_curr != 0: q_div = r_prev // r_curr r_prev, r_curr = r_curr, r_prev - q_div * r_curr t_prev, t_curr = t_curr, t_prev - q_div * t_curr if abs(r_curr) < bound and t_curr != 0 and t_curr % 2 != 0: p_val, q_val = r_curr, t_curr break # Reconstruct full output: alpha = p * q^(-1) mod 2^N N = 7 * 12 + 10 modN = 2**N q_inv = pow(q_val, -1, modN) full_alpha = (p_val * q_inv) % modN all_bits = [(full_alpha >> i) & 1 for i in range(7 * 12)] words = [] for w in range(12): idx = 0 for b in range(7): idx = (idx << 1) | all_bits[w * 7 + b] words.append(MNEMONIC_DICT_EN[idx]) print(" ".join(words)) # REDACTED # === Method 2: Brute-force verification === fcsr = FCSR(845, 0, 338) words2 = [MNEMONIC_DICT_EN[fcsr.get_idx(7)] for _ in range(12)] assert words == words2 print("Verified with FCSR(q=845, m=0, a=338)")