Toward reverse engineering on secret S-boxes in block ciphers  

作　　者：TANG Ming QIU ZhenLong PENG HongBo HU XiaoBo YI Mu ZHANG HuanGuo 

机构地区：[1]School of Computer Science,Wuhan University [2]State Key Lab. of AIS & TC,Ministry of Education,Wuhan University [3]Beijing NanRui ZhiXin Microelectronics Technology Co.,Ltd [4]Centre for Computer and Information Security Research,School of Computer Science and Software Engineering,University of Wollongong

出　　处：《Science China(Information Sciences)》2014年第3期164-181,共18页中国科学（信息科学）（英文版）

基　　金：supported by the National Natural Science Foundation of China(Grant Nos.61202386,60970116,60970115,61003268,61003267)

摘　　要：It has been widely accepted that the security cryptosystems should be only dependent on the security of their secret keys. However, there are still secret ciphers with unknown components in their commercial applications due to various reasons. The existing reverse engineering analyzes are developed for analyzing specific ciphers, and cannot cope with secret algorithms with different structures. By looking into the common characteristics of the secret algorithms of ciphers implemented with unknown S-boxes, we proposed a novel reverse engineering analysis approach referred to as Signed Reverse Engineering based on Differential Power Analysis （SREDPA）. It is a generic reverse engineering analysis and can recover the parameters of the secret S-boxes of the block ciphers in typical structures such as SPN, Feistel, and XFeistel （eXtended Feistel）. By identifying the bias of the differential power analysis （DPA） traces, we build the theoretical model of SREDPA and prove its effectiveness. Experiments are performed on secret algorithms in different structures and further validate our SREDPA experimentally. The complexity of SREDPA only relies on the size of S-boxes and the reverse engineering analysis is efficient. As shown in the theoretical analysis and the conducted experiments, our SREDPA approach is readily to be extended for analyzing other secret ciphers with unknown S-boxes. This renders a new challenge on the design and implementation of secret ciphers.It has been widely accepted that the security cryptosystems should be only dependent on the security of their secret keys. However, there are still secret ciphers with unknown components in their commercial applications due to various reasons. The existing reverse engineering analyzes are developed for analyzing specific ciphers, and cannot cope with secret algorithms with different structures. By looking into the common characteristics of the secret algorithms of ciphers implemented with unknown S-boxes, we proposed a novel reverse engineering analysis approach referred to as Signed Reverse Engineering based on Differential Power Analysis （SREDPA）. It is a generic reverse engineering analysis and can recover the parameters of the secret S-boxes of the block ciphers in typical structures such as SPN, Feistel, and XFeistel （eXtended Feistel）. By identifying the bias of the differential power analysis （DPA） traces, we build the theoretical model of SREDPA and prove its effectiveness. Experiments are performed on secret algorithms in different structures and further validate our SREDPA experimentally. The complexity of SREDPA only relies on the size of S-boxes and the reverse engineering analysis is efficient. As shown in the theoretical analysis and the conducted experiments, our SREDPA approach is readily to be extended for analyzing other secret ciphers with unknown S-boxes. This renders a new challenge on the design and implementation of secret ciphers.

关 键 词：SCA DPA SPEDPA CRYPTANALYSIS block ciphers S-boxes 

分 类 号：TN918[电子电信—通信与信息系统]