English  简体中文
搜索   
首页 中心概况 新闻动态 科研成果 研究队伍 技术园地 公共信息 联系我们

分组密码和SHA-3杂凑函数的差分分析


2017-05-16        撰稿人: 乔珂欣



学科专业:信息安全

研究方向:密 码 学

指导教师:胡磊 研究员

 

 

 

 

分组密码和杂凑函数是信息安全的底层模块,在数据保密、身份认证、安全通信等方面起着重要作用。对分组密码和杂凑函数的设计及安全性分析和评估是现代密码学领域的重要研究内容。差分分析是对分组密码和杂凑函数最有效的分析方法之一。本文围绕差分分析进行了研究。杂凑函数方面,对SHA-3杂凑函数标准Keccak 系列运用代数分析与差分分析相结合的方法进行了约减轮碰撞攻击。分组密码方面,改进了基于线性规划的自动化差分搜索方法,并应用于FOX 密码算法;将动态密钥猜测技术进行了自动化程序实现,并用于分析Simon Simeck 算法。此外,本文研制了轻量级密码算法设计中常用的4-比特S 盒的高效硬件实现工具。具体研究工作和成果如下:

1. 给出了SHA-3 杂凑函数标准Keccak 系列多个版本的5 轮实际碰撞攻击,其中对SHAKE128 版本的攻击结果是目前已知对SHA-3 标准算法的最高轮数实际攻击。我们原创性地提出了可线性化仿射子空间的理念,用于将SHA-3 底层置换函数中唯一的非线性部件S 盒在子空间上进行线性化,从而将搜索满足2 轮特定差分要求的消息对的问题转化为线性方程组的求解问题,方程组的解空间即提供了以概率1 满足2 轮差分要求的消息空间,进而在解空间中以实际可行的计算复杂度搜索后面3 轮的消息碰撞,最终得到5 轮碰撞。利用该方法,我们在少于3 小时的单核计算时间内找到了SHAKE128 和两个Keccak 挑战赛版本的5 轮消息碰撞实例,并将前人4 轮碰撞攻击计算复杂度的对数降低了一半。

2. 改进了基于线性规划的自动化差分搜索方法中对异或操作的建模,并得到对Lai-Massey 结构分组密码FOX 更准确的安全性估计。基于线性规划的自动化差分搜索方法将密码算法的高概率差分搜索问题转化为线性规划问题。我们发现该方法由于对差分传播模式描述上的粗糙性,无法得到FOX 密码的有效差分迹。通过重构差分在异或操作上传播模式的线性不等式约束,改进后的方法完全消除了原方法应用于FOX 密码时产生的无效差分迹。利用改进后的方法,我们得到了FOX 密码算法的更紧的活跃S 盒个数下界,证明了6 (而非之前所认识的8 ) FOX64 的最高差分概率不超过2-64,足够抵抗基本差分攻击。

3. 将差分分析密钥恢复阶段的动态密钥猜测技术进行了自动化实现,并用于分析Simon Simeck 分组密码算法。Simon 算法是美国国家安全局提出的轻量级分组密码算法,Simeck CHES 2015 上提出的类似Simon的算法。动态密钥猜测技术是针对该类密码提出的,从攻击轮数上优于传统的密钥猜测方法,但是具有计算繁琐的缺点。我们将该技术进行了程序实现,程序可以自动输出密钥猜测过程中涉及的密钥比特和计算复杂度,大大减少了复杂度计算的工作量。结合本文找到的高概率差分和原有差分,我们给出了2122 Simeck3228 Simeck483435 Simeck64 22 Simon32/6424 Simon48/962829 Simon64/962930 Simon64/128 的差分分析结果。

4. 研制了4-比特S 盒的低电路深度实现工具。用NOTANDNANDORNORXORXNOR 逻辑门实现S 盒时,低电路深度意味着低延迟和高时钟频率。将S 盒的每个输出比特看作输入比特的布尔函数,用递归算法枚举出一定深度阈值内可以实现的布尔函数,将真值表和最低延迟的实现方式存储下来。对任意给定4-比特S 盒,解析出其对应的布尔函数真值表,即可即时给出深度最低的硬件实现方式。利用该工具,我们还给出了具有最优差分性质和线性性质且能在最小深度内实现的4-比特S 盒。

 

    关键词:分组密码;杂凑函数;SHA-3 算法;差分分析;线性规划;线性化技术;碰撞攻击;S


评论人:          
lois.local\

DCS 中心 版权所有
地址:北京市海淀区闵庄路甲89号 4号楼
联系电话:010-82546536 010-82546537
京ICP备05046059号