TY - JOUR
ID - 24884
TI - Toward A More Efficient Gröbner-based Algebraic Cryptanalysis
JO - Journal of Computing and Security
JA - JCS
LA - en
SN - 2322-4460
AU - Arabnezhad, Hossein
AU - Sadeghian, Babak
AD - Department of Computer Engineering, Amirkabir University of Technology, Tehran, Iran.
Y1 - 2020
PY - 2020
VL - 7
IS - 2
SP - 103
EP - 117
KW - Algebraic Cryptanalysis
KW - Gröbner basis
KW - Universal Proning
KW - S-box representation
DO - 10.22108/jcs.2020.123673.1050
N2 - 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. Chosen correlated plaintexts, as what appears in 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 the Universal Proning technique to provide an efficient method to recover such linear polynomials. Another important parameter in the algebraic cryptanalysis of ciphers is to effectively describe the cipher. We employ the so-called Forward-Backward representation of S-boxes together with Universal Proning to help provide a more powerful algebraic cryptanalysis based on Gröbner-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 the cryptanalysis of several lightweight 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.
UR - http://jcomsec.ui.ac.ir/article_24884.html
L1 - http://jcomsec.ui.ac.ir/article_24884_9daf850f015f16c38c431d919b691b3f.pdf
ER -