SCARE and power attack on AES-like block ciphers with secret S-box

doi:10.1007/s11704-020-0319-z

Front. Comput. Sci.

2022, Vol. 16

Issue (4) : 164814 https://doi.org/10.1007/s11704-020-0319-z

RESEARCH ARTICLE

SCARE and power attack on AES-like block ciphers with secret S-box

Xin LIU^1,², An WANG^1,², Liehuang ZHU¹, Yaoling DING^1,²(

), Zeyuan LYU¹, Zongyue WANG³

¹. School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081, China
². State Key Laboratory of Cryptology, P.O. Box 5159 Beijing 100878, China
³. Open Security Research, Shenzhen 518063, China

Download: PDF(5157 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Despite Kerckhoff's principle, there are secret ciphers with unknown components for diplomatic or military usages. The side-channel analysis of reverse engineering (SCARE) is developed for analyzing secret ciphers. Considering the side-channel leakage, SCARE attacks enable the recovery of some secret parts of a cryptosystem, e.g., the substitution box table. However, based on idealized leakage assumption, most of these attacks have a few limitations on prior knowledge or implementations. In this paper, we focus on AES-like block ciphers with a secret S-box and demonstrate an attack which recovers both the secret key and the secret S-box. On the one hand, the key is recovered under profiled circumstance by leakage analysis and collision attack. On the other hand, the SCARE attack is based on mathematical analysis. It relies on Hamming weight of MixColumns intermediate results in the first round, which can restore the secret S-box. Experiments are performed on real power traces from a software implementation of AES-like block cipher. Moreover, we evaluate the soundness and efficiency of our method by simulations and compare with previous approaches. Our method has more advantages in intermediate results location and the required number of traces. For simulated traces with gaussian noise, our method requires 100000 traces to fully restore the secret S-box, while the previous method requires nearly 300000 traces to restore S-box.

Keywords cryptography SCARE side-channel analysis AES secret S-box

Corresponding Author(s): Yaoling DING

Just Accepted Date: 18 December 2020 Issue Date: 15 November 2021

Cite this article:

Xin LIU,An WANG,Liehuang ZHU, et al. SCARE and power attack on AES-like block ciphers with secret S-box[J]. Front. Comput. Sci., 2022, 16(4): 164814.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-020-0319-z
https://academic.hep.com.cn/fcs/EN/Y2022/V16/I4/164814

Fig.1 The attack scenario

Fig.2 AES-128 encryption structure

Fig.3 The framework of our attack

Fig.4 Standard deviation trace computed on

T 1

traces

Fig.5 k₀ recovery by PCECA

Fig.6 CECA on

T 2

Fig.7

Fig.8 Power consumption of MixColumns operation in the first round

$T$	( $x 0$ , $x 5$ , $x 10$ , $x 15$ ) (Hex)
$T 0$	(00, 01, 02, 03)
$T 1$	(01, 02, 03, 04)
$?$	$?$
$T 254$	(FE, FF, 00, 01)
$T 255$	(FF, 00, 01, 02)

Tab.1 Chosen plaintexts requirement

Fig.9 Standard deviation trace computed on

T

Fig.10 Self-correlation analysis on y₀ (top), 2y₀ (middle), and 3y₀ (bottom)

Fig.11 Self-correlation diagram. (a) Self-correlation with x-axis 387 column samples (2y₀) in

T

; (b) Self-correlation with x-axis 937 column samples (y₀) in

T

; (c) Self-correlation with x-axis 1837 column samples (3y₀) in

T

Fig.12 Annotation of intermediate results

Fig.13 The observation of

T

overlapping

$t$ (Hex)	$τ [t]$ (Hex)
00	0D, 0F, 10, 17, 1B, 1D, 27, 2E, 33, 36, 39, 3A, 47, 4E, 5C, 63, 66
01	1F, 3E, 7C
02	5F, 6F, 77, 7B, 7D
03	5F, 6F, 77, 7B, 7D
$?$	$?$
FF	0B, 0D, 13, 16, 19, 1A, 26, 2C, 31, 32, 34, 43, 46, 4C, 58, 61, 62, 63, 64, 68

Tab.2 Candidate S-box table

Fig.14

$t$ (Hex)	$τ [t] ′$ (Hex)	No.
00	(63, 1F, 5F, 7B), (63, 7C, 77, 7B), $?$	53
$?$	$?$	$?$
09	(01, 67, 2B, FE), (01, 67, 2D, FB), $?$	21
0A	(67, 2B, FE, D7)	1
0B	(2B, FE, D7, AB), (2B, FE, B7, 9E), $?$	7
$?$	$?$	$?$
FF	(61, 5C, 7C, 7B),(62, 47, 7C, 7B), $?$	38

Tab.3 Candidate sets table

Fig.15

Fig.16 Number of candidate values of y₀ obtained in stage 1 and stage 2

Fig.17 S-box searching principle

Fig.18 Terms of the tree

Fig.19

Index	Stage 1	Stage 2	Stage 3
Time complexity	$O (2 m × 2 n)$	$O (2 m × 2 4 n)$	$O (2 m × 2 n)$

Tab.4 Time complexity of three stages in S-box reconstruction

Tab.5 Comparison with previous SCAREs

Fig.20 Accuracy comparison between SREDPA and our method

1	Kocher P, Jaffe J, Jun B. Differential power analysis. In: Proceedings of Annual International Cryptology Conference. 1999, 388−397
2	Kocher P C. Timing attacks on implementations of timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Proceedings of Annual International Cryptology Conference. 1996, 104−113
3	Brier E, Clavier C, Oliver F. Correlation power analysis with a leakage model. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. 2004, 16−29
4	Chari S, Rao J R, Rohatgi P. Template attacks. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. 2002, 13−28
5	Schramm K, Wollinger T, Paar C. A new class of collision attacks and its application to DES. In: Proceedings of International Workshop on Fast Software Encryption. 2003, 206−222
6	Gierlichs B, Batina L, Tuyls P, Preneel B. Mutual information analysis. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. 2008, 426−442
7	Garcia F D, de Koning Gans G, Muijrers R, van Rossum P, Verdult R, Schreur R W, Jacobs B. Dismantling MIFARE classic. In: Proceedings of 13th European Symposium on Research in Computer Security. 2008, 97−114
8	M Holler , M Odstrcil , M Guizar-Sicairos , M Lebugle , E Müller , S Finizio , G Tinti , C David , J Zusman , W Unglaub , O Bunk , J Raabe , A F J Levi , G Aeppli . Three-dimensional imaging of integrated circuits with macro- to nanoscale zoom. Nature Electronics, 2019, 2( 10): 464– 470
9	Tiessen T, Knudsen L R, Kölbl S, Lauridsen M M. Security of the AES with a secret S-box. In: Proceedings of International Workshop on Fast Software Encryption. 2015, 175−189
10	Clavier C, Isorez Q, Wurcker A. Complete SCARE of AES-like block ciphers by chosen plaintext collision power analysis. In: Proceedings of International Conference on Cryptology in India. 2013, 116−135
11	Clavier C, Wurcker A. Reverse engineering of a secret AES-like cipher by ineffective fault analysis. In: Proceedings of 2013 Workshop on Fault Diagnosis and Tolerance in Cryptography. 2013, 119−128
12	Sun B, Liu M, Guo J, Qu L, Rijmen V. New insights on AES-like SPN ciphers. In: Proceedings of Annual International Cryptology Conference. 2016, 605−624
13	L Grassi , C Rechberger , S Rønjom . Subspace trail cryptanalysis and its applications to AES. IACR Transactions on Symmetric Cryptology, 2017, 2016( 2): 192– 225
14	Rivain M, Roche T. SCARE of secret ciphers with SPN structures. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. 2013, 526−544
15	M Tang , Z L Qiu , H B Peng , X B Hu , M Yi , H G Zhang . Toward reverse engineering on secret s-boxes in block ciphers. Science China: Information Sciences, 2014, 57( 3): 1– 18
16	Gao S, Chen H, Wu W, Fan L, Feng J, Ma X. Linear regression attack with F-test: A New SCARE Technique for Secret Block Ciphers. In: Proceedings of International Conference on Cryptology and Network Security. 2016, 3−18
17	J Breier , D Jap , X Hou , S Bhasin . On side channel vulnerabilities of bit permutations in cryptographic algorithms. IEEE Transactions on Information Forensics and Security, 2019, 15 : 1072– 1085
18	Caforio A, Banik S. A study of persistent fault analysis. In: Proceedings of International Conference on Security, Privacy, and Applied Cryptography Engineering. 2019, 13−33
19	Clavier C. An improved SCARE cryptanalysis against a secret A3/A8 GSM algorithm. In: Proceedings of International Conference on Information Systems Security. 2007, 143−155
20	Novak R. Side-channel attack on substitution blocks. In: Proceedings of International Conference on Applied Cryptography and Network Security. 2003, 307−318
21	Moradi A, Mischke O, Eisenbarth T. Correlation-enhanced power analysis collision attack. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. 2010, 125−139
22	Joan D, Vincent R. The design of Rijndael: AES-the advanced encryption standard. 1st ed. Berlin: Springer-Verlag, 2002

[1]

Download

[1]	Yang WANG, Mingqiang WANG. On the hardness of NTRU problems[J]. Front. Comput. Sci., 2022, 16(6): 166822-.
[2]	Yuejun LIU, Yongbin ZHOU, Rui ZHANG, Yang TAO. (Full) Leakage resilience of Fiat-Shamir signatures over lattices[J]. Front. Comput. Sci., 2022, 16(5): 165819-.
[3]	Xinghua LI, Ting CHEN, Qingfeng CHENG, Jianfeng MA. An efficient and authenticated key establishment scheme based on fog computing for healthcare system[J]. Front. Comput. Sci., 2022, 16(4): 164815-.
[4]	Yu OU, Lang LI. Side-channel analysis attacks based on deep learning network[J]. Front. Comput. Sci., 2022, 16(2): 162303-.
[5]	Lein HARN, Chingfang HSU, Zhe XIA. A novel threshold changeable secret sharing scheme[J]. Front. Comput. Sci., 2022, 16(1): 161807-.
[6]	Abhishek MAJUMDAR, Arpita BISWAS, Atanu MAJUMDER, Sandeep Kumar SOOD, Krishna Lal BAISHNAB. A novel DNA-inspired encryption strategy for concealing cloud storage[J]. Front. Comput. Sci., 2021, 15(3): 153807-.
[7]	Momeng LIU, Yupu HU. Universally composable oblivious transfer from ideal lattice[J]. Front. Comput. Sci., 2019, 13(4): 879-906.
[8]	Wei GAO, Guilin WANG, Kefei CHEN, Xueli WANG. Efficient identity-based threshold decryption scheme from bilinear pairings[J]. Front. Comput. Sci., 2018, 12(1): 177-189.
[9]	Weimin TAN,Bo YAN. A survey on high coherence visual media retargeting: recent advances and applications[J]. Front. Comput. Sci., 2016, 10(5): 778-796.
[10]	Mingming JIANG,Yupu HU,Hao LEI,Baocang WANG,Qiqi LAI. Lattice-based certificateless encryption scheme[J]. Front. Comput. Sci., 2014, 8(5): 828-836.
[11]	Xiuhua LU,Qiaoyan WEN,Zhengping JIN,Licheng WANG,Chunli YANG. A lattice-based signcryption scheme without random oracles[J]. Front. Comput. Sci., 2014, 8(4): 667-675.
[12]	Lin CHENG, Qiaoyan WEN, Zhengping JIN, Hua ZHANG. Cryptanalysis and improvement of a certificateless encryption scheme in the standard model[J]. Front. Comput. Sci., 2014, 8(1): 163-173.
[13]	Yi WANG, Renfa LI. FPGA based unified architecture for public key and private key cryptosystems[J]. Front Comput Sci, 2013, 7(3): 307-316.
[14]	Xixiang LV, Hui LI, Baocang WANG. Identity-based key distribution for mobile Ad Hoc networks[J]. Front Comput Sci Chin, 2011, 5(4): 442-447.
[15]	Sheng GAO, Wenping MA, Zepeng ZHUO, Fenghe WANG. On cross-correlation indicators of an S-box[J]. Front Comput Sci Chin, 2011, 5(4): 448-453.

Viewed

Full text

Abstract

Cited

Shared

Discussed