An Improved SAT-Based Guess-and-Determine Attack on the Alternating Step Generator
An Improved SAT-Based Guess-and-Determine Attack on the Alternating Step Generator
复制标题
一种改进的基于 SAT 的对交替步进发生器的猜测和确定攻击
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
S. Kochemazov
中科院分区：
文献类型：
--
作者：
O. Zaikin;S. Kochemazov
在本文中，我们提出了一种算法，用于构建对按键发电机的猜测和确定性攻击，并将其应用于替代步骤生成器（ASG）的加密分析（ASG）和两个修改（MASG和MASG0）攻击，我们首先“猜测”初始状态的某些部分，然后应用一些程序来确定猜测是否正确，我们可以使用猜测的信息来解决问题，从而进行详尽的搜索我们建议在“确定”算法中使用的所有可能的分配设置可以通过Monte-Carlo方法估算相应的猜测和确定性攻击的运行时，因此我们可以通过Black-Box优化算法搜索一组最佳攻击的位增强了我们对ASG，MASG和MASG0的构建和实施的攻击，以证明我们显示的运行时估计是可靠的。控制登记册的所有可能状态，并介绍有关ASG和MASG/MASG0加密分析的实验结果，总寄存器长度为72和96以前尚未发表在文献中。
In this paper, we propose an algorithm for constructing guess-and-determine attacks on keystream generators and apply it to the cryptanalysis of the alternating step generator (ASG) and two its modifications (MASG and MASG0). In a guess-and-determine attack, we first “guess” some part of an initial state and then apply some procedure to determine, if the guess was correct and we can use the guessed information to solve the problem, thus performing an exhaustive search over all possible assignments of bits forming a chosen part of an initial state. We propose to use in the “determine” part the algorithms for solving Boolean satisfiability problem (SAT). It allows us to consider sets of bits with nontrivial structure. For each such set it is possible to estimate the runtime of a corresponding guess-and-determine attack via the Monte-Carlo method, so we can search for a set of bits yielding the best attack via a black-box optimization algorithm augmented with several SAT-specific features. We constructed and implemented such attacks on ASG, MASG, and MASG0 to prove that the constructed runtime estimations are reliable. We show, that the constructed attacks are better than the trivial ones, which imply exhaustive search over all possible states of the control register, and present the results of experiments on cryptanalysis of ASG and MASG/MASG0 with total registers length of 72 and 96, which have not been previously published in the literature.