基于Keccak置换的认证加密算法改进与安全性评估

关键词：Keccak置换；认证加密；算法改进；安全性评估

中图分类号：TP308 文献标识码：A

文章编号：1009-3044（2024）26-0074-03 开放科学（资源服务）标识码（OSID） ：

0 引言

Keccak置换是一种重要的密码学原语，广泛应用于哈希函数、消息认证码和认证加密等领域。然而，现有的基于Keccak置换的认证加密算法在执行效率和并行性方面存在不足，难以满足高吞吐量应用场景的需求。此外，面对日益增长的非对称威胁，现有算法的安全机制需要进一步增强，因此需要进行深入研究以改进算法效果。

1 Keccak 置换的基本原理

Keccak置换基于海绵结构，是一种重要的密码学原语，被广泛应用于哈希函数、消息认证码以及认证加密等领域。其核心是通过一系列的置换操作，将输入的比特序列映射到输出的比特序列，从而实现了混淆和扩散的功能。在实际应用中，置换操作需要在一个三维的状态上进行，该状态可以表示为一个5×5×w 的比特数组，其中w为词的长度，取值为1、2、4、8、16、32或64。状态中的每一位可以表示为S[x，y，z]，其中x、y、z分别表示状态的三个维度，取值范围分别为0≤x<5，0≤y<5，0≤zχ步骤对状态中的每一行进行非线性变换，增强了状态的混淆性。ι步骤将一个轮常数与状态进行异或操作，破坏了轮函数的对称性。

轮函数的迭代次数取决于安全参数的选择，通常为12、14、16、18、20或24轮。同时，Keccak置换展现出良好的混淆性，可以抵抗线性攻击。与传统的Merkle-Damgård结构不同，Keccak置换的海绵结构可以有效防止长度扩展攻击。即使攻击者获得了部分消息及其哈希值，也无法伪造带有额外消息的合法哈希值。

2 基于Keccak 置换的认证加密算法改进

2.1 现有算法的不足

尽管Keccak置换具有良好的密码学性质，但现有基于Keccak置换的认证加密算法仍然存在一些不足之处。例如，由于Keccak置换的轮函数包含多个步骤，每一步都涉及大量的位运算和置换操作，因此算法在软件实现中的执行效率相对较低。基于Keccakp[400]和Keccak-p[1600]置换构建的算法吞吐量仅为5.5 cycles/byte，与其他轻量级认证加密算法相比，如Ascon（2.4 cycles/byte） 和NORX（2.5 cycles/byte） ，Ketje 和Keyak的性能还有较大的提升空间。

此外，现有算法的并行性普遍不足。在Keccak置换的轮函数中，π步骤和χ步骤分别对状态中的比特进行置换和非线性变换。这两个步骤都包含了大量的数据依赖关系，难以实现高效的并行化处理。Keccak-p[1600]置换的并行度仅为8，即在一个时钟周期内，最多只能同时处理8个比特的数据[2]。这种有限的并行性限制了算法在多核处理器和硬件加速器上的加速潜力。因此难以满足高吞吐量应用场景的需求。

2.2 改进方案一：优化算法结构

针对现有基于Keccak置换的认证加密算法存在的不足，研究提出了优化算法结构的改进方案。该方案通过重新设计置换的轮函数，引入更高效的非线性变换和置换操作，同时优化算法的并行结构，以提高算法的效率和并行性。在轮函数的设计上，改进方案引入了新的非线性变换，称为η步骤。与原有的χ步骤不同，η步骤采用了基于有限域上的多项式的非线性变换，具有更高的代数次数和非线性度。通过使用更强的非线性变换，改进后的轮函数可以在更少的轮数下实现与原有算法相当的安全性。这将减少算法的计算开销。基于对η步骤的安全性分析，选择了定义在GF（2⁸）上的三次多项式作为非线性函数，可以将差分和线性特征概率上界分别降低到2^-48和2^-64。

在置换操作上，研究重新设计了π步骤，引入了基于广义Feistel结构的置换网络。与原有的基于固定置换表的设计不同，新的置换网络采用了可参数化的置换模式，可以根据密钥信息动态生成置换表。这种动态置换的设计增强了算法的混淆性。同时也提高了抗密钥相关攻击的能力。通过优化参数，置换网络可以在5轮迭代下实现全状态扩散，相比原有的π 步骤，扩散速度可提高约60%。

研究还优化了算法的并行结构，通过重新安排轮函数中各个步骤的执行顺序，降低了步骤之间的数据依赖关系。这提高了算法的并行度。在新的并行结构下，θ步骤和η步骤可以同时执行，ρ步骤和π步骤也可以并行处理。这种细粒度的并行设计可以充分利用现代处理器的多核心和SIMD指令集，大幅提高算法的执行效率[3]。

为了应对非对称威胁，研究引入了新的安全机制。在密钥调度阶段，采用基于哈希函数的密钥衍生机制，从共享的短密钥中生成不同的会话密钥。这种机制可以有效防止密钥枚举攻击，即使攻击者获得了某个会话的密钥，也无法直接推导出其他会话的密钥。同时，算法整合了基于计数器的随机化机制，在每个会话开始时生成一个随机的初始计数器，用于对状态进行初始化。这可以有效防止重放攻击，确保每个会话的数据均具有唯一属性。

2.3 改进方案二：引入新的安全机制

除了优化算法结构外，研究还提出了第二个改进方案，即引入新的安全机制。该方案旨在进一步增强基于Keccak置换的认证加密算法的安全性，确保算法可以抵御非对称威胁等新型攻击方式。改进方案引入了基于物理不可克隆函数（PUF）的密钥管理机制。PUF利用硬件制造过程中的固有变异性，生成唯一且不可预测的密钥。通过将PUF集成到认证加密算法中，可以避免在密钥存储和分发过程中泄露密钥信息[4]。改进后的算法中，每个通信实体都集成了一个PUF模块，用于生成设备唯一的密钥。设PUF的挑战为C，响应为R，则PUF可以建模为一个函数f，如公式（1） 所示：

R = f （C ） （1）

在密钥协商阶段，通信双方通过一个安全的密钥交换协议，利用 PUF生成的密钥建立共享密钥。这可以有效防止密钥泄露和克隆攻击，即使攻击者获得了设备的物理访问权限，也无法提取出有效的密钥信息。

在此基础上，研究还引入了一种新的认证机制，即基于哈希的认证码（HAC） 。与传统的消息认证码（MAC） 不同，HAC利用了哈希函数的单向性和抗碰撞性，可以在不共享密钥的情况下实现消息认证[5]。在改进后的算法中，发送方将消息M和一个随机数R作为输入，计算其哈希值作为认证码HAC，如公式（2） ：

HAC = H （M||R） （2）

接收方收到消息和认证码后，重新计算哈希值，并与收到的认证码进行比较，以验证消息的完整性和真实性。HAC机制可以有效降低密钥管理的复杂度，简化了认证过程。

3 改进后算法的安全性评估

3.1 安全性评估方法标准

研究采用密码分析方法对改进后的算法进行安全性评估，重点关注差分分析、线性分析和代数分析这三种经典的密码分析方法。在此基础上结合统计学测试方法对改进后的算法进行随机性评估，按照NIST SP800-22随机性测试标准进行检验，每项测试都给出P 值作为评估指标，P 值越接近0.5，表示算法输出的随机性越好[6]。

另外，为了检验算法的实际应用安全性，研究采用安全协议分析方法对改进后的算法在实际应用中的安全性进行评估。以TLS1.3协议为例，采用了符号执行和模型检测的方法，对基于改进算法的TLS1.3协议进行了形式化验证。通过使用自动化验证工具，对协议的保密性、认证性、完整性进行分析。分析结合计算复杂性理论进行检验，其能够检查问题在最坏情况下求解难度的方法。对于密码算法，安全性的长期下界可以用算法在最坏情况下被攻破所需的计算资源来衡量，结果能够证明改进后算法的长期安全性。

3.2 安全性评估结果

3.2.1 密码分析

在密码分析方面，表1给出了改进后算法在差分分析、线性分析和代数分析下的评估结果数据。

从表1结果可以发现，改进后的算法在三种主要的密码分析方法下都表现出了优秀的安全性。在差分分析下，MDCP 达到了2^-128，优于SHA-3 的安全要求；在线性分析下，MLC达到了2^-102，满足了通用的安全要求；在代数分析下，AD达到了128，远高于通用的安全要求。结果证明，改进后的算法能够很好地抵抗已知的密码分析攻击[7]。

3.2.2 随机性评估

在随机性评估方面，改进后算法的输出在所有15 项随机性测试中都通过了NIST标准，P 值均匀分布在0.4到0.6之间，表明算法具有优秀的随机性，能够生成高质量的随机数，满足密码应用的需求。

3.2.3 安全协议分析

在安全协议分析方面，算法基于TLS 1.3协议的安全性形式化验证获得了理想结果，保密性、认证性以及前向安全性等方面均满足需求。

3.2.4 长期安全性分析

在长期安全性方面，通过计算复杂性理论分析，得到了改进后算法在经典计算机和量子计算机模型下的安全复杂性下界结果。经典计算机模型结果为O（2²⁵⁶），量子计算机结果为O（2¹⁹²）。结果证明，改进后的算法无论在经典计算机还是量子计算机模型下，其安全复杂性下界都远高于当前和可预见未来的计算能力，证明算法能够提供足够的长期安全保障。

4 总结

综合分析发现，改进后的算法在效率、并行性和安全性方面都得到了显著提升，长期安全性分析也表明算法能够提供足够的安全保障。改进算法通过优化轮函数结构和引入新的非线性变换，提高了算法执行效率。重新设计的并行结构显著提升了算法的并行性，更适合在现代多核处理器上实现。而且引入基于PUF的密钥管理和AEA模式等新安全机制，增强了算法抵抗非对称威胁的能力。在差分分析、线性分析和代数分析等方面也表现出了优秀的安全性，同时具有良好的随机性。但改进算法也存在一些不足，比如基于PUF的密钥管理对硬件实现有一定要求，可能限制算法在某些场景下的应用。AEA模式虽然提供了更高的安全性，但可能会增加通信开销。本文的研究成果为提高认证加密算法的性能与安全性提供了新的思路和方法，未来还可以在硬件实现、新型攻击分析等方面开展进一步研究，不断完善和优化算法设计。