MILP-Based Differential Cryptanalysis of the FBC-128 Lightweight Cipher

ZHAO Qi; FAN Ting; WEI Yong-zhuang

doi:10.12263/DZXB.20230161

您当前的位置：

首页 >

文章列表页 >

MILP-Based Differential Cryptanalysis of the FBC-128 Lightweight Cipher

PAPERS | 更新时间：2025-12-11

- MILP-Based Differential Cryptanalysis of the FBC-128 Lightweight Cipher
- ACTA ELECTRONICA SINICA Vol. 52, Issue 6, Pages: 1896-1902(2024)
- 作者机构：
  
  桂林电子科技大学广西密码学与信息安全重点实验室，广西桂林 541004
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(62162016);The Innovation Research Team Project of Guangxi Natural Science Foundation(2019GXNSFGA245004)
- DOI：10.12263/DZXB.20230161
  CLC： TN918
- Received：24 February 2023，
  
  Revised：2023-10-25，
  
  Published：25 June 2024
- 稿件说明：
移动端阅览
赵琪, 樊婷, 韦永壮. 基于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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Linear Analysis of Lightweight Cipher ACE and SPIX Based on Mixed-Integer Linear Programming

Linear Key-Recovery Attack on the Lightweight Block Cipher PFP

UPRFloor: A Modeling and Floorplanner for Partially Reconfigurable FPGA Systems

Adaptive Output Consensus of Heterogeneous Open Multi-Agent Systems under Actuator Attacks

Low Sidelobe and High Aperture Efficiency Reflectarray Based on Metasurface

Related Author

LIU Shuai

REN Xiao-guang

WANG Shi-xiong

GUAN Jie

ZHANG Xiao-chuan

TAN Jie

WANG Jun

ZHANG Yingjie

Related Institution

Intelligent Game and Decision Laboratory

Academy of Military Science

School of Cipher Engineering, SSF Information Engineering University

Beijing Institute of Mathematical Sciences and Applications

Cyber Security College, Guangdong Police College

⁰