Table-based guess and determine attack and application to SOSEMANUK

期刊论文
发表日期：

2025年3月31日

查看全文

Zhengting Li,
Lin Ding,
Xinhai Wang,
Zheng Wu

摘要

In this paper, a new variant of the Guess and Determine attack, called table-based Guess and Determine attack, is proposed. By building tables to solving the system of nonlinear equations, the new variant enables the attacker to recover all internal state bits by guessing less bits, which leads to a lower time complexity. To search for the solvable systems, a general tool called SEQsearch is proposed. This is an algorithmic and easy-to-use tool for the attacker to explore table-based Guess and Determine attacks. By applying SEQsearch to the SOSEMANUK stream cipher which is one of the seven eSTREAM finalists, two solvable systems of nonlinear equations are found, and then a table-based Guess and Determine attack on SOSEMANUK with complexities all below $2^{162}$ $2^{162}$ is proposed, which is ${2^{14}}$ $2^{14}$ times better than the best known Guess and Determine attack on SOSEMANUK in terms of the complexity level. To the best of our knowledge, this is the first time that solving the systems of nonlinear equations by building tables is successfully embedded in a Guess and Determine attack. This is the main reason that we can propose a new Guess and Determine attack on SOSEMANUK after more than ten years without new results.