Volume 21, Issue 2 (10-2024)
JSDP 2024, 21(2): 29-42 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Haj-Hosseini Z, Doostari M, Yusefi H. Implementation of a countermeasure method against DPA on McEliece Post Quantum Cryptosystem. JSDP 2024; 21 (2) : 3
URL: http://jsdp.rcisp.ac.ir/article-1-1222-en.html
URL: http://jsdp.rcisp.ac.ir/article-1-1222-en.html
Abstract: (571 Views)
In recent years, embedded systems have continuously gained importance. This ubiquity is accompanied by an increased need for embedded security. Cryptography can address these security requirements. Many symmetric and asymmetric algorithms, such as AES, DES, RSA, ElGamal, and ECC, have been implemented on embedded devices.
All frequently implemented public-key cryptosystems rely on the presumed hardness of either factoring the product of two large primes (FP) or computing discrete logarithms (DLP). These two problems are closely related. Therefore, solving these problems would have significant ramifications for classical public-key cryptography and, consequently, for all embedded devices that utilize these algorithms.
Currently, both problems are believed to be computationally infeasible with a conventional computer. However, a quantum computer capable of performing computations on a few thousand qubits could solve both problems using Shor's algorithm[1]. Although a quantum computer of this scale has not been reported, it could become a reality within the next one to three decades. Consequently, the development and cryptanalysis of alternative post-quantum cryptosystems are crucial. Post-quantum cryptosystems refer to cryptosystems that are not susceptible to the critical security loss or complete compromise caused by quantum computers.
One of the major security challenges is the development of quantum computers and the potential compromise of current cryptosystems in the future. Therefore, it is essential to consider post-quantum cryptosystem algorithms and the challenges of implementing and attacking them. Post-quantum cryptosystems encompass various types, including hash-based cryptography, multivariate-quadratic-equations cryptography, lattice-based cryptography, and code-based cryptography. In this study, our focus is on the QC-MDPC McEliece code-based algorithm. Post-quantum public keys must be designed to gain popularity in practice; they should be optimized for implementation and efficient in execution. McEliece encryption and decryption do not require computationally expensive processing, making it more suitable for implementation[2].
One of the implementation challenges for these algorithms is the large key length, which poses an important issue for implementation on embedded systems. Additionally, countering side-channel attacks caused by information leakage from hardware equipment is crucial. We have addressed this by reducing the key length from 1200 bytes to 180 bytes, providing 80-bit security, and introducing a new method for implementing the QC-MDPC McEliece cryptosystem. Differential power analysis attacks (DPA) exploit the relationship between power consumption and intermediate data to recover the key. In this study, we have used a masking technique for multiplication in the finite field in the syndrome computation part of the decryption algorithm. We have implemented the Threshold Implementation (TI) masking countermeasure for DPA to eliminate information leaks from the previous implementation.
All frequently implemented public-key cryptosystems rely on the presumed hardness of either factoring the product of two large primes (FP) or computing discrete logarithms (DLP). These two problems are closely related. Therefore, solving these problems would have significant ramifications for classical public-key cryptography and, consequently, for all embedded devices that utilize these algorithms.
Currently, both problems are believed to be computationally infeasible with a conventional computer. However, a quantum computer capable of performing computations on a few thousand qubits could solve both problems using Shor's algorithm[1]. Although a quantum computer of this scale has not been reported, it could become a reality within the next one to three decades. Consequently, the development and cryptanalysis of alternative post-quantum cryptosystems are crucial. Post-quantum cryptosystems refer to cryptosystems that are not susceptible to the critical security loss or complete compromise caused by quantum computers.
One of the major security challenges is the development of quantum computers and the potential compromise of current cryptosystems in the future. Therefore, it is essential to consider post-quantum cryptosystem algorithms and the challenges of implementing and attacking them. Post-quantum cryptosystems encompass various types, including hash-based cryptography, multivariate-quadratic-equations cryptography, lattice-based cryptography, and code-based cryptography. In this study, our focus is on the QC-MDPC McEliece code-based algorithm. Post-quantum public keys must be designed to gain popularity in practice; they should be optimized for implementation and efficient in execution. McEliece encryption and decryption do not require computationally expensive processing, making it more suitable for implementation[2].
One of the implementation challenges for these algorithms is the large key length, which poses an important issue for implementation on embedded systems. Additionally, countering side-channel attacks caused by information leakage from hardware equipment is crucial. We have addressed this by reducing the key length from 1200 bytes to 180 bytes, providing 80-bit security, and introducing a new method for implementing the QC-MDPC McEliece cryptosystem. Differential power analysis attacks (DPA) exploit the relationship between power consumption and intermediate data to recover the key. In this study, we have used a masking technique for multiplication in the finite field in the syndrome computation part of the decryption algorithm. We have implemented the Threshold Implementation (TI) masking countermeasure for DPA to eliminate information leaks from the previous implementation.
Article number: 3
Type of Study: Research |
Subject:
Paper
Received: 2021/04/14 | Accepted: 2024/02/25 | Published: 2024/11/4 | ePublished: 2024/11/4
Received: 2021/04/14 | Accepted: 2024/02/25 | Published: 2024/11/4 | ePublished: 2024/11/4
References
1. P. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM Journal on Computing, vol. 26, no. 5, pp. 1484-1509, 1997. [DOI:10.1137/S0097539795293172]
2. S. Heyse, "Post-quantum cryptography: Implementing alternative public key schemes on embedded devices", PhD thesis, Ruhr-University Bochum, 2013.
3. R. McEliece, "A Public-Key Cryptosystem Based On Algebraic Coding Theory", Deep Space Network Progress Report, vol. 44, pp. 114-116, 1978.
4. T. Berson, "Failure of the McEliece public-key cryptosystem under message-resend and related-message attack", Advances in Cryptology - CRYPTO '97, pp. 213-220, 1997. [DOI:10.1007/BFb0052237]
5. R. Misoczki, J. Tillich, N. Sendrier and P. Barreto, "MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes", IEEE International Symposium on Information Theory, 2013. [DOI:10.1109/ISIT.2013.6620590]
6. S. Mangard, E. Oswald and T. Popp, Power analysis attacks: Revealing the secrets of smart cards, Springer US, 2008.
7. حامد یوسفی، محمود گردشی، محمد سبزینژاد، «پیاده سازی حملۀ تحلیل توان ساده به الگوریتم AES روی میکروکنترلر PIC»، پردازش علائم و دادهها، دورة ۹، شمارة ۱، 1391.
8. P. Kocher, J. Jaffe and B. Jun, "Differential Power Analysis", Advances in Cryptology - CRYPTO' 99, pp. 388-397, 1999. [DOI:10.1007/3-540-48405-1_25]
9. E. Brier, C. Clavier and F. Olivier, "Correlation Power Analysis with a Leakage Model", Lecture Notes in Computer Science, pp. 16-29, 2004. [DOI:10.1007/978-3-540-28632-5_2]
10. M. Masoumi and M. Ahmadian, "A practical differential power analysis attack against an FPGA implementation of AES cryptosystem", Ieeexplore.ieee.org, 2010. [Online]. Available: https://ieeexplore.ieee.org/document/6018719. [Accessed: 13- Jan- 2020].
11. P. Kocher, "Design and validation strategies for obtaining assurance in countermeasures to power analysis and related attacks", Proceedings of the NIST Physical Security Workshop, 2005.
12. Y. Ishai, A. Sahai and D. Wagner, "Private Circuits: Securing Hardware against Probing Attacks", Advances in Cryptology - CRYPTO 2003, pp. 463-481, 2003. [DOI:10.1007/978-3-540-45146-4_27]
13. I. von Maurich and T. Güneysu, "Towards Side-Channel Resistant Implementations of QC-MDPC McEliece Encryption on Constrained Devices", Post-Quantum Cryptography, pp. 266-282, 2014. [DOI:10.1007/978-3-319-11659-4_16]
14. C. Chen, T. Eisenbarth, I. von Maurich and R. Steinwandt, "Masking Large Keys in Hardware: A Masked Implementation of McEliece", Lecture Notes in Computer Science, pp. 293-309, 2016. [DOI:10.1007/978-3-319-31301-6_18]
15. C. Chen, T. Eisenbarth, I. von Maurich and R. Steinwandt, "Horizontal and Vertical Side Channel Analysis of a McEliece Cryptosystem", IEEE Transactions on Information Forensics and Security, vol. 11, no. 6, pp. 1093-1105, 2016. [DOI:10.1109/TIFS.2015.2509944]
16. S. Belaïd, F. Benhamouda, A. Passelègue, E. Prouff, A. Thillard and D. Vergnaud, "Private Multiplication over Finite Fields", Advances in Cryptology - CRYPTO 2017, pp. 397-426, [DOI:10.1007/978-3-319-63697-9_14]
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
