Happy Meal
Happy Meal
Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: 2-adic_rational_approximation, fcsr_state_recovery, extended_gcd_lattice_reduction, known_plaintext_prng_attack
Summary
Walkthrough of the CUSTOM Crypto Happy Meal. 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 recov
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)")
Key Takeaways / Lessons
- Mastering 2-adic_rational_approximation, fcsr_state_recovery, extended_gcd_lattice_reduction, known_plaintext_prng_attack was key to this challenge.
- Always check for common misconfigurations and verify assumptions.
Crafted by XESXOR Research • 2026-03-28 • CUSTOM • Happy Meal • Difficulty: Medium