Reverse-Engineering Secret S-box of Block Ciphers by Persistent Fault

WANG An; GU Rui; DING Yao-ling; ZHANG Xue; YUAN Qing-jun; ZHU Lie-huang

doi:10.12263/DZXB.20211032

您当前的位置：

首页 >

文章列表页 >

Reverse-Engineering Secret S-box of Block Ciphers by Persistent Fault

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

- Reverse-Engineering Secret S-box of Block Ciphers by Persistent Fault
- ACTA ELECTRONICA SINICA Vol. 51, Issue 3, Pages: 537-551(2023)
- 作者机构：
  
  1.北京理工大学网络空间安全学院,北京 100081
  2.密码科学技术国家重点实验室,北京 100878
  3.中国科学院信息工程研究所信息安全国家重点实验室,北京 100093
  4.战略支援部队信息工程大学河南省网络密码技术重点实验室,河南郑州 450001
  5.清华大学高等研究院,北京 100084
- 作者简介：
- 基金信息：
  
  National Key R&D Program of China(2021YFB3101500);National Natural Science Foundation of China(62002021);Henan Key Laboratory of Network Cryptography Technology(LNCT2020-A09);Beijing Institute of Technology Research Fund Program for Young Scholars;Cryptographic Application Industry Chain Supply and Demand Docking Platform of New Energy and Intelligent Connected Vehicle Industry(2021-0181-1-1)
- DOI：10.12263/DZXB.20211032
  CLC： TN918;TP309
- Received：01 August 2021，
  
  Revised：2022-11-19，
  
  Published：25 March 2023
- 稿件说明：
移动端阅览
王安,谷睿,丁瑶玲等.基于持续性故障的分组密码算法S盒表逆向分析[J].电子学报,2023,51(03):537-551.

WANG An,GU Rui,DING Yao-ling,et al.Reverse-Engineering Secret S-box of Block Ciphers by Persistent Fault[J].ACTA ELECTRONICA SINICA,2023,51(03):537-551.
王安,谷睿,丁瑶玲等.基于持续性故障的分组密码算法S盒表逆向分析[J].电子学报,2023,51(03):537-551. DOI： 10.12263/DZXB.20211032.

WANG An,GU Rui,DING Yao-ling,et al.Reverse-Engineering Secret S-box of Block Ciphers by Persistent Fault[J].ACTA ELECTRONICA SINICA,2023,51(03):537-551. DOI： 10.12263/DZXB.20211032.

摘要

基于故障注入的逆向分析技术通过向运行保密算法的设备中注入故障，诱导异常加密结果产生，进而恢复保密算法内部结构和参数. 在除S盒表外其他运算结构已知的前提下，本文基于持续性故障提出了一种分组密码算法S盒表逆向分析方法. 我们利用算法中使用故障元素的S盒运算将产生错误中间状态并导致密文出错这一特点，构造特殊的明文和密钥，诱导保密算法第二轮S盒运算取到故障值，从而逆向推导出第一轮S盒运算的输出，进而恢复出保密算法S盒表的全部元素. 以类AES-128（Advanced Encryption Standard-128）算法为例，我们的方法以1 441 792次加密运算成功恢复出完整S盒表，与现有的其他逆向分析方法进行对比，新方法在故障注入次数和计算复杂度上有明显优势. 进一步，我们将该方法应用于类SM4算法，并以1 900 544次加密运算恢复出保密S盒表. 最后，我们综合考虑了分组密码算法的两种典型结构Feistel和SPN（Substitution Permutation Network）的特点，对新方法的普适性进行了讨论，总结出适用算法需具备的条件.

Abstract

Reverse-engineering based on fault analysis works by inducing abnormal ciphertexts by injecting faults into the equipment running a secret cipher

and then restoring its internal structure and parameters. This paper proposes a method of reverse-engineering the S-box table based on persistent fault

when the structure of round function except the S-box table is known. We take advantage of the fact that when S-box operations use the fault element

intermediate state errors appear

leading to ciphertext errors. Therefore

we construct special plaintexts and keys in order to induce errors in the S-box operation of the second round. Then

outputs of the S-box operation in the first round can be derived

i.e. one element of the S-box table is recovered. All elements of the S-box table can be recovered by using different plaintexts and keys. Taking AES-128 (Advanced Encryption Standard-128) algorithm as example

our method restores the complete S-box table by 1 441 792 encryptions. Compared with existing methods

our approach has obvious advantages in number of fault injections and complexity of computations. In addition

we applies this method to a SM4-like algorithm

and recovered its S-box table with an average of 1 900 544 encryptions. Finally

we discuss the universality of the new method

by considering two typical structures of block ciphers

Feistel and SPN (Substitution Permutation Network) structures respectively

and summarize conditions of our method.

关键词

Keywords

references

MATSUI M . Linear cryptanalysis method for DES cipher [M]// Advances in Cryptology — EUROCRYPT'93 . Berlin, Heidelberg : Springer , 1994 : 386 - 397 .

CHO J Y . Linear Cryptanalysis of reduced-round pRESENT [C]// Cryptographers' Track at the RSA Conference . Berlin, Heidelberg : Springer , 2010 : 302 - 317 .

GILBERT H , CHAUVAUD P . A chosen plaintext attack of the 16-round Khufu cryptosystem [C]// Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology . Santa Barbara : Springer , 1994 : 359 - 368 .

DAEMEN J , KNUDSEN L R , RIJMEN V . The block cipher square [C]// Proceedings of the 4th International Workshop on Fast Software Encryption . Haifa : Springer , 1997 : 149 - 165 .

BIRYUKOV A , SHAMIR A . Structural cryptanalysis of SASAS [C]// International Conference on the Theory and Application of Cryptographic Techniques . Innsbruck : Springer , 2001 : 394 - 405 .

TIESSEN T , KNUDSEN L R , KÖLBL S , et al . Security of the AES with a secret S-Box [C]// International Workshop on Fast Software Encryption . Berlin, Heidelberg : Springer , 2015 : 175 - 189 .

TORRANCE R , JAMES D . The state-of-the-art in IC reverse engineering [C]// International Workshop on Cryptographic Hardware and Embedded Systems . Berlin, Heidelberg : Springer , 2009 : 363 - 381 .

QUADIR S E , CHEN J L , FORTE D , et al . A survey on chip to system reverse engineering [J]. ACM Journal on Emerging Technologies in Computing Systems , 2016 , 13 ( 1 ): 1 - 34 .

NOVAK R . Side-Channel Attack on substitution blocks [C]// International Conference on Applied Cryptography and Network Security . Berlin, Heidelberg : Springer , 2003 : 307 - 318 .

CLAVIER C . Side channel analysis for reverse engineering (SCARE)-An improved attack against a secret A3/A8 GSM algorithm [EB/OL]. ( 2004-01 ). https://eprint.iacr.org/2004/049 https://eprint.iacr.org/2004/049 .

DAUDIGNY R , LEDIG H , MULLER F , et al . SCARE of the DES [C]// Applied Cryptography and Network Security . Berlin, Heidelberg : Springer , 2005 : 393 - 406 .

RÉAL D , DUBOIS V , GUILLOUX A M , et al . SCARE of an unknown hardware feistel implementation [C]// International Conference on Smart Card Research and Advanced Applications . Berlin, Heidelberg : Springer , 2008 : 218 - 227 .

RIVAIN M , ROCHE T . SCARE of secret ciphers with SPN structures [C]// International Conference on the Theory and Application of Cryptology and Information Security . Berlin, Heidelberg : Springer , 2013 : 526 - 544 .

CLAVIER C , ISOREZ Q , WURCKER A . Complete SCARE of AES-like block ciphers by chosen plaintext collision power analysis [C]// International Conference on Cryptology in India . Cham : Springer , 2013 : 116 - 135 .

PEDRO M SAN , SOOS M , GUILLEY S . FIRE: Fault injection for reverse engineering [C]//Information Security Theory and Practice. Security and Privacy of Mobile Devices in Wireless Communication . Berlin, Heidelberg : Springer Berlin Heidelberg , 2011 : 280 - 293 .

TANG M , QIU Z , DENG H , LIU S , ZHANG H . Reverse engineering analysis based on differential fault analysis against secret s-boxes [J]. China Communications , 2012 , 9 ( 10 ): 10 - 22 .

CLAVIER C , WURCKER A . Reverse engineering of a secret AES-like cipher by ineffective fault analysis [C]// 2013 Workshop on Fault Diagnosis and Tolerance in Cryptography . Piscataway : IEEE , 2013 : 119 - 128 .

ZHANG F , LOU X X , ZHAO X J , et al . Persistent fault analysis on block ciphers [J]. IACR Transactions on Cryptographic Hardware and Embedded Systems , 2018 , 3 : 150 - 172 .

CAFORIO A , BANIK S . A study of persistent fault analysis [C]// International Conference on Security, Privacy, and Applied Cryptography Engineering . Cham : Springer , 2019 : 13 - 33 .

ZHANG F , ZHANG Y R , JIANG H L , et al . Persistent fault attack in practice [J]. IACR Transactions on Cryptographic Hardware and Embedded Systems , 2020 , 2 : 172 - 195 .

ZHENG S H , LIU X D , ZANG S J , et al . A persistent fault-based collision analysis against the advanced encryption standard [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2021 , 40 ( 6 ): 1117 - 1129 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Security Evaluation Against Impossible Differential Cryptanalysis and Zero Correlation Linear Cryptanalysis for Two Dynamic Cryptographic Structures

Construction of Fault Injection Attacks Resistant S-Boxes

New Integral Attack on Rijndael-256

Differential and Linear Iterative Characteristics of Camellia

Related Author

SHEN Xuan

LIU Guo-qiang

SUN Bing

HE Jun

CHAI Jin-jin

WU Xuan

WEI Yue-chuan

SUN Bing

Related Institution

Hunan Engineering Research Center of Commercial Cryptography Theory and Technology Innovation

State Key Laboratory of Information Security， Institute of Information Engineering， Chinese Academy of Sciences

College of Sciences， National University of Defense Technology

College of Information and Communication， National University of Defense Technology

Institute of Air Defense and Anti-missile， Air Force Engineering University

⁰