基于图论方法的SHA-1差分路径的精准概率计算  

Accurate Probability Calculation of SHA-1 Differential Path Based on Graph Theory

作　　者：李婧瑜 杨阳 曾光 李德刚 LI Jing-Yu;YANG Yang;ZENG Guang;LI De-Gang(State Key Laboratory of Mathematical Engineering and Advanced Computing,PLA Strategic Support Force Information Engineering University,Zhengzhou 450001,China;Trusted Computing and Information Assurance Laboratory,Institute of Software,Chinese Academy of Sciences,Beijing 100190,China)

机构地区：[1]中国人民解放军战略支援部队信息工程大学数学工程与先进计算国家重点实验室,郑州450001 [2]中国科学院软件研究所可信计算与信息保障实验室,北京100190

出　　处：《密码学报》2021年第3期452-467,共16页Journal of Cryptologic Research

基　　金：国家重点研发计划(2017YFB0803203);国家自然科学基金(61972413);数学工程与先进计算国家重点实验室开放基金(2020A08)。

摘　　要：针对SHA-1算法,Stevens提出了以联合概率为基础的高精度差分路径概率模型.它是一个理论值的求解方案,并将理论值分割成三个部分,但对差分路径的概率计算停留在理论层面,未能给出具体的计算方法.本文对第三部分概率进行深入分析,结合图论的方法证明了在由两类最优扰动向量得到的差分路径中,该部分的连通分支中只存在1个或2个布尔函数比特位的结构特性,并给出了两类连通分支的概率特征,利用这些结论可以简化求取差分路径成立概率的过程.最后通过一个差分路径实例展示了概率的具体计算过程,实例证明,本文的差分路径概率模型较原始计算方法(独立地计数充分条件的个数)得到的概率值更贴近真实值,表明了本文的改进概率模型可以对差分路径的概率进行更精准的刻画与计算.For the SHA-1 algorithm,Stevens proposed a high-precision differential path probability model based on joint probability.It is a solution to a theoretical value,and the theoretical value is divided into three parts.However,the probability calculation of the differential path stays at the theoretical level and no specific calculation method is given.In this paper,the probability of the third part is analyzed in depth,and combining graph theory,it is proved that in the differential path obtained by the two types of optimal perturbation vectors,there is a structure characteristic that every connected branch has only one or two Boolean function bits.The probabilistic characteristics of the two types of connected branches are also given.Using these conclusions can simplify the process of obtaining the probability of the differential path.Finally,a specific example of differential path is presented to show the specific calculation process of the probability.The example proves that the differential path probability model in this paper is closer to the true value than the probability value obtained by the original calculation method(independently counting the number of sufficient conditions),which shows that the improved probability model in this paper can more accurately describe and calculate the probability of the differential path.

关 键 词：SHA-1算法 差分路径 概率模型 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]