NORX算法的各种密码分析方法全面盘点
对NORX算法的密码分析，学术界已发展出多种方法，这些分析贯穿了其作为CAESAR竞赛候选算法的整个生命周期。以下是对这些方法的全面盘点。
核心密码分析方法
差分分析及其变种
- 内部差分攻击 (Internal Differential Attack)：针对NORX在并行模式下的弱点，攻击者利用算法内部状态的特殊差分进行攻击。例如，有研究展示了针对2轮核心置换的状态恢复攻击。
- 差分-线性攻击 (Differential-Linear Attack)：结合了差分和线性分析的优点。一个著名的成果是利用该方法，仅用2^48.5次查询就能区分完整的NORX64置换，用2^64.7次查询区分NORX32置换。
- 对称截断差分 (Symmetric Truncated Differentials, STD)：Biryukov等人发现NORX核心置换在不同结构层面上存在旋转对称性，并据此提出了STD这种新型的截断差分分析方法。
- 设计者分析：NORX的设计者Aumasson等人最初分析了核心置换的差分性质，并指出高概率差分无法直接用于攻击完整的NORX AEAD方案。
线性分析
- 线性逼近研究：早期对NORX的线性分析研究较少。程文和关杰在2017年的研究为此奠定了基础，他们提出了H函数线性逼近相关系数的快速计算算法，并给出了G函数非零相关线性逼近的性质。
猜测决定攻击 (Guess and Determine)
- 这是一种经典的密码分析方法，也在NORX的分析中被提及和应用。
针对完整版本的高级攻击
对称性攻击 (Symmetry Attacks)
- 这是对NORX v2.0最著名的攻击之一。Chaigneau等人发现其底层海绵置换存在强对称性保持性质，并成功将其转化为对完整版NORX v2.0的攻击。
- 攻击效果：可以实现仅密文的伪造攻击，并能扩展为密钥恢复攻击，其时间与数据复杂度打破了设计者宣称的128位或256位安全强度。
状态恢复攻击 (State Recovery Attack)
- 针对NORX v3.0，前述的对称性攻击虽然被额外的密钥加操作所阻止，但仍可扩展为一种长消息伪造攻击，并进而发展为状态恢复攻击。
- 攻击意义：虽然该攻击复杂度极高，不构成实际威胁，但它表明一旦伪造成功，其造成的安全损失比预期更大。
其他分析方法与评估
- 区分攻击 (Distinguishing Attack)：核心思想是证明NORX的核心置换并非一个理想的随机置换。前述的差分-线性攻击就是一种区分攻击。
- 代数与旋转分析：设计者早期的安全评估认为，代数密码分析和旋转密码分析难以对NORX构成有效攻击。
- 基于SAT的自动化分析：有研究尝试使用SAT（布尔可满足性问题）求解器对包括NORX-32在内的CAESAR候选算法进行自动化密码分析。
- 故障攻击：有研究探讨了如何对NORX生成故障内部状态碰撞的方法。
攻击目标与成果总结
攻击目标 | 主要方法 | 关键成果与影响 |
简化轮数的NORX | 内部差分、差分-线性 | 实现对2轮（共4轮）核心置换的 状态/密钥恢复攻击。 |
NORX核心置换 | 差分-线性、对称截断差分 | 证明置换非理想，能以远低于理论 安全界的数据复杂度进行区分。 |
完整版 NORX v2.0 | 对称性攻击 | 实现伪造攻击和密钥恢复攻击， 直接打破了其宣称的安全强度。 |
NORX v3.0 | 对称性攻击（扩展） | 实现长消息伪造攻击和状态恢复攻击， 揭示了设计上的安全冗余不足。 |
总结
NORX算法的密码分析历程体现了从分析“简化版本”到攻破“完整版本”的演进。早期的研究（如内部差分、猜测决定）多聚焦于其核心置换的简化轮数。随后，更强大的差分-线性攻击证明了其核心置换的非理想性。最终，对算法结构（对称性）的深刻洞察，成功将对简化版本的攻击推进到了对完整版NORX v2.0的实质性破解。这些分析也直接推动了算法从v2.0到v3.0的演进，尽管后者仍被发现存在新的攻击路径。
