Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 13554))
Included in the following conference series:
2758Accesses
Abstract
Key exchange protocols from the learning with errors (LWE) problem share many similarities with the Diffie-Hellman-Merkle (DHM) protocol, which plays a central role in securing our Internet. Therefore, there has been a long time effort in designing authenticated key exchange directly from LWE to mirror the advantages of DHM-based protocols. In this paper, we revisit signal leakage attacks and show that the severity of these attacks against LWE-based (authenticated) key exchange is still underestimated.
In particular, by converting the problem of launching a signal leakage attack into a coding problem, we can significantly reduce the needed number of queries to reveal the secret key. Specifically, for DXL-KE we reduce the queries from 1,266 to only 29, while for DBS-KE, we need only 748 queries, a great improvement over the previous 1,074,434 queries. Moreover, our new view of signals as binary codes enables recognizing vulnerable schemes more easily. As such we completely recover the secret key of a password-based authenticated key exchange scheme by Dabra et al. with only 757 queries and partially reveal the secret used in a two-factor authentication by Wang et al. with only one query. The experimental evaluation supports our theoretical analysis and demonstrates the efficiency and effectiveness of our attacks. Our results caution against underestimating the power of signal leakage attacks as they are applicable even in settings with a very restricted number of interactions between adversary and victim.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 9723
- Price includes VAT (Japan)
- Softcover Book
- JPY 12154
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
It is important to point out that these attacks are against candidates designed to resist passive adversaries. Hence, security claims are not invalidated by these attacks.
- 2.
Interestingly, assigning corresponding binary values as codewords fails because we fail to find suitable values in the next step.
- 3.
Other values than 1260 are possible but at this time, our attack needs\({\textbf {P}}_A\) to be a constant polynomial.
References
Abdalla, M., Fouque, P.-A., Pointcheval, D.: Password-based authenticated key exchange in the three-party setting. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 65–84. Springer, Heidelberg (2005).https://doi.org/10.1007/978-3-540-30580-4_6
Akleylek, S., Seyhan, K.: A probably secure bi-gisis based modified AKE scheme with reusable keys. IEEE Access8, 26210–26222 (2020)
Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: NewHope without reconciliation. Cryptology ePrint Archive, Report 2016/1157 (2016)
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_26
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_14
Bellare, M., Rogaway, P.: Entity authentication and key distribution. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 232–249. Springer, Heidelberg (1994).https://doi.org/10.1007/3-540-48329-2_21
Bindel, N., Stebila, D., Veitch, S.: Improved attacks against key reuse in learning with errors key exchange. In: Longa, P., Ràfols, C. (eds.) LATINCRYPT 2021. LNCS, vol. 12912, pp. 168–188. Springer, Cham (2021).https://doi.org/10.1007/978-3-030-88238-9_9
Bleichenbacher, D.: Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 1–12. Springer, Heidelberg (1998).https://doi.org/10.1007/BFb0055716
Bos, J.W., Costello, C., Naehrig, M., Stebila, D.: Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In: S &P 2015, pp. 553–570. IEEE (2015)
Brendel, J., Fiedler, R., Günther, F., Janson, C., Stebila, D.: Post-quantum Asynchronous Deniable Key Exchange and the Signal Handshake. Cryptology ePrint Archive, Report 2021/769 (2021)
Canetti, R., Krawczyk, H.: Analysis of key-exchange protocols and their use for building secure channels. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 453–474. Springer, Heidelberg (2001).https://doi.org/10.1007/3-540-44987-6_28
Chang, S.H., Cosman, P.C., Milstein, L.B.: Chernoff-type bounds for the Gaussian error function. IEEE Trans. Commun.59(11), 2939–2944 (2011)
Dabra, V., Bala, A., Kumari, S.: LBA-PAKE: lattice-based anonymous password authenticated key exchange for mobile devices. IEEE Syst. J.15(4), 5067–5077 (2021)
Debris-Alazard, T., Ducas, L., van Woerden, W.P.: An algorithmic reduction theory for binary codes: Lll and more. Cryptology ePrint Archive, Report 2020/869 (2020).https://ia.cr/2020/869
Diffie, W., Hellman, M.: New directions in cryptography. IEEE Trans. Inf. Theory22(6), 644–654 (1976)
Ding, J., Alsayigh, S., Saraswathy, R., Fluhrer, S., Lin, X.: Leakage of signal function with reused keys in RLWE key exchange. In: ICC 2017, pp. 1–6. IEEE (2017)
Ding, J., Branco, P., Schmitt, K.: Key exchange and authenticated key exchange with reusable keys based on RLWE assumption. Cryptology ePrint Archive, Report 2019/665 (2019)
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_27
Ding, J., Xie, X., Lin, X.: A Simple provably secure key exchange scheme based on the learning with errors problem. Cryptology ePrint Archive, Report 2019/688 (2012)
Fluhrer, S.R.: Cryptanalysis of ring-LWE based key exchange with key share reuse. Cryptology ePrint Archive, Report 2016/085 (2016)
Greuet, A., Montoya, S., Renault, G.: Attack on LAC key exchange in misuse situation. Cryptology ePrint Archive, Report 2020/063 (2020)
Günther, F., Towa, P.: KEMTLS with delayed forward identity protection in (almost) a single round trip. Cryptology ePrint Archive, Report 2021/725 (2021)
Hashimoto, K., Katsumata, S., Kwiatkowski, K., Prest, T.: An efficient and generic construction for signal’s handshake (X3DH): post-quantum, state leakage secure, and deniable. Cryptology ePrint Archive, Report 2021/616 (2021)
Huguenin-Dumittan, L., Vaudenay, S.: Classical misuse attacks on NIST round 2 PQC. In: Conti, M., Zhou, J., Casalicchio, E., Spognardi, A. (eds.) ACNS 2020. LNCS, vol. 12146, pp. 208–227. Springer, Cham (2020).https://doi.org/10.1007/978-3-030-57808-4_11
Krawczyk, H.: HMQV: a high-performance secure Diffie-Hellman protocol. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 546–566. Springer, Heidelberg (2005).https://doi.org/10.1007/11535218_33
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_1
Matsumoto, T., Takashima, Y., Imai, H.: On seeking smart public-key-distribution systems. IEICE Trans. (1976–1990)69(2), 99–106 (1986)
Menezes, A., Qu, M., Vanstone, S.: Some new key agreement protocols providing implicit authentication. In: Workshop on Selected Areas in Cryptography (SAC 1995), pp. 22–32. CRC Press (1995)
Menezes, A., Ustaoglu, B.: On reusing ephemeral keys in Diffie-Hellman key agreement protocols. Int. J. Appl. Cryptography2(2), 154–158 (2010)
Okada, S., Wang, Y., Takagi, T.: Improving key mismatch attack on NewHope with fewer queries. Cryptology ePrint Archive, Report 2020/585 (2020)
Peikert, C.: Lattice cryptography for the internet. In: Mosca, M. (ed.) PQCrypto 2014. LNCS, vol. 8772, pp. 197–219. Springer, Cham (2014).https://doi.org/10.1007/978-3-319-11659-4_12
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_24
Qin, Y., Cheng, C., Ding, J.: An efficient key mismatch attack on the NIST third round candidate Kyber. Cryptology ePrint Archive, Report 2019/1343 (2019)
Qin, Y., Cheng, C., Zhang, X., Pan, Y., Hu, L., Ding, J.: A systematic approach and analysis of key mismatch attacks on lattice-based NIST candidate KEMs. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13093, pp. 92–121. Springer, Cham (2021).https://doi.org/10.1007/978-3-030-92068-5_4
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC 2005, pp. 84–93. ACM (2005)
Schwabe, P., Stebila, D., Wiggers, T.: Post-quantum TLS without handshake signatures. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 1461–1480 (2020)
Schwabe, P., Stebila, D., Wiggers, T.: More efficient post-quantum KEMTLS with pre-distributed public keys. In: Bertino, E., Shulman, H., Waidner, M. (eds.) ESORICS 2021. LNCS, vol. 12972, pp. 3–22. Springer, Cham (2021).https://doi.org/10.1007/978-3-030-88418-5_1
Seyhan, K., Nguyen, T.N., Akleylek, S., Cengiz, K., Islam, S.H.: Bi-GISIS KE: modified key exchange protocol with reusable keys for IoT security. J. Inf. Secur. Appl.58, 102788 (2021)
Veitch, S.: Improved key reuse attack implementation.https://git.uwaterloo.ca/ssveitch/improved-key-reuse. Accessed May 2021
Wang, Q., Wang, D., Cheng, C., He, D.: Quantum2FA: Efficient Quantum-Resistant Two-Factor Authentication Scheme for Mobile Devices. IEEE Trans. Dependable Secure Comput. (Early Access) (2021).https://ieeexplore.ieee.org/document/9623421
Zhang, J., Zhang, Z., Ding, J., Snook, M., Dagdelen, Ö.: Authenticated key exchange from ideal lattices. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 719–751. Springer, Heidelberg (2015).https://doi.org/10.1007/978-3-662-46803-6_24
Zhang, X., Cheng, C., Ding, R.: Small leaks sink a great ship: an evaluation of key reuse resilience of PQC third round finalist NTRU-HRSS. In: Gao, D., Li, Q., Guan, X., Liao, X. (eds.) ICICS 2021. LNCS, vol. 12919, pp. 283–300. Springer, Cham (2021).https://doi.org/10.1007/978-3-030-88052-1_17
Acknowledgments
The research in this paper was partially supported by the National Natural Science Foundation of China (NSFC) under Grant no 62172374. Y. Pan was supported by the National Key Research and Development Program of China (No. 2018YFA0704705) and NSFC (No. 62032009). Y. Q and J. D would like to thank CCB Fintech Co. Ltd for partially sponsoring the work (No. KT2000040). Nina Bindel was supported by Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2016-05146, NSERC Discovery Accelerator Supplement grant RGPIN-2016-05146, and Contract 2L 165-180499/001/sv, “PQC Analysis”, funded by Public Works and Government Services Canada.
Author information
Authors and Affiliations
China University of Geosciences, Wuhan, 430074, China
Yue Qin, Ruoyu Ding & Chi Cheng
State Key Laboratory of Cryptology, P.O. Box 5159, Beijing, 100878, China
Yue Qin, Ruoyu Ding & Chi Cheng
SandboxAQ, Palo Alto, CA, USA
Nina Bindel
Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
Yanbin Pan
Yau Mathematical Sciences Center, Tsinghua University, Beijing, China
Jintai Ding
Ding Lab, Yanqi Lake Beijing Institute of Mathematical Sciences and Applications, Beijing, China
Yue Qin & Jintai Ding
- Yue Qin
You can also search for this author inPubMed Google Scholar
- Ruoyu Ding
You can also search for this author inPubMed Google Scholar
- Chi Cheng
You can also search for this author inPubMed Google Scholar
- Nina Bindel
You can also search for this author inPubMed Google Scholar
- Yanbin Pan
You can also search for this author inPubMed Google Scholar
- Jintai Ding
You can also search for this author inPubMed Google Scholar
Corresponding authors
Correspondence toChi Cheng orNina Bindel.
Editor information
Editors and Affiliations
Rutgers University, Newark, NJ, USA
Vijayalakshmi Atluri
Hamad Bin Khalifa University, Doha, Qatar
Roberto Di Pietro
Technical University of Denmark, Kongens Lyngby, Denmark
Christian D. Jensen
Technical University of Denmark, Kongens Lyngby, Denmark
Weizhi Meng
A Parameter Choices in the Improved Attack Against DXL-KE
A Parameter Choices in the Improved Attack Against DXL-KE
1.1A.1 The Choices of k for Absolute Value Recovery
Recall that\({{\textbf {K}}}_B = {\textbf {P}}_A {\textbf {s}}_B+ 2{\textbf {g}}_B = k{\textbf {s}}_B+ 2{\textbf {g}}_B \). Hence,\( |k{\textbf {s}}_B[i]| - |2{\textbf {g}}_B[i]| \le |{\textbf {K}}_B[i]| \le |k{\textbf {s}}_B[i]| + |2{\textbf {g}}_B[i]|. \) Moreover, if\(|{\textbf {K}}_B[i]| < \left\lfloor \frac{q}{4}\right\rfloor \) the corresponding signal is 0, and the signal is 1 if\(\left\lceil \frac{q}{4}\right\rceil< |{\textbf {K}}_B[i]| < \left\lfloor \frac{3q}{4}\right\rfloor \). Thus, a signal is zero in a stable region if
and 1 in a stable region if
We start with the first targeted signal (0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1). When\(|{\textbf {s}}_B[i]| \leqslant 7\), the corresponding signal\(\omega _B[i]\) is in the stable region of 0, otherwise\(\omega _B[i]\) is in the stable region of 1. Thus, according to Equation (7), we need to choose\(k_1\) such that\( k_1 < (\left\lfloor \frac{q}{4}\right\rfloor - |2{\textbf {g}}_B[i]|) / 7.\) When\(7<|{\textbf {s}}_B[i]| \leqslant 15\), based on Equation (8), we need to choose\(k_1\) such that\((\left\lceil \frac{q}{4}\right\rceil + |2{\textbf {g}}_B[i]|) / 8< k_1 < ( \left\lfloor \frac{3q}{4}\right\rfloor - |2{\textbf {g}}_B[i]| ) / 15.\) Combing the above two results, we have
For\(k_2\), the corresponding targeted signal is (0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0) as\(|{\textbf {s}}_B[i]|\) increases from 0 to 15. From our observation, we know that the signal is always 0 when\(|{\textbf {s}}_B[i]|\) increases from 0 to 3, and when\(|{\textbf {s}}_B[i]| \geqslant 12\). Based on Equation (7), we have\((\left\lceil \frac{3q}{4}\right\rceil + |2{\textbf {g}}_B[i]|) / 12< k_2 < (\left\lfloor \frac{q}{4}\right\rfloor - |2{\textbf {g}}_B[i]|) / 3. \) When\(4 \leqslant |{\textbf {s}}_B[i]| \leqslant 11\), the signal changes to 1. Thus, by Equation (8),\((\left\lceil \frac{q}{4}\right\rceil + |2{\textbf {g}}_B[i]|) / 4< k_2 < (\left\lfloor \frac{3q}{4}\right\rfloor - |2{\textbf {g}}_B[i]|) / 11.\) Then we conclude that
For\(k_3\), when\(|{\textbf {s}}_B[i]|\) increases from 0 to 15, the corresponding targeted signal is (0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1). Similarly to before, we conclude that
For parameters of DXL-KE, this means concretely\(k_1 \in (515.88, 580.86)\),\(k_2 \in (1031.75, 1114.36)\),\(k_3 \in (3805.57, 4066)\), and\(k_4 \in (7921.93, 8464.07)\). Consequently, we select\(k_1=550\),\(k_2=1,050\),\(k_3=4,000\), and\(k_4=8,192\).
1.2B.2 The Choices of k in Sign Recovery
In Sect. 4, we follow a similar way as previously to determine the ranges of\(k_1,k_2,k_3,k_4,k_5\). The corresponding targeted signals and chosen\(k_j\)’s are given in Table 4. We choose them depending on the following requirements for\(k_j\):
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Qin, Y., Ding, R., Cheng, C., Bindel, N., Pan, Y., Ding, J. (2022). Light the Signal: Optimization of Signal Leakage Attacks Against LWE-Based Key Exchange. In: Atluri, V., Di Pietro, R., Jensen, C.D., Meng, W. (eds) Computer Security – ESORICS 2022. ESORICS 2022. Lecture Notes in Computer Science, vol 13554. Springer, Cham. https://doi.org/10.1007/978-3-031-17140-6_33
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-031-17139-0
Online ISBN:978-3-031-17140-6
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative