COLM算法的各种密码分析方法全面盘点
COLM算法是一种认证加密（AEAD）算法，曾是CAESAR竞赛“深度防御”类别的获胜者。针对它的密码分析方法可以系统地分为三大类：首先是围绕其核心弱点——秘密白化参数L的基础性攻击；其次是建立在L恢复基础上的三大核心攻击方法；最后是基于算法结构的其他扩展攻击。
🔑核心前提：恢复秘密参数 L
几乎所有针对COLM的高效攻击，都始于恢复其秘密白化参数L = E_K(0)。这个参数是COLM结构的一个核心弱点，一旦被恢复，后续攻击的复杂度将大幅降低。
⚔️三大核心攻击方法
在获取L后，攻击者主要可以发动以下三种攻击：
- 构建底层分组密码的仿真模型 (SEBC/SDBC)：攻击者可以利用COLM结构的缺陷，来模拟其底层分组密码（如AES）的加密（SEBC）或解密（SDBC）行为。这是发动后续攻击的核心技术。
- 明文恢复攻击 (Plaintext Recovery Attack)：通过仿真解密预言机（SDBC），攻击者可以在选择密文攻击（CCA）场景下，从任意密文中恢复出明文。
- 标签猜测/伪造攻击 (Tag Guessing/Forgery Attack)：同样在CCA场景下，攻击者可以为给定的密文伪造出有效的认证标签，从而破坏算法的完整性。
这些攻击在L已知后，其时间复杂度为多项式级别。这意味着COLM的安全性被限制在生日界限（birthday bound）附近，而非其宣称的更高安全级别。
🛠️其他扩展攻击方法
除了上述核心攻击，研究还揭示了COLM的更多弱点：
- 通用伪造攻击 (Universal Forgery Attack)：不局限于特定消息，攻击者可以为任意消息伪造出一个有效的密文-标签对。
- 存在性伪造攻击 (Existential Forgery Attack)：攻击者可以伪造至少一个有效（但内容不受控）的密文-标签对。
- 密钥恢复攻击 (Key Recovery Attack)：利用COLM预言机收集数据，可对底层AES算法发起密钥恢复攻击，例如针对降轮AES的攻击。相关的实现技术包括Biclique攻击、不可能差分分析、中间相遇攻击等。
- 针对COLM变体的攻击：研究也关注了COLM的改进版本。例如，有工作探索了使用广义线性混合函数的COLM变体，以及在白化掩码L使用独立密钥时的安全性。
- 针对特定场景的攻击：
- 随机数滥用（Nonce Misuse）：COLM虽声称对此安全，但仍有研究发现了针对任意混合函数的随机数滥用伪造攻击。
- 释放未验证明文（RUP）：在RUP场景下，COLM的安全性高度依赖于其混合函数的选择。
- 其他攻击：还包括持久性故障分析（Persistent Fault Analysis）等侧信道攻击方法。
💎总结
总而言之，针对COLM的密码分析表明，其安全性过度依赖于秘密参数L的保密性。一旦L被恢复，算法便会暴露于一系列高效的攻击之下，其安全强度并未达到“深度防御”的预期。这些发现为设计更健壮的AEAD算法提供了宝贵经验。
