Paper 2026/2944
Linear Cryptanalysis of ISO Standard SEED: Exact Trail Optima via Divide-and-Decide Search
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
-
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}
}