基于混合整数线性规划的MORUS初始化阶段的差分分析

Differential Analysis of the Initialization of MORUS Based on Mixed-Integer Linear Programming

认证加密算法MORUS是凯撒(CAESAR)竞赛的优胜算法,抗差分分析性能是衡量认证加密算法安全性的重要指标之一。该文研究了MORUS算法初始化阶段的差分性质,首先给出了一个差分推导规则,可以快速获得一条概率较大的差分链。在此基础上利用混合整数线性规划(MILP)自动搜索技术求解更优的差分链。为了提高搜索速度,结合MORUS初始化阶段的结构特点给出了分而治之策略。根据ΔIV的重量、取值将MILP模型划分为多个子模型并证明了部分子模型的等价性,大大缩减了模型的求解时间,得到了MORUS初始化阶段1~6步状态更新的最优差分链。最后给出了简化版MORUS的差分-区分攻击,该文的结果较之前的工作有较大的提升。

The authenticated encryption algorithm MORUS is one of the finalists of Competition on Authenticated Encryption:Security,Apllicability,and Robustness(CAESAR).The ability to resist differential analysis is one of the important indicators to evaluate the security of authenticated encryption algorithm.The differential property of the initialization of MORUS is researched in this paper.Firstly,a differential deduction rule is proposed to give fast a differential characteristic with a relatively high probability.Based on this,a better differential characteristic is given by using Mixed-Integer Linear Programming(MILP).To improve the efficiency of solving the MILP model,a Divide-and-Conquer approach is showed.According to the weight and value of ΔIV,the MILP model is divided to many sub-models.The most sub-models are proved to be equivalent,and this reduces dramatically the time to solve the model.The best differential characteristics are given with 1 to 6 state update functions in the initialization of MORUS.Finally,the differential-distinguish attack on the simplified versions of MORUS is showed.This paper improves the result of the previous related work.