You are looking at a specific version 20171212:140719 of this paper. See the latest version.

Paper 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.

Note: modified abstract to remove cite commands

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
RLWEkey exchangepost quantumkey reuseactive attacks.
Contact author(s)
jintai ding @ gmail com;rvsaras86 @ gmail com
History
2018-04-25: revised
2017-12-12: received
See all versions
Short URL
https://ia.cr/2017/1185
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.