自动化搜索ARX型密码差分-线性特征的模型及应用

摘要

ARX结构是一类仅包含模加(Addition)、循环移位(Rotation)和异或（Exclusive-OR）运算的密码结构，在分组密码、流密码、Hash函数以及MAC算法中都有着广泛的应用。ARX型密码有着算法结构简单、运算效率高的特点，非常适合于软件的实现。
　　差分-线性分析方法是在1994年的美密会上被提出的。通过将满足一定条件的高概率截断差分特征与高偏差线性逼近进行组合得到高偏差的差分-线性特征，可对部分密码算法进行有效地攻击。2016年的欧密会上，Leurent使用差分-线性分析方法，结合改进的比特划分技术，对ARX型MAC算法Chaskey进行了攻击，严重威胁了Chaskey的安全性，体现了差分-线性分析方法对ARX型密码分析的有效性。
　　自动化搜索技术在密码学中有着广泛的应用。尤其在近几年，随着对ARX型密码研究的深入，已形成一整套搜索该类密码差分特征和线性逼近的自动化方法，然而并没有搜索差分-线性特征的自动化工具问世。在实际应用中，将搜索差分特征的自动化技术与搜索线性逼近的自动化技术进行简单结合，以期获得长轮数的差分-线性特征的方法并不十分可行。
　　鉴于如上现状，本文提出了自动化搜索ARX型密码差分-线性特征的模型，并给出了实现该模型的一种可行方法。同时，为验证该模型的有效性，本文将该模型应用到对ARX型MAC算法SipHash和分组密码SPECK的差分-线性分析中，给出了二者的差分-线性分析结果。
　　对于SipHash系列算法中使用最广泛的SipHash-2-4算法，本文找到了终止化阶段4轮的多条较优的差分-线性特征。其中最优特征的绝对值仅为2-2.84，进行区分攻击仅需27.68个已知明文。此前公布的最好的分析结果为差分分析结果，其最优的差分特征概率为2-35，区分需235对选择明文。在明文消息长度不大于7字节且不考虑生成MAC的四支异或运算的情况下，本文同样给出多条较优的差分-线性特征。此外，在原始消息长度不大于7字节情况下，本文给出了SipHash-2-4全算法的差分-线性分析结果，这是已知的对SipHash系列算法的第一个差分-线性分析结果。
　　对于SPECK系列算法，本文分别给出了最小分组实例SPECK32/64和最大分组实例SPECK128/192、SPECK128/256的差分-线性特征。同时，结合搜索到的特征，本文给出了具体差分-线性攻击的流程、数据复杂度、存储复杂度与时间复杂度等，这同样是已知对SPECK系列算法的第一个差分-线性分析结果。

目录

声明

摘要

符号说明

第一章 引言

§1．1 研究背景

§1．2 研究内容及成果

§1．3 论文结构

第二章 差分-线性分析方法与自动化搜索技术

2．1．1 密码分析的常用假设及原则

2．1．2 差分分析与线性分析

2．1．3 差分-线性分析

§2．2 自动化搜索技术

2．2．1 密码分析中的自动化搜索技术

2．2．2 STP求解器介绍

2．2．3 ARX型密码各组件的差分性质及CVC刻画

2．2．4 ARX型密码各组件的线性性质及CVC刻画

第三章 自动化搜索ARX型密码的差分-线性特征的模型

§3．1 自动化搜索模型的建立

§3．2 模型的实现方法

第四章 SipHash算法的差分-线性分析

§4．1 SipHash算法简介

§4．2 SipHash的研究现状

§4．3 对SipHash的差分-线性分析

第五章 SPECK算法的差分-线性分析

§5．1 SPECK算法简介

§5．2 SPECK算法安全性分析

§5．3 对SPECK32的差分-线性分析

5．3．1 寻找差分-线性特征

5．3．2 进行差分-线性分析

§5．4 对SPECK128的差分-线性分析

第六章 总结与展望

参考文献

致谢