Using automatic generation of relaxation constraints to improve the preimage attack on 39-step MD4
Using automatic generation of relaxation constraints to improve the preimage attack on 39-step MD4
复制标题
利用自动生成松弛约束改进39步MD4的原像攻击
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
A. Semenov
中科院分区：
文献类型：
--
作者：
I. Gribanova;A. Semenov
本文对MD4哈希函数的截断变体构造了预像攻击。具体来说，我们研究了MD4算法前39步定义的MD4-39函数。我们建议对MD4-39进行新的攻击，它发展了H. Dobbertin在1998年提出的思想。也就是说，引入特殊的松弛约束是为了简化与寻找任意MD4-39哈希值的原像问题相对应的方程。然后将补充了松弛约束的方程简化为布尔可满足性问题（SAT），并使用最先进的SAT求解器进行求解。我们证明了一组松弛约束的有效性可以用一种特殊的黑盒函数来评估。因此，我们建议通过对该函数应用黑盒优化来自动生成松弛约束。所提出的方法使找到新的松弛约束成为可能，这些约束有助于对MD4-39进行基于sat的预像攻击，从而显着优于竞争对手。
In this paper we construct preimage attack on the truncated variant of the MD4 hash function. Specifically, we study the MD4-39 function defined by the first 39 steps of the MD4 algorithm. We suggest a new attack on MD4-39, which develops the ideas proposed by H. Dobbertin in 1998. Namely, the special relaxation constraints are introduced in order to simplify the equations corresponding to the problem of finding a preimage for an arbitrary MD4-39 hash value. The equations supplemented with the relaxation constraints are then reduced to the Boolean Satisfiability Problem (SAT) and solved using the state-of-the-art SAT solvers. We show that the effectiveness of a set of relaxation constraints can be evaluated using the black-box function of a special kind. Thus, we suggest automatic method of relaxation constraints generation by applying the black-box optimization to this function. The proposed method made it possible to find new relaxation constraints that contribute to a SAT-based preimage attack on MD4-39 which significantly outperforms the competition.