Algebraic attack - Wikipedia
Jump to content
Search
Search
Donate
Create account
Log in
Personal tools
Donate
Create account
Log in
Algebraic attack
Add languages
Add links
From Wikipedia, the free encyclopedia
Cryptanalytic attacks using a system of multivariate equations
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.
Theory<br>[edit]
Algebraic attacks can be used for a variety of cryptosystems which is the encryption scheme consisting of five tuples which are[1]
Set of plaintext units denoted as
{\displaystyle {\mathcal {P}}}
Set of ciphertext units denoted as
{\displaystyle {\mathcal {C}}}
Set called key space denoted as
{\displaystyle {\mathcal {K}}}
Encryption function for every
{\displaystyle k\in K}
where
{\displaystyle E_{k}:{\mathcal {P}}\rightarrow {\mathcal {C}}}
Decryption function for every
{\displaystyle k\in K}
where
{\displaystyle D_{k}:{\mathcal {C}}\rightarrow {\mathcal {P}}}
A map between
{\displaystyle E_{k(1)}}
and
{\textstyle D_{k(2)}}
exists such that
{\displaystyle E_{k(1)}\circ D_{k(2)}=id_{k}}
for every
{\displaystyle k\in K}
. Thus the pair
{\displaystyle (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 :
{\displaystyle {\mathcal {P}}}
(10011) XOR
{\displaystyle {\mathcal {K}}}
(10110) =
{\displaystyle {\mathcal {C}}}
(00101)
{\displaystyle {\mathcal {C}}}
(00101) XOR
{\displaystyle {\mathcal {K}}}
(10110) =
{\displaystyle {\mathcal {P}}}
(10011)
Public key cryptosystem<br>The cryptosystem becomes symmetric when
{\displaystyle k(2)}
can be computed efficiently from
{\displaystyle E_{k(1)}}
and
{\displaystyle 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
{\displaystyle k}
meanwhile in stream cipher, a Boolean function is used to generate a set of keys or keystream
{\displaystyle k_{1},k_{2},\ldots }
from an initial key
{\displaystyle k}
and then this keystream is used to encrypt the plaintext units individually.[1]
Assuming
{\displaystyle {\mathcal {P}}}
and
{\displaystyle {\mathcal {C}}}
as subsets of finite vector spaces of characteristic 2 where the field is
{\displaystyle K=F_{q}}
and
{\displaystyle q=2^{e}}
or
{\displaystyle p^{e}}
where
{\displaystyle p}
is the characteristic and
every map
{\displaystyle \phi :K^{n}\rightarrow K^{m}}
is a polynomial such that
{\displaystyle \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
{\displaystyle AI}
For a set of all Boolean functions
{\displaystyle B_{n}}
of n input variables with mapping of strings to values as
{\displaystyle \{0,1\}^{n}\rightarrow {0,1}}
then each Boolean function
{\displaystyle f}
can be represented as a multivariate polynomial over GF(2) which is called the algebraic normal form (ANF).[2]
{\displaystyle 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
{\displaystyle a_{0},a_{i},a_{i,j},\ldots ,a_{1,2,\ldots ,n}\in \{0,1\}}
and
{\displaystyle deg(f)}
is the algebraic degree or number of variables in highest order term with non zero coefficient.
Also
{\displaystyle g\in B_{n}}
is annihilator of
{\displaystyle f\in B_{n}}
if
{\displaystyle f\cdot g=0}
Given
{\displaystyle f\in B_{n}}
, algebraic immunity
{\displaystyle AI(f)}
is defined as minimum degree of all annihilators of
{\displaystyle f}
or
{\displaystyle 1+f}
.[2]
{\displaystyle AI(f)=(f\oplus 1)\cdot g=0}
This annihilator is exactly located at
{\displaystyle \left\lceil {\frac {N}{2}}\right\rceil }
therefore,[2]
{\displaystyle AI(f)\leqslant \left\lceil {\frac {N}{2}}\right\rceil }
History of algorithms and preventive techniques<br>[edit]
Early algorithms<br>[edit]
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.[3]
Overview of LILI-128 keystream generators<br>One of the approaches to achieve this is the attack on stream cipher done...