New Attacks on Feistel Structures with Improved Memory Complexities

doi:10.1007/s00145-026-09571-y

New Attacks on Feistel Structures with Improved Memory Complexities

2026-03-03

0

PRE

AI

DOI：10.1007/s00145-026-09571-y

原文链接

原文求助

摘要

En 中文

Feistel结构是广泛研究的一种密码方案类型。本文中，我们描述了对轮数大于4的Feistel结构的改进攻击。我们通过一种结合了中间相遇攻击（通过仅比较中间的半块来降低时间复杂度）和分割攻击（可以降低内存复杂度，但需要猜测中间的完整块以执行上下独立攻击）的主要优势的新攻击来实现这一点。例如，对于具有七个独立轮密钥（每个密钥为n/2位）的7轮Feistel结构，中间相遇攻击需要(21.5n, 21.5n)的时间和内存，而分割攻击需要(22n, 2n)的时间和内存。我们的新攻击仅需(21.5n, 2n)的时间和内存，并使用少量已知的明文/密文对。当我们被允许使用更多已知明文时，我们开发了依赖于结构深层中多碰撞和差分性质存在的新技术，以进一步降低内存复杂度。我们的新攻击不仅是理论上的通用构造——实际上，我们可以使用它们来降低对CAST-128（我们将其复杂度从2111降低到264）和完整DEAL-256（我们将其复杂度从2200降低到2144）等具体密码系统的最佳已知攻击的内存复杂度，而不会影响其时间和数据复杂度。我们技术的扩展甚至适用于某些非Feistel结构——例如，在FOX的情况下，我们将所有最佳已知攻击的内存复杂度降低了216倍。

Keyword:

Cryptanalysis

Block cipher

Feistel structure

Dissection

Meet-in-the-middle

Splice-and-cut

CAST-128

DEAL

New Attacks on Feistel Structures with Improved Memory Complexities

摘要

期刊

机构

引用论文