基于MILP对轻量级密码算法FBC-128的差分分析

赵琪; 樊婷; 韦永壮

doi:10.12263/DZXB.20230161

您当前的位置：

首页 >

文章列表页 >

基于MILP对轻量级密码算法FBC-128的差分分析

学术论文 | 更新时间：2025-12-11

- 基于MILP对轻量级密码算法FBC-128的差分分析
- MILP-Based Differential Cryptanalysis of the FBC-128 Lightweight Cipher
- 电子学报 2024年52卷第6期页码：1896-1902
- 作者机构：
  
  桂林电子科技大学广西密码学与信息安全重点实验室，广西桂林 541004
- 作者简介：
  
  [ "赵琪男，1997年2月出生于山西省晋城市，现为桂林电子科技大学计算机与信息安全学院硕士研究生，研究方向为分组密码算法差分分析方法. E-mail: wakeupzq@163.com" ]
  [ "樊婷女，1993年10月出生于山西省忻州市，现为桂林电子科技大学计算机与信息安全学院博士研究生，研究方向为分组密码算法设计与分析. E-mail: fanting0801@163.com" ]
  [ "韦永壮男，1976年12月出生于广西省百色市，现为桂林电子科技大学计算机与信息安全学院教授，博士生导师，主要研究方向为密码函数、对称密码算法设计与分析. E-mail: walker_wyz@guet.edu.cn" ]
- 基金信息：
  
  国家自然科学基金(62162016);广西自然科学基金创新研究团队项目(2019GXNSFGA245004)
- DOI：10.12263/DZXB.20230161
  中图分类号： TN918
- 收稿：2023-02-24，
  
  修回：2023-10-25，
  
  纸质出版：2024-06-25
- 稿件说明：
移动端阅览
赵琪, 樊婷, 韦永壮. 基于MILP对轻量级密码算法FBC-128的差分分析[J]. 电子学报, 2024, 52(06): 1896-1902.

ZHAO Qi, FAN Ting, WEI Yong-zhuang. MILP-Based Differential Cryptanalysis of the FBC-128 Lightweight Cipher[J]. Acta Electronica Sinica, 2024, 52(06): 1896-1902.
赵琪, 樊婷, 韦永壮. 基于MILP对轻量级密码算法FBC-128的差分分析[J]. 电子学报, 2024, 52(06): 1896-1902. DOI：10.12263/DZXB.20230161

ZHAO Qi, FAN Ting, WEI Yong-zhuang. MILP-Based Differential Cryptanalysis of the FBC-128 Lightweight Cipher[J]. Acta Electronica Sinica, 2024, 52(06): 1896-1902. DOI：10.12263/DZXB.20230161

摘要

FBC（Feistel-based Block Cipher）是入围全国密码算法设计竞赛第二轮的轻量级分组密码.由于它具备算法结构简洁、安全性高及软硬件实现性能卓越等优点，备受业界广泛关注.FBC密码算法的数据分组长度和密钥长度至少为128比特，记为FBC-128.目前对FBC-128算法差分攻击的最好结果是12轮，时间复杂度为2

93.41

次加密，数据复杂度为2

122

个选择明文对.然而，FBC算法是否存在更长的差分区分器，能否对其进行更高轮数的密钥恢复攻击仍有待解决.本文基于混合整数线性规划（MILP）的自动化搜索方法，提出了“分段统计法”来求解FBC-128的差分特征.实验测试结果表明：FBC-128存在15轮差分区分器，其概率为2

-121

.然后将其向后扩展1轮，对16轮FBC-128算法发起密钥恢复攻击，其数据复杂度为2

121

个选择明文数据量，时间复杂度为2

92.68

次加密.与已有结果相比，差分区分器和密钥恢复攻击都提升了4轮，并且所需的数据复杂度和时间复杂度更低.

Abstract

FBC (Feistel-based Block Cipher) is a lightweight block cipher selected in the second round of the National Cryptographic Algorithm Design Competition. It has many advantages such as simple algorithm structure

high security and excellent implementation performance

and has attracted much attention in the industry. The block size and key length of FBC are at least 128 bits

denoted as FBC-128. At present

the best result of differential attack on FBC-128 is 12-round.The time complexity is 2

93.41

encryptions

and the data complexity is 2

122

chosen-plaintexts. However

it is still to be solved whether there is a longer differential distinguisher and higher rounds of key recovery attack on FBC. In this paper

a segmental statistical method is proposed to search the differential characteristic of FBC-128 based on the mixed-integer linear programming technology. The results show that FBC-128 exists15-round differentia

l distinguisher with probability 2

-121

. Then

we extend it backward by one round

and launch a key recovery attack on 16-round FBC-128.The data complexity is 2

121

chosen-plaintexts

and the time complexity is 2

92.68

encryptions. Compared with the existing results

the differential distinguisher and key recovery attacks are increased by 4 rounds with lower data and time complexity.

关键词

Keywords

references

BIHAM E , SHAMIR A . Differential cryptanalysis of DES-like cryptosystems [J ] . Journal of Cryptology , 1991 , 4 ( 1 ): 3 - 72 .

National Bureau of Standards . Data Encryption Standard: FIPS 46-3 [S ] . Washington : National Bureau of Standards , 1977 .

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

SUN S W , HU L , SONG L , et al . Automatic security evaluation of block ciphers with S-bP structures against related-key differential attack [C ] // Information Security and Cryptology . Cham : Springer , 2014 ( 8567 ): 39 - 51 .

SUN S W , HU L , WANG M Q , et al . Towards finding the best characteristics of some bit-oriented block ciphers and automatic enumeration of (related-key) differential and linear characteristics with predefined properties [R/OL ] . ( 2015-02-09 )[ 2023-02-16 ] . http://eprint.iacr.org/2014/747 http://eprint.iacr.org/2014/747 .

SASAKI Y , TODO Y . New algorithm for modeling S-box in MILP based differential and division trail search [C ] // Innovative Security Solutions for Information Technology and Communications . Cham : Springer , 2017 ( 10543 ): 150 - 165 .

ZHU B Y , DONG X Y , YU H B . MILP-based differential attack on round-reduced GIFT [C ] // Topics in Cryptology—CT-RSA 2019 . Cham : Spring , 2019 ( 11405 ): 372 - 390 .

BANIK S , PANDEY S K , PEYRIN T , et al . GIFT: A small present [C ] // Cryptographic Hardware and Embedded Systems . Cham : Springer , 2017 ( 10529 ): 321 - 345 .

BOURA C , COGGIA D . Efficient MILP modelings for sboxes and linear layers of SPN ciphers [J ] . IACR Transactions on Symmetric Cryptology , 2020 , 2020( 3 ): 327 - 361 .

ZONG R , DONG X Y , CHEN H F , et al . Towards key-recovery-attack friendly distinguishers: Application to GIFT-128 [J ] . IACR Transactions on Symmetric Cryptology , 2021 , 2021( 1 ): 156 - 184 .

MAKARIM R H , ROHIT R . Towards tight differential bounds of Ascon: A hybrid usage of SMT and MILP [J ] . IACR Transactions on Symmetric Cryptology , 2022 , 2022( 3 ): 303 - 340 .

SOOS M , NOHL K , CASTELLUCCIA C . Extending SAT solvers to cryptographic problems [C ] // Theory and Applications of Satisfiability Testing—SAT 2009 . Berlin : Springer , 2009 ( 5584 ): 244 - 257 .

DOBRAUNIG C , EICHLSEDER M , MENDEL F , et al . Ascon v1.2: Lightweight authenticated encryption and hashing [J ] . Journal of Cryptology , 2021 , 34 ( 3 ): 1 - 42 .

LI T , SUN Y . SuperBall: A new approach for MILP modelings of Boolean functions [J ] . IACR Transactions on Symmetric Cryptology , 2022 , 2022( 3 ): 341 - 367 .

冯秀涛 , 曾祥勇 , 张凡 , 等 . 轻量级分组密码算法FBC‍ [J ] . 密码学报 , 2019 , 6 ( 6 ): 768 - 785 .

FENG X T , ZENG X Y , ZHANG F , et al . On the lightweight block cipher FBC [J ] . Journal of Cryptologic Research , 2019 , 6 ( 6 ): 768 - 785 . (in Chinese)

REN B Q , CHEN J G , ZHOU S H , et al . Cryptanalysis of Raindrop and FBC [C ] // Network and System Security . Cham : Springer , 2019 ( 11928 ): 536 - 551 .

MATSUI M . On correlation between the order of S-boxes and the strength of DES [C ] // EUROCRYPT 1994 . Berlin : Springer , 1994 ( 950 ): 366 - 375 .

ZHANG Y , LIU G Q , LI C , et al . Impossible differential cryptanalysis of FBC-128 [J ] . Journal of Information Security and Applications , 2022 , 69 ( 103279 ): 1 - 8 .

SAGEMATH . Sagemath 9.8 [EB/OL ] . ( 2023-02-11 )[ 2023-02-16 ] . http://www.sagemath.org http://www.sagemath.org .

GUROBI . Gurobi optimizer 10.0 [EB/OL ] . ( 2022-11-30 )[ 2023-02-16 ] . http://www.gurobi.cn http://www.gurobi.cn .

浏览量

下载量

CSCD

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

提交

工具集

关联资源

基于MILP的轻量级密码算法ACE与SPIX的线性分析

轻量级分组密码PFP的线性密钥恢复攻击

UPRFloor:一种动态可重构FPGA建模方法与布局策略

衰减解耦机制的图像分类网络

基于TCAD与DNN的FinFET器件辐射总剂量效应模型