Toward A More Efficient Gröbner-based Algebraic Cryptanalysis

Abstract

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.<br />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.