Side-Channel Linearization Attack on Unrolled Trivium Hardware
Authors
Soichiro Kobayashi, Rei Ueno, Yosuke Todo, Naofumi Homma
Rei Ueno
Kyoto University, Kyoto, Japan
ueno dot rei dot 2e at kyoto-u dot ac dot jp
ueno dot rei dot 2e at kyoto-u dot ac dot jp
Yosuke Todo
NTT Social Informatics Laboratories, Tokyo, Japan
yosuke dot todo at ntt dot com
yosuke dot todo at ntt dot com
Naofumi Homma
Tohoku University, Sendai, Japan
naofumi dot homma dot c8 at tohoku dot ac dot jp
naofumi dot homma dot c8 at tohoku dot ac dot jp
Keywords:
Stream cipher
Trivium
Unrolled implementation
Side-channel attack (SCA)
Correlation power analysis (CPA)
Abstract
This paper presents a new side-channel attack (SCA) on unrolled implementations of stream ciphers, with a particular focus on Trivium. Most conventional SCAs predominantly concentrate on leakage of some first rounds prior to the sufficient diffusion of the secret key and initial vector (IV). However, recently, unrolled hardware implementation has become common and practical, which achieves higher throughput and energy efficiency compared to a round-based hardware. The applicability of conventional SCAs to such unrolled hardware is unclear because the leakage of the first rounds from unrolled hardware is hardly observed. In this paper, focusing on Trivium, we propose a novel SCA on unrolled stream cipher hardware, which can exploit leakage of rounds latter than 80, while existing SCAs exploited intermediate values earlier than 80 rounds. We first analyze the algebraic equations representing the intermediate values of these rounds and present the recursive restricted linear decomposition (RRLD) strategy. This approach uses correlation power analysis (CPA) to estimate the intermediate values of latter rounds. Furthermore, we present a chosen-IV strategy for a successful key recovery through linearization. We experimentally demonstrate that the proposed SCA achieves the key recovery of a 288-round unrolled Trivium hardware implementation using 360,000 traces. Finally, we evaluate the performance of unrolled Trivium hardware implementations to clarify the trade-off between performance and SCA (in)security. The proposed SCA requires 34.5 M traces for a key recovery of 384-round unrolled Trivium implementation and is not applicable to 576-round unrolled hardware.
References
[BGSD10]
Shivam Bhasin, Sylvain Guilley, Laurent Sauvage, and Jean-Luc Danger. Unrolling Cryptographic Circuits: A Simple Countermeasure Against Side-Channel Attacks. In Topics in Cryptology—CT-RSA 2010, pages 195–207. 2010. DOI: https://doi.org/10.1007/978-3-642-11925-5_14
[BMA+18]
Subhadeep Banik, Vasily Mikhalev, Frederik Armknecht, Takanori Isobe, Willi Meier, Andrey Bogdanov, Yuhei Watanabe, and Francesco Regazzoni. Towards low energy stream ciphers. IACR Transactions on Symmetric Cryptology, 2018. DOI: https://doi.org/10.13154/tosc.v2018.i2.1-19
[BZD+16]
Hanno Böck, Aaron Zauner, Sean Devlin, Juraj Somorovsky, and Philipp Jovanovic. Nonce-disrespecting adversaries: practical forgery attacks on GCM in TLS. In Proceedings of the 10th USENIX Conference on Offensive Technologies, pages 15–25. 2016.
[Can06]
Christophe De Canniere. Trivium specifications. http://www.ecrypt.eu.org/stream/p3ciphers/trivium/trivium_p3.pdf. 2006.
[CBT+21]
Andrea Caforio, Subhadeep Banik, Yosuke Todo, Willi Meier, Takanori Isobe, Fukang Liu, and Bin Zhang. Perfect Trees: Designing Energy-Optimal Symmetric Encryption Primitives. IACR Transactions on Symmetric Cryptology, 2021. DOI: https://doi.org/10.46586/tosc.v2021.i4.36-73
[CMM+23]
Gaëtan Cassiers, Loïc Masure, Charles Momin, Thorben Moos, Amir Moradi, and François-Xavier Standaert. Randomness Generation for Secure Hardware Masking - Unrolled Trivium to the Rescue. Cryptology ePrint Archive, Paper 2023/1134. 2023.
[DCP08]
Christophe De Canniere and Bart Preneel. Trivium. New Stream Cipher Designs: The eSTREAM Finalists, 2008.
[dMB08]
Leonardo de Moura and Nikolaj Bjørner. Z3: An Efficient SMT Solver. In Tools and Algorithms for the Construction and Analysis of Systems, pages 337–340. 2008.
[DS09]
Itai Dinur and Adi Shamir. Cube Attacks on Tweakable Black Box Polynomials. In Advances in Cryptology—EUROCRYPT 2009, pages 278–299. 2009. DOI: https://doi.org/10.1007/978-3-642-01001-9_16
[eST]
The eSTREAM portfolio—eSTREAM: the ECRYPT Stream Cipher Project.
[FDLZ15]
Yunsi Fei, A. Adam Ding, Jian Lao, and Liwei Zhang. A statistics-based success rate model for DPA and CPA. Journal of Cryptographic Engineering, 5, 2015. DOI: https://doi.org/10.1007/s13389-015-0107-0
[FGKV06]
Wieland Fischer, Berndt M Gammel, Oliver Kniffler, and Joachim Velten. Differential Power Analysis of Stream Ciphers. In Topics in Cryptology–CT-RSA 2007: The Cryptographers' Track at the RSA Conference 2007, San Francisco, CA, USA, February 5-9, 2007. Proceedings, pages 257–270. 2006. Springer. DOI: https://doi.org/10.1007/11967668_17
[FPS12]
Sebastian Faust, Krzysztof Pietrzak, and Joachim Schipper. Practical Leakage-Resilient Symmetric Cryptography. In International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2012), volume 7428 of Lecture Notes in Computer Science, pages 213–232. 2012. Springer. DOI: https://doi.org/10.1007/978-3-642-33027-8_13
[HHLW24]
Jiahui He, Kai Hu, Hao Lei, and Meiqin Wang. Massive Superpoly Recovery with a Meet-in-the-middle Framework: Improved Cube Attacks on Trivium and Kreyvium. In Advances in Cryptology—EUROCRYPT 2024. 2024. DOI: https://doi.org/10.1007/978-3-031-58716-0_13
[HHN+13]
Takafumi Hibiki, Naofumi Homma, Yuto Nakano, Kazuhide Fukushima, Shinsaku Kiyomoto, Yuta Miyake, and Takafumi Aoki. Chosen-IV Correlation Power Analysis on KCipher-2 and a Countermeasure. In International Workshop on Constructive Side-Channel Analysis and Secure Design (COSADE 2013), volume 7864 of Lecture Notes in Computer Science, pages 169–183. 2013. DOI: https://doi.org/10.1007/978-3-642-40026-1_11
[iso]
ISO/IEC 29192-3:2012 Information technology—Security techniques—Lightweight cryptography— Part 3: Stream ciphers. https://www.iso.org/standard/56426.html.
[ISUH21]
Akira Ito, Kotaro Saito, Rei Ueno, and Naofumi Homma. Imbalanced Data Problems in Deep Learning-Based Side-Channel Attacks: Analysis and Solution. IEEE Transactions on Information Forensics and Security, 16:3790–3802, 2021. DOI: 10.1109/TIFS.2021.3092050
[IUH21]
Akira Ito, Rei Ueno, and Naofumi Homma. Toward Optimal Deep-Learning Based Side-Channel Attacks: Probability Concentration Inequality Loss and Its Usage. https://ia.cr/2021/1216. Cryptology ePrint Archive, Report 2021/1216. 2021.
[JHWW12]
Yanyan Jia, Yupu Hu, Fenghe Wang, and Hongxian Wang. Correlation power analysis of Trivium. Security and Communication Networks, 5(5):479–484, 2012. DOI: https://doi.org/10.1002/sec.329
[KDB+22]
Satyam Kumar, Vishnu Asutosh Dasu, Anubhab Baksi, Santanu Sarkar, Dirmanto Jap, Jakub Breier, and Shivam Bhasin. Side Channel Attack On Stream Ciphers: A Three-Step Approach To State/Key Recovery. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022. DOI: https://doi.org/10.46586/tches.v2022.i2.166-191
[KUH+17]
Wataru Kawai, Rei Ueno, Naofumi Homma, Takafumi Aoki, Kazuhide Fukushima, and Shinsaku Kiyomoto. Practical Power Analysis on KCipher-2 Software on Low-End Microcontrollers. In Workshop on Security for Embedded and Mobile System, IEEE European Symposium on Security and Privacy Workshops (SEMS, EuroSPW 2017), pages 113–121. 2017. DOI: 10.1109/EuroSPW.2017.60
[MHBM+18]
Maxime Montoya, Thomas Hiscock, Simone Bacles-Min, Anca Molnos, and Jacques J.A. Fournier. Energy-efficient Masking of the Trivium Stream Cipher. In 2018 25th IEEE International Conference on Electronics, Circuits and Systems (ICECS), pages 393–396. 2018. DOI: https://doi.org/10.1109/ICECS.2018.8617892
[Mic23]
Microsoft. Z3 API in Python. https://www.microsoft.com/en-us/research/project/z3-3/. 2023.
[Moo20]
Thorben Moos. Unrolled Cryptography on Silicon: A Physical Security Analysis. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020(4):416–442, 2020. DOI: https://doi.org/10.13154/tches.v2020.i4.416-442
[MPO05]
Stefan Mangard, Norbert Pramstaller, and Elisabeth Oswald. Successfully Attacking Masked AES Hardware Implementations. In International Workshop on Cryptographic Hardware and Embedded Systems (CHES), pages 157–171. 2005. DOI: https://doi.org/10.1007/11545262_12
[MS16]
Amir Moradi and Tobias Schneider. Side-Channel Analysis Protection and Low-Latency in Action. In Advances in Cryptology—ASIACRYPT 2016, pages 517–547. 2016. DOI: https://doi.org/10.1007/978-3-662-53887-6_19
[PHJ+19]
Stjepan Picek, Annelie Heuser, Alan Jovic, Shivam Bhasin, and Francesco Regazzoni. The Curse of Class Imbalance and Conflicting Metrics with Machine Learning for Side-channel Evaluations. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019. DOI: https://doi.org/10.13154/tches.v2019.i1.209-237
[Pro05]
Emmanuel Prouff. DPA Attacks and S-Boxes. In Fast Software Encryption, pages 424–441. 2005. DOI: https://doi.org/10.1007/11502760_29
[SA15]
Dillibabu Shanmugam and Suganya Annadurai. Secure Implementation of Stream Cipher: Trivium. In Innovative Security Solutions for Information Technology and Communications, pages 253–266. 2015. DOI: https://doi.org/10.1007/978-3-319-27179-8_18
[SJB21]
Siang Meng Sim, Dirmanto Jap, and Shivam Bhasin. DAPA: Differential Analysis aided Power Attack on (Non-)Linear Feedback Shift Registers. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021. DOI: https://doi.org/10.46586/tches.v2021.i1.169-191
[SPK09]
Daehyun Strobel, Ing Christof Paar, and M Kasper. Side channel analysis attacks on stream ciphers. Masterarbeit Ruhr-Universität Bochum, Lehrstuhl Embedded Security, 2009.
[TSA15a]
Erica Tena-Sánchez and Antonio J Acosta. DPA vulnerability analysis on Trivium stream cipher using an optimized power model. In 2015 IEEE International Symposium on Circuits and Systems (ISCAS), pages 1846–1849. 2015. IEEE. DOI: https://doi.org/10.1109/ISCAS.2015.7169016
[TSA15b]
Erica Tena-Sánchez and Antonio J Acosta. Optimized DPA attack on Trivium stream cipher using correlation shape distinguishers. In 2015 Conference on Design of Circuits and Integrated Systems (DCIS), pages 1–6. 2015. IEEE. DOI: 10.1109/DCIS.2015.7388578
[UHIM23]
Rei Ueno, Naofumi Homma, Akiko Inoue, and Kazuhiko Minematsu. Fallen Sanctuary: A Higher-Order and Leakage-Resilient Rekeying Scheme. IACR Transactions on Cryptographic Hardware and Embedded Systems, 1(2024):264–308, 2023. DOI: https://doi.org/10.46586/tches.v2024.i1.264-308
[YMHA16]
Ville Yli-Mäyry, Naofumi Homma, and Takafumi Aoki. Improved Power Analysis on Unrolled Architecture and Its Application to PRINCE Block Cipher. In Lightweight Cryptography for Security and Privacy, pages 148–163. 2016. DOI: https://doi.org/10.1007/978-3-319-29078-2_9
[YMUM+21]
Ville Yli-Mäyry, Rei Ueno, Noriyuki Miura, Makoto Nagata, Shivam Bhasin, Yves Mathieu, Tarik Graba, Jean-Luc Danger, and Naofumi Homma. Diffusional Side-Channel Leakage From Unrolled Lightweight Block Ciphers: A Case Study of Power Analysis on PRINCE. IEEE Transactions on Information Forensics and Security, 16:1351–1364, 2021. DOI: 10.1109/TIFS.2020.3033441
PDF
History
Submitted: 2024-07-04
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Soichiro Kobayashi, Rei Ueno, Yosuke Todo, and Naofumi Homma, Side-Channel Linearization Attack on Unrolled Trivium Hardware. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/angy11zn4.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.