一种基于中间相遇的Ascon-Hash算法安全性评估方法

摘要: 本技术涉及轻量级密码分析,特别涉及一种基于中间相遇的ascon-hash算法安全性评估方法。背景技术:1、轻量级密码学在物联网(iot)系统、工业控制网络及大规...
一种基于中间相遇的Ascon-Hash算法安全性评估方法

本技术涉及轻量级密码分析,特别涉及一种基于中间相遇的ascon-hash算法安全性评估方法。

背景技术:

1、轻量级密码学在物联网(iot)系统、工业控制网络及大规模传感基础设施等资源受限环境中发挥着关键的安全保障作用。ascon算法凭借其高效的硬件实现和优异的轻量级性能,被美国国家标准与技术研究院(nist)选为轻量级密码学标准化算法的核心候选,其哈希模式ascon-hash广泛应用于嵌入式设备的数据完整性校验与消息认证场景。然而,随着量子计算技术的发展和应用场景对安全强度的持续提升需求,ascon-hash算法在实际部署前需要经过严格的安全性评估,以验证其在有限资源环境下抵抗各类密码分析手段的能力。

2、中间相遇(meet-in-the-middle, mitm)攻击是评估哈希函数原像攻击抵抗能力的重要安全性分析工具。其基本原理为:将密码算法的状态空间划分为red侧自由变量集合与blue侧自由变量集合,分别进行部分计算,并在匹配位置处建立两组候选值之间的关联,从而恢复原像或评估算法的有效安全强度。

3、针对ascon-hash的mitm安全性分析中,现有研究提出了基于混合整数线性规划(milp)的自动化配置搜索框架,通过优化red侧变量、blue侧变量和匹配位点的选择来寻找满足给定时间复杂度的分析路径。然而,面对状态规模达320位、结构非对齐的ascon算法时,milp模型需要为每一轮定义大量变量,所生成的问题规模庞大,导致分析过程中的计算开销和内存消耗急剧增加。然而,面对状态规模较大(320位)、结构非对齐的ascon密码算法时,milp模型需要为每一轮定义至少320个变量,所生成的milp问题规模庞大、计算繁重,因此会产生超出实际可用评估环境的内存容量限制的内存消耗,使得安全性评估在真实受限环境中难以有效部署。

技术实现思路

1、基于此,有必要针对上述技术问题,提供一种基于中间相遇的ascon-hash算法安全性评估方法。

2、本说明书采用下述技术方案:

3、本说明书提供了一种基于中间相遇的ascon-hash算法安全性评估方法,计算机执行以下步骤:

4、获取ascon-hash中间相遇分析候选配置;所述候选配置至少包含red侧变量集合、blue侧变量集合以及用于抑制red侧变量与blue侧变量交叉相乘的抵消位置集合;

5、根据所述候选配置,重建由抵消位置诱导的布尔抵消关系集合,并将所述布尔抵消关系集合划分为线性抵消关系集合和非线性抵消关系集合;

6、对所述线性抵消关系集合提取独立线性约束,并根据所述独立线性约束缩减red侧变量的枚举维度;对所述非线性抵消关系集合执行布尔多项式的三角剖分处理,以再次缩减red侧变量的枚举维度,并得到无法消元的残余非线性抵消关系集合;对所述残余非线性抵消关系集合中的每个残余关系进行red侧与blue侧可分离性判断,并对满足可分离形式的残余非线性抵消关系,构造red侧残差索引和blue侧兼容残差索引;

7、依据所述red侧残差索引和blue侧兼容残差索引,对缩减后red侧变量集合中的每个候选赋值进行分桶和过滤,得到过滤后的red侧变量表;并基于所述过滤后的red侧变量表与blue侧变量集合执行中间相遇匹配,得到满足匹配约束和抵消约束的原像候选,作为所述ascon-hash算法安全强度的评估依据。

8、进一步地,对所述线性抵消关系集合提取独立线性约束,并根据所述独立线性约束缩减red侧变量的枚举维度,包括:

9、将所述线性抵消关系表示为gf(2)上的仿射方程组,提取所述仿射方程组中与red侧变量对应的系数矩阵,并通过高斯消元法得到所述系数矩阵的秩和主元变量;

10、将所述主元变量对应的red侧变量表示为其余自由变量的函数,以缩减red侧变量的枚举维度;其中,当所述仿射方程组相容时,所缩减的red侧变量的枚举维度数量由所述系数矩阵的秩确定。

11、进一步地,对所述非线性抵消关系集合执行布尔多项式的三角剖分处理,包括:

12、在每轮迭代中,寻找能够针对red侧变量进行求解的非线性抵消关系,并通过所述非线性抵消关系将所述red侧变量表示为其余变量的函数,并将所述函数的表达式代入其余有效关系中,以消除所述red侧变量。

13、进一步地,构造red侧残差索引,包括:

14、对于满足可分离形式的每个残余非线性抵消关系,将其拆分为仅与red侧变量相关的red侧残差表达式、仅与blue侧变量相关的blue侧残差表达式以及常数项;

15、根据所述red侧残差表达式构造red侧残差索引,根据所述blue侧残差表达式构造blue侧兼容残差索引。

16、进一步地,对缩减后red侧变量集合中的每个候选赋值进行分桶和过滤,包括:

17、对缩减后red侧变量集合中的变量值进行枚举,并计算每个变量所对应的残差索引值,并将具有相同残差索引值的变量值存入同一桶中;

18、对blue变量集合中的变量值进行枚举并确定blue侧可访问的兼容残差索引集合;

19、并将red侧表中残差索引属于所述兼容残差索引集合的桶保留,得到过滤后的red侧变量表。

20、进一步地,根据布尔抵消关系集中各布尔抵消关系的代数形式,将所述布尔抵消关系集合划分为线性抵消关系集合和非线性抵消关系集合,其中,若布尔抵消关系在gf(2)上仅包含异或项和常数项,则判定为线性抵消关系,否则判定为非线性抵消关系。

21、进一步地,所述基于所述过滤后的red侧变量表与blue侧变量集合执行中间相遇匹配,包括:

22、基于red侧变量集合和blue侧变量集合构成可分离匹配方程;

23、通过所述可分离方程对所述过滤后的red侧变量表与blue侧候选赋值执行中间相遇匹配,获得满足匹配约束和抵消约束的原像候选。

24、进一步地,基于sat模型对ascon-hash算法的中间相遇分析配置进行搜索,以获取满足目标时间复杂度的ascon-hash中间相遇分析候选配置。

25、本说明书提供了一种计算机可读存储介质,所述存储介质存储有计算机程序,所述计算机程序被处理器执行时实现上述针对ascon-hash 3的新型低内存消耗中间相遇攻击方法。

26、本说明书提供了一种计算机设备,包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序,所述处理器执行所述程序时实现上述针对ascon-hash 3的新型低内存消耗中间相遇攻击方法。

27、本说明书采用的上述至少一个技术方案能够达到以下有益效果:

28、本发明通过对线性抵消关系提取独立线性约束,实现red侧变量枚举维度初次降维;通过对非线性抵消关系进行布尔多项式三角化分解,实现red侧变量的二次降维;对无法消除的残余非线性关系,构造残差索引,并在匹配阶段按索引分桶过滤,仅保留与blue侧兼容的桶,从而大幅缩小哈希表规模,使得在时间复杂度不变的情况下大幅降低了攻击所需的存储空间,降低了内存消耗并拓展了密码安全性评估的适用场景。