TY - JOUR
ID - 102461
TI - Extension of Cube Attack with Probabilistic Equations and its Application on Cryptanalysis of KATAN Cipher
JO - The ISC International Journal of Information Security
JA - ISECURE
LA - en
SN - 2008-2045
AU - Eskandari, Zahra
AU - Ghaemi Bafghi, Abbas
AD - Data and Communication Security Lab., Computer Dept., Ferdowsi University of Mashhad, Iran
Y1 - 2020
PY - 2020
VL - 12
IS - 1
SP - 1
EP - 12
KW - Cube Attack
KW - Probabilistic equation
KW - approximation
KW - Solving noisy equation system
DO - 10.22042/isecure.2020.199304.481
N2 - Cube Attack is a successful case of Algebraic Attack. Cube Attack consists of two phases, linear equation extraction and solving the extracted equation system. Due to the high complexity of equation extraction phase in finding linear equations, we can extract nonlinear ones that could be approximated to linear equations with high probability. The probabilistic equations could be considered as linear ones under some noises. Existing approaches to solve noisy equation systems work well provided that the equation system has low error rate; however, as the error rate increases, the success rate of finding the exact solution diminishes, making them rather inefficient in high error rate. In this paper, we extend Cube Attack to probabilistic equations. First, an approximation approach based on linear combinations of nonlinear equations is presented to find probabilistic linear equations with high probability. Then, we present an approach to improve the efficiency of current solving approaches and make them practical to solve high error rate linear equation system. Finally, utilizing proposed approaches, we find the right key under extended noisy equation system with lower complexity in comparison to the original Cube Attack.
UR - http://www.isecure-journal.com/article_102461.html
L1 - http://www.isecure-journal.com/article_102461_63043339d70cc19cf82405c666e85243.pdf
ER -