Lesamnta算法的各种密码分析方法全面盘点
Lesamnta作为SHA-3竞赛的候选算法，其密码分析研究主要集中在缩减轮次的攻击上，涵盖了差分、积分、不可能差分、中间相遇等多种经典方法。其轻量级版本Lesamnta-LW（已纳入ISO/IEC 29192-5标准）是近年来的分析热点，而原版Lesamnta的完整32轮至今仍未存在有效的实用攻击。
🔍差分分析（Differential Cryptanalysis）
差分分析是评估Lesamnta安全性的基础。研究者重点关注其内部非线性函数F的差分概率。
- 核心发现：Lesamnta-256的F
函数由4步AES型SPN结构构成。有研究指出，其中被称为"XS"的2步SPN的最大差分概率为2-11.415
，这一概率高于设计者最初在独立子密钥假设下推导出的值（2-18
或2-12
）。
- 安全性评估：基于该概率，要保证整个压缩函数的安全，F
函数的最大差分概率需低于2-17.067
。分析表明，在64比特截断分析下，混合函数在15个活跃F
函数的情况下是安全的。此外，密钥调度函数也被证明对差分密码分析具有安全性。
📊积分攻击与不可能差分攻击（Integral & Impossible Differential）
这两类攻击在分析Lesamnta的内部分组密码（特别是Lesamnta-LW-BC）时尤为有效。
- 积分区分器：研究者利用混合整数线性规划（MILP）方法，为Lesamnta-LW-BC发现了多个积分区分器，分别可达18、19和25轮。在已知密钥设定下，甚至能构造出47轮的积分区分器。基于18轮积分区分器，可发起20轮的密钥恢复攻击。
- 不可能差分：同样通过MILP方法，发现了可达21轮的不可能差分。利用17轮的不可能差分，可以实现19轮的密钥恢复攻击。在其他研究中，有工作将不可能差分攻击扩展至27轮，所需数据复杂度为2223
个选择明文，时间复杂度为2105.25
次加密。
🔄中间相遇攻击（Meet-in-the-Middle, MitM）
这是一种用于寻找碰撞或原像的通用方法，近年来在自动化工具的辅助下取得了显著进展。
- 自动化攻击框架：2023年的研究提出了一个针对Feistel网络及其推广结构的自动化MitM攻击模型。
- 对Lesamnta-LW的改进：利用该自动化模型，研究者将针对ISO标准哈希函数Lesamnta-LW的碰撞攻击轮数从之前的11轮显著提升至17轮。此外，还发现了一个针对Lesamnta-LW的20轮MitM碰撞攻击，其总时间复杂度为2124
，优于通用的生日攻击界2128
。
🧬自相似性与补码性质（Self-Similarity & Complementation Properties）
这类攻击利用了Lesamnta结构中高度结构化的常数，揭示了其压缩函数的一些意外弱点。
- 自相似性：研究者发现Lesamnta的压缩函数存在一种自相似性属性，可以构造一个非常高效的区分器，并利用它以远快于通用攻击的速度在完整压缩函数上寻找碰撞，甚至能对完整哈希函数发起牧群攻击（herding attack）。
- 影响：这一发现对在算法设计中大量使用高度结构化常数（如AES和多个SHA-3候选算法）的做法提出了质疑。
💥碰撞与第二原像攻击（Collision & Preimage Attacks）
针对缩减轮次的Lesamnta，已有多种碰撞和原像攻击结果。
- 16轮攻击：设计文档中描述了一种针对16轮Lesamnta-256的碰撞攻击，其时间复杂性约为297
，相应的第二原像攻击复杂性约为2193
。
- 24轮攻击：利用自相似性属性，可以发起针对24轮Lesamnta-256的第二原像攻击，复杂性为2240
，以及复杂性为2120
的碰撞攻击，且均无需大量内存。
🎯开放密钥区分器（Open-Key Distinguishers）
这类区分器在已知密钥设定下工作，用于评估分组密码作为哈希函数内部构件时的安全性。
- 对Tweaked Lesamnta：研究表明，对于调整后的Lesamnta，其内部分组密码（共32轮）存在一个31轮的已知密钥（中间文本）区分器，查询复杂度为2192
，内存需求可忽略。这是在算法调整后，针对其压缩函数和内部分组密码的最佳攻击结果。
💎总结
Lesamnta的密码分析历程展现了现代密码学对哈希函数结构的深入审视。差分分析和积分/不可能差分分析为其核心组件提供了严格的安全边界评估。自动化MitM攻击和自相似性攻击则分别代表了算法工具化和结构性弱点挖掘的前沿。尽管针对缩减轮次的攻击不断取得进展，但针对完整32轮Lesamnta的有效攻击尚未出现。同时，其轻量级变体Lesamnta-LW作为ISO标准，持续接受着密码学界的严格检验，其安全性在缩减轮次下已被显著削弱，这提醒我们对于标准化算法的持续分析至关重要。
