7项尚待研究｜新一代密码杂凑算法研究的问题与挑战

密码杂凑算法作为最常用的数据完整性保护算法,广泛应用于数据完整性验证、数字签名、随机数生成等领域, 是保障信息安全的基础性底层密码算法。

为应对量子计算威胁, 推动新一代商用密码算法标准制定, 商用密码标准研究院将面向全球开展新一代公钥密码算法、密码杂凑算法、分组密码算法征集活动, 遴选产生优胜算法, 推动形成我国新一代商用密码算法标准。

格公钥密码作为目前最有前景的后量子密码算法之一, 需要调用密码杂凑算法产生伪随机数, 密码杂凑算法的性能将直接影响格公钥密码算法的性能。

比如, 美国后量子公钥加密标准Kyber调用SHA-3生成所需的伪随机数, SHA-3算法的计算成本约占Kyber算法总成本的30%。

同时大模型训练数据的完整性验证等应用场景对密码杂凑算法的性能有极高的要求, 目前的密码杂凑算法标准均不能很好地满足这些应用需求。

因此, 新一代密码杂凑算法应该具有经典安全性和量子安全性的理论保障, 以及高速、灵活的软件和硬件实现性能。

新一代密码杂凑算法的杂凑值输出长度大、状态规模大, 面向量子计算和人工智能的安全性挑战, 以及大模型大数据、隐私保护对密码杂凑算法的新需求, 有很多问题尚待研究。

首先, 密码杂凑算法的整体结构。

整体结构的理论安全是保障密码杂凑算法安全性的基础, 现有密码杂凑算法的整体结构较为单一, 除传统的MD结构外, 近年推出的大部分算法都采用了Sponge结构。

亟需开展密码杂凑算法整体结构的基础性创新研究, 量子安全模型和证明方法是评估新型整体结构面临的理论难点。

其次, 基于分组密码的杂凑模式。

常用分组密码的分组长度远小于新一代密码杂凑算法的杂凑值输出长度, 需要研究MMO、DM等杂凑模式的可扩展性, 多倍分组长度的杂凑模式, 以及杂凑模式在传统环境和量子环境下的可证明安全性。

第三, 大状态密码函数的设计。

兼顾安全性和实现性能的大状态密码函数是设计新一代密码杂凑算法的关键。

性能方面需综合考虑现代SIMD指令集所支持的功能和时钟周期数, 设计软件和硬件性能俱佳的大状态密码函数。

安全性方面的理论问题是各种参数的等价划分以及等价类函数的安全界证明。

第四, 自动化分析的效率问题。

近年对称密码自动分析取得了丰富成果, 但是目前的自动分析工具多用于轻量级密码算法, 用于大状态密码函数时, 大量参数与约束显著增加了求解难度, 存在不出结果、时间过长而且不可预测等问题。

解决自动化分析的技术瓶颈, 是分析评估新一代密码杂凑算法的技术难点。

第五, 密码杂凑算法的安全性分析与评估。

杂凑算法的分析可以大致分为碰撞攻击、原像攻击和其他新兴攻击。

新一代密码杂凑算法的安全性分析与评估, 除了评估其在传统分析方法下的安全性, 同时要考察其在量子计算下的安全性。

理清量子计算对差分分析、反弹攻击、中间相遇攻击、比特追踪、分段链接、初始结构、完全二分结构、间接匹配等杂凑算法分析方法和技术的影响, 是分析评估新一代密码杂凑算法要面临的问题。

第六, 人工智能对密码杂凑算法的影响。

机器学习在对称密码学领域的应用, 特别是神经区分器的开发, 为密码分析开辟了新的范式。

基于深度神经网络的分析方法有时会展现出超越传统方法的区分能力, 强化学习在优化算法实现上具有很大潜力, 因此, 需研究机器学习方法的发展对新一代密码杂凑算法的安全性和优化实现的影响。

最后, 隐私保护友好密码杂凑算法的设计与分析。

不同于经典密码杂凑算法, 隐私保护友好密码杂凑算法的设计指标主要关注乘法复杂度和乘法深度, 其基本运算多数定义在素域或者扩域, 且规模较大, 非线性层相对简单, 多采用低次数的幂函数, 导致算法的中间状态可能存在线性或低次的多项式关系, 从而更易受到代数类分析方法的攻击。

研究隐私保护友好密码杂凑算法需结合零知识证明协议、安全多方计算的特定场景需求, 非线性组件仍然是此类算法的效率瓶颈。

来源：密码学报-中英文