Also known as: algebraic attack, algebraic cryptanalysis

An algebraic attack writes a cipher as a system of equations in which the known plaintext and ciphertext are coefficients and the key or internal state are the unknowns, then solves the system directly.¹ When the equations are linear over a field or ring, the solve is exact and fast (Gaussian elimination); a cipher whose update is truly linear falls immediately, which is one reason real ciphers add nonlinearity.²

Each known byte is one equation; enough equations over-determine the unknowns and the linear algebra returns them — when the system really is linear.

How it works

The analyst posits a parametric form for the update — say state' = A·state + B + input — and turns each observed transition into an equation modulo the cipher’s word size (2⁸, 2¹⁶, or a prime). Gaussian elimination over that ring, using modular inverses where the modulus is not prime, solves for the constants or proves no solution exists. Nonlinear ciphers resist this: the system becomes high-degree, and the analyst must either linearize, restrict to a subspace, or hand the equations to a SAT/SMT solver.

Relevance to SDR

Algebraic solving is the fast first pass when reverse-engineering an encoder. GopherTrunk’s clean-room analysis of the Motorola P25 talker-alias obfuscation (issue #773) solved modular linear systems (over ℤ/256 and ℤ/2¹⁶, with modular inverses) to recover the per-character keystream and to rule out every linear and low-degree-polynomial update — the negative result that proved the cipher’s core is genuinely nonlinear.

Sources

1. Algebraic attack — Wikipedia, for modeling a cipher as a solvable equation system. ↩

2. Linear cryptanalysis — Wikipedia, for why linear structure is exploitable and must be avoided in real ciphers. ↩

See also

• SAT/SMT solving
• Brute-force attack (exhaustive key search)
• Known-plaintext attack
• Convolutional code
• Cyclic redundancy check (CRC)