基于MILP寻找SM4算法的差分特征

摘要

基于混合整数线性规划(mixed integer linear programming, MILP)的自动化搜索方法被广泛用于搜索密码算法的差分特征,已形成一套完整的框架.该框架采用的基本原理是用线性不等式来刻画密码算法的各个操作,该框架适用于搜索采用4-bit S盒的密码算法的差分特征.对于采用8-bit S盒的密码算法,基于该框架的搜索模型计算量很大,以致无法高效地找到差分特征.SM4算法于2006年由中国政府发布,于2012年成为国家密码行业标准,于2016年成为国家标准的迭代分组密码算法,其分组状态为128 b,每轮包含4个8-bit的S盒.为了高效地搜索SM4算法的差分特征,研究了对8-bit S盒进行MILP建模的问题,对于采用8-bit S盒的密码算法,改进了搜索高概率差分特征的方法.对于19轮SM4算法,不仅找到了概率为2的差分特征,而且找到了概率为2的差分特征,这是目前基于MILP建模找到的SM4算法轮数最多、概率最高的差分特征.