Saturnin算法的不可能差分分析

蒋梓龙; 金晨辉

doi:10.11959/j.issn.1000-436x.2022045

您当前的位置：

首页 >

文章列表页 >

Saturnin算法的不可能差分分析

学术论文 | 更新时间：2024-06-05

- Saturnin算法的不可能差分分析
- Impossible differential cryptanalysis of Saturnin algorithm
- 通信学报 2022年43卷第3期页码：53-62
- 作者机构：
  
  信息工程大学密码工程学院，河南郑州 450001
- 作者简介：
  
  [ "蒋梓龙（1992- ），男，江苏南通人，信息工程大学博士生，主要研究方向为对称密码设计与分析" ]
  [ "金晨辉（1965- ），男，河南扶沟人，博士，信息工程大学教授、博士生导师，主要研究方向为密码学与信息安全" ]
- 基金信息：
  
  国家自然科学基金资助项目(61772547);国家自然科学基金资助项目(61902428);国家自然科学基金资助项目(61802438)
- DOI：10.11959/j.issn.1000-436x.2022045
  中图分类号： TN918.1
- 网络出版日期：2022-03，
  
  纸质出版日期：2022-03-25
- 稿件说明：
移动端阅览
蒋梓龙, 金晨辉. Saturnin算法的不可能差分分析[J]. 通信学报, 2022,43(3):53-62.

Zilong JIANG, Chenhui JIN. Impossible differential cryptanalysis of Saturnin algorithm[J]. Journal on communications, 2022, 43(3): 53-62.
蒋梓龙, 金晨辉. Saturnin算法的不可能差分分析[J]. 通信学报, 2022,43(3):53-62. DOI： 10.11959/j.issn.1000-436x.2022045.

Zilong JIANG, Chenhui JIN. Impossible differential cryptanalysis of Saturnin algorithm[J]. Journal on communications, 2022, 43(3): 53-62. DOI： 10.11959/j.issn.1000-436x.2022045.

摘要

轻量级分组密码算法Saturnin是类AES算法，在资源受限的环境下，仍具有良好的安全性。对Saturnin算法进行了不可能差分分析。首先，基于Saturnin算法的结构特性，提出并证明了Saturnin算法3.5轮不可能差分区分器的充分条件，利用此充分条件可以快速构造2

70.1

个截断式不可能差分区分器。其次，从构造的2

70.1

个区分器中，有针对性地挑选了64个区分器并分成了四类。将这四类区分器向前扩展2轮可得四条攻击路径。这四条攻击路径不仅具有相同的明文结构，而且具有大量的公共密钥比特，利用这2个特性，可以改善攻击方案的复杂度。结合明文早夭等分析技术，提出Saturnin算法的5.5轮不可能差分攻击方案，其数据、存储和时间复杂度分别为2

176.88

个选择明文、2

143.88

算法规模和2

176.91

次5.5轮加密，这是目前可见的对Saturnin算法的一种不可能差分攻击方案。

Abstract

A lightweight block cipher

Saturnin

is an AES-like algorithm.In a resource-constrained environment

Saturnin can also provide high security.The impossible differential analysis on Saturnin was proposed.First

based on the structure of Saturnin

the sufficient condition of 3.5-round impossible differential distinguisher of Saturnin was presented and proved

and 2

70.1

truncated impossible differential distinguishers could be quickly constructed by utilizing the sufficient condition.Then

from the constructed 2

70.1

distinguishers

the 64 distinguishers could be picked out pointedly and classified into four types.Four attack trails could be obtained by appending two rounds before the four types of distinguishers.These four attack trails had the same plaintext structure and a number of common subkey bits.With the help of these two properties

the complexity of the attack scheme could be reduced.Combined with the analysis technologies such as early abort

present the 5.5-round impossible differential attack scheme with 2

176.88

chosen plaintexts

143.88

256-bit blocks

and 2

176.91

5.5-round encryption.As so far

this is the known attack scheme for Saturnin against impossible differential attack.

关键词

Keywords

references

CANTEAUT A , DUVAL S , LEURENT G , et al . Saturnin:a suite of lightweight symmetric algorithms for post-quantum security [J ] . IACR Transactions on Symmetric Cryptology , 2020 ( S1 ): 160 - 207 .

BIHAM E , BIRYUKOV A , SHAMIR A . Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials [C ] // International Conference on the Theory and Applications of Cryptographic Techniques . Berlin:Springer , 1999 : 12 - 23 .

KIM J , HONG S , SUNG J , et al . Impossible differential cryptanalysis for block cipher structures [C ] // International Conference on Cryptology in India . Berlin:Springer , 2003 : 82 - 96 .

LUO Y Y , LAI X J , WU Z M , et al . A unified method for finding impossible differentials of block cipher structures [J ] . Information Sciences , 2014 , 263 : 211 - 220 .

WU S B , WANG M S . Automatic search of truncated impossible differentials for word-oriented block ciphers [C ] // Progress in Cryptology - INDOCRYPT 2012 . Berlin:Springer , 2012 : 283 - 302 .

MOUHA N , WANG Q J , GU D W , et al . Differential and linear cryptanalysis using mixed-integer linear programming [C ] // International Conference on Information Security and Cryptology . Berlin:Springer , 2011 : 57 - 76 .

XIANG Z J , ZHANG W T , BAO Z Z , et al . Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers [C ] // International Conference on the Theory and Application of Cryptology and Information Security . Berlin:Springer , 2016 : 648 - 678 .

SHI D P , SUN S W , DERBEZ P , et al . Programming the demirciselçuk meet-in-the-middle attack with constraints [C ] // International Conference on the Theory and Application of Cryptology and Information Security . Berlin:Springer , 2018 : 3 - 34 .

LIU Y , SUN S , LI C . Rotational cryptanalysis from a differential-linear perspective [C ] // Annual International Conference on the Theory and Applications of Cryptographic Techniques . Berlin:Springer , 2021 : 741 - 770 .

CUI T T , CHEN S Y , FU K , et al . New automatic tool for finding impossible differentials and zero-correlation linear approximations [J ] . Science China Information Sciences , 2020 , 64 ( 2 ): 1 - 3 .

SASAKI Y , TODO Y . New impossible differential search tool from design and cryptanalysis aspects [C ] // Advances in Cryptology – EUROCRYPT 2017 . Berlin:Springer , 2017 : 185 - 215 .

HU X C , LI Y Q , JIAO L , et al . Mind the propagation of states:new automatic search tool for impossible differentials and impossible polytopic transitions [C ] // Advances in Cryptology - ASIACRYPT 2020 . Berlin:Springer , 2020 : 415 - 445 .

张仕伟 , 陈少真 . SIMON不可能差分及0相关路径自动化搜索算法 [J ] . 软件学报 , 2018 , 29 ( 11 ): 3544 - 3553 .

ZHANG S W , CHEN S Z . Automatic search algorithm for impossible differential trials and zero-correlation linear trials in SIMON [J ] . Journal of Software , 2018 , 29 ( 11 ): 3544 - 3553 .

ZHANG K , GUAN J , HU B . Automatic search of impossible differentials and zero-correlation linear hulls for ARX ciphers [J ] . China Communications , 2018 , 15 ( 2 ): 54 - 66 .

武小年 , 李迎新 , 韦永壮 , 等 . GRANULE和MANTRA算法的不可能差分区分器分析 [J ] . 通信学报 , 2020 , 41 ( 1 ): 94 - 101 .

WU X N , LI Y X , WEI Y Z , et al . Impossible differential distinguisher analysis of GRANULE and MANTRA algorithm [J ] . Journal on Communications , 2020 , 41 ( 1 ): 94 - 101 .

王旭姿 , 吴保峰 , 侯林 , 等 . SIMON算法相关密钥不可能差分特征搜索 [J ] . 密码学报 , 2021 , 8 ( 5 ): 881 - 893 .

WANG X Z , WU B F , HOU L , et al . Searching for related-key impossible differentials for SIMON [J ] . Journal of Cryptologic Research , 2021 , 8 ( 5 ): 881 - 893 .

DAEMEN J , RIJMEN V . Reijndael:the advanced encryption standard [J ] . Dr.Dobb’s Journal:Software Tools for the Professional Programmer , 2001 , 26 ( 3 ): 137 - 139 .

HOU T , CUI T , ZHANG J Y . Practical attacks on reduced-round 3D and Saturnin [J ] . The Computer Journal ， 2021 ,doi:10.1093/comjnl/bxab174.

张庆贵 . 不可能差分攻击中的明文对筛选方法 [J ] . 计算机工程 , 2010 , 36 ( 2 ): 127 - 129 .

ZHANG Q G . Plaintext pair sieve methods in impossible differential attack [J ] . Computer Engineering , 2010 , 36 ( 2 ): 127 - 129 .

浏览量

561

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于矩阵方法的减轮

μ^{2}

算法不可能差分分析

FeW的差分故障攻击

TWINE算法的相关密钥不可能飞来去器攻击

轻量级分组密码算法TWINE差分故障攻击的改进

对轻量级分组密码I-PRESENT-80和I-PRESENT-128的biclique攻击