SIMON算法相关密钥不可能差分特征搜索

本文通过求解SIMON算法密钥扩展算法的混合整数线性规划(mixed-integer linear programming, MILP)模型, 首次给出其相关密钥不可能差分分析结果. 对分组密码算法的不可能差分特征搜索一般是限制输入输出差分均只有1比特或1个S盒活跃, 在此基础上遍历求解, 如果其MILP模型无解, 则得到一条不可能差分特征. 而SIMON算法采用线性密钥扩展算法, 主密钥差分确定之后每一轮的子密钥差分都随之确定, 无法控制其随轮数增加而逐渐扩散, 所以限制其输入输出差分并不能得到最长路径. 而遍历所有可能的复杂度高达 O(2(m+2)n),其中 n, m取值与SIMON 2n...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Cryptologic Research 2021-01, Vol.8 (5), p.881
Main Authors: Xu-Zi, WANG, Bao-Feng, WU, HOU, Lin, Dong-Dai, LIN, 王旭姿, 吴保峰, 侯林, 林东岱
Format: Article
Language:Chinese
Subjects:
Algorithms
Constraint modelling
Encryption
Integer programming
Linear programming
Mixed integer
Schedules
Searching
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:本文通过求解SIMON算法密钥扩展算法的混合整数线性规划(mixed-integer linear programming, MILP)模型, 首次给出其相关密钥不可能差分分析结果. 对分组密码算法的不可能差分特征搜索一般是限制输入输出差分均只有1比特或1个S盒活跃, 在此基础上遍历求解, 如果其MILP模型无解, 则得到一条不可能差分特征. 而SIMON算法采用线性密钥扩展算法, 主密钥差分确定之后每一轮的子密钥差分都随之确定, 无法控制其随轮数增加而逐渐扩散, 所以限制其输入输出差分并不能得到最长路径. 而遍历所有可能的复杂度高达 O(2(m+2)n),其中 n, m取值与SIMON 2n/mn相同. 当前计算能力无法达到, 这也是在此之前一直没有SIMON相关密钥不可能差分分析结果的原因. 本文通过研究SIMON算法中ROTATION-AND操作中概率为1的差分传播性质, 结合截断差分路径给出满足miss-in-the-middle条件时, 子密钥差分需满足的约束条件. 通过对密钥扩展算法的MILP模型及约束条件求解, 如果有解则得到一条相关密钥不可能差分特征. 本文首次给出SIMON32/64和SIMON48/96的13轮相关密钥不可能差分特征, 在此前研究结果中其单密钥下最长路径分别为11和12轮.
ISSN:2097-4116
DOI:10.13868/j.cnki.jcr.000484