Fault-injection attacks against NIST’s post-quantum cryptography round 3 KEM candidates. (English) Zbl 1514.94140
Tibouchi, Mehdi (ed.) et al., Advances in cryptology – ASIACRYPT 2021. 27th international conference on the theory and application of cryptology and information security, Singapore, December 6–10, 2021. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 13091, 33-61 (2021).
Summary: We investigate all NIST PQC Round 3 KEM candidates from the viewpoint of fault-injection attacks: Classic McEliece, Kyber, NTRU, Saber, BIKE, FrodoKEM, HQC, NTRU Prime, and SIKE. All KEM schemes use variants of the Fujisaki-Okamoto transformation, so the equality test with re-encryption in decapsulation is critical.
We survey effective key-recovery attacks when we can skip the equality test. We found the existing key-recovery attacks against Kyber, NTRU, Saber, FrodoKEM, HQC, one of two KEM schemes in NTRU Prime, and SIKE. We propose a new key-recovery attack against the other KEM scheme in NTRU Prime. We also report an attack against BIKE that leads to leakage of information of secret keys.
The open-source pqm4 library contains all KEM schemes except Classic McEliece and HQC. We show that giving a single instruction-skipping fault in the decapsulation processes leads to skipping the equality test virtually for Kyber, NTRU, Saber, BIKE, and SIKE. We also report the experimental attacks against them. We also report the implementation of NTRU Prime allows chosen-ciphertext attacks freely and the timing side-channel of FrodoKEM reported in [Q. Guo et al., Lect. Notes Comput. Sci. 12171, 359–386 (2020; Zbl 1504.94144)] remains, while there are no such bugs in their NIST PQC Round 3 submissions.
For the entire collection see [Zbl 1510.94003].
We survey effective key-recovery attacks when we can skip the equality test. We found the existing key-recovery attacks against Kyber, NTRU, Saber, FrodoKEM, HQC, one of two KEM schemes in NTRU Prime, and SIKE. We propose a new key-recovery attack against the other KEM scheme in NTRU Prime. We also report an attack against BIKE that leads to leakage of information of secret keys.
The open-source pqm4 library contains all KEM schemes except Classic McEliece and HQC. We show that giving a single instruction-skipping fault in the decapsulation processes leads to skipping the equality test virtually for Kyber, NTRU, Saber, BIKE, and SIKE. We also report the experimental attacks against them. We also report the implementation of NTRU Prime allows chosen-ciphertext attacks freely and the timing side-channel of FrodoKEM reported in [Q. Guo et al., Lect. Notes Comput. Sci. 12171, 359–386 (2020; Zbl 1504.94144)] remains, while there are no such bugs in their NIST PQC Round 3 submissions.
For the entire collection see [Zbl 1510.94003].
Keywords:
post-quantum cryptography; NIST PQC standardization; KEM; Fujisaki-Okamoto transformation; fault-injection attacksCitations:
Zbl 1504.94144References:
| [1] | ISO/IEC 18033-2:2006 information technology – security techniques – encryption algorithms – part 2: asymmetric ciphers (2006). https://www.iso.org/standard/37971.html |
| [2] | Abdalla, M.; Benhamouda, F.; Pointcheval, D.; Katz, J., Public-key encryption indistinguishable under plaintext-checkable attacks, Public-Key Cryptography - PKC 2015, 332-352 (2015), Heidelberg: Springer, Heidelberg · Zbl 1345.94027 · doi:10.1007/978-3-662-46447-2_15 |
| [3] | Aggarwal, D.; Maurer, U.; Joux, A., Breaking RSA generically is equivalent to factoring, Advances in Cryptology - EUROCRYPT 2009, 36-53 (2009), Heidelberg: Springer, Heidelberg · Zbl 1239.94031 · doi:10.1007/978-3-642-01001-9_2 |
| [4] | Aguilar Melchor, C., et al.: HQC. Technical report, National Institute of Standards and Technology (2020) |
| [5] | Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: STOC 1997, pp. 284-293. ACM Press, May 1997 · Zbl 0962.68055 |
| [6] | Alagic, G., et al.: NISTIR 8309: status report on the second round of the NIST post-quantum cryptography standardization process, July 2020 |
| [7] | Albrecht, M.R., et al.: Classic McEliece. Technical report, National Institute of Standards and Technology (2020) |
| [8] | Antipa, A.; Brown, D.; Menezes, A.; Struik, R.; Vanstone, S.; Desmedt, YG, Validation of elliptic curve public keys, Public Key Cryptography — PKC 2003, 211-223 (2003), Heidelberg: Springer, Heidelberg · Zbl 1033.94509 · doi:10.1007/3-540-36288-6_16 |
| [9] | Aragon, N., et al.: BIKE. Technical report, National Institute of Standards and Technology (2020) |
| [10] | Băetu, C.; Durak, FB; Huguenin-Dumittan, L.; Talayhan, A.; Vaudenay, S.; Ishai, Y.; Rijmen, V., Misuse attacks on post-quantum cryptosystems, Advances in Cryptology - EUROCRYPT 2019, 747-776 (2019), Cham: Springer, Cham · Zbl 1509.81351 · doi:10.1007/978-3-030-17656-3_26 |
| [11] | Barenghi, A., Bertoni, G., Perrinello, E., Pelosi, G.: Low voltage fault attacks on the RSA cryptosystem. In: FDTC 2009. IEEE Computer Society (2009) |
| [12] | Barenghi, A., Breveglieri, L., Koren, I., Pelosi, G., Regazzoni, F.: Countermeasures against fault attacks on software implemented AES: effectiveness and cost. In: WESS 2010 (2010) |
| [13] | Bellare, M. (ed.): CRYPTO 2000, LNCS, vol. 1880. Springer, Heidelberg, August 2000. doi:10.1007/3-540-44598-6 · Zbl 0944.00095 |
| [14] | Bernstein, D.J., et al.: NTRU Prime. Technical report, National Institute of Standards and Technology (2020) |
| [15] | Biehl, I., Meyer, B., Müller, V.: Differential fault attacks on elliptic curve cryptosystems. In: Bellare [13], pp. 131-146 (2000) · Zbl 0989.94505 |
| [16] | Biham, E.; Shamir, A.; Kaliski, BS, Differential fault analysis of secret key cryptosystems, Advances in Cryptology — CRYPTO ’97, 513-525 (1997), Heidelberg: Springer, Heidelberg · Zbl 0886.94010 · doi:10.1007/BFb0052259 |
| [17] | Bindel, N.; Hamburg, M.; Hövelmanns, K.; Hülsing, A.; Persichetti, E.; Hofheinz, D.; Rosen, A., Tighter proofs of CCA security in the quantum random oracle model, Theory of Cryptography, 61-90 (2019), Cham: Springer, Cham · Zbl 1455.94126 · doi:10.1007/978-3-030-36033-7_3 |
| [18] | Blömer, J., Günther, P.: Singular curve point decompression attack. In: FDTC 2015, pp. 71-84. IEEE Computer Society (2015) |
| [19] | Boneh, D.; Dagdelen, Ö.; Fischlin, M.; Lehmann, A.; Schaffner, C.; Zhandry, M.; Lee, DH; Wang, X., Random oracles in a quantum world, Advances in Cryptology - ASIACRYPT 2011, 41-69 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.94033 · doi:10.1007/978-3-642-25385-0_3 |
| [20] | Boneh, D.; DeMillo, RA; Lipton, RJ, On the importance of eliminating errors in cryptographic computations, J. Cryptol., 14, 2, 101-119 (2001) · Zbl 1018.94014 · doi:10.1007/s001450010016 |
| [21] | Boneh, D.; Venkatesan, R.; Nyberg, K., Breaking RSA may not be equivalent to factoring, Advances in Cryptology — EUROCRYPT’98, 59-71 (1998), Heidelberg: Springer, Heidelberg · Zbl 0922.94008 · doi:10.1007/BFb0054117 |
| [22] | Chen, C., et al.: NTRU. Technical report, National Institute of Standards and Technology (2020) |
| [23] | Cheon, JH; Takagi, T., Advances in Cryptology - ASIACRYPT 2016 (2016), Heidelberg: Springer, Heidelberg · Zbl 1349.94005 · doi:10.1007/978-3-662-53887-6 |
| [24] | Coron, J-S; Kizhvatov, I.; Clavier, C.; Gaj, K., An efficient method for random delay generation in embedded software, Cryptographic Hardware and Embedded Systems - CHES 2009, 156-170 (2009), Heidelberg: Springer, Heidelberg · Zbl 1290.94058 · doi:10.1007/978-3-642-04138-9_12 |
| [25] | Costello, C.: The case for SIKE: a decade of the supersingular isogeny problem. Cryptology ePrint Archive, Report 2021/543 (2021). https://eprint.iacr.org/2021/543 |
| [26] | Cramer, R.; Shoup, V., Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, SIAM J. Comput., 33, 1, 167-226 (2003) · Zbl 1045.94013 · doi:10.1137/S0097539702403773 |
| [27] | D’Anvers, J.P., et al.: SABER. Technical report, National Institute of Standards and Technology (2020) |
| [28] | De Feo, L.; Jao, D.; Plût, J., Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, J. Math. Cryptol., 8, 3, 209-247 (2014) · Zbl 1372.94419 |
| [29] | Dent, AW; Paterson, KG, A designer’s guide to KEMs, Cryptography and Coding, 133-151 (2003), Heidelberg: Springer, Heidelberg · Zbl 1123.94336 · doi:10.1007/978-3-540-40974-8_12 |
| [30] | Diffie, W.; Hellman, ME, New directions in cryptography, IEEE Trans. Inf. Theory, 22, 6, 644-654 (1976) · Zbl 0435.94018 · doi:10.1109/TIT.1976.1055638 |
| [31] | Ding, J., Deaton, J., Schmidt, K., Vishakha, Zhang, Z.: A simple and practical key reuse attack on NTRU cryptosystem. Cryptology ePrint Archive, Report 2019/1022 (2019). https://eprint.iacr.org/2019/1022 |
| [32] | Endo, S.; Homma, N.; Hayashi, Y.; Takahashi, J.; Fuji, H.; Aoki, T.; Prouff, E., A multiple-fault injection attack by adaptive timing control under black-box conditions and a countermeasure, Constructive Side-Channel Analysis and Secure Design, 214-228 (2014), Cham: Springer, Cham · Zbl 1440.94047 · doi:10.1007/978-3-319-10175-0_15 |
| [33] | Endo, S.; Sugawara, T.; Homma, N.; Aoki, T.; Satoh, A., An on-chip glitchy-clock generator for testing fault injection attacks, J. Crypt. Eng., 1, 4, 265-270 (2011) · doi:10.1007/s13389-011-0022-y |
| [34] | Fluhrer, S.: Cryptanalysis of ring-LWE based key exchange with key share reuse. Cryptology ePrint Archive, Report 2016/085 (2016). https://eprint.iacr.org/2016/085 |
| [35] | Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener [78], pp. 537-554 (1999) · Zbl 0942.94019 |
| [36] | Fujisaki, E.; Okamoto, T., Secure integration of asymmetric and symmetric encryption schemes, J. Cryptol., 26, 1, 80-101 (2013) · Zbl 1291.94085 · doi:10.1007/s00145-011-9114-1 |
| [37] | Galbraith, S.D., Petit, C., Shani, B., Ti, Y.B.: On the security of supersingular isogeny cryptosystems. In: Cheon and Takagi [23], pp. 63-91 (2016) · Zbl 1404.94073 |
| [38] | Guo, Q.; Johansson, T.; Nilsson, A.; Micciancio, D.; Ristenpart, T., A key-recovery timing attack on post-quantum primitives using the Fujisaki-Okamoto transformation and its application on FrodoKEM, Advances in Cryptology - CRYPTO 2020, 359-386 (2020), Cham: Springer, Cham · Zbl 1504.94144 · doi:10.1007/978-3-030-56880-1_13 |
| [39] | Guo, Q., Johansson, T., Stankovski, P.: A key recovery attack on MDPC with CCA security using decoding errors. In: Cheon and Takagi [23], pp. 789-815 (2016) · Zbl 1404.94079 |
| [40] | Hall, C.; Goldberg, I.; Schneier, B.; Varadharajan, V.; Mu, Y., Reaction attacks against several public-key cryptosystem, Information and Communication Security, 2-12 (1999), Heidelberg: Springer, Heidelberg · Zbl 0981.94027 · doi:10.1007/978-3-540-47942-0_2 |
| [41] | Hayashi, Y., Homma, N., Sugawara, T., Mizuki, T., Aoki, T., Sone, H.: Non-invasive trigger-free fault injection method based on intentional electromagnetic interference. In: Proceedings of The Non-Invasive Attack Testing Workshop - NIAT 2011, September 2011 |
| [42] | Hofheinz, D.; Hövelmanns, K.; Kiltz, E.; Kalai, Y.; Reyzin, L., A modular analysis of the Fujisaki-Okamoto transformation, Theory of Cryptography, 341-371 (2017), Cham: Springer, Cham · Zbl 1410.94082 · doi:10.1007/978-3-319-70500-2_12 |
| [43] | Howe, J.; Prest, T.; Apon, D.; Paterson, KG, SoK: how (not) to design and implement post-quantum cryptography, Topics in Cryptology - CT-RSA 2021, 444-477 (2021), Cham: Springer, Cham · Zbl 1479.94189 · doi:10.1007/978-3-030-75539-3_19 |
| [44] | Huguenin-Dumittan, L.; Vaudenay, S.; Conti, M.; Zhou, J.; Casalicchio, E.; Spognardi, A., Classical misuse attacks on NIST round 2 PQC, Applied Cryptography and Network Security, 208-227 (2020), Cham: Springer, Cham · Zbl 07314284 · doi:10.1007/978-3-030-57808-4_11 |
| [45] | Jao, D., et al.: SIKE. Technical report, National Institute of Standards and Technology (2020) |
| [46] | Jao, D.; De Feo, L.; Yang, B-Y, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, Post-Quantum Cryptography, 19-34 (2011), Heidelberg: Springer, Heidelberg · Zbl 1290.94094 · doi:10.1007/978-3-642-25405-5_2 |
| [47] | Jiang, H.; Zhang, Z.; Chen, L.; Wang, H.; Ma, Z.; Shacham, H.; Boldyreva, A., IND-CCA-Secure key encapsulation mechanism in the quantum random oracle model, revisited, Advances in Cryptology - CRYPTO 2018, 96-125 (2018), Cham: Springer, Cham · Zbl 1457.94142 · doi:10.1007/978-3-319-96878-0_4 |
| [48] | Jiang, H.; Zhang, Z.; Ma, Z.; Lin, D.; Sako, K., Key encapsulation mechanism with explicit rejection in the quantum random oracle model, Public-Key Cryptography - PKC 2019, 618-645 (2019), Cham: Springer, Cham · Zbl 1509.81381 · doi:10.1007/978-3-030-17259-6_21 |
| [49] | Kannwischer, M.J., Rijneveld, J., Schwabe, P., Stoffelen, K.: pqm4: post-quantum crypto library for the ARM Cortex-M4 (2021). https://github.com/mupq/pqm4 |
| [50] | Kocher, PC; Koblitz, N., Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems, Advances in Cryptology — CRYPTO ’96, 104-113 (1996), Heidelberg: Springer, Heidelberg · Zbl 1329.94070 · doi:10.1007/3-540-68697-5_9 |
| [51] | Kocher, P.C., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener [78], pp. 388-397 (1999) · Zbl 0942.94501 |
| [52] | Kuchta, V.; Sakzad, A.; Stehlé, D.; Steinfeld, R.; Sun, S-F; Canteaut, A.; Ishai, Y., Measure-rewind-measure: tighter quantum random oracle model proofs for one-way to hiding and CCA security, Advances in Cryptology - EUROCRYPT 2020, 703-728 (2020), Cham: Springer, Cham · Zbl 1479.94202 · doi:10.1007/978-3-030-45727-3_24 |
| [53] | Lindner, R.; Peikert, C.; Kiayias, A., Better key sizes (and attacks) for LWE-based encryption, Topics in Cryptology - CT-RSA 2011, 319-339 (2011), Heidelberg: Springer, Heidelberg · Zbl 1284.94088 · doi:10.1007/978-3-642-19074-2_21 |
| [54] | Lyubashevsky, V.; Peikert, C.; Regev, O.; Gilbert, H., On ideal lattices and learning with errors over rings, Advances in Cryptology - EUROCRYPT 2010, 1-23 (2010), Heidelberg: Springer, Heidelberg · Zbl 1279.94099 · doi:10.1007/978-3-642-13190-5_1 |
| [55] | McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. The deep space network progress report 42-44, Jet Propulsion Laboratory, California Institute of Technology, January/February 1978. https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF |
| [56] | Misoczki, R., Tillich, J., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: new McEliece variants from moderate density parity-check codes. In: ISIT 2013, pp. 2069-2073. IEEE (2013) |
| [57] | Naehrig, M., et al.: FrodoKEM. Technical report, National Institute of Standards and Technology (2020) |
| [58] | Niederreiter, H., Knapsack-type cryptosystems and algebraic coding theory, Prob. Control Inf. Theory, 15, 2, 159-166 (1986) · Zbl 0611.94007 |
| [59] | Okamoto, T.; Pointcheval, D.; Naccache, D., REACT: rapid enhanced-security asymmetric cryptosystem transform, Topics in Cryptology — CT-RSA 2001, 159-174 (2000), Heidelberg: Springer, Heidelberg · Zbl 0991.94046 · doi:10.1007/3-540-45353-9_13 |
| [60] | Pessl, P., Prokop, L.: Fault attacks on CCA-secure lattice KEMs. IACR TCHES 2021(2), 37-60 (2021). https://tches.iacr.org/index.php/TCHES/article/view/8787 |
| [61] | Qin, Y., Cheng, C., Ding, J.: An efficient key mismatch attack on the NIST second round candidate Kyber. Cryptology ePrint Archive, Report 2019/1343 (2019). https://eprint.iacr.org/2019/1343 |
| [62] | Qin, Y., Cheng, C., Zhang, X., Pan, Y., Hu, L., Ding, J.: A systematic approach and analysis of key mismatch attacks on CPA-secure lattice-based NIST candidate KEMs. Cryptology ePrint Archive, Report 2021/123 (2021). https://eprint.iacr.org/2021/123 |
| [63] | Rackoff, C.; Simon, DR; Feigenbaum, J., Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack, Advances in Cryptology — CRYPTO ’91, 433-444 (1992), Heidelberg: Springer, Heidelberg · Zbl 0767.94006 · doi:10.1007/3-540-46766-1_35 |
| [64] | Ravi, P., Ezerman, M.F., Bhasin, S., Chattopadhyay, A., Roy, S.S.: Will you cross the threshold for me? - Generic side-channel assisted chosen-ciphertext attacks on NTRU-based KEMs. Cryptology ePrint Archive, Report 2021/718 (2021). https://eprint.iacr.org/2021/718 |
| [65] | Ravi, P., Roy, S.S.: Side-channel analysis of lattice-based PQC candidates. NIST PQC Round 3 Seminars (2021). https://csrc.nist.gov/projects/post-quantum-cryptography/workshops-and-timeline/round-3-seminars |
| [66] | Ravi, P., Roy, S.S., Chattopadhyay, A., Bhasin, S.: Generic side-channel attacks on CCA-secure lattice-based PKE and KEMs. IACR TCHES 2020(3), 307-335 (2020). https://tches.iacr.org/index.php/TCHES/article/view/8592 |
| [67] | Rivest, RL; Shamir, A.; Adleman, LM, A method for obtaining digital signatures and public-key cryptosystems, Commun. Assoc. Comput. Mach., 21, 2, 120-126 (1978) · Zbl 0368.94005 |
| [68] | Saha, D., Mukhopadhyay, D., RoyChowdhury, D.: A diagonal fault attack on the advanced encryption standard. Cryptology ePrint Archive, Report 2009/581 (2009). https://eprint.iacr.org/2009/581 |
| [69] | Saito, T.; Xagawa, K.; Yamakawa, T.; Nielsen, JB; Rijmen, V., Tightly-secure key-encapsulation mechanism in the quantum random oracle model, Advances in Cryptology - EUROCRYPT 2018, 520-551 (2018), Cham: Springer, Cham · Zbl 1415.94459 · doi:10.1007/978-3-319-78372-7_17 |
| [70] | Schwabe, P., et al.: CRYSTALS-KYBER. Technical report, National Institute of Standards and Technology (2020) |
| [71] | Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th FOCS, pp. 124-134. IEEE Computer Society Press, November 1994 |
| [72] | Shoup, V.; Preneel, B., Using hash functions as a hedge against chosen ciphertext attack, Advances in Cryptology — EUROCRYPT 2000, 275-288 (2000), Heidelberg: Springer, Heidelberg · Zbl 1082.94530 · doi:10.1007/3-540-45539-6_19 |
| [73] | Singh, S.: The Code Book. Fourth Estate (1999) |
| [74] | Skorobogatov, SP; Anderson, RJ; Kaliski, BS; Koç, K.; Paar, C., Optical fault induction attacks, Cryptographic Hardware and Embedded Systems - CHES 2002, 2-12 (2003), Heidelberg: Springer, Heidelberg · Zbl 1019.68581 · doi:10.1007/3-540-36400-5_2 |
| [75] | Takahashi, A., Tibouchi, M.: Degenerate fault attacks on elliptic curve parameters in openssl. In: Euro S&P 2019, pp. 371-386. IEEE (2019) |
| [76] | Targhi, EE; Unruh, D.; Hirt, M.; Smith, A., Post-quantum security of the Fujisaki-Okamoto and OAEP transforms, Theory of Cryptography, 192-216 (2016), Heidelberg: Springer, Heidelberg · Zbl 1397.94103 · doi:10.1007/978-3-662-53644-5_8 |
| [77] | Vacek, J.; Václavek, J.; Hong, D., Key mismatch attack on ThreeBears, Frodo and Round5, Information Security and Cryptology - ICISC 2020, 182-198 (2021), Cham: Springer, Cham · Zbl 07497446 · doi:10.1007/978-3-030-68890-5_10 |
| [78] | Wiener, M., Advances in Cryptology — CRYPTO’ 99 (1999), Heidelberg: Springer, Heidelberg · Zbl 0921.00042 · doi:10.1007/3-540-48405-1 |
| [79] | Yen, SM; Joye, M., Checking before output may not be enough against fault-based cryptanalysis, IEEE Trans. Comput., 49, 9, 967-970 (2000) · Zbl 1300.94101 · doi:10.1109/12.869328 |
| [80] | Sung-Ming, Y.; Kim, S.; Lim, S.; Moon, S.; Kim, K., A countermeasure against one physical cryptanalysis may benefit another attack, Information Security and Cryptology — ICISC 2001, 414-427 (2002), Heidelberg: Springer, Heidelberg · Zbl 0999.94540 · doi:10.1007/3-540-45861-1_31 |
| [81] | Zhang, X., Cheng, C., Qin, Y., Ding, R.: Small leaks sink a great ship: an evaluation of key reuse resilience of PQC third round finalist NTRU-HRSS. Cryptology ePrint Archive, Report 2021/168 (2021). https://eprint.iacr.org/2021/168. To appear in ICICS 2021 · Zbl 1501.94061 |
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.
