Jeff's LFSR (jeff)

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-24 | Status: Solved Techniques: geffe_correlation_attack, walsh_hadamard_transform, lfsr_generator_matrix, fast_correlation_attack, bruteforce_remaining_lfsr

Summary

Task: a Geffe generator — three Fibonacci LFSRs (19/27/23-bit, 69-bit key total) combined as out = LFSR1 if LFSR0 else LFSR2; 256 output bits given, flag AES-CBC encrypted under sha1(str(key))[:16]. Solution: a fast correlation attack. The output correlates with LFSR1 and LFSR2 at P=0.75 each; model each LFSR's 256 outputs as GF(2)-linear functionals of its initial state and use the Walsh-Hadamard transform to find the max-correlation states for the 27-bit and 23-bit registers, then exhaust the 19-bit LFSR0 to match all 256 bits exactly. Reassemble the 69-bit key, derive the AES key, and decrypt.

Jeff's LFSR (jeff) — cryptohack (Misc, 150 pts)

Description

Source jeff.py prints a 256-bit keystream from a "Jeff" generator and the flag encrypted with AES-CBC under a key derived from the 69-bit secret. Recover the key and decrypt.

Analysis

Jeff is a classic Geffe generator: three Fibonacci LFSRs and a multiplexer combiner.

 python read-only • copy allowed Copy
class Jeff:
    def __init__(self, key):
        key = [int(i) for i in "{:069b}".format(key)]    # 69-bit secret split into 3 shards
        self.LFSR = [
            LFSR(key[:19],  [19, 18, 17, 14]),   # LFSR0  (19-bit)  -> selector
            LFSR(key[19:46],[27, 26, 25, 22]),   # LFSR1  (27-bit)
            LFSR(key[46:],  [23, 22, 20, 18]),   # LFSR2  (23-bit)
        ]
    def bit(self):
        b = [lfsr.bit() for lfsr in self.LFSR]
        return b[1] if b[0] else b[2]            # out = LFSR1 if LFSR0 else LFSR2

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The selector b0 is uniform, so:

P(out == LFSR1) = P(b0=1) + P(b0=0)·P(LFSR1==LFSR2) = 1/2 + 1/2·1/2 = 0.75
P(out == LFSR2) = 0.75   (by symmetry)

This correlation is the textbook weakness of the Geffe generator: we can attack LFSR1 and LFSR2 independently without touching LFSR0.

Fast correlation attack via Walsh–Hadamard

For a length-d Fibonacci LFSR, output bit i is a fixed GF(2)-linear functional of the initial state: out_i(st) = parity(M[i] & st), where M is a 256×d generator matrix (built by running the LFSR on unit basis states). The correlation of a candidate state with the observed stream tgt is: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

corr(st) = Σ_i (-1)^{out_i(st) ⊕ tgt_i}
         = WHT[g](st),  where  g(m) = Σ_{i: M[i]=m} (-1)^{tgt_i}

So a single Walsh–Hadamard transform of size 2^d finds the argmax-correlation state for LFSR1 (d=27) and LFSR2 (d=23) at once — far cheaper than 2^27·256 brute popcounts.

Pinning down LFSR0

With the best candidate states for LFSR1 and LFSR2 (keep the top-10 for robustness), exhaust the small 19-bit LFSR0 and require an exact match on all 256 bits:

 python read-only • copy allowed Copy
def find_lfsr0(s1, s2):
    out1 = gen_bits(state_to_bits(s1,27), TAPS1, 256)
    out2 = gen_bits(state_to_bits(s2,23), TAPS2, 256)
    for st0 in range(1<<19):
        if all((bin(M0[i]&st0).count("1")&1 and out1[i] or
                not(bin(M0[i]&st0).count("1")&1) and out2[i]) == stream[i] for i in range(256)):
            return st0

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

 python read-only • copy allowed Copy
import numpy as np
def _fwht(g):                      # OUT-OF-PLACE Walsh-Hadamard (see gotcha below)
    g = g.astype(np.int64); size=len(g); h=1
    while h<size:
        g2=g.reshape(-1,2*h); l=g2[:,:h]; r=g2[:,h:]
        new=np.empty_like(g2); new[:,:h]=l+r; new[:,h:]=l-r
        g=new.reshape(-1); h*=2
    return g

def fast_corr(d, taps, target, n=256):
    M = gen_matrix(d, taps, n)                 # 256 masks over d state bits
    g = np.zeros(1<<d, dtype=np.int32)
    for i in range(n): g[M[i]] += 1 if target[i]==0 else -1
    g = _fwht(g)
    best = int(np.argmax(g))
    topk = [int(s) for s in np.argsort(-g)[:10]]
    return best, topk
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# 1) recover LFSR1 (27-bit) and LFSR2 (23-bit) candidates by WHT correlation
_, cand1 = fast_corr(27, TAPS1, stream)
_, cand2 = fast_corr(23, TAPS2, stream)
# 2) brute LFSR0 (2^19) over candidate pairs until 256-bit exact match
# 3) reassemble 69-bit key = bits0(19) + bits1(27) + bits2(23)
key = int("".join(map(str, bits0+bits1+bits2)), 2)
# 4) derive AES key and decrypt
aeskey = hashlib.sha1(str(key).encode()).digest()[:16]
flag = AES.new(aeskey, AES.MODE_CBC, iv).decrypt(ct)

Gotcha (numpy 2.x): an in-place Walsh–Hadamard butterfly that writes into views of the same array (a[:, :h] += a[:, h:]) aliases and corrupts results under numpy 2.x, giving the wrong argmax state. Use the out-of-place version above (allocate a fresh buffer each level). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍