Toward A More Efficient Gröbner-based Algebraic Cryptanalysis

Document Type: Original Article


Department of Computer Engineering, Amirkabir University of Technology



In this paper, we propose a new method to launch a more efficient algebraic cryptanalysis.
Algebraic cryptanalysis aims at finding the secret key of a cipher by solving a collection of polynomial equations that describe the internal structure of the cipher,
while chosen correlated plaintexts, as what appears in textit{higher order differential} cryptanalysis and its derivatives such as cube attack or integral cryptanalysis,
forces many linear relations between intermediate state bits in the cipher. In this paper, we take these polynomial relations into account, so it becomes possible to simplify the equation system arising from algebraic cryptanalysis,
and consequently solve the polynomial system more efficiently.
We take advantage of Universal Proning technique to provide an efficient method to recover such linear polynomials.
Another important parameter in algebraic cryptanalysis of ciphers is to effectively describe the cipher.
We employ the so-called textit{Forward-Backward} representation of S-boxes together with Universal Proning to help provide a more powerful algebraic cryptanalysis based on Gr"obner-basis computation.
We show our method is more efficient than doing algebraic cryptanalysis with MQ representation, and also than employing MQ together with Universal Proning.
To show the effectiveness of our approach, we applied it for cryptanalysis of several light weight block ciphers.
By this approach we managed to mount algebraic attack on 12-round LBlock, 6-round MIBS, 7-round PRESENT and 9-round SKINNY light-weight block ciphers, so far.


Main Subjects

Articles in Press, Accepted Manuscript
Available Online from 16 August 2020
  • Receive Date: 24 June 2020
  • Revise Date: 15 July 2020
  • Accept Date: 16 August 2020