Abstract
Cumulative Distribution Table (CDT) sampling is a Gaussian sampling technique commonly used for extracting secret coefficients or core matrix values in lattice-based Post-Quantum Cryptography (PQC) algorithms like FrodoKEM and FALCON. This paper introduces a novel approach: a single trace analysis (STA) method for comparison operation based constant-time CDT sampling, as employed in SOLMAE—a candidate for Korean Post-Quantum Cryptography (KPQC) first-round digital signature Algorithm. The experiment is measuring power consumption during the execution of SOLMAE’s sampling operation on an 8-bit AVR compiler microcontrollers unit (MCU) using ChipWhisperer-Lite. By utilizing STA, this paper recovered output of comparison operation based constant-time CDT sampling. The source of CDT sampling leakage is investigated through an in-depth analysis of the assembly code. The 8-bit AVR MCU conducts comparison operations on values exceeding 8 bits by dividing them into 8-bit blocks. Consequently, the execution time of a CDT sampling operation is influenced by the outcome of each block’s comparison operation due to conditional branching. To address these concerns, this paper begins by summarizing trends in CDT sampling related research to design robust countermeasures against single trace analysis. Furthermore, a novel implementation method for comparison operation based constant-time CDT sampling against STA is proposed. This assembly-level implementation removes branching statements and performs comparative operations on all data words. Through experimental validation, this paper demonstrates the safety of the proposed countermeasure algorithm against STA.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)
Mosca, M.: Cybersecurity in an era with quantum computers: will we be ready? IEEE Secur. Priv. 16(5), 38–41 (2018)
Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_9
Kim, S., Hong, S.: Single trace analysis on constant time CDT sampler and its countermeasure. Appl. Sci. 8(10), 1809 (2018)
Marzougui, S., Kabin, I., Krämer, J., Aulbach, T., Seifert, J.-P.: On the feasibility of single-trace attacks on the gaussian sampler using a CDT. In: Kavun, E.B., Pehl, M. (eds.) COSADE 2023. LNCS, vol. 13979, pp. 149–169. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-29497-6_8
Espitau, T., et al.: Mitaka: a simpler, parallelizable, maskable variant of falcon. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13277, pp. 222–253. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-07082-2_9
Kim, K., et al.: Solmae algorithm specifications (2020). https://kpqc.or.kr/1
Regev, O.: Lecture notes of lattices in computer science, taught at the computer science Tel Aviv university (2009)
Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 284–293 (1997)
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054868
Fouque, P.-A., et al.: Falcon: fast-fourier lattice-based compact signatures over NTRU. Submission to the NIST’s Post-quantum Cryptography Standardization Process, vol. 36, no. 5, pp. 1–75 (2018)
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM (JACM) 56(6), 1–40 (2009)
Bai, S., et al.: Crystals-dilithium: algorithm specifications and supporting documentation (2020)
Avanzi, R., et al.: Crystals-kyber algorithm specifications and supporting documentation. NIST PQC Round 2(4), 1–43 (2019)
Bos, J., et al.: Frodo: take off the ring! practical, quantum-secure key exchange from LWE. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 1006–1018 (2016)
Cheon, J.H., Kim, D., Lee, J., Song, Y.: Lizard: cut off the tail! a practical post-quantum public-key encryption from LWE and LWR. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 160–177. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_9
Howe, J., Prest, T., Ricosset, T., Rossi, M.: Isochronous gaussian sampling: from inception to implementation: With applications to the falcon signature scheme. In: Ding, J., Tillich, J.P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 53–71. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_4
Schneider, T., Paglialonga, C., Oder, T., Güneysu, T.: Efficiently masking binomial sampling at arbitrary orders for lattice-based crypto. In: Lin, D., Sako, K. (eds.) PKC 2019, Part II. LNCS, vol. 11443, pp. 534–564. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17259-6_18
Knuth, D.E.: Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley Professional, Boston (2014)
Fisher, R.A., Yates, F.: Statistical tables for biological, agricultural and medical research. Hafner Publishing Company (1953)
Ngo, K., Dubrova, E., Guo, Q., Johansson, T.: A side-channel attack on a masked IND-CCA secure saber KEM implementation. IACR Trans. Cryptogr. Hardw. Embed. Syst. 676–707 (2021)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Choi, KH., Kim, JH., Han, J., Huh, JW., Han, DG. (2024). Single Trace Analysis of Comparison Operation Based Constant-Time CDT Sampling and Its Countermeasure. In: Seo, H., Kim, S. (eds) Information Security and Cryptology – ICISC 2023. ICISC 2023. Lecture Notes in Computer Science, vol 14561. Springer, Singapore. https://doi.org/10.1007/978-981-97-1235-9_10
Download citation
DOI: https://doi.org/10.1007/978-981-97-1235-9_10
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-1234-2
Online ISBN: 978-981-97-1235-9
eBook Packages: Computer ScienceComputer Science (R0)