Improved power analysis attacks on Falcon. (English) Zbl 07774132
Hazay, Carmit (ed.) et al., Advances in cryptology – EUROCRYPT 2023. 42nd annual international conference on the theory and applications of cryptographic techniques, Lyon, France, April 23–27, 2023. Proceedings. Part IV. Cham: Springer. Lect. Notes Comput. Sci. 14007, 565-595 (2023).
Summary: Falcon is one of the three post-quantum signature schemes selected for standardization by NIST. Due to its low bandwidth and high efficiency, Falcon is seen as an attractive option for quantum-safe embedded systems. In this work, we study Falcon’s side-channel resistance by analysing its Gaussian samplers. Our results are mainly twofold.
The first result is an improved key recovery exploiting the leakage within the base sampler investigated by Guerreau et al. (CHES 2022). Instead of resorting to the fourth moment as in former parallelepiped-learning attacks, we work with the second order statistics covariance and use its spectral decomposition to recover the secret information. Our approach substantially reduces the requirement for measurements and computation resources: \(220\,000\) traces is sufficient to recover the secret key of Falcon-512 within half an hour with a probability of \(\approx 25\%\). As a comparison, even with \(10^6\) traces, the former attack still needs about 1000 h hours CPU time of lattice reduction for a full key recovery. In addition, our approach is robust to inaccurate leakage classification, which is another advantage over parallelepiped-learning attacks.
Our second result is a practical power analysis targeting the integer Gaussian sampler of Falcon. The analysis relies on the leakage of random sign flip within the integer Gaussian sampling. This leakage was exposed in 2018 by Kim and Hong, but it is not considered in Falcon’s implementation and unexploited for side-channel analysis until now. We identify the leakage within the reference implementation of Falcon on an ARM Cortex-M4 STM32F407IGT6 microprocessor. We also show that this single bit of leakage is in effect enough for practical key recovery: with \(170\,000\) traces one can fully recover the key of Falcon-512 within half an hour. Furthermore, combining the sign leakage and the aforementioned leakage, one can recover the key with only \(45\,000\) signature measurements in a short time.
As a by-product, we also extend our power analysis to Mitaka which is a recent variant of Falcon. The same leakages exist within the integer Gaussian samplers of Mitaka, and they can also be used to mount key recovery attacks. Nevertheless, the key recovery in Mitaka requires much more traces than it does in Falcon, due to their different lattice Gaussian samplers.
For the entire collection see [Zbl 1525.94004].
The first result is an improved key recovery exploiting the leakage within the base sampler investigated by Guerreau et al. (CHES 2022). Instead of resorting to the fourth moment as in former parallelepiped-learning attacks, we work with the second order statistics covariance and use its spectral decomposition to recover the secret information. Our approach substantially reduces the requirement for measurements and computation resources: \(220\,000\) traces is sufficient to recover the secret key of Falcon-512 within half an hour with a probability of \(\approx 25\%\). As a comparison, even with \(10^6\) traces, the former attack still needs about 1000 h hours CPU time of lattice reduction for a full key recovery. In addition, our approach is robust to inaccurate leakage classification, which is another advantage over parallelepiped-learning attacks.
Our second result is a practical power analysis targeting the integer Gaussian sampler of Falcon. The analysis relies on the leakage of random sign flip within the integer Gaussian sampling. This leakage was exposed in 2018 by Kim and Hong, but it is not considered in Falcon’s implementation and unexploited for side-channel analysis until now. We identify the leakage within the reference implementation of Falcon on an ARM Cortex-M4 STM32F407IGT6 microprocessor. We also show that this single bit of leakage is in effect enough for practical key recovery: with \(170\,000\) traces one can fully recover the key of Falcon-512 within half an hour. Furthermore, combining the sign leakage and the aforementioned leakage, one can recover the key with only \(45\,000\) signature measurements in a short time.
As a by-product, we also extend our power analysis to Mitaka which is a recent variant of Falcon. The same leakages exist within the integer Gaussian samplers of Mitaka, and they can also be used to mount key recovery attacks. Nevertheless, the key recovery in Mitaka requires much more traces than it does in Falcon, due to their different lattice Gaussian samplers.
For the entire collection see [Zbl 1525.94004].
MSC:
| 68P25 | Data encryption (aspects in computer science) |
| 94A60 | Cryptography |
| 81P94 | Quantum cryptography (quantum-theoretic aspects) |
Software:
GALATICSReferences:
| [1] | Barthe, G., Belaïd, S., Espitau, T., Fouque, P.A., Rossi, M., Tibouchi, M.: Galactics: Gaussian sampling for lattice-based constant-time implementation of cryptographic signatures, revisited. In: ACM CCS 2019, pp. 2147-2164 (2019). doi:10.1145/3319535.3363223 |
| [2] | Bootle, J.; Delaplace, C.; Espitau, T.; Fouque, P-A; Tibouchi, M.; Peyrin, T.; Galbraith, S., LWE without modular reduction and improved side-channel attacks against BLISS, Advances in Cryptology - ASIACRYPT 2018, 494-524 (2018), Cham: Springer, Cham · Zbl 1446.94109 · doi:10.1007/978-3-030-03326-2_17 |
| [3] | Chari, S.; Rao, JR; Rohatgi, P.; Kaliski, BS; Koç, K.; Paar, C., Template attacks, Cryptographic Hardware and Embedded Systems - CHES 2002, 13-28 (2003), Heidelberg: Springer, Heidelberg · Zbl 1019.68541 · doi:10.1007/3-540-36400-5_3 |
| [4] | Dachman-Soled, D.; Ducas, L.; Gong, H.; Rossi, M.; Micciancio, D.; Ristenpart, T., LWE with side information: attacks and concrete security estimation, Advances in Cryptology - CRYPTO 2020, 329-358 (2020), Cham: Springer, Cham · Zbl 1504.94128 · doi:10.1007/978-3-030-56880-1_12 |
| [5] | Ducas, L.; Galbraith, S.; Prest, T.; Yu, Y.; Canteaut, A.; Ishai, Y., Integral matrix gram root and lattice gaussian sampling without floats, Advances in Cryptology - EUROCRYPT 2020, 608-637 (2020), Cham: Springer, Cham · Zbl 1492.94092 · doi:10.1007/978-3-030-45724-2_21 |
| [6] | Ducas, L.; Lyubashevsky, V.; Prest, T.; Sarkar, P.; Iwata, T., Efficient identity-based encryption over NTRU lattices, Advances in Cryptology - ASIACRYPT 2014, 22-41 (2014), Heidelberg: Springer, Heidelberg · Zbl 1317.94103 · doi:10.1007/978-3-662-45608-8_2 |
| [7] | Ducas, L.; Nguyen, PQ; Wang, X.; Sako, K., Learning a Zonotope and more: cryptanalysis of ntrusign countermeasures, Advances in Cryptology - ASIACRYPT 2012, 433-450 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94059 · doi:10.1007/978-3-642-34961-4_27 |
| [8] | Ducas, L., Prest, T.: Fast Fourier Orthogonalization. In: ISSAC 2016, pp. 191-198 (2016). doi:10.1145/2930889.2930923 · Zbl 1365.65105 |
| [9] | Ducas, L.; Yu, Y., Learning strikes again: the case of the DRS signature scheme, J. Cryptol., 34, 1, 1-24 (2020) · Zbl 1466.94045 · doi:10.1007/s00145-020-09366-9 |
| [10] | Espitau, T., Fouque, P.A., Gérard, B., Tibouchi, M.: Side-channel attacks on BLISS lattice-based signatures: Exploiting branch tracing against strongswan and electromagnetic emanations in microcontrollers. In: ACM CCS 2017, pp. 1857-1874 (2017). doi:10.1145/3133956.3134028 |
| [11] | Espitau, T., et al.: MITAKA: a simpler, parallelizable, maskable variant of FALCON. In: Eurocrypt 2022 (2022). doi:10.1007/978-3-031-07082-2_9 |
| [12] | Fouque, P.A., Gérard, F., Rossi, M., Yu, Y.: Zalcon: an alternative FPA-free NTRU sampler for Falcon. In: Proceedings of 3rd NIST PQC Workshop, pp. 1-23 (2021) |
| [13] | Fouque, P-A; Kirchner, P.; Tibouchi, M.; Wallet, A.; Yu, Y.; Canteaut, A.; Ishai, Y., Key recovery from gram-schmidt norm leakage in hash-and-sign signatures over NTRU lattices, Advances in Cryptology - EUROCRYPT 2020, 34-63 (2020), Cham: Springer, Cham · Zbl 1479.94319 · doi:10.1007/978-3-030-45727-3_2 |
| [14] | Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC 2008, pp. 197-206 (2008). doi:10.1145/1374376.1374407 · Zbl 1231.68124 |
| [15] | Gérard, F., Rossi, M.: An efficient and provable masked implementation of qtesla. In: CARDIS 2019, pp. 74-91 (2019). doi:10.1007/978-3-030-42068-0_5 |
| [16] | Groot Bruinderink, L., Hülsing, A., Lange, T., Yarom, Y.: Flush, gauss, and reload-a cache attack on the BLISS lattice-based signature scheme. In: CHES 2016, pp. 323-345 (2016). doi:10.1007/978-3-662-53140-2_16 · Zbl 1411.94065 |
| [17] | Guerreau, M., Martinelli, A., Ricosset, T., Rossi, M.: The hidden parallelepiped is back again: power analysis attacks on falcon. IACR Trans. Cryptograp. Hardware Embedded Syst. (2022). doi:10.46586/tches.v2022.i3.141-164 |
| [18] | Howe, J., Prest, T., Ricosset, T., Rossi, M.: Isochronous Gaussian Sampling: From Inception to Implementation. In: PQCrypto 2020, pp. 53-71 (2020). doi:10.1007/978-3-030-44223-1_4 · Zbl 1501.94044 |
| [19] | Hulsing, A., et al.: SPHINCS+: Submission to the NIST’s post-quantum cryptography standardization process (2020). https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/roun.-3-submissions |
| [20] | Karabulut, E., Aysu, A.: Falcon down: breaking falcon post-quantum signature scheme through side-channel attacks. In: DAC 2021, pp. 691-696 (2021). doi:10.1109/DAC18074.2021.9586131 |
| [21] | Kim, S.; Hong, S., Single trace analysis on constant time CDT sampler and its countermeasure, Appl. Sci., 8, 10, 1809 (2018) · doi:10.3390/app8101809 |
| [22] | Klein, P.N.: Finding the closest lattice vector when it’s unusually close. In: SODA 2000, pp. 937-941 (2000) · Zbl 0953.65043 |
| [23] | Lyubashevsky, V.; Matsui, M., Fiat-shamir with aborts: applications to lattice and factoring-based signatures, Advances in Cryptology - ASIACRYPT 2009, 598-616 (2009), Heidelberg: Springer, Heidelberg · Zbl 1267.94125 · doi:10.1007/978-3-642-10366-7_35 |
| [24] | Lyubashevsky, V.; Pointcheval, D.; Johansson, T., Lattice signatures without trapdoors, Advances in Cryptology - EUROCRYPT 2012, 738-755 (2012), Heidelberg: Springer, Heidelberg · Zbl 1295.94111 · doi:10.1007/978-3-642-29011-4_43 |
| [25] | Lyubashevsky, V., et al.: Dilithium: Submission to the NIST’s post-quantum cryptography standardization process (2020). https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions |
| [26] | Mangard, S.; Oswald, E.; Popp, T., Power Analysis Attacks (2007), Boston, MA: Springer, Boston, MA · Zbl 1131.68449 · doi:10.1007/978-0-387-38162-6 |
| [27] | Migliore, V., Gérard, B., Tibouchi, M., Fouque, P.A.: Masking Dilithium. In: ACNS 2019, pp. 344-362 (2019). doi:10.1007/978-3-030-21568-2_17 · Zbl 1458.94307 |
| [28] | Nguyen, PQ; Regev, O.; Vaudenay, S., Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures, Advances in Cryptology - EUROCRYPT 2006, 271-288 (2006), Heidelberg: Springer, Heidelberg · Zbl 1140.94365 · doi:10.1007/11761679_17 |
| [29] | Peikert, C.; Rabin, T., An efficient and parallel gaussian sampler for lattices, Advances in Cryptology - CRYPTO 2010, 80-97 (2010), Heidelberg: Springer, Heidelberg · Zbl 1280.94091 · doi:10.1007/978-3-642-14623-7_5 |
| [30] | Pessl, P., Bruinderink, L.G., Yarom, Y.: To BLISS-B or not to be: attacking strongswan’s implementation of post-quantum signatures. In: ACM CCS 2017, pp. 1843-1855 (2017). doi:10.1145/3133956.3134023 |
| [31] | Pornin, T.: New efficient, constant-time implementations of falcon. Cryptology ePrint Archive, Report 2019/893 (2019). https://ia.cr/2019/893 |
| [32] | Prest, T.: Gaussian Sampling in Lattice-Based Cryptography. Ph.D. thesis, École Normale Supérieure, Paris, France (2015) |
| [33] | Prest, T., et al.: Falcon: Submission to the NIST’s post-quantum cryptography standardization process (2020). https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions |
| [34] | Tibouchi, M.; Wallet, A., One bit is all it takes: a devastating timing attack on BLISS’s non-constant time sign flips, J. Math. Cryptol., 15, 1, 131-142 (2021) · Zbl 1464.94052 · doi:10.1515/jmc-2020-0079 |
| [35] | Vershynin, R.: High-dimensional probability: An introduction with applications in data science, vol. 47. Cambridge University Press (2018). doi:10.1080/14697688.2020.1813475 · Zbl 1430.60005 |
| [36] | Wisiol, N., Gersch, P., Seifert, J.: Cycle-accurate power side-channel analysis using the chipwhisperer: a case study on gaussian sampling. IACR Cryptol. ePrint Arch, p. 903 (2022). https://eprint.iacr.org/2022/903 |
| [37] | Yu, Y.; Ducas, L.; Peyrin, T.; Galbraith, S., Learning strikes again: the case of the DRS signature scheme, Advances in Cryptology - ASIACRYPT 2018, 525-543 (2018), Cham: Springer, Cham · Zbl 1446.94164 · doi:10.1007/978-3-030-03329-3_18 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
