Analysis and Improvement of Public Key Reuse for A RLWE Key Exchange Protocol

doi:10.3969/j.issn.1671-1122.2020.11.011

Abstract

Abstract:

Aiming at the long-term and unchanged characteristics of the public key in the 0-RTT mode under the secure transport layer protocol, the attacker can repeatedly use the public key to query a key exchange protocol based on error coordination, obtain the effective information and calculate the crack private key. Combining the feature that the modulus is even in the BCNS15 protocol and different error coordination functions, this article proposes an attack scheme that can crack the private key information. The solution infers the private key by analyzing the information leaked in the protocol and completes the attack. According to the different conditions given in the protocol, the article gives corresponding attack schemes, and reduces the number of queries. After an example test, this attack scheme can successfully recover private keys of the key exchange protocol.

Key words: key exchange, learning with errors, information leakage, active attack, key reuse

CLC Number:

TP309

DUAN Xiaowei, HAN Yiliang, WANG Chao, LI Zhe. Analysis and Improvement of Public Key Reuse for A RLWE Key Exchange Protocol[J]. Netinfo Security, 2020, 20(11): 87-94.

Figures/Tables 2

References 17

[1]	DIFFIE W. New Direction in Cryptography[J]. IEEE Transactions on Information Theory, 1976,22(6):644-654. doi: 10.1109/TIT.1976.1055638 URL
[2]	SHOR P W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J]. Siam Review, 1999,41(2):303-332. doi: 10.1137/S0036144598347011 URL
[3]	DEVORET M H, SCHOELKOPF R J. Superconducting Circuits for Quantum Information: An Outlook[J]. Science, 2013,339(6124):1169-1174. URL pmid: 23471399
[4]	MOSCA M. Cybersecurity in an Era with Quantum Computers: Will We Be Ready?[J]. IEEE Security & Privacy, 2018,16(5):38-41.
[5]	BERNSTEIN D J. Introduction to Post-quantum Cryptography[J]. Post-Quantum Cryptography. 2009,1(1):1-14.
[6]	AJTAI M. Generating Hard Instances of Lattice Problems[C]//ACM. Proceedings of the 28th Annual ACM Symposium on Theory of Computing, May 22-24, Philadelphia, Pennsylvania. New York: ACM, 1996: 99-108.
[7]	REGEV O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[J]. Journal of the ACM, 2009,56(6):1-40.
[8]	LYUBASHEVSKY V, PEIKERT C, REGEV O. On Ideal Lattices and Learning with Errors over Rings[J]. Lecture Notes in Computer Scinence, 2010,6110(1):1-23.
[9]	PEIKERT C. Public-key Cryptosystems from the Worst-case Shortest Vector Problem[C]//ACM. Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, May 31-June 2, 2008, Bethesda, Maryland, New York: ACM, 2009: 333-342.
[10]	DING Jintai, XIE Xiang, LIN Xiaodong. A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem[EB/OL]. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.303.3765&rank=1, 2020-7-22.
[11]	PEIKERT C. Lattice Cryptography for the Internet[C]// Springer. International Workshop on Post-quantum Cryptography. October 1-3, 2014. Waterloo, ON, Canada. Berlin: Springer, 2014: 197-219.
[12]	BOS J W, COSTELLO C, NAEHRIG M, et al. Post-quantum Key Exchange for the TLS Protocol from the Ring Learning with Errors Problem[C]//IEEE. 2015 IEEE Symposium on Security and Privacy. May 21, 2015, San Jose, California. New Jersey: IEEE, 2015: 553-570.
[13]	ALKIM E, DUCAS L, POPPELMANN T, et al. Post-quantum Key Exchange-A New Hope[C]//USENIX. USENIX Security Symposium, August 10-12, 2016, Austin, TX, Berkeley: USENIX, 2016: 327-343.
[14]	FLUHRER S. Cryptanalysis of Ring-LWEBased Key Exchange with Share Reuse[J] Cryptology Eprint Archive, 2016,16(85):1-6.
[15]	DING Jintai, ALSAYIGH S, SARASWATHY R V, et al. Leakage of Signal Function with Reused Keys in RLWE Key Exchange[C]//IEEE. IEEE International Conference on Communications. May 21-25, Paris, France. New Jersey: IEEE, 2017: 1-6.
[16]	DING Jintai, FLUHRER S, RV S. Complete Attack on RLWE Key Exchange with Reused Keys, Without Signal Leakage[C]//Springer. Australasian Conference on Information Security and Privacy. July 11-13, 2018, Wollongong, Australia. New York: Springer, 2018: 467-486.
[17]	ZHANG Jiang, ZHANG Zhenfeng, DING Jintai, et al. Authenticated Key Exchange from Ideal Lattices[C]// Springer: Annual International Conference on the Theory and Applications of Cryptographic Techniques. April 26-30, 2015, Berlin, Heidelberg. New York: Springer, 2015: 719-751.