基于混合整数规划的自动化密码分析研究

Mixed-Integer Programming is a widely applicable mathematical optimization method. It has been attracting extensive attentions from both theoretical investigation and engineering implementation for almost half a century. Therefore, automating the process of cryptanalysis with MIP technique —— a powerful mathematical tool, will hopefully reduce the cost of cryptanalysis considerably. . This project studies the application of MIP technique in cryptanalysis, which includes automatic algebraic cryptanalysis by solving systems of multivariate polynomials equations over GF(2), and MIP based automatic differential and linear cryptanalysis. We will investigate the construction of MIP models for problems appearing in cryptanalysis, and the optimization of the algorithms for solving such MIP models.. This project emphasizes the real applications of the MIP based tools for automatic cryptanalysis. We will develop software for automatic cryptanalysis based on MIP technique, conduct large-scale computational experiments, and analyze some well-known ciphers such as DES, DESL, PRESENT, LBlock, SIMON and EPCBC. This will not only provide a practice platform for MIP based automatic cryptanalysis, but also be beneficial to making full use of the domestic resources of super-computing..

混合整数规划（MIP）是一种应用广泛的数学优化方法，无论是其理论研究还是工程实现，近半个世纪一直备受关注。因此，利用MIP这一强有力的数学工具进行自动化密码分析有望大大降低密码分析的成本。. 本课题研究基于MIP的自动化密码分析技术。主要包括利用MIP求解二元域上多元多项式方程组的自动化代数攻击和基于MIP的自动化差分、线性分析技术。我们将在本项目中探索密码分析问题的MIP建模，及针对由密码分问题导出模型的MIP求解算法的优化。. 本项目注重MIP自动化工具的实际应用，我们将开发基于MIP的自动化密码分析软件，进行大规模的实际计算，并对一些著名算法（如：DES、DESL、PRESENT、LBlock、SIMON和EPCBC等）进行分析，这不仅为推动MIP和自动化密码分析技术的研究提供了实践平台，也有利于国内超级计算资源的充分利用。

差分分析、不可能差分分析、线性分析、零相关线性分析、积分分析、相关密钥分析、杂凑函数的原像与碰撞搜索等，是对称密码分析的一系列重要的已知方法。自高级加密标准AES问世以来，所有需要得到学术界及工业界认可的对称密码算法，都必须提供其抵抗已知攻击的安全强度分析。然而，对称密码分析通常涉及跟踪各种代表不同意义的比特模式在密码算法各个部件中的传播模式，极为繁琐复杂。项目组首次提出了精确刻画密码算法比特级密码学性质的整数规划建模方法，基于该方法提出的自动化密码分析方法，自动化程度高，引起了国内外相关研究机构和应用单位的广泛关注。我们提出方法既适用于搜索字级截断差分，也适用于比特级算法确切差分特征的搜索；既适用于单密钥模型，也适用于相关密钥模型；既可以自动化搜索用于攻击的差分线性特征，也可以用于评估密码算法抵抗差分线性攻击的安全界。利用该方法，我们对一些列知名的具体算法进行了分析，包括SIMON、SPECK、SKINNY、PRIDE、SIMECK、LBlock、RECTANGLE和基于Keccak的认证加密算法等。对部分算法的分析结果，达到了国际最优水平。基于本项目的理论成果，我们开发了一个自动化密码分析软件框架，该工具自动化程度较高，使用简便，大大提高了研究组日常密码分析工作的效率，引起了包括兴唐、电子三十所等在内的多个密码学研究和产业机构的关注。利用该软件框架，我们承担了国家密码管理局、军队、航天等相关单位多项对称密码算法设计与分析任务。