Top

Published in:

2020 | OriginalPaper | Chapter

Key Recovery Under Plaintext Checking Attack on LAC

Authors : Ke Wang, Zhenfeng Zhang, Haodong Jiang

Published in: Provable and Practical Security

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The National Institute of Standards and Technology (NIST) is working on the standardization of post-quantum algorithms. In February 2019, NIST announced 26 candidate post-quantum cryptosystems had entered the Round 2. Prior work has shown how to mount key recovery attacks on several candidates like FrodoKEM, NewHope, and Kyber, but their methods do not work for LAC, which uses a different encoding scheme and rounding method. To address this gap, we describe a powerful new attack on LAC. In particular, we propose a simple and effective method to recover the reused secret key of LAC.CPA. Following the method we show that, using the recommended parameters, thousands of queries are sufficient to recover the full secret key with a 100% probability, which is verified by experiments. Since LAC.KE is based on LAC.CPA, our method can be used to assess the key-reuse resilience of LAC.KE. In particular, if Alice reuses a secret key, Bob can recover it by communicating with Alice thousands of times. Since LAC is a Round 2 candidate in the NIST PQ process, the presented result may well have a high impact on the understanding of this important cryptosystem.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Optimal Threshold Changeable Secret Sharing with New Threshold Change Range

next chapter Security of Two NIST Candidates in the Presence of Randomness Reuse

Available only for authorised users

B\(\breve{\text {a}}\)etu et al. also recovered the reused secret keys of the other 8 IND-CPA PKEs, but these schemes did not advance to the second round.

In implementation of LAC, in order to minimize the size of the ciphertext, the lower 4 bits for each coefficient in \(\mathbf{v} \) are discarded, and each coefficient is enlarged by shifting 4 bits to the left when decrypting.

In the paper, they recovered the reused secret key of NewHope-CPA-KEM by querying a key mismatch oracle, which can be regarded as an adaptive variant of the plaintext checking oracle in KEM or key exchange.

In the paper, they proposed an efficient key mismatch attack on Kyber.CCAKEM. However, they replaced oracle \(\mathcal {O}\) with oracle \(\mathcal {O}_m\) in the attack, where these two oracles are not equivalent. In fact, they presented a new method to recover the reused secret key of Kyber.CPAPKE.

ECCEnc(m) is chosen to be \(0^{l_v}\) for ease of explanation. In fact, it’s ok to randomly choose m and generate ECCEnc(m), which will be explained further later.

Recall that in KR-PCA game, when querying the oracle PCO, the oracle return \(1_{m'=m}\) or \(0_{m'\ne m}\).

In LAC.KE, shared secret is usually used to generate symmetric keys that Alice and Bob would use to communicate. Bob can generate his symmetric keys based on his shared secret K; if Alice is able to decrypt (and respond) based on those keys, then (with high probability) Bob’s shared key K matches Alice’s shared key \(K'\); if Alice rejects, then Bob’s shared key K mismatches Alice’s shared key \(K'\), which is why the attack is called key mismatch attack [2, 12, 18].

Fluhrer, S.R.: Cryptanalysis of ring-LWE based key exchange with key share reuse. IACR Cryptol. ePrint Arch. 2016, 85 (2016)

Qin, Y., Cheng, C., Ding, J.: A complete and optimized key mismatch attack on NIST candidate NewHope. In: Sako, K., Schneider, S., Ryan, P.Y.A. (eds.) ESORICS 2019. LNCS, vol. 11736, pp. 504–520. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-29962-0_24CrossRef

Ding, J., Fluhrer, S., Rv, S.: Complete attack on RLWE key exchange with reused keys, without signal leakage. In: Susilo, W., Yang, G. (eds.) ACISP 2018. LNCS, vol. 10946, pp. 467–486. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93638-3_27CrossRef

Ding, J., Alsayigh, S., Saraswathy, R.V., et al.: Leakage of signal function with reused keys in RLWE key exchange. In: 2017 IEEE International Conference on Communications (ICC), pp. 1–6. IEEE (2017)

Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134. IEEE (1994)

Băetu, C., Durak, F.B., Huguenin-Dumittan, L., Talayhan, A., Vaudenay, S.: Misuse attacks on post-quantum cryptosystems. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 747–776. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_26CrossRef

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_1CrossRef

Micciancio, D.: Lattice-based cryptography. In: Tilborg, H.C.V., Jajodia, S. (eds.) Encyclopedia of Cryptography and Security, pp. 713–715. Springer, Boston (2011). https://doi.org/10.1007/978-3-540-88702-7_5CrossRef

Regev, O.: Lattice-based cryptography. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 131–141. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_8CrossRef

10.

Ding, J., Xie, X., Lin, X.: A simple provably secure key exchange scheme based on the learning with errors problem. IACR Cryptol. EPrint Arch. 2012, 688 (2012)

11.

Bos, J., Ducas, L., Kiltz, E., et al.: CRYSTALS-Kyber: a CCA-secure module-lattice-based KEM. In: IEEE European Symposium on Security and Privacy (EuroS&P), pp. 353–367. IEEE (2018)

12.

Bauer, A., Gilbert, H., Renault, G., Rossi, M.: Assessment of the Key-Reuse Resilience of NewHope. In: Matsui, M. (ed.) CT-RSA 2019. LNCS, vol. 11405, pp. 272–292. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12612-4_14CrossRef

13.

Langlois, A., Stehlé, D.: Worst-case to average-case reductions for module lattices. Des. Codes Crypt. 75(3), 565–599 (2014). https://doi.org/10.1007/s10623-014-9938-4MathSciNetCrossRefMATH

14.

National institute of standards and technology: post-quantum cryptography round 1 submissions (2018). https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions

15.

National institute of standards and technology: post-quantum cryptography round 2 submissions (2018). https://csrc.nist.gov/Projects/post-quantum-cryptography/round-2-submissions

16.

Guo, Q., Johansson, T., Yang, J.: A novel CCA attack using decryption errors against LAC. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 82–111. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34578-5_4CrossRef

17.

Kirkwood, D., Lackey, B.C., McVey, J., et al.: Failure is not an option: standardization issues for post-quantum key agreement. Talk at NIST workshop on cybersecurity in a post-quantum world (2015). http://www.nist.gov/itl/csd/ct/post-quantum-crypto-workshop-2015.cfm

18.

Qin, Y., Cheng, C., Ding, J.: An efficient key mismatch attack on the NIST second round candidate Kyber. IACR Cryptol. ePrint Arch. 2019, 1343 (2019)

19.

Saarinen, M.-J.O.: HILA5: on reliability, reconciliation, and error correction for ring-LWE encryption. In: Adams, C., Camenisch, J. (eds.) SAC 2017. LNCS, vol. 10719, pp. 192–212. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-72565-9_10CrossRef

20.

Alkim, E., et al.: NewHope: algorithm specifcations and supporting documentation (2017). https://newhopecrypto.org/data/NewHope2018_12_02.pdf

21.

Gao, X., Ding, J., Li, L., et al.: Practical randomized RLWE-based key exchange against signal leakage attack. IEEE Trans. Comput. 1, 1–1 (2018)MathSciNetMATH

22.

Liu, C., Zheng, Z., Zou, G.: Key reuse attack on NewHope key exchange protocol. In: Lee, K. (ed.) ICISC 2018. LNCS, vol. 11396, pp. 163–176. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12146-4_11CrossRef

23.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM (JACM) 56(6), 34 (2009)MathSciNetCrossRef

24.

Bernstein, D.J., Groot Bruinderink, L., Lange, T., Panny, L.: HILA5 Pindakaas: on the CCA security of lattice-based encryption with error correction. In: Joux, A., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT 2018. LNCS, vol. 10831, pp. 203–216. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89339-6_12CrossRef

25.

Alkim, E., Ducas, L., P\(\rm \ddot{o}\)ppelmann, T., et al.: Post-quantum key exchange-a new hope. In: USENIX Security Symposium (2016)

26.

Bernstein, D.J.: Introduction to post-quantum cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 1–14. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-88702-7_1CrossRefMATH

27.

National institute of standards and technology: announcing request for nominations for public-key post-quantum cryptographic algorithms (2016). https://csrc:nist:gov/news/2016/public-key-post-quantum-cryptographic-algorithms

28.

Buchmann, J., Ding J.: PQCrypto, Post-quantum cryptography. In: Second International Workshop, pp. 17–19 (2008)

29.

Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions and lattices. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 719–737. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_42CrossRef

30.

Wang, K., Jiang, H.: Analysis of two countermeasures against the signal leakage attack. In: Buchmann, J., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT 2019. LNCS, vol. 11627, pp. 370–388. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-23696-0_19CrossRef

31.

D’Anvers, J.-P., Guo, Q., Johansson, T., Nilsson, A., Vercauteren, F., Verbauwhede, I.: Decryption failure attacks on IND-CCA secure lattice-based schemes. In: Lin, D., Sako, K. (eds.) PKC 2019. LNCS, vol. 11443, pp. 565–598. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17259-6_19

32.

Hall, C., Goldberg, I., Schneier, B.: Reaction attacks against several public-key cryptosystem. In: Varadharajan, V., Mu, Y. (eds.) ICICS 1999. LNCS, vol. 1726, pp. 2–12. Springer, Heidelberg (1999). https://doi.org/10.1007/978-3-540-47942-0_2CrossRef

33.

Verheul, E.R., Doumen, J.M., van Tilborg, H.C.A.: Sloppy Alice attacks! Adaptive chosen ciphertext attacks on the McEliece public-key cryptosystem. In: Blaum, M., Farrell, P.G., van Tilborg, H.C.A. (eds.) Information, Coding and Mathematics, pp. 99–119. Springer, Boston (2002). https://doi.org/10.1007/978-1-4757-3585-7_7CrossRef

34.

D’Anvers, J.-P., Vercauteren, F., Verbauwhede, I.: The impact of error dependencies on ring/Mod-LWE/LWR based schemes. In: Ding, J., Steinwandt, R. (eds.) PQCrypto 2019. LNCS, vol. 11505, pp. 103–115. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25510-7_6CrossRef

35.

Ding, J., Cheng, C., Qin, Y.: A simple key reuse attack on LWE and ring LWE encryption schemes as key encapsulation mechanisms (KEMs). IACR Cryptol. ePrint Arch. 2019, 271 (2019)

36.

Greuet, A., Montoya, S., Renault, G.: Attack on LAC key exchange in misuse situation. IACR Cryptol. ePrint Arch. 2020, 063 (2020)

37.

Dumittan, L.H., Vaudenay, S.: Classical misuse attacks on NIST round 2 PQC: the power of rank-based schemes. IACR Cryptol. ePrint Arch. 2020, 409 (2020)

38.

Okada, S., Wang, Y., Takagi, T.: Improving key mismatch attack on NewHope with fewer queries. IACR Cryptol. ePrint Arch. 2020, 585 (2020)

Title: Key Recovery Under Plaintext Checking Attack on LAC
Authors: Ke Wang
Zhenfeng Zhang
Haodong Jiang
Publisher: Springer International Publishing
Book: Provable and Practical Security
Print ISBN: 978-3-030-62575-7

Electronic ISBN: 978-3-030-62576-4

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-62576-4_19

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner