Paper 2026/2944

Linear Cryptanalysis of ISO Standard SEED: Exact Trail Optima via Divide-and-Decide Search

Haonan Hong, Information Engineering University
Kai Zhang, Information Engineering University
Abstract

SEED is a block cipher developed by the Korea Information Security Agency (KISA) and standardized in ISO/IEC 18033-3. For more than two decades, its best linear cryptanalysis has remained KISA's evaluation: a 5-round distinguisher and no key-recovery attack. In this paper, a new hierarchical certified search framework, called divide-and-decide (D&D), is proposed to determine exact optima of linear trails rather than heuristic upper bounds. D&D divides the trail space at two levels, followed by one decision. At the pattern level, the trail space is partitioned by the positions of trivial rounds, and whole patterns are eliminated before any solver call by the F-function spacing bound (FSB) for SEED, an analytic lower bound. At the layer level, each remaining pattern is divided into layers of integer cost, and the lowest layers are enumerated with a satisfiability (SAT) solver to obtain an incumbent trail. At the decision level, the weight beyond the integer cost is treated as an excess, and each remaining layer is closed by a single SAT decision model on this excess instead of being enumerated. For SEED, D&D gives the exact 3- to 7-round optima 18.830, 33.541, 43.472, 55.027, and 65.220, and shows that every 16-round trail has weight at least 112.980. The 6-round hull of weight 53.168 leads to the first linear key-recovery attack on 7-round SEED, and the 7-round hull of weight 63.391 extends linear distinguishers within the codebook from 5 to 7 rounds.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Linear cryptanalysisSEEDdivide-and-decidelinear hullmodular additionkey recovery
Contact author(s)
h2n_02 @ 163 com
zhkai2010 @ 139 com
History
2026-11-22: approved
2026-11-19: received
See all versions
Short URL
https://ia.cr/2026/2944
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2944,
      author = {Haonan Hong and Kai Zhang},
      title = {Linear Cryptanalysis of {ISO} Standard {SEED}: Exact Trail Optima via Divide-and-Decide Search},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2944},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2944}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.