Cryptology ePrint Archive: Report 2017/1185

Complete Attack on RLWE Key Exchange with reused keys, without Signal Leakage

Jintai Ding and Scott Fluhrer and Saraswathy RV

Abstract: Key Exchange (KE) from RLWE (Ring-Learning with Errors) is a potential alternative to Diffie-Hellman (DH) in a post quantum setting. Key leakage with RLWE key exchange protocols in the context of key reuse has already been pointed out in previous work. The Signal leakage attack relies on changes in the signal sent by the responder reusing his key, in a sequence of key exchange sessions initiated by an attacker with a malformed key. A possible defense against this attack would be by requiring the initiator of the key exchange to send the signal, which is the one pass case of the KE protocol. The initial attack described bu Fluhrer is designed in such a way that it only works on Peikertís KE protocol and its variants that derives the shared secret from the most significant bits of the approximately equal keys computed by both parties. It does not work on the Dingís key exchange that uses the least significant bits to derive a shared key. In this work, we describe a new attack on Dingís one pass case without relying on the signal function output but using only the information of whether the final key of both parties agree. We also use LLL reduction to make the adversaryís keys random looking to the party being compromised. This completes the series of attacks on RLWE key exchange with key reuse for all variants in both cases of the initiator and responder sending the signal. This work shows that when a party fixes their public key for a long term, the protocol can always be broken by a malicious user. Moreover, we show that the previous Signal leakage attack can be made more efficient with fewer queries and how it can be extended to Peikertís key exchange, which was used in the BCNS implementation and integrated with TLS and a variant used in the New Hope implementation.

Category / Keywords: RLWE, key exchange, post quantum, key reuse, active attacks.

Date: received 4 Dec 2017, last revised 8 Dec 2017

Contact author: jintai ding at gmail com;rvsaras86@gmail com

Available format(s): PDF | BibTeX Citation

Note: modified abstract to remove cite commands

Version: 20171212:140719 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]