Encyclopedia

Algebraic attack

Cryptanalytic attacks using a system of multivariate equations

Wikipedia contributorsAdapted for Fathomly · View authors

5 min read
Source updated August 19, 2026

Algebraic attack is a method of algebraic cryptanalysis by which a set of algebraic equations can be used to solve a cryptographic Boolean function that has a low degree or a high degree of non linearity. The main objective is to reduce the non linearity of the equations and then solve the cipher to decrypt into plaintext. It has been used for vulnerability testing for encryption algorithms as well as hacking systems for malicious intent.

01Theory

Algebraic attacks can be used for a variety of cryptosystems which is the encryption scheme consisting of five tuples which are

Set of plaintext units denoted as ${\mathcal {P}}$
Set of ciphertext units denoted as ${\mathcal {C}}$
Set called key space denoted as ${\mathcal {K}}$
Encryption function for every $k\in K$ where $E_{k}:{\mathcal {P}}\rightarrow {\mathcal {C}}$
Decryption function for every $k\in K$ where $D_{k}:{\mathcal {C}}\rightarrow {\mathcal {P}}$

A map between $E_{k(1)}$ and ${\textstyle D_{k(2)}$ exists such that $E_{k(1)}\circ D_{k(2)}=id_{k}$ for every $k\in K$ . Thus the pair $(k(1),k(2))$ becomes key pair.

The most basic process of describing encryption and decryption in cryptography using XOR cipher is as follows with an example :

${\mathcal {P}}$ (10011) XOR ${\mathcal {K}}$ (10110) = ${\mathcal {C}}$ (00101)
${\mathcal {C}}$ (00101) XOR ${\mathcal {K}}$ (10110) = ${\mathcal {P}}$ (10011)

The cryptosystem becomes symmetric when $k(2)$ can be computed efficiently from $E_{k(1)}$ and $k$ else if not then it is a public key cryptosystem. In block cipher, the plaintext is broken into plaintext units and encrypted by fixed key $k$ meanwhile in stream cipher, a Boolean function is used to generate a set of keys or keystream $k_{1},k_{2},\ldots$ from an initial key $k$ and then this keystream is used to encrypt the plaintext units individually.

Assuming ${\mathcal {P}}$ and ${\mathcal {C}}$ as subsets of finite vector spaces of characteristic 2 where the field is $K=F_{q}$ and $q=2^{e}$ or $p^{e}$ where $p$ is the characteristic and

every map $\phi :K^{n}\rightarrow K^{m}$ is a polynomial such that

$\phi (a_{1},\ldots ,a_{n})=(f_{1}(a_{1},\ldots ,a_{n}),\ldots ,f_{m}(a_{1},\ldots ,a_{n}))$

The main criteria for deciding to algebraic attack a stream or a block cipher is algebraic immunity $AI$ .

For a set of all Boolean functions $B_{n}$ of n input variables with mapping of strings to values as $\{0,1\}^{n}\rightarrow {0,1}$ then each Boolean function $f$ can be represented as a multivariate polynomial over GF(2) which is called the algebraic normal form (ANF).

$f(x_{1},\ldots ,x_{n})=a_{0}+\sum _{1\leqslant i\leqslant n}a_{i}x_{i}+\sum _{1\leqslant i\leqslant j\leqslant n}a_{i,j}x_{i}x_{j}+\ldots +a_{1,2,\ldots ,n}x_{1}x_{2}\ldots x_{n},$

where the coefficients $a_{0},a_{i},a_{i,j},\ldots ,a_{1,2,\ldots ,n}\in \{0,1\}$ and $deg(f)$ is the algebraic degree or number of variables in highest order term with non zero coefficient.

Also $g\in B_{n}$ is annihilator of $f\in B_{n}$ if $f\cdot g=0$

Given $f\in B_{n}$ , algebraic immunity $AI(f)$ is defined as minimum degree of all annihilators of $f$ or $1+f$ .

$AI(f)=(f\oplus 1)\cdot g=0$

This annihilator is exactly located at $\left\lceil {\frac {N}{2}}\right\rceil$ therefore,

$AI(f)\leqslant \left\lceil {\frac {N}{2}}\right\rceil$

02History of algorithms and preventive techniques

Early algorithms

Algebraic attack has many ways of decrypting an encrypted message using well developed cryptanalysis algorithms. The overall one-size-fits-all approach is breaking the stream or block cipher as a system of multivariate polynomial equations using a GF(2) binary field. The unknowns in the equations are what we need to solve for as they are the keys. If it is solved the key is recovered.

One of the approaches to achieve this is the attack on stream cipher done with the help of an over defined system of algebraic equations. Thus the $2^{92}$ toyocrypt (TOYOCRYPT-HRI) stream cipher can be attacked in $2^{49}$ CPU clocks with only 20 KB of keystream which is the fastest attack to break this encryption. LILI-128 can be broken with an algebraic attack in $2^{57}$ CPU clocks. If the stream cipher will at most use 10 Linear Feedback Shift Registers (LFSR) and a Boolean function $f$ , the cipher can be broken with a general algebraic attack.

If the cipher is having non linear equation system the attacker can try to replace the non linear terms with variables thus exceeding the variable count than in the original non linear equation. If the new equation system is solvable, they put the variable solution thus making the original equation linear. Common algebraic equation can be used then to solve the system.

To make good approximation for the key value pairs in the cipher sent using linear cryptanalysis is another method of solving the cipher. One can use $2^{21}$ known plaintexts to break the 8 round Data Encryption Standard (DES) and $2^{47}$ plaintexts to break the 16 round DES in this method which is also one of the first practically described use case of algebraic attack using linear cryptanalysis.

Cube attacks later developed are one of the algebraic attack sub method by which the Bluetooth E0 encryption can be converted into the plaintext in fraction of a second. This was further improvement from the precomputation algorithms that were the fastest known to break the Bluetooth cipher.

Modern algorithms

SAT solvers are widely used standard of doing algebraic attacks. It is similar to how we solve NP-complete problems which are the hardest problems to solve in the NP class and easy to verify in polynomial time. SAT solvers take up the logical formula and return the Boolean true or false value depending on whether the solution exists for the problem or not.

Gröbner basis attack uses Gröbner basis of an ideal which is a polynomial equation system with same variety (or solutions) and is easier to solve but computationally expensive. The reduced Gröbner basis generating the zero dimensional ideal has a univariate form and can be solved with factorization. On a 3 round pure cipher, a 96 bit key is found under a second and uses very less (plaintext, ciphertext) pairs. Thus this is a lot faster than using exhaustive search of key space using Gröbner basis. This algorithm is directly based from Bruno Buchberger as he had computed the Gröbner basis of an ideal.

Preventive techniques

There has been research work for strengthening the Crypto-1 stream cipher by causing the attackers to use too high CPU time and too high memory in the modified version of Crypto-1. This is one of the demonstrated ways to protect encryption from algebraic attack in RFID systems.

S-box technique is used for securing image transfer so that the information enclosed within the image cannot be decrypted. It has thus been used in satellite image encryption using Fredkin logic.

03Notable examples

Keeloq remote access to car and door alarms with an experimental attack was successfully broken in 2007. Given $2^{16}$ known plaintexts, a slide-algebraic attack that uses a SAT solver can break $2^{53}$ Keeloq encryptions in $2^{64}$ CPU clocks. It is also the first time that a real life full round cipher has been broken using an algebraic attack.

Bluetooth stream cipher E0 is decoded easily by many attacks including algebraic and hence are removed from 4.0 versions which used the AES-CCM encryption standard. For E0's four LFSR system its initial value can be found using an algebraic attack that has a realistic space complexity of $2^{83}$ (84MB RAM) and time complexity of $2^{87}$ CPU clocks.

Data Encryption Standard (DES) although robust from complete break was last widely used in 2001 for banking services and government websites as a result of vulnerability to algebraic attacks. One of the algebraic attacks on 6 round DES can be done with just a single plaintext.

Reduced round version of Data Encryption Standard (DES) and KeeLoq remote car locking ciphers were broken by SAT solvers which outperformed the Gröbner basis technique which is used when the keystream is extremely small. It was shown that the Hitag2 ciphers commonly used in automobiles can be broken in few hours using the same SAT solvers and algebraic attack with conversion.

Modern cryptography algorithms such as Post Quantum Cryptography are trying to prevent algebraic attacks made by hackers using quantum computer in future. One such algorithm is Cryptographic Suite for Crystal Lattices (CRYSTALS).

Watch videos about Algebraic attackExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Algebraic attack”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Public key encryption.svg by Davidgothberg, Public domain
Overview of LILI-128 keystream generators.png by Xiangao Huang, Chao Wang, Wei Huang, Junxian Li, CC BY 4.0

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.