Linear Algebra over GF(2) — solving bit-level unknowns as a linear system mod 2

GF(2) — the two-element field {0,1} where addition is XOR and multiplication is AND — is the algebra every bit-linear cryptographic primitive secretly lives in; once you notice a mechanism is XOR/shift-only, its unknowns become a linear system mod 2 that Gaussian elimination solves in polynomial time, no brute force needed.

The signal that betrays it

Look for a mechanism built ONLY from XOR, bit-shifts, and fixed (public) bit selections — no AND/OR/S-box mixing unknowns together nonlinearly. Concretely:

- The output bit is described as "shift register + XOR of some taps" (LFSR State Recovery — when the keystream itself hands you the seed) — the classic case. - A checksum or MAC is stated to be "linear" or computed as repeated XOR/shift over the message (CRC and Polynomial Recovery — forging or reversing a checksum built from GF(2) division). - A cipher's round/key-schedule difference is said to propagate as a fixed XOR delta with no nonlinear step (Related-Key Attack — exploiting encryptions under keys with a known relationship). - An S-box, when profiled, turns out to be an affine function of its input bits — every output bit is literally XOR of a subset of input bits (+ constant), no genuine nonlinearity (S-box Analysis — profiling a cipher's S-box to pick the right statistical attack: this is the "catastrophic" case in a DDT/LAT profile, not the normal one). - You can count: n unknown bits, and you can obtain ≥ n independent linear observations (output bits, equations, samples). If unknowns ≤ knowns and every relation is additive-over-GF(2), you're in business.

The tell that stops you: if any single output bit needs the AND/product of two unknown bits (a genuine S-box, an LWE noise term, a Poly1305 field *multiplication* of the unknown key with itself across samples), it is NOT plain GF(2) linear algebra anymore — see "What does NOT work" below.

How to exploit it

1. Model each observation as a linear equation. Every known bit of output is a sum (XOR) of a known subset of unknown bits, possibly plus a known constant: b_i = ⊕_j a_ij x_j ⊕ c_i. Stack these into a matrix equation A x = b over GF(2).

2. Make sure you have enough equations. You need at least as many independent equations as unknowns. For an n-bit LFSR state with known taps, the first n output bits already give you the seed directly (the output *is* the shifted-out state); for unknown taps too, 2n consecutive bits give a determined system in the tap coefficients (LFSR State Recovery — when the keystream itself hands you the seed). If equations are short, wait for more keystream/traffic rather than guessing.

3. Solve by Gaussian elimination over GF(2). Row-reduce A to row-echelon form: the only operations you ever need are conditional row-XOR and row swap — there is no fraction/pivot division to worry about, since the only nonzero scalar is 1. This makes the implementation simpler than elimination over the reals (no numerical-stability or fraction bookkeeping) and, once rows are bit-packed, faster by a constant factor — but the asymptotic complexity is the same O(n³) either way; the win is implementation efficiency, not a better algorithm. It's the standard approach in stream-cipher cryptanalysis literature for exactly that simplicity.

``python # Bit-packed Gaussian elimination over GF(2). # rows: list of ints, each bit i = coefficient of unknown i; # rhs: parallel list of 0/1, the known right-hand side. def solve_gf2(rows, rhs, n_unknowns): rows = [r | (b << n_unknowns) for r, b in zip(rows, rhs)] # augment pivot_row = 0 for col in range(n_unknowns): piv = next((r for r in range(pivot_row, len(rows)) if (rows[r] >> col) & 1), None) if piv is None: continue # free variable / underdetermined column rows[pivot_row], rows[piv] = rows[piv], rows[pivot_row] for r in range(len(rows)): if r != pivot_row and (rows[r] >> col) & 1: rows[r] ^= rows[pivot_row] pivot_row += 1 return rows # back-substitute / read off bit n_unknowns of each row ` Bit-packing rows into Python ints (or numpy uint64 words, or a real bitvector library for large n) turns each row-XOR into O(n/64) machine words instead of O(n) scalar ops — worth doing whenever n` is more than a few hundred bits, which covers essentially every CTF-sized LFSR or CRC.

4. Recognize it hiding inside other attacks. This is the common solving core behind several named techniques, not a standalone challenge type on its own: - LFSR State Recovery — when the keystream itself hands you the seed — state (and optionally taps) from keystream bits. - CRC and Polynomial Recovery — forging or reversing a checksum built from GF(2) division — CRC/checksum is an affine function of input bits; solve for unknown input bits or forge a target checksum. - Related-Key Attack — exploiting encryptions under keys with a known relationship — when a key schedule's difference propagation is linear over GF(2), the master-key-bit relations reduce to this system directly instead of a statistical differential search. - Feistel Structure — the split-and-XOR shape that tells you which attack family applies — if the round function F itself is XOR/linear (no real S-box), the whole cipher collapses to a GF(2) system. - S-box Analysis — profiling a cipher's S-box to pick the right statistical attack — confirming an S-box is affine is itself a GF(2) linear-algebra check (fit each output bit as a linear form of the input bits over the full truth table; zero residual = affine). - Berlekamp-Massey Algorithm — recover the minimal LFSR from raw keystream — a faster, purpose-built alternative to full Gaussian elimination when what you want is specifically the *minimal* LFSR tap polynomial from a keystream; prefer it over brute-force elimination when you don't already know the register length.

5. Watch for the field, not just the shape. "Set up a linear system and solve it" shows up for other algebraic structures that are NOT literally GF(2) and need different arithmetic underneath the same elimination idea: - Index Calculus — sub-exponential DLP attack for large prime fields with no smooth structure solves its relation matrix mod the group order n (or mod each prime factor via CRT) — integer/modular arithmetic, not bit-XOR. - GMAC (a GCM/AES construct, *not* a Poly1305 variant — the two only share a wiki page, Poly1305 Nonce Issues — nonce reuse turns a one-time MAC into a solvable polynomial, because both are one-time MACs broken by nonce reuse) lives in the extension field GF(2^128): "addition" is still XOR, but "multiplication" is polynomial multiplication modulo an irreducible polynomial, not AND. Poly1305 itself is arithmetic mod 2^130-5, not GF(2^128) — don't conflate the two. Use a real finite-field library (e.g. SageMath's GF(2^128)) for GMAC's multiplication — reusing bit-vector-only GF(2) code for it silently gives wrong answers. - Hill Cipher — a linear block cipher that known-plaintext breaks in one matrix inversion is linear algebra over Z_m (usually m = 26), with matrix inversion needing gcd(det K, m) = 1, not GF(2) at all.

Don't blur these: the elimination *algorithm* rhymes across all of them, but plugging GF(2) bit-XOR arithmetic into a problem that's actually mod-26 or mod-2^130-5 produces a system that looks solved but gives garbage.

What does NOT work

- Nonlinear combiner/filter generators. If a stream cipher mixes several LFSRs (or an LFSR's own bits) through a nonlinear boolean function before output, plain Gaussian elimination on the output bits fails outright — the equations are no longer linear in the state. You need correlation attacks against the weakly-correlated linear approximation, or an algebraic system per output tap; don't waste time trying to force a straight linear solve first when the challenge explicitly names a "combiner" or "filter" function. - Genuine S-boxes / AND-mixing. A real (non-affine) S-box makes at least one output bit a nonlinear (degree ≥ 2) function of the input bits. Fitting a GF(2)-linear system to it will either be inconsistent or silently wrong on unseen inputs. Confirm affinity first (zero nonlinear residual across the *whole* truth table, not just a few samples) before committing to this technique — see S-box Analysis — profiling a cipher's S-box to pick the right statistical attack. If it's not affine, pivot to Differential Cryptanalysis — chosen-plaintext XOR-difference propagation through S-boxes or Linear Cryptanalysis — known-plaintext linear approximation with a biased key parity bit instead. - LWE-style noisy systems. Without noise, b = A·s mod q is trivial Gaussian elimination (over Z_q, not even GF(2), unless q=2). The moment small error terms e_i are added, straight elimination no longer recovers s — the noise doesn't cancel, it accumulates and corrupts every derived unknown. That's the entire point of LWE's hardness; don't try to "solve through" the noise with more equations, you need a lattice attack (LWE Fundamentals — recognizing and breaking noisy linear equations mod q, Hidden Number Problem — recovering a secret from many small-bounded-error samples) instead. - Underdetermined systems mistaken for solvable ones. If you have fewer independent equations than unknowns (short keystream, short CRC sample, colliding rows after elimination), Gaussian elimination returns free variables, not a unique answer — a partial state-guess "solution" that passes on the observed data can still be wrong on unobserved bits. Check the rank of the matrix after elimination, not just that it ran without error; if rank < n_unknowns, get more samples rather than guessing the free bits. - Applying bit-XOR arithmetic where the real field is `Z_m` or `GF(2^k)`. Covered above, but worth repeating as a failure mode on its own: this is a very easy copy-paste mistake between Hill Cipher — a linear block cipher that known-plaintext breaks in one matrix inversion (mod m), GMAC's GF(2^128) multiplication (documented alongside Poly1305 on Poly1305 Nonce Issues — nonce reuse turns a one-time MAC into a solvable polynomial, but not the same field — Poly1305 itself is mod 2^130-5), Index Calculus — sub-exponential DLP attack for large prime fields with no smooth structure (mod group order), and true GF(2) problems — the elimination *code* looks reusable, the arithmetic underneath is not.

Related

LFSR State Recovery — when the keystream itself hands you the seed CRC and Polynomial Recovery — forging or reversing a checksum built from GF(2) division Hill Cipher — a linear block cipher that known-plaintext breaks in one matrix inversion Feistel Structure — the split-and-XOR shape that tells you which attack family applies S-box Analysis — profiling a cipher's S-box to pick the right statistical attack Index Calculus — sub-exponential DLP attack for large prime fields with no smooth structure Poly1305 Nonce Issues — nonce reuse turns a one-time MAC into a solvable polynomial Berlekamp-Massey Algorithm — recover the minimal LFSR from raw keystream Related-Key Attack — exploiting encryptions under keys with a known relationship Repeated / Linearly-Related Nonce Recovery — when nonces aren't reused, but ARE related by a known formula LWE Fundamentals — recognizing and breaking noisy linear equations mod q Hidden Number Problem — recovering a secret from many small-bounded-error samples Stream-Cipher Keystream Reuse — the umbrella break behind every reused-keystream challenge