Fault-Tolerant Bidirectional Choice Attack Combining EDCA and CPA

doi:10.3778/j.issn.1673-9418.2206108

Abstract

Abstract: When the designed attack scheme is fault-tolerant, it is often necessary to pick out the correct key in a very large candidate space. How to effectively achieve this goal is a very important and challenging problem in side-channel attacks. Aiming at this problem, a fault-tolerant bidirectional choice attack combining EDCA (Euclidean distance enhanced collision attack) and CPA (correlation power analysis) is studied with AES-128 as the target. Firstly, in order to improve the success rate of collision detection, the EDCA is proposed. Compared with correlation enhanced collision attack (CCA), EDCA utilizes the Euclidean distance to distinguish the similarity between two sets of energy traces. Its collision detection has a higher success rate, making the optimization more practical and meaningful. In addition, combined with EDCA and CPA, the keys and the corresponding collision pairs are grouped, and then bidirectional screening is performed to obtain the optimal collision chain, which greatly reduces the candidate space and reduces the complexity of key enumeration, effectively recovering the key. Experimental results show that, under the conditions of low signal-to-noise ratio[SNR=-3 dB]and [SNR=-6 dB], setting the threshold of collision pair being 5, the success rate of the proposed scheme reaches 98.78% and 80.25% when there are 3000 energy traces, both of which are better than the existing schemes.

Key words: AES-128, collision attack, Euclidean distance enhanced collision attack (EDCA), correlation power analysis (CPA), bidirectional choice

摘要： 当所设计的攻击方案带有容错功能时，往往需要在非常大的候选空间中挑出正确的密钥。如何有效地实现这个目标是侧信道攻击中非常重要且具有挑战性的问题。针对这一问题，以AES-128为目标研究了结合欧式距离增强碰撞攻击（EDCA）和相关能量分析攻击（CPA）的容错双向选择攻击。为了提高碰撞检测的成功率，提出了EDCA，与传统的相关增强碰撞攻击（CCA）相比，EDCA利用欧式距离来区分两组能量迹之间的相似性，其碰撞检测的成功率更高，从而使优化更加实用和有意义。除此之外，结合EDCA和CPA，将密钥以及对应的碰撞对做分组处理，然后进行双向筛选，得到最优的碰撞链，大大减少了候选空间，从而降低了密钥枚举的复杂性，有效地恢复密钥。实验结果表明，在低信噪比[SNR=-3 dB]和[SNR=-6 dB]的条件下，设置碰撞对的阈值[ThΔ=5]，所提出的方案在3 000条能量迹时成功率达到98.78%和80.25%，均优于现有方案。

关键词: AES-128, 碰撞攻击, 欧式距离增强碰撞攻击（EDCA）, 相关能量分析攻击（CPA）, 双向选择

ZHANG Meiling, SHANG Lirong, ZHENG Dong. Fault-Tolerant Bidirectional Choice Attack Combining EDCA and CPA[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(9): 2229-2240.

张美玲, 尚利蓉, 郑东. 结合EDCA和CPA的容错双向选择攻击[J]. 计算机科学与探索, 2023, 17(9): 2229-2240.

References

[1] KOCHER P C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[C]//LNCS 1109: Pro-ceedings of the 16th Annual International Cryptology Con-ference, Santa Barbara, Aug 18-22, 1996. Berlin, Heidelberg: Springer, 1996: 104-113.
[2] KOCHER P, JAFFE J, JUN B. Differential power analysis[C]//LNCS 1666: Proceedings of the 19th Annual International Cryptology Conference, Santa Barbara, Aug 15-19, 1999. Berlin, Heidelberg: Springer, 1999: 388- 397.
[3] 张俊. SCVerify: 抗功耗侧信道攻击软件实现的验证[J]. 计算机科学与探索, 2021, 15(6): 1074-1083.
ZHANG J. SCVerify: verification of software implementation against power side-channel attacks[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(6): 1074-1083.
[4] GANDOLFI K, MOURTEL C, OLIVIER F. Electromagnetic analysis: concrete results[C]//LNCS 2162: Proceedings of the 3rd International Workshop on Cryptographic Hardware and Embedded Systems, Paris, May 14-16, 2001. Berlin, Hei-delberg: Springer, 2001: 251- 261.
[5] SCHL?SSER A, NEDOSPASOV D, KR?MER J, et al. Simple photonic emission analysis of AES[C]//LNCS 7428: Proceedings of the 14th International Workshop on Crypto-graphic Hardware and Embedded Systems, Leuven, Sep 9-12, 2012. Berlin, Heidelberg: Springer, 2012: 41-57.
[6] BRIER E, CLAVIER C, OLIVIER F. Correlation power analysis with a leakage model[C]//LNCS 3156: Proceedings of the 6th International Workshop on Cryptographic Hard-ware and Embedded Systems, Cambridge, Aug 11-13, 2004. Berlin, Heidelberg: Springer, 2004: 16-29.
[7] CHARI S, RAO J R, ROHATGI P. Template attacks[C]//LNCS 2523: Proceedings of the 4th International Workshop on Cryptographic Hardware and Embedded Systems, Red-wood Shores, Aug 13-15, 2002. Berlin, Heidelberg: Springer, 2002: 13-28.
[8] LI Y, WANG S, WANG Z, et al. A strict key enumeration algorithm for dependent score lists of side-channel attacks[C]//LNCS 10728: Proceedings of the 16th International Conference on Smart Card Research and Advanced Appli-cations, Lugano, Nov 13-15, 2017. Cham: Springer, 2017: 51-69.
[9] POUSSIER R, STANDAERT F X, GROSSO V. Simple key enumeration (and rank estimation) using histograms: an inte-grated approach[C]//LNCS 9813: Proceedings of the 18th International Conference on Cryptographic Hardware and Embedded Systems, Santa Barbara, Aug 17-19, 2016. Cham: Springer, 2016: 61-81.
[10] VEYRAT C N, GéRARD B, STANDAERT F X. Security evaluations beyond computing power[C]//LNCS 7881: Pro-ceedings of the 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, May 26-30, 2013. Berlin, Heidelberg: Springer, 2013: 126-141.
[11] SCHRAMM K, WOLLINGER T, PAAR C. A new class of collision attacks and its application to DES[C]//LNCS 2887: Proceedings of the 10th International Workshop on Fast Software Encryption. Berlin, Heidelberg: Springer, 2003: 206-222.
[12] SCHRAMM K, LEANDER G, FELKE P, et al. A collision-attack on AES combining side channel and differential-attack[C]//LNCS 3156: Proceedings of the 6th International Workshop on Cryptographic Hardware and Embedded Systems. Berlin, Heidelberg: Springer, 2004: 163-175.
[13] BOGDANOV A. Improved side-channel collision attacks on AES[C]//LNCS 4876: Proceedings of the 14th International Workshop on Selected Areas in Cryptography, Ottawa, Aug 16-17, 2007. Berlin, Heidelberg: Springer, 2007: 84-95.
[14] BOGDANOV A. Multiple-differential side-channel collision attacks on AES[C]//LNCS 5154: Proceedings of the 10th International Workshop on Cryptographic Hardware and Embedded Systems, Washington, Aug 10-13, 2008. Berlin, Heidelberg: Springer, 2008: 30-44.
[15] YUAN Y, WU L, YANG Y, et al. A novel multiple-bits collision attack based on double detection with error-tolerant mechanism[J]. Security and Communication Networks, 2018: 2483619.
[16] ZHENG D, JIA X, ZHANG M. Hypothesis testing based side-channel collision analysis[J]. IEEE Access, 2019, 7: 104218-104227.
[17] DING Y, SHI Y, WANG A, et al. Adaptive chosen-plaintext collision attack on masked AES in edge computing[J]. IEEE Access, 2019, 7: 63217-63229.
[18] 郑东, 王柳生, 赵秉宇, 等. 改进的基于掩码AES选择明文碰撞攻击方法[J]. 西安邮电大学学报, 2021, 26(6): 57-65.
ZHENG D, WANG L S, ZHAO B Y, et al. Improved chosen-plaintext collision attack on masked AES[J]. Journal of Xi’an University of Posts and Telecommunications, 2021, 26(6): 57-65.
[19] BOGDANOV A, KIZHVATOV I. Beyond the limits of DPA: combined side-channel collision attacks[J]. IEEE Transactions on Computers, 2011, 61(8): 1153-1164.
[20] OU C, LAM S K, ZHOU C, et al. A lightweight detection algorithm for collision-optimized divide-and-conquer attacks[J]. IEEE Transactions on Computers, 2020, 69(11): 1694-1706.
[21] WANG D, WANG A, ZHENG X. Fault-tolerant linear col-lision attack: a combination with correlation power analysis[C]//LNCS 8434: Proceedings of the 10th International Con-ference on Information Security Practice and Experience, Fuzhou, May 5-8, 2014. Cham: Springer, 2014: 232-246.
[22] OU C, WANG Z, SUN D, et al. Group collision attack[J]. IEEE Transactions on Information Forensics and Security, 2019, 14(4): 939-953.
[23] DAEMEN J, REIJNDAEL R V. The advanced encryption standard[J]. Dr. Dobb’s Journal: Software Tools for the Pro-fessional Programmer, 2001, 26(3): 137-139.
[24] ROZANOV Y. Probability theory, random processes and mathematical satatistics[M]. Berlin: Springer Science & Business Media, 2012: 171-200.
[25] MORADI A, MISCHKE O, EISENBARTH T. Correlation-enhanced power analysis collision attack[C]//LNCS 6225: Proceedings of the 12th International Workshop on Crypto-graphic Hardware and Embedded Systems, Santa Barbara, Aug 17-20, 2010. Berlin, Heidelberg: Springer, 2010: 125-139.
[26] YE X, CHEN C, EISENBARTH T. Non-linear collision analysis[C]//LNCS 8651: Proceedings of the 10th International Workshop on Radio Frequency Identification: Security and Privacy Issues, Oxford, Jul 21-23, 2014. Cham: Springer, 2015: 198-214.